Internet topology discovery aims at analyzing one of the most complex distributed systems currently deployed. Usually, it relies on measurement campaigns using hop-limited probes sent with traceroute. However, this probing tool comes with several limits. In particular, some MPLS clouds might obfuscate collected traces. The resulting Internet maps, their inferred properties, and the graph models are thus incomplete and inaccurate. In this paper, we introduce TNT (Trace the Naughty Tunnels), an extension to Paris traceroute for revealing, or at least detect, all MPLS tunnels along a path. First, along with traceroute and ping probes, TNT looks for hints indicating the presence of hidden tunnels. Those hints are peculiar patterns in the resulting output, e.g., significant TTL shifts or duplicate IP addresses. Second, if those hints trigger alarms, TNT launches additional dedicated probing for possibly revealing hidden tunnels. We use GNS3 to reproduce, verify, and understand the limits and capabilities of TNT in a controlled environment. We also calibrate the thresholds at which alarms are triggered through a dedicated measurement campaign. Finally, we deploy TNT on the Archipelago platform and provide a quantified classification of MPLS configurations. All our results, including the data, the code, and the GNS3 experiments, are fully and publicly available.

In this paper, we are interested in the relationship between packet losses and routing changes in an operational network. To do so we designed and deployed DCART, a monitoring platform over RENATER, the French research and education network. Our platform collects four data sources using both active and passive measurements in order to unveil their temporal correlations. Active probing allows especially for measuring packet losses on specifically crafted data flows. Those flows explore several load balanced paths and ease the revelation of forwarding loops. Passive monitoring is achieved by listening to all routing updates from IS-IS, the intra-domain routing protocol in use, and by retrieving tickets generated by the Network Operations Center (NOC). During our monitoring campaign, we observe that most of the series of loss were correlated to routing events either because routing changes lead to inconsistent state transitions , or because faulty – and so lossy – links trigger numerous periods of link flapping. In particular, we show that losses due to forwarding loops resulting from inconsistent routing states are quite common when links come back after an outage. We also show that link flapping sometimes induce very long lasting lossy periods frequently unnoticed by the NOC. A lightweight monitoring platform such as DCART could be used to better anticipate recurrent network outages and to improve the ticketing system.

For years, Internet topology research has been conducted through active measurement. For instance, Caida builds router level topologies on top of IP level traces obtained with traceroute. The resulting graphs contain a significant amount of nodes with a very large degree, often exceeding the actual number of interfaces of a router. Although this property may result from inaccurate alias resolution, we believe that opaque MPLS clouds made of invisible tunnels are the main cause. Using Layer-2 technologies such as MPLS, routers can be configured to hide internal IP hops from traceroute. Consequently, an entry point of an MPLS network appears as the neighbor of all exit points and the whole Layer-3 network turns into a dense mesh of high degree nodes.

Traffic Engineering (TE) is one of the keys for improving packet forwarding in the Internet. It allows IP network operators to finely tune their forwarding paths according to various customer needs. One of the most popular tool available today for optimizing the use of networking resources is MPLS. On the one hand, operators may use MPLS and label distribution mechanisms such as RSVP-TE in conjunction with BGP to define multiple transit paths (for a given edge pair) verifying different constraints on their network. On the other hand, when operators simply enable LDP for distributing MPLS labels in order to improve the scalability of their network, another kind of path diversity may appear thanks to the ECMP feature of IGP routing.

Manageability and high availability are critical properties for IP networks. Unfortunately, with link-state routing protocols commonly used in such networks, topological changes lead to transient forwarding loops inducing service disruption. This reduces the frequency at which operators can adapt their network. Prior works proved that it is possible to avoid disruptions due to the planned reconfiguration of a link by progressively changing its weight, leading to a solution that does not require changing protocol specification. In this paper, we study the more general problem of gracefully modifying the logical state of multiple interfaces of a router, while minimizing the number of weight updates. Compared to single-link modifications, the router update problem is k-dimensional for a router having k neighbors. We also show that multidimensional updates may trigger new kinds of disruptions that make the problem more challenging than the single-link case. We then present and evaluate efficient algorithms that compute minimal sequences of weights enabling disruption-free router reconfigurations. Based on analysis of real IP network topologies, we show that both the size of such sequences and the computing time taken by our algorithms are limited.

The use of real-time multimedia or mission-critical applications over IP networks puts strong pressure on service providers to operate disruption-free networks. However, after any topological change, link-state Interior Gateway Protocols (IGPs), such as IS-IS or OSPF, enter a convergence phase during which transient forwarding loops may occur. Such loops increase the network latency and cause packet losses. In this paper, we propose and evaluate an efficient algorithm aimed at avoiding such traffic disruptions without modifying these IGPs. In case of an intentional modification of the weight of a link (e.g., to shut it down for maintenance operations or to perform traffic engineering), our algorithm iteratively changes this weight, splitting the modification into a sequence of loop-free transitions. The number of weight increments that need to be applied on the link to reach its target state is minimized in order to remain usable in existing networks. Analysis performed on inferred and real Internet service provider (ISP) topologies shows that few weight increments are required to handle most link shutdown events (less than two intermediate metrics for more than 85% of the links). The evaluation of our implementation also reveals that these minimal sequences can be computed in a reasonable time.

Manageability and evolvability are crucial needs for IP networks. Unfortunately, planned topological changes may lead to transient forwarding loops in link-state routing protocols commonly used in IP networks. These lead to service unavailability, reducing the frequency at which operators can adapt the network topology. Prior works proved that the state of a given link can be modified while avoiding forwarding inconsistencies without changing protocol specifications. In this paper, we study the more general problem of gracefully modifying the state of an entire router, while minimizing the induced operational impact. As opposed to a single-link modification, the router update problem is k-dimensional for a node of degree k. Moreover, we show that the interplay between operations applied at the router granularity can lead to loops that do not occur considering a single-link modification. In this paper, we present an efficient algorithm that computes minimal sequences of weights to be configured on the links of the updated node. Based on real IP network topologies, we show that the size of such sequence is limited in practice.

Fingerprinting networking equipment has many potential applications and benefits in network management and security. More generally, it is useful for the understanding of network structures and their behaviors. In this paper, we describe a simple fingerprinting mechanism based on the initial TTL values used by routers to reply to various probing messages. We show that main classes obtained using this simple mechanism are meaningful to distinguish routers platforms. Besides, it comes at a very low additional cost compared to standard active topology discovery measurements. As a proof of concept, we apply our method to gain more insight on the behavior of MPLS routers and to, thus, more accurately quantify their visible/invisible deployment.

Recent developments in router level topology discovery have suggested the introduction of IGMP probing in addition to standard techniques such as traceroute and alias resolution. With a single IGMP probe, one can obtain all multicast interfaces and links of a multicast router. If such a probing is a promising approach, we noticed that IGMP probes are subject to filtering, leading so to the fragmentation of the collected multicast graph into several disjoint connected components. In this paper, we cope with the fragmentation issue. Our contributions are threefold: (i) we experimentally quantify the damages caused by IGMP filtering on collected topologies of large tier-1 ISPs; (ii) using traceroute data, we construct a hybrid graph and estimate how far each IGMP fragment is from each other; (iii) we provide and experimentally evaluate a recursive approach for reconnecting disjoint multicast components. The key idea of the third contribution is to recursively apply alias resolution to reassemble disjoint fragments and, thus, progressively extend the mapping of the targeted ISP. Data presented in the paper, as well as reconstructed topologies, are freely available at http://svnet.u-strasbg.fr/merlin.

Most multicast flows such as IPTV are streamed at a constant rate using UDP. To fairly share the bandwidth with TCP streams, several multicast congestion controls have been proposed. Highly scalable and most efficient ones are receiver-driven and use dynamic multicast groups, which means that each group begins to send at a high rate and slows down progressively. Each receiver joins groups to obtain a fair rate and thus gets a different amount of the data sent by the source. Thereby, despite promising results in terms of fairness, it is a challenging task to efficiently use these dynamic groups and to send useful data whatever the amount of data acquired by a receiver. This article presents a sequencer which maps out application data to dynamic groups in an optimal way. Multiple applications such as file transfer or video streaming, can use this sequencer, thanks to a simple API usable with any buffer containing the most important data first. This API insures that a receiver subscribed to N% of the source rate obtains the N% most important data of each buffer sent by the source. This solution is experimented on two test beds providing ideal or realistic network conditions. The first results prove the sequencer optimal performances, as well as the agreement between the received rate and the importance of the received data. However, the second scenario shows that even with this optimal sequencer, a lossy network may impact on the performances of applications unable to use data containing gaps. But, an extra evaluation shows that a simple FEC mechanism is enough to remove most of this impact. Finally, to show the relevance of this sequencer to the application layer, we propose a file transfer software using a FEC encoding. Results show the file transfer efficiency as a download with a single receiver generates only little more overhead than TCP. Moreover, download time is almost independent of the number of receivers, and is already faster than TCP with only 2 competing downloads.

For a long time, traceroute measurements combined with alias resolution methods have been the sole way to collect Internet router level maps. Recently, a new approach has been introduced with the use of a multicast management tool, mrinfo, and a recursive probing scheme. In this paper, after analyzing advantages and drawbacks of probing approaches based on traceroute and mrinfo, we propose a hybrid discovery tool, Merlin (MEasure the Router Level of the INternet), mixing mrinfo and traceroute probes. Using a central server controlling a set of distributed vantage points in order to increase the exploration coverage while limiting the probing redundancy, the purpose of Merlin is to provide an accurate router level map inside a targeted Autonomous System (AS). Merlin also takes advantage of alias resolution methods to reconnect scattered multicast components. To evaluate the performance of Merlin, we report experimental results describing its efficiency in topology exploration and reconstruction of several ASes.

The Internet topology data collected through traceroute exploration has been extensively studied in the past. In particular, a remarkable property of the Internet, the power-law shape of node degree distribution, drew the attention of the research community. Several studies have since questioned this property.

Redundant connectivity (or multiconnectivity) between adjacent autonomous systems (ASes) is important for interdomain traffic engineering and fast recovery in case of failures. However, the redundancy of ASes business relationship links has not been quantitatively studied, mainly due to the difficulty of obtaining relevant data. In this paper, we show that the mrinfo multicast monitoring tool can provide useful data about the Internet topology and such redundant links in particular. Our analysis relies on more than four years of daily queries to about ten thousand routers mapped into more than two hundred ASes. We demonstrate that peering links between ASes are frequently redundant. In particular, our analysis shows that more than half of the studied ASes pairs are connected through multiple physical links. We then refine our analysis by considering the different types of ASes and their business relationships. A particular result of our analysis is that at least 75% of the peer-to-peer relationships between adjacent Tier-1 ASes are redundant, i.e., the connections between these ASes involve several physical links. Our analysis is conservative, providing so a lower bound, as some links might not be seen by mrinfo due to ISPs filtering policies.

Internet service providers have to provision network resources to optimize bandwidth utilization. Dynamic routing protocols take traffic variations into account to control the load distribution. Multipath routing protocols attempt to take advantage of the path diversity to bring network robustness and reliability. Indeed, with a specific traffic engineering policy, they enable load balancing across several paths. Our aim is to compute a set of loopfree paths in order to allow routers to share the load on several next hops depending on current load measurement. In this paper, we first describe our original Incoming Interface Multipath Routing technique, DT(p), then we present a scheme for load balancing, DT(p)-TE, based on link monitoring. We evaluate and compare our technique with several existing approaches by a set of simulations, using different scenarios and topologies. The simulations results suggest that the path diversity achieved with our proposition can significantly improve the network response time.

Steven Deering's multicast communication model offers a powerful and flexible service for group communicating processes. Sending a multidestination datagram with only one local source operation, implicit source discovery for an open group, and logical binding. All theses features without limits on group size and dynamics. This proposition, later called any source multicast (ASM) has not been deployed at large scale on Internet partially because of the unscalability of multicast routing protocols. A new service model but potentially scalable to the whole Internet has been proposed: source specific multicast (SSM). It is less powerful because it needs an explicit source discovery mechanism for receivers. In this paper, we propose and evaluate such a session layer mechanism. This protocol offers the source discovery service missing from source specific multicast routing. We have implemented this protocol, which permits us to evaluate its feasibility and scalability.

Many protocols and applications need a discovery mechanism to enable a given client node to locate one or several specific nodes involved in the same communication. However, there is no protocol ready to fulfill this service at the network layer. Every protocol usually implements its own solution. In particular, multicast protocols often use a search technique called expanding ring search. This method searches for those specific nodes in all directions and thus uses much bandwidth. However, a typical search can usually restrict its scan in a specific direction. To answer this problem, we propose a network layer search service in replacement of the expanding ring search whenever it is appropriate. This service is based on an oriented multicasting protocol in order to ensure an efficiency higher than the expanding ring search. The oriented multicasting principle is to channel the multicasting of search packets towards a special node, involved in the communication, in order to scan only a limited area. We describe both the network layer search service and the oriented multicasting and we provide comparative simulation results between our service and the expanding ring search.

Creating a network topology is the first step in building a scenario for a network protocol simulation. The simulation results usually depend on the topology layout, especially for routing and multicasting protocols. Therefore the topology used should be generated with the highest possible accuracy. In particular, protocols designed for the Internet should be simulated over Internet-like topologies. Many topology generators currently exist but the discovery of power laws in the Internet has brought new constraints upon the generated topologies. We introduce a flexible novel way to create Internet-like topologies. It is based on an algorithm that performs a sampling on a measured Internet map. The created topologies accurately comply with the newly found power laws as well as other more common topology properties such as the average path length.

An increasing number of Internet applications and services will require the use of multicast in the near future. However, only a few techniques are currently used in network-layer multicast routing protocols, such as flooding, pruning or reverse path construction methods. We propose an algorithm to define a new way of multicasting. The base principle is to perform a limited multicast channeled around the unicast path joining the sender to a specific destination, hence the name "oriented". This algorithm is close to reverse path multicast algorithms but the flooding is much more controlled. A protocol based on our algorithm could have many applications such as performing network node searches in a specific area. The algorithm is tailored as to be scalable to enable its use in an inter-domain environment.