𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Worst Case Bounds for Shortest Path Interval Routing

✍ Scribed by Cyril Gavoille; Eric Guévremont

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
285 KB
Volume
27
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

Consider shortest path inter¨al routing, a popular memory-balanced method for Ž . solving the routing problem on arbitrary networks. Given a network G, let IRS G denote the maximum number of intervals necessary to encode groups of destinations on an edge, minimized over all shortest path interval routing schemes on G.

Ž . In this paper, we establish tight worst case bounds on IRS G . More precisely for Ž . Ž . any n, we construct a network G of n nodes with IRS G g ⌰ n , thereby Ž . improving on the best known lower bound of ⍀ nrlog n . We also establish a worst case bound on bounded degree networks: for any ⌬ G 3 and any n, we Ž . construct a network G of n nodes and maximum degree ⌬ with IRS G g ⌬ ⌬ Ž Ž . 2 . ⍀ nr log n .

📜 SIMILAR VOLUMES

Lower bounds for linear interval routing
Lower bounds for linear interval routing
✍ Eilam, T.; Moran, S.; Zaks, S. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB 👁 2 views

Linear interval routing is a space-efficient routing method for point-to-point communication networks. It is a restricted variant of interval routing where the routing range associated with every link is represented by an interval with no wraparound. A common way to measure the efficiency of such ro

A scalable multicast routing protocol fo
A scalable multicast routing protocol for building shortest path trees
✍ Baoxian Zhang; Jun Zheng; Hussein T. Mouftah 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB 👁 1 views

## Abstract Scalability is a great concern in the design of multicast routing protocols for the global Internet. Building shortest path trees (SPT) is currently one of the most widely used approaches to supporting multicast routing because of the simplicity and low per‐destination cost of such tree

A lower bound for interval routing in ge
A lower bound for interval routing in general networks
✍ Tse, Savio S. H.; Lau, Francis C. M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

Interval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of t