Loading...
Please wait, while we are loading the content...
Similar Documents
On Space-Stretch Trade-Offs: Lower Bounds (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Abraham, Ittai Gavoille, Cyril |
| Abstract | One of the fundamental trade-offs in compact routing schemes is between the space used to store the routing table on each node and the stretch factor of the routing scheme – the ratio between the cost of the route induced by the scheme and the cost of a minimum cost path between the same pair. Using a distributed Kolmogorov Complexity argument, we give a lower bound for the name-independent model that applies even to single-source schemes and does not require a girth conjecture. For any integer k ≥ 1 we prove that any routing scheme for networks with arbitrary weights and arbitrary node names (even a single-source routing scheme) with maximum stretch strictly less than 2k + 1 requires Ω((n log n) 1/k)-bit routing tables. We extend our results to lower bound the average-stretch, showing that for any integer k ≥ 1 any name-independent routing scheme with (n/(9k)) 1/k-bit routing tables has average-stretch of at least k/4 + 7/8. This result is in sharp contrast to recent results on the average-stretch of labeled routing schemes. |
| File Format | |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Fundamental Trade-off Minimum Cost Path Space-stretch Trade-off Recent Result Girth Conjecture Name-independent Routing Scheme Arbitrary Node Name Name-independent Model Routing Scheme K-bit Routing Table Labeled Routing Scheme Bit Routing Table Sharp Contrast Maximum Stretch Single-source Routing Scheme Single-source Scheme Arbitrary Weight Distributed Kolmogorov Complexity Argument Stretch Factor |
| Content Type | Text |
