TY - GEN
T1 - Efficient construction of virtual p-cycles protecting all cycle-protectible working links
AU - Xue, Guoliang
AU - Gottapu, R.
PY - 2003
Y1 - 2003
N2 - It has been shown that p-cycles, proposed by W.D. Grover and D. Stamatelakis (see Proc. ICC'98, p.537-43, 1998), have great potential in link restoration in IP networks in the event of single link failure. However, previously published schemes for computing p-cycles are time consuming and do not guarantee protection against every cycle-protectible working link. We say a working link connecting nodes u and v is cycle-protectible if there exists a simple cycle of spare links that contains both u and v. We present an efficient algorithm for constructing cycles made of spare links such that every cycle-protectible working link is protected by one of the cycles. For a network with n nodes and m spans, our algorithm runs in O(n·(n+m)) time to construct O(m) cycles and to associate each working link to one of the cycles. We then extend our scheme to provide protection for every protectible working link, where a working link connecting nodes u and v is protectible if there exists a u-v path of spare links that does not use the span between u and v. To the best of our knowledge, our scheme is the first that guarantees protection of every cycle-protectible working link. The previous best algorithm requires O(nm3) time for computing a single p-cycle, which is a factor of O(m2) higher than the time complexity of our algorithm for computing all O(m) p-cycles.
AB - It has been shown that p-cycles, proposed by W.D. Grover and D. Stamatelakis (see Proc. ICC'98, p.537-43, 1998), have great potential in link restoration in IP networks in the event of single link failure. However, previously published schemes for computing p-cycles are time consuming and do not guarantee protection against every cycle-protectible working link. We say a working link connecting nodes u and v is cycle-protectible if there exists a simple cycle of spare links that contains both u and v. We present an efficient algorithm for constructing cycles made of spare links such that every cycle-protectible working link is protected by one of the cycles. For a network with n nodes and m spans, our algorithm runs in O(n·(n+m)) time to construct O(m) cycles and to associate each working link to one of the cycles. We then extend our scheme to provide protection for every protectible working link, where a working link connecting nodes u and v is protectible if there exists a u-v path of spare links that does not use the span between u and v. To the best of our knowledge, our scheme is the first that guarantees protection of every cycle-protectible working link. The previous best algorithm requires O(nm3) time for computing a single p-cycle, which is a factor of O(m2) higher than the time complexity of our algorithm for computing all O(m) p-cycles.
KW - Protection and restoration
KW - p-cycles
KW - single link/node failure
UR - http://www.scopus.com/inward/record.url?scp=57249117078&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57249117078&partnerID=8YFLogxK
U2 - 10.1109/HPSR.2003.1226723
DO - 10.1109/HPSR.2003.1226723
M3 - Conference contribution
AN - SCOPUS:57249117078
SN - 0780377109
SN - 9780780377103
T3 - IEEE International Conference on High Performance Switching and Routing, HPSR
SP - 305
EP - 309
BT - HPSR 2003 - 2003 Workshop on High Performance Switching and Routing
PB - IEEE Computer Society
T2 - 2003 Workshop on High Performance Switching and Routing, HPSR 2003
Y2 - 24 June 2003 through 27 June 2003
ER -