References of "Donnet, Benoît"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailPath Similarity Evaluation using Bloom Filters
Donnet, Benoît ULg; Gueye, Bamba,; Kaafar, Mohamed Ali

in Computer Networks (2012), 56(2), 858-869

The performance of several Internet applications often relies on the measurability of path similarity between different participants. In particular, the performance of content distribution networks mainly ... [more ▼]

The performance of several Internet applications often relies on the measurability of path similarity between different participants. In particular, the performance of content distribution networks mainly relies on the awareness of content sources topology information. It is commonly admitted nowadays that, in order to ensure either path redundancy or efficient content replication, topological similarities between sources is evaluated by exchanging raw traceroute data, and by a hop by hop comparison of the IP topology observed from the sources to the several hundred or thousands of destinations. In this paper, based on real data we collected, we advocate that path similarity comparisons between different Internet entities can be much simplified using lossy coding techniques, such as Bloom filters, to exchange compressed topology information. The technique we introduce to evaluate path similarity enforces both scalability and data confidentiality while maintaining a high level of accuracy. In addition, we demonstrate that our technique is scalable as it requires a small amount of active probing and is not targets dependent. [less ▲]

Detailed reference viewed: 92 (15 ULg)
Full Text
Peer Reviewed
See detailTopology Discovery at the Router Level: a New Hybrid Tool Targeting ISP Networks
Marchetta, Pietro; Mérindol, Pascal; Donnet, Benoît ULg et al

in IEEE Journal on Selected Areas In Communications (2011), 29(6), 1776--1787

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 ... [more ▼]

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 mul- ticast components. To evaluate the performance of MERLIN, we report experimental results describing its efficiency in topology exploration and reconstruction of several ASes. [less ▲]

Detailed reference viewed: 41 (13 ULg)
Full Text
Peer Reviewed
See detailMERLIN: MEasure the Router Level of the INternet
Mérindol, Pascal; Donnet, Benoît ULg; Pansiot, Jean-Jacques, et al

in 7th Euro-NF Conference on Next Generation Internet (2011, June)

The Internet topology discovery has been an extensive research subject those last years. While the raw data is collected using large traceroute campaigns, additional probing and/or extensive computation ... [more ▼]

The Internet topology discovery has been an extensive research subject those last years. While the raw data is collected using large traceroute campaigns, additional probing and/or extensive computation are required to gather subsets of IP addresses into single identifiers cor- responding to routers. This process, known as alias reso- lution, leads to a router level map of the Internet. In this paper, we push further the Internet router level mapping with a new probing tool called MERLIN. MER- L I N is based on mrinfo, a multicast management tool. mrinfo is able to silently collect all IPv4 multicast en- abled interfaces of a router and all its multicast links to- wards its neighbors: it does not need or rely on any alias resolution mechanism. In addition, M E R L I N comes with the advantage of being much more scalable than standard data gathering techniques. In this paper, we deploy and evaluate the performance of MERLIN. We demonstrate that the use of several vantage points is crucial to circum- vent IGMP filtering in order to collect large amounts of routers. We also investigate the completeness of MERLIN by providing a lower bound on the proportion of in- formation that it may miss. Finally, our dataset and the MERLIN implementation are freely available. [less ▲]

Detailed reference viewed: 57 (8 ULg)
Full Text
See detailIP Geolocation Databases: Unreliable?
Poese, Ingmar; Uhlig, Steve; Kaafar, Mohamed Ali et al

in Computer Communication Review (2011), 41(2), 53-56

The most widely used technique for IP geolocation con- sists in building a database to keep the mapping between IP blocks and a geographic location. Several databases are available and are frequently used ... [more ▼]

The most widely used technique for IP geolocation con- sists in building a database to keep the mapping between IP blocks and a geographic location. Several databases are available and are frequently used by many services and web sites in the Internet. Contrary to widespread belief, geolo- cation databases are far from being as reliable as they claim. In this paper, we conduct a comparison of several current geolocation databases -both commercial and free- to have an insight of the limitations in their usability. First, the vast majority of entries in the databases refer only to a few popular countries (e.g., U.S.). This creates an imbalance in the representation of countries across the IP blocks of the databases. Second, these entries do not re- flect the original allocation of IP blocks, nor BGP announce- ments. In addition, we quantify the accuracy of geolocation databases on a large European ISP based on ground truth information. This is the first study using a ground truth show- ing that the overly fine granularity of database entries makes their accuracy worse, not better. Geolocation databases can claim country-level accuracy, but certainly not city-level. [less ▲]

Detailed reference viewed: 58 (7 ULg)
Full Text
Peer Reviewed
See detailImproving Retouched Bloom Filter for Trading Off Selected False Positives Against False Negatives
Donnet, Benoît ULg; Baynat, Bruno; Friedman, Timur

in Computer Networks (2010), 54(18), 3373-3387

Where distributed agents must share voluminous set membership information, Bloom fil- ters provide a compact, though lossy, way for them to do so. Numerous recent networking papers have examined the trade ... [more ▼]

Where distributed agents must share voluminous set membership information, Bloom fil- ters provide a compact, though lossy, way for them to do so. Numerous recent networking papers have examined the trade-offs between the bandwidth consumed by the transmis- sion of Bloom filters, and the error rate, which takes the form of false positives. This paper is about the retouched Bloom filter (RBF). An RBF is an extension that makes the Bloom fil- ter more flexible by permitting the removal of false positives, at the expense of introducing false negatives, and that allows a controlled trade-off between the two. We analytically show that creating RBFs through a random process decreases the false positive rate in the same proportion as the false negative rate that is generated. We further provide some simple heuristics that decrease the false positive rate more than the corresponding increase in the false negative rate, when creating RBFs. These heuristics are more effective than the ones we have presented in prior work. We further demonstrate the advantages of an RBF over a Bloom filter in a distributed network topology measurement application. We finally discuss several networking applications that could benefit from RBFs instead of standard Bloom filters. [less ▲]

Detailed reference viewed: 23 (4 ULg)
Full Text
Peer Reviewed
See detailOn the Impact of Layer-2 on Node Degree Distribution
Mérindol, Pascal; Donnet, Benoît ULg; Bonaventure, Olivier et al

in 10th annual conference on Internet measurement (2010, November)

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 ... [more ▼]

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. In this paper, based on a large dataset collected using mrinfo, we show that the node degree distribution is strongly impacted by the presence of layer-2 (L2) networks, such as switches. L2 devices interconnect a large number of routers, themselves being also involved in multiple L2 interconnec- tions. Such a situation induces nodes with very high degree when analyzing the layer-3 (L3) graph with traceroute probing. Considering the physical design of a network, our analysis provides a lower bound on the bias generated by using only an L3 view. We also provide a model that can be a first step towards L2 aware topology generation. [less ▲]

Detailed reference viewed: 52 (3 ULg)
Full Text
Peer Reviewed
See detailA Survey on Network Coordinates Systems, Design, and Security
Donnet, Benoît ULg; Gueye, Cheikh Ahmadou Bamba ULg; Kaafar, Mohamed Ali

in IEEE Communications Surveys and Tutorials (2010)

During the last decade, a new class of large-scale globally-distributed network services and applications have emerged. Those systems are flexible in the sense that they can select their communication ... [more ▼]

During the last decade, a new class of large-scale globally-distributed network services and applications have emerged. Those systems are flexible in the sense that they can select their communication path among a set of available ones. However, ceaselessly gathering network information such as latency to select a path is infeasible due to the large amount of measurement traffic it would generate. To overcome this issue, Network Coordinates Systems (NCS) have been proposed. An NCS allows hosts to predict latencies without performing direct measurements and, consequently, reduce the network resources consumption. During these last years, NCS opened new research fields in which the networking community has produced an impressive amount of work. We believe it is now time to stop and take stock of what has been achieved so far. In this paper, we survey the various NCS proposed as well as their intrinsic limits. In particular, we focus on security issues and solutions proposed to fix them. We also discuss potential future NCS developments, in particular how to use NCS for predicting bandwidth. [less ▲]

Detailed reference viewed: 93 (21 ULg)
Full Text
See detailThe 2nd Workshop on Active Internet Measurements (AIMS-2) Report
claffy, kc; Aben, Emile; Auge, Jorge, et al

in Computer Communication Review (2010), 40(5), 53-58

On February 8-10, 2010, CAIDA hosted the second Work- shop on Active Internet Measurements (AIMS-2) as part of our series of Internet Statistics and Metrics Analysis (ISMA) workshops. The goals of this ... [more ▼]

On February 8-10, 2010, CAIDA hosted the second Work- shop on Active Internet Measurements (AIMS-2) as part of our series of Internet Statistics and Metrics Analysis (ISMA) workshops. The goals of this workshop were to further our understanding of the potential and limitations of active mea- surement research and infrastructure in the wide-area Inter- net, and to promote cooperative solutions and coordinated strategies to addressing future data needs of the network and security research communities. The three-day workshop included presentations, group discussion and analysis, and focused interaction between participating researchers, oper- ators, and policymakers from all over the world. This report describes the motivation and findings of the workshop, and reviews progress on recommendations developed at the 1st Active Internet Measurements Workshop in 2009 [18]. Slides from the workshop presentations are available at [9]. [less ▲]

Detailed reference viewed: 12 (1 ULg)
Full Text
Peer Reviewed
See detailExtracting Intra-Domain Topology from mrinfo Probing
Pansiot, Jean-Jacques; Mérindol, Pascal; Donnet, Benoît ULg et al

in 11th international Conference on Passive and active Measurement (2010, April)

Activeandpassivemeasurementsfortopologydiscoveryhave known an impressive growth during the last decade. If a lot of work has been done regarding inter-domain topology discovery and modeling, only a few ... [more ▼]

Activeandpassivemeasurementsfortopologydiscoveryhave known an impressive growth during the last decade. If a lot of work has been done regarding inter-domain topology discovery and modeling, only a few papers raise the question of how to extract intra-domain topologies from measurements results. In this paper, based on a large dataset collected with mrinfo, a multicast tool that silently discovers all interfaces of a router, we provide a mechanism for retrieving intra-domain topologies. The main challenge is to assign an AS number to a border router whose IP addresses are not mapped to the same AS. Our algorithm is based on probabilistic and empirical IP allocation rules. The goal of our pool of rules is to converge to a consistent router to AS mapping. We show that our router-to-AS algorithm results in a mapping in more than 99% of the cases. Furthermore, with mrinfo, point-to-point links between routers can be distinguished from multiple links attached to a switch, providing an accurate view of the collected topologies. Finally, we provide a set of large intra-domain topologies in various formats. [less ▲]

Detailed reference viewed: 13 (2 ULg)
Full Text
Peer Reviewed
See detailQuantifying ASes Multiconnectivity Using Multicast Information
Mérindol, Pascal; Van den Schriek, Virginie; Donnet, Benoît ULg et al

in 9th ACM SIGCOMM Conference on Internet Measurement (2009, November)

Redundant connectivity (or multiconnectivity) between adjacent autonomous systems (ASes) is important for inter-domain traffic engineering and fast recovery in case of failures. However, the redundancy of ... [more ▼]

Redundant connectivity (or multiconnectivity) between adjacent autonomous systems (ASes) is important for inter-domain 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 con- nections 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. [less ▲]

Detailed reference viewed: 19 (5 ULg)
Full Text
Peer Reviewed
See detailA Comparative Study of Path Performance Metrics Predictors
Narino Mendoza, Juan Pablo; Donnet, Benoît ULg; Dupont, Pierre

in Advanced Learning for Networking Workshop (2009, June)

Using quality-of-service (QoS) metrics for Internet traffic is expected to improve greatly the performance of many network enabled applications, such as Voice-over-IP (VoIP) and video conferencing ... [more ▼]

Using quality-of-service (QoS) metrics for Internet traffic is expected to improve greatly the performance of many network enabled applications, such as Voice-over-IP (VoIP) and video conferencing. However, it is not possible to constantly measure path performance metrics (PPMs) such as delay and throughput without interfering with the network. In this work, we focus on PPMs measurement scalability by considering machine learning techniques to estimate predictive models from past PPMs observations. Using real data collected from PlanetLab, we provide a comparison between three different predictors: AR(MA) models, Kalman filters and support vector machines (SVMs). Some predic- tors use delay and throughput jointly to take advantage of the possible relationship between PPMs, while other predictors consider PPMs individually. Our current results illustrate that the best performing model is an individual SVM specific to each time series. Overall, delay can be predicted with very good accuracy while accurate forecasting of throughput remains an open problem. [less ▲]

Detailed reference viewed: 172 (0 ULg)
Full Text
Peer Reviewed
See detailDTS: a Decentralized Tracing System
Masui, Kenji; Donnet, Benoît ULg

in First International Workshop on Traffic Monitoring and Analysis (2009, May)

A new generation of widely distributed systems to measure the Internet topology at the interface level is currently being deployed. Cooperation between monitors in these systems is required in order to ... [more ▼]

A new generation of widely distributed systems to measure the Internet topology at the interface level is currently being deployed. Cooperation between monitors in these systems is required in order to avoid over-consumption of network resources. This paper proposes an architecture for a distributed topology measurement (DTM) system that, for the first time, decentralizes probing information. The key idea of our proposal is that, by utilizing a shared database as a communication method among monitors and taking advantage of the characteristics of the Doubletree algorithm, we can get rid of a specific control point, and a DTM system can be constructed in a decentralized manner. In this paper, we describe our implementation of a DTM, called Decentralized Tracing System (DTS). Decentralization within DTS is achieved using various distributed hash tables (DHTs), each one being dedicated to a particular plane (i.e., control or data). We also provide preliminary evaluation results. [less ▲]

Detailed reference viewed: 7 (0 ULg)
Full Text
Peer Reviewed
See detailIncentives for BGP Guided IP-Level Topology Discovery
Donnet, Benoît ULg

in First International Workshop on Traffic Monitoring and Analysis (2009, May)

Internet topology discovery has been an attractive research field during the past decade. In particular, the research community was interested in modeling the network as well as providing efficient tools ... [more ▼]

Internet topology discovery has been an attractive research field during the past decade. In particular, the research community was interested in modeling the network as well as providing efficient tools, mostly based on traceroute, for collecting data. In this paper, we follow this track of rendering traceroute-based exploration more efficient. We discuss incentives for coupling passive monitoring and active measurements. In particular, we show that high-level information, such as BGP updates, might be used to trigger targeted traceroutes. As a result, the network dynamics might be better capture. We also provide a freely available tool for listening to BGP feeds and triggering dedicated traceroutes. [less ▲]

Detailed reference viewed: 23 (2 ULg)
Full Text
Peer Reviewed
See detailOn the Impact of Clustering on Measurement Reduction
Saucez, Damien; Donnet, Benoît ULg; Bonaventure, Olivier

in 8th International IFIP-TC 6 Networking Conference (2009, May)

Measuring a path performance according to one or several metrics, such as delay or bandwidth, is becoming more and more pop- ular for applications. However, constantly probing the network is not suitable ... [more ▼]

Measuring a path performance according to one or several metrics, such as delay or bandwidth, is becoming more and more pop- ular for applications. However, constantly probing the network is not suitable. To make measurements more scalable, the notion of clustering has emerged. In this paper, we demonstrate that clustering can limit the measurement overhead in such a context without loosing too much accuracy. We first explain that measurement reduction can be observed when vantage points collaborate and use clustering to estimate path performance. We then show, with real traces, how effective is the overhead reduction and what is the impact in term of measurement accuracy. [less ▲]

Detailed reference viewed: 13 (1 ULg)
Full Text
Peer Reviewed
See detailInterdomain Traffic Engineering in a Locator/Identifier Separation Context
Saucez, Damien; Donnet, Benoît ULg; Iannone, Luigi et al

in IEEE Internet Network Management Workshop (2008, October)

The Routing Research Group (RRG) of the Internet Research Task Force (IRTF) is currently discussing several architectural solutions to build an interdomain routing architecture that scales better than the ... [more ▼]

The Routing Research Group (RRG) of the Internet Research Task Force (IRTF) is currently discussing several architectural solutions to build an interdomain routing architecture that scales better than the existing one. The solutions family currently being discussed concerns the addresses separation into locators and identifiers, LISP being one of them. Such a separation provides opportunities in terms of traffic engineering. In this paper, we propose an open and flexible solution that allows an ISP using identifier/locator separation to engineer its interdomain traffic. Our solution relies on the utilization of a service that transparently ranks paths using cost functions. We implement a prototype server and demonstrate its benefits in a LISP testbed. [less ▲]

Detailed reference viewed: 10 (1 ULg)
Full Text
See detailOn BGP Communities
Donnet, Benoît ULg; Bonaventure, Olivier

in Computer Communication Review (2008), 38(2),

This paper focuses on BGP communities, a particular BGP attribute that has not yet been extensively studied by the research community. It allows an operator to group destinations in a single entity to ... [more ▼]

This paper focuses on BGP communities, a particular BGP attribute that has not yet been extensively studied by the research community. It allows an operator to group destinations in a single entity to which the same routing decisions might be applied. In this paper, we show that the usage of this attribute has increased and that it also contributes to routing table growth. In addition, we propose a taxonomy of BGP community attributes to allow operators to better document their communities. We further manually collect information on BGP communities and tag it according to our taxonomy. We show that a large propor- tion of the BGP communities are used for traffic engineering purposes. [less ▲]

Detailed reference viewed: 14 (0 ULg)
Full Text
See detailIDIPS: ISP-Driven Informed Path Selection
Saucez, Damien; Donnet, Benoît ULg; Bonaventure, Olivier

Report (2008)

This draft describes a simple network-based protocol to facilitate Path Selection and to improve traffic engineering capabilities in multihomed corporate networks. With this protocol, any network device ... [more ▼]

This draft describes a simple network-based protocol to facilitate Path Selection and to improve traffic engineering capabilities in multihomed corporate networks. With this protocol, any network device that requires to select a path among a list of different paths asks a Traffic Engineering service called IDIPS (ISP-Driven Informed Path Selection) to obtain an ordered list of the possible paths. The ordering is constructed according to policies and performance requirements of both the host and network provider [less ▲]

Detailed reference viewed: 23 (1 ULg)
Full Text
See detailThe Case for an Informed Path Selection Service
Bonaventure, Olivier; Saucez, Damien,; Donnet, Benoît ULg

Report (2008)

With today's peer-to-peer applications, more and more content is available from multiple sources. In tomorrow's Internet hosts will have multiple paths to reach one destination host with the deployment of ... [more ▼]

With today's peer-to-peer applications, more and more content is available from multiple sources. In tomorrow's Internet hosts will have multiple paths to reach one destination host with the deployment of dual-stack IPv4/IPv6 hosts, but also with new techniques such as shim6 or other locator/identifier mechanisms being discussed within the IRTF RRG. All these hosts will need to rank paths in order to select the best paths to reach a given destination/content. In this draft, we propose an informed path selection service that would be queried by hosts and would rank paths based on policies and performance metrics defined by the network operator to meet his traffic engineering objectives. A companion document describes a protocol that implements this service. [less ▲]

Detailed reference viewed: 11 (2 ULg)
Full Text
Peer Reviewed
See detailInternet Topology Discovery: a Survey
Donnet, Benoît ULg; Friedman, Timur

in IEEE Communications Surveys and Tutorials (2007), 9(4), 2-15

Since the beginning of the nineties, the internet has undergone impres- sive growth. This growth can be appreciated in terms of the equipment, such as routers and links, that has been added, as well as in ... [more ▼]

Since the beginning of the nineties, the internet has undergone impres- sive 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. [less ▲]

Detailed reference viewed: 103 (9 ULg)
Full Text
Peer Reviewed
See detailOn the Construction of WiMAX Mesh Tree
Nahle, Salim; Iannone, Luigi,; Donnet, Benoît ULg et al

in IEEE Communications Letters (2007), 11(12),

The IEEE 802.16 protocol, also known as WiMAX, has been designed to support long-range communications with high bitrates, using two operation modes: Point-to-Multi-Point (PMP) and Mesh. In the mesh mode ... [more ▼]

The IEEE 802.16 protocol, also known as WiMAX, has been designed to support long-range communications with high bitrates, using two operation modes: Point-to-Multi-Point (PMP) and Mesh. In the mesh mode, Subscriber Stations (SSs) can directly communicate with each other, thus forming a tree, and can be used to forward other's data packets in a multi-hop fashion. On the contrary, in the PMP mode only one hop communication toward the Base Station (BS) is allowed. In this paper, we investigate the performance of the mesh mode by proposing an algorithm for constructing the WiMAX mesh tree. Our algorithm increases routes' effective throughput by splitting long links into multiple shorter ones. We show through simulations that this approach leads to improving the throughput capacity of WiMAX-based wireless mesh networks. [less ▲]

Detailed reference viewed: 11 (0 ULg)