Monday, April 30, 2007

vanity, all is vanity, or else its strings, that's my theory

grauniad
podcast of april 2007
with me in....lord knows why:)

So the musical intro was "interesting" - allegedly, Bowie's Jean Genie (sic) was based on the life of Jean Genet (bit of a reach that - but possible - there was a ballet called our lady of the flowers based on work of Jean Genet which used a bunch of 1970s glam rock, and was choreographed by Lindsay Kemp a while back, and he's a Bowie chum according to fanzines of the time. However, I don't see many netheads or internet geeks knowing that (I do, but I am extremely weird (TM)). Also, as i said, its spelled wrong. Also, I dont know if US congress would like being associated with a notorious french
convicted murderer who wrote rather louche poetry and was extremely aggressively gay (hey, not me that has a problem, but just pointing out some un-reconstructed reborn americans might have "issues"), and was really championed by some rather weird french (freedom) fried people like Sartre....

Perhaps we should ask the guardian to podcast the song by Brian Quinn written for the American Medical Association, about Henrik Celine in his Golden Submarine, out to catch the Illuminati. After all, there's just as good a link to technology, and its got all sorts of other nice associations including the barking mad Ken Campbell's Liverpool Science Fiction Theatre's non stop 8 hour production of the Illuminatus Trilogy, but I can't recall what this has to do with GENI. Oh yes, GENI in the LAMP; LAMP Illuminates; illuminati; imanantize the eschaton; QED.

meanwhile,
some folks
say that there's this rule about prime producers, secondary snesationalists and couch potatoes - while this observation might be historically right, the lowering of the barrier to entry by things like garageband+myspace, or youtube+webcams, shifts the distribution in favour of more people contributing. Note Bene - shifting the distribution beyond a certain point may result in a phase shift or emergent property - for example if the distribution causes tipping of the market towards a change in "ownership laws" or there are "flash creationists" or some other new-scary-thing happens that will delight and discombobulate us.
meanwhile, here's a mad idea: can we model wireless mobile ad hoc networks using
String Theory?

go on: you know it makes sense: you saw it here first.

Saturday, April 28, 2007

just one pixel, but 1 billion pounds?

so everyone knows the million pound web page where the guy sold
pixels for a pound each...
and very imaginative it was too...

so i'm interestged in a 1 pixel sale - how many different ways could i
sell a single pixel (lets cheat a bit and make it 24 bit trucolor)

over space (it could be different depending whoo looks at it from what
IP address dmain, it could be _overlayed, or xord with some or all
pixels on another page)
over time - can i sell it for a period, meaningfully - is there some
neat dutch or english auction i can run

can i create a schedule so that the use of the single pixel plus its
sequene of values might be nice

can i write a game based on a single pixel

are there steganographic ways to use the pixel, or covert signaling,
or can i combine all the above

suggestions on a (1 pel) postcard...

hawks and doves and ()rational game theory

mort gave me this paper to read about how hawks often win arguments with doves in a level playing field - essentially, this can be considered as a weighted game, so it could be easily accounted for in various first strike, prisoner's dilemma, iterated/cooperative and non-cooperative games.

It also accoutns for how Programme Cttes often seem to hear out the people arguing to keep a paper out of a conference than those arguing in favour of keeping the paper in. Interestingly (unsurprisingly?) telling people this (that combative is more likely to sway people than passivity) is not sufficient to get them to adjust their influencability....so I guess what we need is a passive aggresive counter strike:)

Tuesday, April 24, 2007

democracy in wireless action:bluemuting and powerpoinlessness

so here's two ideas for democray in wireless nets

1. in a meeting in stead of having 1. a power struggle for plugging in laptops to mains, and 2. a power struggle getting your laptop to talk to the projector, or to the session chair's USB memory stick to then transfer tyo her laptop to plug into the VGA( Daft bloody cable, almost as bad as SCART), why not have the projector have WiFi (some do, but of course, be aware of the alleged health risks:-). and then have it understand a simple protocol (e.g. VNC) and then give people a USB memory stick with an autoexect program which, when they THINK they are transferfring trheir PPT to the memory stick, atually sends it over the wifi to the "shared space" and then lets anyone project it over wifi and then there would be a "floor control" protocol to says who actually has the projector output "channel" (i.e. the floor) right now - in really exciting meetings, severa prople could scribble at once on the visiable version of th shared space

2. voting to turn off people's phones/noise on laptops - all machines should advertise the ring tone.mode they are in (including windows boot songs) and then people in a room can click on an icon to vote to turn off the soun - if enough people vote (e.g. 2, or say (n+1)/2) to turn it off, off it goes...
til they are out of bluetooth/wifi range

bluemuting:)

nash equilibrium

sitting in Regents Park on sunday in the beautiful weather, i reached a Nash Equilibrium - the Terrace, the Ogden and the Game were all peaking - to take anythign away from any one of them and give to another would have been so unfair...

Wednesday, April 18, 2007

shared media denial of service based scheduler

so if we have a shared medium wireless net, we could arrange for a bunch of senders to send "busy idle" traffic (instead of doing some central scheduler) on a set of periodic frequcnies that are distributed over time such that the channel has effectively infinite variance use. in this case someone wishing to use it is dened any useful service unless they first ask one of the senders to give up their channel, and then get that instead to send on - the idea is that I have to pay someone out of the current "incumbents" to stop sending, so I can - this has two effects
1. the payment is distributed
2. cheating is very very hard

this can be done with fairly poor clocks, since the timescales i am talkign about are TCP retransmit/rtt estimation, or RTP playout buffer estimation algorithm times - so we can make the channel effecttiley useles for anythign other than 1 shot traffic (which is allowed as it is used to request capacity off of another sender by a newbie) because the algorithms would be completely screwed up by the jitter from waiting for a non busy channel....(note it isn';t really "busy" but it looks like it is)....

safety in randomness?

Wednesday, April 11, 2007

Electronic voting systems & other NSDI 07 fun and games

NSDI07 in Cambridge, MA, USA,
is very good. I just saw a neat talk at NSDI by Ron Rivest on the problems and some suggested solutions for electronic voting systems - seemed to me his ThreeBallot system (and some others) are amenable to horrible denial of service attacks on the integrity check (brings whole new power to the ballot spoiler) but I need to go check this more carefully.

On the other hand, why prop up an outmoded form of government like democracy? its like trying to build computer systems that use 25% less power, when we are still expanding the number of cars on the planet at the same rate as PCs:)

Meanwhile, I notice a surprising number of people here are
1) not using MACs
2) are using Windows (XP!)
for an allegedly "systems" conference!!!

wouldn't it be cool to survey OSDI, NSDI, PLDI, HOT*, SOSP, SIGCOMM, INFOCOM for OS/laptop preferences...

First paper
Do Incentives Build Robustness in BitTorrent?

Michael Piatek, Tomas Isdal, Thomas Anderson, and Arvind Krishnamurthy
is clueful work on fixing incentives more carefuly in p2p systems like bittorrent.(won student paper award) - very solid work - bittyrant client well worth a looksee.
anyone using up v. down link strategies should look at this work (e.g. also applies in MANET, DTN, as well as pdp)...

2nd paper
Exploiting Similarity for Multi-Source Downloads Using File Handprints



Himabindu Pucha, Purdue University; David G. Andersen, Carnegie Mellon University; Michael Kaminsky, Intel Research Pittsburgh
is on finding common sub-parts of common downloads for multi-source download using handprints - looking like rabin fingerprint things done elsewhere...but applied to source selection - solid engineering research. This paper also made the
bbc news website the same day!



3rd paper
Cobra: Content-based Filtering and Aggregation of Blogs and RSS Feeds
Ian Rose, Rohan Murty, Peter Pietzuch, Jonathan Ledlie, Mema Roussopoulos, and Matt Welsh,
on aggregating blog/rss feed (argh - am I being aggregated as I speak:)
peter pietzuch was a co author, so essentially this is a mash up of blog/rss with pub/sub/event/notify, and nicely done...very large reduction in bandwidth (as you'd expect given how daft RSS is and how good systems like Siena are) - useful to fix the naivite of RSS, though - either to reduce server load, or improve latency/timeliness!

4th paper
Information Slicing: Anonymity Using Unreliable Overlays
Sachin Katti, Jeff Cohen, and Dina Katabi,
looks rather like Eternity done via Ron with onion routing...! but nice systems paper - definitely worth a read if you want to see how to put all the ideas together in an elegant fashion - Sachin did his usual very fine laid back, but humerous and clear presentation which is a relief from the typical rather over zealous and aggresive MIT thang:)

5th paper is


SAAR: A Shared Control Plane for Overlay Multicast
Animesh Nandi, Rice University and Max Planck Institute for Software Systems; Aditya Ganjam, Carnegie Mellon University; Peter Druschel, Max Planck Institute for Software Systems; T.S. Eugene Ng, Rice University; Ion Stoica, University of California, Berkeley; Hui Zhang, Carnegie Mellon University; Bobby Bhattacharjee, University of Maryland



is what to do if no-one deploys multicast ever (unlike now, then:-), and everyone wants 1 way to do multicast (unlike now, then:-) workmanlike proposal/eval...I'm still waiting for someone to do a decent architecture that uses wide area native IP multicast AND P2P, where appropriate - its non trivial due to the potential overlap



Ricochet: Lateral Error Correction for Time-Critical Multicast
Mahesh Balakrishnan and Ken Birman, Cornell University; Amar Phanishayee, Carnegie Mellon University; Stefan Pleisch, Cornell University


moving to a new model of time critical....this was a sideways look at the Reliable Multicast space - PGM has hooks in it to do this sort of thing, but was never (to my knowledge) engineered to use them so its nice to see how to, especially from folks that have been doing quality RM work since day zero!


Next, wireless networky stuff:-

WiLDNet: Design and Implementation of High Performance WiFi Based Long Distance Networks
Rabin Patra and Sergiu Nedevschi, University of California, Berkeley, and Intel Research, Berkeley; Sonesh Surana, University of California, Berkeley; Anmol Sheth, University of Colorado, Boulder; Lakshminarayanan Subramanian, New York University; Eric Brewer, University of California, Berkeley, and Intel Research, Berkeley

so the reason this is cool is that they basically bring together a number of modest changes to 802.11, which all combined let you run it over 100km (40m) and sort out a few problems with interference and fairness...its based on a real empirical set of results so pretty much more than plausible, but is probably not the kiss of dfeath to Wimax just yet...of course, I joked that this only works in california as the air is so rarified, and it wouldn't have a hope in the East Coast:)



S4: Small State and Small Stretch Routing Protocol for Large Wireless Sensor Networks
Yun Mao, University of Pennsylvania; Feng Wang, Lili Qiu, and Simon S. Lam, The University of Texas at Austin; Jonathan M. Smith, University of Pennsylvania


this really does what it says on the tin - use theory in practice...worth a read if you've seen the small stretch theory papers and want to see how to use them in anger - also nice to see JMS is back in action!


A Location-Based Management System for Enterprise Wireless LANs
Ranveer Chandra, Jitendra Padhye, Alec Wolman, and Brian Zill, Microsoft Research

nice practical results for the problem statement in the title...I guess this will show up in Vista SP2:-)



Poster session:- ones I talked to:


The Case for Conditional Link Metrics and Routing
Saumitra M. Das, Purdue University; Yunnan Wu and Ranveer Chandra, Microsoft Research, Redmond; Y. Charlie Hu, Purdue University

neat way of unifying several ideas under one hat! inclouded network coding and interference (as effective shadow price routing) - several of the ideas are well known, but combining them in thie iead (metric for a link is metric conditional on some other link metric - useful for MANETs, Net Coded, multi-path etc etc - main question is how do you actually know the priors, i.e. in many cases the implication is that there is additional link state info distributed (ok if your routing protocol is a link state flooding protocol, but not so great for distance vector...or proactive manet)


Lighweight OS Support for a Scalable and Robust Virtual Network Infrastructure
Sapan Bhatia, Marc Fiuczynski, Andy Bavier, and Larry Peterson, Princeton University and

Network Troubleshooting: An In-band Approach
Murtaza Motiwala, Georgia Institute of Technology; Andy Bavier, Princeton University; Nick Feamster, Georgia Institute of Technology

were both Vini related ones and i talked about using xen/xorp instead of quagga/click...we (CAM CL ) need to talk to these guys about our xen/xorp work...

there were a lot of other good posters but i didn't manage to talk to them much aside from Marcel Dischinger (who interned in the lab 2 years back, and is now at MPI with Peter Druschel) - his poster was on DSL measurements:


day 2:-
Tolerating Faults and Misbehavior


Beyond One-Third Faulty Replicas in Byzantine Fault Tolerant Systems
Jinyuan Li, VMware, Inc.; David Mazières, Stanford University

defines a new model of consistency ("Fork* consistency") which allows one to consider execution sequences with more than 1/3 of replicas being malicious - requires careful consideration of separation of concerns of consistency, correctness, and eventual completion, under certain specific partition cases....don't have time to think it through here - sounds important and useful (can we use it in p2p/manet/dtn too = not sure we need to as we can triangulate bad guys geographically and contain them?).


Ensuring Content Integrity for Untrusted Peer-to-Peer Content Distribution Networks
Nikolaos Michalakis, Robert Soulé, and Robert Grimm, New York University


attestation based system (viz reputations) in decentralised way...


TightLip: Keeping Applications from Spilling the Beans
Aydan R. Yumerefendi, B


not h/w, not language, and not taint track - but slight change to OS to have shadow process....which is a doppelganger...sounds a lot like what Sugih Jamin did way back for shadowing execution in game servers (with compresed execution state) and also how the euro black hat guys deconstructed skype. also, the assertaion on slowness of tain is a bit outta date i think..


Network Measurement

Peering Through the Shroud: The Effect of Edge Opacity on IP-Based Client Identification
Martin Casado and Michael J. Freedman, Stanford University


next gen NAT detection, writ large

A Systematic Framework for Unearthing the Missing Links: Measurements and Impact
Yihua He, Georgos Siganos, Michalis Faloutsos, and Srikanth Krishnamurthy, University of California, Riverside

Emulation and Virtualization

The Flexlab Approach to Realistic Evaluation of Networked Systems
Robert Ricci, Jonathon Duerig, Pramod Sanaga, Daniel Gebhardt, Mike Hibler, Kevin Atkinson, Junxing Zhang, Sneha Kasera, and Jay Lepreau, University of Utah


hybridized planetlab + emulab - i.e. use besxt of both worlds - seems sensible...


An Experimentation Workbench for Replayable Networking Research
Eric Eide, Leigh Stoller, and Jay Lepreau, University of Utah


Very amusing talk! and sensible....not sure if its the tool - but we should give them benefit of the doubt...


how many papers on the meta agument "we should do reproduceable research" can be accepted before we start to accept papers that reproduce results ? :-)


Black-box and Gray-box Strategies for Virtual Machine Migration
Timothy Wood, Prashant Shenoy, and Arun Venkataramani, University of Massachusetts Amherst; Mazin Yousif, Intel, Portland


Debugging and Diagnosis

Life, Death, and the Critical Transition: Finding Liveness Bugs in Systems Code
Charles Killian, James W. Anderson, Ranjit Jhala, and Amin Vahdat, University of California, San Diego


model checking - peter sewell might like to look at this !!!


X-Trace: A Pervasive Network Tracing Framework
Rodrigo Fonseca, George Porter, Randy H. Katz, Scott Shenker, and Ion Stoica, University of California, Berkeley

spoke to george porter who has some interesting other work with Randy on energy saving in clusters which is pretty much like Anthony Hylick's stuff, but at a higher level...I guess x-trace is a sort of Magpie type project...


for both these papersmight have been nice to have seen them before the pervasive debugging project!!!


Friday: Global Comprehension for Distributed Replay
Dennis Geels, Google, Inc.; Gautam Altekar, University of California at Berkeley; Petros Maniatis, Intel Research Berkeley; Timothy Roscoe, ETH Zürich; Ion Stoica, University of California at Berkeley



Just caught the tail end of this - seems very neat - again, quite like the replay/rewind stuff in Tim Harris' first version of PDB


Friday, Day 3

Network Localization


Network Coordinates in the Wild
Jonathan Ledlie, Harvard University; Paul Gardner, Aelitis; Margo Seltzer, Harvard University


This reminds me of the work when people looked at how bad early akamai cache selection was at finding the right "locality" releative to a particular client.
But I guess the point here is that they've looked at all the recent techniques and gone a lot further in a "heroic scale" big science way that is a sign of good systems papers these days. As with other recent work on coordinates, the idea is not to get an actual coordinate (in the sense of mapping node location onto the surface of the planet geographically, via some embedding), but to get a system that is useful. So they use a spring model with ageing. Unsurprisingly a DHT is also used. Eval is very thorough.


Octant: A Comprehensive Framework for the Geolocalization of Internet Hosts
Bernard Wong, Ivan Stoyanov, and Emin Gün Sirer, Cornell University


so this paper is actually trying to get a real mapping from IP to geo-location. This is worrying, as we know lots of reasons why this actually only possible for a subset of the net with any degree of reality. So what they do is to interatively reduce errors (i.e. not embedding as primary approach). having done this, they get remarkably good results - although they use planetlab (usual warning) for some eval:(



dFence: Transparent Network-based Denial of Service Mitigation
Ajay Mahimkar, Jasraj Dange, Vitaly Shmatikov, Harrick Vin, and Yin Zhang, The University of Texas at Austin


I really wanted to say "Looking over dFence at networking research"....so basically this is a midbox approach (as opposed to an arbornet front end, or a re-architect the application to be distributed...) and is as such perfectly reasonabl, but there's the deployment argument...worked example was attack mitigation of syn flood. the midboxes need dynamic state management. the eval used IXPs and Xorp:)

R-BGP: Staying Connected in a Connected World
Nate Kushman, Srikanth Kandula, and Dina Katabi, Massachusetts Institute of Technology; Bruce M. Maggs, Carnegie Mellon University


is about pre-cumputing a failover path so that you can forward data WHILE the BGP convergence is happening - i.e. de-couple forwarding and route computation. Gosh, where's that happened before (phone networks? :-) of course, you do need to think about how you install forwarding state for failover path without a routing update...question for me is precisely why there is any outage in a path (or distance)-vector protocol...they look at that - for me, it shouldn't happen.

Mutually Controlled Routing with Independent ISPs
Ratul Mahajan, Microsoft Research; David Wetherall, University of Washington and Intel Research; Thomas Anderson, University of Washington


So I really like this work since it incoproates a very subtle understanding of what revelation is allowed between "competing" ISPs to permit necessary, but sufficient cooperation to get more fine grain control (and convergence) in a policy routing system. As the speaker/author pointed out, the idea applies across many other networked systems (p2p, e-mail, multiple wireless nets) and so is well worth paying attention to - Sid Chau's work in the area is related...

Tesseract: A 4D Network Control Plane
Hong Yan, Carnegie Mellon University; David A. Maltz, Microsoft Research; T.S. Eugene Ng, Rice University; Hemant Gogineni and Hui Zhang, Carnegie Mellon University; Zheng Cai, Rice University


Every aspect of networking that isn't just forwarding the end user data is control. All control is just another problem for distributed computing. This is a mantra in Cambridge, and other places seem to be buying into this - you don't have to go quite so far as Active Nets or Programmable Networks, but treating every aspect (fault diagnosis, routing, traffic engineering, etc etc) as just distributed computing problems like anyhting else (web serving, CDN, email, p2p) is a step in the right direction.