𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Shortest-Path Routing in Arbitrary Networks

✍ Scribed by Friedhelm Meyer auf der Heide; Berthold Vöcking

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
197 KB
Volume
31
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We introduce an on-line protocol which routes any set of N packets along shortest paths with congestion C and dilation D through an arbitrary network in Ž . O C q D q log N steps, with high probability. This time bound is optimal up to the additive log N, and it has previously only been reached for bounded-degree leveled networks.

Further, we show that the preceding bound holds also for random routing problems with C denoting the maximum expected congestion over all links. Based on this result, we give applications for random routing in Cayley networks, general node symmetric networks, edge symmetric networks, and de Bruijn networks.

Finally, we examine the problems arising when our approach is applied to routing along non-shortest paths, deterministic routing, or routing with bounded buffers.

📜 SIMILAR VOLUMES

Optimal routing in shortest-path data ne
Optimal routing in shortest-path data networks
✍ K. G. Ramakrishnan; Manoel A. Rodrigues 📂 Article 📅 2002 🏛 Institute of Electrical and Electronics Engineers 🌐 English ⚖ 249 KB 👁 1 views
Shortest path routing and fault-tolerant
Shortest path routing and fault-tolerant routing on de Bruijn networks
✍ Mao, Jyh-Wen; Yang, Chang-Biau 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 170 KB 👁 1 views

In this paper, we study the routing problem for the undirected binary de Bruijn interconnection network. Researchers have never proposed a shortest path routing algorithm on the undirected binary de Bruijn network. We first propose a shortest path routing algorithm, whose time complexity in the bina

Worst Case Bounds for Shortest Path Inte
Worst Case Bounds for Shortest Path Interval Routing
✍ Cyril Gavoille; Eric Guévremont 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 285 KB

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 ro