Search

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.

The classical connectivity is typically used to capture the robustness of networks. Robustness, however, encompasses more than this simple definition of being connected. A spectral metric, referred to as the algebraic connectivity, plays a special role for the robustness since it measures the extent to which it is difficult to cut the network into independent components. We rely on the algebraic connectivity to study the robustness to random node and link failures in three important network models: the random graph of Erdos-Renyi, the small-world graph of Watts and Strogatz and the scale-free graph of Barabasi-Albert. We show that the robustness to random node and link failures significantly differs between the three models. This points to explicit influence of the network structure on the robustness. The homogeneous structure of the random graph of Erdos-Renyi implies an invariant robustness under random node failures. The heterogeneous structure of the small-world graph of Watts and Strogatz and scale-free graph of Barabasi-Albert, on the other hand, implies a non-trivial robustness to random node and link failures.

International audience; The lack of adoption of a DNS-based geographic location service as proposed in RFC 1876 has lead to the deployment of alternative ways to locate Internet hosts. The two main alternatives rely either on active probing of individual hosts or on doing exhaustive tabulation of IP address ranges and their corresponding locations. Using active measurements, we show that the geographic span of blocks of IP addresses make their location difficult to choose. Using the single location for a block of IP addresses as an estimation of the location of its IP addresses leads to significant localization errors, whatever the choice made for the location of the block. Even using as the location of a block the one that minimizes the global localization error for all its IP addresses leads to large errors. The notion of the geographic span of a block of IP addresses is fuzzy, and depends in practice very much on the uncertainty associated to the location estimates of its IP addresses.

The border gateway protocol (BGP) is used today by routers of all autonomous systems (AS) in the Internet. BGP is responsible for end-to-end reachability in the Internet. BGP routers have to exchange routes towards about 200,000 prefixes (blocks of IP addresses). Inside each AS, routers are using internal iBGP sessions to exchange their best route with other routers. The objective of an iBGP topology is to redistribute BGP routes inside the whole AS. In large ASs, some BGP routers are used as route reflectors because it reduces the total number of sessions needed for this route redistribution.Checking the correctness of iBGP configuration [1] and detecting potential problems inside the iBGP [2] are particularly difficult when route reflection [3] is used. The scalability of route reflection compared to an iBGP full-mesh comes at the cost of opacity in the choice of the best routes by the routers inside the AS. This opacity induces problems like suboptimal route choices in the IGP cost, deflection and forwarding loops. We propose to check for the optimality of the routes choice in a route reflection graph. We do so without requiring to simulate the complex operations of the BGP protocol. Our check procedure is applied to a tier-1 AS. Our simulations show that a significant fraction of suboptimal path choices may occur, between 10 and 30% in realistic cases.

The Internet was originally designed to provide connectivity from every node to every other node. However, policies can impede this connectivity [1]. This is especially true for newly allocated address space. Some Internet Service Providers (ISPs) simply do not realize that the status of previously unallocated address space has changed, and they continue blocking that space. Therefore, it would be desirable to test whether filters block newly apportioned address space before it is allocated to ISPs and/or end users.In this paper we present a methodology that aims to detect incorrectly configured filters, so that ISPs can be contacted and asked to update their router configurations. Our methodology is capable of detecting paths on which reachability is actually present but which are routed around an outdated filter configuration, as well as cases where a destination is inaccessible. To help narrowing down the most likely ASs that actually filter, we introduce a filtering likelihood index.We apply our methodology on newly allocated address space and perform initial experiments on a large fraction of ISPs, covering over 80% of all Autonomous Systems (ASs).

Recent work on hot-potato routing [1] has uncovered that large transit ASs can be sensitive to hot-potato disruptions. Designing a robust network is felt as overly important by transit providers as paths crossed by the traffic have both to be optimal and reliable. However, equipment failures and maintenance make this robustness non-trivial to achieve. To help understanding the robustness of large networks to internal failures, [2] proposed metrics aimed at capturing the sensitivity of ASs to internal failures. In this paper, we discuss the strengths and weaknesses of this approach to understand the robustness of the control plane of large networks, having carried this analysis on a large tier-1 ISP and smaller transit ASs. We argue that this sensitivity model is mainly useful for intradomain topology design, not for the design the whole routing plane of an AS. We claim that additional effort is required to understand the propagation of BGP routes inside large ASs. Complex iBGP structures, in particular route-reflection hierarchies [3], affect route diversity and optimality but it an unclear way.

International audience; Geolocation techniques aim at determining the geographic location of an Internet host based on its IP address. Currently, measurement-based geolocation techniques disregard the buffering delays that may be introduced at each hop along the path taken by probe packets. To fill this gap, we propose the GeoBuD (Geolocation using Buffering Delay estimation) approach. Although the network delay and the geographic distance between two Internet hosts have been shown to be related to some extent, leveraging buffering delay estimation at each hop for geolocation purposes is challenging for two reasons. First, correctly estimating the buffering delay at intermediate hops along a traceroute path for geolocation purposes depends on the accurate estimation of the geolocation of the intermediate routers. Second, even given an a priori knowledge of the location of the routers, estimating the buffering delays is difficult due to the coarse-grained information provided by delay measurements. Relying on traceroute measurements, we show that leveraging buffering delay estimation improves accuracy in the measurement-based geolocation of Internet hosts as well as the confidence that the geolocation service associates to each estimation.

Many large ISP networks today rely on route-reflection [1] to allow their iBGP to scale. Route-reflection was officially introduced to limit the number of iBGP sessions, compared to the $\frac{n\times(n-1)}{2}$ sessions required by an iBGP full-mesh. Besides its impact on the number of iBGP sessions, route-reflection has consequences on the diversity of the routes known to the routers inside an AS. In this paper, we quantify the diversity of the BGP routes inside a tier-1 network. Our analysis shows that the use of route-reflection leads to a very poor route diversity compared to an iBGP full-mesh. Most routers inside a tier-1 network know only a single external route in eBGP origin. We identify two causes for this lack of diversity. First, some routes are never selected as best by any router inside the network, but are known only to some border routers. Second, among the routes that are selected as best by at least one other router, a few are selected as best by a majority of the routers, preventing the propagation of many routes inside the AS. We show that the main reason for this diversity loss is how BGP chooses the best routes among those available inside the AS.

We present the TOTEM open source Traffic Engineering (TE) toolbox and a set of TE methods that we have designed and/or integrated. These methods cover intra-domain and inter-domain TE, IP-based and MPLS-based TE. They are suitable for network optimisation, better routing of traffic for providing QoS, load balancing, protection and restoration in case of failure, etc. The toolbox is designed to be deployed as an on-line tool in an operational network, or used off-line as an optimisation tool or as a traffic engineering simulator.

Nowadays, the success of MPLS is mostly due to the increasing demand for BGP/MPLS VPNs. Even though the need for interdomain LSPs is growing, no ISP today proposes the dynamic establishment of LSPs across AS boundaries. In this paper, we investigate the complexity of establishing end-to-end interdomain LSPs with QoS guarantees, based on the BGP routes locally available at a router. We explain the main issues of relying on BGP for the computation of interdomain constrained paths. To illustrate our point, we compare two LSP establishment techniques. Our benchmark technique is centralized and assumes the complete knowledge of the intradomain topologies. The second path computation technique is decentralized and relies on the BGP routes locally available by each router. Our simulations confirm that the difficulty in designing BGP-based interdomain LSP establishment techniques lies within the trade-off between the scalability of the computation technique and the quality of the path found in terms of the considered metrics.

Today, engineering interdomain traffic in large transit ASs is a difficult task due the opacity of BGP and the interactions between the BGP decision process and IGP routing. In this paper we propose Tweak-it, a tool that, based on the steady-state view of BGP routing inside the AS and the traffic demands of the AS, computes the BGP updates to be sent to the ingress routers of a transit AS to traffic engineer its interdomain traffic over time. Tweak-it is based on two components: 1) a scalable BGP simulator (CBGP) that computes the steady-state behavior of BGP routing and 2) a multiple-objectives evolutionary heuristic that can deal with multiple conflicting objectives as they can occur in real networks. Tweak-it takes the intradomain configuration (IGP weights and topology), BGP messages received from peers, BGP routing policies, and traffic demands. By keeping the state of the routing inside the AS up-to-date and based on the traffic demands, the heuristics computes how to engineer the traffic of the AS while trying to minimize the number of BGP tweakings required.

Network robustness is something all providers are striving for without being able to know all the aspects it encompasses. A key aspect of network design is the sensitivity of the network to internal failures. In this paper we present an open-source tool implementing the sensitivity model of [1], allowing network operators to study the sensitivity of their network to internal failures. We apply our methodology on the GEANT network, and we show that some of the routers and links of GEANT are sensitive to internal failures. Our results indicate that improvements can be made to the network design so as to reduce the risk of disruptions due to internal failures. Furthermore, we show great consistency between the results of the control plane and the data plane, indicating that applying the analysis on the control plane might be sufficient to provide insight into how to improve the resilience of the network to internal failures.

Many Internet Service Providers tune the configuration of the Border Gateway Protocol on their routers to control their traffic. Content providers often need to control their outgoing traffic while access providers need to control their incoming traffic. We show, by means of measurements and simulations, that controlling the flow of the incoming interdomain traffic is a difficult problem. For this purpose, we first rely on detailed measurements to show the limitations of AS-Path prepending. Then, we show by using large-scale simulations that the difficulty of controlling the flow of the incoming traffic lies in the difficulty of predicting which BGP route will be selected by distant Autonomous Systems (ASs).

Conservative cascades are among the class of multiscaling processes that accommodate the two competing objectives of deterministic and random cascades. This paper discusses in what sense the cascade model can be seen as an invariant of the Internet traffic. It explains why conservative cascades model the time-invariant properties of the Internet traffic at timescales up to hundreds of milliseconds. Furthermore, it shows the limitations of the conservative cascades to model part of the time-dependent scaling properties of Internet traffic.

In this paper we study the behavior of Internet traffic on the AS-level topology and discuss its implications on interdomain traffic engineering. We rely on two notable interdomain traffic traces, the first is one month long and the other is one day long. This study shows that interdomain paths are stable for a large majority of the traffic from a routing viewpoint. We show that the aggregation of the traffic occurring on the AS-level graph is essentially limited to direct peers, with almost no aggregation occurring at larger AS hop distances. Furthermore, only part of the AS paths of the AS-level topology that see a lot of traffic are stable, when considering their presence among the largest AS paths on a hourly basis. Relying on the largest AS paths in traffic over a time window to capture the traffic over the next time interval discloses the important variability of the traffic seen by the largest AS paths in traffic. Interdomain traffic engineering is hence due to be difficult because of the limited traffic aggregation on the AS-level topology and the important topological variability of the traffic for a significant percentage of the total traffic.

We propose a method based on multi-objective combinatorial optimization to perform interdomain traffic engineering with minimal BGP configurations. Our method relies on an evolutionary algorithin that tries to minimize an objective function by finding the successive BGP filters to be applied on the BGP routes. We study the impact of the number of providers, the traffic aggregation in the AS-level topology and the objective function on the behavior of our algorithm.

In this paper, we present a traffic engineering technique that can be used by regional ISPs and customer networks. On the basis of various characterizations of ASes in today's Internet we show the requirements of the small ASes. Then we detail the methods that such ASes currently use to engineer interdomain traffic. We present an analysis of real routing tables showing that a lot of ISPs rely on the BGP Community attribute to build scalable traffic engineering configurations. We also show that this solution suffers from several drawbacks that limit its widespread utilization. To avoid the problems of such a technique, we propose the redistribution communities, a special type of non transitive extended community attribute and show that the cost of implementing this solution is small.

This paper analyzes the characteristics of Internet traffic by studying a six days long trace of the entire interdomain traffic received by an ISP.Our study shows that this traffic is self-similar at time-scales spanning minutes to hours.W e show that this self-similarity could be explained by two factors.First, the traffic volume received from each external source exhibits a heavy-tailed distribution.Second, the number of these external sources is also self-similar.Finally, we show that self-similar traffic can be simulated by users transferring exponentially distributed traffic provided that the number of users is self-similar.

Multi-Protocol Label Switching (MPLS) is currently heavily used inside autonomous systems for traffic engineering and VPN purposes. We study the cost of using MPLS to carry interdomain traffic by analyzing two one day traces from two different ISPs. Our study shows that a hybrid MPLS+IP solution can significantly reduce the number of LSPs and signalling operations by using MPLS for high bandwidth flows and pure IP for low bandwidth flows. However, the burstiness of the interdomain LSPs could be a problem.

We propose the use of an improved Internet coordinate system to allow multihomed IPv6 sites to select the source and destination address pair that provides a low delay path. We describe the new coordinate system and evaluate its use on the RIPE test box data set.

Over the past several years, a number of measures have been introduced to characterize the topology of complex networks. We perform a statistical analysis of real data sets, representing the topology of different real-world networks. First, we show that some measures are either fully related to other topological measures or that they are significantly limited in the range of their possible values. Second, we observe that subsets of measures are highly correlated, indicating redundancy among them. Our study thus suggests that the set of commonly used measures is too extensive to concisely characterize the topology of complex networks. It also provides an important basis for classification and unification of a definite set of measures that would serve in future topological studies of complex networks.

We study the interdomain traffic as seen by a non-transit ISP, based on a six days trace covering all the interdomain links of this ISP. Our analysis considers the relationships between the interdomain traffic and the interdomain topology. We first discuss the day-to-day stability of the interdomain traffic matrix to evaluate the feasibility of interdomain traffic engineering. Then, we study the variability of the interdomain flows for several aggregation levels (prefix, AS and sink tree) and with respect to the interdomain topology seen by BGP. We show that despite the important variability of interdomain flows, it would be useful for a non-transit ISP to traffic engineer its access traffic by relying on a sink tree aggregation level.

Existing models for Internet Autonomous System (AS) topology generation make structural assumptions about the AS graph. Those assumptions typically stem from beliefs about the true properties of the Internet, e.g. hierarchy and powerlaws, which arise from incorrect interpretations of incomplete observations of the AS topology. In this paper we compare AS topology generation models with several observed AS topologies without making assumptions as to the relative importance of different topological characteristics. We find that although existing AS topology models capture degree-based properties well, they fail to capture the complexity of the local interconnection structure between ASes. We use a wide range of metrics including the weighted spectral distribution and make it available as toolbox1. We show that the shortcomings of existing models stem from underestimating the complexity of connectivity in the core due to incomplete understanding of collected data limitations, and narrow focus on particular aspects of the AS topology structure.

Part 1: Tools and Lessons Learned from Passive Measurement; International audience; In passive network measurement, the quality of an observed traffic stream is obviously crucial to the quality of the results. Some sources of error (e.g., packet loss at a capture device) are well understood, others less so. In this work, we describe the inline data integrity measurement provided by the QoF TCP-aware flow meter. By instrumenting the data structures QoF uses for detecting lost and retransmitted TCP segments, we can provide an in-band, per-flow estimate of observation loss: segments which were received by the recipient but not observed by the flow meter. We evaluate this mechanism against controlled, induced error, and apply it to two data sets used in previous work.

Part 3: Web, Content, and Interdomain; International audience; An IP prefix can be announced on the Internet from multiple endpoints, possibly leading to so-calledMOAS (Multiple-Origin AS) prefixes. Longlived MOASes are traditionally considered to be the result of network topology engineering such as prefix multihoming. Short-lived MOAS are commonly attributed to be the result of router misconfigurations.In this article, we look atMOAS prefixes in the long term and seek the patterns behind these situations. We first revisit previous work by looking at the duration of MOAS events. We group these events according to the prefix announced and show that short-lived MOASes are not due to misconfigurations, but to origin instability or route flapping.We also identify topology patterns that result inMOAS prefixes and use them to classify these events. We show that, contrary to popular belief, multihoming is neither the main use case leading to MOAS, nor the most popular pattern. Finally, we look at the evolution of these observations by analysing data collected 10 years apart.

Part 3: Web, Content, and Interdomain; International audience; In this paper, we propose a lightweight method for detecting and classifying BitTorrent content providers with a minimal amount of resources. While heavy methodologies are typically used (which require long term observation and data exchange with peers of the swarm and/or a semantic analysis of torrent websites), we instead argue that such complexity can be avoided by analyzing the correlations between peers and torrents. We apply our methodology to study over 50K torrents injected in ThePirateBay during one month, collecting more than 400K IPs addresses. Shortly, we find that exploiting the correlations not only enhances the classification accuracy keeping the technique lightweight (our methodology reliably identifies about 150 seedboxes), but also uncovers seeding behaviors that were not previously noticed (e.g., as multi-port and multi-host seeding). Finally, we correlate the popularity of seedbox hosting in our dataset to criteria (e.g., cost, storage space, Web popularity) that can bias the selection process of BitTorrent content providers.

Part 3: Web, Content, and Interdomain; International audience; With the advent of Over-The-Top content providers (OTTs), Internet Service Providers (ISPs) saw their portfolio of services shrink to the low margin role of data transporters. In order to counter this effect, some ISPs started to follow big OTTs like Facebook and Google in trying to turn their data into a valuable asset. In this paper, we explore the questions of what meaningful information can be extracted from network data, and what interesting insights it can provide. To this end, we tackle the first challenge of detecting “user-URLs”, i.e., those links that were clicked by users as opposed to those objects automatically downloaded by browsers and applications. We devise algorithms to pinpoint such URLs, and validate them on manually collected ground truth traces. We then apply them on a three-day long traffic trace spanning more than 19,000 residential users that generated around 190 million HTTP transactions. We find that only 1.6% of these observed URLs were actually clicked by users. As a first application for our methods, we answer the question of which platforms participate most in promoting the Internet content. Surprisingly, we find that, despite its notoriety, only 11% of the user URL visits are coming from Google Search.

Part 1: Tools and Lessons Learned from Passive Measurement; International audience; Passive probes continuously generate statistics on large number of metrics, that are possibly represented as probability mass functions (pmf). The need for consolidation of several pmfs arises in two contexts, namely: (i) whenever a central point collects and aggregates measurement of multiple disjoint vantage points, and (ii) whenever a local measurement processed at a single vantage point needs to be distributed over multiple cores of the same physical probe, in order to cope with growing link capacity.In this work, we take an experimental approach and study both cases using, whenever possible, open source software and datasets. Considering different consolidation strategies, we assess their accuracy in estimating pmf deciles (from the 10th to the 90th) of diverse metrics, obtaining general design and tuning guidelines. In our dataset, we find that Monotonic Spline Interpolation over a larger set of percentiles (e.g., adding 5th, 10th, 15th, and so on) allow fairly accurate pmf consolidation in both the multiple vantage points (median error is about 1%, maximum 30%) and local processes (median 0.1%, maximum 1%) cases.

Part 1: Tools and Lessons Learned from Passive Measurement; International audience; While the ultimate goal of kernel-level network stacks is to manage individual packets at line rate, the goal of user-level network monitoring applications is instead to match packets with the flow they belong to, and take actions accordingly. With current improvements in Network Interface Cards hardware and network software stacks, traffic monitors and traffic analyzers are fed with multi-Gbps streams of packets – which de facto pushes bottlenecks from kernel-level networking stack up to user-level applications. In this paper, we argue that flow management is a crucial module for any user-application that needs to process traffic at multiple Gbps, and we study the performance impact of different design choices of the flow management module by adopting a trace-driven emulation approach. While our results do not show a single “best” system settings under all circumstances, they highlight several tradeoffs, in terms of, e.g., the kind of structure, its size, and the computational complexity, that may affect system performance in a non-trivial way. We further make our software tools available to the scientific community to promote sharing of best practices.