Title :
The new shortest best path tree (SBPT) algorithm for dynamic multicast trees
Author :
Fujinoki, Hiroshi ; Christensen, Kenneth J.
Author_Institution :
Dept. of Comput. Sci. & Eng., Univ. of South Florida, Tampa, FL, USA
Abstract :
This paper presents the new shortest best path tree (SBPT) algorithm for multicast trees. The SBPT algorithm establishes and maintains dynamic multicast trees which maximize the bandwidth to be shared by multiple receivers and simultaneously guarantee the shortest paths for each receiver node. The SBPT algorithm is a distributed algorithm with cost in the same order as the sum of the shortest path tree (SPT) and Greedy algorithms. The SBPT algorithm reduces bandwidth consumption by utilizing partial paths already established for other multicast receiver nodes. The SBPT algorithm finds such partial paths when multiple shortest paths exist. Simulation experiments comparing the SBPT and SPT algorithms show that the SBPT algorithm reduces bandwidth consumption by 5% to 17% when node utilization is greater than approximately 25% and always achieves the same shortest path lengths
Keywords :
digital simulation; distributed algorithms; multicast communication; network routing; receivers; telecommunication network routing; trees (mathematics); Greedy algorithm; SBPT algorithm; SPT algorithm; bandwidth consumption reduction; bandwidth sharing; distributed algorithm; dynamic multicast trees; end-to-end delay control; multicast receiver nodes; multicast routing algorithm; multiple receivers; node utilization; partial paths; shortest best path tree algorithm; shortest path lengths; shortest path tree algorithm; simulation experiments; Bandwidth; Computer science; Costs; Delay effects; Greedy algorithms; Heuristic algorithms; Maintenance engineering; Multicast algorithms; Routing; Surface-mount technology;
Conference_Titel :
Local Computer Networks, 1999. LCN '99. Conference on
Conference_Location :
Lowell, MA
Print_ISBN :
0-7695-0309-8
DOI :
10.1109/LCN.1999.802017
