References of "Friedman, Timur"
     in
Bookmark and Share    
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: 14 (3 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: 8 (1 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: 89 (7 ULg)
Full Text
Peer Reviewed
See detailInvestigating Depth-Fanout Trade-Off in WiMAX Mesh Networks
Nahle, Salim; Iannone, Luigi; Donnet, Benoît ULg et al

in 1st WEIRD Workshop on WiMAX, Wireless and Mobility (2007, May)

In the last years, Wireless Mesh Networks (WMNs) have been an emerging technology for providing cost/effective broadband Internet access. The research done insofar usually assumes that the wireless ... [more ▼]

In the last years, Wireless Mesh Networks (WMNs) have been an emerging technology for providing cost/effective broadband Internet access. The research done insofar usually assumes that the wireless backbone of a WMN is built using IEEE 802.11 technologies. Such an approach has the drawback of leading to dense and sub-optimal deployments, due to the short transmission range of this standard. Recently standardized, the WiMAX technology is supposed to transcend this limitation by a transmission range of several miles. In particular, the mesh mode of the WiMAX standard enables direct communications between subscriber stations and, hence, reduces dead zones while increasing the global throughput. In this paper, we investigate the throughput capacity of a WiMAX mesh tree. More specifically, we are interested in balancing the impact of the depth of the tree with its fanout. We provide a traffic model and evaluate the WiMAX mesh tree by simulations. [less ▲]

Detailed reference viewed: 24 (0 ULg)
Full Text
Peer Reviewed
See detailIncreasing the Coverage of a Cooperative Internet Topology Discovery Algorithm
Donnet, Benoît ULg; Huffaker, Bradley; Friedman, Timur et al

in Proceedings IFIP/TC6 Networking (2007, May)

Recently, Doubletree, a cooperative algorithm for large-scale topology discovery at the IP level, was introduced. Compared to classic probing systems, Doubletree discovers almost as many nodes and links ... [more ▼]

Recently, Doubletree, a cooperative algorithm for large-scale topology discovery at the IP level, was introduced. Compared to classic probing systems, Doubletree discovers almost as many nodes and links while strongly reducing the quantity of probes sent. This paper examines the problem of the nodes and links missed by Doubletree. In particular, this paper's first contribution is to carefully describe properties of the nodes and links that Doubletree fails to discover. We explain incomplete coverage as a consequence of the way Doubletree models the network: a tree-like structure of routes. But routes do not strictly form trees, due to load balancing and routing changes. This paper's second contribution is the Windowed Doubletree algorithm, which increases Doubletree's coverage up to 16% without increasing its load. Compared to classic Doubletree, Windowed Doubletree does not start probing at a fixed hop distance from each monitor, but randomly picks a value from a range of possible values. [less ▲]

Detailed reference viewed: 10 (1 ULg)
Full Text
Peer Reviewed
See detailDeployment of an Algorithm for Large-Scale Topology Discovery
Donnet, Benoît ULg; Raoult, Philippe; Friedman, Timur et al

in IEEE Journal on Selected Areas In Communications (2006), 24(12), 2210--2220

Topology discovery systems are starting to be in- troduced in the form of easily and widely deployed software. Unfortunately, the research community has not examined the problem of how to perform such ... [more ▼]

Topology discovery systems are starting to be in- troduced in the form of easily and widely deployed software. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. This paper describes several contributions towards that end. These were first presented in the proceedings of ACM SIGMETRICS 2005. We show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We propose two metrics focusing on redundancy in probing and show that both are important. We also propose and evaluate Doubletree, an algorithm that strongly reduces redundancy while maintaining nearly the same level of node and link coverage. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Following the SIGMETRICS work, we implemented Doubletree, and deployed it in a real network environment. This paper describes that implementation, as well as preliminary favorable results. [less ▲]

Detailed reference viewed: 16 (6 ULg)
Full Text
Peer Reviewed
See detailRetouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives
Donnet, Benoît ULg; Baynat, Bruno; Friedman, Timur

in ACM CoNEXT (2006, December)

Where distributed agents must share voluminous set mem- bership information, Bloom filters 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 mem- bership information, Bloom filters 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 transmission of Bloom filters, and the er- ror rate, which takes the form of false positives, and which rises the more the filters are compressed. In this paper, we introduce the retouched Bloom filter (RBF), an extension that makes the Bloom filter more flexible by permitting the removal of selected false positives at the expense of gen- erating random false negatives. We analytically show that RBFs created through a random process maintain an overall error rate, expressed as a combination of the false positive rate and the false negative rate, that is equal to the false positive rate of the corresponding Bloom filters. We further provide some simple heuristics that decrease the false posi- tive rate more than than the corresponding increase in the false negative rate, when creating RBFs. Finally, we demon- strate the advantages of an RBF over a Bloom filter in a dis- tributed network topology measurement application, where information about large stop sets must be shared among route tracing monitors. [less ▲]

Detailed reference viewed: 18 (2 ULg)
Full Text
Peer Reviewed
See detailApproche Récursive d'Etiquetage des Chemins Alternatifs au Niveau IP
Donnet, Benoît ULg; Huffaker, Bradley; Friedman, Timur, et al

in Colloque Francophone d'Ingénierie des Protocoles (2006, October)

Un diamant correspond à l'existence de plusieurs chemins alternatifs entre deux points du réseau. Cette notion joue un rôle important en ingénierie du trafic où il faut, par exemple, répartir la charge de ... [more ▼]

Un diamant correspond à l'existence de plusieurs chemins alternatifs entre deux points du réseau. Cette notion joue un rôle important en ingénierie du trafic où il faut, par exemple, répartir la charge de trafic entre plusieurs chemins. Ces diamants peuvent être présents au niveau SA ou au niveau IP. Cet article s'intéresse au niveau IP et propose une méthode récursive d'étiquetage des diamants, RLPA. Nous avons appliqué RLPA sur un sous-ensemble des données skitter. Nous montrons, sur le sous-ensemble observé, que les diamants sont majoritairement composés d'un seul noeud intermédiaire, qu'ils sont formés de deux chemins alternatifs, qu'ils sont essentiellement symétriques et qu'ils se situent entre 10 et 15 sauts de la source du traceroute. [less ▲]

Detailed reference viewed: 7 (3 ULg)
Full Text
Peer Reviewed
See detailEvaluation of a Large-Scale Topology Discovery Algorithm
Donnet, Benoît ULg; Huffaker, Bradley; Friedman, Timur et al

in IEEE International IP Operation and Management (IPOM) Workshop (2006, October)

In the past few years, the network measurement community has been interested in the problem of internet topology discovery using a large number (hundreds or thousands) of measurement monitors. The ... [more ▼]

In the past few years, the network measurement community has been interested in the problem of internet topology discovery using a large number (hundreds or thousands) of measurement monitors. The standard way to obtain information about the internet topology is to use the traceroute tool from a small number of monitors. Recent papers have made the case that increasing the number of monitors will give a more accurate view of the topology. However, scaling up the number of monitors is not a trivial process. Duplication of effort close to the monitors wastes time by reexploring well-known parts of the network, and close to destinations might appear to be a distributed denial-of-service (DDoS) attack as the probes converge from a set of sources towards a given destination. In prior work, authors of this paper proposed Doubletree, an algorithm for cooperative topology discovery, that reduces the load on the network, i.e., router IP interfaces and end-hosts, while discovering almost as many nodes and links as standard approaches based on traceroute. This paper presents our open-source and freely downloadable implementation of Doubletree in a tool we call traceroute@home. We evaluate the performance of our implementation on the PlanetLab testbed and discuss a large-scale monitoring infrastructure that could benefit of Doubletree. [less ▲]

Detailed reference viewed: 11 (1 ULg)
Full Text
Peer Reviewed
See detailTopology Discovery Using an Address Prefix Based Stopping Rule
Donnet, Benoît ULg; Friedman, Timur

in IFIP, International Federation for Information Processing (2006), 196

Recently, a first step towards a highly distributed IP-level topology dis- covery tool has been made with the introduction of the Doubletree al- gorithm. Doubletree is an efficient cooperative algorithm ... [more ▼]

Recently, a first step towards a highly distributed IP-level topology dis- covery tool has been made with the introduction of the Doubletree al- gorithm. Doubletree is an efficient cooperative algorithm that allows the discovery of a large portion of nodes and links in the network while strongly reducing probing redundancy on nodes and destinations as well as the amount of probes sent. In this paper, we propose to reduce more strongly the load on destinations and, more essentially, the communica- tion cost required for the cooperation by introducing a probing stopping rule based on CIDR address prefixes. [less ▲]

Detailed reference viewed: 8 (0 ULg)
Full Text
Peer Reviewed
See detailTopology Discovery Using an Address Prefix Based Stopping Rule
Donnet, Benoît ULg; Friedman, Timur

in EUNICE Workshop (2005, July)

Recently, a first step towards a highly distributed IP-level topology discovery tool has been made with the introduction of the Doubletree algorithm. Doubletree is an efficient cooperative algorithm that ... [more ▼]

Recently, a first step towards a highly distributed IP-level topology discovery tool has been made with the introduction of the Doubletree algorithm. Doubletree is an efficient cooperative algorithm that allows the discovery of a large portion of nodes and links in the network while strongly reducing probing redundancy on nodes and destinations as well as the amount of probes sent. In this paper, we propose to reduce more strongly the load on destinations and, more essentially, the communication cost required for the cooperation by introducing a probing stopping rule based on CIDR address prefixes. [less ▲]

Detailed reference viewed: 13 (1 ULg)
Full Text
Peer Reviewed
See detailEfficient Algorithms for Large-Scale Topology Discovery
Donnet, Benoît ULg; Raoult, Philippe; Friedman, Timur et al

in ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (2005, June)

There is a growing interest in discovery of internet topology at the interface level. A new generation of highly distributed measurement systems is currently being deployed. Unfortunately, the research ... [more ▼]

There is a growing interest in discovery of internet topology at the interface level. A new generation of highly distributed measurement systems is currently being deployed. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. In this paper we make two contributions toward that end. First, we show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We measure two kinds of redundancy in probing (intra- and inter-monitor) and show that both kinds are important. We show that straightforward approaches to addressing these two kinds of redundancy must take opposite tacks, and are thus fundamentally in conflict. Our second contribution is to propose and evaluate Doubletree, an algorithm that reduces both types of redundancy simultaneously on routers and end systems. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Our results show that Doubletree can reduce both types of measurement load on the network dramatically, while permitting discovery of nearly the same set of nodes and links. [less ▲]

Detailed reference viewed: 19 (0 ULg)
Full Text
Peer Reviewed
See detailA CIDR Prefix Stopping Rule for Topology Discovery
Donnet, Benoît ULg; Friedman, Timur

in Proc. Algotel (2005, May)

Recently, a first step towards a highly distributed IP-level topology discovery tool has been made with the introduction of the Doubletree algorithm. Doubletree is an efficient cooperative algorithm that ... [more ▼]

Recently, a first step towards a highly distributed IP-level topology discovery tool has been made with the introduction of the Doubletree algorithm. Doubletree is an efficient cooperative algorithm that allows the discovery of a large portion of nodes and links in the network while strongly reducing probing redundancy on nodes and destinations as well as the amount of probes sent. In this paper, we propose to reduce more strongly the load on destinations and, more essentially, the communication cost required for the cooperation by introducing a probing stop rule based on CIDR address prefixes. [less ▲]

Detailed reference viewed: 39 (0 ULg)
Full Text
Peer Reviewed
See detailImproved Algorithms for Network Topology Discovery
Donnet, Benoît ULg; Friedman, Timur; Crovella, Mark

in International Workshop on Passive and Active Network Measurement (2005, April)

Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, little consideration has been given as to how to perform large-scale topology ... [more ▼]

Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, little consideration has been given as to how to perform large-scale topology discovery efficiently and in a network-friendly manner. In prior work, we have described how large numbers of traceroute monitors can coordinate their efforts to map the network while reducing their impact on routers and end-systems. The key is for them to share information regarding the paths they have explored. However, such sharing introduces considerable communication overhead. Here, we show how to improve the communication scaling properties through the use of Bloom filters to encode a probing stop set. Also, any system in which every monitor traces routes towards every destination has inherent scaling problems. We propose capping the number of monitors per destination, and dividing the monitors into clusters, each cluster focusing on a different destination list. [less ▲]

Detailed reference viewed: 23 (3 ULg)