[talks] Brighten Godfrey talk on Distributed Compact Routing Thrus 3pm

[Nicole E. Wagenblast]

Title: Distributed Compact Routing
Speaker: Brighten Godfrey, UIUC
Time: 3pm, Thursday, Feb 4th
Room: CS 302

Abstract:

Common wisdom is that the way to scale networks to large size is hierarchy: 
routing is performed on higher level aggregates across domains, separately from 
routing within domains.  We live with the consequences: inflated path lengths, 
and the use of location-dependent addresses (IP addresses in the Internet) 
which complicate management, mobility, and multihoming.

I will present Distributed Compact Routing, a protocol which (1) guarantees 
scalability, in the form of roughly \sqrt{n} state for a network of n nodes; 
(2) guarantees approximately-shortest paths, in the form of constant stretch; 
and (3) routes directly on flat, location-independent identifiers.  Our work 
builds on recent theoretical advances in the area of compact routing. Past 
attempts to translate these centralized algorithms to practical distributed 
protocols have had limited success, compromising state or stretch guarantees or 
assuming special topologies. Our results thus represent a significant step 
forward in routing technology, which we believe has direct applicability to 
many kinds of networks including peer-to-peer networks, Internet routing, and 
content-centric networks.

Joint work with Ankit Singla, Kevin Fall, Gianluca Iannaccone, and Sylvia 
Ratnasamy.