Topology and Challenge Modelling

Realistic topology generators are essential to the understanding of network design and survivability analysis. Two important issues that are not sufficiently addressed by current topology generators are node-positioning and cost considerations. The utility of the existing models could be vastly improved by incorporating these two features. This project aims at developing a new network topology generator, which enables node positioning and cost constraints on the topologies generated with several well-known graph generation models. Our approach incorporates network design practices in topology generation, thereby enabling a tool that can be used to generate viable alternate topologies during the network design and engineering phase. Further, we consider the representativeness of the generated topologies using several graphical properties such as degree distribution, shortest path distribution, link length distribution, and spectrum of the graph amongst several others.

An essential aspect of resilient network design is to understand how the networks behave under various challenges. To analyse network resiliency we model the challenges that disrupts the normal operation of network. In order to analyse full set of scenarios, simulation scripts require n networks for c challenges. Our model decouples the c×n input files required for complex simulation scripts, and reducing it to c+n input files, thus any challenge model can be applied to any network topology. This decoupling gains challenge scenario analysis efficiency.

Topology Modelling

Realistic topology generators are crucial to numerous aspects of networking research. In particular, there are three distinct applications of topology generators: understanding the graphical properties of the network and evaluating the performance of protocols and services over a given topology; resilience and survivability analysis of the network to determine how well the network will react to challenges; and finally, a tool for network architects, providing alternate topologies that meet certain constraints during the design and engineering phase. It should be noted that research in the past has rigorously studied the first application by modeling the graphical properties of the network and to some extent have addressed the survivability issues. However the existing research focuses on independent single link failures as opposed to geographically correlated link failures. Finally, to our knowledge there is very little effort on the third application - development of a practical tool to be used in the network design process.

Two important issues that are not sufficiently addressed by current topology generators are node-positioning and cost considerations. The utility of the existing models could be vastly improved by incorporating these two features. This project aims at developing a new network topology generator, which enables node positioning and cost constraints on the topologies generated with several well-known graph generation models. Our approach incorporates network design practices in topology generation, thereby enabling a tool that can be used to generate viable alternate topologies during the network design and engineering phase. Further, we consider the representativeness of the generated topologies using several graphical properties such as degree distribution, shortest path distribution, link length distribution, and spectrum of the graph amongst several others.

Challenge Modelling

An essential aspect to the evaluation of network resilience and design of resilient networks is to understand how various architectures, designs, and protocol respond to challenges. These challenges to normal operation include:

• unintentional misconfiguration or operational mistakes
• large scale natural disasters such as hurricanes, tsunami, floods, earthquakes
• attacks from an intelligent adversary
• environmental challenges
• unusual but legitimate traffic
• service failure at a lower level

In order to simulate a wide variety of challenges, complex simulation scripts are needed that model both the network topology, protocols, as well as the challenges. Challenge simulation requires manual and careful modification of the simulation script, for example by disabling links and nodes for the duration of the challenge. For c challenges to n networks this requires c×n simulation files.

We are looking at a new approach that decouples the network model from the challenge description, resulting in c challenge descriptions applied to n networks, for a total of c+n input files, thus increased efficiency of simulation generation. This is accomplished by feeding network topology (via an adjacency matrix) and geographical coordinates of nodes to C++ based ns-3 simulation script. The network topology file that is fed to the simulation model can be organic or synthetically generated via KU-LoCGen.

Presentations and Publications

Papers

James P.G. Sterbenz Джеймс Ф.Г. Штербэнз, Egemen K. Çetinkaya, Mahmood Abdul Hameed, Abdul Jabbar, Qian Shi, Justin P. Rohrer,
“Evaluation of Network Resilience, Survivability, and Disruption Tolerance: Analysis, Topology Generation, Simulation, and Experimentation (invited paper)”,
Springer Telecommunication Systems Journal,
(online December 2011)
BibTeX

Keywords: resilient survivable disruption-tolerant network, dependability performability, diverse topology generation, network analysis experimentation, ns-3 simulation methodology

Abstract: “As the Internet becomes increasingly important to all aspects of society, the consequences of disruption become increasingly severe. Thus it is critical to increase the resilience and survivability of future networks. We define resilience as the ability of the network to provide desired service even when challenged by attacks, large-scale disasters, and other failures. This paper describes a comprehensive methodology to evaluate network resilience using a combination of topology generation, analytical, simulation, and experimental emulation techniques with the goal of improving the resilience and survivability of the Future Internet.”

Egemen K. Çetinkaya, Dan Broyles, Amit Dandekar, Sripriya Srinivasan, and James P.G. Sterbenz Джеймс Ф.Г. Штербэнз,
“Modelling Communication Network Challenges for Future Internet Resilience, Survivability, and Disruption Tolerance: A Simulation-Based Approach”,
Springer Telecommunication Systems Journal,
(online September 2011)
BibTeX

Keywords: Internet resilience, survivability, disruption tolerance, dependability and performability, reliability and availability; ns-3 simulation; failure analysis; challenge modeling; threats and vulnerabilities; network logical and physical topology; correlated failures

Abstract: “Communication networks play a vital role in our daily lives and they have become a critical infrastructure. However, networks in general, and the Internet in particular face a number of challenges to normal operation, including attacks and large-scale disasters, as well as due to mobility and the characteristics of wireless communication channels. Understanding network challenges and their impact can help us to optimise existing networks and improve the design of future networks; therefore it is imperative to have a framework and methodology to study them. In this paper, we present a framework to evaluate network dependability and performability in the face of challenges. We use a simulation-based approach to analyse the effects of perturbations to normal operation of networks. We analyse Sprint logical and physical topologies, synthetically generated topologies, and present a wireless example to demonstrate a wide spectrum of challenges. This framework can simulate challenges on logical or physical topologies with realistic node coordinates using the ns-3 discrete event simulator. The framework models failures, which can be static or dynamic that can temporally and spatially evolve. We show that the impact of network challenges depends on the duration, the number of network elements in a challenge area, and the importance of the nodes in a challenge area. We also show the differences between modelling the logical router-level and physical topologies. Finally, we discuss mitigation strategies to alleviate the impact of challenges.”

James P.G. Sterbenz, Egemen K. Çetinkaya, Mahmood A. Hameed, Abdul Jabbar, and Justin P. Rohrer,
“Modelling and Analysis of Network Resilience (invited paper)”,
The Third IEEE International Conference on Communication Systems and Networks (COMSNETS),
Bangalore, India, January 2011, pp. 1–10
BibTeX

Keywords: Future Internet architecture, resilience, survivability, performability, dependability, topology, population, attack, disaster, challenge, metrics, generation, simulation, modelling

Abstract: “As the Internet becomes increasingly important to all aspects of society, the consequences of disruption become increasingly severe. Thus it is critical to increase the resilience and survivability of the future network. We define resilience as the ability of the network to provide desired service even when challenged by attacks, large-scale disasters, and other failures. This paper describes a comprehensive methodology to evaluate network resilience using a combination of analytical and simulation techniques with the goal of improving the resilience and survivability of the Future Internet.”

Mahmood A. Hameed, Abdul Jabbar, Egemen K. Çetinkaya, and James P.G. Sterbenz,
“Deriving Network Topologies from Real World Constraints”,
Proceedings of IEEE GLOBECOM Workshop on Complex and Communication Networks (CCNet),
Miami, FL, December 2010, pp. 415–419
BibTeX

Keywords: Network topology model, cost-constraint, geography, population, resilience, technology penetration

Abstract: “Realistic network topologies are crucial for network research and are commonly used for the analysis, simulation, and evaluation of various mechanisms and protocols. In this paper, we discuss network topology models to generate physical topologies for backbone networks. In order to gain better understanding of current topologies and engineer networks for the future, it is necessary to generate realistic physical topologies that are governed by the infrastructure as opposed to only logical topologies that are governed by policy or higher-layer abstractions. The objective of this work is to present the principles that are key to node distributions of realistic topologies and the challenges involved. We argue that the dominant factors that influence the location of the PoPs are population density distribution and the technology penetration of a given region. Hence we implement clustering algorithm to accurately predict the location of PoPs and later explore cost constrained models to generate realistic physical topologies.”

Egemen K. Çetinkaya, Dan Broyles, Amit Dandekar, Sripriya Srinivasan, and James P.G. Sterbenz Джеймс Ф.Г. Стербэнз,
“A Comprehensive Framework to Simulate Network Attacks and Challenges”,
IEEE/IFIP Second International Workshop on Reliable Networks Design and Modeling (RNDM'10),
Moscow, Russia, October 2010, pp. 538–544.
BibTeX

Keywords: Internet resilience, survivability, dependability, performability; challenge, attack, disaster, correlated failure; network topology, critical infrastructure; ns-3 simulation, modelling

Abstract: “Communication networks have evolved tremendously over the past several decades, offering a multitude of services while becoming an essential critical infrastructure in our daily lives. Networks in general, and the Internet in particular face a number of challenges to normal operation, including attacks and large-scale disasters, as well as due to the characteristics of the mobile wireless communication environment. It is therefore vital to have a framework and methodology for understanding the impact of challenges to harden current networks and improve the design of future networks. In this paper, we present a framework to evaluate network dependability and performability in the face of challenges. This framework uses ns-3 simulation as the methodology for analysis of the effects of perturbations to normal operation of the networks, with a challenge specification applied to the network topology. This framework can simulate both static and dynamic challenges based on the failure or wireless-impairment of individual components, as well as modelling geographically-correlated failures. We demonstrate this framework with the Sprint Rocketfuel and synthetically generated topologies as well as a wireless example, to show that this framework can provide valuable insight for the analysis and design of resilient networks.”

Technical Reports

Abdul Jabbar, Qian Shi, Egemen Çetinkaya, and James P.G. Sterbenz,
KU-LocGen: Location and Cost-Constrained Network Topology Generator,
ITTC Technical Report ITTC-FY2009-TR-45030-01, The University of Kansas, December 2008.
BibTeX

Keywords: geographic location, network topology generator, node positioning, cost analysis, Waxman

Abstract: “Realistic topology generators are essential to the understanding of network design and survivability analysis. Two important issues that are not sufficiently addressed by current topology generators are node-positioning and cost considerations. We propose that the utility of the existing models could be vastly improved by incorporating these two features. In this paper we introduce a new network topology generator KU-LocGen, which enables node positioning in several well-known random graph generation models. We conduct our studies based on two backbone networks. We show that the proposed generator produces graphs that are representative of the real network as well as realistic alternatives. Finally, we present a cost analysis methodology and apply it to our topology generator.”

Presentations

Egemen K. Çetinkaya, Justin P. Rohrer, and James P.G. Sterbenz,
“Resilience of Backbone Provider Networks”,
INFOCOM Student Poster, Orlando, FL, March 2012.

Egemen K. Çetinkaya, Justin P. Rohrer, and James P.G. Sterbenz,
“Resilience Modelling of Networks against Adaptive Challenges”,
IWSOS Student Poster, Delft, March 2012.

Abdul Jabbar, Mahmood Hameed, Qian Shi, and James P.G. Sterbenz,
Location and Cost Constrained Multilevel Topology Generation,
ITTC IAB poster, The University of Kansas, June 2010.

Mahmood Hameed, Abdul Jabbar, Jing Han, and James P.G. Sterbenz,
Network Topology Generation from Real-World Constraints,
ITTC IAB poster, The University of Kansas, June 2010.

Egemen K. Çetinkaya, Dan Broyles, Amit Dandekar, Sripriya Srinivasan, and James P.G. Sterbenz,
Challenge Simulation Module for Evaluating Resilience,
ITTC IAB poster, The University of Kansas, June 2010.

Qian Shi, Abdul Jabbar, Egemen K. Çetinkaya, Güneş Erçal-Özkaya, and James P.G. Sterbenz,
KU-LoCGen: Location and Cost Constrained Topologies,
ITTC IAB poster, The University of Kansas, April 2009.

Rabat Mahmood, Abdul Jabbar, Egemen K. Çetinkaya, and James P.G. Sterbenz,
Challenge Simulation Module for Evaluating Resilience,
ITTC IAB poster, The University of Kansas, April 2009.

Abdul Jabbar, Manasa K., Rabat Mahmood, Qian Shi, Ruru Rai, and James P.G. Sterbenz,
Simulating Challenges in ns-2 for Resilient Networks,
ITTC IAB poster, The University of Kansas, June 2008.

People

Graduate Research Assistants

Abdul Jabbar: technical lead for methodologies to implement location and cost constraints
Qian Shi: implementation of the topology generator in MATLAB
Mahmood Hameed: population-based topology generation
Egemen Çetinkaya: evaluation of topology representativeness

Principal Investigators

James P.G. Sterbenz* (PI)

Sponsors

This work funded in part by NSF FIND program