A Comparative Study ofTwo Multicast Routing Algorithms
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
This Master Thesis examines several aspects of two different multicast forwarding algorithms. The scaling properties of the currently used algorithms were examined under different criteria, such as delay, traffic concentration, and size of the routing tables.
Many new Internet applications, such as videoconferencing, resource discovery, Internet radio and online games, depend on a network support for efficient point-to-multipoint communication. Sending identical data to a group of receivers using a series of unicast transmissions obviously has massive scaling problems. Multicasting provides an efficient and elegant solution that significantly reduces the total bandwidth demand as well as the load on both senders and intermediate routers.
In this report we study two multicast routing algorithms, source based trees (SBT) and core based trees (CBT). SBT builds one delivery tree per source and group by flooding the initial packet through the entire network, and then removing the links that do not lead to group members (“pruning”). To be able to discover new members, flooding must occur periodically. CBT on the other hand, builds one delivery tree per group, shared by all sources. There is one core router per group and members must explicitly join the delivery tree by notifying the core. Off-tree sources must tunnel their traffic to the core for distribution along the tree.
SBT has two main drawbacks. Firstly, the maintenance of the delivery tree requires periodic flooding of the network. Furthermore, SBT routers must keep state that grows as the product of the number of sources and the number of groups. CBT solves both of these scaling problems, but the shared tree will often lead to sub-optimal paths and increased delay. The traffic may also be concentrated on fewer links than in SBT.
We compared the characteristics of the SBT and CBT algorithms in different network topologies using a simulation program. Since existing network simulation tools were found to be poor when it came to multicasting, we decided to develop a new network generator and simulator tool with multicasting aspects in focus. We also developed a tool to visualize the networks generated by the simulator and monitor the traffic. The report presents many simulation results that illustrate the significance of different trade-offs between SBT and CBT. Performance characteristics such as delay, join latency, tree size, total traffic and traffic concentration are analysed and examined.
The conclusion is that each protocol can be preferable in certain scenarios, depending on how important the different parameters are. CBT always performs better than SBT for single source applications if the core can be placed at the sender’s local router. However, this core placement is not necessarily optimal for CBT. The situation is more complex in groups with several sources. There is a trade-off between the scaling problems of SBT and the increased delay and traffic concentration of CBT.
Place, publisher, year, edition, pages
2002. , 112 p.
IdentifiersURN: urn:nbn:se:kth:diva-93199OAI: oai:DiVA.org:kth-93199DiVA: diva2:515365
2002-12-06, Seminar room "Gemini", Forum, Isafjordsgatan 39, Kista, 11:00 (English)
Maguire Jr., Gerald Q., professorJohnsson, Martin
Maguire Jr., Gerald Q., professor