Ruud Van De Bovenkamp

Fernando Kuipers

Piet Van Mieghem
email: vanmieghem@tudelft.nl

A Kuipers

Gossip-based counting in dynamic networks

Keywords: Gossip-algorithms, network dynamics, node counting

We propose Gossipico, a gossip algorithm to average, sum or find minima and maxima over node values in a large, distributed, and dynamic network. Unlike previous work, Gossipico provides a continuous estimate of, for example, the number of nodes, even when the network becomes disconnected. Gossipico converges quickly due to the introduction of a beacon mechanism that directs messages to an autonomously selected beacon node. The information spread through the network shows a percolation-like phase-transition and allows information to propagate along near-shortest paths. Simulations in various different network topologies (ranging in size up to one million nodes) illustrate Gossipico's robustness against network changes and display a near-optimal count time. Moreover, in a comparison with other related gossip algorithms, Gossipico displays an improved and more stable performance over various classes of networks.

Introduction

Several developments over the past years, such as the growing use of peer-topeer overlay networks and sensor networks have led to the deployment of very large distributed networks. Although distributed networks are very scalable, they have no central point where information is stored, which makes it challenging to gather global network properties or perform coordinated actions.

One of the paradigms that has emerged to spread and gather information in a fully distributed network is that of gossip algorithms [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]. During the gossip process, a node periodically selects one of its neighbours and either sends, requests or exchanges information with that neighbour. This simple communication structure can be used to perform various tasks in distributed networks, ranging from overlay building and information location to calculating functions such as sums and averages.

In this paper we investigate averaging and summation over node values in large dynamic networks, and in particular the specific case of counting the number of nodes. Good estimates of the size of a distributed network can be valuable in optimising the performance of protocols and services that run on top of it, such as topology building in a peer-to-peer network. Node counting can also provide information on how many sensors are still working in a sensor network or how large an ad-hoc network currently is. The latter can be useful in vehicular communication to estimate traffic conditions. This paper is organised as follows. Related research is first discussed in Sec. 2, after which we propose our gossip-based counting algorithm Gossipico in Sec. [START_REF] Kostoulas | Decentralized schemes for size estimation in large and dynamic groups[END_REF]. In Sec. 4, we illustrate the algorithm's speed and robustness against network dynamics by a series of simulations. Sec. 5 presents our conclusions.

Related Work

Algorithms specifically designed to estimate or count the number of nodes in a network can be roughly divided into three groups: probabilistic polling algorithms, random walk based algorithms, and gossip-based algorithms [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF]. We highlight two representative examples of the first two techniques, after which we overview gossip-based algorithms. The probabilistic polling technique proposed by Kostoulas et al. [START_REF] Kostoulas | Decentralized schemes for size estimation in large and dynamic groups[END_REF] uses a conditional reply to a request message to estimate the network size, where the condition is determined by the distance between the replying node and the initiating node. In the algorithm by Massoulié et al. [START_REF] Massoulié | Peer counting and sampling in overlay networks: random walk methods[END_REF], a node sends a message containing an initial counter value on a random walk, and each node that is passed on the walk adds a degree dependent value to the counter. When the random walk returns to the initiating node, it can estimate the network size based on the counter value.

The gossip-based algorithms in [START_REF] Montresor | Towards robust peer counting[END_REF][START_REF] Jelasity | Epidemic-style proactive aggregation in large overlay networks[END_REF] rely on averaging an initial value over all nodes to estimate the network size. Jelasity and Montresor [START_REF] Jelasity | Epidemic-style proactive aggregation in large overlay networks[END_REF] initialise the node values to 0, with the exception of a single "special" node that has value 1. Nodes find the estimate of the network size as the reciprocal of the average. Montresor and Ghodsi [START_REF] Montresor | Towards robust peer counting[END_REF] first build an overlay structure based on random node values to determine an initial guess of the network size at each node. That initial guess is subsequently averaged to improve the estimate. In the work of Kempe et al. [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF] each node has a weight-value pair, and periodically sends half of its weight and value to both a random neighbour and itself. Nodes sum the pairs they receive and estimate the network size by dividing the summed value by the summed weight. By assigning a 1 or 0 to the initial weight of one or all of the nodes, the algorithm either sums or averages. Finally, Guerrieri et al. [START_REF] Guerrieri | Distributed estimation of global parameters in delay-tolerant networks[END_REF] studied the performance of both an averaging-based gossiping algorithm and three variations on a token collecting algorithm in delay-tolerant networks.

A major drawback of the random walk and probabilistic polling strategies is the poor accuracy [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF]. Size estimation based on averaging using gossip, however, currently also has its drawbacks. First of all, the process has to be started by a single node, which requires some sort of coordination in the initial phase of the algorithm. Moreover, the estimate of the network size at a specific node can exhibit a large overshoot, and joining or leaving nodes cause large local variations in the estimate that have to be spread out over the network. More extreme network dynamics such as the joining of two networks will result in an estimate that is half the new network size, whereas splitting the network in two will lead each part to believe it consists of the original number of nodes.

Our goal is to develop a gossip algorithm that does not share the drawbacks that averaging-based algorithms show and can be used in continuously changing networks, even when the network becomes disconnected. In our design we aim for little processing and storage at each node. Also, all nodes are uniform in capabilities and function, i.e. no node is special. The only requirements for the nodes are that they have a unique identifier and can reliably pass messages to their direct neighbours.

Gossipico

We propose Gossipico, a gossip-based algorithm that does not rely on averaging to estimate the network size, but combines messages to count the number of nodes. Message combining offers more flexibility in algorithm design than pair-wise gossip interactions alone, and allows for the simultaneous execution of several functions such as summation, finding maxima, and averaging in a single algorithm. Gossipico consists of two parts: Count and Beacon. Count performs the actual counting of the nodes, while Beacon is used to speed up Count. We first introduce the basic ideas behind Count and Beacon in Sec. 3.1 and 3.2, respectively, and will further develop those in Sec. 3.3 where we add robustness against dying nodes and disconnecting networks. In both Count and Beacon, nodes initiate communication periodically. We define a gossip cycle as the time period during which all nodes have initiated communication with one of their neighbours. The time between cycles in a deployment scenario will be a trade off between bandwidth consumption and speed.

Count

The general idea behind Count is that information from every node is combined and then spread to all the nodes again. This idea is illustrated in Fig. 1, where in the left-hand side picture every node has a single token. Each node periodically selects a random neighbour and gives this neighbour all its tokens (the path of the tokens is indicated by arrows); when a node receives tokens from another node it spreads messages telling how many tokens it has. The centre picture shows the spreading messages as hexagons with the number of tokens inside. As can be seen, tokens start to accumulate at different points in the network and the first estimates of the network size start to spread. In the right-hand side picture all tokens have piled up and every node knows how many tokens there are.

In Count the exchanged messages are more complex than tokens to allow for greater functionality: counting both upwards and downwards, averaging and finding minima and maxima. A message M = {C, F, T } contains a count value C ∈ Z, a freshness value F ∈ N, and a type value T ∈ {0, 1}. The type value Fig. 1. Three snapshots in the counting process.

indicates whether the message is an Information Spreading (IS) (T = 0) message, corresponding to the hexagons in Fig. 1, or an Information Collecting (IC) (T = 1) message, corresponding to the tokens. The count value C is the current estimate of the network size, whereas the freshness value F is a measure for the estimate's recentness. The message with the highest value for F contains the most recent information. Every node that joins the network is initialised with an IC message with count and freshness value 1, i.e. M = {1, 1, 1}, analogous to the single token in Fig. 1. Nodes send their message periodically and always create a new IS message afterwards. Messages are processed by the receiving node by following one of four rules, based on the type and the freshness of both the received message, M r , and the receiving node's current message waiting, M w (subscripts r and w stand for received and waiting, respectively). These four rules are explained below: 1 (T r = 0, T w = 0) If both messages are IS messages, the received message will replace the waiting message if the received message has a higher freshness value F than the waiting one. By keeping the message with the freshest information, only new information is spread through the network. 2 (T r = 1, T w = 0) A received IC message will replace a waiting IS message in order not to lose the collected information. 3 (T r = 0, T w = 1) A received IS message will be discarded if the waiting message is an IC message. This again ensures that no collected information is lost. 4 (T r = 1, T w = 1) If both messages are IC messages, a new message will replace the waiting message. The new message will be an IC message containing the sums of the waiting and received messages' C and F values, i.e. M = {C w + C r , F w + F r , 1}. 1 We call the process of replacing M w and M r by a new message combining messages.

In addition to the waiting message, every node has two state values: a count value C s ∈ Z, and a freshness value F s ∈ N (subscript s stands for state).

After processing the message, the receiving node updates its state values C s and F s if the resulting waiting message contains fresher information. Without separate state information, a node's estimate of the network size could go down temporarily when, for example, rule 2 forces a node to discard an IS message with fresher information, in order not to lose an IC message. After the node has passed on this IC message, it uses the state information to create a new spreading message with the most recent information it has.

All nodes are counted when there is only one IC message left. Rule 4 forces nodes to combine a received and waiting IC message, thereby reducing the number of IC messages in the network. At the same time, nodes cannot create new IC messages after initialisation; all new waiting messages are IS messages. The four rules described above ensure that if there is only one IC message left, it will contain the combined information of all the initial IC messages.

A message's freshness value will only differ from the count value in dynamic networks or when the algorithm is used to sum or average. When the algorithm is used in dynamic settings, the freshness value could run out of its range, but this can be fixed by allowing nodes to accept messages with a freshness value much lower than their F s as fresher, if F s is close to the maximum, or, alternatively, to trigger a recount using the mechanisms described in Sec. 3.3.

Beacon

The rules listed in Sec. 3.1 ensure that an IC message is passed on from one node to another, until it reaches a node that already has an IC message waiting, where it is combined. When nodes select a communication partner at random, IC messages perform random walks. Since a static network is counted when the last two remaining IC messages are combined, the count time is at least equal to the time it takes two independent random walks to meet at the same node, which increases prohibitively with the network size. Hence, IC messages should be forwarded in a less random fashion in order to speed up the counting process.

IC messages have a much higher chance of meeting each other when they are guided to a particular node in the network. We propose Beacon to guide IC messages towards each other by using a beacon. A beacon is a node whose location information spreads through the network by means of gossip.

Every node starts out as a beacon and competes for dominance with the other nodes to ensure that eventually there will be only one beacon. The competition resembles a battle between different armies, with the beacons as the army leaders. Every node j belongs to an army A j that has a certain strength S j ∈ R; node j also knows which neighbour P j is the first hop towards the beacon of its army, and the estimated hopcount D j to that beacon.

Initially, every node forms its own one-node army with a randomly chosen strength, i.e. A j = j, P j = j, D j = 0, and S j = random. 2 Nodes periodically and randomly select one of their neighbours to skirmish with. The outcome of such a skirmish is determined by two rules:

1 If both nodes are of the same army, the shortest path to the beacon is updated. 2 If one node is stronger than the other, the weaker node is incorporated into the army of the stronger one. The losing node takes over the values for A and S from the winning node, sets the winning node as the next hop to the beacon, and sets the estimated hopcount to one more than the estimated hopcount of the winning node.

Following these rules, the strongest node in the network will defeat all other nodes and become the only beacon. At the same time, the hop sequences towards the beacon converge to shortest paths along which IC messages can combine.

Network dynamics

Gossipico, as outlined so far, can cope very efficiently with a growing network: new nodes simply initialise their message at M w = {1, 1, 1} and start communicating. Node (and link) removals, however, are more challenging. A node can leave gracefully by sending an IC message with a count value of -1 (M w = {-1, 1, 1}) to account for its departure, but when a node dies, it cannot send this message. Moreover, even when a node leaves the network gracefully, there is no guarantee that the network will remain connected. If the network indeed becomes disconnected, a restart of the counting process must be triggered.

In order for nodes to be able to trigger a recount, the counting process is restricted to work only within the Beacon armies. When a new army is built, the nodes that are a part of that army count the size of their army using Gossipico as described above. As the growing army conquers the network, the network is counted. Triggering a restart comes down to building a new army that can defeat the reigning army.

Gossipico copes with dying nodes and disconnecting networks by following a single rule: every time a link is removed, the nodes adjacent to the link rebuild their armies to trigger a recount. In case the link removal did not disconnect the network, the two new armies will compete for dominance and the network is recounted. In case the link removal disconnects the network, the two revived armies will both survive, but cannot reach each other to compete. The algorithm is unaffected by network dynamics such as node and link addition or removal, because every node can trigger a recount in response to node or link removals.

Recounts are possible in Count if nodes will only accept messages from neighbours that are in the same army, and return any received messages to the sender otherwise. When a node is incorporated in a new army, it will create a new IC message with all values set to one (M w = {1, 1, 1}) to be counted in its new army.

Two concepts are added to Beacon to support recounts: army revival and immunity. Army revival allows a node j that is conquered by another army (A j = k) to build its own army again by selecting a new random strength S j and setting itself with a zero distance as the first hop to the beacon (P j = j, D j = 0). The newly revived army of node j (A j = j) will also be immune ( its previous army k. The immunity ensures that all nodes of army j will win all skirmishes with nodes of army k. Without immunity the recount will be suppressed if the new army j is weaker than the reigning army k.

I j = k) to Algorithm 1 Count Init: Mw ← {1, 1, 1} Sending 1: if Tw = 1 & A =
Although Gossipico is robust against dying nodes and other network dynamics using recounts as described above, a node's count value might drop during the recount process. Dips do not last long, and can even be avoided at the expense of a slight delay if nodes estimate the network size based on their estimate before the recount and the current count value. A node's estimate X could be calculated as X = (1 -f (t))X old + f (t)C s , where X old is the node's estimate at the time it was incorporated into a new army and f (t) is a logistic function that shifts the current estimate from the previous estimate to the current count value. The logistic function is given by f (t) = 1/(1 + exp(-t + 2D + 5)) where t is the number of times the node created the same IS message. The constant 5 is used to make sure that f (t) starts at a value close to 0. The distance D to the beacon ensures that high diameter (and therefore slower converging) networks automatically adjust to the recount time without the need of a tuning parameter. If the value of C s is larger than X old , nodes accept C s as the best estimate. In all simulations we avoid dips.

Interaction between Count and Beacon

The interactions between Count and Beacon are illustrated in Fig. 2. Count uses the next hop to the beacon in Beacon when an IC message is sent and the army information when receiving messages; Beacon resets the count process when a node is conquered by another army. The precise interactions will be discussed using the pseudo-codes of both Count and Beacon. The pseudo-code for Count is given in Algorithm 1. Lines 1-6 ensure that if a node wants to send an IC message (T = 1), and it is not the beacon of its own army, it will send the message to the next hop towards the beacon of its army. In all other cases the node will send its waiting message to a random neighbour. After sending a message a new waiting message is created in line 7. Lines 8-11 make sure that nodes only accept messages from within their army. If the message is indeed from within the army, it is processed according to the four rules in Sec. 3.1: lines 12-16 execute rule 1, rules 2 and 3 are executed in lines 17-19, and finally lines 20-22 form rule 4. The node's state values are updated in lines 23-26 if the new information is fresher than the current information. When a node is incorporated into a new army, it has to reset its state and message as shown in lines 27-29.

Gossipico

Algorithm 2 shows the pseudo-code for Beacon. The first thing that is checked during a skirmish is whether one of the nodes is immune to the army of the other node, as can be read from lines 1-8. If this is the case, the node that is immune will win the skirmish and the losing node takes over the strength, army and immunity from the winning node (ll. 26-30), sets the winning node as the first hop towards the beacon (ll. 29-30), and resets its Count process (l. 31). If both nodes are of the same army (ll. 9-12) the shortest path to the beacon is updated by checking whether either node can reach the beacon quicker via the other (ll. 18-25). If both nodes are from different armies, the stronger one will incorporate the weaker one (ll. 13-17). When a node revives its army it will determine a new random strength, set its army id equal to its node id, set its immunity equal to its present army, set itself at distance zero from the beacon and reset its Count process (ll. 32-37).

Convergence of Gossipico

In this discussion we divide the node counting process into three stages, although in reality these stages happen at the same time. In the first stage, the armies fight for dominance to establish a single beacon. In the second stage, the nodes send their IC messages around until they have all been combined. Finally, in the third stage, there is only one IC message left and the freshest count value spreads through the network. All three stages can be bounded by the spreading time of a single rumour in a network, which Giakkoupis [START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF] where N is the number of nodes in the network and φ the conductance. 3 It is important to note that φ depends on the network type and can depend on N .

During the first stage, the beacon information of the strongest army spreads unhindered through the network, just as a rumour in Giakkoupis' work. During the second stage, the IC messages are routed towards the beacon. Most messages combine on their way to the beacon, but in the worst case they combine at the beacon. Since the beacon information was spread in at most φ -1 log(N ) rounds, the longest path to the beacon is also O(φ -1 log(N )). During the third stage of the algorithm, a single piece of information, i.e. the count value of the last IC message, spreads to all other nodes by means of gossip; this is exactly the same process as rumour spreading. Simulations in the following section show that Gossipico has an O(log(N )) convergence in random and scale-free graphs.

Simulation results

We have performed various simulations to test the convergence and dynamic behaviour of Gossipico. Time is measured in gossip cycles. During each gossip cycle, the nodes are processed sequentially and in a random order. The count time of the network is defined as the number of gossip cycles that pass until every node in the network reaches a count value equal to the network size, and is averaged over a number of runs. When we use Erdős-Rényi random graphs, the probability p that a link exists is set to p = 2 log(N )/N ; scale-free graphs are

3 φ = min S⊆N , i∈S d i ≤|L| cut(S,S c ) i∈S d i
, where cut(S, S c ) is the set of links crossing a partition of a graph G = (N , L) in S and S c , with N the set of nodes, L the set of links, and di the degree of node i. generated following the preferential attachment model in Batagelj and Brandes [START_REF] Batagelj | Efficient generation of large random networks[END_REF] with such a number of links per new node that the total number of links is closest to that in an Erdős-Rényi graph with the same number of nodes. We will first discuss the rate of convergence in static networks. We then discuss the dynamic behaviour of Gossipico.

Counting in static networks

To illustrate the impact of Beacon on the performance of Count, we compare the performance of Gossipico to that of Count alone. Since Count can be seen as an extension of randomized token forwarding algorithms, these simulations also illustrate by how much Beacon might speed up other algorithms. Simulated network sizes range up to 10 6 nodes, and for every size a hundred different networks were generated. Fig. 3 shows the count time for both Gossipico and Count as a function of the network size for the two graph types. It is clear from Fig. 3 that Gossipico greatly outperforms Count on its own. The count time of Count scales as a power function of N , whereas the count time of Gossipico scales logarithmically. The logarithmic scaling of Gossipico is illustrated in Fig. 4. This plot is based on an average over 500 runs per size and shows an error band at ± one standard deviation. The count time can be fitted with 3.6 + 5.2 log 10 (N ) for the random graphs and 6.0 + 4.0 log 10 (N ) for the scale-free graphs. For random graphs the fit goes through all data points from N = 100 nodes and upwards, whereas for scale-free graphs the fit starts at N = 1000 nodes, because the scale-free degree distribution only emerges for larger networks. Both Count and Gossipico perform better in scale-free graphs than in random graphs; the hub nodes in scale-free graphs function as meeting places where IC messages can be combined. Because Beacon ensures that Gossipico scales logarithmically in random and scale-free networks, Count and similar algorithms are made suitable for use in very large networks.

Counting in dynamic networks

In order to illustrate Gossipico's robustness against node failure and to show that no node is indispensable, we track the average estimate of the network size while the node currently functioning as beacon is killed every 40th cycle. By killing a node it is meant that all links adjacent to the node are removed and that the node's state information and current message are lost to the network. We start out with both Erdős-Rényi random graphs and scale-free graphs ranging from N = 1000 to N = 100, 000 nodes. In Fig. 5 the average estimate of the network size over time is shown. As can be seen from Fig. 5, the average estimate of the network size follows the real network size. During the 25 cycles after the beacon dies, the network is recounted and the nodes shift their estimate from the previous count value to the new one to prevent a drop in the estimate. Even when the beacon node dies before the network is recounted, the average count value does not fluctuate too much as can be seen in the case of the 100, 000 node network (the upper graph in Fig. 5). This shows that Gossipico can keep up with dynamics with a rate of change close to, or marginally over, its own speed of convergence without introducing large fluctuations in the estimate. We next show Gossipico's behaviour in fully dynamic and disconnecting networks. We start by creating two random graphs, one of 1500 nodes (component 1) and one of 500 nodes (component 2), and connect them by adding 10 links between randomly selected nodes in each component. After fifty cycles we add 300 nodes to each component, all new nodes only link to nodes in their own components. After another 100 cycles the 10 links connecting the two components are removed, and are added again after another 150 cycles.

The average estimate of the network size over time is plotted in Fig. 6. The figure shows that the maximum count time for the initial 2000-node network over all the runs in this simulations is 33 cycles, regardless of the bottleneck of 10 links connecting the two components.

The addition of the 300 nodes per component (event 1 in Fig. 6) shows that new IC messages combine along near shortest paths. All IC messages combine, on average, within 7 cycles, while the average hopcount in these bridged networks is 4.2. After another 14 cycles, the spreading process finishes. The narrow dip (which only lasts for 1 cycle) in the estimated network size that is visible immediately after the addition of the new nodes is the result of the initial estimate of 1 of all new nodes.

Removing the bridging links between the two components (event 2) has a similar impact on the average estimate as a single dying node. The estimate falls (event 3) rapidly after an initial delay of about 25 cycles, without fluctuating. Regardless of the fact that 20 nodes trigger a recount at the same time, the estimate of the component size smoothly approaches the correct value in both components.

After reconnecting the two components (event 4), the estimate of the network size is updated just as quickly as a normal count of the network would be, as can be seen by comparing the first 25 cycles in Fig. 6 to the first 25 cycles after the components are reconnected in cycle 300. The increase in the smaller component is continuous, while the estimate in the larger component displays a bend (event 5) half way. This bend can be explained by observing that in half of the cases the army in the smaller component will dominate the network, and in the other half of the cases the army in the larger component will do so. When the larger component assimilates the smaller, the nodes in the smaller component will immediately accept the new count value as the new estimate because it is higher than their previous count value. In the opposite case, the nodes in the larger component will hang on to their previous count value a little longer. In either case, the counting process continuous without a restart as soon as the two components are connected.

Figs. 5 and 6 illustrate that Gossipico smoothly tracks all dynamics in the network, ranging from node addition to dying nodes and network components disconnecting and reconnecting again. Instead of relying on a periodic recount, Gossipico reacts to changes in the network. This ensures that in periods of network stability the estimate of the network size is also stable, while during periods of network dynamics, the algorithm tracks the changing network size.

Maximum count value over time

In this section we discuss the maximum count value in the network as a function of the normalised number of sent messages. The product of the number of nodes and the expected hopcount E[H] is taken as the normalisation constant. We simulated four different network topologies, an Erdős-Rényi random graph, a scale-free graph, a square grid, and a path. For each network type the highest count value in the network after every interaction between two nodes is averaged over 500 different realisations, both for N = 1, 000 and N = 10, 000. As an approximation of the average hopcount of both an Erdős-Rényi graph and a scale-free graph we use log(N ), while for the grid and path graph we use the approximation for a regular lattice E[H] Fig. 7 shows that the normalised number of sent messages before the maximum count value is reached, is of the same order of magnitude for all four networks. The main difference between the networks lies in the slope of the curves. In random and scalefree graphs, the maximum count value follows an S-curve that is more pronounced for larger networks, while in the grid and path graphs the maximum count value increases more steadily, and shows little influence of the network size. The difference between the grid and path graphs on the one hand and the random graphs on the other, is probably best explained by the speed at which the winning army can grow. The winning army in the path graph will grow at a fixed rate because the configuration at the borders of the army never changes. A growing army will always have two nodes at its endpoints that are neighbours with different armies. In the case of a square grid, the nodes in the winning army roughly form a circle and the army grows at an increasing rate proportional to the circumference of that circle. The increase in growth rate, however, is stable. For the random and scale-free graphs the situation is quite different. With every addition of a node to the winning army, the percentage of nodes not in the winning army that can be reached by the winning army can increase rapidly, thus allowing the army to grow explosively. After a brief initial phase the number of nodes in the winning army undergoes a phase-transition and covers almost the entire network. Similar phase transitions have been observed in processes where connections are randomly formed and have been explained in the context of percolation theory (e.g., [START_REF] Achlioptas | Explosive percolation in random networks[END_REF]). Although the average hopcount is the most important factor in the count time for all four network types, the speed at which an army can grow determines the slope of the graph.

Conclusions

We have proposed a gossip algorithm, Gossipico, to count the number of nodes in a network (or sum/average over node values). Our algorithm works by combining messages, which has an advantage over averaging-based counting algorithms in that the estimate approaches the network size quicker and more smoothly. Gossipico uses only O(log(N )) messages per node to count Erdős-Rényi random graphs and scale-free graphs, while randomised token forwarding based counting algorithms use O(N α ) messages per node, with a power exponent α > 0. The count time closely follows the average hopcount for grids and path graphs, which matches the lower bound O(D), with D the network diameter.

A major improvement, besides speed, over previous algorithms is that Gossipico automatically restarts the counting process when a change is detected that could lead to disconnectedness in the network. When two components are joined, the algorithm converges to the correct count without a restart, which is impossible for algorithms based on averaging. Simulations show that Gossipico is a very robust algorithm that provides nodes with a continuously updated estimate of the network size at a speed of convergence that equals that of rumour spreading, which is known to be very fast.

Fig. 2 .

 2 Fig. 2. Interactions between Count and Beacon.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Count time for Gossipico and Count. ER indicates an Erdős-Rényi graph, SF a scale-free graph.

d 3 N

 3 1/d , where d is the dimension of the lattice (for a grid d = 2, for a path d = 1)[START_REF] Van Mieghem | A scaling law for the hopcount in internet[END_REF].

Fig. 7 .

 7 Fig. 7. Maximum count value as a function of the normalised number of sent messages for four graph types.

  message consists of three fields: C, F , and T , i.e. M = {C, F, T }. Subscripts r, w and s indicate received, waiting and state, respectively.

			10:	return	21:	Mw	← {Fw +
		id	11: end if		Fr, Cw + Cr, Tw}
		then	12: if Tr = 0 & Tw = 0	22: end if
	2:	select peer P		then	23: if Fw > Fs then
	3: else	13:	if Fr > Fw then	24:	Fs ← Fw
	4:	select random peer	14:	Mw ← Mr	25:	Cs ← Cw
	5: end if	15:	end if	26: end if
	6: send message Mw to	16: end if
		peer	17: if Tr = 1 & Tw = 0		resetCount
	7: Mw ← {Cs, Fs, 0}		then	27: Cs ← 1
			18:	Mw ← Mr	28: Fs ← 1
		Receiving	19: end if	29: Mw ← {1, 1, 1}
	8: if Ar = A then	20: if Tr = 1 & Tw = 1
	9:	return Mr to sender		then

A

  bounds as O(φ -1 log(N )),

	Algorithm 2 Beacon
		Skirmish(Node i,j )	16:	prWinner(j,i)	27: Sj ← Si
	1: if Ii = Aj then	17: end if	28: Ij ← Ii
	2:	prWinner(i,j )			29: Dj ← Di + 1
	3:	return	updatePath(Node	30: Pj ← i
	4: end if	i,j )		31: resetCount	in
	5: if Ij = Ai then	18: if Di < Dj + 1 then	Count
	6:	prWinner(j,i)	19:	Pi ← j
	7:	return	20:	Di ← Dj + 1	reviveArmy(Node i)
	8: end if	21: end if	32: Si ← random integer
	9: if Ai = Aj then	22: if Dj < Di + 1 then	33: Di ← 0
	10:	updatePath(i,j )	23:	Pj ← i	34: Pi ← i
	11:	return	24:	Dj ← Di + 1	35: Ii ← Ai
	12: end if	25: end if	36: Ai ← i
	13: if Si > Sj then			37: resetCount	in
	14:	prWinner(i,j )	prWinner(Node i,j )	Count
	15: else	26: Aj ← Ai

Nodes should be initiated with a message Mw = {V, 1, 1} to sum over node values V instead. Finding a minimum or maximum value is achieved by not summing the values but keeping the highest or lowest value, whereas averaging requires an extra field in the message where the number of summed values are counted to allow the average to be calculated as V /C.

We assume perfect randomness, i.e. Pr[Sj = S k ] = 0, for j = k.


Haiyang Wang

Feng Wang

Jiangchuan Liu
email: jcliu@cs.sfu.ca

Ke Xu
email: xuke@csnet1.cs.tsinghua.edu.cn

Enhancing Traffic Locality in BitTorrent via Shared Trackers

Keywords: BitTorrent, Traffic locality, Multiple-torrent

The fast-growing traffic of peer-to-peer (P2P) applications, most notably BitTorrent, is putting unprecedented pressure to Internet Service Providers (ISPs). P2P locality has therefore been widely suggested to mitigate the costly inter-ISP traffic. In this paper, we find that even in the most popular ASes (Autonomous Systems), very few individual torrents are able to form large enough local clusters of peers, making state-of-the-art locality mechanisms for individual torrents quite inefficient. Inspired by peers' multiple torrent behavior, we develop a novel framework that traces and recovers the available contents at peers across multiple torrents, and thus effectively amplifies the possibilities of local sharing. We address some key design issues in this framework; in particular, we discuss the detection of peer migration and further explore the trends of improving peers' incentive. We develop a smart detection mechanism with shared trackers, which achieves 45% success rate without any tracker-level communication overhead. Our trace-based simulation results indicate that our framework can successfully reduce the cross-ISP traffic and minimize the possible degradation of peers' downloading experiences.

Introduction

Peer-to-peer (P2P) communications have gained tremendous popularity in the past decade. The most successful peer-to-peer file sharing application, BitTorrent (BT), enjoys phenomenal growth since its deployment in 2001, and now contributes to almost 35% of Internet's data exchanges [1]. Its exceptional scalability and robustness come from the enormous computation, storage, and communication resources collectively available at participating peers. Unfortunately, the ever-increasing traffic among the peers has also put unprecedented pressure to Internet Service Providers (ISPs). In particular, even though many BT peers interested in identical contents are located in the same or nearby Autonomous Systems (ASes), they are unnecessarily connected in the existing BT systems, thereby persistently increasing the costly cross-AS/ISP traffic.

To alleviate the cross-AS traffic, many solutions have been proposed beyond the straightforward throttling of P2P flows [START_REF] Dischinger | Detect Bittorrent Blocking[END_REF]. Among them, P2P locality [START_REF] Karagiannis | Should Internet Service Providers Fear Peer-Assisted Content Distribution?[END_REF] has been widely suggested, which explores the access localities to reduce the long-haul traffic. Yet, so far the distribution of BT peers has seldom been examined in the global Internet [START_REF] Otto | On Blind Mice and the Elephant: Understanding the Network Impact of a Large Distributed System[END_REF]. As such, the potential benefit and even the applicability of the locality mechanisms in the real world remain unclear.

In this paper, we examine the existence and distribution of peer locality through a large-scale measurement. Our measurement lasts three months, collecting information from more than 800, 000 peers. The results demonstrate that the BitTorrent peers do exhibit strong geographical locality that could be explored. Unfortunately, if we focus only on individual torrents, very few torrents are able to form large enough local cluster of peers. Even for the most popular ASes, this ratio is less than 5%, which makes stateof-the-art locality mechanisms for individual torrents quite inefficient.

Recent measurements, on the other hand, suggest that over 85% of the peers indeed participate in multiple torrents [START_REF] Guo | Measurements, Analysis, and Modeling of BitTorrent-like Systems[END_REF], which is also validated by our data. Inspired by this, we develop a novel framework that traces and recovers the available contents at peers across multiple torrents, thus effectively promoting the locality. We address the key design issues in this framework, particularly, the detection of peer migration. We demonstrate that the detection does not necessarily involve complex and costly tracker-level cooperations. Instead, a clever use of shared trackers can successfully detect around 45% of the peer migrations without extra communication overhead.

The performance of our locality mechanism across multiple torrents has been evaluated through extensive trace-driven simulations with various detection rates. Compared to state-of-the-art locality mechanisms for individual torrents, our solution improves the local content availability, thus significantly reducing cross-AS traffic. In addition, it brings minimal impact to the peer downloading experiences.

The rest of this paper is organized as follows. In Section 2, we illustrate the related works. We then present our measurement results in Section 3, which reveal the challenges to the design and implementation of P2P locality. In Sections 4 and 5, we explore the P2P locality across multiple torrents, and present an effective detection mechanism for peer migration. Finally, after the trace-driven evaluation in Section 6, we conclude the paper and offer some future directions in Section 7.

Related Works

There have been numerous studies on the implementation, analysis, and optimization of the BitTorrent system [START_REF] Qiu | Modeling and Performance Analysis of Bit Torrent-Like Peer-to-Peer Networks[END_REF]. P2P locality has recently attracted particular attention following the pioneering work of Karagiannis et al. [START_REF] Karagiannis | Should Internet Service Providers Fear Peer-Assisted Content Distribution?[END_REF]. Based on real traces and simulated torrents, they proposed the concept of locality in peer-to-peer systems and evaluated its benefit. Blond et al. [START_REF] Blond | Pushing BitTorrent Locality to the Limit[END_REF] showed through a controlled environment that high locality values (defined by [START_REF] Karagiannis | Should Internet Service Providers Fear Peer-Assisted Content Distribution?[END_REF]) yield up to two orders of magnitude savings on cross-AS traffic, without any significant impact to the peers' download completion time. Xie et al. [START_REF] Xie | P4p: Provider Portal for Applications[END_REF] further suggested cooperation between peer-to-peer applications and ISPs by a new locality architecture, namely, P4P, which can reduce both the external traffic and the average downloading time. Choffnes et al. [START_REF] Choffnes | Taming the torrent: a practical approach to reducing cross-isp traffic in peer-to-peer systems[END_REF] proposed Ono, a BitTorrent extension that leverages a CDN (Content distribution network) infrastructure, which effectively locates peers that are close to each other. Bindal et al. [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF] also examined a novel approach to enhance BitTorrent traffic locality, namely, biased neighbor selection. Using this method, a peer chooses the majority, but not all, of its neighbors from peers within the same ISP.

Guo et al. [START_REF] Guo | Measurements, Analysis, and Modeling of BitTorrent-like Systems[END_REF] revealed that more than 85% of all peers participate in multiple torrents and noted the peer migration behavior. This migration behavior indicates that some BT peers have the potential to serve others even when they have already left the swarm. They proposed an inter-torrent approach through tracker-level collaborations. The main idea is to build a tracker site overlay for tracker-level collaboration; the peers migrating between different torrents can then be detected and recovered as potential seeders for the torrents. Dan et al. [START_REF] Dan | Dynamic Swarm Management for Improved BitTorrent Performance[END_REF] further investigated how the separated torrents can be merged together to improve the performance of an entire torrent. The measurement from Piatek et al. [START_REF] Piatek | One hop reputations for peer to peer file sharing workloads[END_REF] however found that about 91% of peers in any single swarm do not arise in any other swarms. This observation seems to contradict the study in [START_REF] Guo | Measurements, Analysis, and Modeling of BitTorrent-like Systems[END_REF]; yet this is mainly due to the difference of their objective as well as their measurement schemes. On the other hand, the measurement study by Neglia et al. [START_REF] Neglia | Availability in BitTorrent Systems[END_REF] investigated the availability of BitTorrent system among different tracker configurations. The popularity and the performance of the multi-tracker configuration [START_REF]BitTorrent Multi-tracker Specification[END_REF] was discussed. Their study showed that around 35% of the torrents enable multi-tracker configurations. Pouwelse et al. [START_REF] Pouwelse | The Bittorrent P2P File-sharing System: Measurements and Analysis[END_REF] further discussed the relationship between BT trackers and torrents, and examined the tracker availability across multiple websites, albeit with individual torrents.

It is worth noting that, the studies of content bundling [START_REF] Menasche | Content Availability and Bundling in Swarming Systems[END_REF] also provide useful insights to understand multiple torrents behavior. A pioneering work from Menasche et al. [START_REF] Menasche | Content Availability and Bundling in Swarming Systems[END_REF] studied the content unavailability problem in the BitTorrent system. This study for the first time proposed a model to analyze the availability and the performance implications of bundling through an extensive measurement. Follow up studies such as [START_REF] Lev-Tov | Dynamic File-selection Policies for Bundling in BitTorrent-like Systems[END_REF] also studied some other aspects for content bundling in BitTorrent systems.

Our work was motivated by these studies; yet we explore the multi-tracker configuration across multiple torrents simultaneously, providing a seamless and light-weight solution to locality in the real BitTorrent system.

Pitfalls of BitTorrent Traffic Locality

We extracted a large collection of real torrents as advertised by www.btmon.com, one of the most popular torrent sites. We developed a script to automatically detect the 'href' field in each given HTML file and downloaded the metainfo files ending with '.torrent', which resulted in 74, 732 metainfo files. Within our data set, there are 316 bad metainfo files, 1, 027 unavailable torrents due to tracker failures, and 3, 340 torrents having only 1 peer. We excluded these abnormal torrents, and, to balance accuracy and measurement overhead, randomly selected 8, 893 out of the 70, 049 normal torrents for our study.

We then ran a modified version of CTorrent (a typical BitTorrent client in FreeBSD) [START_REF] Ctorrent | [END_REF] on the PlanetLab nodes. Different from conventional pure PlanetLab experiments in which the clients communicate with others within the PlanetLab only, our modified CTorrent clients actively joined existing torrents in the global Internet and recorded the observable peer information from the trackers and from other peers over time. As such, the small set of controlled PlanetLab nodes were able to capture the information of most peers in the torrents, in particular, their IP addresses. With a maximum of 50 initial peers from the trackers, we successfully detected the IP addresses of over 95% peers for most of the torrents. 1Given the IP addresses of the peers, we extracted their corresponding ASes through the 'whois' command in Linux. This resulted in 2, 405 distinct ASes, and Figure 1 shows the peer popularity across all torrents in these ASes. We can see that it can roughly be fitted by an exponential distribution (y = a bx , where a = 1.261 × 10 5 , b = -0.0480); in other words, despite the common belief that BitTorrent is extremely popular everywhere, a majority of the ASes indeed do not host a noticeable number of BitTorrent peers, e.g., 65% of them have less than 100 peers across all torrents.

Since the existing locality mechanisms have focused on individual torrents only, it is important to further investigate the distribution of local clusters, where a local cluster is the collection of local peers downloading the same content in an AS. Unfortunately, as shown in Figure 2, even for the very popular ASes, only a few torrents are able to As an example, in the most popular AS (AS3352), most of the torrents (over 95%) have less than 50 peers, even though these torrents are of quite large client populations (generally more than 500 peers). A close look reveals that the peers of most torrents are distributed in more than 150 ASes (the big picture of this distribution is shown in Figure 3), thus unavoidably involving extensive cross-AS communications. Such results suggest that a locality mechanism designed exclusively for individual peers can be ineffective for many of the torrents. In addition, since it only works with local peers that simultaneously participate in the same torrent; once a peer leaves the torrent, its downloaded contents will become invisible immediately. Fortunately, recent studies have revealed that over 85% of the peers indeed remain in the BT system, participating in other torrents after their departure [START_REF] Guo | Measurements, Analysis, and Modeling of BitTorrent-like Systems[END_REF]. Assume that the trackers can keep tracking those peers remaining in the system, the available local peers for most torrents could be increased significantly. Figure 4 validates the potentials of this locality approach across multiple torrents, where the peer population of most torrents (more than 85%) is tripled after 10 hours.

P2P Locality across Multiple Torrent: An Overview

We now proceed with a framework design for exploring P2P locality across multiple torrents. We particularly focus on the tracker-and-client-based solutions [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF], which rely only on modifications to end-system implementations. These locality solutions typically replaces the random peer selection by an AS hop count-based metric. Upon a request, the modified tracker sorts all other peers in the torrent in ascending order of their AS hop count to the requesting peer, and then sends the prefix of this sorted list (e.g., first 50 peers) to the requesting peer. The requesting peer would then choose the majority, but not all, of its neighbors from peers within the same ISP. Typically, 35 peers within the same ISP (AS hop count 0) can be returned together with 15 other random peers [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF].

For the individual torrent scenario, many neighbor selection approaches have been proposed [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF] [START_REF] Liu | Locality-Awareness in BitTorrent-Like P2P Applications[END_REF], which could also be applied in the multiple torrent scenario. The new challenge, however, is the detection of peer migrations among torrents. That is, if a peer has finished downloading in a torrent (say torrent 1) and left, but remains in other torrents, 2 how can we detect it, so as to recover the previously downloaded content to facilitate the locality for the remaining peers in torrent 1? This is illustrated in Figure 5, where peer x leaves torrent 1, but remains in torrent 2. If this migration can be detected, peer x can still serve as a potential seeder for torrent 1, which will greatly promote the locality for the peers in AS1.

It is easy to see that there are two challenges in this design: First, this solution may need a tracker overlay for tracker-to-peer and tracker-to-tracker communications; in particular, adding extra collaboration among the trackers to trace the migration of peer x [START_REF] Guo | Measurements, Analysis, and Modeling of BitTorrent-like Systems[END_REF]. Unfortunately, besides the overheads, enforcing communications between the public trackers can be quite difficult. Second, as shown in Figure 5, since peer x is no longer interested in torrent 1, it is hard to guarantee that this peer will have enough incentive and online time to seed the content again for others. To address these challenges, we will explore the detecting of peer migration as well as the incentive issues in the remaining sections.

Detecting Peer Migration with Shared Trackers

In this section, we will consider the migration detection with shared trackers. Assume torrent 1 and torrent 2 are both managed by tracker A; any peer migrating between these two torrents can simply be detected by tracker A without communication to other trackers. While this seems to be an ideal case, we now show that it indeed exists and is not uncommon.

Our observation starts from the fact that the latest BitTorrent metainfo file can include multiple tracker sites stored in the announce-list section [START_REF]BitTorrent Multi-tracker Specification[END_REF]. This multi-tracker configuration allows peers to connect to more than one tracker at the same time, which brings two tangible benefits: (1) better accommodates tracker failures; and (2) balances load among the trackers. Figure 6 offers an example with the multi-tracker configuration, where torrent 1 is managed by both trackers A and B, and torrent 2 is managed both by tracker B and C. In this case, if there is a BT peer x migrating from torrent 1 to torrent 2, tracker B will receive the arrival message of peer x twice with different content identifications (one arrival message for each torrent). Therefore, tracker B can actually be aware of any peer migration between torrent 1 and torrent 2 without any tracker-level collaboration.

The question now becomes (1) how popular is the multi-tracker configuration in the real world? and (2) how many migrations can be detected by this configuration in practice? To answer the first question, we consider all the 1192 trackers in our measurement. We record the announce-list of the torrents in our dataset, and show the cumulative distribution of the trackers that have been used in Figure 7. It indicates that more than 90% torrents have specified at least two trackers, and a few torrents even have announce-lists of multi-hundred trackers. This is much higher than an earlier measurement in 2007 [START_REF] Neglia | Availability in BitTorrent Systems[END_REF] (observed multi-trackers in 35% of the torrents), and thus suggests the multi-tracker configuration has been quickly recognized and deployed in the BitTorrent community. M i,j 1 is of a binary value, indicating whether torrents i and j have at least one common tracker (1-Yes, 0-No); similarly, each component of M 2 , M i,j 2 indicates whether torrents i and j share at least one migrating peer. It is easy to verify that a dot product between these two matrixes,

M 3 = M 1 • M 2 ,
gives the detectable migrations by the shared tracker approach. Specifically, M i,j 3 = 0 indicates that peer migrations between torrent i and j are either undetectable or do not exist at all; otherwise, the migrations between these two torrents will be detected even when M 2 (i, j) > 1. In our measured data, matrix M3 has 2538 non-zero entities, where M2 has 5707. Therefore, the peer migrations among about 45% torrents can be detected with shared trackers.

Once detected, the shared tracker can then use the biased neighbor selection [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF] to improve the P2P locality. It may also forward the migration information to other trackers; however, this collaboration is not compulsory in our framework.

Performance Evaluation

We now evaluate the performance of our framework design in the multiple torrent environment. We also compare it with other state-of-the-art locality solutions; in particular, the biased neighbor selection for individual torrents [10][19]. To achieve a fair comparison and also to examine the diverse factors that would affect their performance, we also use the discrete-event BitTorrent simulator developed by Stanford University [20] as [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF] did; we summarize the key network settings as follows (more configuration details can be found in [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF]):

All peers inside the ISPs are modeled after cable modem and DSL nodes, and have asymmetric upload/download bandwidth. The upload bandwidth of these peers is 100kbps and downloading bandwidth is 1Mbps. Considering the peer arrival/departure, most peers are joining the network at once, i.e. the flash crowd scenario. We focus on this feature since it is the most challenging for ISPs to handle. For each torrent, there is one original seeder that will always stay online (with 400Kbps uplink bandwidth), and other peers (except for the migrating peers) will leave the BT network forever as soon as they finish downloading. This is in accordance with the measurements because only 85% peers are participating in multiple torrents.

For the multiple torrent scenario, we assume that 1000 peer migrations occur during a 48-hour simulation, which is consistent with the data in Figure 4. We then evaluate the locality performance with different peer distributions and migration detection rate. The downloaded content of detected peers will be recovered for locality. These extra peers however will not simply serve as selfless seeders, but rather normal peers that expect data, albeit from other related torrents through a cross-torrent credit approach [START_REF] Yang | Multi-Torrent: a Performance Study[END_REF]. This will eliminate biases related to seeding incentives, which has been discussed in section 6.

We will focus on two metrics: cross-AS traffic and downloading completion time of peers, which reflect the potential benefit and impact of P2P locality, respectively.

We first calculate the percentage of the cross-AS traffic over the total downloading/uploading traffic of the peers in different torrents in the multiple torrent environment. Figures 8 and9 show the results of two typical torrents. The first is a relatively small torrent with 100 initial peers, and the second is a large torrent with 600 initial peers. With regular unmodified trackers, we can see that the cross-AS traffic is quite high (over 95%) when the peers are uniformly distributed among the ASes; for the exponential peer distribution, the cross-ASes traffic is relatively lower, implying that S-torrent M-torrent: 25% M-torrent: 50% M-torrent: 75% M-torrent: 100% Fig. 13: Downloading completion time of 600 peers (exponential distribution with biased tracker) certain peer localities have been naturally utilized. Even though this exponential peer distribution is more realistic as validated in our earlier measurement (Fig. 1 and2), the regular trackers do not take full advantage of the localities, and hence the cross-AS traffic remains high (around 80%). On the other hand, the biased tracker design prioritizes local peers for sharing, which, as shown in Figures 8 and9, significantly reduces the cross-AS traffic. This is particularly true for larger torrents that enable more opportunities for local connections.

Note that, when the detection rate is 0, the multiple torrent setting degenerates to a single torrent setting with no previously downloaded content being recovered from migrating peers. In this case, the cross-AS traffic is the highest in the figures. With biased trackers, the percentage of cross-AS traffic is also decreasing with the increase of migration detection rate. This suggests that the combination of locality and multiple torrent is quite effective in reducing cross-AS traffic. Recall that, for detection with shared tracker only, we have a success rate of 45% (see Section V), which translates into percentages of cross-AS traffic of roughly 50% and 35% for the 100-peer and 600-peer torrents, respectively. Even for uniform peer distribution, the traffic reduction is still remarkable, suggesting the necessity for exploring locality.

We next examine whether the re-shaping of the traffic will affect user experience; in particular, whether it will slow down the peer completion time. Figures 10 to 13 present the cumulative distribution of the downloading completion time with different peer distributions and torrent-tracker combinations. In the figures, we use M-torrent and S-torrent to represent the multiple-torrent-based and single-torrent-based solutions, respectively (the percentage values refer to the possible detection rate of peers' migration behavior). We show the results of the larger torrent with 600 peers, and we have observed similar curves for torrents of other sizes.

We first look at the case of peers uniformly distributed among ASes, as shown in Figures 10. Surprisingly, although no extra peers will serve as selfless seeders, the downloading completion time of the peers is still improved by the multiple torrent approach. Moreover, as shown in Figures 11, all peers will finish their downloading within 2700sec in the individual locality torrent; this completion time will be further improved to 2100sec with the proposed multiple torrent based locality. Note that the peers are assumed to be uniformly distributed among different ASes, all ASes therefore have enough local resources to utilize. Intuitively, potential benefits can be obtained by accessing these local peers.

However, for the exponential peer distribution (a more realistic case yet seldom been discussed in the previous studies), the downloading completion times of most peers are increased as shown in Figures 12. In particular, if the peers are connected to regular trackers, the multiple torrent based approach will slow down the downloading completion time of all peers significantly. The peers' downloading completion time is almost doubled when the detection rate reaches to 100%. This result shows that the exponential peer distribution across the ASes will potentially reduce peers' downloading experience with an increase of torrents' population. An intuitive explanation is that the flash crowd of peers as well as the trackers' random peer selection will put more pressure to the cross-ISP links and unavailable cause link overload (especially for the most popular ASes). Moreover, we have also observed that a great number of peers in the most popular ASes have very close downloading completion time (also leave the BT networks at similar time). Their departure will also reduce downloading performance of other peers in the BitTorrent system. Fortunately, as shown in Figure 13, the biased trackers can well address such a problem and peers' completion times only slightly increase. Note that, to clarify the possible degradation of the downloading performance, we have ignored the first quartile (25th percentile) of the CDF where the lines are too close to each other.

For easy comparison, we also show the completion times of the four typical torrenttracker combinations in Figure 14, where the peers are sorted in ascending order of their downloading completion time (the detection rate of M-torrent is set to 100%). It clearly shows that the combination of locality and multiple torrent will minimize the impact to the peer downloading experiences.

Conclusions

In this paper, we proposed a novel framework that traces and extracts the available contents at peers across multiple torrents, thus effectively improving the locality. A series of key design issues are addressed in this framework; in particular, we discussed the detection of peer migration and further explored the trends of sharing incentive. We developed a smart detection mechanism with shared trackers, which incurs no extra communication overhead. The performance of our framework was evaluated through extensive trace-driven simulations. Compared to the locality for individual torrents, our solution has successfully promoted the local content availability, thus significantly reducing cross-AS traffic and yet keeping minimal impact to peers' downloading experiences.

Fig. 1 :

 1 Fig. 1: Total peer popularity of 2864 ASes

Fig. 3 :Fig. 4 :

 34 Fig. 3: Peer distribution of the torrents

Fig. 5 :

 5 Fig. 5: Multiple torrent based P2P locality

Fig. 6 :Fig. 7 :

 67 Fig. 6: Peer migration in the shared tracker environment

Fig. 8 :Fig. 9 :

 89 Fig. 8: Percentage of cross-AS traffic (a small torrent with 100 initial peers)

Fig. 10 :Fig. 11 :

 1011 Fig. 10: Downloading completion time of 600 peers (uniform distribution with regular tracker)

Fig. 12 :

 12 Fig. 12: Downloading completion time of 600 peers (exponential distribution with regular tracker)

  Fig. 14: Comparison of downloading completion time

This ratio is calculated by comparing the number of detected peers with the total number of peers as advertised by the tracker of a torrent.

For ease of exposition, we will focus on the scenario that the migrating peer remains in only one another torrent. Our solution however can be easily extended to the scenario that the peer remains in more than one torrent.

Acknowledgement

This research was supported by a Canadian NSERC Discovery Grant, a Discovery Accelerator Supplements Award, an NSERC Engage Grant, China NSFC projects (61170292, 60970104), and a China NSFC Major Program of International Cooperation Grant (61120106008).