on 18-03-2011
João Sobrinho (IST - TU Lisbon / IT).
March 18, 2011, Friday, 16h15m.
Abstract: What is the minimum number of links in a network whose failure interrupts the flow of traffic from a node X to a node Y? If all paths in the network can be used to carry traffic, then Menger’s theorem provides the answer: the minimum number of links whose failure interrupts the flow of traffic from X to Y equals the maximum number of link-disjoint paths from X to Y, a quantity which can be computed in polynomial-time. However, routing policies preclude some paths from carrying traffic. Moreover, these routing policies are substantiated by routing protocols which, alas, discover some paths all the while hiding others. The bottom line is that, in a networking setting, the question above is not answered by Menger’s theorem or any other result from graph theory. We algebraically identify a broad class of routing policies for which we can answer our opening question with a polynomial-time algorithm. Complementarily, we show the counter-intuitive behavior of routing policies that call out of that class. The theory is applied to a public description of the Internet’s topology to quantify how much of its intrinsic connectivity is lost to current routing policies and how much is recovered with simple alternative ones.
Room: 3.10, Mathematics
Support: SQIG/IT with support from FCT and FEDER, namely via the following projects:
* PTDC/MAT/68723/2006 KLog;
* POCI/MAT/55796/2004 QuantLog;
* POSC/EIA/55582/2004 Space-Time-Types