Network Topology
Topology Generic
[Haddadi-Rio-Iannaccone-Moore-Mortier-2008 (doi) .]
H. Haddadi, M. Rio, G. Iannaccone, A. Moore, R. Mortier
“Network topologies: inference, modeling, and generation”,
IEEE Communications Surveys & Tutorials, vol.10, #2, Second Quarter 2008, pp. 48–69
ResiliNets Keywords: list
Keywords: Internet, telecommunication network planning, telecommunication network routing, telecommunication network topology, Internet topology research, failure detection, network planning, network routing, network topology, spatial analysis
Abstract: “Accurate measurement, inference and modeling techniques are fundamental to Internet topology research. Spatial analysis of the Internet is needed to develop network planning, optimal routing algorithms, and failure detection measures. A first step toward achieving such goals is the availability of network topologies at different levels of granularity, facilitating realistic simulations of new Internet systems. The main objective of this survey is to familiarize the reader with research on network topology over the past decade. We study techniques for inference, modeling, and generation of the Internet topology at both the router and administrative levels. We also compare the mathematical models assigned to various topologies and the generation tools based on them. We conclude with a look at emerging areas of research and potential future research directions.”
Notes: importance and relevance to ResiliNets
[Chakrabarti-Faloutsos-2006 (doi) .]
D. Chakrabarti, C. Faloutsos
“Graph mining: Laws, generators, and algorithms”,
ACM Comput. Surv., vol.38, #1, 2006, Article No. 2
ResiliNets Keywords: list
Keywords: Generators, graphs, patterns, social networks
Abstract: “How does the Web look? How could we tell an abnormal social network from a normal one? These and similar questions are important in many fields where the data can intuitively be cast as a graph; examples range from computer networks to sociology to biology and many more. Indeed, any M : N relation in database terminology can be represented as a graph. A lot of these questions boil down to the following: “How can we generate synthetic but realistic graphs?” To answer this, we must first understand what patterns are common in real-world graphs and can thus be considered a mark of normality/realism. This survey give an overview of the incredible variety of work that has been done on these problems. One of our main contributions is the integration of points of view from physics, mathematics, sociology, and computer science. Further, we briefly describe recent advances on some related and interesting graph problems.”
Notes: importance and relevance to ResiliNets
[Amin-2002 (doi) .]
M. Amin
“Modeling and control of complex interactive networks [Guest Editorial]”,
IEEE Control Systems Magazine, vol.22, #1, Feb. 2002, pp. 22–27
ResiliNets Keywords: list
Keywords:
Abstract: “.”
Notes: importance and relevance to ResiliNets
[Wang-Chen-2003 (doi) .]
X. F. Wang, G. Chen
“Complex networks: small-world, scale-free and beyond”,
IEEE Circuits and Systems Magazine, vol.3, #1, 2003, pp. 6–20
ResiliNets Keywords: list
Keywords: dynamics, large-scale systems, network topology, stability, synchronisation
Abstract: “In the past few years, the discovery of small-world and scale-free properties of many natural and artificial complex networks has stimulated a great deal of interest in studying the underlying organizing principles of various complex networks, which has led to dramatic advances in this emerging and active field of research. The present article reviews some basic concepts, important progress, and significant results in the current studies of various complex networks, with emphasis on the relationship between the topology and the dynamics of such complex networks. Some fundamental properties and typical complex network models are described; and, as an example, epidemic dynamics are analyzed and discussed in some detail. Finally, the important issue of robustness versus fragility of dynamical synchronization in complex networks is introduced and discussed.”
Notes: importance and relevance to ResiliNets
[Xu-Chen-2008 (doi) .]
J. Xu, H. Chen
“The topology of dark networks”,
Commun. ACM, vol.51, #10, 2008, pp. 58–65
ResiliNets Keywords: list
Keywords:
Abstract: “Knowing the structure of criminal and terrorist networks could provide the technical insight needed to disrupt their activities.”
Notes: importance and relevance to ResiliNets
[Strogatz-2001 (doi) .]
S. H. Strogatz
“Exploring complex networks”,
Nature, vol.410, 8 March 2001, pp. 268–276
ResiliNets Keywords: list
Keywords:
Abstract: “The study of networks pervades all of science, from neurobiology to statistical physics. The most basic issues are structural: how does one characterize the wiring diagram of a food web or the Internet or the metabolic network of the bacterium Escherichia coli? Are there any unifying principles underlying their topology? From the perspective of nonlinear dynamics, we would also like to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture. Researchers are only now beginning to unravel the structure and dynamics of complex networks.”
Notes: importance and relevance to ResiliNets
[Hayes-2000a (doi) .]
B. Hayes
“Graph Theory in Practice: Part I”,
American Scientist, vol.88, issue 1, Jan.-Feb. 2000, pp. 9–
ResiliNets Keywords: list
Keywords:
Abstract: “”
Notes: importance and relevance to ResiliNets
[Hayes-2000b (doi) .]
S. H. Strogatz
“Graph Theory in Practice: Part II”,
American Scientist, vol.88, issue 2, Mar.-Apr. 2000, pp. 104–
ResiliNets Keywords: list
Keywords:
Abstract: “”
Notes: importance and relevance to ResiliNets
[Dorogovtsev-Mendes-2003]
Sergei N. Dorogovtsev, Jose F.F. Mendes
Evolution of networks : from biological nets to the Internet and WWW
Oxford University Press 2003
ResiliNets Keywords: networks
[Network Science Tutorials and Papers]
[Mieghem-2011 .]
Piet Van Mieghem
“Robustness of Complex Network(Tutorial)”,
International Workshop on the Design of Reliable Communication Networks<DRCN>,
Krakow Poland, October 2011
Topology Metrics
[Albert-Barabási-2002 (doi) .]
R. Albert, A-L. Barabási
“Statistical mechanics of complex networks”,
Rev. Mod. Phys., vol.74, #1, Jan. 2002, pp. 47–97
ResiliNets Keywords: list
Keywords:
Abstract: “Complex networks describe a wide range of systems in nature and society. Frequently cited examples include the cell, a network of chemicals linked by chemical reactions, and the Internet, a network of routers and computers connected by physical links. While traditionally these systems have been modeled as random graphs, it is increasingly recognized that the topology and evolution of real networks are governed by robust organizing principles. This article reviews the recent advances in the field of complex networks, focusing on the statistical mechanics of network topology and dynamics. After reviewing the empirical data that motivated the recent interest in networks, the authors discuss the main models and analytical tools, covering random graphs, small-world and scale-free networks, the emerging theory of evolving networks, and the interplay between topology and the network’s robustness against failures and attacks.”
Notes: importance and relevance to ResiliNets
[[Ali-Leon-Garcia-2010] (doi) .]
Ali Tizghadam and Alberto Leon-Garcia
“Betweennes Centrality and Resistance Distance in Communication Networks”,
IEEE Network, vol.24, #6, November/December 2010, pp. 10–16
ResiliNets Keywords: Graph Metrics
Keywords: betweenness centrality; communication networks; control algorithms; control loops design; directed weighted graph models; network control; network criticality;resistance distance; two-loop general architecture; weighted graph theory; directed graphs; telecommunication control; telecommunication networks;
Abstract: “n this article we report on applications and extensions of weighted graph theory in the design and control of communication networks. We model the communication network as a weighted graph and use the existing literature in graph theory to study its behavior. We are particularly interested in the notions of betweenness centrality and resistance distance in the context of communication networks. We argue that in their most general form, the problems in a communication network can be converted to either the optimal selection of weights or optimal selection of paths based on the present values of weights in a graph. Motivated by this, we propose a two-loop general architecture for the control of networks and provide directions to design appropriate control algorithms in each control loop. We show that the total resistance distance (network criticality) of a graph has very useful interpretations in the context of communication networks; therefore, we propose to use network criticality as the main objective function, and we provide guidelines to design the control loops to minimize network criticality. We also discuss the development of new directed weighted graph models and their application to communication networks.”
Notes: importance and relevance to ResiliNets
[Zhou-Mondragon-2004 (doi) .]
S. Zhou, R.J. Mondragon
“The rich-club phenomenon in the Internet topology”,
IEEE Communications Letters, vol.8, #3, March 2004, pp. 180–182
ResiliNets Keywords: list
Keywords: Internet, graph theory, modelling, network topology, telecommunication links Barabasi-Albert scale-free network model, Inet-3.0 model, Internet topology, autonomous system graph, autonomous system level, core tier, fitness BA model, network graph, network model, node-node link distribution, power law topology, rich node, rich-club connectivity, rich-club phenomenon
Abstract: “We show that the Internet topology at the autonomous system (AS) level has a rich-club phenomenon. The rich nodes, which are a small number of nodes with large numbers of links, are very well connected to each other. The rich-club is a core tier that we measured using the rich-club connectivity and the node-node link distribution. We obtained this core tier without any heuristic assumption between the ASs. The rich-club phenomenon is a simple qualitative way to differentiate between power law topologies and provides a criterion for new network models. To show this, we compared the measured rich-club of the AS graph with networks obtained using the Baraba´si-Albert (BA) scale-free network model, the Fitness BA model and the Inet-3.0 model.”
Notes: importance and relevance to ResiliNets
[Vukadinović-Huang-Erlebach-2002 (doi) .]
D. Vukadinović, P. Huang, T. Erlebach
“On the Spectrum and Structure of Internet Topology Graphs”,
Proceedings of the Second International Workshop on Innovative Internet Computing Systems, IICS '02, vol. 2346/2002, pp. 83–95
ResiliNets Keywords: list
Keywords:
Abstract: “In this paper we study properties of the Internet topology on the autonomous system (AS) level. We find that the normalized Laplacian spectrum (nls) of a graph provides a concise fingerprint of the corresponding network topology. The nls of AS graphs remains stable over time in spite of the explosive growth of the Internet, but the nls of synthetic graphs obtained using the state-of-the-art topology generator Inet-2.1 is significantly different, in particular concerning the multiplicity of eigenvalue 1. We relate this multiplicity to the sizes of certain subgraphs and thus obtain a new structural classification of the nodes in the AS graphs, which is also plausible in networking terms. These findings as well as new power-law relationships discovered in the interconnection structure of the subgraphs may lead to a new generator that creates more realistic topologies by combining structural and power-law properties.”
Notes: importance and relevance to ResiliNets
[Dorogovtsev-Goltsev-Mendes-Samukhin-2003 (doi) .]
S. N. Dorogovtsev, A. V. Goltsev, J. F. F. Mendes, A. N. Samukhin
“Spectra of complex networks”,
Phys. Rev. E, vol.68, #4, Oct. 2003, pp. 046109–046119
ResiliNets Keywords: list
Keywords:
Abstract: “We propose a general approach to the description of spectra of complex networks. For the spectra of networks with uncorrelated vertices (and a local treelike structure), exact equations are derived. These equations are generalized to the case of networks with correlations between neighboring vertices. The tail of the density of eigenvalues ρ(λ) at large |λ| is related to the behavior of the vertex degree distribution P(k) at large k. In particular, as P(k)∼k-γ, ρ(λ)∼|λ|1-2γ. We propose a simple approximation, which enables us to calculate spectra of various graphs analytically. We analyze spectra of various complex networks and discuss the role of vertices of low degree. We show that spectra of locally treelike random graphs may serve as a starting point in the analysis of spectral properties of real-world networks, e.g., of the Internet.”
Notes: importance and relevance to ResiliNets
[Gkantsidis-Mihail-Zegura-2003 .]
C. Gkantsidis, M. Mihail, E. Zegura
“Spectral analysis of Internet topologies”,
Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, INFOCOM 2003., vol.1, March-April 2003, pp. 364–374
ResiliNets Keywords: list
Keywords: Internet, eigenvalues and eigenfunctions, network topology, spectral analysis, telecommunication links, telecommunication traffic AS cluster, AS level topology, Internet topology, adjacency matrix, clustering property, eigenvector examination, eigenvector weight, geographic area, matrix eigenvalue, natural semantic proximity, network core, network edge, network link stress, spectral analysis, standard spectral filtering method, synthetic data, traffic pattern
Abstract: “Spectral analysis of the Internet topology at the autonomous system (AS) level, by adapting the standard spectral filtering method of examining the eigenvectors corresponding to the largest eigenvalues of matrices related to the adjacency matrix of the topology is performed. We observe that the method suggests clusters of ASs with natural semantic proximity, such as geography or business interests. We examine how these clustering properties vary in the core and in the edge of the network, as well as across geographic areas, over time, and between real and synthetic data. We observe that these clustering properties may be suggestive of traffic patterns and thus have direct impact on the link stress of the network. Finally, we use the weights of the eigenvector corresponding to the first eigenvalue to obtain an alternative hierarchical ranking of the ASs.”
Notes: importance and relevance to ResiliNets
[Jamakovic-Mieghem-2006 .]
A. Jamakovic and P. Van Mieghem
“The Laplacian Spectrum of Complex Networks”,
European Conference on Complex Systems, ECCS'06, September 25-29., Oxford, UK,
ResiliNets Keywords: list
Keywords:
Abstract: “The set of all eigenvalues of a characteristic matrix of a graph, also referred to as the spectrum, is a well-known topology retrieval method. In this paper, we study the spectrum of the Laplacian matrix of an observable part of the Internet graph at the IP-level, extracted from traceroute measurements performed via RIPE NCC and PlanetLab. In order to investigate the factors influencing the Laplacian spectrum of the observed graphs, we study the following complex network models: the random graph of Erd˝os-Rényi, the small-world of Watts and Strogatz and the scale-free graph, derived from a Havel-Hakimi power-law degree sequence. Along with these complex network models, we also study the corresponding Minimum Spanning Tree (MST). Extensive simulations show that the Laplacian spectra of complex network models differ substantially from the spectra of the observed graphs. How- ever, the Laplacian spectra of the MST in the Erd˝os-Rényi random graph with uniformly distributed link weights does bear resemblance to it. Furthermore, we discuss an extensive set of topological characteristics extracted from the Laplacian spectra of the observed real-world graphs as well as from complex network models.”
Notes: importance and relevance to ResiliNets
[Haddadi-Fay-Uhlig-Moore-Mortier-Jamakovic-Rio-2008 (doi) .]
H. Haddadi, D. Fay, S. Uhlig, A. Moore, R. Mortier, A. Jamakovic, and M. Rio
“Tuning Topology Generators Using Spectral Distributions”,
Proceedings of the SPEC International Performance Evaluation Workshop, SIPEW 2008, vol. 5119/2008, pp. 154–173
ResiliNets Keywords: list
Keywords: Internet Topology, Graph Spectrum
Abstract: “An increasing number of synthetic topology generators are available, each claiming to produce representative Internet topologies. Every generator has its own parameters, allowing the user to generate topologies with different characteristics. However, there exist no clear guidelines on tuning the value of these parameters in order to obtain a topology with specific characteristics. In this paper we optimize the parameters of several topology generators to match a given Internet topology. The optimization is performed either with respect to the link density, or to the spectrum of the normalized Laplacian matrix. Contrary to approaches in the literature that rely only on the largest eigenvalues, we take into account the set of all eigenvalues. However, we show that on their own the eigenvalues cannot be used to construct a metric for optimizing parameters. Instead we present a weighted spectral method which simultaneously takes into account all the properties of the graph.”
Notes: importance and relevance to ResiliNets
[Gertsbakh-Shpungin-2011 (doi) .]
Ilya Gertsbakh and Yoseph Shpungin,
Network Reliability and Resilience
Springer, Heidelberg Dordrecht London New York, Edition 1, 2011,
ISBN 978-3-642-22373-0
Keywords: computer attacks, connectivity estimation, marginal D-spectra, Monte Carlo, multidimensional D-spectra, network Resilience, node removal, probabilistic measures
ResiliNets Keywords: resilience
Abstract:“This book is devoted to the probabilistic description of a network in the process of its destruction, i.e. removal of its components (links, nodes) appearing as a result of technical failures, natural disasters or intentional attacks . It is focused on a practical approach to network reliability, based on application of Monte Carlo methodology to numerical evaluation of network most important structural parameters. This allows to obtain a probabilistic description of the network in the process of its destruction, to identify most important network components and to develop efficient heuristic algorithms for network optimal design. The methodology works with satisfactory accuracy and efficiency for small –to-medium size networks.”
Notes:
[Li-Alderson-Doyle-Willinger-2005 (doi) .]
L. Li, D. Alderson, J.C. Doyle, W. Willinger
“Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications”,
Internet Mathematics Journal, vol.2, #4, 2005, pp. 431–523
ResiliNets Keywords: list
Keywords:
Abstract: “There is a large, popular, and growing literature on “scale-free” networks with the Internet along with metabolic networks representing perhaps the canonical examples. While this has in many ways reinvigorated graph theory, there is unfortunately no consistent, precise definition of scale-free graphs and few rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and that the most celebrated claims regarding the Internet and biology are verifiably false. In this paper, we introduce a structural metric that allows us to differentiate between all simple, connected graphs having an identical degree sequence, which is of particular interest when that sequence satisfies a power law relationship. We demonstrate that the proposed structural metric yields considerable insight into the claimed properties of SF graphs and provides one possible measure of the extent to which a graph is scale-free. This structural view can be related to previously studied graph properties such as the various notions of self-similarity, likelihood, betweenness and assortativity. Our approach clarifies much of the confusion surrounding the sensational qualitative claims in the current literature, and offers a rigorous and quantitative alternative, while suggesting the potential for a rich and interesting theory. This paper is aimed at readers familiar with the basics of Internet technology and comfortable with a theorem-proof style of exposition, but who may be unfamiliar with the existing literature on scale-free networks.”
Notes: importance and relevance to ResiliNets
[Mahadevan-Krioukov-Fomenkov-Dimitropoulos-claffy-Vahdat-2006 (doi) .]
P. Mahadevan, D. Krioukov, M. Fomenkov, X. Dimitropoulos, k.c. claffy, A. Vahdat
“The internet AS-level topology: three data sources and one definitive metric”,
SIGCOMM Comput. Commun. Rev., vol.36, #1, Jan. 2006, pp. 17–26
ResiliNets Keywords: list
Keywords: internet topology
Abstract: “We calculate an extensive set of characteristics for Internet AS topologies extracted from the three data sources most frequently used by the research community: traceroutes, BGP, and WHOIS. We discover that traceroute and BGP topologies are similar to one another but differ substantially from the WHOIS topology. Among the widely considered metrics, we find that the joint degree distribution appears to fundamentally characterize Internet AS topologies as well as narrowly define values for other important metrics. We discuss the interplay between the specifics of the three data collection mechanisms and the resulting topology views. In particular, we how how the data collection peculiarities explain differences in the resulting joint degree distributions of the respective topologies. Finally, we release to the community the input topology datasets, along with the scripts and output of our calculations. This supplement hould enable researchers to validate their models against real data and to make more informed election of topology data sources for their specific needs.”
Notes: importance and relevance to ResiliNets
[Xiao-Xiao-Cheng-2008 (doi) .]
S. Xiao, G. Xiao, T. H. Cheng
“Tolerance of intentional attacks in complex communication networks”,
IEEE Communications Magazine, vol.46, #1, Jan. 2008, pp. 146–152
ResiliNets Keywords: list
Keywords: Internet, computer network reliability, fault tolerance, telecommunication network topology, telecommunication securityInternet, complex communication networks, intentional attack tolerance, local-network topology information
Abstract: “Motivated by recent developments in the theory of complex networks, we examine the tolerance of communication networks for intentional attacks that aim to crash the network by taking down network hubs. In addition to providing a brief survey of key existing results, we investigate two different effects that largely have been ignored in past studies. Many communication networks, such as the Internet, are too large for anyone to have global information of their topologies, which makes accurate, intentional attacks virtually impossible; most attacks in communication networks must propagate from nodes to adjacent nodes, utilizing local-network topology information only. We show that incomplete global information has a different impact on intentional attacks in different circumstances, and local information-based attacks can actually be highly efficient. Such insights will be helpful for the future development of efficient protection schemes against network attacks.”
Notes: importance and relevance to ResiliNets
[Bollobás-1979]
Béla Bollobás
Graph theory : an introductory course
Springer Verlag 1979.
ResiliNets Keywords: Graph theory, topology metrics
[Wilson-1996]
Robin J. Wilson
Introduction to graph theory 4th ed.
Longman 1996.
ResiliNets Keywords: Graph theory, topology metrics
[Harary-1969]
Frank Harary
Graph theory
Addison-Wesley Pub. Co. 1969
ResiliNets Keywords: Graph theory, topology metrics
[Buckley-Harary-1990]
Fred Buckley, Frank Harary
Distance in graphs
Addison-Wesley Pub. Co. 1990
ResiliNets Keywords: Graph theory, topology metrics
[Chung-1997]
Fan R. K. Chung
Spectral Graph Theory
AMS and CBMS 1997
ResiliNets Keywords: Spectral properties of graphs
Topology Inference
[Burch-Cheswick-1999 (doi) .]
H. Burch, B. Cheswick
“Mapping the Internet”,
IEEE Computer Magazine, vol.32, #4, April 1999, pp. 97–98, 102
ResiliNets Keywords: list
Keywords: Internet, colour graphics, data visualisation, intranets, utility programs, Internet map, color, information networks, intranet, link use, network changes, ownership, visual displays
Abstract: “How can you determine what the Internet or even an intranet looks like? The answer is, of course, to draw it on screen. Once you can see the data succinctly, it becomes much easier to understand. The drawing itself can help locate bottlenecks and possible points of failure. Where is that newly acquired subsidiary connected? Which business units have connections to business partners? More important, visual displays of networks have another dimension-color. Color is an easy way to display link use, status, ownership, and network changes.”
Notes: importance and relevance to ResiliNets
[Coates-Hero-Nowak-Yu-2002 (doi) .]
A. Coates, A.O Hero III, R. Nowak, Bin Yu
“Internet tomography”,
IEEE Signal Processing Magazine, vol.19, #3, May 2002, pp. 47–65
ResiliNets Keywords: list
Keywords: Internet, inference mechanisms, network servers, performance evaluation, reviews, signal processing, telecommunication network, routing, telecommunication traffic, tomography
Abstract: “Today's Internet is a massive, distributed network which continues to explode in size as e-commerce and related activities grow. The heterogeneous and largely unregulated structure of the Internet renders tasks such as dynamic routing, optimized service provision, service-level verification, and detection of anomalous/malicious behavior increasingly challenging tasks. The problem is compounded by the fact that one cannot rely on the cooperation of individual servers and routers to aid in the collection of network traffic measurements vital for these tasks. In many ways, network monitoring and inference problems bear a strong resemblance to other "inverse problems" in which key aspects of a system are not directly observable. Familiar signal processing problems such as tomographic image reconstruction, system identification, and array processing all have interesting interpretations in the networking context. This article introduces the new field of network tomography, a field which we believe will benefit greatly from the wealth of signal processing theory and algorithms .”
Notes: importance and relevance to ResiliNets
[Chang-Govindan-Jamin-Shenker-Willinger-2004 (doi) .]
H. Chang, R. Govindan, S. Jamin, S.J. Shenker, W. Willinger
“Towards capturing representative AS-level Internet topologies”,
Computer Networks, vol.44, #6, 2004, pp. 737–755
ResiliNets Keywords: list
Keywords: Internet topology, BGP routing tables
Abstract: “Recent studies on AS-level Internet connectivity have attracted considerable attention. These studies have exclusively relied on BGP data from the Oregon route-views [University of Oregon Route Views Project, http://www.routeviews.org] to derive some unexpected and intriguing results. The Oregon route-views data sets reflect AS peering relationships, as reported by BGP, seen from a handful of vantage points in the global Internet. The possibility that these data sets may provide only a very sketchy picture of the complete inter-AS connectivity of the Internet has received little scrutiny. By augmenting the Oregon route-views data with BGP summary information from a large number of Internet Looking Glass sites and with routing policy information from Internet Routing Registry (IRR) databases, we find that (1) a significant number of existing AS peering relationships remain hidden from most BGP routing tables, (2) the AS peering relationships with tier-1 ASs are in general more easily observed than those with non-tier-1 ASs, and (3) there are at least about 40% more AS peering relationships in the Internet than commonly-used BGP-derived AS maps reveal (but only about 4% more ASs). These findings point out the need for continuously questioning the applicability and completeness of data sets at hand when establishing the generality of any particular Internet-specific observation and for assessing its (in)sensitivity to deficiencies in the measurements.”
Notes: importance and relevance to ResiliNets
[Donnet-Friedman-2007 (doi) .]
B. Donnet, T. Friedman
“INTERNET TOPOLOGY DISCOVERY: A SURVEY”,
IEEE Communications Surveys & Tutorials, vol.9, #4, Fourth Quarter 2007, pp. 56–69
ResiliNets Keywords: list
Keywords:
Abstract: “Since the beginning of the nineties, the internet has undergone impressive growth. This growth can be appreciated in terms of the equipment, such as routers and links, that has been added, as well as in the numbers of users and the value of commerce that it supports. In parallel to this expansion, over the past decade the networking research community has shown a growing interest in discovering and analyzing the internet topology. Some researchers have developed tools for gathering network topology data while others have tried to understand and model the internet’s properties. These efforts have brought us to a crucial juncture for toplogy measurement infrastructures: while, previously, these were both small (in terms of number of measurement points) and monolithic, we are starting to see the deployment of large-scale distributed systems composed of hundreds or thousands of monitors. As we look forward to this next generation of systems, we take stock of what has been achieved so far. In this survey, we discuss past and current mechanisms for discovering the internet topology at various levels: the IP interface, the router, the AS, and the PoP level. In addition to discovery techniques, we provide insights into some of the well known properties of the internet topology.”
Notes: importance and relevance to ResiliNets
[Gao-2001 (doi) .]
L. Gao
“On Inferring Autonomous System Relationships in the Internet”,
IEEE/ACM Transactions on Networking, vol.9, #6, December 2001, pp. 733–745
ResiliNets Keywords: list
Keywords:
Abstract: “The Internet consists of rapidly increasing number of hosts interconnected by constantly evolving networks of links and routers. Interdomain routing in the Internet is coordinated by the Border Gateway Protocol (BGP). BGP allows each autonomous system (AS) to choose its own administrative policy in selecting routes and propagating reachability information to others. These routing policies are constrained by the contractual commercial agreements between administrative domains. For example, an AS sets its policy so that it does not provide transit services between its providers. Such policies imply that AS relationships are an important aspect of Internet structure. We propose an augmented AS graph representation that classifies AS relationships into customer–provider, peering, and sibling relationships. We classify the types of routes that can appear in BGP routing tables based on the relationships between the ASs in the path and present heuristic algorithms that infer AS relationships from BGP routing tables. The algorithms are tested on publicly available BGP routing tables. We verify our inference results with AT&T internal information on its relationship with neighboring ASs. As much as 99.1% of our inference results are confirmed by the AT&T internal information. We also verify our inferred sibling relationships with the information acquired from the WHOIS lookup service. More than half of our inferred sibling-to-sibling relationships are confirmed by the WHOIS lookup service. To the best of our knowledge, there has been no publicly available information about AS relationships and this is the first attempt in understanding and inferring AS relationships in the Internet. We show evidence that some routing table entries stem from router misconfigurations.”
Notes: importance and relevance to ResiliNets
Topology Modeling
[Waxman-1988 (doi) .]
B.M. Waxman
“Routing of multipoint connections”,
IEEE Journal on Selected Areas in Communications, vol.6, #9, Dec. 1988, pp. 1617–1622
ResiliNets Keywords: list
Keywords: packet switching, telecommunication networks, telecommunication traffic, trees (mathematics) Steiner tree problem, large-scale packet-switched network, multipoint communications, multipoint connections, routing, traffic, weighted greedy algorithm
Abstract: “The author addresses the problem of routing connections in a large-scale packet-switched network supporting multipoint communications. He gives a formal definition of several versions of the multipoint problem, including both static and dynamic versions. He looks at the Steiner tree problem as an example of the static problem and considers the experimental performance of two approximation algorithms for this problem. A weighted greedy algorithm is considered for a version of the dynamic problem which allows endpoints to come and go during the life of a connection. One of the static algorithms serves as a reference to measure the performance of the proposed weighted greedy algorithm in a series of experiments .”
Notes: importance and relevance to ResiliNets
[Zegura-Calvert-Bhattacharjee-1996 (doi) .]
E.W. Zegura, K.L. Calvert, S. Bhattacharjee
“How to model an internetwork”,
Fifteenth Annual Joint Conference of the IEEE Computer Societies. Networking the Next Generation. Proceedings IEEE , INFOCOM '96, vol. 2, March 1996, pp. 594–602
ResiliNets Keywords: list
Keywords: graph theory, internetworking, network topology, telecommunication network routing
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: importance and relevance to ResiliNets
[Watts-Strogatz-1998 (doi) .]
D. J. Watts, S. H. Strogatz
“Collective dynamics of 'small-world' networks”,
Nature, vol.393, 4 June 1998, pp. 440–442
ResiliNets Keywords: list
Keywords:
Abstract: “Networks of coupled dynamical systems have been used to model biological oscillators1, 2, 3, 4, Josephson junction arrays5,6, excitable media7, neural networks8, 9, 10, spatial games11, genetic control networks12 and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks 'rewired' to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them 'small-world' networks, by analogy with the small-world phenomenon13,14 (popularly known as six degrees of separation15). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.”
Notes: importance and relevance to ResiliNets
[Mitzenmacher-2004 (doi) .]
M. Mitzenmache
“A Brief History of Generative Models for Power Law and Lognormal Distributions ”,
Internet mathematics, vol.1, #2, 2004, pp. 226–251
ResiliNets Keywords: list
Keywords:
Abstract: “Recently, I became interested in a current debate over whether file size distributions are best modelled by a power law distribution or a lognormal distribution. In trying to learn enough about these distributions to settle the question, I found a rich and long history, spanning many fields. Indeed, several recently proposed models from the computer science community have antecedents in work from decades ago. Here, I briefly survey some of this history, focusing on underlying generative models that lead to these distributions. One finding is that lognormal and power law distributions connect quite naturally, and hence, it is not surprising that lognormal distributions have arisen as a possible alternative to power law distributions across many fields.”
Notes: importance and relevance to ResiliNets
[Faloutsos-Faloutsos-Faloutsos-1999 (doi) .]
M. Faloutsos, P. Faloutsos, C. Faloutsos
“On power-law relationships of the Internet topology”,
Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication , SIGCOMM '99, 1999, pp. 251–262
ResiliNets Keywords: list
Keywords: Design, Measurement, Performance, Theory, Verification
Abstract: “Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period. We show that our power-laws fit the real data very well resulting in correlation coefficients of 96% or higher.Our observations provide a novel perspective of the structure of the Internet. The power-laws describe concisely skewed distributions of graph properties such as the node outdegree. In addition, these power-laws can be used to estimate important parameters such as the average neighborhood size, and facilitate the design and the performance analysis of protocols. Furthermore, we can use them to generate and select realistic topologies for simulation purposes.”
Notes: importance and relevance to ResiliNets
[Barabási-Albert-1999 (doi) .]
A-L Barabási, R. Albert
“Emergence of Scaling in Random Networks”,
Science, vol.286, #5439, 1999, pp. 509–512
ResiliNets Keywords: list
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: importance and relevance to ResiliNets
[Carlson-Doyle-1999 (doi) .]
J. M. Carlson, J. Doyle
“Highly optimized tolerance: A mechanism for power laws in designed systems”,
Phys. Rev. E, vol.60, #2, Aug. 1999, pp. 1412–1427
ResiliNets Keywords: list
Keywords: HOT
Abstract: “We introduce a mechanism for generating power law distributions, referred to as highly optimized tolerance (HOT), which is motivated by biological organisms and advanced engineering technologies. Our focus is on systems which are optimized, either through natural selection or engineering design, to provide robust performance despite uncertain environments. We suggest that power laws in these systems are due to tradeoffs between yield, cost of resources, and tolerance to risks. These tradeoffs lead to highly optimized designs that allow for occasional large events. We investigate the mechanism in the context of percolation and sand pile models in order to emphasize the sharp contrasts between HOT and self-organized criticality (SOC), which has been widely suggested as the origin for power laws in complex systems. Like SOC, HOT produces power laws. However, compared to SOC, HOT states exist for densities which are higher than the critical density, and the power laws are not restricted to special values of the density. The characteristic features of HOT systems include: (1) high efficiency, performance, and robustness to designed-for uncertainties; (2) hypersensitivity to design flaws and unanticipated perturbations; (3) nongeneric, specialized, structured configurations; and (4) power laws. The first three of these are in contrast to the traditional hallmarks of criticality, and are obtained by simply adding the element of design to percolation and sand pile models, which completely changes their characteristics.”
Notes: importance and relevance to ResiliNets
[Albert-Jeong-Barabási-2000 (doi) .]
R. Albert, H. Jeong, A-L. Barabási
“Error and attack tolerance of complex networks”,
Nature, vol.409, #6819, 2000, pp. 378–382
ResiliNets Keywords: list
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: importance and relevance to ResiliNets
[Yook-Jeong-Barabási-2002 (doi) .]
S-H Yook, H. Jeong, A-L Barabási
“Modeling the Internet's large-scale topology”,
Proceedings of the National Academy of Sciences of the United States of America, vol.99, #21, Oct. 15 2002, pp. 13382–13386
ResiliNets Keywords: list
Keywords:
Abstract: “Network generators that capture the Internet's large-scale topology are crucial for the development of efficient routing protocols and modeling Internet traffic. Our ability to design realistic generators is limited by the incomplete understanding of the fundamental driving forces that affect the Internet's evolution. By combining several independent databases capturing the time evolution, topology, and physical layout of the Internet, we identify the universal mechanisms that shape the Internet's router and autonomous system level topology. We find that the physical layout of nodes form a fractal set, determined by population density patterns around the globe. The placement of links is driven by competition between preferential attachment and linear distance dependence, a marked departure from the currently used exponential laws. The universal parameters that we extract significantly restrict the class of potentially correct Internet models and indicate that the networks created by all available topology generators are fundamentally different from the current Internet.”
Notes: importance and relevance to ResiliNets
[Doyle-Alderson-Li-Low-2005 (doi) .]
J.C. Doyle, D.L. Alderson, L. Li, S. Low, M. Roughan, S. Shalunov, R. Tanaka, and W. Willinger
“The "robust yet fragile" nature of the Internet”,
Proceedings of the National Academy of Sciences, vol.102, #41, 2005, pp. 14497–14502
ResiliNets Keywords: list
Keywords: complex network, HOT, Internet topology, network design,scale-free network
Abstract: “The search for unifying properties of complex networks is popular, challenging, and important. For modeling approaches that focus on robustness and fragility as unifying concepts, the Internet is an especially attractive case study, mainly because its applications are ubiquitous and pervasive, and widely available expositions exist at every level of detail. Nevertheless, alternative approaches to modeling the Internet often make extremely different assumptions and derive opposite conclusions about fundamental properties of one and the same system. Fortunately, a detailed understanding of Internet technology combined with a unique ability to measure the network means that these differences can be understood thoroughly and resolved unambiguously. This article aims to make recent results of this process accessible beyond Internet specialists to the broader scientific community and to clarify several sources of basic methodological differences that are relevant beyond either the Internet or the two specific approaches focused on here (i.e., scale-free networks and highly optimized tolerance networks).”
Notes: Bibliographic Entries
[Chen-Chang-Govindan-Jamin-Shenker-Willinger-2002 (doi) .]
Q. Chen, H. Chang, R. Govindan, S. Jamin, S.J. Shenker, W. Willinger
“The origin of power laws in Internet topologies revisited”,
Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2002, vol.2, pp. 608–617
ResiliNets Keywords:
Keywords: Internet, graph theory, network topology, protocols, statistical analysis BGP, Internet connectivity, Internet topologies, border gateway protocol, dynamic graph models, inter autonomous system topology, power laws, vertex degree distribution
Abstract: “C. Faloutsos et al. (see Proc. ACM SIGCOMM, 1999) found that the inter autonomous system (AS) topology exhibits a power-law vertex degree distribution. This result was quite unexpected in the networking community and stirred significant interest in exploring the possible causes of this phenomenon. The work of A.-L. Barabasi and R. Albert (see Science, p.509-512, 1999) and its application to network topology generation in the work of A. Medina et al. (see Proc. MASCOTS, 2001) have explored a promising class of models that yield strict power-law vertex degree distributions. We re-examine the BGP (border gateway protocol) measurements that form the basis for the results reported by Faloutsos et al. We find that by their very nature (i.e., being strictly BGP-based), the data provides a very incomplete picture of Internet connectivity at the AS level. The AS connectivity maps constructed from this data (original maps) typically miss 20-50% or even more of the physical links in AS maps constructed using additional sources (extended maps). Subsequently, we find that while the vertex degree distributions resulting from the extended maps are heavy-tailed, they deviate significantly from a strict power law. Finally, we show that available historical data does not support the connectivity-based dynamics assumed by Barabasi and Albert. Together, our results suggest that the Internet topology at the AS level may well have developed over time following a very different set of growth processes than those proposed by Barabasi and Albert.”
Notes: importance and relevance to ResiliNets
[Fabrikant-Koutsoupias-Papadimitriou-2002 (doi) .]
A. Fabrikant, E. Koutsoupias, C.H. Papadimitriou
“Heuristically optimized trade-offs: A new paradigm for power laws in the Internet”,
Lecture notes in computer science, vol. 2380/2002, pp. 110–122
ResiliNets Keywords: list
Keywords:
Abstract: “We propose a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [Faloutsos, Faloutsos, and Faloutsos, SIGCOMM 1999] based on a toy model of Internet growth in which two objectives are optimized simultaneously: “last mile” connection costs, and transmission delays measured in hops. We also point out a similar phenomenon, anticipated in [Carlson and Doyle, Physics Review E 1999], in the distribution of file sizes. Our results seem to suggest that power laws tend to arise as a result of complex, multi-objective optimization.”
Notes: importance and relevance to ResiliNets
[Siganos-Faloutsos-Faloutsos-Faloutsos-2003 (doi) .]
G. Siganos, M. Faloutsos, P. Faloutsos, C. Faloutsos
“Power laws and the AS-level internet topology”,
IEEE/ACM Trans. Netw., vol.11, #4, Aug. 2003, pp. 514–524
ResiliNets Keywords: list
Keywords: network modeling, power laws
Abstract: “In this paper, we study and characterize the topology of the Internet at the autonomous system (AS) level. First, we show that the topology can be described efficiently with power laws. The elegance and simplicity of the power laws provide a novel perspective into the seemingly uncontrolled Internet structure. Second, we show that power laws have appeared consistently over the last five years. We also observe that the power laws hold even in the most recent and more complete topology with correlation coefficient above 99% for the degree-based power law. In addition, we study the evolution of the power-law exponents over the five-year interval and observe a variation for the degree-based power law of less than 10%. Third, we provide relationships between the exponents and other topological metrics.”
Notes: importance and relevance to ResiliNets
[Jaiswal-Rosenberg-Towsley-2004 (doi) .]
S. Jaiswal, A.L. Rosenberg, D. Towsley
“Comparing the Structure of Power-Law Graphs and the Internet AS Graph”,
Proceedings of the 12th IEEE International Conference on Network Protocols, ICNP '04, 2004, pp. 294–303
ResiliNets Keywords: list
Keywords: Internet Topology, AS Graph, power-law graphs
Abstract: “In this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS Graph with that of graphs produced by topology generators that match the power-law degree distribution of the AS graph. We are guided by the existing notion that nodes in the AS graph can be placed in tiers with the resulting graph having an hierarchical structure. Our techniques are based on identifying graph nodes at each tier, decomposing the graph by removing such nodes and their incident edges, and thus explicitly revealing the interconnection structure of the graph. We define quantitative metrics to analyze and compare the decomposition of synthetic power-law graphs with the Internet-AS graph. Through experiments, we observe qualitative similarities in the decomposition structure of the different families of power-law graphs and explain any quantitative differences based on their generative models. We believe our approach provides insight into the interconnection structure of the AS graph and will find continuing applications in evaluating the representativeness of synthetic topology generators.”
Notes: importance and relevance to ResiliNets
[Alderson-Doyle-Govindan-Willinger-2003 (doi) .]
D. Alderson,J. Doyle, R. Govindan, W. Willinger
“Toward an optimization-driven framework for designing and generating realistic Internet topologies”,
SIGCOMM Comput. Commun. Rev., vol.33, #1, 2003, pp. 41–46
ResiliNets Keywords: First Principles
Keywords: Internet topology, complex systems, highly optimized tolerance, network optimization, robustness
Abstract: “We propose a novel approach to the study of Internet topology in which we use an optimization framework to model the mechanisms driving incremental growth. While previous methods of topology generation have focused on explicit replication of statistical properties, such as node hierarchies and node degree distributions, our approach addresses the economic tradeoffs, such as cost and performance, and the technical constraints faced by a single ISP in its network design. By investigating plausible objectives and constraints in the design of actual networks, observed network properties such as certain hierarchical structures and node degree distributions can be expected to be the natural by-product of an approximately optimal solution chosen by network designers and operators. In short, we advocate here essentially an approach to network topology design, modeling, and generation that is based on the concept of Highly Optimized Tolerance (HOT). In contrast with purely descriptive topology modeling, this opens up new areas of research that focus on the causal forces at work in network design and aim at identifying the economic and technical drivers responsible for the observed large-scale network behavior. As a result, the proposed approach should have significantly more predictive power than currently pursued efforts and should provide a scientific foundation for the investigation of other important problems, such as pricing, peering, or the dynamics of routing protocols.”
Notes: importance and relevance to ResiliNets
[Li-Alderson-Willinger-Doyle-2004 (doi) .]
L. Li, D. Alderson, W. Willinger, J.C. Doyle
“A first-principles approach to understanding the internet's router-level topology”,
ACM SIGCOMM Computer Communication Review, vol.34, #4, 2004, pp. 3–14
ResiliNets Keywords: First Principles
Keywords: degree-based generators, heuristically optimal topology, network topology, topology metrics
Abstract: “A detailed understanding of the many facets of the Internet's topological structure is critical for evaluating the performance of networking protocols, for assessing the effectiveness of proposed techniques to protect the network from nefarious intrusions and attacks, or for developing improved designs for resource provisioning. Previous studies of topology have focused on interpreting measurements or on phenomenological descriptions and evaluation of graph-theoretic properties of topology generators. We propose a complementary approach of combining a more subtle use of statistics and graph theory with a first-principles theory of router-level topology that reflects practical constraints and tradeoffs. While there is an inevitable tradeoff between model complexity and fidelity, a challenge is to distill from the seemingly endless list of potentially relevant technological and economic issues the features that are most essential to a solid understanding of the intrinsic fundamentals of network topology. We claim that very simple models that incorporate hard technological constraints on router and link bandwidth and connectivity, together with abstract models of user demand and network performance, can successfully address this challenge and further resolve much of the confusion and controversy that has surrounded topology generation and evaluation.”
Notes: importance and relevance to ResiliNets
[Alderson-Li-Willinger-Doyle-2005 (doi) .]
D. Alderson, L. Li, W. Willinger, J.C. Doyle
“Understanding internet topology: principles, models, and validation”,
IEEE/ACM Trans. Netw., vol.13, #6, Dec. 2005, pp. 1205–1218
ResiliNets Keywords: list
Keywords: degree-based generators, heuristically optimal topology, network design, network topology, router configuration, topology metrics
Abstract: “Building on a recent effort that combines a first-principles approach to modeling router-level connectivity with a more pragmatic use of statistics and graph theory, we show in this paper that for the Internet, an improved understanding of its physical infrastructure is possible by viewing the physical connectivity as an annotated graph that delivers raw connectivity and bandwidth to the upper layers in the TCP/IP protocol stack, subject to practical constraints (e.g., router technology) and economic considerations (e.g., link costs). More importantly, by relying on data from Abilene, a Tier-1 ISP, and the Rocketfuel project, we provide empirical evidence in support of the proposed approach and its consistency with networking reality. To illustrate its utility, we: 1) show that our approach provides insight into the origin of high variability in measured or inferred router-level maps; 2) demonstrate that it easily accommodates the incorporation of additional objectives of network design (e.g., robustness to router failure); and 3) discuss how it complements ongoing community efforts to reverse-engineer the Internet.”
Notes: importance and relevance to ResiliNets
[Krioukov-claffy-Fomenkov-Chung-Vespignani-Willinger-2007 (doi) .]
D. Krioukov, kc. claffy, M. Fomenkov, F. Chung, A. Vespignani, W. Willinger
“The workshop on internet topology (wit) report”,
SIGCOMM Comput. Commun. Rev., vol.37, #1, 2007, pp. 69–73
ResiliNets Keywords: list
Keywords: internet topology
Abstract: “Internet topology analysis has recently experienced a surge of interest in computer science, physics, and the mathematical sciences. However, researchers from these different disciplines tend to approach the same problem from different angles. As a result, the field of Internet topology analysis and modeling must untangle sets of inconsistent findings, conflicting claims, and contradicting statements.On May 10-12, 2006, CAIDA hosted the Workshop on Internet topology (WIT). By bringing together a group of researchers spanning the areas of computer science, physics, and the mathematical sciences, the workshop aimed to improve communication across these scientific disciplines, enable interdisciplinary cross-fertilization, identify commonalities in the different approaches, promote synergy where it exists, and utilize the richness that results from exploring similar problems from multiple perspectives.This report describes the findings of the workshop, outlines a set of relevant open research problems identified by participants, and concludes with recommendations that can benefit all scientific communities interested in Internet topology research.”
Notes: importance and relevance to ResiliNets
[Haddadi-Uhlig-Moore-Mortier-Rio-2008 (doi) .]
H. Haddadi, S. Uhlig, A. Moore, R. Mortier, M. Rio
“Modeling internet topology dynamics”,
SIGCOMM Comput. Commun. Rev., vol.38, #2, Dec. 2008, pp. 65–68
ResiliNets Keywords: list
Keywords: internet, models, topology, topology generation
Abstract: “Despite the large number of papers on network topology modeling and inference, there still exists ambiguity about the real nature of the Internet AS and router level topology. While recent findings have illustrated the inaccuracies in maps inferred from BGP peering and traceroute measurements, existing topology models still produce static topologies, using simplistic assumptions about power law observations and preferential attachment.
Today, topology generators are tightly bound to the observed data used to validate them. Given that the actual properties of the Internet topology are not known, topology generators should strive to reproduce the variability that characterizes the evolution of the Internet topology over time. Future topology generators should be able to express the variations in local connectivity that makes today's Internet: peering relationships, internal AS topology and routing policies each changing over time due to failures, maintenance, upgrades and business strategies of the network. Topology generators should capture those dimensions, by allowing a certain level of randomness in the outcome, rather than enforcing structural assumptions as the truths about Internet's evolving structure, which may never be discovered”
Notes: importance and relevance to ResiliNets
[Lakhina-Byers-Crovella-Matta-2003 (doi) .]
A. Lakhina, J.W. Byers, M. Crovella, I. Matta
“On the geographic location of Internet resources”,
IEEE Journal on Selected Areas in Communications', vol.21, #6, Aug. 2003, pp. 934–948
ResiliNets Keywords: list
Keywords: Internet, delays, network topology, performance evaluation, telecommunication links, telecommunication network routing
Abstract: “One relatively unexplored question about the Internet's physical structure concerns the geographical location of its components: routers, links, and autonomous systems (ASes). We study this question using two large inventories of Internet routers and links, collected by different methods and about two years apart. We first map each router to its geographical location using two different state-of-the-art tools. We then study the relationship between router location and population density; between geographic distance and link density; and between the size and geographic extent of ASes. Our findings are consistent across the two datasets and both mapping methods. First, as expected, router density per person varies widely over different economic regions; however, in economically homogeneous regions, router density shows a strong superlinear relationship to population density. Second, the probability that two routers are directly connected is strongly dependent on distance; our data is consistent with a model in which a majority (up to 75%-95%) of link formation is based on geographical distance (as in the Waxman (1988) topology generation method). Finally, we find that ASes show high variability in geographic size, which is correlated with other measures of AS size (degree and number of interfaces). Among small to medium ASes, ASes show wide variability in their geographic dispersal; however, all ASes exceeding a certain threshold in size are maximally dispersed geographically. These findings have many implications for the next generation of topology generators, which we envisage as producing router-level graphs annotated with attributes such as link latencies, AS identifiers, and geographical locations.”
Notes: importance and relevance to ResiliNets
[Mahadevan-Krioukov-Fall-Vahdat-2006 (doi) .]
Priya Mahadevan, Dmitri Krioukov, Kevin Fall, Amin Vahdat
“Systematic Topology Analysis and Generation Using Degree Correlations”,
SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, 2006, pp. 135–146
ResiliNets Keywords: Topology generator
Keywords: Network topology, degree correlations
Abstract: “Researchers have proposed a variety of metrics to measure important graph properties, for instance, in social, biologi- cal, and computer networks. Values for a particular graph metric may capture a graph’s resilience to failure or its rout- ing efficiency. Knowledge of appropriate metric values may influence the engineering of future topologies, repair strate- gies in the face of failure, and understanding of fundamen- tal properties of existing networks. Unfortunately, there are typically no algorithms to generate graphs matching one or more proposed metrics and there is little understanding of the relationships among individual metrics or their applica- bility to different settings. We present a new, systematic approach for analyzing net- work topologies. We first introduce the dK-series of proba- bility distributions specifying all degree correlations within d-sized subgraphs of a given graph G. Increasing values of d capture progressively more properties of G at the cost of more complex representation of the probability distribu- tion. Using this series, we can quantitatively measure the distance between two graphs and construct random graphs that accurately reproduce virtually all metrics proposed in the literature. The nature of the dK-series implies that it will also capture any future metrics that may be proposed. Using our approach, we construct graphs for d = 0, 1, 2, 3 and demonstrate that these graphs reproduce, with increas- ing accuracy, important properties of measured and modeled Internet topologies. We find that the d = 2 case is sufficient for most practical purposes, while d = 3 essentially recon- structs the Internet AS- and router-level topologies exactly. We hope that a systematic method to analyze and synthe- size topologies offers a significant improvement to the set of tools available to network topology and protocol researchers.”
Notes: systematic topology generation
[Holme-Karlin-Forrest-2008 (doi) .]
P. Holme, J. Karlin, S. Forrest
“An Integrated Model of Traffic, Geography and Economy in the Internet”,
SIGCOMM Comput. Commun. Rev., vol.38, #3, July 2008, pp. 5–16
ResiliNets Keywords: list
Keywords: internet, models, geography, population
Abstract: “Modeling Internet growth is important both for understanding the current network and to predict and improve its future. To date, Internet models have typically attempted to explain a subset of the following characteristics: network structure, traffic flow, geography, and economy. In this paper we present a discrete, agent-based model, that integrates all of them. We show that the model generates networks with topologies, dynamics, and more speculatively spatial distributions that are similar to the Internet.”
Notes: importance and relevance to ResiliNets
[Chang-Jamin-Willinger-2003 (doi) .]
H. Chang, S. Jamin, WWillinger
“Internet Connectivity at the AS-level: An Optimization-Driven Modeling Approach”,
MoMeTools '03: Proceedings of the ACM SIGCOMM workshop on Models, methods and tools for reproducible network research, Karlsruhe, Germany, Dec. 2003, pp. 33–46
ResiliNets Keywords: list
Keywords: internet, models, geography, economics, peering relations
Abstract: “Two ASs are connected in the Internet AS graph only if they have a business "peering relationship." By focusing on the AS subgraph ASPC whose links represent provider-customer relationships, we develop a new optimization-driven model for Internet growth at the ASPC level. The model's defining feature is an explicit construction of a novel class of intuitive, multi-objective, local optimizations by which the different customer ASs determine in a fully distributed and decentralized fashion their "best" upstream provider AS. Key criteria that are explicitly accounted for in the formulation of these multi-objective optimization problems are (i) AS-geography, i.e., locality and number of PoPs within individual ASs; (ii) AS-specific business models, abstract toy models that describe how individual ASs choose their "best" provider; and (iii) AS evolution, a historic account of the "lives" of individual ASs in a dynamic ISP market. We show that the resulting model is broadly robust, perforce yields graphs that match inferred AS connectivity with respect to a number of different metrics, and is ideal for exploring the impact of new peering incentives or policies on AS-level connectivity.”
Notes: importance and relevance to ResiliNets
Topology Generators
[Calvert-Doar-Zegura-1997 (doi) .]
K.I. Calvert, M.B. Doar, E.W. Zegura
“Modeling Internet topology”,
IEEE Communications Magazine, vol.35, #6, June 1997, pp. 160–163
ResiliNets Keywords: GT-ITM
Keywords: Internet, computer network management, graph theory, network topology, performance evaluation, telecommunication network routingInternet topology modeling, graph based models, hierarchy, internetworking technology, network locality, network management, network performance, network topological structure, network topology, publicly available source code, routing algorithms
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: importance and relevance to ResiliNets
[Palmer-Steffan-2000 (doi) .]
C.R. Palmer, J.G. Steffan
“Generating network topologies that obey power laws”,
IEEE Global Telecommunications Conference, GLOBECOM '00, vol. 1, 2000, pp. 434–438
ResiliNets Keywords: PLOD
Keywords: Internet, graph theory, multicast communication, network topology, telecommunication networks Internet graphs, multicast study, network topology generators, power laws, power-law topologies
Abstract: “Recent studies have shown that Internet graphs and other network systems follow power-laws. Are these laws obeyed by the artificial network topologies used in network simulations? Does it matter? In this paper we show that current topology generators do not obey all of the power-laws, and we present two new topology generators that do. We also re-evaluate a multicast study to show the impact of using power-law topologies.”
Notes: importance and relevance to ResiliNets
[Medina-Matta-Byers-2000 (doi) .]
A. Medina, I. Matta,J. Byers
“On the origin of power laws in Internet topologies”,
SIGCOMM Comput. Commun. Rev., vol.30, #2, 2000, pp. 18–28
ResiliNets Keywords: BRITE
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: importance and relevance to ResiliNets
[Bu-Towsley-2002 (doi) .]
T. Bu, D. Towsley
“On distinguishing between Internet power law topology generators”,
Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE , INFOCOM 2002, vol. 2, 2002, pp. 638–647
ResiliNets Keywords: GLP
Keywords: Internet, graph theory, network topology Internet topology, WWW induced graph, clustering phenomena, node degree, power law graphs, power law topology generators
Abstract: “Recent work has shown that the node degree in the WWW induced graph and the autonomous system (AS) level Internet topology exhibit power laws. Since then, several algorithms have been proposed to generate such power law graphs. We evaluate the effectiveness of these generators to generate representative AS-level topologies. Our conclusions are mixed. Although they (mostly) do a reasonable job at capturing the power law exponent, they do less well in capturing the clustering phenomena exhibited by the Internet topology. Based on these results, we propose a variation of the recent incremental topology generator of R. Albert and A. Barabasi (see Phys. Rev. Letters, vol.85, p.5234-7, 2000) that is more successful at matching the power law exponent and the clustering behavior of the Internet. Last, we comment on the small world behavior of the Internet topology.”
Notes: importance and relevance to ResiliNets
[Tangmunarunkit-Govindan-Jamin-Shenker-Willinger-2002 (doi) .]
H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, W. Willinger
“Network topology generators: degree-based vs. structural”,
Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, SIGCOMM '02, pp. 147–159
ResiliNets Keywords: list
Keywords: degree-based generators, hierarchy, large-scale structure, network topology, structural generators, topology characterization, topology generators, topology metrics
Abstract: “Following the long-held belief that the Internet is hierarchical, the network topology generators most widely used by the Internet research community, Transit-Stub and Tiers, create networks with a deliberately hierarchical structure. However, in 1999 a seminal paper by Faloutsos et al. revealed that the Internet's degree distribution is a power-law. Because the degree distributions produced by the Transit-Stub and Tiers generators are not power-laws, the research community has largely dismissed them as inadequate and proposed new network generators that attempt to generate graphs with power-law degree distributions.Contrary to much of the current literature on network topology generators, this paper starts with the assumption that it is more important for network generators to accurately model the large-scale structure of the Internet (such as its hierarchical structure) than to faithfully imitate its local properties (such as the degree distribution). The purpose of this paper is to determine, using various topology metrics, which network generators better represent this large-scale structure. We find, much to our surprise, that network generators based on the degree distribution more accurately capture the large-scale structure of measured topologies. We then seek an explanation for this result by examining the nature of hierarchy in the Internet more closely; we find that degree-based generators produce a form of hierarchy that closely resembles the loosely hierarchical nature of the Internet.”
Notes: importance and relevance to ResiliNets
[Winick-Jamin-2002 .]
J. Winick, S. Jamin
“Inet-3.0: Internet Topology Generator”,
Tech Report UM-CSE-TR-456-02.
ResiliNets Keywords: Inet-3.0
Keywords:
Abstract: “In this report we present version 3.0 of Inet, an Autonomous System (AS) level Internet topology generator. Our understanding of the Internet topology is quickly evolving, and thus, our understanding of how synthetic topologies should be generated is changing too. We document our analysis of Inet-2.2, which highlighted two shortcommings in its topologies. Inet-3.0 improves upon Inet-2.2’s two main weaknesses by creating topologies with more accurate degree distributions and minimum vertex covers as compared to Internet topologies. We also examine numerous other metrics to show that Inet-3.0 better approximates the actual Internet AS topology than does Inet-2.2. Inet-3.0’s topologies still do not well represent the Internet in terms of maximum clique size and clustering coefficient. These related problems stress a need for a better understanding of Internet connectivity and will be addressed in future work.”
Notes: importance and relevance to ResiliNets
[Magoni-2002 (doi) .]
D. Magoni
“nem: A Software for Network Topology Analysis and Modeling”,
Proceedings of 10th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunications Systems, MASCOTS 2002, pp. 364–371
ResiliNets Keywords: nem
Keywords: Internet, digital simulation, internetworking, network topology, telecommunication computing Internet topology, internetworking, nem, network manipulator, network protocols, network topology generators, open source software
Abstract: “The design of network protocols is greatly accelerated by the use of simulators, particularly when studying a protocol's behavior in a large internetwork topology. However the accuracy of the simulation results are heavily affected by the input network topology. As taking a real map as an input is not always feasible, artificially created topologies are often used. There are many network topology generators available, but recent discoveries about the topology of the Internet have made most of them obsolete when it comes to modeling a typical part of the Internet. The paper presents a free open source software designed for network topology analysis and modeling called network manipulator (nem). It is capable of creating realistic Internet-like topologies and it can check proof them on the fly by a thorough topology analysis. The paper especially focuses on the architecture and the capabilities of the software.”
Notes: importance and relevance to ResiliNets
[Magoni-Pansiot-2002 .]
D. Magoni,J-J. Pansiot
“Analysis and Comparison of Internet Topology Generators”,
Proceedings of the Second International IFIP-TC6 Networking Conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; and Mobile and Wireless Communications, NETWORKING '02, vol. 2345/2002, pp. 364–375
ResiliNets Keywords: nem
Keywords:
Abstract: “The modeling of Internet topology is of vital importance to network researchers. Some network protocols, and particularly multicast ones, have performances that depend heavily on the network topology. That is why the topology model used for the simulation of those protocols must be as realistic as possible. In particular a protocol designed for the Internet should be tested upon Internet-like generated topologies. In this paper we provide a comparative study of three topology generators. The first two are among the latest available topology generators and the third is a generator that we have created. All of them try to generate topologies that model the measured Internet topology. We check their efficiency by comparing the produced topologies with the topology of a recently collected Internet map.”
Notes: importance and relevance to ResiliNets
[Chakrabarti-Zhan-Faloutsos-2004 .]
D. Chakrabarti, Y. Zhan, C. Faloutsos
“R-MAT: A Recursive Model for Graph Mining”,
Fourth SIAM International Conference on Data Mining , 2004, pp. 442–446
ResiliNets Keywords: R-MAT
Keywords: graph, mining, model
Abstract: “How does a ‘normal ’ computer (or social) network look like? How can we spot ‘abnormal ’ sub-networks in the Internet, or web graph? The answer to such questions is vital for outlier detection (terrorist networks, or illegal money-laundering rings), forecasting, and simulations (“how will a computer virus spread?”). The heart of the problem is finding the properties of real graphs that seem to persist over multiple disciplines. We list such “laws ” and, more importantly, we propose a simple, parsimonious model, the “recursive matrix ” (R-MAT) model, which can quickly generate realistic graphs, capturing the essence of each graph in only a few parameters. Contrary to existing generators, our model can trivially generate weighted, directed and bipartite graphs; it subsumes the celebrated Erdős-Rényi model as a special case; it can match the power law behaviors, as well as the deviations from them (like the “winner does not take it all ” model of Pennock et al. [20]). We present results on multiple, large real graphs, where we show that our parameter fitting algorithm (AutoMAT-fast) fits them very well.”
Notes: importance and relevance to ResiliNets
[Quoitin-2005 (doi) .]
B. Quoitin
“Topology generation based on network design heuristics”,
Proceedings of the 2005 ACM conference on Emerging network experiment and technology , CoNEXT '05, 2005, pp. 278–279
ResiliNets Keywords: IGen
Keywords: network design heuristics, topology generation
Abstract: “”
Notes: importance and relevance to ResiliNets
[Zhou-Zhang-Zhang-Zhuge-2006 (doi) .]
S. Zhou, G. Zhang, G. Zhang, Z. Zhuge
“Towards a Precise and Complete Internet Topology Generator”,
Proceedings of International Conference on Communications, Circuits and Systems , vol. 3, June 2006, pp. 1830–1834
ResiliNets Keywords: PFP
Keywords: Internet, graph theory, telecommunication network topology, transport protocolsAS, Internet topology generator, PFP model, autonomous systems, network protocols, numerical simulation, positive-feedback preference model
Abstract: “Correctly modeling the Internet topology is critical for the design of the next-generation network protocols. In this paper we present a more rigorous evaluation of the positive-feedback preference (PFP) model by comparing the model against a measurement of the Internet topology at the autonomous systems (AS) level which was collected later than that used in the previous evaluation, and a recent measurement of the Chinese Internet AS graph which is a local subgraph evolved fairly independently from rest of the global graph. Our numerical simulation shows that the PFP model, using the same parameters, precisely reproduces both the global AS graph and the AS subgraph in China. This work increases our confidence that the PFP model is a precise and complete Internet topology generator and suggests that the model's grow mechanisms have successfully captured the fundamental dynamics that universally govern the Internet evolution.”
Notes: importance and relevance to ResiliNets
[Wang-Byers-2007 (doi) .]
C. Wang, J.W. Byers
“Generating representative ISP topologies from first-principles”,
Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, SIGMETRICS '07, pp. 365–366
ResiliNets Keywords: list
Keywords: network design, network topology modeling, optimization
Abstract: “Understanding and modeling the factors that underlie the growth and evolution of network topologies are basic questions that impinge upon capacity planning, forecasting, and protocol research. Early topology generation work focused on generating network-wide connectivity maps, either at the AS-level or the router-level, typically with an eye towards reproducing abstract properties of observed topologies. But recently, advocates of an alternative "first-principles" approach question the feasibility of realizing representative topologies with simple generative models that do not explicitly incorporate real-world constraints, such as the relative costs of router configurations, into the model. Our work synthesizes these two lines by designing a topology generation mechanism that incorporates first-principles constraints. Our goal is more modest than that of constructing an Internet-wide topology: we aim to generate representative topologies for single ISPs. However, our methods also go well beyond previous work, as we annotate these topologies with representative capacity and latency information. Taking only demand for network services over a given region as input, we propose a natural cost model for building and interconnecting PoPs and formulate the resulting optimization problem faced by an ISP. We devise hill-climbing heuristics for this problem and demonstrate that the solutions we obtain are quantitatively similar to those in measured router-level ISP topologies, with respect to both topological properties and fault-tolerance.”
Notes: importance and relevance to ResiliNets
[Cheng-Hutchinson-Ito-2008 (doi) .]
L. Cheng, N.C. Hutchinson, M.R. Ito
“RealNet: A Topology Generator Based on Real Internet Topology”,
22nd International Conference on Advanced Information Networking and Applications , AINAW 2008, 2008, pp. 526–532
ResiliNets Keywords: RealNet
Keywords: Internet, telecommunication network routing, telecommunication network topologyBGP routing tables, RealNet, autonomous system, large-scale network simulations, realistic Internet topology generators, router cluster topology, router level topology, traceroute records
Abstract: “One of the challenges of large-scale network simulations is the lack of scalable and realistic Internet topology generators. Previous topology generators are either not scalable to millions of nodes, or not able to capture characteristics of the Internet topology. In this work, we propose a topology generator which can generate accurate large-scale models of the Internet. We extract the AS (autonomous system) level and router level topology of the Internet with various data sources such as BGP routing tables and traceroute records. With the real Internet topology, we infer the AS topology and the commercial relationship among ASes. We also group the routers into clusters according to their positions in the Internet. A compact routing core is built with the AS topology and router cluster topology. Each generated topology consists of the routing core and a set of end-hosts connected to router clusters. The generated topology is realistic since its routing core is extracted from Internet. We make the assumption of uniform routing policy within an AS. Therefore, the routing path calculation of any source/destination pair consists of finding the AS path for the source/destination ASes and finding the router level path within each AS in the AS path. Since the routing pate depends only on the routing core, its size is independent of the number of end-hosts in the generated topology.”
Notes: importance and relevance to ResiliNets
[Mahadevan-Hubble-Krioukov-Huffaker-Vahdat-2007 (doi) .]
Priya Mahadevan, Calvin Hubble, Dmitri Krioukov, Bradley Huffaker, Amin Vahdat
“Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies”,
ACM SIGCOMM Computer Communication Review, vol. 37, issue 4, Oct 2007, pp. 325–336
ResiliNets Keywords: Orbis
Keywords: Network topology, degree correlations
Abstract: “Researchers involved in designing network services and protocols rely on results from simulation and emulation environments to eval- uate correctness, performance and scalability. To better understand the behavior of these applications and to predict their performance when deployed across the Internet, the generated topologies that serve as input to simulated and emulated environments must closely match real network characteristics, not just in terms of graph struc- ture (node interconnectivity) but also with respect to various node and link annotations. Relevant annotations include link latencies, AS membership and whether a router is a peering or internal router. Finally, it should be possible to rescale a given topology to a variety of sizes while still maintaining its essential characteristics. In this paper, we propose techniques to generate annotated, Inter- net router graphs of different sizes based on existing observations of Internet characteristics. We find that our generated graphs match a variety of graph properties of observed topologies for a range of tar- get graph sizes. While the best available data of Internet topology currently remains imperfect, the quality of our generated topologies will improve with the fidelity of available measurement techniques or next generation architectures that make Internet structure more transparent.”
Notes: Topology generator: Orbis
Wireless Topology
[Bettstetter-2002 (doi) .]
C. Bettstetter
“On the minimum node degree and connectivity of a wireless multihop network”,
ACM MobiHoc , 2002, pp. 80–91
ResiliNets Keywords:
Keywords: ad hoc networking, analytical methods, connectivity, geometric random graphs, isolated nodes, minimum node degree, modeling, sensor networks
Abstract: “This paper investigates two fundamental characteristics of a wireless multi -hop network: its minimum node degree and its k--connectivity. Both topology attributes depend on the spatial distribution of the nodes and their transmission range. Using typical modeling assumptions :--- :a random uniform distribution of the nodes and a simple link model :--- :we derive an analytical expression that enables the determination of the required range r0 that creates, for a given node density ρ, an almost surely k--connected network. Equivalently, if the maximum r0 of the nodes is given, we can find out how many nodes are needed to cover a certain area with a k--connected network. We also investigate these questions by various simulations and thereby verify our analytical expressions. Finally, the impact of mobility is discussed.The results of this paper are of practical value for researchers in this area, e.g., if they set the parameters in a network--level simulation of a mobile ad hoc network or if they design a wireless sensor network. ”
Notes:
[Hekmat-Mieghem-2006 (doi) .]
R. Hekmat and P. Van Mieghem
“Connectivity in Wireless Ad-hoc Networks with a Log-normal Radio Model”,
Mobile Networks and Applications, vol. 11, #3, June 2006, pp. 351–360
ResiliNets Keywords:
Keywords: connectivity, giant component, log-normal, random graph, ad-hoc network
Abstract: “In this paper we study connectivity in wireless ad-hoc networks by modeling the network as an undirected geometric random graph. The novel aspect in our study is that for finding the link probability between nodes we use a radio model that takes into account statistical variations of the radio signal power around its mean value. We show that these variations, that are unavoidably caused by the obstructions and irregularities in the surroundings of the transmitting and the receiving antennas, have two distinct effects on the network. Firstly, they reduce the amount of correlation between links causing the geometric random graph tend to behave like a random graph with uncorrelated links. Secondly, these variations increase the probability of long links, which enhances the probability of connectivity for the network.Another new result in our paper is an equation found for the calculation of the giant component size in wireless ad-hoc networks, that takes into account the level of radio signal power variations. With simulations we show that for the planning and design of wireless ad-hoc networks or sensor networks the giant component size is a good measure for "connectivity".”
Notes:
[Hekmat-Mieghem-2003 (doi) .]
R. Hekmat and P. Van Mieghem
“Degree Distribution and Hopcount in Wireless Ad-hoc Networks”,
Proceeding of the 11th IEEE International Conference on Networks(ICON),
Sydney, Australia, September 2003, pp. 603–609
ResiliNets Keywords:
Keywords: graph theory, ad-hoc networks, radio modeling, degree distribution, hopcount
Abstract: “This article is a contribution to mathematical modeling and better understanding of fundamental properties of wireless ad-hoc networks. Our focus in this article is on the degree distribution and hopcount in these networks. The results presented here are useful in the study of connectivity and estimation of the capacity in ad-hoc networks. We model a wireless ad-hoc network as an undirected geometric random graph. For the calculation of the link probability between nodes we have suggested to use a realistic radio model; the so-called log-normal shadowing model. Through a combination of mathematical modeling and simulations we have shown that the degree distribution in wireless ad-hoc networks is binomial for low values of the mean degree. Further, we have investigated the hopcount and have shown that the hopcount in wireless ad-hoc networks can vary between the expected values for lattice networks and random graphs, depending on radio propagation conditions”
Notes:
[Doci-Springer-Xhafa-2008.pdf (doi) .]
Arta Doci, William Springer and Fatos Xhafa
“Maximum Node Degree Mobility Metric for Wireless Ad hoc Networks”,
Proceeding of The Second International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies(UBICOMM)
Valencia, Spain, October 2008, pp. 463–468
ResiliNets Keywords:
Keywords: maximum node degree , mobility metrics , real mobility model
Abstract: “Mobility has a significant impact on the ad hoc network protocol performance. Mainly, the protocol performance has been evaluated in simulations and using synthetic mobility models, which have two main drawbacks: (a) they assume that wireless devices start and remain in the simulation for a user defined simulation time; and, (b) they are unrealistic. Real mobility models that are derived from real user traces challenge the assumption that wireless devices start and remain in the simulation for the entire user defined simulation time, but they rather show that wireless nodes posses dynamic membership (nodes join and leave the simulation dynamically based on some random variable). In this paper, we evaluate the maximum node degree mobility metric for real mobility models, which has got little attention due to the assumption of static connectivity graph on the number of nodes. The contributions of this paper are two-fold. First, we introduce the algorithm that computes the maximum node degree mobility metric, which in turn provides the upper bound on the number of neighbors for a given node. Second, we show that the upper bound can be used to improve the algorithm complexity by introducing a new algorithm metric, namely efficiency. Its usefulness is shown through a case study for evaluating the gains in the algorithm complexity of incentive protocols.”
Notes:
[Ferreira-2004 (doi) .]
Afonso Ferreira
“Building a Reference Combinatorial Model for MANETs”,
IEEE Network, vol.18, #5, September–October 2004, pp. 24–29
ResiliNets Keywords: MANET, Modelling
Keywords:
Abstract: “Wireless technologies and the deployment of mobile and nomadic services are driving the emergence of complex ad hoc networks that have a highly dynamic behavior. Modeling such dynamics and creating a reference model on which results could be compared and reproduced, was stated as a fundamental issue by a recent NSF workshop on networking. In this article we show how the modeling of time-changes unsettles old questions and allows for new insights into central problems in networking, such as routing metrics, connectivity, and spanning trees. Such modeling is made possible through evolving graphs, a simple combinatorial model that helps capture the behavior or dynamic networks over time.”
Notes:
[Kim-Tipper-Krishnamurthy-2009.pdf (doi) .]
Tae-Hoon Kim, David Tipper, and Prashant Krishnamurthy
“Connectivity and Critical Point Behavior inMobile Ad hoc and Sensor Networks”,
IEEE Symposium on Computers and Communications (ISCC)
Sousse, Tunisia, July 2009, pp. 153–158
ResiliNets Keywords:
Keywords: critical point identification algorithm, mobile ad hoc network, network routes;network topology
Abstract: “A well-known approach to increase the resilience of mobile ad hoc networks (MANETs) and unstructured sensor networks is to ensure a network topology where there are at least k disjoint routes in the network between each pair of network nodes (usually called k-connectivity). Asymptotic analyses of node density requirements for k-connectivity have been considered in the literature. In this paper, we present the results of a simulation study investigating the relationship between asymptotic results in the literature and k-connectivity under varying nodal density and nodal degree. The numerical results illustrate where the asymptotic approximations breakdown and we show that this largely due to the existence of critical connectivity points in the topology. Using a critical point identification algorithm we examine how the number of critical points varies with nodal degree, nodal density and node mobility. In addition, critical point is evaluated its effectiveness on the network caused by failure.”
Notes:
Special Topics in Network Science
[Ramanathan-Bar-Noy-Basu-Johnson-Ren-Swami-Zhao-2011 (doi) .]
R. Ramanathan, A. Bar-Noy, P. Basu, M. Johnson, W. Ren, A. Swami, Q. Zhao,
“Beyond Graphs: Capturing Groups in Networks”,
Proceedings of the IEEE INFOCOM Workshop on Network Science for Communication Networks (NetSciCom), Shanghai, April 2011, pp. 870–875
ResiliNets Keywords: network groups
Keywords: Betti numbers , collaborative teams , combinatorial optimization problems , communications networks , de facto representational networks choice , network groups , network science , pairwise relationship capturing , social networks , structural analysis
Abstract: “Currently, the de facto representational choice for networks is graphs. A graph captures pairwise relationships (edges) between entities (vertices) in a network. Network science, however, is replete with group relationships that are more than the sum of the pairwise relationships. For example, collaborative teams, wireless broadcast, insurgent cells, coalitions all contain unique group dynamics that need to be captured in their respective networks. We propose the use of the (abstract) simplicial complex to model groups in networks. We show that a number of problems within social and communications networks such as network-wide broadcast and collaborative teams can be elegantly captured using simplicial complexes in a way that is not possible with graphs. We formulate combinatorial optimization problems in these areas in a simplicial setting and illustrate the applicability of topological concepts such as 'Betti numbers' in structural analysis. As an illustrative case study, we present an analysis of a real-world collaboration network, namely the ARL NS-CTA network of researchers and tasks.”
Notes: importance and relevance to ResiliNets
Network Design and Optimization
[Klincewicz-1998 (doi) .]
John G. Klincewicz
“Hub location in backbone/tributary network design: a review”,
Location Science, vol.6, #1-4, 1998, pp. 307–335
ResiliNets Keywords: list
Keywords:
Abstract: “A common architecture for a communications network consists of tributary networks, which connect nodes to hubs, and a backbone network, which interconnects the hubs. Often, because of the size of the problem or the nature of the application, the design of the backbone network and the tributary networks are considered independently. However, in many cases, it is desirable or necessary to treat backbone and tributary design as an integrated problem, in which a key decision is the choice of hub locations. We provide a review of earlier algorithmic work on this integrated problem, drawing from the literature on facility location, network design, telecommunications, computer systems and transportation. Certain key issues in modeling hub location problems in the particular context of communications networks are discussed, and possible avenues for future work are proposed.”
Notes: importance and relevance to ResiliNets
[Gavish-1992 (doi) .]
Bezalel Gavish
“Topological design of computer communication networks — The overall design problem”,
European Journal of Operational Research, vol.58, #2, 1992, pp. 149–172
ResiliNets Keywords: list
Keywords: Topological design; Lagrangean relaxation; combinatorial optimization; computer networks
Abstract: “Mathematical formulations of the topological design problem of computer communication networks are developed. The topological design of computer networks involves decisions on where to place network control processors (NCPs), selecting the set of backbone links to connect NCPs, linking end user nodes to the NCPs, and deciding on the set of routes which support communications between communicating end user node pairs. The overall design problem is formulated as a nonlinear combinatorial optimization problem, a Lagrangean relaxation of the problem is presented and effective solution procedures of the Lagrangean problem are developed. The Lagrangean solutions provide lower bounds on the optimal solutions to the complete problem. The Lagrangean-based solutions are further improved using subgradient optimization procedures. Three heuristics are developed for generating feasible solutions to the problem. The heuristic solutions are demonstrated on problems involving 200 end user nodes and up to 30 NCP locations.”
Notes: importance and relevance to ResiliNets
[Gerla-Kleinrock-1977 (doi) .]
Mario Gerla and Leonard Kleinrock
“On the Topological Design of Distributed Computer Networks”,
IEEE Transactions on Communications, vol.25, #1, 1977, pp. 48–60
ResiliNets Keywords: list
Keywords: Distributed computer systems , Packet switching
Abstract: “The problem of data transmission in a network environment involves the design of a communication subnetwork. Recently, significant progress has been made in this technology, and in this article we survey the modeling, analysis, and design of such computercommunication networks. Most of the design methodology presented has been developed with the packet-switched Advanced Research Projects Agency Network (ARPANET) in mind, although the principles extend to more general networks. We state the general design problem, decompose it into simpler subproblems, discuss the solutions to these subproblems, and then suggest a heuristic topological design procedure as a solution to the original problem.”
Notes: importance and relevance to ResiliNets
[Boorstyn-Frank-1977 (doi) .]
Robert R. Boorstyn and Howard Frank
“Large-Scale Network Topological Optimization”,
IEEE Transactions on Communications, vol.25, #1, 1977, pp. 29–47
ResiliNets Keywords: list
Keywords: Communication networks, Computer communications, Hierarchical systems
Abstract: “A cost-effective structure for a large network is a multilevel hierarchy consisting of a backbone network and a family of local access networks. The backbone network is generally a distributed network, while the local access networks are typically centralized systems. In special cases, the network may consist primarily of either centralized or distributed portions. This paper discusses topological design problems for such systems, including the concentrator location problem, the terminal assignment problem, the terminal layout problem (the constrained minimum spanning tree problem), the distributed network topological layout problem, and the backbone node location problem. Recent algorithm research, including exact and heuristic problem solutions, are described and computational experience is given. Finally, open problems in large-scale topological design are reported.”
Notes: importance and relevance to ResiliNets
[Konak-Smith-2006 (doi) .]
Abdullah Konak and Alice E. Smith
“Network Reliability Optimization”, in Handbook of Optimization in Telecommunications,
Springer, US, 2006, pp. 735–760
ResiliNets Keywords: list
Keywords: Network reliability, network resilience, network design, network survivability
Abstract: “This chapter presents design of reliable networks. The exact calculation of any general network reliability measure is NP-hard. Therefore, network designers have been reluctant to use reliability as a design criterion. However, reliability is becoming an important concern to provide continuous service quality to network customers. The chapter discusses various network reliability measures and efficient techniques to evaluate them. Two genetic algorithms are presented to demonstrate how these techniques to estimate and compute network reliability can be incorporated within an optimization algorithm. Computational experiments show that the proposed approaches significantly reduce computational effort without compromising design quality.”
Notes: importance and relevance to ResiliNets
[Minoux-1989 (doi) .]
M. Minoux
“Networks synthesis and optimum network design problems: Models, solution methods and applications”,
Networks, vol.19, #3, 1989, pp. 313–360
ResiliNets Keywords: list
Keywords:
Abstract: “This paper is intended as a survey in the area of network synthesis and optimum network design, which, in view of the importance and variety of the underlying applications, has attraced, since the early 1960s, much interest in the Operations Research community. Indeed, if the first models were studied in connection with telecommunication networks, the range of applications kept on getting broader and broader, including transportation networks, computer and teleprocessing networks, energy transport systems, water distribution networks, etc. However, beyond the apparent diversity of practical situations involved, most of these applications can be accounted for (modulo possibly a few minor adaptations), by a rather limited number of basic models. One of the main purposes of this paper is to provide the reader with a relevant classification of the area which will help him identify the fundamental structure of the problem (if any) he has to cope with, and relate it to already published work. In order to obtain a fairly good coverage of the matter, we have thus been led to identify three basic models aroung which the whole paper is organized: a general model using minimum cost multicommodity flows (Section 2); models in terms of tree-like networks (Section 3); models using nonsmultaneous single-commodity or multicommodity flows (Section 4). In each bcase the most important variants of the basic models have been surveyed with the purpose of providing as much information as possible concerning (a) the various contexts of applications from which the problem arose; (b) the main computational methods proposed in the literature for solving it, with emphasis on those techniques which appear at present, to be most efficient or promising.”
Notes: importance and relevance to ResiliNets
[Boesch-1986 (doi) .]
Francis T. Boesch
“Synthesis of reliable networks - a survey”,
IEEE Transactions on Reliability, vol.35, #3, 1986, pp. 240–246
ResiliNets Keywords: list
Keywords: Network reliability, Connectivity, Graph theory, Vulnerability, Synthesis of networks
Abstract: “In contrast to the usual probabilistic model for network reliability, one can use a deterministic model which is called network vulnerability. Many different vulnerability criteria and the related synthesis results are reviewed. These synthesis problems are all graph external questions. Certain reliability synthesis problems can be converted to a vulnerability question. Several open problems and conjectures are presented.”
Notes: importance and relevance to ResiliNets
[Soi-Aggarwal-1981 (doi) .]
Inder M. Soi and Krishnan K. Aggarwal
“Reliability Indices for Topological Design of Computer Communication Networks”,
IEEE Transactions on Reliability, vol. R-30, #5, 1981, pp. 438–443
ResiliNets Keywords: list
Keywords: Computer communication network, Network topology, Reliability indices
Abstract: “Incorporating network reliability parameter in the design of reliable computer communication networks makes the computations prohibitive. Interdependence among network topological parameters does not permit the design of a maximally reliable network using any one of the parameters and thus, there arises a real need for a composite reliability index which gives a more realistic assessment of network reliability. After discussing experimental results regarding the effects of various topological parameters on network reliability, we present two heuristic reliability indices which give a fair indication of overall reliability. A design procedure for reliable computer communication network based on local search technique incorporating these reliability indices is suggested. Having only one composite reliability index which is very simple to evaluate saves computation while designing maximally reliable computer networks as compared to the existing techniques based on several reliability measures.”
Notes: importance and relevance to ResiliNets
[Liu-Iwamura-2000 (doi) .]
Baoding Liu and K. Iwamura
“Topological optimization models for communication network with multiple reliability goals”,
Computers & Mathematics with Applications, vol. 39, #7-8, 2000, pp. 59– 69
ResiliNets Keywords: list
Keywords: Network reliability; Stochastic programming; Genetic algorithm; Simulation
Abstract: “Network reliability models for determining optimal network topology have been presented and solved by many researchers. This paper presents some new types of topological optimization model for communication network with multiple reliability goals. A stochastic simulation-based genetic algorithm is also designed for solving the proposed models. Some numerical examples are finally presented to illustrate the effectiveness of the algorithm.”
Notes: importance and relevance to ResiliNets
[Sydney-Scoglio-Gruenbacher-2013 (doi) .]
Ali Sydney, Caterina Scoglio, and Don Gruenbacher
“Optimizing algebraic connectivity by edge rewiring”,
Applied Mathematics and Computation, vol. 219, #10, 2013, pp. 5465– 5479
ResiliNets Keywords: list
Keywords: Robustness; Complex networks; Optimization; Algebraic connectivity; Rewiring
Abstract: “Robustness in complex networks is an ongoing research effort that seeks to improve the connectivity of networks against attacks and failures. Among other measures, algebraic connectivity has been used to characterize processes such as damped oscillation of liquids in connected pipes. Similar characterizations include the number of edges necessary to disconnect a network: the larger the algebraic connectivity, the larger the number of edges required to disconnect a network and hence, the more robust a network. In this paper, we answer the question, “Which edge can we rewire to have the largest increase in algebraic connectivity?”. Furthermore, we extend the rewiring of a single edge to rewiring multiple edges to realize the maximal increase in algebraic connectivity. The answer to this question above can provide insights to decision makers within various domains such as communication and transportation networks, who seek an efficient solution to optimize the connectivity and thus increase the robustness of their networks. Most importantly, our analytical and numerical results not only provide insights to the number of edges to rewire, but also the location in the network where these edges would effectuate the maximal increase in algebraic connectivity and therefore, enable a maximal increase in robustness.”
Notes: importance and relevance to ResiliNets
