Further items from the DIMACS workshop

Peter Winzer argued for using (variants of) Valiant's randomized load balancing (route to a random intermediate spot, and go from there to the end destination) as an actual network architecture, over shortest-path and virtual private network methods. And I do mean argued. A heated discussion broke out among various real networking people as to whether this was realistic. The cost of potentially doubling the transport time (speed-of-light time) for say cross-country transmissions was argued to be unacceptable, even if the payoff was essentially zeroing queueing delays and making a simpler, cheaper (less equipment) network. (Perhaps it could be used for smaller networks, or only to/from the center, to avoid doubling cross-country trips.) It was very entertaining and instructive; one of the classis theoretical ideas, an argument about how it could be used and what its benefit could be, and a counterargument based on practical experience, leaving a somewhat vague end result -- you probably can't tell how useful it is until you build it out...

Cristian Estan gave an excellent talk giving an overview of data plane algorithms -- hardware router algorithms for longest matching prefix, string/regexp matching, packet classification/deep packet inspection, etc.

Ho and Sprintson gave their survey on network coding, covering the background, the integrality gap of network coding for undirected networks (Agarwal and Charikar), finding network codes through integer programming for undirected networks, bounds on the number of encoding nodes needed for various graphs, robust network coding in the face of edge failures, practical implementations, and more.