University of Birmingham > Talks@bham > Theoretical computer science seminar > On the Forwarding Paths Produced by Internet Routing Algorithms

## On the Forwarding Paths Produced by Internet Routing AlgorithmsAdd to your list(s) Download to your calendar using vCal - Timothy Griffin (Cambridge)
- Friday 25 September 2015, 13:00-14:00
- CS 217.
If you have a question about this talk, please contact Neel Krishnaswami. Most Internet routing protocols have one of two algorithms lurking at their core — either Dijkstra’s algorithm in the case of link-state protocols or a distributed Bellman-Ford algorithm in the case of distance-vector or path-vector protocols. When computing simple shortest paths these protocols can be modified to utilize all best paths with a combination of nexthop sets and Equal Cost Multi-Path (ECMP) forwarding. We show that this picture breaks down even for simple modifications to the shortest path metric. This is illustrated with widest-shortest paths where among all shortest paths only those with greatest bandwidth are considered best. In this case Bellman-Ford and Dijkstra may compute different sets of paths and neither can compute all best paths. In addition, some paths computed by Dijkstra’s algorithm cannot be implemented with next-hop forwarding. We provide a general algebraic model that helps to clarify such anomalies. This is accomplished by computing paths within the route metric rather than with specialized algorithmic extensions. Our results depend on the distinction between global and local optima that has hitherto been applied almost exclusively to more exotic routing protocols such as BGP . This is joint work with Seweryn Dynerowicz (University of Namur) and appeared in ICNP 2013 : http://www.cl.cam.ac.uk/~tgg22/publications/dynerowicz_griffin_icnp_2013.pdf This talk is part of the Theoretical computer science seminar series. ## This talk is included in these lists:- CS 217
- Computer Science Departmental Series
- Computer Science Distinguished Seminars
- Theoretical computer science seminar
- computer sience
Note that ex-directory lists are not shown. |
## Other listsOptimisation and Numerical Analysis Seminars Nanoscale Physics Seminars Topology and Dynamics Seminar## Other talksStructured Decompositions: recursive data and recursive algorithms The science of the large scale heliosphere and the missions that made it possible How to stratify PSPACE-complete logics into fragments complete for each level of the polynomial time hierarchy? Energy release and transport in solar eruptive events View fusion vis-à-vis a Bayesian interpretation of Black-Litterman for portfolio allocation Advancing biomedical photoacoustic imaging using structured light and optical microresonators |