Abstract
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 wrap-around. A common way to measure the efficiency of such routing methods is in terms of the maximal length of a path a message traverses. For Interval Routing the upper bound and lower bound on this quantity are 2D and 1.75D — 1, respectively, where D is the diameter of the network. We prove a lower bound of Ω(D2) on the length of a path a message traverses under Linear Interval Routing. We further extend the result by showing a connection between the efficiency of Linear Interval Routing and the bi-diameter of the network.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bakker, E.M., van Leeuwen, J., Tan, R.B.: Prefix Routing Schemas in Dynamic Networks. Tech. Rep. RUU-CS-90-10, Dept. of Computer science, Utrecht University, Utrecht (1990).
Bakker, E.M., van Leeuwen, J., Tan, R.B.: Linear Interval Routing. Algorithms Review 2 (1991) 45–61.
Dinitz, Y., Private communication.
Even, S.: Graph Algorithms. Computer Science Press, Inc., (1979).
Eilam, T., Moran, S., Zaks, S.: Bi-Diameter in 2-Edge-Connected Graphs. In preparation.
Fraigniaud, P., Gavoile, C.: Interval Routing Schemes. Research Rep. 94-04, LIPS-ENS Lyon (1994).
Li, Q., Sotteau, D., Xu, J.: 2-Diameter of De Bruijn Networks. Rapport de Recherche 950, Universite de Paris Sud, centre d'Orsay, Laboratoire de Recherche en Informatique, 91405 Orsay, France (1995).
van Leeuwen, J., Tan, R.B.: Routing with Compact Routing Tables. Tech. Rep. RUU-CS-83-16, Dept. of Computer Science, Utrecht University (1983). Also as: Computer Networks with Compact Routing Tables. In: G. Rozenberg and A. Salomaa (Eds.) The book of L, Springer-Verlag, Berlin (1986) 298–307.
van Leeuwen, J., Tan, R.B.: Computer Network with Compact Routing Tables. In: G. Rozenberg and A. Salomaa (Eds.), The Book of L., Springer-Verlag, Berlin (1986) 259–273.
Ružička, P.: A Note on the Efficiency of an Interval Routing Algorithm. The Computer Journal 34 (1991) 475–476.
Santoro, N., Khatib, R.: Routing Without Routing Tables. Tech. Rep. SCS-TR-6, School of Computer Science, Carleton University (1982). Also as: Labeling and Implicit Routing in Networks. The Computer Journal 28 (1) (1985) 5–8.
Santoro, N., Khatib, R.: Labeling and Implicit Routing in Networks. The Computer Journal, 28 (1) (1985) 5–8.
Tse, S. S.H., Lau, F. C.M.: A Lower Bound for Interval Routing in General Networks. Tech. Rep. TR-94-09, Department of Computer Science, University of Hong Kong (1994).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eilam, T., Moran, S., Zaks, S. (1996). A lower bound for Linear Interval Routing. In: Babaoğlu, Ö., Marzullo, K. (eds) Distributed Algorithms. WDAG 1996. Lecture Notes in Computer Science, vol 1151. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61769-8_13
Download citation
DOI: https://doi.org/10.1007/3-540-61769-8_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61769-3
Online ISBN: 978-3-540-70679-3
eBook Packages: Springer Book Archive