Scalability of network-failure resilience: analysis using multi-layer probabilistic graphical models

ABSTRACT

In this work, we quantify scalability of network re-silience upon failures. We characterize resilience as the percentage of lost traffic upon failures and define scalability as the growth rate of the percentage of lost traffic with respect to network size, link failure probability, and network traffic for given failure protection schemes. We apply probabilistic graphical models to characterize statistical dependence between physical-layer failures and the net-work-layer traffic, and analyze the scalability for large networks of different topologies.

We first focus on the scalability of resilience for regular topolo-gies under uniform deterministic traffic with independent and de-pendent link failures, with and without protection. For large net-works with small probabilities of failures and without protection, we show that the scalability of network resilience grows linearly with the average route length and with the "effective" link failure probability. For large networks with 1 + 1 protection, we obtain lower and upper bound of the percentage of lost traffic. We de-rive approximations of the scalability for arbitrary topologies, and attain close-form analytical results for ring, star, and mesh-torus topologies. We then study network resilience under random traffic with Poisson arrivals. We find that when the network is under light load, the network resilience is reduced to that under uniform de-terministic traffic. When the network load is under heavy load, the percentage of lost traffic approaches the marginal probability of link failure. Our scalability analysis shows explicitly how network resilience varies with different factors and provides insights for re-silient network design.

REFERENCES

• 1: Report of the National Science Foundation Workshop on Fundamental Research in Networking, Arlington, VA, Apr. 24-25, 2003.
• 2: Y. Liu and K. S. Trivedi, "A general framework for network surviv-ability quantification," presented at the 12th GI/ITG Conf. Measuring, Modeling, and Evaluation of Computer and Communication Systems, Dresden, Germany, Sep. 2004.
• 3: G. Weichenberg, V. Chan, and M. Médard, "High-reliability topo-logical architectures for networks under stress," IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1830-1845, Nov. 2004.
• 4: F. Harary, Graph Theory. Reading, MA: Addison Wesley, Jan. 1995, new education edition.
• 5: J. J. Shi and J. P. Fonseka, "Analysis and design of survivable telecom-munications networks," IEE Proc. Commun., vol. 144, no. 5, pp. 322-330, Oct. 1997.
• 6: T. P. Ng, "K-terminal reliability of hierarchical networks," IEEE Trans. Reliabil., vol. 40, no. 2, pp. 218-225, Jun. 1991.
• 7: J. Zhang and B. Mukherjee, "A review of fault management in WDM mesh networks: Basic concepts and research challenges," IEEE Net-work, vol. 18, no. 2, pp. 41-48, Mar.-Apr. 2004.
• 8: F. Kelly, "Loss networks," Ann. Appl. Probabil., vol. 1, no. 3, pp. 319-378, 1991.
• 9: A. Zolfaghari and F. J. Kaudel, "Framework for network survivability performance," IEEE J. Sel. Areas Commun., vol. 12, no. 1, pp. 46-51, Jan. 1994.
• 10: S. C. Liew and K. W. Lu, "A framework for characterizing disaster-based network survivability," IEEE J. Sel. Areas Commun., vol. 12, no. 1, pp. 52-58, Jan. 1994.
• 11: V. Tamilraj and S. Subramaniam, "A comparison of optical network topologies," in Proc. Allerton Conf. Communications, Control, and Computing, Oct. 2003, pp. 1337-1346.
• 12: Behrooz Parhami, Introduction to Parallel Processing: Algorithms and Architectures, Kluwer Academic Publishers, Norwell, MA, 1999
• 13: Kumar N. Sivarajan , Rajiv Ramaswami, Lightwave networks based on de Bruijn graphs, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.70-79, Feb. 1994 [doi>10.1109/90.282610]
• 14: W. Feller, An Introduction to Probability Theory and Its Applications, 3rd ed. New York: Wiley, 1968.
• 15: J. D. Spragins, "Dependent failures in data communication systems," IEEE Trans. Commun., vol. 25, no. 12, pp. 1494-1499, Dec. 1977.
• 16: K. V. Le and V. O. Li, "Modeling and analysis of systems with multi-mode components and dependent failures," IEEE Trans. Reliabil., vol. 38, no. 1, pp. 68-75, Apr. 1989.
• 17: D. Papadimitriou, F. Poppe, J. Jones, S. Venkatachalam, S. Dha-ranikota, R. Jain, R. Hartani, and D. Griffith, "Inference of shared risk link groups," in Optical Internetworking Forum (OIF), Fremont, CA, 2001, contribution oif2001-066.
• 18: Srikanth Kandula , Dina Katabi , Jean-Philippe Vasseur, Shrink: a tool for failure diagnosis in IP networks, Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080173.1080178]
• 19: Ramana Rao Kompella , Jennifer Yates , Albert Greenberg , Alex C. Snoeren, IP fault localization via risk modeling, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.57-70, May 02-04, 2005
• 20: P. Erdos and A. Renyi, "On the evolution of random graphs," Publ. Math. Inst. Hungarian Acad. Sci., vol. 5, pp. 17-61, 1960.
• 21: G. Liu and C. Ji, "Resilience of all-optical network architectures under in-band crosstalk attacks: A probabilistic graphical model approach," IEEE J. Sel. Areas Commun., vol. 25, no. 4, pp. 2-17, Apr. 2007.
• 22: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 23: Lun Li , David Alderson , Walter Willinger , John Doyle, A first-principles approach to understanding the internet's router-level topology, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 24: S. A. Berezner, A. E. Krzesinski, and P. G. Taylor, "On the inverse of Erlang's function," J. Appl. Probabil., vol. 35, no. 1, pp. 246-252, Mar. 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Fault tolerance

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing; Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
Erlang fixed point approximation, dependent failures, network resilience, probabilistic graphical models, scalability