article

Resilience analysis of packet-witched communication networks

Authors:

Michael Duelli,

Ruediger Martin,

Jens MilbrandtAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 6

Pages 1950 - 1963

https://doi.org/10.1109/TNET.2009.2020981

Published: 01 December 2009 Publication History

Abstract

In the presence of local network outages, restoration and protection switching mechanisms redirect the traffic over alternative paths to mitigate the effect of failures. However, some failure combinations still lead to loss of ingress-egress connectivity within a network or to severe congestion due to rerouted traffic. Congestion may also be caused by unexpected traffic shifts due to changed user behavior or due to changes of interdomain routing. This paper presents a framework for the analysis of ingress-egress unavailability and link congestion due to: 1) failures; 2) changes of user behavior; and 3) changed interdomain routing. It proposes algorithms to find the most probable combinations of 1)-3) according to some models, and to evaluate the connectivity and the relative link load of the network under these conditions. We have implemented this concept in a software tool and its visualization of the results leads to a comprehensive view of the network's resilience. It helps to anticipate potential ingress-egress disconnection and congestion before failures and overload occur or before planned modifications (new infrastructure, new routing, new customers) take effect. Thus, it detects weak points in a network, predicts the effectiveness of potential upgrades, and thereby supports careful bandwidth overprovisioning.

References

[1]

S. Bhattacharyya, C. Diot, G. Iannaccone, A. Markopoulou, and C. Chuah, "Service availability in IP networks," Sprint, ATL Res. Rep. RR03-ATL-071888, July 2003.

[2]

S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot, "An approach to alleviate link overload as observed on an IP backbone," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 406-416.

[3]

T. Schwabe and C. G. Gruber, "Traffic variations caused by inter-domain re-routing," presented at the Int. Workshop DRCN, Ischia Island, Italy, Oct. 2005.

[4]

M. Menth, R. Martin, and J. Charzinski, "Capacity overprovisioning for networks with resilience requirements," in Proc. ACM SIGCOMM, Pisa, Italy, Sep. 2006, pp. 87-98.

Digital Library

[5]

L. Shen, X. Yang, and B. Ramamurthy, "Shared risk link group (SRLG)-diverse path provisioning under hybrid service level agreements in wavelength-routed optical mesh networks," IEEE/ACM Trans. Netw., vol. 13, no. 4, pp. 918-931, Aug. 2005.

Digital Library

[6]

J.-P. Vasseur, M. Pickavet, and P. Demeester, Network Recovery, 1st ed. New York: Morgan Kaufmann/Elsevier, 2004.

[7]

B. Mukherjee, Optical WDM Networks, 2nd ed. New York: Springer, 2006.

Digital Library

[8]

G. Iannaccone, C.-N. Chuah, R. Mortier, S. Bhattacharyya, and C. Diot, "Analysis of link failures in an IP backbone," in Proc. ACM SIGCOMM Internet Measure. Workshop, Marseille, France, Nov. 2002, pp. 237-242.

Digital Library

[9]

A. Markopoulou, G. Iannaccone, S. Bhattacharyya, and C.-N. Chuah, "Characterization of failures in an IP backbone," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 2307-2317.

[10]

G. Willems, P. Arijs, W. V. Parys, and P. Demeester, "Capacity vs. availability trade-offs in mesh-restorable WDM networks," presented at the Int. Workshop DRCN, Budapest, Hungary, Oct. 2001.

[11]

H. C. Cankaya, A. Lardies, and G. W. Ester, "A methodology for availability-aware cost modelling of long-haul networks," presented at the Int. SPECTS, San Jose, CA, Jul. 2004.

[12]

S. D. Maesschalck, D. Colle, I. Lievens, M. Pickavet, P. Demeester, C. Mauz, M. Jaeger, R. Inkret, B. Mikac, and J. Derkacz, "Pan-european optical transport networks: An availability-based comparison," Photon. Netw. Commun., vol. 5, no. 3, pp. 203-225, 2005.

[13]

ISO, "ISO/IEC 10589:2002: Intermediate system to intermediate system intra-domain routing information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode network system," ISO 8473, Nov. 1990.

[14]

G. Iannaccone, C.-N. Chuah, S. Bhattacharyya, and C. Diot, "Feasibility of IP restoration in a tier-1 backbone," IEEE Netw., vol. 18, no. 2, pp. 13-19, Mar. 2004.

Digital Library

[15]

B. Fortz, J. Rexford, and M. Thorup, "Traffic engineering with traditional IP routing protocols," IEEE Commun. Mag., vol. 40, no. 10, pp. 118-124, Oct. 2002.

Digital Library

[16]

B. Fortz and M. Thorup, "Robust optimization of OSPF/IS-IS weights," in Proc. INOC, Paris, France, Oct. 2003, pp. 225-230.

[17]

A. Nucci, B. Schroeder, S. Bhattacharyya, N. Taft, and C. Diot, "IGP link weight assignment for transient link failures," presented at the 18th ITC, Berlin, Germany, Sep. 2003, in Proc..

[18]

D. Yuan, "A bi-criteria optimization approach for robust OSPF routing," in Proc. 3rd IEEE Workshop on IPOM, Kansas City, MO, Oct. 2003, pp. 91-98.

[19]

A. Sridharan and R. Guerin, "Making IGP routing robust to link failures," presented at the IFIP-TC6 Netw. Conf. (Networking), ON, Canada, May 2005.

Digital Library

[20]

M. Menth, M. Hartmann, and R. Martin, "Robust IP link costs for multilayer resilience," presented at the IFIP-TC6 Netw. Conf. (Networking), Atlanta, GA, May 2007.

Digital Library

[21]

P. Cholda and A. Jajszczyk, "Availability assessment of resilient networks," in Proc. 12th GI/ITG Conf. Meas., Model. and Eval. Comput. Commun. Syst. (MMB) Together With 3rd PGTS, Dresden, Germany, Sep. 2004, pp. 389-398.

[22]

V. O. K. Li and J. A. Silvester, "Performance analysis of networks with unreliable components," IEEE Trans. Commun., vol. COM-32, no. 10, pp. 1105-1110, Oct. 1984.

[23]

M. Clouqueur and W. D. Grover, "Computational and design studies on the unavailability of mesh-restorable networks," in Proc. Int. Workshop DRCN, Munich, Germany, Apr. 2000, pp. 181-186.

[24]

M. Clouqueur and W. D. Grover, "Availability analysis of span-restorable mesh networks," IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 810-821, May 2002.

Digital Library

[25]

D. A. Schupke and R. G. Prinz, "Capacity efficiency and restorability of path protection and rerouting in WDM networks subject to dual failures," Photon. Netw. Commun., vol. 8, no. 2, pp. 191-207, Sep. 2004.

[26]

M. Menth, R. Martin, and U. Spoerlein, "Impact of unprotected multi-failures in resilient SPM networks: A capacity dimensioning approach," in Proc. IEEE Globecom, San Francisco, CA, Nov. 2006, pp. 1-6.

[27]

W. Najjar and J.-L. Gaudiot, "Network resilience: A mesaure of network fault tolerance," IEEE Trans. Comput., vol. 39, no. 2, pp. 174-181, Feb. 1990.

Digital Library

[28]

J. Milbrandt, R. Martin, M. Menth, and F. Hoehn, "Risk assessment of end-to-end disconnection in IP networks due to network failures," in Proc. 6th IEEE Workshop on IPOM, Dublin, Ireland, Oct. 2006, pp. 181-192.

Digital Library

[29]

P. Cholda and A. Jajszczyk, "Reliability assessment of optical p-cycles," IEEE/ACM Trans. Netw., vol. 15, no. 6, pp. 1579-1592, Dec. 2007.

Digital Library

[30]

M. Durvy, C. Diot, N. Taft, and P. Thiran, "Network availability based service differentiation," in Proc. 11th IEEE IWQoS, Berkeley, CA, 2003, pp. 305-324.

Digital Library

[31]

P. Cholda, A. Mykkeltveit, B. E. Helvik, O. J. Wittner, and A. Jajszczyk, "A survey of resilience differentiation frameworks in communication networks," IEEE Commun. Surveys Tutor., vol. 9, no. 4, pp. 32-55, 2007.

Digital Library

[32]

M. Dahlin, B. B. V. Chandra, L. Gao, and A. Nayate, "End-to-end WAN service availability," IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 300-313, Apr. 2003.

Digital Library

[33]

A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "NetScope: Traffic engineering for IP networks," IEEE Netw., vol. 14, no. 2, pp. 11-19, Mar. 2000.

Digital Library

[34]

R. Keralapura, A. Moerschell, C.-N. Chuah, G. Iannaccone, and S. Bhattacharyya, "A case for using service availability to characterize IP backbone topologies," J. Commun. Netw., vol. 8, no. 2, pp. 241-252, Jun. 2006.

[35]

J. Milbrandt, M. Menth, and F. Lehrieder, "A priori detection of link overload due to network failures," presented at the ITG/GI Conf. Commun. Distrib. Syst. (KiVS), Bern, Switzerland, Feb. 2007.

[36]

SNDlib 1.0--Survivable Network Design Data Library, 2005 {Online}. Available: http://sndlib.zib.de

[37]

M. Duelli, M. Hartmann, M. Menth, R. Hülsermann, and M. Düser, "Performance evaluation of IP over cost-optimized optical multilayer networks with SRLGS," presented at the ITG Workshop on Photon. Netw. Leipzig, Germany, Apr. 2008.

[38]

A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot, "Traffic matrix estimation: Existing techniques and new directions," in Proc. ACM SIGCOMM, Pittsburgh, PA, Aug. 2002, pp. 1-174.

Digital Library

[39]

M. Menth, "Efficient admission control and routing in resilient communication networks," Ph.D. dissertation, Faculty of Comput. Sci., Univ. Würzburg, Am Hubland, Germany, Jul. 2004.

[40]

T. Brinkhoff, "Population of the major cities and agglomerations for each country," 1998-2006 {Online}. Available: http://www.citypopulation. de/

Cited By

Dey PYuksel M(2023)Delegating Data Plane With Cloud-Assisted RoutingIEEE Transactions on Network and Service Management10.1109/TNSM.2023.323980220:3(3190-3204)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3239802
Foerster KKamisiński APignolet YSchmid STredan G(2021)Grafting Arborescences for Extra Resilience of Fast Rerouting SchemesIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488782(1-10)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1109/INFOCOM42981.2021.9488782
Jensen JKrøgh TMadsen JSchmid SSrba JThorgersen MDimitropoulos XDainotti AVanbever LBenson T(2018)P-RexProceedings of the 14th International Conference on emerging Networking EXperiments and Technologies10.1145/3281411.3281432(217-227)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3281411.3281432
Show More Cited By

Index Terms

Resilience analysis of packet-witched communication networks

Recommendations

Resilience in computer systems and networks
ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design

The term resilience is used differently by different communities. In general engineering systems, fast recovery from a degraded system state is often termed as resilience. Computer networking community defines it as the combination of trustworthiness (...
A methodology on MPLS VPN service management with resilience constraints
ISAS'04: Proceedings of the First international conference on Service Availability

Recent advent of broad bandwidth wireless and optical networks makes the resilience of information and communication service to system failures to become a critical issue. In this article, we present a methodology for MPLS VPN service management ...
Multi-Level Resilience: Reconciling Robustness, Recovery and Adaptability from a Network Science Perspective

From a multi-disciplinary point of view, research on resilience focuses on robustness, recovery, and adaptive capacity. Robustness quantifies how much damage a system can take before it breaks, whereas recovery refers to the ability of a system to ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 6

December 2009

331 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2009

Revised: 23 April 2008

Received: 25 May 2007

Published in TON Volume 17, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
297
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dey PYuksel M(2023)Delegating Data Plane With Cloud-Assisted RoutingIEEE Transactions on Network and Service Management10.1109/TNSM.2023.323980220:3(3190-3204)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3239802
Foerster KKamisiński APignolet YSchmid STredan G(2021)Grafting Arborescences for Extra Resilience of Fast Rerouting SchemesIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488782(1-10)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1109/INFOCOM42981.2021.9488782
Jensen JKrøgh TMadsen JSchmid SSrba JThorgersen MDimitropoulos XDainotti AVanbever LBenson T(2018)P-RexProceedings of the 14th International Conference on emerging Networking EXperiments and Technologies10.1145/3281411.3281432(217-227)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3281411.3281432
Borokhovich MPignolet YSchmid STredan G(2018)Load-Optimal Local Fast Rerouting for Dense NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2018.287108926:6(2583-2597)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2871089
Al Muktadir AOki E(2016)A coding-aware reliable route design scheme for instantaneous recoveryTelecommunications Systems10.1007/s11235-015-0089-362:3(495-509)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s11235-015-0089-3
Gardner MMay RBeard CMedhi D(2016)Determining Geographic Vulnerabilities Using a Novel Impact Based Resilience MetricJournal of Network and Systems Management10.1007/s10922-016-9383-y24:3(711-745)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10922-016-9383-y
Braun WMenth M(2016)Loop-Free Alternates with Loop Detection for Fast Reroute in Software-Defined Carrier and Data Center NetworksJournal of Network and Systems Management10.1007/s10922-016-9369-924:3(470-490)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10922-016-9369-9
da Silva ASmith PMauthe ASchaeffer-Filho A(2015)Resilience support in software-defined networkingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.09.01292:P1(189-207)Online publication date: 9-Dec-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.09.012
Qin ZDenker GTalcott CVenkatasubramanian NSastry SBaşar TBushnell LRohrbough L(2013)Achieving resilience of heterogeneous networks through predictive, formal analysisProceedings of the 2nd ACM international conference on High confidence networked systems10.1145/2461446.2461459(85-92)Online publication date: 9-Apr-2013
https://dl.acm.org/doi/10.1145/2461446.2461459
Manzano MCalle ETorres-Padrosa VSegovia JHarle D(2013)EnduranceComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2013.08.01157:17(3641-3653)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.comnet.2013.08.011
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents