1,720,983 research outputs found
Measuring the internet
No full textThe Internet is a collection of networks that use the TCP/IP suite of protocols. It has a huge impact on human activity. There are currently hundreds of millions of computers connected to the Internet, generating several petabytes traffic a day. Internet is still growing rapidly. However, the Internet today is not yet precisely characterized. One reason for this is that it is dynamic, constantly changing in size, traffic load, and application types. Recently, there has been a lot of effort put into various aspects of Internet measurements. These are important to the scientists as they provides crucial, fundamental knowledge about Internet structure and performance, and, at the same time, these measurements have added value for Internet Service Providers (ISPs) in terms of service monitoring and for management purposes. Results obtained so far in Internet measurements are very encouraging. Significant progress has been made in many fields (e.g., we now understand the topology of Web much better than before), but there are still many aspects of that the Internet's structure, workload, and applications that are unexplored. This thesis addresses several unanswered questions about the performance of the Internet at the network and the application layer. To mention a few: 1. How can we model the Internet infrastructure, and how can this be measured? 2. How does IPv6 compare to IPv4 in terms of delay and loss performance and how has performance evolved over the past few years? 3. How can we evaluate user application performance through Internet measurements? 4. Is there any method to estimate network distance based on reduced or incomplete measurements (e.g., delay and hopcount)? This thesis intends to address these questions by measuring the Internet and analyzing empirical evidence obtained from Internet data. In this thesis, we show that accurate measurements not only enhance our understanding of the current Internet, but can also lead to recommendations for improvements on both the network infrastructure and network protocols.Electrical Engineering, Mathematics and Computer Scienc
Robustness of networks
No full textOur society depends more strongly than ever on large networks such as transportation networks, the Internet and power grids. Engineers are confronted with fundamental questions such as “how to evaluate the robustness of networks for a given service?”, “how to design a robust network?”, because networks always affect the functioning of a service. Robustness is an important issue for many complex networks, on which various dynamic processes or services take place. In this work, we define robustness as follows: a network is more robust if the service on the network performs better, where performance of the service is assessed when the network is either (a) in a conventional state or (b) under perturbations, e.g. failures, virus spreadings etc. In this thesis, we survey a particular line of network robustness research within our general framework: robustness quantification, optimization and the interplay between service and network. Significant progress has been made in understanding the relationship between the structural properties of networks and the performance of the dynamics or services taking place on these networks. We assume that network robustness can be quantified by a topological measure of the network. A brief overview of the topological measures is presented. Each measure may represent the robustness of a network with respect to a certain performance aspect of a service. We focus on the measure known as algebraic connectivity. Evidence collected from literature shows that the algebraic connectivity characterizes network robustness with respect to synchronization of dynamic processes at nodes, random walks on graphs and the connectivity of a network. Moreover, we illustrate that, on a given diameter, graphs with large algebraic connectivity tend to be dense in the core and sparse at the border. Such structures distribute traffic homogeneously and are thus robust in terms of traffic engineering. How do we design a robust network with respect to the metric algebraic connectivity? First, the complete graph has the maximal algebraic connectivity, while its high link density makes it impractical to use due to the cost of constructing links. Constraints on other network features are usually set up to incorporate realistic requirements. For example, constraint on the diameter may guarantee certain end-to-end quality of service levels such as the delay. We propose a class of clique chain structures which optimize the algebraic connectivity and many other robust features among all graphs with diameter D and size N. The optimal graph within the class can be determined either analytically or numerically. Second, complete replacement of an existing infrastructure is expensive. Thus, we design strategies for robustness optimization using minor topological modifications. These strategies are evaluated in various classes of graphs. The robustness quantification, or equivalently, the association of the performance of a service with a topological measure, may be implicit. In this case, we explore the interplay between topology and service in determining the overall performance. Many services on communications and transportation networks are based on shortest path routing. The weight of a link, such as delay or bandwidth, is generally a metric optimized via shortest path routing. Thus, link weight tuning, a mechanism to control traffic, is also considered as part of the service. The interplay between service (shortest path routing and link weight tuning) and topology is investigated for the following performance aspects: (a) the structure of the transport overlay network, which is the union of shortest paths between all node pairs and (b) the traffic distribution in the overlay network. Important new findings are (i) the universal phase transition in overlay structures as we tune the link weight structure over different classes of networks and (ii) the power law traffic distribution in the overlay networks when link weights vary strongly in various classes of networks. Furthermore, we consider the service that measures a network topology as the union of shortest paths among a set of testboxes (nodes). The measured topology is a subgraph of the overlay network, which is again a subgraph of the actual network. The performance in terms of the sampling bias of measuring a network topology is investigated. Our work contributes substantially to a better understanding of the effect of the service (testbox selection) and the actual network structure on the performance with respect to sampling bias. Our investigations on the interplay between service and network reveal again the association between the performance of a service and certain topological feature, and thus, contribute to the quantification of network robustness. The multidisciplinary nature of this research lies not only in the presence of robustness issues in many complex networks, but also in that advances in other disciplines such as graph theory, combinatorics, linear algebra and statistical physics are widely applied throughout the thesis to study optimization problems and the performance of large networks.TelecommunicationsElectrical Engineering, Mathematics and Computer Scienc
Robustness and Optimization of Complex Networks: Reconstructability, Algorithms and Modeling
No full textThe infrastructure networks, including the Internet, telecommunication networks, electrical power grids, transportation networks (road, railway, waterway, and airway networks), gas networks and water networks, are becoming more and more complex. The complex infrastructure networks are crucial to our human society, and it has been a hot research \u85eld to make our complex infrastructure networks more robust and optimize the performance of them. Besides man-designed infrastructure networks, complex networks also cover many natural networks, such as social networks, ecological networks, and biological networks. In order to tackle some of the di¢ cult social issues, ecological problems, and unsolved medical problems, we must learn how these natural complex networks organize, operate, and function. Complex networks can be represented by graphs. A graph consists of a collection of nodes and a collection of links that connect the nodes. A graph is uniquely described by its adjacency matrix, of which the entry on row i and column j is one only if node i and node j in the graph is connected by a link, otherwise the entry is zero. Each adjacency matrix is associated to a unique set of eigenvalues and corresponding eigenvectors. The eigenvalues and corresponding eigenvectors of a graph, also called the spectrum of the graph, contains all the information of the graph, and the topological/physical meanings of some eigenvalues and eigenvectors are already known. The knowledge on the spectra of networks is of crucial importance to the many aspects of the researches on complex network, such as connectivity of networks and virus spreading in networks. The line graph l (G) of a graph G has a set of nodes mapping the set of links in G, and two nodes in l (G) are adjacent if and only if the corresponding links in G have a node in common. Some problems of graphs can be transformed to much easier ones in the domain of line graphs. For example, partitioning the nodes to \u85nd the overlapping communities in a graph can be done by partitioning the links in the line graph of the concerned graph. Moreover, the line graphs often share common features with real-world complex networks, like highly clustered and assortative mixing. Hence, the line graphs are considered by many to model real-world complex networks. The robustness and optimization of complex network is a rather broad research fi\u85eld. We focus on the reconstruction of complex networks from the spectral domain and the line graph domain. This thesis is organized as follows. We \u85first study the reconstruction of networks from their eigenvalues and eigenvectors and the spectral properties of networks. In the second part of this thesis, we present two algorithms which reconstruct networks from the line graph domain, the properties of the line graphs, and a random line graph model. We at last give the research results on two types of real-world networks. The adjacency matrix of a graph can be computed with its eigenvalues and eigenvectors. When some of the eigenvalues are set to zero, the adjacency matrix can still be correctly computed. We propose a measure, the reconstructability coefficient, de\u85fined as the maximum number of eigenvalues that can be removed. We \u85find that the reconstructability coefficient is linear function of the size of the network for all networks that we have studied. We give some results on the spectral metric, the energy of a graph, which is de\u85fined by the sum of the absolute value of all the eigenvalues. We also explore the relations between graph energy and the topological metric, assortativity, for many different types of networks. For the reconstruction of networks from the line graph domain, we propose two algorithms Marinlinga and Iligra. While all previous algorithms rely on Whitney'\u92s theorem, Marinlinga is based on the principle of link relabeling and endnode recognition. Iligra reconstructs the graphs from the line graph domain with the linear time complexity. This thesis extends the researches in the line graph domain. We fi\u85nd that the number of links in a line graph with a fi\u85xed number of nodes can not take some consecutive natural numbers, and these numbers are called a bandgap of the line graph. We present the exact expressions of the bands and bandgaps of the number of links in line graphs. In order to facilitate the researches in the line graph domain, we propose a model which randomly generates line graphs. The essence of our model is to merge step by step a pair of nodes in cliques, subjecting to some rules to ensure that the resulting graphs are line graphs. Thanks to the random line model, a method to generate a serial of graphs of which the assortativity increases linearly has been invented. This thesis studies two types of real-world networks: social networks and human brain networks. We characterize the overlapping community structure of the social networks of ArXiv coauthorship, IMDB actors collaboration and SourceForge collaboration, and propose a growing hypergraph model, based on preferential attachment. The proposed hypergraph model captures the fundamental properties including the power-law distributions of group size, group degree, overlapping depth, individual degree and interest-sharing number of real-world affiliation networks, and reproduces the properties of high clustering, assortative mixing and short average path length of social networks. To study brain networks, we propose a spectral randomness metric to quantize the randomness of networks. Based on the randomness measuring method, we have found that the brain networks of Alzheimer\u92s disease are statistically more random than the healthy brain networks.Intelligent SystemsElectrical Engineering, Mathematics and Computer Scienc
Quality of Service Routing in the Internet. Theory, Complexity and Algorithms
No full textThe Internet consists of many network elements that direct packets on the correct path leading towards the destination. This process of finding and following a path to the destination is called routing. Routing is not infallible and packets may get lost: the current Internet cannot give any quality guarantees regarding the packets it transports. However, many new multi-media applications (e.g., VoIP) cannot properly operate without such guarantees. Finding paths that can meet such demands is called Quality of Service (QoS) routing. This thesis identifies several algorithmic concepts of QoS routing, which are all incorporated into our exact SAMCRA algorithm. The first large-scale performance evaluation of QoS algorithms indicates that the SAMCRA algorithm performs best. Besides SAMCRA, also algorithms for multicast QoS routing and link-disjoint QoS routing are proposed in this thesis. QoS routing is NP-complete, which means that to find the exact solution, algorithms require, in the worst case, a running time that cannot be bounded by a polynomial function. This thesis also analyzes the complexity of QoS routing and argues that it is feasible in practice. Hence, exact algorithms like SAMCRA should be used instead of heuristics. Finally, the dynamics of QoS routing are discussed and some preliminary work in this area is provided. Here, too, SAMCRA outperformed the other implemented algorithms.Electrical Engineering, Mathematics and Computer Scienc
Modular Structures, Robustness and Protection of Complex Networks: Theory, Complexity and Algorithms
No full textCommunity structure is observed in many real-world networks, such as (online) social networks, where groups of friends of a certain person are often also friends of each other. Newman's modularity has been explored as an important quantitative metric for communities and clusters detection in networks. We present a new expressions and bounds for the modularity. These expressions reveal conditions for or properties of the maximum modularity of a network in both topological and spectral domains. Finding the maximum modularity of a given graph has been proven to be NP-complete and therefore, several heuristic algorithms have been proposed in the past. We investigate the problem of finding the maximum modularity of classes of graphs that have the same number of links and/or nodes and determine analytical upper bounds. Moreover, from the set of all connected graphs with a fixed number of links and/or number of nodes, we construct graphs that can attain maximum modularity, named maximum modular graphs. The maximum modularity is shown to depend on the residue obtained when the number of links is divided by the number of partitions. The modularity depends on the chosen partitioning of the network into communities, which makes finding the specific partition that leads to the maximum modularity a hard problem. In this thesis, we prove that deciding whether a graph with a given number of links, number of communities, and modularity exists is NP-complete and subsequently propose a heuristic algorithm for generating random graphs with a given modularity and number of links with different topological properties. The generator can be used in the broad field of modeling and analyzing clustered social or organizational networks. We also propose a model which can randomly generate simple graphs which are line graphs of other simple graphs, employing an iterative merging procedure. These graphs possess interesting properties, for example, if the cliques are all of the same size, the assortativities of the line graphs in each step are close to 0, and the assortativities of the corresponding root graphs increases linearly from -1 to 0 with the steps of the nodal merging process. Due to their importance to society, communication systems, represented as complex networks, should be built and operated to withstand failures. We define robustness as the maintenance of functionality under node or link removal. In this context, the functionality is measured by several graph metrics. We study the robustness of both static and time-varying networks under node removal, considering random node failure, as well as targeted node attacks based on network centrality measures. In static networks, targeted and random failures have been studied in the literature; however, existing approaches tend to study random failure in terms of average-case behavior, giving no idea of how badly network performance can degrade purely by chance. Instead of considering average network performance under random failure, we compute the network performance probability density functions as functions of the fraction of nodes removed. We show that many centrality measures produce similar targeted attacks in both static and time-varying networks and that a combination of degree centrality and eigenvector centrality may be enough to evaluate worst-case behavior of static networks: even small subsets of highly connected nodes act as a bottleneck in the static or temporal information flow, becoming critical weak points of the entire system. We also study the robustness envelope and targeted attack responses of static networks that are rewired to have high and low degree assortativities, discovering that moderate assortativity increases confer more robustness against targeted attacks whilst moderate decreases confer more robustness against random uniform attacks. In time-varying randomly generated networks, where all the nodes have similar properties, we show that random errors and intelligent attacks exhibit similar behavior. However, cost considerations make network providers less inclined to take robustness measures against failures that are unlikely to manifest, like several failures coinciding simultaneously. Considering networks embedded in a two-dimensional plane, we study the problem of finding a critical region - a part of the network that can be enclosed by a given elementary figure of predetermined size - whose destruction would lead to the highest network disruption. We determine that the problem is polynomially solvable and propose appropriate algorithms. In addition, we consider region-aware network augmentation to decrease the impact of a regional failure. We subsequently address the region-disjoint paths problem, which asks for two paths with minimum total weight between a source and a destination that cannot both be cut by a single regional failure of a given diameter (unless that failure includes the source and the destination). We prove that deciding whether region-disjoint paths exist is NP-hard and propose a heuristic region-disjoint paths algorithm. Defining an optimal protection strategy against viruses, spam propagation or any other kind of contamination process is an important feature for designing new networks and architectures. The first approach is a network adaptation, which is the interplay between disease dynamics on a network and the topology dynamics. A continuous-time adaptive Susceptible-Infectious-Susceptible (ASIS) model is introduced in order to investigate this interaction, where a susceptible node avoids infections by breaking its links to its infected neighbors while it enhances the connections with other susceptible nodes by creating links to them. When the initial topology of the network is a complete graph, an exact solution to the average metastable state fraction of infected nodes is derived without resorting to any mean-field approximation. A linear scaling law of the epidemic threshold as a function of the effective link-breaking rate is found. The metastable state topology shows high connectivity and low modularity in two cases: (i) a ``strongly adaptive'' region with very high effective spreading rate, and (ii) a ``weakly adaptive'' region with very low effective spreading rate. These two regions are separated from the other half-open elliptical-like regions of low connectivity and high modularity in a contour-line-like way. Our results indicate that the adaptation of the topology in response to disease dynamics suppresses the infection, while it promotes the network evolution towards a topology that exhibits assortative-mixing, modular structure and a binomial-like degree distribution. In the second approach, we consider decentralized optimal protection strategies when a virus is propagating over a network through a SIS epidemic process. By assuming that each node in the network can decide to protect itself from infection at a constant cost, we model our system using a game theoretic framework. We find pure, mixed equilibria, and the Price of Anarchy (PoA) in several network topologies and propose algorithms to compute a pure equilibrium.Intelligent SystemsElectrical Engineering, Mathematics and Computer Scienc
Measuring Robustness of Complex Networks
No full textSpecially over the last ten years, societies depend more strongly than ever on networked and communication systems. This dependency has grown to the point to which our well-being depends on these networked critical infrastructures. Bettering our understanding of such complex networks and their robustness is on the bleeding edge of graph theory, of which this thesis is part of.Intelligent Systems (INSY)Electrical Engineering, Mathematics and Computer Scienc
Analysis of streaming media systems
No full textMultimedia services have been popping up at tremendous speed in recent years. A large number of these multimedia streaming systems are introduced to the consumer market. Internet Service Providers, Telecommunications Operators, Service/Content Providers, and end users are interested in the mechanisms they use, the Quality-of-Experience they provide (e.g. video/audio quality, audio-video synchronization, communication delay, start-up time, etc.), the resources they need, the system stability, and the service availability. The multimedia streaming systems analyzed in this thesis include IP layer multicast TV (IPTV), Peer-to-Peer TV (P2PTV), Content Delivery Networking (CDN), Peer-to-Peer Video-on-Demand (P2PVoD), Server-to-Client Video Conferencing (IPVC) and Peer-to-Peer Video Conferencing (P2PVC). This thesis aims to study various kinds of popular streaming systems, through analytical models, measurement experiments, and simulations, to reveal their characteristics and performance in different aspects. Based on this research, we can not only better understand the behavior and limitations of existing systems and find out the key parameters that affect their performance, but also investigate the potential problems and predict the system performance for future cases. By comparing the two general streaming content delivery methods (Server-Client and Peer-to-Peer), we gain in-depth insights on “which is better” and “what determines better” for different services and in different scenarios.TelecommunicationsElectrical Engineering, Mathematics and Computer Scienc
Dynamic Routing in QoS-aware Traffic Engineered Networks
No full textWe propose a proper length function for an existing QoS routing algorithm (SAMCRA) that attempts to optimize network utilization while still offering QoS guarantees. This paper presents a comparison between several proposed algorithms via simulation studies. The simulations show that SAMCRA with a proper length performs similarly or even better than the best among the other algorithms and it has a fast running time
Internet pathfinder SAMCRA for irritation-free internet phoning
No full textThe growth of the Internet is going to grind to a halt unless fundamental changes are made in its organisation, predicts Piet Van Mieghem, Professor of Telecommunication Networks at TU Delft. Routing, the information highways traffic control system, is already a cause for concern. And, as in the case of road congestion, simply creating additional capacity will not provide relief. Van Mieghems solution: simply offer better Internet connections for sale in order to guarantee the quality of the connection for Internet phoning or video conferencing and ensure the service proceeds without interruption. Internet service providers could then really start making money from the Internet. But this calls first of all for smart routing software which is guaranteed to find the best route through the network, preferably without having to compute for days. With the routing algorithm samcra, Van Mieghem and his Network Architectures & Services (nas) research group at Delft University of Technology have found a prospective solution that, theoretically, seems to have the best qualifications. A comprehensive simulation and test programme recently carried out together with American researchers demonstrated that the computation method also satisfied the high requirements under practical conditions.Delft University of Technolog
- …
