On Finding the Best Partial Multicast Protection Tree Under Dual-homing Architecture

Document Type

Conference Proceeding

Publication Date


Publication Title

2005 Workshop on High Performance Switching and Routing, HPSR 2005



First page number:


Last page number:



In this paper, we introduce the concept of partial protection and propose an efficient solution for providing partial multicast protection given the dual-homing architecture in the access network. In the dual-homing architecture, each destination is connected to two edge routers to enhance the survivability in the access network. The routing algorithm which finds a path from the source to each edge router holds the key for the multicast protection. We study the problem of finding the best partial multicast protection tree for the multicast session given the dual-homing architecture assuming that the hop count on each path is limited. We show the NP-completeness of the problem and propose the partition and sharing (PAS) algorithm to solve the problem efficiently. Simulation results show that the PAS algorithm achieves performance very close to the computed lower bounds. The solution proposed in this paper fills the gap between traditional 100% protection and non-protection subject to single link failure.


Computer architecture; Computer science; Electronic mail; High definition video; Hydrogen; Multicast algorithms; Partitioning algorithms; Protection; Routing; Videoconference


Computer and Systems Architecture | Computer Engineering | Controls and Control Theory | Digital Communications and Networking | Electrical and Computer Engineering | Electrical and Electronics | Electronic Devices and Semiconductor Manufacturing | Hardware Systems | Signal Processing | Systems and Communications




Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library