✦ LIBER ✦

A lower bound for interval routing in general networks

✍ Scribed by Tse, Savio S. H.; Lau, Francis C. M.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 109 KB
Volume: 29
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199701)29:1<49::aid-net5>3.0.co;2-c

No coin nor oath required. For personal study only.

✦ Synopsis

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 the graph with intervals. An optimal labeling would result in routing of messages through the shortest paths. Optimal labelings have existed for regular as well as some of the common topologies, but not for arbitrary graphs. In fact, it has already been shown that it is impossible to find optimal labelings for arbitrary graphs. In this paper, we prove a 7D/4 0 1 lower bound for interval routing in arbitrary graphs, where D is the diameter-i.e., the best any interval labeling scheme could do is to produce a longest path having a length of at least 7 D/4 0 1.

📜 SIMILAR VOLUMES

Lower bounds for linear interval routing

✍ Eilam, T.; Moran, S.; Zaks, S. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB 👁 1 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 lower bound for groupies in graphs

✍ Mackey, John 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contai

A new proximal decomposition algorithm f

A new proximal decomposition algorithm for routing in telecommunication networks

✍ Mahey, P.; Ouorou, A.; LeBlanc, L.; Chifflet, J. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 1 views

We present a new and much more efficient implementation of the proximal decomposition algorithm for routing in congested telecommunication networks. The routing model that we analyze is a static one intended for use as a subproblem in a network design context. After describing our new implementation

A proposal of a greedy neural network fo

A proposal of a greedy neural network for route assignments in multihop radio networks

✍ Takayuki Baba; Nobuo Funabiki; Seishi Nishikawa 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 240 KB

In a radio communications network, all of the nodes cannot communicate with each other directly. Then packets are transferred from a source node to a destination node through several nodes. Therefore, we need to schedule transfer timing at each node, and communications routes must be assigned to min

A practical method for analysis of river

A practical method for analysis of river waves and for kinematic wave routing in natural channel networks

✍ T. Moramarco; V. P. Singh 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

The behaviour of river waves is described using a simpli®ed dimensionless form of the momentum equation in conjunction with the continuity equation. Three dimensionless parameters were derived based on a quantitative linear analysis. These parameters, which depend on the Froude number of the steady

Using a simple algorithm and platform in

Using a simple algorithm and platform in optical DWDM networks for reaching a satisfactory wavelength-routing assignment

✍ Abelardo Podcameni; Joseuda Lopes 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views