C Andujar

E Puppo

Anass Lasram

Sylvain Lefebvre

Cyrille Damez

Scented Sliders for Procedural Textures

Keywords: (according to ACM CCS): I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism-Color, shading, shadowing, and texture

Figure 1: Left: Four random variations of the same procedural texture. Middle: Two textures with standard sliders controlling their appearances. Right: Two textures with

Introduction

Procedural texture design software, such as Substance from Allegorithmic, Genetica from Spiral Graphics or Filter Forge let technical artists carefully design complex procedures generating a large variety of textures. These procedures are controlled by a set of parameters exposed to the user. The most widely spread interface for this task is a set of sliders with the name of the parameters next to them. Such interfaces have proven efficient for setting parameters in a computer graphics context [KP10]. However, they are diffi-cult to use for someone discovering a new procedural texture: Contrary to other applications, the set of parameters and their meaning varies strongly from one texture to another (see Figure 1 or Figure 2). Since there is no visual clue -besides the parameter name -of what each slider exactly does, it is hard to predict and understand the influence of each parameter without trying a large number of different settings. In addition, dozens of parameters are exposed and many of them change the effect of each other. This quickly becomes a bottleneck for users exploring the possibilities of- fered by different textures. For instance, the parameters 'Cereals type' and 'Cereals color' in Figures 2 would not have any effect if the parameter 'Milk level' is set to its highest value. Our slider previews solve this problem by illustrating the effect of each parameter for the current settings. In particular, our sliders dynamically adapt to user interactions by refreshing all the slider previews if one parameter changes. This way, our visual slider previews make the user aware that the 'Milk level' is the only parameter that could affect the settings of Figures 2,bottom.

Designing such visual slider previews presents a number of challenges:

• The slider previews should indicate in an obvious manner all the changes that will occur in the texture when the slider is manipulated. • The pixel space is very limited: We cannot afford to display a large image below each slider, or the navigation from one slider to the next would quickly become tedious. This is especially problematic when the slider impacts small features in the texture. • The continuous refresh of slider previews imposes a fast synthesis algorithm.

We address these three points in Section 3.

Previous work

In ] seek to summarize the content of a large image in a smaller pixel-space. These techniques, mainly targeted at photographs, change the layout of features in the image in order to preserve the most important elements. We exploit these approaches to create our visual sliders.

Slider previews

Overview To synthesize visual slider previews following the requirements set in Section 1, we need to concentrate in a small pixel area the important information: in this case the parts of the image that are effectively changed by the slider.

We understand this as an importance-driven image-relayout problem: Starting from an image showing all changes we would like to discard non-essential information that remains unchanged when moving the slider. This is done by the following steps:

• A large image is formed by tiling the texture a number of times horizontally. The large image is then divided into a grid of patches (Figure 3, (b)). Each column of patches reflects the appearances of one setting of parameters. The parameter corresponding to the slider is increasing from left to right while others keep their current values. This means that the leftmost column of patches reflects the appearances produced if the parameter is at its lowest value. The rightmost column reflects the appearances produced if the parameter is at its highest value. • An importance map is computed (Figure 3,(c)) by giving a score to each patch depending on its variance during slider manipulation. Patches that vary very often will get high scores. • The set of patches is reduced by removing patches with low scores (Figure 3, (d)). To limit distortions and preserve the layout of patches, seam-carving is applied on the importance map to remove patches rather than pixels. • The remaining patches (Figure 3, (e)) are stitched together using patch-based texture synthesis (Figure 3, (f)).

Generating the grid of patches We note V ∈ [0, 1] N the parameter vector of size N describing the current state of the texture. There are N sliders and we are interested in synthesizing the slider s, s ∈ {1..N}. The values in V will be fixed with the exception of V [s] that varies linearly from 0(left) to 1(right). We construct a grid of patches G of size

W G × H G in which every element G[x, y], (x, y) ∈ {1..W G } × {1..H G }, is a patch of size W P × H P . The patch at G[x, y] is contained in the texture Tx that has a size of W T × H T and parameters v such as v[i] = V [i] i f i = s and v[s] = x-1
WG-1 otherwise. The upper-left corner of this patch is located at coordinates Importance map The importance map I gives a score to every patch in G (Figure 3,(c)). This score is high for patches with high visual impact. We note I[x, y] the score of patch p = G[x, y]. We note (x 0 , y 0 ) the upper-left coordinates of patch p = G[x, y] and stored in texture Tx. The score I[x, y] of patch p is computed as follows:

I[x, y] = WG ∑ t=1 e -||x-t|| 2 2σ 2 1 + ∑ x0+WP i=x0 ∑ y0+HP j=y0 ||Tx[i, j] -Tt [i, j]|| 2
The corresponds to a per-pixel difference between the patch p contained in texture Tx and the patch having the same location as p but contained in another texture Tt . As an example, in Figure 3,(a), the blue patch in texture Tx is compared to the two blue patches in T x-1 and T x+1 . The numerator controls the contribution of each texture Tt in the score. Textures with very different parameters will contribute less. These contributions can be further customized using the scalar σ = 0. A small σ 2 emphasizes the possible variations when little changes occur to the slider cursor. If σ 2 goes to infinity then all textures Tt will have a same contribution making the score independent from the cursor position. We typically set σ = 1 and, in order to speed up the algorithm, we ignore textures with very low contribution (the numerator is very low).

Patch carving

We shrink the grid of patches G with seam-carving [START_REF] Avidan | Seam carving for content-aware image resizing[END_REF], removing vertical/horizontal seams of patches. Carving at the patch-level rather than pixel-level avoids texture distortion but produces discontinuities along the boundaries of the remaining patches. The carving is done simultaneously on G and I according to the scores contained in I. The shrunk version of the map I is shown Figure 3,(d).

It mostly contains patches with high scores. In principle, non-linear relayout may occur due to the carving. However in practice we never noticed a bias strong enough to justify remapping the parameters.

Synthesizing After carving, we hide abrupt and discontinuous changes of appearance between patches by optimizing their boundaries. Starting from the shrunk version of G (Figure 3, (e)), we find an optimal boundary with graphcut [KSE * 03]. To further reduce potential visible seams, we allow for small changes in the patch positioning and repeat graph-cut optimization a few times (typically four times). The result is a continuous preview strip, with an emphasis on the part of the texture impacted by the slider Figure 3, (f).

Results

Figures 4 shows the benefit of our patch summarization method. In this figure, the most varying elements of the texture (the green stars) represent small features that are far from each other. Sliders (a) and (c) are generated with a naive algorithm that starts from a large slider preview having the same width as the final slider and the same height as the procedural texture. It then crops the horizontal region that maximizes the overall variation. Sliders (b) and (d) are generated using our method. These sliders reveal more variation and give a better insight to the user. Figure 5 shows an example containing texture and color parameters. User interactions are shown in the accompanying video. Generating one slider for this texture takes on average 151 milliseconds. This timing is dominated by the generation of the 16 textures required to build the slider. Figure 6 shows another example of sliders for a more complex texture. In this case, an average of 355 milliseconds is required to generate one slider.

Limitations

Photographs or textures exhibiting global structural changes are not handled well by our approach. The synthesizer fails to preserve the structure as shown Figure 7, top. One possible work-around is to show these particular parameters as thumbnails. We included this possibility in our sliders by selecting high variance regions as thumbnails and ordering them on the slider Figure 7, bottom.

Conclusion

Procedural textures tend to have parameters exhibiting unpredictable effects. In this paper a visually driven slider interface for procedural textures has been described to ease parameter selection. Our algorithm generates and analyses several procedural textures at interactive rates. This allowed the creation of dynamic visual sliders that give users more control over the result.

Our sliders are not only useful for final users, but also during the design of the texture. Most procedural textures are obtained by assembling image filters, between tens to hundreds of them. Each filter exposes a number of parameters (e.g. blur intensity, blending alpha value, emboss direction). Our slider previews help quickly revealing the possible effects to the designer.

Figure 2 :

 2 Figure 2: Two settings of the 'Cereals' texture with visual sliders control. Top: The 'Milk level' parameter has a low value. Bottom: The 'Milk level' parameter has a high value, masking the effect of other parameters.

Figure 3 :

 3 Figure 3: Algorithm overview: (a) Texture samples from which patches are extracted. (b) Initial grid G of patches. (c) Per-patch importance map I. This map will be carved to remove patches with low scores. (d) Carved map I. Bright pixels correspond to patches with high scores. (e) The remaining patches. Notice how the flowers, which are the most impacted, dominate the patches. (f) Resulting slider after the synthesis step.

Figure 4 :

 4 Figure 4: A procedural texture with two different types of sliders controlling parameters. (a) and (c): Sliders generated by cropping the best horizontal strip from a larger initial slider. (b) and (d): Sliders generated by our method.

Figure 5 :

 5 Figure 5: Two different settings of the 'bark' texture with visual sliders controlling parameters.

  content of the video. In a recent work, Kerr and Pellacini [KP10] compare different approaches for the task of selecting material shader parameters. The study concludes that, under interactive feedback, sliders perform best in particular when precise adjustments are required. Image summarization techniques [AS07, SCSI08

	that summarizes the
	a human-computer-interaction context techniques have
	been developed to improve sliders efficiency by augment-
	ing the sliders with visual clues such as histograms or color
	bars [Eic94, WHA07]. Video tapestry [BGSF10] replaces
	the slider used to navigate in a video by a single image strip

c The Eurographics Association 2012.

Acknowledgments

We thank Allegorithmic's texture artists for producing the examples shown in this paper. This work was supported by the ANR SIMILAR-CITIES 2008-COORD-021-01. Figure 6: Two different settings of the 'rotten wall' texture with visual sliders controlling parameters.

Figure 7: Top: Failure cases : our approach does not capture global, sudden structural changes in the textures. Bottom: Slider thumbnails constitute a possible solution for structural parameters.


Benoit Donnet
email: benoit.donnet@uclouvain.be

Bamba Gueye
email: gueye@run.montefiore.ulg.ac.

Mohamed Ali Kaafar
email: mohamed-ali.kaafar@inrialpes.fr

Path Similarity Evaluation Using Bloom Filters

Keywords: Traceroute, topology, Bloom filter, similarity

The performance of several Internet applications often relies on the measurability of path similarity between different participants. In particular, the performance of content distribution networks mainly relies on the awareness of content sources topology information. It is commonly admitted nowadays that, in order to ensure either path redundancy or efficient content replication, topological similarities between sources is evaluated by exchanging raw traceroute data, and by a hop by hop comparison of the IP topology observed from the sources to the several hundred or thousands of destinations.

In this paper, based on real data we collected, we advocate that path similarity comparisons between different Internet entities can be much simplified using lossy coding techniques, such as Bloom filters, to exchange compressed topology information. The technique we introduce to evaluate path similarity enforces both scalability and data confidentiality while maintaining a high level of accuracy. In addition, we demonstrate that our technique is scalable as it requires a small amount of active probing and is not targets dependent.

Introduction

Intuitively, the path similarity between two nodes is defined as the IP paths overlap when those two nodes infer their paths towards an arbitrary third one. Two nodes are considered as being similar if they observe a large portion of overlapping paths (or path segments) towards a set of destinations.

Path similarity is very useful for many Internet applications, ranging from efficient distributed systems deployment to content location selection. In the context of Content Distribution Networks, for instance, providers could use path similarity to achieve both optimal performance path selection and path redundancy insurance, the path selection being obtained through similarity, while redundancy by non similarity.

Similarity and non similarity might find also a suitable usage in the deployment of large-scale measurement infrastructure. In particular, in the context of the Internet topology discovery [START_REF] Donnet | Internet topology discovery: a survey[END_REF] based on traceroute [START_REF] Jacobson | traceroute, man page, UNIX[END_REF], it is important that monitors are well diversified in the network. An infrastructure such as the recently introduced Archipelago [START_REF] Hyun | Internet mapping: from art to science[END_REF] or the Internet monitoring project grenouille.com [?] would benefit from similarity/non similarity when deploying a new monitor. Indeed, if two vantage points share a large path similarity, it is obvious that they will collect redundant data, making their contribution marginal. On the contrary, if two monitors are quite non similar, data collected should lead to a broader view of the network. In the same way, monitoring distributed systems from a set of vantage points can benefit from path similarity information in order to diversify monitoring locations [START_REF] Radoslavov | On characterizing network topologies and analyzing their impact on protocol design[END_REF][START_REF] Teixeira | In search of path diversity in ISP networks[END_REF][START_REF] Fei | How to select a good alternate path in large peer-to-peer systems?[END_REF][START_REF] Agapi | Synthetic coordinates for disjoint multipath routing over the Internet[END_REF].

Finally, as previously mentioned by Hu and Steenkiste, path similarity might be used in the context of available bandwidth estimation [START_REF] Hu | Quantifying Internet end-to-end route similarity[END_REF]. Indeed, if several monitors are similar, it is very likely they will share the same bottleneck, and as most of the end-hosts encounter bottleneck at the first or the last four hops [START_REF] Hu | Optimizing network performance in replicated hosting[END_REF], it would be sufficient to collect bandwidth information from a single of these monitors.

Path similarity between monitors is evaluated based on actively collected data. A monitor probes a portion of the Internet, using traceroute, and sends the discovered topology to other monitors in the system for comparison. It should however be noted that current "raw" paths comparison for route similarity only achieve desirable accuracy, reliability and sensitivity properties at the expense of scalability and high overhead issues [START_REF] Teixeira | In search of path diversity in ISP networks[END_REF][START_REF] Hu | Quantifying Internet end-to-end route similarity[END_REF]. In other words, several monitors that would like to compare mutual similarities may need to exchange a huge amount of "raw" traceroute data, which can prove to be very onerous in terms of overhead, and may lead to severe under performances of the network, especially when considering thousands of monitors, probing millions of IP destinations.

Further, exchanging "raw" traceroute data reveals most, if not all, of the network topology information of monitors, that are often controlled by Content Distribution Networks (CDN) [START_REF] Ratnasamy | Topologically-aware overlay construction and server selection[END_REF][START_REF] Bakira | Approximate server selection algorithms in content distribution networks[END_REF]. Such an information is of primary economic and security importance for CDNs. Encryption could of course help with such confidentiality issue, but it does not solve any of the scalability issues.

Such non scalable and cumbersome properties are then a compelling case for a lossy coding technique that would be used to exchange compressed data while maintaining both accuracy and confidentiality about path similarity.

In this paper, we propose to apply Bloom filters [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF] for allowing monitors to exchange path information. A Bloom filter is a lossy summary technique based on a bit vector and a set of hash functions. While, Bloom filters have found numerous usages, particularly in networking due to their bandwidth saving capabilities [START_REF] Broder | Network applications of Bloom filters: A survey[END_REF][START_REF] Mitzenmacher | Compressed Bloom filters[END_REF], our approach uses them for encoding links discovered by a monitor during its probing (i.e., tracerouting) phase. The compressed path information is then exchanged between monitors and the bit vectors are compared by each monitor for evaluating its similarity with others. Scalability is achieved through the exchange of much lower amount of data, while confidentiality is maintained without encryption, as hop by hop information that would reveal networks topology is hashed by the Bloom filter. We provide methods for comparing two Bloom filters and infer, from this comparison, the similarity level between monitors.

Nevertheless, if a Bloom filter has the advantage of compressing the information, it comes with the drawback of triggering false positives. It would be a matter of concern if the bandwidth advantages of Bloom filters would be overcome by those false positives. A tradeoff must thus be found between compression, false positives, and similarity accuracy.

In this paper, we tackle also issues related to such tradeoffs. Based on real traceroutes we collected from PlanetLab monitors towards sets of thousands of destinations1 , we examine the benefits of applying Bloom filters, and compare the efficiency of similarity results obtained by exchanging compact traceroute data. We first demonstrate that our Bloom filter-based approach allows one to reduce bandwidth consumption by more than, at least, four order of magnitude in terms of exchanged information, compared to traditional proposals quantifying path similarity. We also examine the effects of the Bloom filter parameters on the similarity results, showing that, as long as we consider a reasonable compression ratio, we provide accurate similarity results. We finally demonstrate that our approach is scalable, reducing so the risk of the probing phase from various monitors to turn out into a distributed denialof-service (DDoS) attack. Indeed, we show that our technique is independent from the number of traceroutes performed, as well as from the overlapping of destinations (i.e., monitors in the system do not necessarily require to traceroute exactly the same destinations).

h 1 (b) h 2 (b) h 2 (a) h 1 (a)
The remainder of this paper is organized as follows: Sec. 2 provides the required background on Bloom filters and explains how they can be applied to study Internet paths similarity; Sec. 3 formally describes the similarity metrics we introduce in this paper; Sec. 4 evaluates our lossy similarity technique; Sec. 5 positions this paper regarding the state of the art; finally, Sec. 6 concludes this paper by summarizing its main contributions and discussing future directions.

Bloom Filter

In this section, we briefly remind the Bloom filters theory (Sec. 2.1) and, then, explain how they can be used for coding path similarity information (Sec. 2.2).

Theory

A Bloom filter [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF] is a vector v of m bits that codes the membership of a subset A = {a 1 , a 2 , . . . , a n } of n elements of a universe U consisting of N elements. Typically, the size of the universe is not specified [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF][START_REF] Broder | Network applications of Bloom filters: A survey[END_REF]. However, Bloom filters are only useful if the size of U is much larger than the size of A.

The idea is to initialize this vector v to '0', and then take a set H = {h 1 , h 2 , . . . , h k } of k independent hash functions h 1 , h 2 , . . . , h k , each with range {1, . . . , m}. For each element a ∈ A, the bits at positions h 1 (a), h 2 (a), . . . , h k (a) in v are set to '1'. Note that a particular bit can be set to 1 several times. This is illustrated in Fig. 1.

To check if an element b of the universe U belongs to the set A, all one has to do is check that the k bits at positions h 1 (b), h 2 (b), . . . , h k (b) are all set to 1. If at least one bit is set to 0, we are sure that b does not belong to A. If all bits are set to 1, b possibly belongs to A. There is always a non-zero probability that b does not belong to A. In such a case, a false positives is raised.

In order to calculate the false positive rate, one can assume that all hash functions map each item in the universe into a random number uniformly over the range {1, . . . , m}. As a consequence, the probability that a specific bit is set to 1 after the application of one hash function to one element of A is 1 m and the probability that this specific bit is left to '0' is 1 -1 m . After all elements of A are coded in the Bloom filter, the probability that a specific bit is always equal to '0' is

p 0 = 1 - 1 m kn . (1)
As m becomes large, 1 m is close to zero and p 0 can be approximated by e -kn m .

The probability that a specific bit is set to '1' can thus be expressed as

p 1 = 1 -p 0 . (2)
The false positive rate can then be estimated by the probability that each of the k array positions computed by the hash functions is 1. f P is then given by

f P = p k 1 = 1 -1 -1 m kn k ≈ 1 -e -kn m k . (3)
The false positive rate f P is thus a function of three parameters: n the size of subset A, m the size of the filter, and k the number of hash functions.

In networking, Bloom filters find a suitable usage in overlay and peer-to-peer networks, resource routing, packet routing, and measurement infrastructures. Although Bloom filters allow false positives, for many applications the space savings outweigh this drawback when the probability of an error is sufficiently low (see Mitzenmacher and Broder for details [START_REF] Broder | Network applications of Bloom filters: A survey[END_REF]).

The question arises now on how to use Bloom filters in the context of path similarity, and hence profit from the compression benefits while maintaining sufficiently accurate similarity detection.

Application to Similarity

Any entity (let us call it monitor ) wanting to evaluate its path similarity with others considers a set of probing targets (i.e., the destinations) and launches traceroutes towards those targets. Once the traceroutes have been collected, a monitor has a list of links, i.e., hop-by-hop connections.

This set of links is then encoded in a Bloom filter, as described in Sec. 2.1. That is, our universe U is supposed to be the set of all possible pairs of IP addresses in the Internet while the subset A is the links discovered by the monitor during the exploration phase. All links are then mapped to k positions in the bit vector using H, the set of hash functions. The resulting bit vector is then exchanged between the various monitors. How a monitor can compare two bit vectors and retrieve path similarity information is discussed in Sec. 3.

This scheme has the obvious advantage of completely hiding topological information collected by a monitor. Of course, it is still possible to determine which links are encoded in the filter but it requires to test the whole universe, i.e., 2 32 × 2 32 tests. And the risk of false positives when querying the filter cannot guarantee to retrieve the exact set of links. The compression advantage of a Bloom filter is difficult to determine a priori and must be rather evaluated on a case study basis. This will be done in Sec. 2.

Coding hop-by-hop information in a Bloom filter and retrieving path similarity information from it might work if and only if two Bloom filters are comparable. This requires the set of hash functions used must be the same for all monitors. And, by extension, all the bit vectors must have the same size.

Such a situation requires that all monitors in the system reach an agreement on the Bloom filter tuning, given that a trade-off must be found between a good compression ratio of the links set and the false positive rate. If the monitors use the same set of destinations (or, at least, probe the same number of destination), one can infer the average of the number of links discovered. This average might then be used to tune the bit vector size.

Similarity Metrics

In the remainder of this paper, we refer by M, to the set of monitors and M i denotes any monitor in M measuring paths towards a set of destinations D .

Hu and Steenkiste [START_REF] Hu | Quantifying Internet end-to-end route similarity[END_REF] define path similarity as the percentage of links shared by routes from two monitors, M i and M j , to the set of destinations D. This metric, called RSIM is defined as follows:

RSIM (M i , M j , D) = d∈D 2 × Common(M i , M j , d) d∈D T otal(M i , M j , d) . (4)
Intuitively, closer to one RSIM (M i , M j , D), the more similar paths issued from M i and M j .

This metric however assumes that both upstream and downstream paths share a unique path from monitors to destinations and vice versa. The RSIM (•, •, •) metric considers "raw" traceroute data sharing. As it does not require any lossy compression technique, it will then be used as reference point for comparison with Bloom filters.

If monitors have to rely on Bloom filters to compare their similarity, new metrics comparing those filters should be added. In the following, we introduce such metrics and compare their respective performances in Sec. 4.

Let m i be the bit vector for monitor M i , constructed as described in Sec. 2.2.

Since the filters that the monitors compare are a set of bit vectors, a straight way to compare them is to use the Hamming distance between them. Such a distance counts the number of positions where vectors elements differ. In other words, the Hamming distance measures the minimum number of bits that need to be substituted to change one Bloom filter into the other. To consider a ratio of the differences that do exist between the filters, we normalize by the bit vector size of the compared filters. We define then the relative Hamming distance as follows:

rH(M i , M j ) = H( m i , m j ) | m i | . ( 5
)
where H( m i , m j ) provides the Hamming distance between both bit vectors. Put simply, the relative Hamming distance between two Bloom filters, of the same size and created with the same hash functions, can be used as a measure of the non-similarity of the underlying sets (IP hops from monitors to a set of destinations). A trend of rH(M i , M j ) towards 0 (respectively 1) implies that paths from these two monitors are similar (respectively non similar).

To observe the number of positions where both vectors m i and m j are identical, we compute the Relative Inverse Hamming distance as:

rH(M i , M j ) = H( m i , m j ) | m j | . ( 6
)
where H( m i , m j ) is the inverse of the Hamming distance. The larger rH(M i , M j ), the more similar paths issued from M i and M j .

It is important to note though that the Hamming distance, in case of binary sequences comparison (as it is the case for our Bloom filters), is equal to a XOR operation. In other words, the relative Hamming distance provides the percentage of cases where links are coded with different values in the same positions. The inverse relative Hamming distance provides the percentage of cases where the filters contain the same values at the same positions (either the value is set to '1' or '0').

However, recall from Sec. 2, that the Bloom filters are initialized to '0', and that elements are set to '1' and added to positions that correspond to the hash of that particular element. In order to alleviate the impact of the initialization process on the comparison of the filters, one can compare the positions identically set to '1' in both filters, as an indication of similarity. We introduce the so-called Bloom Distance, defined as the following:

B(M i , M j ) = One(And( m i , m j )) | m i | . (7)
where, And( m i , m j ) performs a logical AND between both vectors and One(•) counts the number of '1' in the bit vector in argument.

In this case, the optimum similarity value is given by the theoretical probability of filling the bit vector with ones, which can be easily calculated using Eqn. 2. The closer B(M i , M j ) to this probability, the more similar paths issued from M i and M j are.

Analysis

In this section, we evaluate the performance of our three metrics for retrieving path similarity information from Bloom filters. We first discuss our methodology, in particular how we actively collected data (Sec. 4.1). We next describe the performance metrics we use throughout this evaluation (Sec. 4.2). Sec. 4.3 discusses the results while Sec. 4.4 provides a summary of the main achievements of this section.

Methodology

For the purpose of our studies in this paper, we collected data using traceroute from 30 PlanetLab machines towards sets of 1,000 destinations. The measurement campaign was done between March 31 st , 2009 and April 5 th , 2009. All these experiments were run concurrently so as to experience the same network conditions. We used the native PlanetLab traceroute. Our dataset is freely available2 . Regarding the geographical situation of PlanetLab monitors used during the probing phase, Europe was the most represented continent, with 25 monitors, followed by America (four monitors in the United States), and Asia (a single monitor in China).

The traceroute destinations were randomly selected within the Archipelago set of 3,000,000 destinations [START_REF] Hyun | Internet mapping: from art to science[END_REF]. Archipelago is skitter' successor and has been deployed since September 2007. Destinations in Archipelago are selected from all routed /24's. As we will be, in the following, interested in the impact of overlapping destinations, i.e., monitors in the system share entirely the same set of destinations or a given proportion of destinations in their set of targets, we defined nine different destinations sets.

From our dataset, we removed one monitor, located in Europe (Italy), as it was unable to perform correctly the traceroutes: it stopped discovering interfaces after the second hop. Note that, for the rest of the monitors, on average, 85% of the paths were incomplete, i.e., did not terminate at the destination.

When tracerouting, some routers along the path might reply with invalid address, typically because of mis-configuration, or might not respond to probes.

For our study, we chose to remove links containing at least one invalid address and links containing at least one non responding node. 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, RFC 3330[END_REF]. Specifically, we eliminate visits to the private IP address blocks 10.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. On average, 15% of links discovered by a monitor were categorized as invalid.

Regarding Bloom filters, the hashing was emulated with random numbers. We simulated randomness with the Mersenne Twister MT19937 pseudo-random number generator [START_REF] Matsumoto | Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator[END_REF].

Performance Metrics

To When looking for the monitor that is the most similar to its observations, a monitor M i looks for the monitor M j which corresponds to max M j ∈M RSIM (M i , M j , D). When looking for the set of T OP n similar monitors, the most similar monitors involve those which returns the first top n RSIM (•, •, •) values.

A negative is a non similar monitor, according to the RSIM (•, •, •) metric, which should therefore be rejected by the similarity test. In others words, a negative is a monitor for which the RSIM (•, •, •) value compared to another monitor is not the maximum (or not within the set of n values if addressing the T OP n similarity). On the other hand, a positive is a monitor that has been considered as similar to another monitor by the RSIM (•, •, •) metric, i.e., that has the maximum RSIM value compared to the set of other monitors. The number of negatives (respectively positives) in the population comprising all the monitors comparisons is P N (respectively P P ).

For each metric, we identify a false positive as the case when a non-similar monitor has been wrongly identified by the specific metric as similar to the monitor in consideration. A false negative is a similar monitor that has been wrongly rejected by the specific metric as a non similar monitor. True positives (respectively true negatives) are positives (respectively negatives) that have been correctly reported by the specific metric and therefore identified as similar monitors to the monitors to which they are compared. The number of false negatives (respectively false positives, true negatives and true positives) reported by the metrics is T F N (respectively T F P , T T N and T T P ).

We use the notion of false negative rate (FNR) which is the proportion of all the similar monitors that have been wrongly reported as non similar (negatives) by the metric. The FNR is defined as:

FNR = T F N P P . (8)
The false positive rate (FPR) is the proportion of all the non similar monitors that have been wrongly reported as similar (positives) by the metric and is defined as

FPR = T F P P N . (9)
Similarly, the true positive rate (TPR) is the proportion of similar monitors that have been rightly reported as similar by the metric. TPR = T T P P P .

Finally, the true positive test fraction (TPTF) is the proportion of positive tests that correctly identified similar monitors:

TPTF = T T P (T T P + T F P ) . (11)

Results

In this section, we discuss the relevance of using Bloom filters for compacting path similarity information as well as the accuracy of our metrics for retrieving path similarity information from Bloom filters. We first show the advantage of Bloom filters in terms of compression (Sec. 4.3.1) and, next, evaluate factors that can influence the accuracy of our metrics for detecting compact path similarity. These factors are: the Bloom filter parameters (Sec. 4.3.2), the proportion of destinations overlap (Sec. 4.3.3), and the number of destinations probed by monitors (Sec. 4.3.3). In order to avoid biased statistical study, as these factors are interdependent, the factor being studied changes and the remaining are fixed. For example, evaluation of Bloom filter parameters may ignore changes in the overlapping proportion.

Bloom Filters Gain

Fig. 2 provides an insight into the gain of using Bloom filters instead of exchanging a list of links between monitors. The horizontal axis gives the 29 monitors, while the vertical axis gives the amount of bits sent by a given 1 Bloom filter parameters and false positive rate monitor. The curve labeled "list" is calculated based on the average number of links discovered by a given monitor over the nine destinations sets. This mean is then multiplied by 64, i.e., two 32-bits IP addresses. We determined the 95% confidence interval for the mean based on the Student t distribution. However, these confidence intervals, although being plotted in Fig. 2, are too tight to clearly appear.

As expected, the usage of Bloom filter provides an interesting compression ratio. With a vector made of 45,000 bits (a value selected for providing a very low false positive rate), we are already able to reduce the bandwidth consumption by a factor of 4. Note that, obviously, using a smaller bit vector will provide a stronger compression ratio. It is also worth to notice that some additional savings are possible by applying the compression techniques described by Mitzenmacher [START_REF] Mitzenmacher | Compressed Bloom filters[END_REF]. However, it would be a matter of concern if an higher compression ratio comes with an accuracy loss in the path similarity information. This is exactly the point we investigate in the following section.

Bloom Filter Parameters

In this section, we study the impact of varying the Bloom filter parameters on the similarity accuracy. As explained in Sec. 2, a Bloom filter is driven by two key parameters: m, the bit vector size, and k, the number of hash functions. Depending on the number of elements to record in the filter, these parameters have an impact on the false positive rate of the filter. Typically, smaller the filter (i.e., a high compression ratio), larger the false positive rate. Table 1 gives the correspondence between the values we selected for tuning the filter and the theoretical false positive rate. This correspondence is calculated using Eqn. 3. When tuning the Bloom filter according to the values given in Table 1, we consider a complete overlap of destinations between monitors and each monitor probes a set of 1,000 destinations. On average, this leads to the insertion of 4,100 links in the filter.

For each filter parameter, we plot the TPTF values for the T OP 1 and T OP 5 most similar monitors. This is given by Fig. 3. Each TPTF value is obtained as explained in Sec. 4.2, i.e., the total number of true positives and false negatives over all monitors for a given similarity metric. It is worth to notice that Fig. 3(a) and 3(b) are classified into four portions according to the used number of hash functions (k ∈ {1, 3, 5, 10}). Each point located within a given portion, for a given similarity metric, depicts m, the bit vector size. That means that for instance the first dotted point (respectively second, and third), within a given portion in figure 3(a), corresponds to a m value of 4, 500 (respectively 45, 000, and 450, 000).

The main observation retrieved from Fig. 3 is that, an acceptable compression ratio (e.g., m = 45, 000) always provides high TPTF. We see that the proportion of positive tests that are true positives is constantly high, regardless of the number of hash functions chosen, for moderate to quite significant compression ratios used by the filters.

However, the proportion of correct positive tests decreases each time we con- sider a too high compression ratio. It should be noted that if a small bit vector size is used (m = 4, 500), the proportion of true positives is not acceptable. Even if in the first portion, using k = 1, we observe a high TPTF, we still consider the test performance as non acceptable since the false positive rates of the filter in this case are too high (see Table 1).

In the light of this, we can conclude that as long as the compression ratio is not too high, whatever the number of hash functions is (i.e., even k = 1), the three metrics we propose produce a large number of positive tests, catching most of the similarities among monitors. For the remainder of this paper, we arbitrarily tune a Bloom filter with m = 45, 000 and k = 5.

Destination Sensitivity

In this section, we evaluate how sensitive are the B(•, •), rH(•, •), and rH(•, •) metrics to destinations. We evaluate this sensitivity on two planes: the destinations choice between monitors and the number of destinations probed. The destinations choice is expressed by the overlapping of destinations sets between monitors. To this end, we picked nine different destinations sets, each of them corresponding to a certain proportion of destinations overlap. We considered an overlap of 0% (i.e., all the monitors probe different destinations), 5%, 10%, 25%, 50%, 75%, 90%, 95%, and 100% (i.e., all the monitors probe the same destinations set). Fig. 4 illustrates how our metrics are sensitive to the choice of destinations with respect to different overlapping proportion, each monitor probing a set of 1,000 destinations. Each curve plots the TPTF values for the nine destinations overlaps.

As expected, a large overlapping proportion results in more accurate metrics, classifying correctly a larger portion of monitors as similar. This is exemplified in Fig. 4(a) with the increase trend of the B(•, •) curve. Despite the fact that the true positive test fraction curves clearly exhibit positive slopes, one should note that these rates increase much slower than the increase in overlapping proportions. That is to say that as long as we consider a non completely independent set of destinations, that is probed by monitors, it is very likely that the three metrics achieve constant similarity detection, that are roughly equal to 70%.

To further evaluate the impact of overlapping proportion on the Bloom filterbased similarity metrics, and to evaluate the efficiency of the similarity classification test, we plot in Fig. 5 the receiver operating characteristic (ROC) curves for different overlapping proportions. These plots show, for each metric, the point corresponding to the false positive rate (FPR) along the X-axis and to the true positive rate (TPR) along the Y-axis, with one portion for each destinations overlapping (90%, 95%, and 100%). The TPR and the FPR values are obtained by comparing the similarity computed over all monitors by rH(•, •), rH(•, •), and B(•, •) metrics with respect to RSIM (•, •, •). Obviously, the closer to the upper left corner of the graph a point, the better, since such points correspond to high true positive rates (i.e., a high proportion of positives being reported as such by the test) for low false positive rates (i.e., a small proportion of negatives incorrectly reported as positives).

We observe in Fig. 5 that, from this perspective, as already suggested in Fig. 4, our metrics for evaluating the path similarity through Bloom filters perform very well. Indeed, The FPR is very low (i.e., less than 2%) while the TPR is high (i.e., above 65%). In particular, rH(•, •) and rH(•, •) reach 80% of when looking for the T OP 5 most similar monitors for a full overlap of destinations. It is worth to notice the very low FPR rate obtained by the three metrics, giving with a high level of certainty the most similar monitor to another one, if detected as such, and providing also with a high confidence with the set of monitors that are more similar than others to the considered one.

Comparing the three metrics, in both Fig. 4 and5, we see that that B(•, •) performs worst compared to rH(•, •) and rH(•, •). Although, in Fig. 5(a), the false positive rates exhibited by the test in all the metrics are roughly similar -such values are too small to notice any significant difference-, better performances of the rH(•, •) and rH(•, •) metrics are particularly obvious for T OP 1 (Fig. 4(a)). We see that B(•, •) is quiet sensitive to the destinations choice, detecting on average 15% less true positives than the two other metrics. On the contrary, rH(•, •) and rH(•, •), provide mostly a constant true positive test fraction of 70% with little sensitivity to destinations choice.

The reason that either rH(•, •) and rH(•, •) outperform B(•, •) is due to the fact that the B(•, •) metric takes into account partial information in the filters (only bits set to 1') whereas rH(•, •) and rH(•, •) metrics consider the whole bit vector, a bit set to '0' being a valuable information as it indicates that no information has been recorded in that position in the filter. So far, the path similarity study consisted in each monitor probing a set of one thousand destinations. It would also be important to determine if the number of destinations to be probed has some influences on the path similarity between monitors. This might potentially lead to a scalability issue. Indeed, it might be a concern if, for providing quite accurate results, a large set of destinations must be probed, traceroute being known to be intrusive. On the contrary, if probing a small set of destinations is enough to obtain accurate results, this would be an incentive for the deployment of any system requiring the estimate of similarity.

Actually, the number of destinations parameter needs to be studied from two sides: a first side is related to the coding of paths towards the set of destinations, and hence the impact of the number of destinations on the exchanged Bloom filters among monitors. The first question to answer is then how the number of destinations can impact the accuracy of the metrics we propose to detect similarity between monitors. The second aspect of the problem is much more related to path similarity itself, and what we need to answer is "what is the number of destinations monitors need to probe in order to achieve desirable similarity results, in terms of high true positive detection of similarity and low false positives".

To study the first aspect, we consider a full overlap of destinations and vary the number of destinations probed. We take into account the following destinations set cardinality: 1, 10, 25, 50, 75, 100, 250, 500, 750, and 1,000. Fig. 6 shows the TPTF (vertical axis) when the number of destinations probed varies (horizontal axis). In this first experiment, similarity metrics we propose are again considered having as a reference the similarity as returned by the RSIM (•, •, •) metric. Note that the TPTF values in Fig. 6 show how accurate rH(•, •), rH(•, •), and B(•, •) are if monitors probe different set of destinations, while assuming that such a choice is not impacting the RSIM (•, •, •) metric itself.

The first interesting observation is that the accuracy of similarity detection in terms of true positives test fraction and false positive rates (not shown), is slightly constant if we consider a minimum number of 500 destinations. This gives to the three metrics a high utility if we consider that the overhead gained by not exchanging traceroute data is quadrupled when using Bloom filters. As expected, when monitors probe a small set of destinations, the accuracy is low. However, acceptable similarity detection can be considered when monitors probe sets of overall a hundred of destinations. This observation is generalized when looking for the T OP 5 most similar monitors. In essence, when considering a very small number of destinations, the similarity as computed by the metrics rH(•, •), rH(•, •), and B(•, •) are skewed by outliers inside the set of destinations. However, a set of destinations that are close to 100, is closely representative enough of the overall population of traceroute that a monitor can perform, being not shadowed by outliers while preserving a high degree of generality.

The choice of the optimal number of destinations to be probed would then require a compromise between the number of destinations where the Bloom filter-based metrics are not impacted, and the number of destinations where similarity using "raw" data would actually provide accurate results. tively row) in both tables represents the number of destinations probed by a monitor. Each cell T ij gives the proportion of monitors that return the same most similar monitors when probing a set of i destinations or a set of j destinations. Table 2 and A first global look at Table 2 and 3 suggests that, for obtaining accurate results, a certain amount of probing must be done, on the order of hundred of destinations. Probing so would allow one to obtain, in 80% of the cases, the same T OP 1 most similar monitor as larger probing campaign. On the 4 Summary contrary, retrieving the T OP 5 most similar monitors implies more probing, at least 250 destinations, for reaching the same accuracy level than T OP 1 .

A conclusion from Table 2 and 3 is that once a certain threshold of destinations probed has been reached (100 T OP 1 for and 250 for T OP 5 ), it is not necessary to burden more the network as it will not increase so much the similarity accuracy.

Note that we found similar results for the two other metrics, i.e., rH(•, •) and B(•, •).

Summary

In Sec. 4.3, we evaluated the behavior of our metrics for comparing several large sets of information encoded as Bloom filters. Those sets were made of topological data (i.e., links between routers) collected through traceroute.

During our analysis, we mostly focused on two planes: Bloom filters and destination sensitivity. For both planes, we showed that the metrics rH(•, •) and rH(•, •) provide globally better performance results than B(•, •).

Table 4 aims at highlighting the main lessons learned from Sec. 4.3. Regarding the Bloom filter plane, the number of hash functions does not impact the accuracy. On the contrary, the bit vector size, m, has some influence. A too high compression ratio would lead to bad performance. For the destination plane, it is sufficient to probe between 100 and 250 destinations, while the overlap of destinations sets between monitors does not influence the performance accuracy.

Despite, on average, 85% of the paths were incomplete in our data set, all above observations indicate that the data set used in this paper can plausibly represent a rich cross-section of the whole situation on today's Internet, and thus allow us to quantify path similarity with high accuracy.

Related Work

Since the late 90's, the topology discovery has been an extensive research field [START_REF] Donnet | Internet topology discovery: a survey[END_REF]. This research activity focused mostly on developing efficient traceroutelike tool or on modeling the Internet topology. Although there are many potential applications, the problem of path similarity does not appear to have been the subject of much study. Only a few work has been done on path similarity or diversity.

For instance, Teixeira et Hu and Steenkiste propose a metric, RSIM, for evaluating end-to-end path similarity. This metric is based on the number of common links between two monitors. A specificity of RSIM is that it is a bi-directional metric, i.e., it provides the similarity between monitor A and B, but also between B and A. An application of RSIM is for scalable bandwidth estimation [START_REF] Hu | Exploiting Internet route sharing for large scale available bandwidth estimation[END_REF]. However, it is not explained how this similarity information might be exchanged between monitors. Pathak et al. use path similarity at the AS and router level for evaluating the asymmetry of delay in the Internet [START_REF] Pathak | A measurement study of Internet delay asymmetry[END_REF]. Roughly, they propose a metric somewhat equivalent to RSIM but without taking into account the bi-directionality of links.

Works has also been done on identifying relays for alternative paths in large scale networks to increase route diversity [START_REF] Fei | How to select a good alternate path in large peer-to-peer systems?[END_REF][START_REF] Agapi | Synthetic coordinates for disjoint multipath routing over the Internet[END_REF]. Indeed, multipath routing has been proposed to better reduce maximum load on nodes and congestion. The use of alternatives paths improves the quality of service of communications across the Internet. For instance, Agapi et al. seek to find good relay nodes by using path similarity-based synthetic coordinates [START_REF] Agapi | Synthetic coordinates for disjoint multipath routing over the Internet[END_REF]. The key idea is based on the assumption that if a relay is suitable for a given path, it is also likely to be good for other similar paths. They define path similarity between paths P 1 and P 2 as the probability that a relay that is good for P 1 is also good for P 2 . Note that a set of relay could be exchanged between nodes using Bloom filters. This has not been investigated by Agapi et al.

Bloom filters have been extensively studied, particularly in networking due to their capacities in bandwidth savings when membership information must be exchanged between monitors [START_REF] Broder | Network applications of Bloom filters: A survey[END_REF]. Recent works used Bloom filters for exchanging topology information between traceroute-like monitors [19,?]. However, authors do not investigate how these Bloom filters might be used to evaluate path similarity.

Conclusions and Future Work

In this paper, we presented a Bloom filter-based approach to measure and exchange Internet path similarity between monitors. Our solution aims at considerably decreasing the amount of data sent through the network and ensuring the secrecy of topology information, while maintaining a high level of confidence in the measurability of path similarity.

It is based on compacting traceroute data through the use of Bloom filters, exchange those Bloom filters, and then compute similarities or dissimilarities based on a set of metrics to compare each pair of monitors' Bloom filters. Our approach does not rely on destination overlapping, and as such is unaffected by the choice of the set of destinations that the monitors can probe. In fact, we have shown that for different percentages of destinations overlaps, and for even an acceptable low number of probed destinations, our metrics still provide very good performance, distinguishing clearly between similar monitors paths.

To the best of our knowledge, this is the first such general method capable of providing accurate results while maintaining a very low overhead in exchanging traceroute information. Optionally, our method allows one to hide the network topology from monitors to the set of destinations they are monitoring. Since hops are hashed through the Bloom filters, topological information is then hidden and immune from any malicious data sniffing activity. Encryption of raw data provides also efficient confidentiality for data, but does not resolve the problem of overhead.

In practice, we introduced a simple way to study path similarity between monitors through compacted traceroute information. We choose to illustrate this study through traceroute information, which is at the very core of any Internet topology. This leads us to believe that our proposed similarity detection approach can effectively identify similar monitors in very many CDNs monitors deployment without any major software change. However, the way to code "raw" information and the metrics introduced to compare Bloom filters are generic enough to allow for their application on very many other topology characteristics information needed to be exchanged. We could, for instance, include information describing available bandwidth estimation for paths, as complementary to traceroute paths, and encode such an information into Bloom filters. Again, the gain in terms of reduced overhead would allow an easier and more practical information exchange among monitors. Note that, despite we performed measurement in an IPv4 environment, our technique is independent of the used IP version. This means that in a world where IPv6 would be largely deployed, our technique would present stronger interest in term of compression.

The measurements collected in this paper were deliberately tested on monitors and destinations chosen at random in the real Internet, with a realistic high percentage of non complete traceroute, although their similarities or dissimilarities increase with traceroute paths fullness. Despite the possible non optimal similarity measurements resulting from such a choice, the results obtained show the effectiveness of our method in characterizing path similarity with very low overhead. Nevertheless, given the gain afforded by our approach, one can envisage that CDNs may readily want to deploy monitors within their network to offer enhanced services to their customers, and to select well suited set of controlled destinations inside the core network. Such business driven strategic deployment can only improve the measurability of our similarity metrics and thus improve the path similarity accuracy, with much higher similarity detection rates than the lower bound reported in this paper. We have also shown that the false positive rates are very low, promising not considering monitors to be similar while it is not actually the case. This feature can be exploited when deploying redundant backup content servers. In this case, we insure (with very high confidence) that the backup server, if solicited, will continue to serve customers under the same conditions than the previous server.

The schemes presented in this paper are generic and might be applied in any context in which large sets of information must be exchanged and compared. Future work should reveal the efficiency of our techniques under those contexts. We further aim at evaluating them in a geolocalisation context.

Fig. 1 .

 1 Fig. 1. A Bloom filter with two hash functions

(a) T OP 1 (b) T OP 5 Fig. 3 .

 153 Fig. 3. Effects of Bloom filter parameters for a full overlap of destinations

(a) T OP 1 (b) T OP 5 Fig. 4 .

 154 Fig. 4. Impact of destination sets on similarity

(a) T OP 1 (b) T OP 5 Fig. 5 .

 155 Fig. 5. Destinations measurability

(a) T OP 1 (b) T OP 5 Fig. 6 .

 156 Fig. 6. Effects of the number of destinations probed

  [START_REF] Hyun | Internet mapping: from art to science[END_REF] indicates results for the rH(•, •) metric.

  characterize the performance of our similarity tests, we use the classical false/true positives/negatives indicators. Let us first define specifically what would be defined as a monitor similar to another one. First, we use the RSIM (•, •, •) metric as a reference of path similarity, as it uses 'raw data' exchange to compare routes in a hop by hop way (see Eqn. 4, Sec. 3). Since our Bloom filters-based algorithms compact exchanged data, and as such, the metrics we introduce alike should be evaluated considering raw data similarity as a reference. We then consider that monitors routes are actually similar if the RSIM (•, •, •) metric returns the maximum value. It can also happen that we look for the n most similar monitors to another one. In this case, we consider the set of RSIM (•, •, •) values corresponding to the highest n values, and we refer to those monitors by T OP n .

Table 2 and

 2 3 provides the proportion of monitors finding the same T OP 1 (Table2) most similar monitor and the same T OP 5 (Table3) most similar monitors when probing different sets of destinations. Each column (respec-

	# destinations	1	10	25	50	75	100	250	500	750 1,000
	1	1.00
	10	0.42 1.00
	25	0.42 0.53 1.00
	50	0.42 0.50 0.75 1.00
	75	0.42 0.53 0.85 0.89 1.00
	100	0.39 0.53 0.67 0.78 0.78 1.00
	250	0.39 0.53 0.71 0.71 0.75 0.89 1.00
	500	0.39 0.50 0.64 0.71 0.67 0.82 0.82 1.00
	750	0.39 0.50 0.67 0.78 0.71 0.85 0.85 0.89 1.00
	1,000	0.39 0.46 0.60 0.71 0.64 0.82 0.82 0.82 0.89 1.00

Table 2 T

 2 OP 1 : Incidence of the number of destinations (rH(•, •))

	# destinations	1	10	25	50	75	100	250	500	750 1,000
	1	1.00
	10	0.39 1.00
	25	0.40 0.54 1.00
	50	0.37 0.53 0.67 1.00
	75	0.38 0.52 0.71 0.75 1.00
	100	0.41 0.50 0.67 0.73 0.76 1.00
	250	0.33 0.46 0.62 0.68 0.70 0.71 1.00
	500	0.31 0.47 0.61 0.68 0.69 0.68 0.86 1.00
	750	0.32 0.48 0.60 0.70 0.67 0.66 0.82 0.89 1.00
	1,000	0.33 0.47 0.61 0.71 0.67 0.68 0.83 0.88 0.93 1.00

Table 3 T

 3 OP 5 : Incidence of the number of destinations (rH(•, •))

  al. evaluate the IP-level path diversity between Points of Presence (PoPs), i.e., a collection of routers owned by an AS in a specific location (city or suburb). Based on real ISP dataset, Teixeira et al. found that all pairs of PoPs have, at least, two disjoint paths between them. However, Teixeira et al. do not discuss if this diversity might be observed at the Internet scale, neither how a given application might use this diversity.

Our dataset is freely available. See http://planete.inrialpes.fr/ similarity_data/Traceroute-Similarity.tar.gz

See http://planete.inrialpes.fr/similarity_data/ Traceroute-Similarity.tar.gz

Acknowledgements

This work has been partially supported by the European Commission-funded 223936 ECODE project and the European Commission-fund 27489 ANA project.

Mr. Donnet's work is supported by the FNRS (Fonds National de la Recherche Scientifique, rue d'Egmont 5 -1000 Bruxelles, Belgium.).