NDLI: Linear time construction of redundant trees for recovery schemes enhancing QoP and QoS

Content Provider	IEEE Xplore Digital Library
Author	Zhang, W. Xue, G. Tang, J. Thulasiraman, K.
Copyright Year	2005
Description	Author affiliation: Dept. of Comput. Sci. & Eng., Arizona State Univ., Tempe, AZ, USA (Zhang, W.; Xue, G.; Tang, J.)
Abstract	Medard, Finn, Barry and Gallager proposed an elegant recovery scheme (known as the MFBG scheme) using redundant trees. Xue, Chen and Thulasiraman extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric of multifailure recovery capabilities for single failure recovery schemes. In this paper, we present three linear time algorithms for constructing redundant trees for single link failure recovery in 2-edge connected graphs and for single node failure recovery in 2-connected graphs. Our first algorithm aims at high QoP for single link recovery schemes in 2-edge connected graphs. The previous best algorithm has a running time of O(n/sup 2/(m+n)), where n and m are the number of nodes and links in the network. Our algorithm has a running time of O(m+n), with comparable performance. Our second algorithm aims at high QoS for single link recovery schemes in 2-edge connected graphs. Our algorithm improves the previous best algorithm with O(n/sup 2/(m+n)) time complexity to O(m+n) time complexity with comparable performance. Our third algorithm aims at high QoS for single node recovery schemes in 2-connected graphs. Again, our algorithm improves the previous best algorithm with O(n/sup 2/(m+n)) time complexity to O(m+n) time complexity with comparable performance. Simulation results show that our new algorithms outperform previously known linear time algorithms significantly in terms of QoP or QoS, and outperform other known algorithms in terms of running time, with comparable QoP of QoS performance.
Starting Page	2702
Ending Page	2710
File Size	1899714
Page Count	9
File Format	PDF
ISBN	0780389689
ISSN	0743166X
DOI	10.1109/INFCOM.2005.1498553
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-03-13
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Protection Tree graphs Quality of service Computer science SONET High-speed networks WDM networks Wavelength division multiplexing Solids
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in