Technical Report CS0623

Authors: s. Bitan and S. Zaks
Abstract: As the communication lines and switching hardware in disoibuted 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 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. algorithms that compute
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion