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.

Project activities

Node Positioning

There are two phases of topology generation: one is the positioning of the nodes and the second is the generation of interconnecting links. Most of the existing graph models, focus only on the link generation. The physical location of nodes with respect to each other is commonly a random distribution, however in practice, network designers are almost always constrained on node locations. For example, the node location (point-of-presence) of any major ISP is guided by several economical and policy decisions and plays a dominant role in the resulting network topology. Therefore, we address this issue from a practical perspective. Instead of a random node location, we propose a fixed position for every node in the topology based on pre-determined locations. In case of a commercial network such as an ISP, this information is often a given design constraint. Hence our problem can be formulated as that of topology generation given a set of PoP locations. In this paper, we consider several random graph models to generate edges between a fixed set of nodes as discussed below.

Random Link Generation Models

The initial study consists of using random graph generation models. However, we use exact node placement instead of a random node distribution while using the original link generation algorithm from the model. The shortcomings of random graph models such as inability to capture all the statistical properties of large-scale graphs are well known. Our objective is to evaluate the impact of node positioning on the generated topologies and their statistical properties. So far, we have implemented modified locality and Waxman models based topology generator.

Network Costs

The cost analysis of the generated topologies provides valuable perspective on graph model. In practice the capital available for network deployment is limited. Therefore, it is essential that if not directly integrated in to the model, the cost should be at least used to obtain a realistic set of model parameters. In this paper. we use a realistic cost function with arbitrary units (for simplicity, the smallest cost factor is assigned a unit value) to determine the range of model parameters that provide a feasible solution. Given this range of “affordable” parameters, we can then analyze which topologies optimize the performance. The cost a link between a pair of nodes is defined as:

C = f_c + δ × d

where f_c is the fixed cost associated with deploying a link of any length. δ is the variable cost expressed per unit distance and d is the euclidean distance between the nodes.

Topology Representativeness

Node degree distribution: The node degree distribution is defined as the probability that a randomly selected node is of degree k

Shortest path length: The shortest path length distribution is defined as the distribution of the probability of the two randomly selected nodes being at minimum distance of k hops from each other.

Link lengths: We define the link length distribution as the probability that a random edge in the network will be of length k such that m < k < n where n–m = δ is a fixed length increment.

Simulation Results

Original router level Sprint topology	Sample topology generated with Waxman model	Sample topology generated with modified Waxman model

Comparison of topological representativeness

Statistical distributions of different models for Sprint topolgy

Topology	Node Degree (μ/σ)	Shortest Path (μ/σ)	Link Lengths (μ/σ)
Real topology	5.04/3.88	2.44/1.10	1.41/1.18
Waxman model	4.74/1.75	2.25/0.87	1.15/0.63
Modified Waxman model	5.04/2.36	2.51/1.17	0.81/0.74

Source Code

We developed this topology generator in Matlab R2007b. You can dowload the the source code here. To run the code simply run the downloaded file in Matlab. The program is somewhat interactive.

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.”

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.”

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.

Presentations

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.

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.

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 K. Çetinkaya: evaluation of topology representativeness

Principal Investigators

James P.G. Sterbenz* (PI)

Sponsors

This work funded in part by NSF FIND program