Benoit Donnet

Philippe Raoult

Timur Friedman

Efficient Route Tracing from a Single Source

Traceroute is a networking tool that allows one to discover the path that packets take from a source machine, through the network, to a destination machine. It is widely used as an engineering tool, and also as a scientific tool, such as for discovery of the network topology at the IP level. In prior work, authors on this technical report have shown how to improve the efficiency of route tracing from multiple cooperating monitors. However, it is not unusual for a route tracing monitor to operate in isolation. Somewhat different strategies are required for this case, and this report is the first systematic study of those requirements. Standard traceroute is inefficient when used repeatedly towards multiple destinations, as it repeatedly probes the same interfaces close to the source. Others have recognized this inefficiency and have proposed tracing backwards from the destinations and stopping probing upon encounter with a previously-seen interface. One of this technical report's contributions is to quantify for the first time the efficiency of this approach. Another contribution is to describe the effect of non-responding destinations on this efficiency. Since a large portion of destination machines do not reply to probe packets, backwards probing from the destination is often infeasible. We propose an algorithm to tackle non-responding destinations, and we find that our algorithm can strongly decrease probing redundancy at the cost of a small reduction in node and link discovery.

Introduction

Traceroute [START_REF] Jacobsen | traceroute," UNIX[END_REF] is a networking diagnostic tool natively available on most of the operating systems. It allows one to determine the path followed by a packet. Traceroute allows therefore to draw up the map of router interfaces present along the path between a machine S (the source or the monitor ) and a machine D (the destination). Traceroute has also engineering applications as it can be used, for instance, to detect routers that fail in a network. This report proposes and evaluates improvements to standard traceroute for tracing routes from a single point.

Today's most extensive tracing system at the IP interface level, skitter [START_REF] Huffaker | Topology discovery by active probing[END_REF], uses 24 monitors, each targeting on the order of one million destinations. In the fashion of skitter, scamper [START_REF]IPv6 scamper[END_REF] makes use of several monitors to traceroute IPv6 networks. The Distributed Internet MEasurements & Simulations [START_REF] Shavitt | DIMES: Let the internet measure itself[END_REF] (Dimes) is a measurement infrastructure somewhat similar to the famous SETI@home [START_REF] Anderson | SETI@home: An experiment in public-resource computing[END_REF]. SETI@home's screensaver downloads and analyzes radio-telescope data. The idea behind Dimes is to provide to the research community a publicly downloadable distributed route tracing tool. It was released as a daemon in September 2004. The Dimes agent performs Internet measurements such as traceroute and ping at a low rate, consuming at peak 1KB/sec. At the time of writing this report, Dimes counts more than 8,700 agents scattered over five continents. In the fashion of skitter, scamper [START_REF]IPv6 scamper[END_REF] makes use of several monitors to traceroute IPv6 networks. Other well known systems, such as Ripe NCC TTM [START_REF] Georgatos | Providing active measurements as a regular service for ISPs[END_REF] and Nlanr AMP [START_REF] Mcgregor | The NLANR network analysis infrastructure[END_REF], each employs a larger set of monitors, on the order of one-to two-hundred, but they avoid probing outside their own network. Scriptroute [START_REF] Spring | Scriptroute: A public internet measurement facility[END_REF] is a system that allows an ordinary internet user to perform network measurements from several distributed vantage points. It proposes remote measurement execution on PlanetLab nodes [START_REF]PlanetLab project[END_REF], through a daemon that implements ping, hop-by-hop bandwidth measurement, and a number of other utilities in addition to traceroute.

Recently, in the context of large-scale internet topology discovery, we have shown [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF] that standard traceroute probing (such as skitter) is particularly inefficient due to duplication of effort at two levels: measurements made by an individual monitor that replicate its own work (intra-monitor redundancy), and measurements made by multiple monitors that replicate each other's work (inter-monitor redundancy). Using skitter data from August 2004, we have quantified both kinds of redundancy. We showed that intra-monitor redundancy is high close to each monitor and, with respect to intermonitor redundancy, we find that most interfaces are visited by all monitors, especially when close to destinations. We further proposed an algorithm, Doubletree, for reducing both forms of redundancy at the same time.

This technical report focuses more deeply on the intra-monitor redundancy problem. Systems that discover internet topology at IP level from a set of isolated vantage points (i.e., there is no cooperation between monitors) have interest to reduce their intra-monitor redundancy. By sending much less probes, monitors can probe the network more frequently. The more frequent snapshots you have, the more accurate should be your view of the topology. This technical report demonstrates how a monitor can act to reduce its intra-monitor redundancy.

The nature of intra-monitor redundancy suggest to start probing far from the traceroute monitor and probe backwards (i.e., decreasing TTLs), as first noticed by Govindan and Tangmunarunkit [START_REF] Govindan | Heuristics for internet map discovery[END_REF], Spring et al. [START_REF] Spring | Scriptroute: A public internet measurement facility[END_REF], Moors [START_REF] Moors | Streamlining traceroute by estimating path lengths[END_REF] and Donnet et al. [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF]. However, performing backward probing from non-cooperative traceroute monitors in the context of intra-monitor redundancy has never been evaluated previously. Even if backward probing is simple to understand, it is not clear how efficient it is. This report evaluates the redundancy reduction of backward probing as well as the eventual information lost compared to standard traceroute.

Nevertheless, backward probing is based on the assumption that destinations reply to probes in order to estimate path lengths and the distance of the last hop before the destination. Unfortunately, a large set of destinations (40% in our data set) does not reply to probes, probably due to strongly configured firewalls. In this case, backward probing cannot be performed. In this report, we also propose a way to face non-responding destinations. We further propose an efficient algorithm that can handle both cases, i.e., responding and nonresponding destinations. We evaluate these algorithms in terms of intra-monitor redundancy and quantity of information lost.

The remainder of this report is organized as follows: Sec. 2 introduces the data set used throughout this technical report; Sec. 3 gives a key for reading quantile plots; Sec. 4 evaluates standard traceroute; Sec. 5 presents and evaluates separately our backward probing algorithms; Sec. 6 compares the different algorithms; finally, Sec. 7 concludes this report by summarizing its principal contributions.

Data Set

Our study is based on skitter [START_REF] Huffaker | Topology discovery by active probing[END_REF] data from August 1 st through 3 rd , 2004. This data set was generated by 24 monitors located in the United States, Canada, the United Kingdom, France, Sweden, the Netherlands, Japan, and New Zealand. The monitors share a common destination set of 971,080 IPv4 addresses. Each monitor cycles through the destination set at its own rate, taking typically three days to complete a cycle. For the purpose of our studies, in order to reduce computing time to a manageable level, we worked from a limited destination set of 50,000, randomly chosen from the original set.

Visits to host and router interfaces are the metric by which we evaluate redundancy. We consider an interface to have been visited if its IP address returned by the host or router appears, at least, at one of the hops in a traceroute. Though it would be of interest to calculate the load at the host and router level, rather than at the individual interface level, we make no attempt to disambiguate interfaces in order to obtain router-level information. The alias resolution techniques described by Pansiot and Grad [START_REF] Pansiot | On routes and multicast trees in the internet[END_REF], by Govindan and Tangmunarunkit [START_REF] Govindan | Heuristics for internet map discovery[END_REF], for Mercator, and applied in the iffinder tool from Caida [START_REF] Keys | iffinder," a tool for mapping interfaces to routers[END_REF], would require active probing beyond the skitter data, preferably at the same time that the skitter data is collected. The methods used by Spring et al. [START_REF] Spring | Measuring ISP topologies with Rocketfuel[END_REF], in Rocketfuel, and by Teixeira et al. [START_REF] Teixeira | In search of path diversity in ISP networks[END_REF], apply to routers in the network core, and are untested in stub networks. Despite these limitations, we believe that the load on individual interfaces is a useful measure. As Broido and claffy note [START_REF] Broido | Internet topology: Connectivity of IP graphs[END_REF], "interfaces are individual devices, with their own individual processors, memory, buses, and failure modes. It is reasonable to view them as nodes with their own connections."

How do we account for skitter visits to router and host interfaces? Like many standard traceroute implementations, skitter sends three probe packets for each hop count. An IP address appears thus in a traceroute result if it appears in the replies to, at least, one of the three probes sent (but it may also appear two or three times). For each reply, we account one visit. If none of the three probes are returned, the hop is recorded as non-responding.

Even if an IP address is returned for a given hop count, it might not be valid. Due to the presence of poorly configured routers along traceroute paths, skitter occasionally records anomalies such as private IP addresses that are not globally routable. We account for invalid hops as if they were non-responding hops. The addresses that we consider as invalid are a subset of the special-use IPv4 addresses described in RFC 3330 [START_REF] Iana | Special-use IPv4 addresses[END_REF]. Specifically, we eliminate visits to the private IP address blocks 10.0.0.0/8, 172.16.0.0/12, and 192.168.0.0/16. We also remove the loopback address block 127.0.0.0/8. In our data set, we find 4,435 different special addresses, more precisely 4,434 are private addresses and only one is a loopback address. Special addresses account for approximately 3% of the entire set of addresses seen in this trace. Though there were no visits in the data to the following address blocks, they too would be considered invalid: the "this network" block 0.0.0.0/8, the 6to4 relay any cast address block 192.88.99.0/24, the benchmark testing block 198.18.0.0/15, the multicast address block 224.0.0.0/4, and the reserved address block formerly known as the Class E addresses, 240.0.0.0/4, which includes the lan broadcast address, 255.255.255.255.

Description of the Plots

In this report, we plot interface redundancy distributions. Since these distributions are generally skewed, quantile plots give us a better sense of the data than would plots of the mean and variance. There are several possible ways to calculate quantiles. We calculate them in the manner described by Jain [19, p. 194], which is: rounding to the nearest integer value to obtain the index of the element in question, and using the lower integer if the quantile falls exactly halfway between two integers.

Fig. 1 provides a key to reading the quantile plots found in subsequent sections of this report.

A dot marks the median (the 2 nd quartile, or 50 th percentile). The vertical line below the dot delineates the range from the minimum to the 1 st quartile, and leaves a space from the 1 st to the 2 nd quartile. The space above the dot runs from the 2 nd to the 3 rd quartile, and the line above that extends from the 3 rd quartile to the maximum. Small tick bars to either side of the lines mark some additional percentiles: bars to the left for the 10 th and 90 th , and bars to the right for the 5 th and 95 th .

In the case of highly skewed distributions, or distributions drawn from small amounts of data, the vertical lines or the spaces between them might not appear. For instance, if there are tick marks but no vertical line above the dot, this means that the 3 rd quartile is identical to the maximum value.

In the figures, each quantile plot sits directly above an accompanying bar chart that indicates the quantity of data upon which the quantiles were based. For each hop count, the bar chart displays the number of interfaces at that distance. For these bar charts, a log scale is used on the vertical axis. This allows us to identify quantiles that are based upon very few interfaces (fewer than twenty, for instance), and so for which the values risk being somewhat arbitrary.

Standard Traceroute

Our basis for comparison is the results from the standard forward tracing algorithm implemented in traceroute. All monitors operate from a set of common destinations, D. Each monitor probes forward starting from TTL=1 and increasing the TTL hop by hop towards each of the destinations in D in turn. As it probes, a monitor i updates the set, S i , initially empty, of interfaces that it has visited.

Evaluating redundancy in the standard traceroute was already published in an authors' SIGMETRICS 2005 paper [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF]. For comparison reasons in the next sections of this report, we summarize in this section our redundancy evaluation of standard traceroute. Interested readers might find plots for the 22 other skitter monitors in our technical report [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF].

Looking first at the histograms for interface counts (the lower half of each plot), we find data consistent with distributions typically seen in such cases. If we were to look at a plot on a linear scale (not shown here), we would see that these distributions display the familiar bell-shaped curve typical of internet interface distance distributions [START_REF] Begtasevic | Measurement of the hopcount in the internet[END_REF]. If we concentrate on champagne, we see that it discovers 92,354 unique and valid IP addresses. The interface distances are distributed with a mean at 17 hops corresponding to a peak of 9,135 interfaces that are visited at that distance.

The quantile plots show the nature of the redundancy problem. Looking at how the redundancy varies by distance, we see that the problem is worse the closer one is to the monitor. This is what we expect given the treelike structure of routing from a monitor, but here we see how serious the phenomenon is from a quantitative standpoint. For the first two hops from each monitor, the median redundancy is 150,000. A look at the histograms shows that there are very few interfaces at these distances. Just one interface for arin, and two (2 nd hop) or three (3 rd hop) for champagne. These close to the monitor interfaces are only visited three times, as represented by the presence of the 5 th and 10 th percentile marks (since there are only two data points, the lower values point is represented by the entire lower quarter of values on the plot).

Beyond three hops, the median redundancy drops rapidly. By the eleventh hop, in both cases, the median is below ten. However, the distributions remain highly skewed. Even fifteen hops out, some interfaces experience a redundancy on the order of several hundred visits. With small variations, these patterns are repeated for each of the monitors.

Backward Tracing

As seen and discussed in Sec. 4, the most worrisome feature of redundancy in a standard measurement system is the exceptionally high number of visits to the median interfaces close in to the monitor. Also of concern is the heavy tail of the distribution at more distant hop counts, with a certain number of interfaces consistently receiving a high number of visits. Our approach here is to tackle the first problem head-on, and then to see if the second problem remains.

The large number of visits to nodes close in to a monitor is easily explained by the tree-like or conal structure of the graph generated by traceroutes from a single monitor, as described by Broido and claffy [START_REF] Broido | Internet topology: Connectivity of IP graphs[END_REF]. There are typically only a few interfaces close to a monitor, and these interfaces must therefore be visited by a large portion of the traceroutes. The solution to this problem is simple, at least in principle: these close in interfaces must be skipped most of the time.

Traceroute works forward from source to destination. Its first set of probes goes just one hop, its second set goes two, and so forth. It would seem that the best way to reduce intra-monitor redundancy is to start further out and probes backward, i.e., decreasing TTLs. Govindan and Tangmunarunkit [START_REF] Govindan | Heuristics for internet map discovery[END_REF] do just this in the Mercator system. Using a probing strategy based upon IP address prefixes, Mercator conducts a check before probing the path to a new address that has a prefix P . If paths to an address in P already exist in its database, Mercator starts probing at the highest hop count for a responding router seen on those paths. No results have been published on the performance of this heuristic, though it seems to us an entirely reasonable approach in light of our data.

The Mercator heuristic requires that a guess be made about the relevant prefix length for an address. That guess is based upon the class that the address would have had before the advent of classless inter-domain routing (CIDR) [START_REF] Fuller | Classless inter-domain routing (CIDR): an address assignment and aggregation strategy[END_REF]. In this technical report, we have tested a number of simple heuristics that do not require us to hazard such a guess.

Our algorithms work backwards. As illustrated in Fig. 3, a monitor sends its first probes to the destination, its second to one hop short of the destination, and so forth. Now arises the question of when to stop backward probing. Based on the tree-like structure of routes emanating from a single point (i.e., the traceroute source), we choose a stopping rule based on the set of interfaces previously encountered. A monitor will stop backward probing when an already visited interface is encountered. The only redundancy such a strategy should produce would be on interfaces that are branching points in paths between a monitor and its destinations. A backward probing scheme uses the set, S i , of interfaces that a monitor i has visited. In early probing, S i will have few elements, and so paths should be traced from the destination almost all the way back to the monitor. Later probing should terminate further and further out, as more and more interfaces are added to S i .

There are practical problems with a strategy of back-wards probing. They arise because of inherent flaws with methods for establishing the number of hops from a monitor to a destination. These methods rely upon the sending of a ping packet (or a scout packet, following Moors' terminology [START_REF] Moors | Streamlining traceroute by estimating path lengths[END_REF]), and the examination of the time to live (TTL) value in the IP packet that the destination returns. Various heuristics have been described, by Templeton and Levitt [START_REF] Templeton | Detecting spoofed packets[END_REF], Jin et al. [START_REF] Jin | Hop-count filtering: An effective defense against spoofed DDoS traffic[END_REF], Moors [START_REF] Moors | Streamlining traceroute by estimating path lengths[END_REF] and Beverly [START_REF] Beverly | A robust classifier for passive TCP/IP fingerprinting[END_REF], to guess the original TTL (typically one of a few standard values) based upon the observed value, and thus to guess the hop count from destination to monitor. While these heuristics have been shown to work well, the most serious problem is that they cannot work when the destination does not reply, as is often the case (40.3% in our data). In such a case, a system that takes a backwards probing approach will ideally start from the most distant interface that responds with an ICMP "TTL expired" packet when discarding a hoplimited probe. In practice, this might take some search to locate, adding redundancy. Furthermore, as established by Paxson [START_REF] Paxson | End-to-end routing behavior in the internet[END_REF] based upon data from 1995, and confirmed with data from 2002 by Amini et al. [START_REF] Amini | Issues with inferring internet topological attributes[END_REF], a considerable number of paths in the Internet are asymmetric: most recently almost 70%. This is a less serious problem, however, as the differences in routing often do not translate into considerable differences in hop count. Paxson's work indicated that differences in one or two hops were typical. For the purposes of our simulations we assume that, if a destination does reply to a ping, the system thereby learns the correct number of hops on the forward path.

Pure Backwards

We simulate an algorithm for backwards probing in which the most distant responding interface is assumed to be known a priori. Called pure backward probing, this algorithm is unrealistic because of its assumption. However, its performance sets a benchmark.Against that algorithm, we later compare algorithms that use only information that is actually available to a monitor. Fig. 4 shows redundancy for monitors running the pure backwards algorithm 1 . We notice a significant drop in comparison to the redundancy in straightforward tracerouting shown in Fig. 2. The median drops for the close interfaces, and the distribution tails are significantly shortened overall. However, Figs. 4(a) and 4(b) show still high redundancy for interfaces located one hop from the traceroute source.

We hypothesize that these remanent high redundancies close to the monitors are caused by the existence of firewalls or gateways that either do not permit probes to pass through them, or do not permit replies to return.

1 Plots for others monitors can be found in an appendix at the end of this report. If the destination addresses are invalid, these interfaces could also be default free routers. Under pure backwards probing, a node situated immediately in front of such a device, whatever it might be, will be visited again and again, for each destination that lies beyond, thus resulting in a high visit count for one of its interfaces. Without any further knowledge, the actual cause of such high redundancy under backwards probing remains for us an open question. However, Figs. 4(a) and 4(b) show that maximum redundancies are in the thousands, rather that the hundreds of thousands as before. Furthermore, median values are a little higher than with standard traceroute. The strong drop in redundancy close to the monitor thus comes at the expense of some increased redundancy further out. The overall effect is one of smoothing the load.

There are costs associated with this drop in redundancy. We measure these in terms of the number of interfaces missed, using the set S i of interfaces visited by the standard algorithm as the reference. For the pure backwards algorithm, the numbers missed are relatively small, as shown in Table 7. Table 7 gives also the cost in term of links missed by the pure backwards algorithm.

Interfaces will necessarily be missed in backwards probing when a hard and fast rule is applied that requires probing to stop once an already visited interface is encountered. Any routing change that might have taken place between the monitor and that interface will go unnoticed. A routing system that adopts a backwards probing algorithm should also adopt a strategy for periodically reprobing certain paths, so as not to miss such changes entirely. So long as the portion of interfaces missed is small, we believe that the development of such a reprobing strategy can be left to future work.

Ordinary Backwards

The ordinary backwards algorithm works in much the same way as perfect backwards, but it is a more realistic algorithm. Just as with pure backwards, when a destination responds, the monitor starts probing backwards from the destination until an already visited interface is met. However, when a destination doesn't reply, the monitor, since it cannot know a priori the most distant responding interface along the path, gives up probing for this particular destination altogether. This is the first of two building blocks that will be used by the algorithm presented in Sec. 5.4, and is not intended to be used in isolation.

Approximately 40% the traceroutes in our data set terminate in a non-responding destination. What does this mean in terms of interfaces that are missed? Table 2 shows the costs of not probing these paths combined with the early stopping that is in any case associated with backwards probing. What is remarkable to note is that, compared to perfect backwards probing, ordinary backwards probing only misses an additional 16% of interfaces.

Fig. 5 shows trends very similar to those observed with perfect backwards probing, but some high values are no longer present.

Searching

If we are to use ordinary backwards probing as one element of a larger probing strategy, we need a second element to handle destinations that do not respond. Since the last responding interface on a path to such a destination cannot be known a priori, the monitor must search Our algorithm, labeled searching, now sends its initial probe with a TTL value h. If it receives a response, it continues to probe forwards, to TTLs h + 1, h + 2, and so forth. When the farthest responding interface is found, probing resumes from TTL h -1, and probes backwards, to TTLs h -2, h -3, and so back. If, at any point, a monitor i visits an interface that is in its set S i of interfaces already viewed, probing for that destination stops. The working of the searching algorithm is illustrated in Fig. 6, where h = 3 and R 5 being the last responding interface.

If the algorithm is supposed to start probing from a midpoint h in the network, we have to decide which value give to h. Doubletree [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF] thors of this report, is a cooperative and efficient algorithm for large-scale topology discovery. Each Doubletree monitor starts probing at some hop h from itself, performing forwards probing from h and backwards probing from h -1. The value h is fixed by each monitor according to its probability p of hitting a destination with the very first probe sent. This choice is driven by the risk of probing looking like a distributed denial-ofservice (DDoS) attack. Indeed, when probes sent by multiples monitors converge towards a given destination, the probe traffic might appear, for an end-host, as a DDoS attack. Doubletree aims to minimize this risk and, therefore, each monitor chooses an appropriate h value.

In this report, we are not interested in large-scale distributed probing, i.e., from a large set of monitors that cooperate when probing towards a large set of destinations. We consider that each monitor works in isolation of others. It does not make sense to choose the h value like Doubletree does. Fig. 7 shows the incomplete paths distribution, i.e., the distance distribution of the last responding hop when a traceroute does not terminate by hitting the destination. Such a case occurs in approximately 40% of the traceroutes in our dataset. We propose that each monitor tunes its h value with the mean hop count for its incomplete traceroutes. A monitor can easily evaluates its own h value by performing a small number of standard traceroutes.

In the special case where there is no response at distance h, the distance is halved, and halved again until there is a reply, and probing continues forwards and backwards from that point.

Our results in Fig. 8 indicate that low redundancy can be achieved. We tested the heuristic algorithm using only those traceroutes for which the destination does not respond.

However, we notice that close to the monitor, in the fashion of the pure backwards algorithm (see Fig. 4), the redundancy is still high. We believe that this is caused by very short paths for which the last responding interface is close to the monitor. For those paths, there is a high probability that sending the first probe at h hops to the monitor will corresponds a non-response. The h value will be divided by two, again and again, until reaching a responding interface that will be located close to the monitor, increasing therefore the redundancy of such interfaces.

Searching Ordinary Backwards

In this section, we study a comprehensive strategy for reducing probing redundancy. We employ ordinary backwards probing, along with the heuristic algorithm for cases in which the destination does not respond. This algorithm is called searching ordinary backwards.

Fig. 9 shows redundancy reduction similar to that obtained with the other algorithms examined so far.

Table 3 shows the interfaces and links missed when probing with the searching ordinary backwards algorithm. Table 3 indicates that the numbers of missed interfaces are a bit smaller (this is specially true for arin) than with the supposedly pure backwards algorithm, a surprising fact which will be explained in the next section. 4 giving the mean over the 24 monitors.

Algorithms Comparison

Our goal is to avoid both redundancy and missed interfaces as much as possible, however there is a tradeoff between the two. Extremes are represented by the standard traceroute, which by definition misses no interfaces, but has high average redundancy, and by the heuristic algorithm which, having been applied to just those traceroutes for which the destination did not respond, necessarily misses a large number of interfaces.

We see that the ordinary backwards provides the lowest redundancy but, as it is applied on only respond-

Conclusion

This technical report addresses the area of efficient probing in the context of traceroute monitors working in isolation from each others. Prior work stated that standard traceroutes are particularly inefficient by repeatedly reprobing the same interfaces close to the monitor. The solution to this redundancy problem is, at least in principle, simple: those interfaces close to the monitor must be skipped most of the time. It seems that the best way to achieve this solution is to probe backwards from the destinations and stop when encountering a previously seen interface.

In this report, we perform the first careful study of the efficiency of backwards probing, by evaluating it in terms of redundancy reduction and information lost.

Nevertheless, we state that a pure backwards probing algorithm is unrealistic as it is based on the assumption that destinations reply to probes. We therefore propose an algorithm that searches for the last responding interface. The key idea of this algorithm is to start probing at some hop h from the monitor, probe forwards from h until the last responding interface and, then, probe backwards from h -1 until reaching an already discovered interface.

We finally propose a realistic algorithm that can handle both cases, i.e., responding and non-responding des-

Figure 1 :

 1 Figure 1: Quantiles key

Figure 2 :

 2 Figure 2: Redundancy when probing with the pure forwards algorithm

Fig. 2 Figure 3 :

 23 Figure 3: Pure backwards algorithm

Figure 4 :

 4 Figure 4: Redundancy when probing with the pure backwards algorithm

Figure 5 :

 5 Figure 5: Redundancy when probing with the ordinary backwards algorithm

Figure 6 :Figure 7 :

 67 Figure 6: Searching algorithm with h = 3

Figure 8 :

 8 Figure 8: Redundancy when probing with the searching algorithm

Fig. 10

 10 Fig.10shows the trade-offs between redundancy and missed address interfaces. Redundancy is here repre-

Figure 9 :

 9 Figure 9: Redundancy when probing with the searching ordinary backwards algorithm

Figure 10 :

 10 Figure 10: Algorithms comparison

Figure 11 :

 11 Figure 11: Redundancy when probing with the pure backwards algorithm -1

Figure 12 :

 12 Figure 12: Redundancy when probing with the pure backwards algorithm -2

Figure 13 :

 13 Figure 13: Redundancy when probing with the pure backwards algorithm -3

Figure 14 :

 14 Figure 14: Redundancy when probing with the pure backwards algorithm -4

Figure 15 :

 15 Figure 15: Redundancy when probing with the ordinary backwards algorithm -1

Figure 16 :

 16 Figure 16: Redundancy when probing with the ordinary backwards algorithm -2

Figure 17 :

 17 Figure 17: Redundancy when probing with the ordinary backwards algorithm -3

Figure 18 :

 18 Figure 18: Redundancy when probing with the ordinary backwards algorithm -4

Figure 19 :

 19 Figure 19: Redundancy when probing with the searching algorithm -1

Figure 20 :

 20 Figure 20: Redundancy when probing with the searching algorithm -2

Figure 21 :

 21 Figure 21: Redundancy when probing with the searching algorithm -3

Figure 22 : 4 CFigure 23 :Figure 24 :Figure 25 :Figure 26 : 4 D

 224232425264 Figure 22: Redundancy when probing with the searching algorithm -4

Figure 27 :Figure 28 :

 2728 Figure 27: Redundancy when probing with the SearchingOB ordinary backwards algorithm -1

Figure 29 :

 29 Figure 29: Redundancy when probing with the SearchingOB ordinary backwards algorithm -3

Figure 30 :

 30 Figure 30: Redundancy when probing with the SearchingOB ordinary backwards algorithm

Figure 34 :

 34 Figure 31: Algorithms comparison -1

Table 1 :

 1 , proposed by the au-Interfaces missed by the pure backwards algorithm

	Monitor		Interfaces			Links
		total	discovered % missed	total	discovered % missed
	arin	92,381	88,204	4.52%	101,850	92,602	9.09%
	champagne 92,354	88,012	4.70%	101,652	92,331	9.17%
	Monitor		Interfaces			Links
		total	discovered % missed	total	discovered % missed
	arin	92,381	73,529	20.40%	101,850	75,163	27.21%
	champagne 92,354	73,410	20.51%	101,652	74,987	27.24%

Table 2 :

 2 Interfaces missed by the ordinary backwards algorithm

	Probing Sequence	Monitor	R1	R2	R3	R4	R5 Destination

Table 3 :

 3 Interfaces missed by the searching ordinary backwards algorithm

	Monitor		Interfaces			Links
			total	discovered % missed	total	discovered % missed
	arin	92,381	90,156	2.40%	101,850	94,149	7.57%
	champagne 92,354	87,946	4.77%	101,652	91,123	10.36%
	Algorithms	Mean visit Prop. missed
	standard	25.08		0
	heuristic	9.16		0.74
	search. ord. bwd	6.21		0.03
	pure bwd	5.58		0.04
	ordinary bwd	4		0.2
	Table 4: Algorithms comparison -mean
	ing traceroutes, it misses a lot of interfaces. The most
	interesting comparison is between the pure backwards
	algorithm and searching ordinary backwards. Both are
	based upon the full set of traceroutes, and so are strictly
	comparable. The searching ordinary backwards algo-

rithm manages to outperform the pure backwards algorithm by paying a slight price in terms of increased redundancy (in the case of arin).

Table 5 :

 5 Interfaces missed by the pure backwards algorithm

	A.2 Losses
	Monitor		Interfaces			Links
		total	discovered % missed	total	discovered % missed
	apan-jp	86,763	82,659	0.04730% 96,908	88,562	0.08612%
	b-root	92,754	88,565	0.04516% 103,595	94,379	0.08896%
	cam	90,796	86,799	0.04402% 101,068	92,546	0.08431%
	cdg-rssac 90,962	87,015	0.04339% 100,258	92,114	0.08123%
	d-root	91,136	87,228	0.04288% 100,821	92,757	0.07998%
	e-root	90,952	86,592	0.04793% 102,749	93,093	0.09397%
	f-root	92,123	88,136	0.04327% 101,956	93,058	0.08727%
	g-root	91,547	87,108	0.04848% 103,872	93,742	0.09752%
	h-root	91,825	87,725	0.04465% 102,948	94,106	0.08588%
	i-root	91,942	87,827	0.04475% 104,017	94,657	0.08998%
	iad	92,175	88,092	0.04429% 102,324	93,046	0.09067%
	ihug	94,719	89,715	0.05282% 107,979	96,292	0.10823%
	k-peer	91,851	87,730	0.04486% 103,672	94,353	0.08988%
	k-root	91,726	87,806	0.04273% 101,974	93,858	0.07958%
	lhr	92,079	88,215	0.04196% 101,188	92,837	0.08252%
	m-root	92,347	88,078	0.04622% 101,321	92,247	0.08955%
	mwest	91,525	87,388	0.04520% 103,074	93,881	0.08918%
	nrt	92,021	87,897	0.04481% 101,286	92,276	0.08895%
	riesling	90,913	86,766	0.04561% 100,426	91,334	0.09053%
	sjc	91,459	87,433	0.04401% 101,665	92,695	0.08823%
	uoregon	90,585	86,624	0.04372% 100,851	92,360	0.08419%
	yto	91,200	87,199	0.04387% 102,625	93,766	0.08632%

Table 6 :

 6 Interfaces missed by the ordinary backwards algorithm

Table 7 :

 7 Interfaces missed by the SearchingOB ordinary backwards algorithm

	D.2 Losses
	Monitor		Interfaces			Links
		total discovered % missed	total	discovered % missed
	apan-jp	86763	83,674	0.03560% 96,908	88,147	0.09040%
	b-root	92754	89,540	0.03465% 103,595	94,469	0.08809%
	cam	90796	88,278	0.02773% 101,068	93,822	0.07169%
	cdg-rssac 90962	87,958	0.03302% 100,258	92,844	0.07394%
	d-root	91136	89,167	0.02160% 100,821	94,634	0.06136%
	e-root	90952	88,831	0.02332% 102,749	95,018	0.07524%
	f-root	92123	90,926	0.01299% 101,956	95,770	0.06067%
	g-root	91547	89,480	0.02257% 103,872	95,335	0.08218%
	h-root	91825	88,914	0.03170% 102,948	94,040	0.08652%
	i-root	91942	88,158	0.04115% 104,017	94,484	0.09164%
	iad	92175	90,374	0.01953% 102,324	95,031	0.07127%
	ihug	94719	91,882	0.02995% 107,979	98,129	0.09122%
	k-peer	91851	89,431	0.02634% 103,672	96,780	0.06647%
	k-root	91726	89,715	0.02192% 101,974	95,884	0.05972%
	lhr	92079	89,877	0.02391% 101,188	94,754	0.06358%
	m-root	92347	89,448	0.03139% 101,321	93,277	0.07939%
	mwest	91525	89,953	0.01717% 103,074	96,561	0.06318%
	nrt	92021	89,825	0.02386% 101,286	93,955	0.07237%
	riesling	90913	87,681	0.03555% 100,426	91,518	0.08870%
	sjc	91459	89,299	0.02361% 101,665	93,713	0.07821%
	uoregon	90585	87,990	0.02864% 100,851	92,971	0.07813%
	yto	91200	89,541	0.01819% 102,625	95,834	0.066173%


Benoit Donnet
email: benoit.donnet@lip6.fr

Bradley Huffaker
email: bhuffake@caida.org

Timur Friedman
email: timur.friedman@lip6.fr

Implementation and Deployment of a Distributed Network Topology Discovery Algorithm

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 denialof-service (DDoS) attack as the probes converge from a set of sources towards a given destination. In prior work, authors of this report 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 report presents our open-source and freely downloadable implementation of Doubletree in a tool we call traceroute@home. We describe the deployment and validation of traceroute@home on the PlanetLab testbed and we report on the lessons learned from this experience. We discuss how traceroute@home can be developed further and discuss ideas for future improvements.

I. INTRODUCTION

For some time, the problem of internet topology discovery has drawn the attention of the network measurement community. One can see the internet topology at three different levels. The first one, the IP interface level, considers internet protocol (IP) interfaces of routers and end systems. Usually, this topology is obtained by using data collected with the probing tool traceroute [START_REF] Jacobsen | traceroute," man page[END_REF]. Traceroute is a networking tool that allows one to discover IP interfaces along the path that data packets take to go from a source machine or monitor to a destination machine. The second level, the router level, is an aggregation of the IP level. It can be obtained by using a technique called alias resolution [START_REF] Govindan | Heuristics for internet map discovery[END_REF], [START_REF] Spring | Measuring ISP topologies with Rocketfuel[END_REF], [START_REF] Pansiot | On routes and multicast trees in the internet[END_REF], [START_REF] Teixeira | In search of path diversity in ISP networks[END_REF]. The idea is to summarize all the IP addresses of a router into a single identifier. Finally, the AS level provides information about the connectivity of autonomous systems (ASes). An AS is a set of routers that are under the same administrative control. The ASes are interconnected in order to allow IP packets to transit from one network to another, so providing global connectivity. The connectivity information might be inferred from BGP tables [START_REF]Route views, University of Oregon Route Views project[END_REF], BGP being the routing protocol used between ASes. Note that the special problem of determining the topology AS1 AS2 AS3 Fig. 1. The different levels of topology within a single AS is a separate area of inquiry. It is not, strictly speaking, internet topology discovery, and it is considerably helped by the privileged access available to the administrator of an AS. Fig. 1 illustrates the three levels of the internet topology. Black dots represents router interfaces, blank shapes stand for routers and shaded areas for ASes. The plain and dotted lines correspond to links. The IP interface level is illustrated by the links between routers. The router level is obtained when all interfaces of a router are grouped in a single identifier. Finally, the AS level is obtained when we look only at ASes and the links between them.

This report focuses on the IP interface level. More specially, it describes the implementation and deployment story of a topology discovery algorithm, Doubletree [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF], that reduces load on the network, i.e., router IP interfaces and end-hosts, while discovering nearly the same set of nodes and links as standard approaches based on traceroute. Doubletree was proposed by authors of this report.

Today's most extensive tracing system at the IP interface level, skitter [START_REF] Huffaker | Topology discovery by active probing[END_REF], uses 24 monitors, each targeting on the order of one million destinations. Authors of this report are responsible for skitter. In the fashion of skitter, scamper [START_REF]IPv6 scamper[END_REF] makes use of several monitors to traceroute IPv6 networks. Other well known systems, such as RIPE NCC TTM [START_REF] Georgatos | Providing active measurements as a regular service for ISPs[END_REF] and NLANR AMP [START_REF] Mcgregor | The NLANR network analysis infrastructure[END_REF], each employ a larger set of monitors, on the order of one-to two-hundred, but they avoid probing outside their own network. However, recent work has indicated the need to increase the number of traceroute sources in order to obtain a more complete topology measurement [START_REF] Lakhina | Sampling biases in IP topology measurements[END_REF], [START_REF] Clauset | Traceroute sampling makes random graphs appear to have power law degree distributions[END_REF]. Indeed, it has been shown that reliance upon a relatively small number of monitors to generate a graph of the internet can introduce unwanted biases.

One way of rapidly creating a large distributed monitor infrastructure would be to deploy traceroute monitors in an easily downloadable and readily usable piece of software, such as a screensaver. This was first proposed by Jörg Nonnenmacher, as reported by Cheswick et al. [START_REF] Cheswick | Mapping and visualizing the internet[END_REF]. Such a suggestion is in keeping with the spirit of of that have arisen in the past few years. The most famous one is probably SETI@home [START_REF] Anderson | SETI@home: An experiment in public-resource computing[END_REF]. SETI@home's screensaver downloads and analyzes radio-telescope data. Others similar projects are Folding@home [START_REF] Larson | FOLDING@home and GENOME@home: Using distributed computing to tackle previously intractable problems in computational biology[END_REF], a computation application that studies protein folding, and, distributed.net [17] a general-purpose distributed computing project. The first publicly downloadable distributed route tracing tool is DIMES [START_REF] Shavitt | DIMES: Let the internet measure itself[END_REF], released as a daemon in September 2004. At the time of writing this report, DIMES counts more than 6,000 agents scattered over five continents.

However, building such a large structure leads to potential scaling issues: the quantity of probes launched might consume undue network resources and the probes sent from many vantage points might appear as a distributed denial-of-service (DDoS) attack to end-hosts. These problems were quantified in our prior work [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF]. There are two ways to avoid these problems: the first one is to stay small, as skitter does for instance, but this solution is opposed to the basic idea of scaling up the number of tracing monitors. The second is to trace slowly, as does DIMES. In this case, the problem is that the resulting network snapshot may be blurred bye the routing changes that take place over the course of a probing interval.

The Doubletree algorithm [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF] is a first attempt to perform large-scale topology discovery efficiently and in a network friendly manner. Doubletree acts to avoid retracing the same routes in the internet by taking advantage of the tree-like structure of routes fanning out from a source or converging on a destination. The key to Doubletree is that monitors share information regarding the paths that they have explored. If one monitor has already probed a given path to a destination then another monitor should avoid that path. Probing in this manner can significantly reduce load on routers and destinations while maintaining high node and link coverage [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF]. By avoiding redundancy, not only is Doubletree able to reduce the load on the network but it also allows one to probe the network more frequently. This makes it possible to better capture network dynamicity (routing changes, load balancing) compared to standard approaches based on traceroute.

This report goes beyond earlier theory and simulation to propose a Doubletree implementation written in Java [START_REF]Java Sun Microsystems[END_REF]. We call this prototype traceroute@home. traceroute@home is certainly not the first tracerouting tool developed. However, it differs from standard approaches, such as skitter, due to its distributed aspect and its scaling resistance thanks to Doubletree. traceroute@home is easily tunable and extensible for further developments. traceroute@home is completely opensource and freely downloadable [START_REF] Donnet | traceroute@home 1.0[END_REF].

To validate traceroute@home, we deployed it on the Plan-etLab [START_REF]PlanetLab project[END_REF] testbed. We installed traceroute@home on ten PlanetLab nodes and probed the network, using 200 other In this report, we describe the traceroute@home system. We evaluate the performance of our prototype, point out its weaknesses and the problems encountered in its deployment. We discuss directions for future development of our tool and the opportunity for creating an infrastructure entirely dedicated to network measurement.

The remainder of this report is organized as follows: Sec. II explains how traceroute works; Sec. III describes the Doubletree algorithm and some of its extensions; Sec. IV describes traceroute@home; in Sec. V, we discuss its on PlanetLab nodes; Sec. VI introduces directions for future extensions; finally, Sec. VII summarizes the principal contributions of this report.

II. TRACEROUTE

Traceroute is a networking tool that allows one to discover the path a data packet takes to go from a machine S (the source or the monitor) to a machine D (the destination).

Fig. 2 illustrates how traceroute works. S is the source of the traceroute, D is the destination and the Ris are the routers along the path. S sends multiple UDP probes, UDP being the User Datagram Protocol which is a connectionless transport protocol, into the network with increasing time-to-live (TTL) values, the TTL being a field in the IP header indicating how long a packet can circulate in the network. Each time a packet enters a router, the router decrements the TTL. When the TTL value is one, the router determines that the packet has consumed sufficient resources in the network, drops it, and informs the source of the packet by sending back an ICMP time exceeded message (ICMP TE in Fig. 2). ICMP, Internet Control Message Protocol, is a protocol for managing errors related to networked machines. By looking at the IP source address of the ICMP message, the monitor can learn the IP address of the router at which the probe packet stopped.

When, finally, a probe reaches the destination, the destination is supposed to reply with an ICMP destination unreachable message (ICMP DU in Fig. 2).

Unfortunately, the traceroute behavior explained above is the ideal case. A router along the path might not reply to probes because the ICMP protocol is not activated, or the router is overloaded. In order to avoid waiting an infinite time for the ICMP reply, the traceroute monitor actives a timer when it launches the UDP probe. If the timer expires and no reply was received, then, for that TTL, the machine is considered as non-responding.

However, a particular problem occurs when it is the destination that does not reply to probes because, for instance, of a restrictive firewall. In this case, the destination will be recorded as non responding but it is impossible to know that it was reached. In order to avoid inferring a boundless path, an upper bound on the number of successive non-responding machines is used. For instance, in skitter and in our application, this upper bound is set to five.

Standard traceroute, as just described, is based on UDP probes. However, two variants exist. The behavior of the traceroute for the intermediate routers is the same as standard traceroute. The difference comes with the destination. The first variant is based on ICMP. Instead of launching UDP probes, the source sends ICMP Echo Request messages. The destination is supposed to reply with an ICMP Echo Reply. The second sends packets using the Transport Control Protocol (TCP) which is a connection-oriented transport protocol. The TCP traceroute aims to bypass most common firewall filters by sending TCP SYN packets. It assumes that firewalls will permit inbound TCP packets to specific ports listening for incoming connections. III. DOUBLETREE Doubletree [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF] is the key component of a coordinated probing system that significantly reduces load on routers and end-hosts while discovering nearly the same set of nodes and links as standard approaches based on traceroute. It takes advantage of the tree-like structures of routes in the context of probing. Routes leading out from a monitor towards multiple destinations form a tree-like structure rooted at the monitor (see Fig. 3(a)). Similarly, routes converging towards a destination from multiple monitors form a tree-like structure, but rooted at the destination (see Fig. 3(b)). A monitor probes hop by hop so long as it encounters previously unknown interfaces. However, once it encounters a known interface, it stops, assuming that it has touched a tree and the rest of the path to the root is also known. Using these trees suggests two different probing schemes: backwards (monitor-rooted tree) and forwards (destination-rooted tree).

For both backwards and forwards probing, Doubletree uses stop sets. The one for backwards probing, called the local stop set, consists of all interfaces already seen by that monitor. Forwards probing uses the global stop set of (interface, destination) pairs accumulated from all monitors. A pair enters the stop set if a monitor received a packet from the interface in reply to a probe sent towards the destination address.

A monitor that implements Doubletree starts probing for a destination at some number of hops h from itself. It will probe forwards at h + 1, h + 2, etc., adding to the global stop set at each hop, until it encounters either the destination or a member of the global stop set. It will then probe backwards at h -1, h -2, etc., adding to both the local and global stop sets at each hop, until it either has reached a distance of one hop or it encounters a member of the local stop set. It then proceeds to probe for the next destination. When it has completed probing for all destinations, the global stop set is communicated to the next monitor. Doubletree has one tunable parameter. The choice of initial probing distance h is crucial. Too close, and duplication of effort will approach the high levels seen by classic forwards probing techniques [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF]Sec. 2]. Too far, and there will be high risk of traffic looking like a DDoS attack for destinations. The choice must be guided primarily by this latter consideration to avoid having probing look like a DDoS attack.

While Doubletree largely limits redundancy on destinations once hop-by-hop probing is underway, its global stop set cannot prevent the initial probe from reaching a destination if h is set too high. Therefore, each monitor sets its own value for h in terms of the probability p that a probe sent h hops towards a randomly selected destination will actually hit that destination. Fig. III shows the cumulative mass function for this probability for skitter monitor apan-jp. If one considers as reasonable a 0.2 probability of hitting a responding destination on the first probe, it must chose h ≤ 12.

Simulation results [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF]Sec. 3.2] show for a range of p values that, compared to classic probing, Doubletree is able to reduce measurement load by approximately 70% while maintaining interface and link coverage above 90%.

However, one possible obstacle to successful deployment of Doubletree concerns the communication overhead from sharing the global stop set among monitors. Tracing from 24 monitors, i.e., the same quantity of probing monitors as skitter, to a relatively small set of just 50,000 destinations with p = 0.05 produces a set of 2.7 million (interface, destination) pairs. As pairs of IPv4 addresses are 64 bits long, an uncompressed stop set based on these parameters requires 20.6 MB.

A way to reduce this communication overhead is to use Bloom filters [START_REF] Donnet | Improved algorithms for network topology discovery[END_REF] to implement the global stop set. A Bloom filter [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF] summarizes information concerning a set in a bit vector that can then be tested for set membership. An empty Bloom filter is a vector of all zeroes. A key is registered in the filter by hashing it to a position in the vector and setting the bit at that position to one. Multiple hash functions may be used, setting several bits to one. Membership of a key in the filter is tested by checking if all hash positions are set to one. A Bloom filter will never falsely return a negative result for set membership. It might, however, return a false positive. For a given number of keys, the larger the Bloom filter, the less likely is a false positive. The number of hash functions also plays a role.

In prior work [START_REF] Donnet | Improved algorithms for network topology discovery[END_REF], we have shown that, when p = 0.05, using a bit vector of size 10 7 and five hash functions allows nearly the same coverage level as a list implementation of the global stop set while slightly reducing the redundancy on both destinations and internal interfaces and yielding a compression factor of 17.3.

Donnet and Friedman, co-authors of this report, also proposed an enhancement to the forwards stopping rule based on Classless Inter-Domain Routing (CIDR) address prefixes [START_REF] Donnet | Topology discovery using an address prefix based stopping rule[END_REF]. The idea is to aggregate the destinations set by recording the CIDR address prefixes of destinations rather than the full IP address. This allows one to reduce the amount of communication required by Doubletree. Instead of sharing a set of (interface, destination) pairs, monitors will share a set of (interface, prefix destination) pairs. The shortest the prefix, the more destinations can be represented by a single entry, but also the more likely the entry will generate false positives. With this simple mechanism, load on destinations can be further reduced while maintaining the coverage accuracy around 90%. When combined with a Bloom filter, one further reduces the global stop set size, providing a compression factor of 57.1.

IV. TRACEROUTE@HOME IMPLEMENTATION

This section describes the traceroute@home implementation. Sec. IV-A presents our design choices. Sec. IV-B introduces the macroscopic functioning of the cooperative system that makes use of the Doubletree algorithm. Sec. IV-C takes a microscopic look at traceroute@home by explaining the behavior of a monitor and each module composing it. Sec. IV-D discusses the general messages framework.

A. Design Choices

We implemented traceroute@home in Java [START_REF]Java Sun Microsystems[END_REF]. We choose Java as the development language because of two reasons: the large quantity of available packages and the possibility of abstracting ourselves from technical details. As a consequence, the development time was strongly reduced. Unfortunately, Sun does not provide any package for accessing packet headers and handling raw sockets, which is necessary to implement traceroute. Instead of developing our own raw sockets library, we used the open-source JSocket Wrench library [START_REF]Jsocket wrench R04[END_REF]. We modified the JSocket Wrench library in order to support multithreading. Our modifications are freely available [START_REF] Donnet | traceroute@home 1.0[END_REF].

We aimed for the design of traceroute@home to be easily extended in the future by ourselves but also by the networking community. For instance, concerning the messages exchanged by monitors, we define a general framework for messages, making creation and handling of new messages easier. In addition to that, traceroute@home is readily tunable due to a configuration file that is loaded by the application at its starting. Our implementation is freely available [START_REF] Donnet | traceroute@home 1.0[END_REF].

We designed our application by considering two levels: the microscopic level and the macroscopic level.

From a macroscopic point of view, i.e., all the monitors together, the monitors are organized in a ring, adopting a round robin process. At a given time, each monitor focuses on its own part of the destination list. When it finishes probing its part, it sends information to the next monitor and waits for data from the previous one, if it was not yet received. Sec. IV-B explains this macroscopic aspect of traceroute@home.

From a microscopic point of view of our implementation, i.e., a single monitor, a monitor is composed of several modules that interact with each other. Our implementation is thread-safe, as a monitor is able to send several probes at the same time. Further, topological information collected by a monitor is regularly saved to XML files. Sec. IV-C explains this microscopic level of traceroute@home.

B. System Overview

The simulations conducted in prior work [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF] were based on a simple probing system: each monitor in turn covers the destination list, adds to the global stop set the (interface, destination) pairs that it encounters, and passes the set to the subsequent monitor. This simple scenario is not suitable in practice: it is too slow, as an iterative approach allows only one monitor to probe the network at a given time. We want all the monitors probing in Fig. 5. Doubletree with sliding windows parallel. However, how would one manage the global stop set if it were being updated by all the monitors at the same time?

An easy way to parallelize is to deploy several sliding windows that slide along the different portions of the destination list. At a given time, a given monitor focuses on its own window, as shown in Fig. 5. There is no collision between monitors, in the sense that each one is filling in its own part of the global stop set. The entire system counts m different sliding windows, where m is the number of Doubletree monitors. If there are n destinations, each window is of size w = n/m. This is an upper-bound on the window size as the concept still applies if they are smaller.

A sliding window mechanism requires us to decide on a step size by which to advance the window. We could use a step size of a single destination. After probing that destination, a Doubletree monitor sends a small set of pairs corresponding to that destination to the next monitor, as its contribution to the global stop set. It advances its window past this destination, and proceeds to the next destination. Clearly, though, a step size of one will be costly in terms of communication. Packet headers (see Sec. IV-D for details about packet format) will not be amortized over a large payload, and the payload itself, consisting of a small set, will not be as susceptible to compression as a larger set would be.

On the other hand, a step size equal to the size of the window itself poses other risks. Suppose a monitor has completed probing each destination in its window, and has sent the resulting subset of the global stop set on to the following monitor. It then might be in a situation where it must wait for the prior monitor to terminate its window before it can do any further useful work.

A compromise must be reached, between lowering communications costs and continuously supplying each monitor with useful work. This implies a step size somewhere between 1 and w. For our implementation of Doubletree, we let the user decide the step size. This is a part of the XML configuration file that each Doubletree monitor loads at its start-up (see Sec. IV-C). Future work might reveal information about how to tune the step size of a monitor.

C. Inside a traceroute@home Monitor

Fig. 6 shows the different modules composing a traceroute@home monitor and the way they interact with each other (the arrows) and with their environment, i.e., hard disk or network (circles).

First, a traceroute@home monitor loads an XML file (config.xml) that contains configuration information, such as the number of sliding windows and the name (or IP address) of the next monitor in the round robin process. This XML file must strictly follow a DTD (Document Type Definition). 1In the current version of the application, the XML file must be present on the machine running the software. In the following versions (See Sec. VI), we can imagine that a traceroute@home monitor will upload this file from a remote server. Note also that the destination list and sliding window information must also be present on the machine. We can envisage that these will also be remotely available in the future.

This configuration file is processed by the Agent. The Agent is the heart of a traceroute@home monitor as it first creates all other modules, manages them and, finally, allows the various components to interact with each other.

The Agent creates the StopSet module that implements the stop set data structure [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF]. Our stop set implementation is multithread safe. Two types of implementations are proposed: list and Bloom filter. The list is the basic implementation and can be used for the local stop set as well as the global stop set. The Bloom filter implementation [START_REF] Donnet | Improved algorithms for network topology discovery[END_REF] may only be used for the global stop set. The hash functions needed by the Bloom filter are emulated with the SHA-1 algorithm [START_REF] Eastlake | US secure hash algorithm 1 (SHA-1)[END_REF]. Depending on the XML configuration file, the global stop set may be compressed or not before being sent to the next monitor. Note that, for consistency reasons, each monitor in the system must use the same implementation for the global stop set. Doubletree is a cooperative algorithm. The different monitors have to share their global stop set. They thus exchange messages. The purpose of the Message component is therefore to build, parse and store messages (before their handling by the Agent) sent and received by a monitor. We explain in detail the Message component by describing our general message framework in Sec. IV-D.

A traceroute@home monitor, through the Message module, is able to handle messages. To send and receive them, it makes use of the Communication component that allows a monitor to interact with other monitors. It sends messages to a given monitor when the Agent orders it and listens to potential connections for incoming messages. Incoming messages are parsed and stored by the Message module before their handling by the Agent. In order to make this module as efficient as Forward Backward Fig. 6. A traceroute@home monitor's modules possible, it was implemented using a selector. A selector provides the ability to do readiness selection, which enables multiplexed I/O operations. A selector makes it possible for a single thread to manage many I/O channels simultaneously. This corresponds to the select() operation in C.

The Probe module builds probes (UDP or ICMP), assigns them a TTL value, sends them into the network and waits for eventual ICMP replies. The Probe module is created by a client that wants to probe the network. An example of such a client is the Agent. The client may require multithreading in its network exploration. Therefore, the Probe module allows one to send multiple probes at the same time. Another unique thread listens to incoming ICMP replies messages and dispatches them to the client. The client is in charge of the matching between a probe sent and the eventual ICMP reply. This matching is possible because the ICMP reply (destination unreachable or time exceeded) contains the IP header and the 8 first bytes of the original datagram (refer to Sec. II for details about how traceroute works). a unique source port number in the UDP header of each outgoing probe allows the returning ICMP replies to be identified. Moors discusses the reasons for varying the source port of UDP datagram instead of the destination port [27, Sec. III].

The PLEstimator (for "Path Length Estimator") module is in charge of discovering path lengths for the current sliding window. It sends to destinations UDP probes with a TTL of 64 and a high destination port. If a destination replies with a Destination Unreachable ICMP message, the PLEstimator is able to know the distance by looking at the TTL field contained in the IP header copied in the ICMP message payload. A simple subtraction allows one to know the path length. With all the path length information received, the PLEstimator builds the path length CDF, as shown in Fig. III. As suggested in prior work [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF], the PLEstimator will use, by default, a p value of 0.05 in order to determine the h value that must be used for the current sliding window. The PLEstimator is a client of the Probe module.

The Doubletree module defines an interface describing the general behavior of a probing scheme. This interface is implemented in two ways, such that it defines the two probing scheme behaviors, i.e., backwards and forwards, proposed by prior work [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF]. However, the Doubletree module is not a Probe module client. In this case, multithreading is managed by the Agent. The Doubletree module is only used to decide, according to a probe reply (which might be empty if the router did not reply to probes), if a stopping condition is reached. Four stopping conditions are defined: i) normal (the destination, forwards probing, or the first hop, backwards probing, is reached), ii) stop set, iii) loop and iv) gap. A gap occurs when the monitor encounters five successive nonresponding interfaces. The Doubletree module is also in charge of deciding the next TTL value.

When a traceroute@home monitor has finished probing a part of the sliding window corresponding to the step size, it sends the corresponding stop set to the subsequent monitor but it also saves the topological information that it has gathered. Maintaining information about the topology discovered and saving this information on the hard disk is the Data module's job. The topological information is transformed into an XML file according to a DTD. 2 The XML format was chosen in order to facilitate eventual later data migration into a more complex data type. An XML format also makes the data handling easier. For each destination probed, we currently record the following information: the source (i.e., the IP address of the monitor), the destination, a timestamp, the backwards probing stopping reason as described above, the backwards probing stopping distance, the forwards probing stopping reason, the forwards probing stopping distance, and the path discovered. The path is composed of several hops, a hop being composed of the TTL value and three IP addresses or "*", corresponding to a non-responding interface. If the IP address corresponds to a responding router, then the round-trip time (RTT) for the probe and the response is added.

D. Message Exchange

Monitors in the system have to share information about what was previously discovered. This is achieved by regularly <msg> = <header><payload> ? <header> = <length><type> <length> = <integer 16 > <type> = <stopset> <stopset> = "0" <integer 16 > = "4" | . . . | "65535" Fig. 7. ABNF for a message 0 15 16 31 length type header data A trivial implementation could have a monitor simply send its global stop set as a byte stream to another monitor, without any additional information. However, such a simple mechanism would make further extensions difficult, specially in the case of a peer-to-peer or overlay system used to manage the whole system (see Sec. VI).

❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤                      payload
For that reason, we provide a general framework for messages exchanged between monitors. This framework might be easily extended in order to manage any type of messages.

In this section, we describe the message framework we propose and a specific message that is actually the only one currently implemented: STOPSET. Both will be first described in Augmented Backus-Naur Form (ABNF) [START_REF] Crocker | Augmented BNF for syntax specifications: ABNF[END_REF] and second as a byte stream.

A message in a traceroute@home system is composed of the two parts: the header and the payload. The header is mandatory and gives information about the message length and its type. As opposed to the header, the payload is optional. Some messages, for instance a heartbeat-like message, do not need any payload. The ABNF for a message is given in Fig. 7.

Fig. 8 provides a byte-stream vision of a message. Length and type are expressed as 16 bit integers. Note that the length includes both the header and the payload. The minimum length of a message is thus four bytes, i.e., the header length. The type and length encoding is big-endian.

In the current traceroute@home implementation, a monitor sends and receives only one type of message: the STOPSET. This message contains information about the topology discovered by a monitor. A STOPSET message is sent when, for a given sliding window, a step size is reached. Two pieces of information (number of the sliding window and the step 10. STOPSET packet format size considered) must be present in the STOPSET message so that the receiver might identify the message and link it to a portion of a sliding window. In the ABNF, the step size is called a slice. A STOPSET message must provide information on implementation details: the type of stop set (the stype, list or Bloom filter), the type of network probed (the ip, IPv4 or IPv6) 3 and the eventual compression (the compress) of the stop set. Of course, it also contains the relevant portion of the global stop set. The STOPSET payload in an ABNF format is given by Fig. 9. Fig. 10 shows the STOPSET message as a byte stream. We see that 13 bits are reserved for future extensions. Padding is used to fill in this unused part of the packet. The stop set is encoded as a byte array. If the stop set is implemented as a list, a group of 8 bytes refers to a global stop set key. The first four bytes represent the interface address and the last four bytes represent the destination address. The principle is identical modulo group size in case of IPv6 addresses.

stop set ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ❤ Fig.

V. DEPLOYMENT STORY

This section talks about the deployment and validation of traceroute@home on PlanetLab nodes, the different difficulties we encountered (not necessarily related to PlanetLab) and the way we solved them (Sec. V-A). Sec. V-B presents our deployment results.

A. Difficulties Encountered

Some routers along the path may be poorly configured. It seems that they, when building the ICMP message, can modify the original datagram. Several ICMP messages were returned with the source and destination ports changed in the original datagram. This is a critical issue as the source port of the originating UDP datagram is different for each datagram, as explained in Sec. IV-C, in order to identify the thread that sends the datagram. This problem can be avoided by also checking the destination address in the original IP header.

By definition, a PlanetLab node is minimalist in the sense that it provides a nearly empty file system. The only environments provided consist of Perl (version 5.8.3) and Python (version 2.3.3). By default, there are no compilation possibilities (no make, no gcc, no g++) and no Java environment. We had to install a Java runtime environment, on each nodes supposed to run traceroute@home.

Table I describes the availability of PlanetLab nodes in December, 2005. Offline nodes are those that are either being installed or having long term issues. When gathering these statistics, 18.9% of the PlanetLab nodes were offline. unreachable nodes are in production, i.e., the PlanetLab system is running, but not reachable via SSH. 10.9% of the nodes were unreachable. broken nodes are those that have failed tests but that can be logged into via SSH as root. No PlanetLab nodes were broken. ok nodes are those that can be used normally. 70.2% of the PlanetLab nodes were up but it was important for us to check availability before running any experiment.

PlanetLab nodes reboot periodically for scheduled maintenance and upgrades. Fig. 11 shows the number of reboot during one week in December 2005. 64 PlanetLab nodes were involved in rebooting, for a total of 18,577 reboots. Among these 64 nodes, 40 rebooted only once. However, 14 nodes rebooted more than 50 times. Among these 14 nodes, 10 nodes rebooted more than 1,000 times during the one week period and one node rebooted 3,144 times. As it is not clear how to know which PlanetLab node will reboot and when, a longterm experiment must allow for the possibility that a portion of the nodes will reboot.

Fig. 12 evaluates the performances of the ten PlanetLab nodes we used as traceroute@home monitors (see Sec. V-B for details about the traceroute@home monitors). The performance statistics were gathered on December 20 th , 2005. The horizontal axis shows the PlanetLab nodes we used as traceroute@home monitors. The left-side vertical axis gives the number of active slices on each monitor (black bar). A slice is the PlanetLab term for an account. The right-side vertical axis gives the proportion of network resources used by the most consuming slice on each monitor (grey bar). By network resources, we understand the quantity of information sent and received.

Regarding first the quantity of slices per monitor, we see that the maximum, 59, is reached with the monitor labeled 2. The minimum is 32 for the monitor 6. On average, a PlanetLab node chosen for being a traceroute@home monitor hosted 45 slices. These statistics give us an idea of a PlanetLab node load, as each PlanetLab node is supposed to affect resources to a slice in a best effort way.

The right-hand of the vertical axis informs us of the proportion of network resources used, on each monitor, by the most active slice. It oscillates between 0.5526 (monitor 2) and 0.8383 (monitor 1). On average, 0.65601 of the network resources are used by a single slice.

B. Deployment Success

As described in prior work [START_REF] Donnet | Efficient algorithms for large-scale topology discovery[END_REF], security concerns are paramount in large-scale active probing. It is important to not trigger alarms inside the network with Doubletree probes. It is also important to avoid burdening the network and the destination hosts. It follows from this that the deployment of a cooperative active probing tool must be done carefully, proceeding step by step, from an initial small size, up to larger-scales. Note that this behavior is strongly recommended by PlanetLab [START_REF] Peterson | Using PlanetLab for network research: Myths, realities, and best practices[END_REF]Pg. 5].

Our application was deployed to only ten PlanetLab nodes. We selected ten nodes based on their relatively high stability (i.e., remaining up and connected), and their relatively low load. These traceroute@home monitors are scattered around the world: North America (USA, Canada), Europe (France, Spain, Switzerland, Spain), and Asia (Japan, Korea). In the future, we will wish to scale up the number of monitors to, at least, the skitter scale (i.e., 24 monitors).

The destination list consists of n = 200 PlanetLab nodes randomly chosen amongst the approximately 300 institutions that currently host PlanetLab nodes. Restricting ourselves to PlanetLab nodes destinations was motivated by security concerns. By avoiding tracing outside the PlanetLab network, we avoid disturbing end-systems that do not welcome probe traffic. None of the ten PlanetLab monitors (or other nodes located at the same place) belongs to this destination list. The sliding window size of w = n/m consists of twenty destinations. We consider two step sizes (i.e., slices) by window, so each slice counts ten destinations.

Finally, each traceroute@home monitor was configured as follows: the probability p was set to 0.05, the global stop set implementation was the list (i.e., the standard implementation) and no compression was required before sending the STOPSET messages.

The experiment was run on the PlanetLab nodes on Dec. 20 th 2005. All the traceroute@home monitors were started at the same time. The experiment was finished when each monitor had probed the entire destination list.

A total of 2,703 links and 2,232 nodes were discovered. We also encountered 2,434 non-responding interfaces (routers and destinations). We recorded 36 invalid addresses. Invalid addresses are, for example, private addresses [7, Sec. 2.1].

Table II shows the different reasons for stopping backwards and forwards probing for each traceroute@home monitor. It further indicates the h value computed by each monitor. The last row of the table indicates the mean for each column.

Looking first at the backwards stopping reasons, we see that the stop set rule strongly dominates (98.6% on average). On average, normal stopping (i.e., reaching the first hop) occurs only 0.65% of the time.

Fig. 13 shows the stopping distance (in terms of hops), for a given monitor, Uoregon, when probing backwards and forwards. The vertical line indicates the h value computed by Uoregon. Results presented in Fig. 13 are typical for the other traceroute@home monitors.

We see that more than 90% of the backwards stopping occurs at a distance of 5, that is to say the distance corresponding to h -1. In 2.5% of the cases, the probing stops between hop 1 (normal stopping) and hop 4. Except for hop 1, the other stops are caused by the stop set, probably due to very short paths. They illustrate the cases in which the first probe sent with a TTL of h directly hits a destination.

Looking now at the forwards stopping reasons in interfaces) plays a greater rule. We believe that these gaps occur when a destination does not respond to probes because of a restrictive firewall or because the PlanetLab node is down. On average, in 58% of the cases, the stop set rule applies, and in 28.2% of the cases, the normal rule applies. The normal rule proportion might be seen as high but we have to keep in mind that a Doubletree monitor starts with an empty stop set. Therefore, during the first sliding window, the only thing that can stop a monitor, aside from the gap rule, is an encounter with the destination.

Looking at the stopping distance in Fig. 13, we see that the distances are more scattered for forwards probing than for backwards probing. Regarding the forwards probing, a peak is reached at a distance of 10 (18.5% of the cases). In 7% of the cases, the monitor stops probing at a distance of 6, that is equal to the value h. It could correspond to the stop set rule application or the normal rule, by definition of p. Recall that p defines the probability of hitting a destination with the probe sent with a TTL equals to h. For our experiment, we set p = 0.05, meaning that in 5% of the cases the first probe sent by a monitor will hit a destination.

Table III shows the total size of STOPSET messages (in KB) sent by each monitor. The size takes into account the header of the message (4 bytes) and the payload.

A STOPSET message is sent by a monitor when it reaches a step size (i.e. a slice) in the current sliding window. As we define for our experiment two step sizes per sliding window and as we deploy our prototype on ten PlanetLab nodes, each monitor sent 20 STOPSET messages. We tune each Doubletree monitor in order to use the list implementation of the stopset. The monitors do not exchange their entire stop set. They only send an update that contains the (interface, destination) pairs discovered during the current step size probing.

In Table III, we can see that a monitor sends a total of between 7.41 KB (Ethz) and 12.84 KB (Nbgisp) to the subsequent monitor. On average, a monitor sends 10.39 KB of stop set information into the network.

During our experimentation, the traceroute@home application did not flood the network with STOPSET messages. However, our prior work [START_REF] Donnet | Improved algorithms for network topology discovery[END_REF] has shown, on a larger destination list, that it can grow to excessive sizes. In this case, we recommend configuring a traceroute@home monitor to first use the Bloom filter implementation of the stop set and second compress it before sending it in the network.

Table IV shows, for each traceroute@home monitor, the running time (in minutes) in terms of probing and waiting. The waiting period occurs when a monitor has finished its sliding window or a slice in a given sliding window and is waiting for the global stop set that should be sent by the previous monitor in the round-robin topology. We see that nearly all monitors have to wait. A waiting period, in our implementation, lasts 30 seconds. When the timer expires, the monitor checks if it received a new message. If so, the waiting period ends and a new probing period begins. Otherwise, it sleeps during 30 seconds. To avoid infinite waiting, if after 40 sleeping periods (i.e., 20 minutes), nothing was received, the monitor quits with an error message. Fig. 14 illustrates the interactions between the probing state and the waiting state.

We believe that these long waiting periods are due to a characteristic of the PlanetLab IP stack. It seems that when ICMP replies are received by the stack, the recvfrom() function does not read them immediately. As the timer set on the listening socket never expires in this case, we think that the recvfrom() function is waiting for the permission to access the IP stack. It looks like the resource is owned (or locked) by another process on the PlanetLab node. Note that this behavior was also noticed by other Planet-Lab users [START_REF]Planet-Lab users mailing list[END_REF].

VI. FURTHER WORK

This section discusses possible extensions and ways to improve traceroute@home (Sec. VI-A). It also discusses some key points to enhance measurement infrastructures in general (Sec. VI-B).

A. traceroute@home

One of the main aspects we would like to address in the near future is the stability of the whole system. Currently, it is like dominos: when a monitor fails, the whole system fails.

From a long term point of view, we aim to develop a peer-topeer (p2p) or overlay application to manage the whole system. However, it is not yet obvious how this p2p/overlay should work. We need a transitional solution. Currently, our main concern is monitor failure recovery.

A simple solution would be to build a centralized server. We keep the basic round robin functioning of the system (see Sec. IV-B) but in the middle, we place a server. In this case, the system has a star topology. The server's job will be to maintain the coherency of the round robin structure.

The basic idea is the following: the server knows the entire topology of the system and, for a given monitor, to which monitor it is supposed to send its global stop set and from which it must receive it. Regularly, the server checks each monitor's state by sending messages of type HEARTBEAT. When a monitor receives a HEARTBEAT message, it is supposed to reply immediately with a HEARTBEAT ACK message.

Non receiving consecutively, e.g., three HEARTBEAT ACK messages from a given monitor leads to its removal from the topology. The central server then begins a maintenance (or reorganization) phase of the topology. We estimate that the system can still work while there are at least two working monitors.

The second aspect we would like to tackle in the near future is load balancing between monitors. Each traceroute@home monitor focuses on its own part of the destination list, as described in Sec. IV-B. However, a problem arises on the step size by which to advance the window. A manually tunable step size does not eliminate blocking situations in which a monitor is waiting for the prior monitor to terminate its window before it can do any further useful work. Some monitors may potentially wait a long time before receiving the needed information (see Table IV). This might happen because some monitors are slower (as they are more heavily loaded) than others.

We plan to develop, in our future version, a way to balance the load between monitors. This will imply that the sliding window size will differ from one monitor to another. Some monitors will work harder while others will maintain a low probing rate.

Currently, a person who controls a traceroute@home system might use it in a malicious way in order perform DDoS attacks. Nothing is done to prevent this misuse of our tool. However, the centralized solution also has the opportunity to improve the security in traceroute@home.

The new version of traceroute@home should also allow communicating entities (monitors and servers) to mutually authenticate themselves through cryptographic level authentication. The next version must also prevent third parties from eavesdropping network communications, i.e., guarantee their confidentiality. It is unfortunately impossible to fully prevent eavesdropping from administrators of machines running our programs. In addition to that, the next version of traceroute@home must be able to guarantee the integrity of the results. We should be able to identify tampering if and when it happens. While it is not reasonable to expect that we will be able to detect subtle modifications, we shall reject absurd results and stop accepting input from those trying to submit them.

We are likely to extensively use cryptographic means. They have all the features we need and good tools are already available. We should use a public key infrastructure (PKI) to create and manage certificates for both clients and servers. Communicating entities will thus have the ability to easily verify their peer's identity before proceeding.

Furthermore, in addition to the Doubletree prototype robustness increase, this centralized infrastructure opens interesting perspectives, in particular for the development of a general network monitoring tool, along the lines suggested by COMNI Workshop [START_REF] Crovella | Community-oriented network measurement infrastructure (COMNI)[END_REF] in which we were active. We can imagine an extension to our tracerouting tool in order to provide additional measurement services that can be used for network monitoring. This could differ from Scriptroute [START_REF] Spring | Scriptroute: A public internet measurement facility[END_REF] as the monitors have the opportunity to cooperate.

Another interesting future undertaking would be to make our traceroute@home prototype IPv6 networks aware, allowing thus the use of Doubletree in IPv6 networks. Currently, the prototype can only probe IPv4 networks. In the near future, we would like to increase its capabilities to IPv6 networks. We believe that the current version can be easily extended in order to support IPv6. The main work should be done in the JSocket Wrench library, to handle IPv6 messages and sockets. Note that standard IPv6 traceroute, such as scamper [START_REF]IPv6 scamper[END_REF], or more complex tools, such as atlas [START_REF] Waddington | Topology discovery for public IPv6 network[END_REF], already exist.

B. Measurement Infrastructure

To test our prototype, we choose the PlanetLab infrastructure because it offers an easy access to a relatively large quantity of nodes. However, despite this apparent simplicity, we encountered several difficulties, as mentioned in Sec. V-A.

In a certain sense, these problems were expected as Plan-etLab is a testbed oriented towards overlays and peer-topeer networks. It is not an infrastructure entirely dedicated to network measurement or the deployment of measurement tools. Such tools have to share resources (CPU, memory, network access) with all the users, to strongly limit their use of disk space, cannot control node management.

Consequently and inspired by the COMNI workshop [START_REF] Crovella | Community-oriented network measurement infrastructure (COMNI)[END_REF], we believe it is time to think about an infrastructure entirely dedicated to network measurements and network monitoring. This infrastructure should allow us to go beyond the experimental environment of PlanetLab.

In the fashion of PlanetLab, the nodes composing this infrastructure should be numerous and geographically diverse. Further, this infrastructure should be carefully engineered in order to avoid attacks from the outside world and to avoid abuse from users.

VII. CONCLUSION

In this report, we described our Java implementation of an efficient and cooperative topology discovery algorithm, Doubletree. We implemented the algorithm in a tool we call traceroute@home. traceroute@home is freely available and easy to extend.

We first discussed the global functioning of the system and, next, we introduced the internal architecture of a traceroute@home monitor. We also explained the message frame-

Fig. 3 .

 3 Fig. 3. Tree-like routing structures

Fig. 4 .

 4 Fig. 4. Cumulative mass plot of path lengths from skitter monitor apan-jp

Fig. 8 .

 8 Fig. 8. General packet format

Fig. 9 .

 9 Fig. 9. ABNF for the STOPSET message 0 7 8 15 16 32 length 0 window slice s i c reserved

Fig. 11 .Fig. 12 .

 1112 Fig. 11. PlanetLab nodes reboot, one week (December 2005)

  Fig. 14. Probing/waiting state interactions

  Table II, we see that the gap rule (five successive non responding

								backwards probing
		0 0 1					forwards probing
	-0 1	1
	pdf
	1	2 -0
			0	5	10	15	20	25	30	35
				distance from monitor (hops)
	Fig. 13. Stopping distance for the Uoregon monitor
					monitor		size
					Blast	12.31
					Cornell	8.77
					Ethz		7.41
					Inria	7.85
					Kaist	11.41
					Nbgisp	12.84
					Paris	10.96
					UCSD		10.44
					Uoregon 11.62
					Upc		10.29
					mean		10.39
					TABLE III
	TOTAL STOPSET MESSAGE SIZE (IN KB) PER MONITOR

TABLE IV RUNNING

 IV TIME (IN MINUTES)

For interested readers, the DTD is available online[START_REF] Donnet | traceroute@home 1.0[END_REF].

Interested readers may find it online[START_REF] Donnet | traceroute@home 1.0[END_REF].

Currently, only IPv4 is implemented.

work proposed for our prototype. This message framework is easy to extend for further improvements.

In order to test our implementation, we deployed our prototype on a few PlanetLab nodes and evaluated its performance.

We finally identified some weaknesses in our prototype and proposed several ideas for further development. We also introduce a discussion about the opportunity of developing a networking measurement infrastructure.


Z

MobySpace : Mobility Pattern Space Routing for DTNs

Jérémie Leguay 1,2 , Timur Friedman 1 , Vania Conan 2

Basic concept

A MobySpace

Simulation results

• Epidemic routing: Bundles are flooded in the network. It is the optimum in terms of delays but leads to high buffer and radio utilization.

• Opportunistic routing: A node waits to meet the destination in order to transfer its bundle. It involves only one transmission per bundle.

• Random routing: At any time, a node may transfer the bundle to a neighbor chosen at random. Loops are avoided.

Preliminary simulations have shown promising results:

• Low delays compared to Random and Opportunistic.

Problem:

• Routing is a challenge in DTNs (Delay Tolerant Networks). Regular adhoc routing protocols fail because the topology suffers from connectivity disruptions.

Proposition:

• We propose to use mobility patterns of nodes, i.e. regularities in nodes contacts or movements, to define their position in a virtual Euclidean space used for routing. This space is called the MobySpace.

• Each node's position in the MobySpace (its MobyPoint) is flooded throughout the network. Other nodes use this information for routing.

• To route a bundle, a node chooses among its physical neighbors. It passes the bundle to the neighbor whose MobyPoint is closest to the destination's.

• The MobySpace can be defined in many ways, e.g. type/number of dimensions, distance function. This poster describes preliminary work.

• Let's consider users with power-law based mobility patterns. Their frequency of visits to locations follows a power-law distribution. This behavior has often been observed in reality.

• Each dimension in the MobySpace represents a location in the physical space. Each coordinate corresponds to the probability of finding the node at that location. We assume that these probabilities are known.

• Euclidean distance is used. • keep the bundle.

• give it to A.

• give it to D.

B uses the

  Fig. 2 : node mobility patterns

  Fig. 3 : MobySpace

• Low route lengths compared to Epidemic and Random. 54.6 59.1 103 MobySpace 203.3 160 117.8 Random 550.2 287.4 123.3 Opportunistic 16.2 13.2 10.9 Epidemic 2 1.5 1.1 d

		1.1	1.5	2
	Epidemic	3.7	3.7	3.8
	Opportunistic	1	1	1
	Random	44.5	55.9	69.8
	MobySpace	3.3	3.2	3.2

d Average bundle delay (s) Average route length (hops) Simulation

parameters: 50 mobile nodes, 25 locations, pause time at each location is uniformly distributed on [5s,15s], nodes generate bundles every 30s toward each of the others during the first 500s, simulation time is 4000s.

This work has been funded by the ANRT through a CIFRE grant, and by EuronetLab, and was conducted at the Université Pierre et Marie Curie (1) and Thales Communications (2).