Project Team INRIA: CEPAGE

Author of the post-doctoral research subject: Cyril Gavoille

Title of the post-doctoral research subject: Topology Name-Independent
Routing Schemes

Scientific priorities (cf strategic plan): ?

Scientific Research context (10-15 lines): The Internet routing system
and addressing architecture is facing performance challenges in terms
scalability as well as stability and convergence. Resulting from its
expansion, the Internet routing system has to cope with a growing
number of sites/routes, and autonomous systems along with a steadily
increasing meshedness.  Additionally, topology independent address
prefix allocation (impeding prefix aggregation) as well as existing
solutions to mobility, site multi-homing, and inter-domain traffic
engineering (using address prefix de-aggregation) exacerbate the
limitations of the current routing system. Nowadays, the latter must
not only scale with increasing network size and growth of the Internet
hosts but also with growing set of constraints and functionality.  In
these conditions new routing paradigms compared to the current
(policy-based) shortest path routing shall be investigated that do not
scale proportionally to nlog(n) where n is the number of
nodes/autonomous systems but sub-linearly and at best logarithmically.

Post-doctoral researcher work description (10-15 lines) : The goal of
this work is to design new routing schemes for the Internet with
compact routing tables. The naming system of the routers must be
independent of the underlying topology, while keeping near
shortest-path route length. The scheme must be universal (in the sense
they can apply to any topology) however good performences must be
achieved for some specific topology families (scalefree networks,
hyperbolic toplogies, bounded tree-width networks, etc.). The ultimate
goal will be to make the schemes supporting dynamic topology changes.

Required Knowledge and background: graph algorithms, complexity and
data-structures

References (max 5) :

Marta Arias, Lenore Jennifer Cowen, Kofi Ambrose Laing, Rajmohan
Rajaraman, and Orjeta Taka. Compact routing with name
independence. SIAM Journal on Discrete Mathematics, 20(3):705-726,
2006

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel
Thorup. Compact name-independent routing with minimum stretch. ACM
Transactions on Algorithms, 3(4):Article 37, June 2008

Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch
trade-offs: Lower bounds. In 18th Annual ACM Symposium on Parallel
Algorithms and Architectures (SPAA), pages 217-224. ACM Press, July
2006.

Ittai Abraham and Dahlia Malkhi. Name independent routing for growth
bounded networks. In 17th Annual ACM Symposium on Parallel Algorithms
and Architectures (SPAA), pages 49-55. ACM Press, July 2005.

Goran Konjevod, Andréa Werneck Richa, and Donglin Xia. Dynamic routing
and location services in metrics of low doubling dimension. In 22nd
International Symposium on Distributed Computing (DISC), volume 5218
of Lecture Notes in Computer Science, pages 379-393. Springer,
September 2008.

Keywords (max 5-6): routing tables, compact routing

Duration : 1 or 2 years