Event
Advanced Networks Colloquium: Timothy Griffin, "Reverse-Engineering Inter-Domain Routing"
Friday, October 28, 2011
11:00 a.m.
1146 A.V. Williams Building
Kimberly Edwards
301 405 6579
kedwards@umd.edu
Advanced Networks Colloquium
What Have We Learned from Reverse-Engineering the Internets Inter-domain Routing Protocol?
Timothy Griffin
University of Cambridge
| video |
Abstract
The Border Gateway Protocol (BGP) is the routing protocol used to stitch together the entire public Internet. BGP has evolved in a very organic way, adapting to changing constraints in a rapidly growing commercial interconnection environment. This leads to the questionWhat type of "path problem" is BGP trying to solve? It turns out that the BGP routing policies used to implement commercial relationships between Internet Service Providers cannot be captured using standard generalizations of shortest-path routing based on semirings and related algebraic structures. However, replacing the notion of "global optima" in semiring-based path problems with "unique local optima" in weakened algebraic structures leads to a new class of path problems. This enables us to solve directly some problems that have previously been tackled only with ad hoc methods in areas as diverse as routing, circuit layout, and scheduling. This talk will not assume any prior knowledge of Inter-domain routing. The results presented are a summary of work done over the last ten years with many collaborators Chi-kin Chau, Lixin Gao, Richard Gibbens, Alexander Gurney, Jennifer Rexford, Bruce Shepherd, Joao Sobrinho, and Gordon Wilfong.
Biography
Timothy G. Griffin has a BS in Mathematics from the University of Wisconsin, Madison, and a PhD in Computer Science from Cornell University. Tim was on the faculty of UNICAMP in Brazil and then a researcher at Bell Laboratories. Since 2005 Tim has been on the faculty of the Computer Laboratory at the University of Cambridge. Tim's recent research has focused on algebraic modeling of Internet routing protocols.
