Performance evaluation of multicast routing algorithms to trade-off path length and bandwidth consumption and of a protocol to reduce messaging overhead.

摘要

Multicast applications are growing in popularity in the Internet. Efficient multicast routing algorithms and protocols in both bandwidth consumption and end-to-end delay are needed. There is a need to be able to trade-off delay and bandwidth consumption—no existing algorithm can do this. Being able to trade-off delay and bandwidth consumption will enable better support of delay-constrained and elastic applications. There is also a need to reduce the overhead of probe messages in existing protocols. Existing protocols, such as the Flooding and Distributed Spanning Join (DSJ) protocols, can cause an explosion of probe messages in the Internet, which can congest and overflow protocol processing in routers. In this dissertation, algorithms for generating multicast trees with a trade-off in delay and bandwidth consumption are investigated. The Shortest Best Path Tree (SBPT) and Path Length Control (PLC) algorithms are proposed and evaluated. The SBPT algorithm minimizes bandwidth consumption at the same time paths from a sender to receivers is guaranteed be the shortest. The PLC algorithm builds on the SBPT algorithm by adding non-shortest path routing for lower bandwidth consumption when the shortest path routing is not necessary. Simulation experiments demonstrate that the SBPT algorithm resulted in lower bandwidth consumption compared to the SPT algorithm but with the same shortest path. The PLC algorithm demonstrated that when the path length does not have to be the shortest, up to 21% of bandwidth was saved from the SPT algorithm. In this dissertation, a new Distributed Reverse Path Join protocol is proposed and evaluated. The DRPJ protocol reduced messaging overhead depending on how broad multicast neighbor search should be performed. Compared to the Flooding and DSJ protocols, the DRPJ protocol is shown to reduce the significant amount of messaging overhead (reduced 91% and 42% of messaging overhead of the Flooding and DSJ protocols, respectively) when multicast receivers were sparsely distributed and a multicast sender is located away from network cores. The DRPJ protocol can be implemented in IP networks as an extension of Border Gateway Protocol.