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

Authors

Mei Yang, University of Nevada, Las VegasFollow
Jianping Wang, Chongqing UniversityFollow
Xiangtong Qi
Yingtao Jiang, University of Nevada, Las VegasFollow

Document Type

Conference Proceeding

Publication Date

5-12-2005

Publication Title

2005 Workshop on High Performance Switching and Routing, HPSR 2005

Publisher

IEEE

First page number:

128

Last page number:

132

Abstract

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.

Keywords

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

Disciplines

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

Language

English

Permissions

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.

Repository Citation

Yang, M., Wang, J., Qi, X., Jiang, Y. (2005). On Finding the Best Partial Multicast Protection Tree Under Dual-homing Architecture. 2005 Workshop on High Performance Switching and Routing, HPSR 2005 128-132. IEEE.