Abstract: Compact routing schemes were until recently considered as the main alternative to overcome the fundamental scaling limitations of the Internet routing system. Such schemes have been introduced to address the fundamental and unavoidable trade-off between the stretch of a routing scheme and the routing table size it produces. Recent studies have shown that static routing on topology-dependent identifiers (that includes "some" topological information) scales (poly)logarithmically on the number of nodes in scale-free graphs such as the Internet. Nevertheless, evolution of the Internet routing system also demonstrates that i) topology-independence of the numbering scheme becomes a fundamental requirement for e.g. multi-homing, nomadicity, and mobility, and ii) "static" routing is unable to handle dynamic graphs, i.e., routing update messages (triggered by topology-driven, policy-driven, and other protocol-driven events) must be exchanged to timely inform remote routers such that each router maintains a consistent view of the non-local topology.This tutorial starts by reviewing the fundamental dimensions of routing schemes. It then introduces the compact routing theory and its application to scale-free graphs. Next, it describes and analyses the consequences resulting from i) routing on topology-independent numbering space and ii) dynamic routing information exchanges and resulting costs. This tutorial will conclude by outlining the open research coupled-challenges (stretch x routing table size x dynamics) and possible direction(s) to address them.

First part

Second part

Other formats :

• pdf slides
• high quality MPEG4 :part 1 part 2
• medium quality Quicktime : part 1 part 2
• low quality Quicktime : part 1 part 2

This presentation was recorded during the first Trilogy Future Internet summer school held in Louvain-la-Neuve, Belgium in August 2009. The video and the slides are © Dimitri Papadimitriou, 2009. Please contact the author for any republication.