Topology Generators
[[ Zegura-Calvert-Bhattacharjee-1996] ]
Ellen W. Zegura, Kenneth L. Calvert, and Samrat Bhattacharjee,
“How to Model an Internetwork”,
Proceedings of IEEE Infocom '96, San Francisco, CA. ,
vol.2 iss.24-28, Mar 1996, pp. 594–602
ResiliNets Keywords: Network model
Keywords:
Abstract: “Graphs are commonly used to model the structure of internetworks, for the study of problems ranging from routing to resource reservation. A variety of graph models are found in the literature, including regular topologies such as rings or stars, “well-known” topologies such as the original ARPAnet, and randomly generated topologies. Less common is any discussion of how closely these models correlate with real network topologies. We consider the problem of efficiently generating graph models that accurately reflect the topological properties of real internetworks. We compare the properties of graphs generated using various methods with those of real internets. We also propose efficient methods for generating topologies with particular properties, including a transit-stub model that correlates well with the internet structure. Improved models for the internetwork structure have the potential to impact the significance of simulation studies of internetworking solutions, providing a basis for the validity of the conclusions .”
Notes: transit-stub model for domain structure.
[[Calvert-Doar-Zegura-1997] ]
Kenneth L. Calvert, matthew B. Doar and Ellen W. Zegura,
“Modeling Internet Topology”,
Communications Magazine, IEEE ,
vol.35 iss.6, Jun 1997 , pp. 160–163
ResiliNets Keywords: Network model
Keywords:
Abstract: “The topology of a network, or a group of networks such as the Internet, has a strong bearing on many management and performance issues. Good models of the topological structure of a network are essential for developing and analyzing internetworking technology. This article discusses how graph-based models can be used to represent the topology of large networks, particularly aspects of locality and hierarchy present in the Internet. Two implementations that generate networks whose topology resembles that of typical internetworks are described, together with publicly available source code.”
Notes: transit-stub and Tiers modeling.
[[Tomas-Zegura-1994] ]
Megan Thomas and Ellen W. Zegura,
“ Generation and analysis of random graphs to model internetworks”,
Technical report, Georgia Tech, College of Computing,
Jun 1994 , pp. 46.
ResiliNets Keywords: random graph Network model
Keywords:
Abstract: “Graph models are commonly used in studying solutions to internetworking problems. This paper considers several random graph models that have been used to model internetworks, and considers ways to characterize the properties of these graphs. By matching the characteristics of the random graphs to the characteristics of real internetworks, more accurate modeling can be achieved.”
Notes: Random graph.
[Medina-Matta-Byers-2000(doi)]
Alberto Medina, Ibrahim Matta and John Byers,
“On the Origin of Power Laws in Internet Topologies ”,
ACM Computer Communications Review ,
vol.30 iss.2, April 2000 , pp. 18–28.
ResiliNets Keywords: BRITE model
Keywords:
Abstract: “Recent empirical studies [6] have shown that Internet topologies exhibit power laws of the form y = x α for the following relationships: (P1) outdegree of node (domain or router) versus rank; (P2) number of nodes versus outdegree; (P3) number of node pairs within a neighborhood versus neighborhood size (in hops); and (P4) eigenvalues of the adjacency matrix versus rank. However, causes for the appearance of such power laws have not been convincingly given. In this paper, we examine four factors in the formation of Internet topologies. These factors are (F1) preferential connectivity of a new node to existing nodes; (F2) incremental growth of the network; (F3) distribution of nodes in space; and (F4) locality of edge connections. In synthetically generated network topologies, we study the relevance of each factor in causing the aforementioned power laws as well as other properties, namely diameter, average path length and clustering coefficient. Different kinds of network topologies are generated: (T1) topologies generated using our parametrized generator, we call BRITE; (T2) random topologies generated using the well-known Waxman model [12]; (T3) Transit-Stub topologies generated using GT-ITM tool [3]; and (T4) regular grid topologies. We observe that some generated topologies may not obey power laws P1 and P2. Thus, the existence of these power laws can be used to validate the accuracy of a given tool in generating representative Internet topologies. Power laws P3 and P4 were observed in nearly all considered topologies, but different topologies showed different values of the power exponent α. Thus, while the presence of power laws P3 and P4 do not give strong evidence for the representativeness of a generated topology, the value of α in P3 and P4 can be used as a litmus test for the representativeness of a generated topology. We also find that factors F1 and F2 are the key contributors in our study which provide the resemblance of our generated topologies to that of the Internet.”
Notes: Brite Model
[Aiello-Chung-Lu-2000(doi)) ]
William Aiello, Fan Chung and Linyuan Lu,
“ A Random Graph Model for Massive Graphs”,
Proceedings of the thirty-second annual ACM symposium on Theory of computing ,
may 21-23, 2000 ,Portland, Oregon, United States, pp. 171–180.
ResiliNets Keywords: Power-Law random graph model for network
Keywords:
Abstract: “We propose a random graph model which is a special case of sparse random graphs with given degree sequences. This model involves only a small number of parameters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. Furthermore, from these parameters, various properties of the graph can be derived. For example, for certain ranges of the parameters, we will compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We will illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We will also discuss the threshold function, the giant component, and the evolution of random graphs in this model.”
Notes: Power-Law Random graph.
[Jin-Chen-jamin-1998 ]
Cheng jin, Qian Chen and Sugih Jamin,
“ Inet: Internet Topology Generator”,
Technical Report CSE-TR443 -00, Department of EECS, University of Michigan, 2000.
ResiliNets Keywords: Inet topology generator
Keywords:
Abstract: “Network research often involves the evaluation of new application designs, system architectures, and protocol implementations. Due to the immense scale of the Internet, deploying an Internet-wide system for the purpose of experimental study is nearly impossible. Instead, researchers evaluate their designs using generated random network topologies. In this report, we present a topology generator that is based on Autonomous System (AS) connectivity in the Internet. We compare the networks generated by our generator with other types of random networks and show that it generates topologies that best approximate the actural Internet AS topology.”
Notes: Manual book for Inet topology generator and also a survey paper for other generators.
[Barabasi-Albert-1999]
Albert-Laszlo Barabasi and Reka Albert ,
“ Emergence of Scaling in Random Networks”,
Science.
vol.286 iss.5439, October 1999, pp. 509–512
ResiliNets Keywords: Barabasi-Albert model
Keywords:
Abstract: “Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.”
Notes: Barabasi-Albert model for network modeling first introduce scale-free power-law distribution.
[[ Konak-Bartolacci-2006] ]
Abdullah Konak and Michael R. Bartolacci,
“Designing survivable resilient networks: A stochastic hybrid genetic algorithm approach ”,
OMEGA- The International Journal of Management Science ,
vol.35 iss.6, December 2007, pp. 645–658
ResiliNets Keywords: Network model
Keywords: Telecommunications; Reliability; Simulation; Stochastic programming
Abstract: “As high-speed networks have proliferated across the globe, their topologies have become sparser due to the increased reliability of components and cost considerations. Reliability has been a traditional goal within network design optimization. An alternative design consideration, network resilience, has not been studied or incorporated into network designs nearly as much. The authors propose a methodology for the difficult estimation of traffic efficiency (TE), a measure of network resilience, and a hybrid genetic algorithm to design networks using this measure.”
Notes: Stochastic hybrid genetic algorithm instead of TE (traffic efficiency)
[Konak-Smith-2005(doi) ]
Abdullah Konak and Alice E. Smith,
“Designing resilient networks using a hybrid genetic algorithm approach ”,
Genetic and Evolutionary Computation Conference - GECCO 2005, Washington, DC, USA.,
June 2005, pp. 1279–1285
ResiliNets Keywords: Network model
Keywords: genetic algorithms, network reliability, network survivability, resilience, simulation optimization
Abstract: “As high-speed networks have proliferated across the globe, their topologies have become sparser due to the increased capacity of communication media and cost considerations. Reliability has been a traditional goal within network design optimization of sparse networks. This paper proposes a genetic approach that uses network resilience as a design criterion in order to ensure the integrity of network services in the event of component failures. Network resilience measures have been previously overlooked as a network design objective in an optimization framework because of their computational complexity - requiring estimation by simulation. This paper analyzes the effect of noise in the simulation estimator used to evaluate network resilience on the performance of the proposed optimization approach.”
Notes: Hybrid Genetic algorithm (HGA)
[Ho-Cheung-2007(doi)]
Kwok Shing Ho and Kwok Wai Cheung,
“Generalized survivable network”,
IEEE/ACM Transactions on Networking (TON),
vol.15 iss.4, August 2007 , pp. 750–760.
ResiliNets Keywords: New Network Concept
Keywords: ASON, ASTN, IP network, VPN, network design, nonblocking network, survivable network
Abstract: “Two important requirements for future backbone networks are full survivability against link failures and dynamic bandwidth provisioning. We demonstrate how these two requirements can be met by introducing a new survivable network concept called the Generalized Survivable Network (GSN), which has the special property that it remains survivable no matter how traffic is provisioned dynamically, as long as the input and output constraints at the nodes are fixed. A rigorous mathematical framework for designing the GSN is presented. In particular, we focus on the GSN Capacity Planning Problem, which finds the edge capacities for a given physical network topology with the input/output constraints at the nodes. We employ fixed single-path routing which leads to wide-sense nonblocking GSNs. We show how the initial, infeasible formal mixed integer linear programming formulation can be transformed into a more feasible problem using the duality transformation. A procedure for finding the realizable lower bound for the cost is also presented. A two-phase approach is proposed for solving the GSNCPP. We have carried out numerical computations for ten networks with different topologies and found that the cost of a GSN is only a fraction (from 39% to 97%) more than the average cost of a static survivable network. The framework is applicable to survivable network planning for ASTN/ASON, VPN, and IP networks as well as bandwidth-on-demand resource allocation.”
Notes: GSN mathematical framework
[[ Monma-Shallcross-1989] ]
Clyde L. Monma and Divid F. Shallcross,
“Methods for Designing Communications Networks with Certain Two-Connected Survivability Constraints”,
Operations Research,
vol.37 iss.4, Jul-Aug 1989, pp. 531–541.
ResiliNets Keywords:
Keywords:
Abstract: “In this paper, we consider the problem of designing a minimum cost communication network subject to certain two-connected survivability constraints. This problem was motivated by work at Bellcore on planning fiber optic communications networks. We introduce heuristics for constructing initial feasible networks, and local improvement heuristics for reducing the cost of existing network designs while preserving a feasible network. This approach is shown to be effective on data from both real-world fiber optic communications network problems and randomly generated problems. ”
Notes: how to design minimum cost communication network
[Albert-Jeong-Barabasi-2000 ]
Réka Albert, Hawoong Jeong and Albert-László Barabási,
“Error and attack tolerance of complex networks”,
Nature,
vol.406, July 2000, pp. 378–382.
ResiliNets Keywords: tolerance test
Keywords:
Abstract: “Many complex systems display a surprising degree of tolerance against errors. For example, relatively simple organisms grow, persist and reproduce despite drastic pharmaceutical or environmental interventions, an error tolerance attributed to the robustness of the underlying metabolic network. Complex communication networks display a surprising degree of robustness: although key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these and other complex systems is often attributed to the redundant wiring of the functional web defined by the systems' components. Here we demonstrate that error tolerance is not shared by all redundant systems: it is displayed only by a class of inhomogeneously wired networks, called scale-free networks, which include the World-Wide Web, the Internet, social networks and cells. We find that such networks display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates. However, error tolerance comes at a high price in that these networks are extremely vulnerable to attacks (that is, to the selection and removal of a few nodes that play a vital role in maintaining the network's connectivity). Such error tolerance and attack vulnerability are generic properties of communication networks.”
Notes: comparison of exponential and scale-free network
