Average stretch analysis of compact routing schemes

DOI10.1016/J.DAM.2006.09.010MaRDI QIDQ875595zbMATH OpenOpenAlexFDO

Authors Tamar Eilam, Cyril Gavoille, David Peleg

Publication date 13 April 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.09.010

zbMATH Keywords

average stretchcompact routing schemesinterval routing schemespivot interval routingstretch factor

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Review text

This paper presents some analytic results concerning the pivot interval routing strategy. That strategy allows message routing on every weighted \(n\)-node network along paths whose stretch (namely, the ratio between their length and the distance between their endpoints) is at most five, and whose average stretch is at most three.

Recommendations

• Compact routing schemes with low stretch factor
• Compact routing schemes with improved stretch
• Improved routing strategies with succinct tables
• Compact routing with minimum stretch
• scientific article; zbMATH DE number 1305414

Cites work

• A survey on interval routing
• A trade-off between space and efficiency for routing tables
• Compact routing schemes with low stretch factor
• Designing networks with compact routing tables
• scientific article; zbMATH DE number 3940741 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1517100 (Why is no real title available?)
• scientific article; zbMATH DE number 1760012 (Why is no real title available?)
• scientific article; zbMATH DE number 4119974 (Why is no real title available?)
• Improved routing strategies with succinct tables
• Labelling and Implicit Routing in Networks
• Memory requirement for routing in distributed networks
• Memory requirement for universal routing schemes
• Multidimensional interval routing schemes
• On the ratio of optimal integral and fractional covers
• Routing with Polynomial Communication-Space Trade-Off
• Space-efficiency for routing schemes of stretch factor three
• Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method
• The Compactness of Interval Routing
• The compactness of interval routing for almost all graphs
• Worst Case Bounds for Shortest Path Interval Routing

Cited in

(2)

• Compact routing schemes with low stretch factor
• Space-efficiency for routing schemes of stretch factor three

This page was built for publication: Average stretch analysis of compact routing schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q875595)