BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Theoretical computer science seminar
SUMMARY:On the Forwarding Paths Produced by Internet Routi
ng Algorithms - Timothy Griffin (Cambridge)
DTSTART:20150925T120000Z
DTEND:20150925T130000Z
UID:TALK1871AT
URL:/talk/index/1871
DESCRIPTION:Most Internet routing protocols have one of two\na
lgorithms lurking at their core — either Dijkstra’
s algorithm\nin the case of link-state protocols o
r a distributed Bellman-Ford\nalgorithm in the cas
e of distance-vector or path-vector protocols.\nWh
en computing simple shortest paths these protocols
can be\nmodified to utilize all best paths with a
combination of nexthop\nsets and Equal Cost Multi
-Path (ECMP) forwarding. We\nshow that this pictur
e breaks down even for simple modifications\nto th
e shortest path metric. This is illustrated with w
idest-shortest\npaths where among all shortest pat
hs only those with\ngreatest bandwidth are conside
red best. In this case Bellman-Ford\nand Dijkstra
may compute different sets of paths and neither\nc
an compute all best paths. In addition\, some path
s computed\nby Dijkstra’s algorithm cannot be impl
emented with next-hop\nforwarding. We provide a ge
neral algebraic model that helps to\nclarify such
anomalies. This is accomplished by computing paths
\nwithin the route metric rather than with special
ized algorithmic\nextensions. Our results depend o
n the distinction between global\nand local optima
that has hitherto been applied almost exclusively
\nto more exotic routing protocols such as BGP.\n\
nThis is joint work with Seweryn Dynerowicz (Unive
rsity of Namur) and\nappeared in ICNP 2013:\nhttp:
//www.cl.cam.ac.uk/~tgg22/publications/dynerowicz_
griffin_icnp_2013.pdf
LOCATION:CS 217
CONTACT:Neel Krishnaswami
END:VEVENT
END:VCALENDAR