Abstract
As the communication lines and switching hardware in distributed networks become much faster, a new trend of algorithms is needed to utilize it. Traditional broadcast algorithm send one packet along each communication line at a time, and propagate it by replicating and sending it on all the outgoing lines. This method does not use the high bandwidth or the switching hardware, and it overloads the processor. Our routing algorithms send several packets simultaneously on one communication line, and each packet is sent along a linear route. In this paper we assume that the switching hardware has limited strength. We present algorithms that compute an optimal broadcast routing, using a bounded number of linear routes. We prove that a greedy algorithm solves the problem, and present an improved algorithm for the same problem.
(Extended Abstract)
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
A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley. June 1976,pp. 97–99.
S. Bitan and S. Zaks, Optimal Linear Broadcast, Technion — Israel Institute of Technology, Department of Computer Science, Technical Report # 623, May 1990.
C.T. Chou and I.S. Gopal, Linear Broadcast Routing, Journal of Algorithms, Vol 10(4), 1989, pp.490–517.
I. Cidon and I.S. Gopal, PARIS: An Approach to Private Integrated Networks, Journal of Analog and Digital Cabled Systems, June 1988.
I. Cidon, I.S. Gopal and S. Kutten, New Models and Algorithms for Future networks, Proceedings of the 7'th Annual ACM Symposium on Principles of Distributed Computing, Toronto, CANADA, August 1988, pp. 75–89.
R. Cohen and A. Segall, A Distributed Query Protocol For High-Speed Networks, Proceedings of the 9'th International Conference on Computers and Communication, Tel-Aviv, ISRAEL, October 1987, pp. 299–302.
A. Segall, Distributed Networks Protocols, IEEE Trans. on Information Theory, IT-29(1), January 1983, pp. 23–35.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bitan, S., Zaks, S. (1990). Optimal linear broadcast. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_86
Download citation
DOI: https://doi.org/10.1007/3-540-52921-7_86
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52921-7
Online ISBN: 978-3-540-47177-6
eBook Packages: Springer Book Archive