Different algorithms for normal and protection paths

Rajarshi Gupta; E. Chi; J. Walrand

doi:10.1109/DRCN.2003.1275356

Different algorithms for normal and protection paths

Rajarshi Gupta
, E. Chi
, J. Walrand

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

Many network routing situations commonly require backup paths that satisfy various constraints on bandwidth, link or node selection, and ease of configuration. In this paper, we attempt to validate whether it is beneficial to have distinct algorithmic treatments of normal and backup path calculation, configuration and maintenance. We present a modular suite of algorithms that enable us to manage normal and protection paths differently. We incorporate a distributed algorithm to separately calculate normal and backup paths in the network, using link state information, and present an evaluation of asynchronous dynamic reorganization of backup paths to reduce congestion in the network. Simulations demonstrate quantitative reductions in blocking probabilities under certain conditions. We conclude that in order to choose an optimal algorithm for a protected QoS routing application, it is recommended to also consider a combination of two different algorithms for normal and backup paths.

Original language	English (US)
Title of host publication	Proceedings - 4th International Workshop on Design of Reliable Communication Networks
Subtitle of host publication	Design and Management of Highly Reliable Networks and Services, DRCN 2003
Editors	Mike MacGregor
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	189-196
Number of pages	8
ISBN (Electronic)	0780381181, 9780780381186
DOIs	https://doi.org/10.1109/DRCN.2003.1275356
State	Published - 2003
Externally published	Yes
Event	4th International Workshop on Design of Reliable Communication Networks, DRCN 2003 - Banff, Canada Duration: Oct 19 2003 → Oct 22 2003

Publication series

Name	Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003

Conference

Conference	4th International Workshop on Design of Reliable Communication Networks, DRCN 2003
Country/Territory	Canada
City	Banff
Period	10/19/03 → 10/22/03

Bibliographical note

Publisher Copyright:
© 2003 IEEE.

Keywords

Algorithm design and analysis
Analytical models
Bandwidth
Computer networks
Distributed algorithms
Multiprotocol label switching
Optical fiber networks
Probability
Protection
Routing protocols

Publisher link

10.1109/DRCN.2003.1275356

Find It

Find It at U of M Libraries

Cite this

Gupta, R., Chi, E., & Walrand, J. (2003). Different algorithms for normal and protection paths. In M. MacGregor (Ed.), Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003 (pp. 189-196). Article 1275356 (Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/DRCN.2003.1275356

Different algorithms for normal and protection paths. / Gupta, Rajarshi; Chi, E.; Walrand, J.
Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003. ed. / Mike MacGregor. Institute of Electrical and Electronics Engineers Inc., 2003. p. 189-196 1275356 (Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Gupta, R, Chi, E & Walrand, J 2003, Different algorithms for normal and protection paths. in M MacGregor (ed.), Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003., 1275356, Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003, Institute of Electrical and Electronics Engineers Inc., pp. 189-196, 4th International Workshop on Design of Reliable Communication Networks, DRCN 2003, Banff, Canada, 10/19/03. https://doi.org/10.1109/DRCN.2003.1275356

Gupta R, Chi E, Walrand J. Different algorithms for normal and protection paths. In MacGregor M, editor, Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003. Institute of Electrical and Electronics Engineers Inc. 2003. p. 189-196. 1275356. (Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003). doi: 10.1109/DRCN.2003.1275356

Gupta, Rajarshi ; Chi, E. ; Walrand, J. / Different algorithms for normal and protection paths. Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003. editor / Mike MacGregor. Institute of Electrical and Electronics Engineers Inc., 2003. pp. 189-196 (Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003).

@inproceedings{ca5065d893a843ea89af76696a73af7c,

title = "Different algorithms for normal and protection paths",

abstract = "Many network routing situations commonly require backup paths that satisfy various constraints on bandwidth, link or node selection, and ease of configuration. In this paper, we attempt to validate whether it is beneficial to have distinct algorithmic treatments of normal and backup path calculation, configuration and maintenance. We present a modular suite of algorithms that enable us to manage normal and protection paths differently. We incorporate a distributed algorithm to separately calculate normal and backup paths in the network, using link state information, and present an evaluation of asynchronous dynamic reorganization of backup paths to reduce congestion in the network. Simulations demonstrate quantitative reductions in blocking probabilities under certain conditions. We conclude that in order to choose an optimal algorithm for a protected QoS routing application, it is recommended to also consider a combination of two different algorithms for normal and backup paths.",

keywords = "Algorithm design and analysis, Analytical models, Bandwidth, Computer networks, Distributed algorithms, Multiprotocol label switching, Optical fiber networks, Probability, Protection, Routing protocols",

author = "Rajarshi Gupta and E. Chi and J. Walrand",

note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 4th International Workshop on Design of Reliable Communication Networks, DRCN 2003 ; Conference date: 19-10-2003 Through 22-10-2003",

year = "2003",

doi = "10.1109/DRCN.2003.1275356",

language = "English (US)",

series = "Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "189--196",

editor = "Mike MacGregor",

booktitle = "Proceedings - 4th International Workshop on Design of Reliable Communication Networks",

}

TY - GEN

T1 - Different algorithms for normal and protection paths

AU - Gupta, Rajarshi

AU - Chi, E.

AU - Walrand, J.

PY - 2003

Y1 - 2003

N2 - Many network routing situations commonly require backup paths that satisfy various constraints on bandwidth, link or node selection, and ease of configuration. In this paper, we attempt to validate whether it is beneficial to have distinct algorithmic treatments of normal and backup path calculation, configuration and maintenance. We present a modular suite of algorithms that enable us to manage normal and protection paths differently. We incorporate a distributed algorithm to separately calculate normal and backup paths in the network, using link state information, and present an evaluation of asynchronous dynamic reorganization of backup paths to reduce congestion in the network. Simulations demonstrate quantitative reductions in blocking probabilities under certain conditions. We conclude that in order to choose an optimal algorithm for a protected QoS routing application, it is recommended to also consider a combination of two different algorithms for normal and backup paths.

AB - Many network routing situations commonly require backup paths that satisfy various constraints on bandwidth, link or node selection, and ease of configuration. In this paper, we attempt to validate whether it is beneficial to have distinct algorithmic treatments of normal and backup path calculation, configuration and maintenance. We present a modular suite of algorithms that enable us to manage normal and protection paths differently. We incorporate a distributed algorithm to separately calculate normal and backup paths in the network, using link state information, and present an evaluation of asynchronous dynamic reorganization of backup paths to reduce congestion in the network. Simulations demonstrate quantitative reductions in blocking probabilities under certain conditions. We conclude that in order to choose an optimal algorithm for a protected QoS routing application, it is recommended to also consider a combination of two different algorithms for normal and backup paths.

KW - Algorithm design and analysis

KW - Analytical models

KW - Bandwidth

KW - Computer networks

KW - Distributed algorithms

KW - Multiprotocol label switching

KW - Optical fiber networks

KW - Probability

KW - Protection

KW - Routing protocols

UR - https://www.scopus.com/pages/publications/84945901077

UR - https://www.scopus.com/pages/publications/84945901077#tab=citedBy

U2 - 10.1109/DRCN.2003.1275356

DO - 10.1109/DRCN.2003.1275356

M3 - Conference contribution

AN - SCOPUS:84945901077

T3 - Proceedings - 4th International Workshop on Design of Reliable Communication Networks: Design and Management of Highly Reliable Networks and Services, DRCN 2003

SP - 189

EP - 196

BT - Proceedings - 4th International Workshop on Design of Reliable Communication Networks

A2 - MacGregor, Mike

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 4th International Workshop on Design of Reliable Communication Networks, DRCN 2003

Y2 - 19 October 2003 through 22 October 2003

ER -

Different algorithms for normal and protection paths

Abstract

Publication series

Conference

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this