A lower bound for interval routing in general networks

A lower bound for interval routing in general networks

0.00 Avg rating0 Votes
Article ID: iaor2002392
Country: United States
Volume: 29
Issue: 1
Start Page Number: 49
End Page Number: 53
Publication Date: Jan 1997
Journal: Networks
Authors: ,
Keywords: communication
Abstract:

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 7 D/4 – 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 – 1.

Reviews

Required fields are marked *. Your email address will not be published.