Distributed construction of resource-efficient overlay tree by approximating MST

Abstract

This thesis describes the design, simulation, and evaluation of a distributed routing protocol called RESMO (Resource-Efficient Scalable Multicast Overlay) for constructing overlay tree to support video streaming applications. RESMO reduces network resource usage by approximating MST and achieves low end-to-end latency between the sender and each receiver at the same time. The resulting overlay is a compromise between minimum spanning tree and shortest path tree.RESMO is a mesh-first protocol -- nodes in RESMO maintains a mesh and the overlay tree is build on top of the mesh. The tree is constructed in a stepwise manner initiated from the sender. The end-to-end latency is dynamically measured as overlay edge weight during tree construction process. Each end host in the multicast group only maintains states for a small number of neighbors and uses soft-states to keep them up to date. In order to adapt to network conditions and group membership changes, the tree is reconstructed periodically without hanging data transmission.We evaluated the tree constructed by RESMO through simulations and compared it with NICE and Narada application-layer multicast protocols, minimum spanning tree, shortest path tree on the same network scenarios. Simulation results support that RESMO gives significant improvement over existing protocols in terms of link stress, relative delay penalty and resource usage.