The highlight of the DIMACS workshop on designing networks for manageability for me was Nick Duffield‘s talk on characterizing IP flows at network scale. The basic idea is to use machine learning to identify the flow predicates that best reproduce packet-level classifications. By sampling flows according to a simple dynamical weighting, Duffield et al. demonstrate that this sort of flow classification is accurate (to a few percent, with the misclassifications largely due to overloading of HTTP, e.g., with media over web), scalable (i.e., faster than real-time), versatile (i.e., independent of the particular ML classifier), and stable (over space and time, with a deployment on a separate but similar network producing essentially equivalent results over several months). This work is more recent than related research we’ve cited in our whitepaper “Scalable visual traffic analysis” (on our downloads page) detailing the rationale behind our own traffic aggregation methods.
Much of the workshop (especially its first day) was more focused on current deployment and engineering issues than I would have thought for an overarching focus on “algorithmic foundations of the internet”. Both another mathematician that came with me and I expected to see some work on (or at least suggesting the use of) sparse linear algebra to deal with traffic matrices. I was surprised not to see anyone talk about some kind of agent-based configuration methods for networks–this sort of approach has been used to great effect on hosts.
But there were a number of other talks I found interesting: Aditya Akella from Wisconsin talked about an entropy characterization of “reachability sets” describing packets that can be sent between pairs of routers based on their configurations, and used this to construct a routing complexity measure for networks. Dan Rubenstein from Columbia talked about a “canonical graph” method for efficiently detecting misconfigurations for routing protocols. Iraj Saniee talked about why networks are globally hyperbolic (using a result of Gromov’s well-known work on groups), a conclusion that seems intuitively obvious to me if the existence of a global curvature (bound) is assumed. (Basically a network spreads out if it’s drawn in any reasonable way, and hyperbolic geometry amounts to expansion.)
Mung Chiang from Princeton talked about the results in “Link-State Routing with Hop-by-Hop Forwarding Can Achieve Optimal Traffic Engineering” first presented at INFOCOM 2008. He and coworkers perturb assumptions behind routing protocols to obviate the need for hard optimization problems (i.e., computation of optimal link weights to input to OSPF is NP-hard, but changing OSPF can make the corresponding optimization problem easier). From what I could tell OSPF corresponds to a “zero-temperature” protocol, whereas the improved protocol corresponds to a “finite-temperature” one.
Michael Schapira from Yale and Berkeley talked about game-theoretic and economic perspectives on routing. It is a happy “accident” that the internet is BGP stable (usually, although a notable event where a Pakistani ISP set all its hop counts to 1 some time ago created a routing “black hole”). Although ISPs are selfish, economic considerations tend to result in stability. But that’s not a guarantee. So Schapira and coworkers analyzed the situation and found that “interdomain routing with BGP is a game” in which the ASes are the players, the BGP stable states are pure Nash equilibria, and BGP is the “best response“. I mentioned to him that the “accidental” nature of this stablity is likely due to reciprocity, in that an ISP that discovers one of its neighbors engaging in predatory routing is likely to retaliate in the future. I think the use of economic and game theory is generally a good idea. An emphasis of the economics of cybercrime has developed recently, and understanding the market forces at play here and elsewhere is likely to lead to improvements in the reliability and security of networks.
