Name
Abstract | ||
|---|---|---|
The Internet's routing system is facing stresses due to its poor fundamental scaling properties. Compact routing is a research field that studies fundamental limits of routing scalability and designs algorithms that try to meet these limits. In particular, compact routing research shows that shortest-path routing, forming a core of traditional routing algorithms, cannot guarantee routing table (RT) sizes that on all network topologies grow slower than linearly as func- tions of the network size. However, there are plenty of com- pact routing schemes that relax the shortest-path require- ment and allow for improved, sublinear RT size scaling that is mathematically provable for all static network topologies. In particular, there exist compact routing schemes designed for grids, trees, and Internet-like topologies that offer RT sizes that scale logarithmically with the network size. In this paper, we demonstrate that in view of recent re- sults in compact routing research, such logarithmic scaling on Internet-like topologies is fundamentally impossible in the presence of topology dynamics or topology-independent (flat) addressing. We use analytic arguments to show that the number of routing control messages per topology change cannot scale better than linearly on Internet-like topologies. We also employ simulations to confirm that logarithmic RT size scaling gets broken by topology-independent address- ing, a cornerstone of popular locator-identifier split propos- als aiming at improving routing scaling in the presence of network topology dynamics or host mobility. These pes- simistic findings lead us to the conclusion that a fundamen- tal re-examination of assumptions behind routing models and abstractions is needed in order to find a routing archi- tecture that would be able to scale "indefinitely." |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1273445.1273450 | acm special interest group on data communication |
Keywords | Field | DocType |
routing scaling,shortest-path routing,network size,compact routing,compact routing scheme,traditional routing algorithm,compact routing research,routing architecture,routing scalability,routing system,internet-like topology,internet routing,shortest path,network topology,algorithms,design | Link-state routing protocol,Multipath routing,Dynamic Source Routing,Computer science,Enhanced Interior Gateway Routing Protocol,Policy-based routing,Hierarchical routing,Static routing,Computer network,Routing table,Distributed computing | Journal |
Volume | Issue | ISSN |
37 | 3 | ACM SIGCOMM Computer Communication Review (CCR), v.37, n.3,
p.41-52, 2007 |
Citations | PageRank | References |
66 | 3.45 | 26 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dmitri Krioukov | 1 | 1138 | 90.70 |
| k c claffy | 2 | 509 | 73.77 |
| Kevin R. Fall | 3 | 5687 | 625.48 |
| Arthur Brady | 4 | 103 | 6.38 |