João Taveira Araújo
email: j.araujo@ee.ucl.ac.uk

Richard Clegg
email: r.clegg@ee.ucl.ac.uk

Imad Grandi
email: i.grandi@ee.ucl.ac.uk

Miguel Rio
email: m.rio@ee.ucl.ac.uk

George Pavlou
email: g.pavlou@ee.ucl.ac.uk

Balancing by PREFLEX: Congestion Aware Traffic Engineering

Keywords:

There has long been a need for a robust and reliable system which distributes traffic across multiple paths. In particular such a system must rarely reorder packets, must not require per-flow state, must cope with different paths having different bandwidths and must be self-tuning in a variety of network contexts. PREFLEX, proposed herein, uses estimates of loss rate to balance congestion. This paper describes a method of automatically adjusting how PREFLEX will split traffic in order to balance loss across multiple paths in a variety of network conditions. Equations are derived for the automatic tuning of the time scale and traffic split at a decision point. The algorithms described allow the load balancer to self-tune to network conditions. The calculations are simple and do not place a large burden on a router which would implement the algorithm. The algorithm is evaluated by simulation using ns-3 and is shown to perform well under a variety of circumstances. The resulting adaptive, end-to-end traffic balancing architecture provides the necessary framework to meet the increasing demands of users while simultaneously offering edge networks more fine-grained control at far shorter timescales.

Introduction

Traffic engineering, whether applied intradomain [START_REF] Fortz | Optimizing OSPF/IS-IS weights in a changing world. Selected Areas in Communications[END_REF][START_REF] Wang | Explicit routing algorithms for internet traffic engineering[END_REF] or interdomain [START_REF] Feamster | Guidelines for interdomain traffic engineering[END_REF][START_REF] Gao | Stable internet routing without global coordination. Networking[END_REF][START_REF] Quoitin | Interdomain traffic engineering with BGP[END_REF], focuses on distributing traffic across multiple paths whilst reducing an explicit cost, typically by minimizing the maximum link load observed over a period of time. Most research within traffic engineering however has been limited to optimizing traffic distribution from the vantage point of a single domain [START_REF] Wang | An overview of routing optimization for internet traffic engineering[END_REF], failing to take into consideration the wider impact such actions may have on end-to-end performance. This myopic view of traffic has become a severe limitation as endhosts become increasingly able to pool multiple paths according to their own preferences, optimizing for throughput, latency or reliability. While such trends are already noticeable due to peer-to-peer applications such as Bittorrent, it is expected that resource pooling will further tip toward the end-host with the deployment of multipath transport protocols such as MPTCP [START_REF] Wischik | The resource pooling principle[END_REF].

As a consequence of traffic patterns becoming more dynamic, traffic engineering has been forced to remain static. Since both congestion control and traffic engineering are intrinsically tied but unaware of each other by nature, there is a justified concern that updating routing too often may lead to oscillations in demand as hosts shift traffic to paths with better end-to-end performance. Coupled with an aversion to costly upgrades, this conservative approach to traffic management has meant that despite proposals for dynamic, online traffic engineering [START_REF] Elwalid | MATE: multipath adaptive traffic engineering[END_REF][START_REF] Kandula | Walking the tightrope: Responsive yet stable traffic engineering[END_REF], such solutions have remained both untested and undeployed.

While interest in traffic engineering has steadily waned within the research community due to these perceived limitations, the demand for fine grained traffic management tools remains high, as demonstrated by the continued proliferation of tools such as deep-packet inspection in order to shape traffic explicitly. Such mechanisms illustrate the continued tussle to circumvent the opaqueness inherent to the Internet's layered architecture. Networks frequently attempt to act on information contained within the transport or application layer in order to override resource allocation as performed by TCP. Conversely, the transport layer often makes incorrect assumptions due to the limited information contained within the network layer. With no explicit information on the path taken by each packet, TCP assumes a single path is maintained for the entire flow, and as such has grown to expect in-order delivery from the IP layer [START_REF] Thaler | Evolution of the ip model[END_REF].

PREFLEX [START_REF] Araújo | A mutualistic resource pooling architecture. Third Workshop on Re-Architecting the Internet (Re-Arch)[END_REF] is an architecture which addresses this information asymmetry by providing hosts with explicit knowledge of paths and networks with insight into the loss rate experienced by TCP. PREFLEX provides the means by which edge networks can assign flows to paths, but has not yet defined a method for such an assignment. In this paper we formulate an autonomous tuning mechanism for balancing traffic according to expected congestion rather than load.

PREFLEX overview

PREFLEX (Path RE-Feedback with Loss EXposure) [START_REF] Araújo | A mutualistic resource pooling architecture. Third Workshop on Re-Architecting the Internet (Re-Arch)[END_REF] is an architecture which redraws the boundaries between transport and network layers in an attempt to make both aware of each other's actions. PREFLEX relies on three components:

1. Hosts provide the network with an estimate of loss using LEX (Loss EXposure). 2. Edge networks provide hosts with information on which outgoing path to use through PREF (Path RE-Feedback). 3. A mechanism which assigns "flowlets" [START_REF] Sinha | Harnessing TCP's burstiness with flowlet switching[END_REF] to paths in order to balance loss. The latter is the focus of this paper. In the following sections we will briefly review the first two components.

Loss Exposure

Loss exposure is a mechanism by which hosts signal transport semantics at the network layer by marking the IP header, in a similar fashion to re-ECN [START_REF] Briscoe | Policing congestion response in an internetwork using re-feedback[END_REF]. If a host does not support LEX, all traffic is unmarked and will appear to the network as legacy traffic. For LEX-capable traffic, there are three possible codepoints: The FNE codepoint is set by the host when feedback on the path has not yet been established, and therefore there is no congestion control loop. This applies to the first packet of a flow, such as TCP SYN packets, or the first packet after a long idle time, such as keep-alives. An important distinction is that FNE marks the beginning of a "flowlet" [START_REF] Sinha | Harnessing TCP's burstiness with flowlet switching[END_REF], rather than a flow. We define flowlets as a burst of packets which the sender does not wish to be reordered. As such, it is the end-hosts decision on how and when to divide traffic into flowlets. While a flow is a transport association between two endpoints, a flowlet is a sequence of packets which is expected to follow the same path. As an example, an IMAP connection may remain open several hours, but is composed of several distinct flowlets each time a client requests data from the server. Operating on flowlets rather than flows allows networks to balance traffic at a finer granularity and in a transport agnostic manner.

The remaining two codepoints, LECT and LEx in table 1, are used to signal path loss. By default, traffic is marked as being Loss Exposure capable, and for every loss experienced by a host, the ensuing packet is marked with the Loss Experienced codepoint. In reliable transport protocols such as TCP this corresponds to marking every retransmitted packet accordingly, but can also be applied to non-reliable transport protocols with some form of feedback on loss, such as DCCP [START_REF] Kohler | Designing dccp: Congestion control without reliability[END_REF].

Path Re-Feedback

With LEX, hosts provide information on both path loss and flowlet start at the network layer. We now focus on how edge networks specifically, which are naturally multi-homed, can reflect path diversity back to hosts.

In PREF (Path RE-Feedback) the network selects a preferred outgoing path for each incoming FNE packet (fig. 1(a)). Upon receiving the first packet of a flowlet, the host performs a reverse lookup on the source address (step 1) and selects a path according to the perceived performance [START_REF] Wang | Explicit routing algorithms for internet traffic engineering[END_REF]. The router then associates the chosen path identifier to the packet and forwards the packet toward the host (3).

The treatment of outbound traffic by PREFLEX is illustrated in figure 1(b). The host, having received indication of the preferred path, tags all traffic deemed sensitive to reordering with the given path identifier. As the PREFLEX aware router receives this marked traffic it updates statistics associated to path, aggregating loss for each destination prefix (4). It then discards the path identifier (5) and forwards traffic along the appropriate path [START_REF] Wang | An overview of routing optimization for internet traffic engineering[END_REF]. The resulting architecture provides many benefits. The balancing is both transport agnostic and allows flow state to be kept to a minimum, requiring policing at the edges only if congestion accountability is required. Additionally, path selection is receiver driven, aligning the stakeholder who can decide when to issue FNE packets with the stakeholder who benefits the most. The key to path selection is the information provided by the sender (point 7), which allows the network to calculate the percentage of path loss. We assume for the entirety of this paper that each flow follows a single path and that a host does not override the path selected by its network, although neither is strictly necessary. The implications of both assumptions being broken and the incentives involved are briefly reviewed in [START_REF] Araújo | A mutualistic resource pooling architecture. Third Workshop on Re-Architecting the Internet (Re-Arch)[END_REF].

Balancing congestion

While PREFLEX provides an architecture within which transport and network layers exchange relevant information, it does not yet define how networks select outgoing paths. In this section we present a solution for balancing traffic according to expected congestion which works in a wide variety of network conditions.

Model

Consider LEX-capable traffic, that is explicitly marked as either being retransmitted or non-retransmitted, from a single origin prefix to a single destination prefix, with a number of possible paths and within a single time period. Let N be the number of paths (numbered 1, . . . , N ). Let T i be the number of bytes sent down path i for the previous time period. Let R i be the number of bytes marked as retransmissions down path i for the previous time period. Let R = ∑ i R i and T = ∑ i T i . While R i does not strictly represent the number of lost bytes, the ratio of R i /T i should be a good approximation of the loss rate within period i. A starting assumption is that it is desirable to equalise the proportion of lost bytes on all interfaces -that is make R i /T i equal for all i -and by doing so loss is balanced.

The loss rate ρ i = R i /T i is an unknown function of T i and B i the bandwidth of the link. It is, however, likely that the loss rate is increasing (or at least non-decreasing) with T i . Similarly, the loss rate is decreasing (or at least nonincreasing) with the unknown B i . Assume then that whatever the true function, for a small region around the current values of T i and B i then it is locally linear

ρ i = k i T i /B i
where k i is an unknown constant. Substituting gives

B i /k i = T 2 i /R i . ( 1
)
Now consider the next time period. Use the dash notation for the same quantities in the next time period. In typical time periods E [T ′ ] = E [T ] (since, for example, if the next time period on average had more traffic, the overall amount of traffic would be growing -while this is true in the year-on-year setting, this effect is negligible in the time scale discussed here). Now

ρ ′ i = R ′ i /T ′ i = kT ′ i /B ′ i . Choose the T ′ i to make all R ′ i /T ′ i = C (hence all equal) where C is some unknown constant. Therefore T ′ i = CB ′ i /k ′ i but if this is still near our locally linear region then B ′ i /k ′ i ≃ B i /k i and B i /k i is determined by (1) hence the predicted distribution is T ′ i = CT 2 i /R i . Now it is necessary to calculate C by summing over i. T = C ∑ i T 2 i /R i and hence C = T / ∑ i T 2 i /R i .
This gives the final answer:

T ′ i = T T 2 i R i ∑ j (T 2 j /R j ) . ( 2
)
There is, of course, a problem when R i = 0. Because of the assumption that the traffic is assigned in inverse proportion to loss rate then a branch with no loss would naturally have all the traffic assigned to it. To correct this, we increment R i for each path by one maximum segment size (MSS). This problem will be further discussed in subsequent sections.

Understanding the design space

Because only local linearity is assumed then large adjustments of the traffic split are likely to cause problems. It is also useful to send a small amount of probe traffic down each route even if the loss rate is high [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF]. In the absence of other information (for example when there is no loss) it is useful to assign traffic according to the current traffic throughput split. Therefore there are three tendencies to be accounted for, the loss-equalisation tendency from (2), the conservative tendency to keep the traffic split the same as the throughput split in the previous period and the equalisation tendency to keep the traffic equally split on all interfaces. Call the traffic split assigned to path i by each of these schemes T (E) i , T (C) i and T (L) i where E, C and L stand for "equal", "conservative" and "loss-driven".

Then our final distribution of traffic across all links is:

T ′ i = β E T ′ (E) i + β C T ′ (C) i + β L T ′ (L) i , where the β • are user set parameters in (0, 1) such that β E + β C + β L = 1. Now T ′ (C) i = T i and T ′ (E) i = T /N
where N is the number of interfaces. This gives a first equation for the desired flow split f ′ i , which represents the probability with which path i will be assigned to a new flow:

f ′ i = T ′ i T = β E 1 N + β C T i T + β L T 2 i R i ∑ j (T 2 j /R j ) . ( 3
)
While (3) describes a very broad design space, we provide some intuition on how each component acts through a simple example, which is described in full in section 4.1. Consider a network balancing traffic to a given prefix between two paths with equal bottleneck capacity L 1 = L 2 = 120Mbps. For the duration of the experiment, a source sends traffic according to the same distribution. At t = 300s, cross-traffic is generated towards client C through L 1 . At t = 600s, a greater quantity cross-traffic is generated towards client C through L 2 . The results for this example are shown in figure 2 in four different guises, and in each case we show the throughput, loss rate and the proportion of flows assigned to each path as computed by the PREFLEX balancer.

We first investigate the effect of equalisation, which is necessary to ensure all paths are continually probed. Equalisation alone however leads to an inefficient use of the network if there is a mismatch in path capacity, as is clearly visible in figure 2(a) as congestion arises on either link. Such behaviour arises in traditional traffic engineering, which resorts to equalising traffic weighted by a local link's capacity. Where a bottleneck is remote and distinct however, such behaviour will lead traffic across all links to be roughly bound by the capacity of the slowest path, as can be seen between t = 300s and t = 600s where throughput over the first path is dragged down by congestion on a second path.

Figure 2(b) and 2(c) on the other hand show distinctive behaviour when using a solely conservative or solely loss-driven approach. Predictably for small values of loss the loss-driven approach overreacts and flaps between either path. While the net effect of these oscillations does not result in significant losses, a conservative approach lends itself more naturally to situations where loss is too small to provide a reliable indicator on path quality. Once loss becomes significant however a conservative approach is unable to drive traffic in order to balance loss across both paths. More worryingly, a pure conservative approach demonstrates the wrong dynamics, as highlighted between t = 250s and t = 300s. Despite being saturated, the balancer continues to push more traffic towards path 1 while the second path remains under-utilized, dropping its throughput further.

Note that in figure 2 the conservative approach obtains higher throughput than its loss-driven counterpart once loss settles in. While this may seem advantageous, in reality we shall show that this behaviour is detrimental to the system as a whole and only by balancing loss can social welfare be optimized [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF].

Balancing between conservative and loss-driven

We wish to tune PREFLEX to balance between conservative and loss-driven modes for differing regimes of loss. Equalisation is required in some measure as every path must attract some traffic if it is not to fall out of use ([15], remark 2). If this is not the case, a path with relatively high loss will never be probed to determine whether it has improved. The remaining two components must be adjusted to be able to respond adequately to loss while not being overly sensitive to statistically insignificant fluctuations in loss. We define γ to replace both β C and β L in (3) and adjust between conservative and loss-driven modes:

f ′ i = β E 1 N + (1 -β E ) ( γ T i T + (1 -γ) T 2 i R i ∑ j (T 2 j /R j ) ) (4)
As a result, β E may now vary between [0, 1]. A simple but effective value for γ is to define a minimum average loss µ min below which we do not react to loss, and react increasingly as the average loss µ becomes more significant:

γ = { µmin µ , if µ > µ min 1, if µ ≤ µ min (5)
This completes the PREFLEX balancer, as shown in figure 2(d). The evolution of γ for the example shown in figure 2(d) is shown in figure 3(left). The value of µ min was set to 0.005.

Tuning update interval

Another issue is how often to update the flow split considering the sparseness of loss. Assume that for a given prefix packet loss is measured over a given time period τ . It would be useful to tune this τ per prefix in order that the loss estimate was "accurate". If τ is short then only a very small number of packets will be lost. On the other hand, if τ is long then the control system will be unable to react quickly to changes. The idea is to set τ sufficiently small that an accurate measure of loss can be obtained. It is useful therefore, to have a rough estimate of a time period over which it is necessary to measure in order that estimates of loss are accurate to a given degree. Because this time period of measurement is per prefix, this must to some extent take account of how important a given measurement is to the system as a whole (for example, not slowing down measurements because one route with a tiny amount of traffic has an inaccurate measurement). This will be achieved with the concept of a weighted coefficient of variation. Let t i be the number of packets transmitted down path i in the time period τ and let l i be the number of packets which were lost in this time period. (To prevent divide by zero issue set l i = 1 if no packets are lost).

Let p i be the probability that a given packet is lost on path i and assume that packet loss is a Bernoulli process. An unbiased estimate of p i is pi = l i /t i (it is important to what follows that pi is only an estimate of p i by "chance" more or fewer packets may have been lost). If packet loss is Bernoulli then l i has a binomial distribution and its variance σ 2 is given by t i p(1 -p). The coefficient of variation (CV), is a dimensionless measure given by the standard deviation over the mean c v = σ/µ. Keeping the coefficient of variation within some bound δ is a measure of the amount by which an estimate is likely to vary from the true mean. (Note, however, that this is not technically a confidence interval.)

For the number of lost packets on a given prefix i the estimated CV is ĉv (i) = √ t i pi (1 -pi )/t i pi . Let r i be the rate of packet arrival per unit time on i giving t i = r i τ . Define W the CV weighted by transmitted packets over the prefix as W = ∑ i t i /t ĉv (i) where t = ∑ i t i and this expands as

W = ∑ i t i t √ (1 -pi ) r i τ .
The "accuracy" of the measurement of p i is determined by the accuracy of l i and hence, for the prefix as a whole by the CV W . The aim now is to pick the time period for the next measurement τ ′ such that W ≤ δ for some δ. Assuming that the loss rates and traffic rates will be the same in the next time period will give a good indication of how to set τ ′ . Therefore for the next time period

δ ≥ W = 1 √ τ ′ ∑ i t i t √ (1 -pi ) r i .
This gives an estimated minimum time period to set for the next time period. In order to get weighted CV of packet loss (and hence loss rate) equal to or below δ the time period τ ′ is bounded by

τ ′ ≥ τ ( 1 δt ∑ i √ t i -l i ) 2 .
This equation gives the smallest value to set the time period of measurement to in order that the weighted coefficient of variation of the loss measurement is a given δ.

While a number of simplifying assumptions have been made, such as modelling loss as Bernoulli, the time scale choice is not a critical system parameter so long as it provides "good enough" estimates of loss. The evolution of τ ′ for the example in figure 2(d) is plotted in figure 3. As throughput decreases, the time inbetween updates is inflated to adjust to the lower occurrence of loss events.

Performance Analysis

We evaluate PREFLEX through simulation in ns-3 [16]. Since PREFLEX balances traffic using loss rather than load, there is a need to emulate the end-to-end behaviour of traffic. This proves more challenging than analysis of existing traffic engineering proposals which typically only focus on adjusting load, since we wish to verify the impact of PREFLEX on end-user metrics.

Methodology

For all simulations we will use the topology displayed in figure 4. The topology links a client domain C to a server domain S through N paths with equal bottlenecks L i , and total bandwidth B = ∑ L i . While a domain is represented as a single entity in figure 4, each domain is composed by a traffic generator connected to a router. Client C generates G simultaneous HTTP-like requests (or "gets") from S according to a specified distribution, described at the end of this section. As traffic flows from S to C, the router within S is responsible for balancing traffic over all available paths. Across simulations, as the number of paths increases, total bandwidth B and the number of simultaneous requests G is fixed. In this manner we wish to analyze how PREFLEX balances traffic as the granularity with which it can split traffic becomes coarser.

Since we are interested in evaluating how PREFLEX shifts traffic in response to loss, we introduce additional "dummy" servers D i which are connected to C through a single path. We partition the total simulation time T into N + 2 intervals starting on s i , in which s 0 and s N +1 have no traffic to D i . Starting at time s i , client C generates g i requests to D i according to the same distribution as used to server S. All requests to D i end at time s N +1 . Equation ( 6) sets the start time s i for requests to D i as a function of total simulation time T and number of paths N . Likewise, equation [START_REF] Wischik | The resource pooling principle[END_REF] sets the number of simultaneous requests g i to D i as a function of G, the total number of requests to S, and N .

s i = T i N + 2 ( 6
)
θ i = 1 N +1-i ∑ 1 N +1-i , g i = Gθ i . ( 7
)
Figure 5 illustrates the number of simultaneous gets from C to D i for N = 2 (used in the example shown in figure 2) and N = 4. Generating cross-traffic in this manner serves two purposes. Firstly, ∑ g i = G, so independently of the number of concurrent paths, the maximum load in the system is 2G. However, as the number of paths increases, the fluctuation in load for each path becomes smaller, and so we will stress the sensitivity with which PREFLEX balances traffic. Secondly, the number of requests for each D i over time is the same. Over timescale T , equalisation appears to be an acceptable strategy, however within each interval we will show it performs poorly achieve consistent behaviour. This is a fundamental limitation of offline traffic engineering, which is calculated over very long timescales and is unable to adapt as traffic routinely shifts. We now specify the settings common to all simulations, including those previously shown in figure 2. Total simulation time T is set to 1200 seconds, while total bandwidth B is fixed at 240Mbps. The number of requests G sent from C to S is set to 240. Upon completing, a request is respawned after an idle period following an exponential distribution with a 15s mean. Transfer size follows a Weibull distribution with an average value of 2MB. These values attempt to reflect traffic to a single prefix with a file size that mimics the small but bursty nature of web traffic, which does not lend itself to being balanced by the endhost. PREFLEX is configured with β E = 0.05, µ min = 0.01/N and δ = 0.005.

Varying bottleneck distribution

We start by examining the case where all bottlenecks share the same bandwidth, L i = B/N , and compare PREFLEX to equalisation, which mimics traffic engineering techniques based on hashing flow tuples and assigning them to a path. The goodput, calculated as the total data transfered to client C by flows completed within T , is shown for both equalisation and PREFLEX methods in figure 6. While both saturate most available bandwidth, equalisation leads to disproportionate distribution of goodput amongst competing traffic. As loss is not equalised over all paths, the amount of goodput achieved by servers D i differs despite demand being similar.

Equalisation, even when weighted according to local link capacity, is often prone to remote bottlenecks. We investigate the effect of differing bottlenecks by repeating previous simulations with the same total bandwidth B, but with L i set proportionally to B in a similar manner to [START_REF] Wischik | The resource pooling principle[END_REF], that is Figure 6 shows the goodput as a proportion of total link bandwidth for the case where all links have equal bandwidth. We vary the number of links N , and for each case compare equalisation (as illustrated in 2(a)) and PREFLEX as the balancing methods used. The bulk of goodput originates from server S, which is the only domain to be connected to all links. If traffic is correctly balanced, we expect to see servers D 1-N generate the same amount of goodput.

L i = θ i B.
In this scenario, equalisation can be seen as the optimal static TE solution, yet both approaches bear similar performance. With no knowledge of topology, link bandwidth or expected traffic matrices, PREFLEX is able to adequately mimic the performance of the static TE solution for the case where such an approach is best suited.

Where bottleneck bandwidth is unequal however equalisation proves inadequate. Once again comparing goodput (figure 7) we highlight two significant shortcomings of equalisation which PREFLEX overcomes. Firstly, goodput for S drops as N increases. Unable to realize it is overloading a path, equalisation is reduced to sending traffic over each link at approximately the same rate as the most congested link. In contrast, PREFLEX detects congestion and adapts accordingly. Secondly, the incorrect distribution of traffic due to equalisation in S distorts the goodput of others servers. While in PREFLEX goodput from D 1-N is perfectly balanced, with equalisation traffic crossing the most congested links are directly affected by another domain's inability to distribute its traffic appropriately. It may seem unfair to judge equalisation for cases where there is a mismatch in link capacity, however this mismatch between link weight and path capacity arises regularly as operators continue to adjust traffic engineering according to local conditions, with little thought spared for the impact this may have further downstream. This impact is in turn perceived by users, who experience longer flow completion times, as shown in figure 8. In the equal bandwidth case the flow completion time is similar for both balancers. Where bandwidth differs however, PREFLEX outperforms equalisation and maintains a stable performance when balancing over all six paths. This shows that the algorithm scales well as the number of available paths increases.

Conclusions and further work

In this paper we have introduced congestion balancing using PREFLEX. PRE-FLEX uses packet marking to estimate and balance loss across multiple paths. It requires no per-flow state or significant changes at routers, is computationally simple to implement, and does not cause packet reordering.

PREFLEX has been implemented and evaluated in ns-3 for dynamic traffic scenarios where it balances traffic using different strategies which are weighted according to the network conditions it detects. In conditions where loss is deemed significant, PREFLEX balances congestion between paths. In the absence of sustained loss PREFLEX assigns traffic based on current throughput. By balancing between these strategies PREFLEX can operate in a variety of dynamic traffic settings and has been shown to perform as well as the ideal static traffic assignment bandwidths are equal. Where bandwidth asymmetry arises, PRE-FLEX successfully balances loss with no significant degradation of performance as both the number of paths and inherent complexity of balancing increases.

By readjusting traffic according to end-to-end metrics, PREFLEX is unique in proposing congestion, rather than just load, as an essential metric for traffic engineering and signals a novel approach in bridging the divide between traffic engineering and congestion control.

Fig. 1 .

 1 PREFLEX architecture.

Fig. 2 .

 2 Fig. 2. Simulation using PREFLEX to balance traffic over two paths. Each simulation demonstrates the dynamics of a single mode, except for (d) which balances between conservative and loss-driven components.

Fig. 3 .

 3 Fig. 3. Parameters γ (left) and τ ′ (right) as seen in in example in figure 2(d).

Fig. 4 .

 4 Fig. 4. Simulation topology

4 Fig. 5 .

 45 Fig. 5. Number of requests from C to cross traffic servers Di for N = 2 (left) and N = 4 (right)

Fig. 6 .

 6 Fig. 6. Goodput relative to B achieved by each server for equal capacity links.

Fig. 7 .

 7 Fig. 7. Goodput relative to B achieved by each server for different capacity links.

Fig. 8 .

 8 Fig. 8. Mean average flow completion time for equal and differing bottleneck links.

Table 1 .

 1 LEX markings.

	Codepoint Meaning
	Not-LECT Not Loss Exposure Capable Transport
	LECT Loss Exposure Capable Transport
	LEx	Loss Experienced
	FNE	Feedback Not Established


Haiyang Wang

Feng Wang

Jiangchuan Liu
email: jcliu@cs.sfu.ca

Enhancing Peer-to-Peer Traffic Locality Through Selective Tracker Blocking

Keywords: BitTorrent, Locality, Peer control, Tracker blocking

Peer-to-peer (P2P) applications, most notably BitTorrent (BT), are generating unprecedented traffic pressure to the Internet Service Providers (ISPs). To mitigate the costly inter-ISP traffic, P2P locality, which explores and promotes local peer connections, has been widely suggested. Unfortunately, existing proposals generally require that an ISP control the neighbor selection of most peers, which is often not practical in a real-world deployment given there are noncooperative trackers. In this paper, for the first time, we examine the characteristics and the impacts of these noncooperative trackers through real-world measurements. We find that tracker blocking has the potential to address this noncooperation problem, and help the ISPs to control more peers for traffic locality. Yet, how to guarantee torrents' availability at the same time remains a significant challenge for the ISPs. To this end, we model the tracker blocking problem coherently with torrent's availability, and address it through a novel selective tracker blocking algorithm, which iteratively improves traffic locality with a given availability threshold. Our trace-driven evaluation shows that our solution successfully reduces the cross-ISP traffic in the presence of noncooperative trackers and yet with minimal impact to torrents' availability.

Introduction

Peer-to-Peer (P2P) networking has emerged as a successful architecture for content sharing over the Internet. BitTorrent (BT), the most popular P2P application, has attracted attentions from network operators and researchers for its wide deployment. Bit-Torrent, however, also generates a huge amount of cross-ISP traffic. Since the ISPs typically pay their peering or higher-level ISPs for global connectivity, the traffic between different ISPs is costly and presents significant network engineering challenges.

In order to alleviate this cross-ISP traffic, P2P locality has been widely suggested. Different with caching or blocking the P2P traffic, this method explores the access of existing localities to reduce the long-haul traffic. It is well known that modifying the trackers [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF] is the one of the most efficient ways to deploy P2P locality. This method proposes to manipulate the neighbor selection of peers via a biased tracker deployment.

In particular, the biased trackers will select the majority, but not all, of the neighbors for the BT peers within the same ISP.

In this paper, we explore the problem that many trackers are not owned by the ISPs and thus can hardly be modified for traffic locality. We take a first step towards the characteristics and the impacts of these noncooperative trackers (the trackers that cannot be modified for locality) via extensive measurements. We show that the existence of noncooperative trackers will greatly reduce the efficiency of traffic locality. In particular, we show that an ISP will lose the control of 53% (67, 132 out of 126, 133) peers due to the existence of some Pirate Bay trackers 1The well known tracker blocking approach has the potential to address the problem. Yet, this approach will also reduce torrents' availability and unavoidably decay peers' downloading experience. Therefore, we discuss the main challenge in this design: "How to control the neighbor selection of more peers and minimize the impact to torrents' availability at the same time?". Fortunately, the great popularity of multiple tracker configuration [START_REF] Liu | Understanding Peer Distribution in Global Internet[END_REF] gives us the opportunity to minimize the impact to torrents' availability. We thus formulate the tracker blocking problem coherently with the torrents' availability under this scenario. The problem is then addressed through a novel selective tracker blocking algorithm, which iteratively improves traffic locality with a given availability threshold. Our evaluation shows that it can successfully reduce the cross-ISP traffic in the presence of noncooperative trackers and yet with minimal impact to torrents' availability.

The rest of this paper is organized as follows: In section 2, we illustrate the related works. We discuss the existence of noncooperative trackers and our motivation in section 3. In order to address the problem, we formalize the problem and proposed a selective tracker blocking approach in section 4, and Section 5 presents our trace-based evaluation. We further discuss some piratical issues in Section 6 and conclude the paper in Section 7.

Related Works

There have been numerous studies on the analysis, optimization, and implementation, 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 pioneer work of Karagiannis et al. [START_REF] Karagiannis | Should Internet Service Providers Fear Peer-Assisted Content Distribution?[END_REF]. For example, 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. Xie et al. [START_REF] Xie | P4p: Provider Portal for Applications[END_REF] 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. also proposed Ono, a BitTorrent extension that leverages a CDN infrastructure, which effectively locates peers that are close to each other. A recent study from Ren et al. [START_REF] Ren | TopBT: A Topology-aware and Infrastructure-independent BitTorrent Client[END_REF] also confirms the possible benefit of a topology-aware and infrastructure-independent BitTorrent protocol.

On the other hand, many studies also addressed some pitfalls of the locality mechanism. Piatek et al. [START_REF] Piatek | Pitfalls for ISP-friendly P2P Design[END_REF] shown that a "win-win" outcome is unlikely to obtain for all the ISPs during the locality; the reason is that reducing inter-domain traffic reduces costs for some ISPs, while it also reduces revenue for others. Cuevas et al. [START_REF] Cuevas | Deep Diving into BitTorrent Locality[END_REF] further investigated the maximum transit traffic reduction as well as the "win-win" boundaries across the ISPs. These studies indicate that the ISPs are more likely to be selfish during the locality deployment, especially given the considerable gain of traffic locality.

Our work extends these studies through an Internet-wide measurement. We show that the peer control is a very important issue to reduce the cross-ISP traffic. The existence of noncooperative trackers may greatly reduce the efficiency of traffic locality. Given by the popularity of multiple tracker configuration, we propose a selective tracker blocking approach that can effectively help the ISPs to control more traffic while minimizing the impact to the torrents' availability.

Motivation: Problem of Peer Control

To investigate the deployment of traffic locality, we conduct a measurement over 3month and collect the information for more than 9 million BT peers. Our measurement configuration and the raw dataset (including the torrents information) can be found at: http://netsg.cs.sfu.ca/n tracker.htm.

It is well known that the trackers play a very important rule for the deployment of traffic locality. Table 1 presents the site information of the Top-10 most popular trackers in our measurement. We can see that many of them are belonging to Pirate Bay and etc., which are involved in a series of lawsuits, as plaintiffs or as defendants. In terms of traffic locality, unless the copyrights and other related problems are well solved, we can hardly expect to organize these tracker sites together for traffic locality optimization. Therefore, we use the term noncooperative tracker to refer to them; intuitively, if the ISPs cannot modify these trackers, they will also fail to control the peers that managed by the trackers.

In order to quantify their impact in deployment, we investigate the tracker blocking problem in AS#3352 as an example. This is the most popular AS with 126, 133 peers in our measurement; these peers are distributed in 6, 065 torrents that managed by 384 trackers.

In this case study, we pick out a set of trackers that are managed by private organizations. In particular 4 trackers belong to Demonoid and 4 trackers belong to Pirate Bay. Except these noncooperative trackers, we assume that all other trackers have already been modified by the ISPs for traffic locality. Figure 1 shows the probability that the peers in AS#3352 will connect to the modified biased trackers (the probability that their traffic will be optimized). The detailed data can be found in Table 2. (where in Case A, all the trackers can be modified for traffic locality; Case B, 4 noncooperative trackers from Pirate Bay cannot be for traffic locality; and Case C, 8 noncooperative trackers from Pirate Bay and Demonoid cannot be for traffic locality).

We can see that in Figure 1(a) when 4 noncooperative trackers (from Pirate Bay) cannot be modified, only 60, 331 peers in this ISP will be optimized by traffic locality for sure. We find that, 53% peers (67, 132 out of 126, 133) will be affected by the noncooperative trackers; none of these peers will be optimized for sure and the peers will connect to the biased trackers with relatively low probability. Moreover, as shown in Figure 1(b), if more trackers are not willing to cooperate (8 in this case), the ISP will lose the control of more peers.

We can see that even a small number of noncooperative trackers can bring noticeable damage to the ISPs; a large number of noncooperative trackers many easily ruin the deployment of traffic locality. However, control the neighbor selection of numerous peers one by one is even more troublesome. It is thus important to see whether we can enhance the peer control for the ISPs.

Tracker Blocking Problem

Intuitively, the ISPs can prevent their peers to connect to these noncooperative trackers via tracker blocking. Yet, this approach will also reduce the torrents' availability and the experience of P2P users. In our study, we find that block all the noncooperative trackers will greatly reduce the availability of torrents (see detailed discussions in Section 5). Fortunately, the latest BitTorrent metainfo file can include multiple tracker sites stored in the announce-list section [START_REF]BitTorrent Multi-tracker Specification[END_REF]. In particular, unless we block all the trackers in torrents' announce-lists, their availability will not be affected.

In our measurement, we also record the announce-list of the torrents, pick out the cited trackers and then compute the number of trackers that have been used by the torrents. Figure 2 confirms that more than 80% torrents have specified at least two trackers for the load balance (or backup) purpose, and a few torrents even have announce-lists of several 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 that the multiple tracker configuration has been quickly recognized and deployed in the BitTorrent community. We thus formulate the tracker blocking problem coherently with the torrents' availability under the scenario of multiple tracker configuration.

Problem Formulation

We now give a formal description of the tracker blocking problem in BitTorrent networks. We use ℵ to denote all the ASes on the Internet, to denote the set of existing torrents and use to denote the set of trackers. We define three variables A, S and T ; A takes on values over the set of ASes a ∈ ℵ; S takes on values over the set of torrents ,and T takes on values over the set of trackers that managing the torrents. Based on the above components, two relationships can be learnt from the measurement: [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF] The relationship between S (torrents) and T (trackers); (2) The relationship

Fig. 2. Popularity of multiple tracker configuration

between A (ASes) and S (torrents). We use binary matrix R tor,tra to define the relationship between S and T , and this matrix is learnt directly from the metainfo (.torrent) files; each element of R tor,tra (s, t) is of a binary value, indicating whether torrent s includes tracker t in its metainfo file (1-Yes, 0-No). On the other hand, we use matrix R tor,as to refer to the frequency table of S and A. This matrix is learnt from the IP/AS information of the probed BT peers; each element R tor,as (s, a) is an integer which refers to the number of peers (in torrent s) that belong to AS a. The peers' AS information is learnt by the 'whois' command on the Linux system, and most replies are from 'whois.cymru.com'. A local view of R tor,as is shown in Figure 3.

For a given ISP x (generally includes n ASes A x = {a 1 , a2, ..., a n }, n ≥ 1) that managed by k trackers T x = {t 1 , t2, ..., t k }; We use the set T x modif ied to refer the trackers that are modified for traffic locality, set T x blocked to refer the trackers that are blocked by the ISPs, and set T x unchanged to refer the trackers that are unchanged (neither modified nor blocked) during the locality deployment. Note that in this definition, the set of noncooperative trackers

T x noncoop = T x blocked ∪ T x unchanged .
Note that when we decide to block a noncooperative tracker, this decision will bring ISPs certain benefits and costs. In particular, the benefit is that some peers will switch to their alterative trackers that can be modified for traffic locality; the cost, on the other hand, can be qualified by the number of peers that cannot find an alterative trackers and thus fail to connect to the BT networks. The tracker blocking problem is that for ISP x (with a known set of noncooperative trackers T x noncoop ), how to division the tracker set T x into three parts of T x blocked , T x unchanged , and T x modif ied . This division should maximize the total benefit; meanwhile, the torrents' availability (total number of peers that cannot connect to the BT networks due to the tracker unavailability) should also be bounded by a given threshold β; where β ∈ [0, 1] refers to the percentage of peers that become unavailable. We formulate this problem step by step as follows:

For any division, the peers in a given torrent (for example torrent s 1 ) will be optimized by the locality mechanism with the probability of:

P s1 = t∈Tx modif ied R tor,tra (s 1 , t)/ t∈Tx R tor,tra (s 1 , t) (1)
This probability is computed by the ratio of modified trackers and the total number of trackers that the torrent cite in its metainfo file. Therefore, a probability distribution of each torrents S can be given by P s = {P s1 , P s2 , ..., P si }. This distribution describes the probability that the peers(in each torrents) will connect to the bias trackers. On the other hand, for ISP x, the distribution of peer population across the torrents is given by:

D s = a∈Ax R tor,as (S, a) (2)
Based on these two distributions, we use a normalized expectation to qualify the total benefit. The tracker blocking problem is therefore to maximize:

E(x) = S (D s • P s )/ S D s (3) s.t. V (x) S D s ≥ β (4)
where V (x) = S [ a∈T * R tor,tra (S, t)]/k • D s indicating the total number of peers that can at least connect to one available tracker. T * = T x -T blocked x refers to the trackers that are not blocked. The physical meaning of E(x) is the average probability that the peers in ISP x will be optimized by the traffic locality; meanwhile, the constraint in eqn.4 helps us to bound the torrent availability during the tracker blocking.

Which Trackers Should be Blocked?

In this part, we will discuss the details of tracker blocking algorithm. It is easy to see that this problem can be transformed into a restricted napsack problem which known as NP complete. Note that in the real-world deployment, both R tor,tra and R tor,as cloud be dynamic (we will further discuss this impact in Section 5). Therefore, instead of finding an optimal solution, we are focusing on a more efficient algorithm for realworld implementations.

To this end, we design an algorithm that can improve the solution quality iteratively. As shown in , in each liberation, we compute the blocking benefits B and the costs H for all the unblocked noncooperative trackers (as discussed in eqn.3 and eqn.4). If the total cost is less than β, then we block the tracker with maximal W (W = B-H) in this liberation. After this blocking, we recompute the blocking benefits/costs (B and H) for the remaining trackers and goto next round. Otherwise, if the availability constraint was violated or all the noncooperative trackers are blocked, stop and exit. In next section, we will show that our solution can bring considerable benefits for the real-world ISPs.

Evaluation

In this section, we will evaluate the performance of our tracker blocking algorithm based on real trace. First, we will discuss the discuss the improvement of peer control for the ISPs. After that, we will further investigate the traffic saving as well as the possible degrading of peers' availability.

We evaluate the tracker blocking problem in a real ISP with multiple ASes. This ISP includes AS#3352, AS#6461, AS#3301, AS#3243, and AS#2847 with 402, 496 peers that managed by 428 trackers. Among all these trackers, we find 104 noncooperative trackers that can hardly cooperate with the ISPs (based on the hosting of copyright contents). We set β = 90% in this simulation, which indicates the ISP need to guarantee the access of 90% peers to BT networks. Based on the our algorithm, 10 noncooperative trackers are selected (blocked) in this ISP. Following two cases are discussed to evaluate its performance: Case #1. All the noncooperative trackers are neither modified nor blocked by the ISPs; Case #2. A Algorithm Tracker Blocking() 1: while the tracker list is not empty and the total availability cost is equal 2: or less than β 3:

for ∀ tracker t ∈ T noncoop 4:

compute E of blocking this tracker based on eqn. 3 5: compute V of blocking this tracker based on eqn.4 6:

find the tracker with maximal W = B -H 7:

if the tracker is not checked and the total cost 8:

after blocking this tracker is equal or less than β 12: then 9:

remove this tracker from tracker list (this tracker is blocked) 10: update this information in R tor,tra and R tor,as . 12: else 13: mark this tracker as checked and goto 6 : 14: end if 15: end for 16: end while Fig. 4. The selective tracker blocking algorithm selective set of noncooperative tracker is blocked by the ISP while other noncooperative trackers are unchanged (and not blocked); Note that Case#2 is the proposed method; the comparison of these two cases indicates the benefit of our selective blocking approach.

Figure 5 shows the cooperation of these two cases. In particular, the E(x) values stress the gain is over 50% where the E(x) in Case#1 is 0.4422 and E(x) in Case#2 is 0.6809 (recall that this value refers to the probabilities that the peers will be optimized in each cases). In this figure, we can see that if we simply ignore these noncooperative trackers (Case#1), only 6.45% (25952 out of 402496) peers will be optimized for sure and most peers will be optimized with the probabilities no greater than 0.5. On the other hand, with our selective blocking approach, 38.22% (153833 out of 402496) peers will be optimized for sure. The detailed data of this figure can be found in Table 3.

We also compute the case when all the noncooperative trackers are blocked. In this case, only 28.18% (113, 419 out of 402, 496) peers are able to connect to the BT networks. This less than our β value which is set to 90%. The result indicates that the over-blocking of noncooperative trackers will greatly harm the users' experiences and can hardly be appreciated.

The improvement of peer control is encouraging especially considering the overhead of blocking 10 trackers. To further investigate the saved cross-ISP traffic, we perform another simulation using the discrete-event BitTorrent simulator developed by Stanford University [START_REF] Bt-Sim | [END_REF] as [START_REF] Bindal | Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[END_REF] did; we summary the key network settings as follows:

The network contains 13 ASes and 1, 600 BT peers, where the peers are managed by 80 logic trackers and 75 of them are noncooperative trackers. The peers are skewedly distributed among these trackers as we observed in our measurement. When one tracker is blocked, the peers will randomly switch to an alternative tracker as described in the standard BT protocol. Note that in this simulation, each AS from an individual ISP. These ISPs will all benefit from the tracker blocking approach, and we compute the overall inter-AS (ISP) traffic to quantify this benefit. For other detailed configurations, all peers inside the ISPs are modeled as nodes behind cable modem and DSl, 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 will leave the BT network forever as soon as they finish downloading. We run multiple simulations to average the randomness and the results are shown in Figure 6 and Figure 7 with different β values. Figure 6 present the traffic saving of our algorithm. We can see that when no trackers are blocked with β = 1.0 (only 5 out of 80 trackers are modified for traffic locality), the ratio of cross-ISP traffic is around 90%. As we decrease the β value and block more noncooperative trackers, more peers will switch to the modified trackers, and the cross-ISP traffic will noticeable decreased. Compare to Figure 7, we can see that the blocking of 20 trackers (β changed from 0.93 to 0.84) will generally reduce the 17% traffic across the ISPs. It is also worth noting that when we block more trackers, the peers' availability is linearly decreasing. However, the cross-ISP traffic is more slowly decreasing with increased standard deviation. This result also indicates the inefficiency of over-blocking (see details in Table 4).

Further Discussions

This paper takes a first step towards the tracker blocking problem for the traffic locality. There are still many piratical issues that can be further explored.

First, the trackers are dynamic, which can be considered in the locality deployment. We are currently probing the availability of more than 700 trackers (we have already obtained the data for over 8 months), as shown in Figure 8. We cluster the trackers in three classes: 1) Highly available trackers (with the total online time more than 7 months); 2. Normally available trackers (with the total online time more than 0 and less than 7 months); 3. Not available trackers, as shown in Figure 9. We can see that more than 30% trackers have very good availability. These trackers are more eligible to be blocked (if noncooperative) during the locality deployment. We are currently trying to add this information and further improve our model. Second, our model is based on the measurement information of R tor,tra and R tor,as . Therefore, an inefficient dataset may potentially reduce the benefit. Our ongoing work is to use the relationship between ASes and trackers to enhance our model. Note that this relationship can be easily computed/probed by the ISPs. We find that this relationship is quite consistent over time. More importantly, it can also be used to infer R tor,tra and R tor,as when either of which is missing.

Conclusions

In this paper, we studied the deployment traffic locality when some tracker sites cannot be modified by the ISPs. Due to the existence of these noncooperative trackers, the ISPs will lose the control of many peers and unavoidably reduce the efficiency of traffic locality. We show that a selective tracker blocking approach can well address this problem, and thus formulate the tracker blocking problem coherently with the torrents' availability under the scenario of multiple tracker configuration. Our trace-based evaluation show that this solution successfully reduces the cross-ISP traffic in the presence of noncooperative trackers and yet with minimal impact to torrents' availability.

Fig. 1 .

 1 Fig. 1. The impact of noncooperative trackers

Fig. 3 .

 3 Fig. 3. Local view of matrix R tor,as

Fig. 5 .

 5 Fig. 5. Improvement of peer control

Fig. 6 .Fig. 7 .

 67 Fig. 6. Improvement of traffic locality

Fig. 8 .Fig. 9 .

 89 Fig. 8. # of available trackers over time

Table 1 .

 1 Top-10 Most Popular Trackers

	Rank	Peers	Torrents *	Tracker Sites (URLs)
	1	607987	19915	open.tracker.thepiratebay.org
	2	593205	16724	trackeri.rarbg.com
	3	560580	23386	denis.stalker.h3q.com
	4	509140	15308	tpb.tracker.thepiratebay.org
	5	504173	12117	vtv.tracker.thepiratebay.org
	6	442708	12821	vip.tracker.thepiratebay.org
	7	414095	10019	eztv.tracker.prq.to
	8	262991	6079	tracker.prq.to
	9	184843	3016	tk2.greedland.net
	10	142220	3114	www.sumotracker.org
	* Note that the torrent level popularity is obtained from the metainfo files
	which can include multiple trackers.

Table 2 .

 2 Number of peers that will choose the modified biased trackers in certain probability (In AS#3352)

	Pr	0.1-0.2	0.3-0.4	0.5-0.6	0.7-0.8	0.9-1.0
	Case A	0	0	0	0	126133
	Case B	2360	7317	28685	23279	60331
	Case C	11751	19672	32448	7469	47347

Table 3 .

 3 Number of peers that will choose the modified biased trackers in certain probability

	Pr	0.1-0.2	0.3-0.4	0.5-0.6	0.7-0.8	0.9-1.0
	Case1	30494	82496	137533	24100	52952
	Case2	20151	51943	108906	52819	154257

Table 4 .

 4 Facts of views (in Figure6)

	Cross traffic	β = 0.9	β = 0.8	β = 0.7	β = 0.6
	Max	0.887	0.837	0.784	0.738
	Min	0.809	0.627	0.441	0.341
	Median	0.833	0.677	0.456	0.368
	Mean	0.861	0.719	0.566	0.491
	Std	0.045	0.072	0.189	0.212

The Pirate Bay is a Swedish website that indexes BitTorrent contents. It has been involved in a number of lawsuits generally due to the violation of copyright laws. Meanwhile, the ISPs can hardly modify the Pirate Bay trackers for traffic locality.


Eleni Agiatzidou
email: agiatzidou@aueb.gr

George D Stamoulis
email: gstamoul@aueb.gr

Collaboration between ISPs for Efficient Overlay Traffic Management

Keywords: Overlay Applications, Peering Agreements, Peer-to-Peer Networks, Traffic Management

As peer-to-peer (P2P) applications (e.g. BitTorrent) impose high costs to Internet Service Providers (ISPs) due to the large volumes of interdomain traffic generated, extensive research work has been done concerning locality-awareness approaches. Although such approaches are based on properties of the physical network topology, they take very little consideration of the real business relationships between ISPs (peering and transit agreements) as well as of the heterogeneous peer distributions among ISPs. In this paper, we propose an innovative way to exploit the business relationships between ISPs of either the same or different Tiers, by introducing new collaborative approaches for overlay traffic management on top of the locality-awareness ones. By means of simulations, we show that win-win situation (reduced transit traffic for ISPs and better performance for users) can mostly be achieved under certain complicated collaborative approaches. Also we show how the collaboration between the upper Tier ISPs can affect favorably both the inter-domain traffic in the transit links, where charging applies, and the performance of their customers ISPs and how the latter can benefit from their collaboration with the transit ISPs.

Introduction

Peer-to-peer (P2P) applications, particularly those based on BitTorrent, have become very popular recently, since they allow the users to distribute collaboratively large volumes of content, which account for 43% to 57% of the Internet traffic depending on the geographic area [START_REF] Ipoque | Internet Study[END_REF]. Despite the advantages that the ISPs and the users gained through the increasing demand for such applications, a significant problem has arisen for the ISPs. Indeed, overlay applications exchange their traffic through logical overlay connections, which are usually agnostic to the physical structure of the Internet. This imposes traffic engineering difficulties and high costs to the ISPs due to the inter-domain traffic exchanged. Extensive research work has been carried out aiming at the reduction of the transit inter-domain traffic and, consequently, of the associated costs of the ISPs. This work led to overlay traffic management techniques, referred to as locality-awareness, which are successful from the ISP's point of view since they increase the level of locality of the traffic. In Section 2, we present an overview of such approaches. In this paper though, we build on the approach developed by EU-funded project SmoothIT [START_REF]SmoothIT Simple Economic Management Approaches of Overlay Traffic in Heterogeneous Internet Topologies[END_REF], which deals with the incentive-based management of overlay traffic so that this is done beneficially for both the ISP (wrt inter-domain traffic and charges) and users (wrt overlay performance). In most of the locality-awareness approaches (including that of SmoothIT), ISPs provide information about the physical topology to the overlay application clients, thus helping peers to choose their overlay neighbors in a more localized way. However, neither this approach nor the other ones overviewed in Section 2 distinguish non-local peers according to the business relationships [START_REF] Chang | To peer or not to peer: Model the evolution of the Internet's AS-level topology[END_REF] among the ISPs. In our opinion, such a distinction is very important, because it may lead to a significant reduction of the transit inter-domain traffic where charging applies, as will be seen in our work.

The specific Locality-Aware BitTorrent peer selection algorithm employed by SmoothIT is based on a combination of Biased Neighbor Selection (BNS) and Biased Unchoking (BU), as presented in [START_REF] Bindal | Improving traffic locality in bittorrent via biased neighbor selection[END_REF] and [START_REF] Oechsner | Pushing performance of Biased Neighbor Selection through Biased Unchoking[END_REF], and has already been evaluated successfully for a wide variety of simulated scenarios; see also Section 3. We introduce an innovative variation to this that employs the notion of interconnection agreements in the ranking method of the peers that is used by BNS and BU. Our objective is to investigate the benefits of employing this information for the ISPs and the peers. Moreover, we introduce and evaluate an innovative traffic management approach on top of the locality-awareness techniques that also exploits the business relationships though in a different way. This approach referred to as Splitting of Chunks, aims to avoid the download of redundant (duplicate) content via the costly inter-domain links, while allowing more traffic to be exchanged through the peering links. This approach requires detailed coordination between the collaborating ISPs at the level of swarm, which can be considered as not realistic for practical cases and possibly not acceptable by users. Nevertheless, Splitting of Chunks represents the "ultimate" way for ISPs to collaborate in order to reduce traffic redundancy in the charged transit links, which motivates our studying it. We present the specification of the BNS-BU algorithms that are based on the agreements of the ISPs (Collaborative BNS-BU approaches) and the Splitting of Chunks approach and we compare their performance to the standard BNS-BU algorithm. Note that the practical application of our proposed approaches does not involve any additional overhead compared to SmoothIT BNS-BU, except for a modification in the information already exchanged between the overlay client and the ISP server. To the best of our knowledge, there is no published work up to date that takes into account interconnection agreements in locality promotion or employs some other collaboration between ISPs.

The remainder of this paper is organized as follows: In the next section, we overview approaches for locality promotion proposed in the literature, while in Section 3 we describe briefly the BNS and BU algorithms. In Section 4, we present the simulation setup used for our experimental evaluation. Sections 5 and 6 follow the same structure; the first part presents the analysis of the Collaborative BNS-BU approaches and Splitting of Chunks mechanism respectively, while the second part is dedicated to the simulation results of the aforementioned mechanism. Finally in Section 7 we present our conclusions and future work.

Extensive research work has already been done in the literature on the promotion of locality in P2P networks. In this section we present an overview of proposals for locality awareness mechanisms as well as research work that indicates arising issues resulted from these mechanisms that provided an extra motivation for our work.

Aggrawal et al. propose an Oracle service hosted by the ISPs in order for them to cooperate with P2P users [START_REF] Aggrarwal | Can ISPs and P2P users cooperate for improved performance?[END_REF]. The Oracle ranks a list of potential neighbors based on locality (same AS) and proximity (AS hops distance). The evaluation results showed that the properties of the overlay topologies, such as small diameter, small mean path lengths and node degree are not affected by the use of the oracle service, while at the same time the network locality increases. A similar approach where again an overlay entity called iTracker communicates either with the peers or with application trackers providing them information about the underlay, is P4P project [START_REF] Xie | A: P4p: provider portal for applications[END_REF]. The simulations in PlanetLab and real networks showed a reduction in transit inter-domain traffic and download times as well. Bindal et al. [START_REF] Bindal | Improving traffic locality in bittorrent via biased neighbor selection[END_REF] in their Biased Neighbor Selection (BNS) algorithm presume that a peer can be provided by a biased list of peers (in order to connect to). The simulation results over 14 different ASes showed that the transit inter-domain traffic is reduced significantly, while the download times of the peers are not influenced much. Oechsner et al. propose in [START_REF] Oechsner | Pushing performance of Biased Neighbor Selection through Biased Unchoking[END_REF] a new algorithm, referred to as Biased Unchoking (BU) and they combine it with the aforementioned BNS algorithm (BNS-BU). BU influences, based on the ranked list, the optimistic unchoking algorithm of a peer that indicates to which neighbor to upload. This list is received from the tracker, unlike SmoothIT and our approaches, where it is received from an ISP-owned overlay server; see Section 3. The experimental evaluation and comparison of plain BitTorrent, BNS, BU and BNS-BU in [START_REF] Oechsner | Pushing performance of Biased Neighbor Selection through Biased Unchoking[END_REF] showed that the two complementary mechanisms should be used together in order to achieve better performance in terms of transit inter-domain traffic while the performance of the peers remains unaffected. A different implementation of the same idea is presented by Choffnes and Bustamante in [START_REF] Choffnes | Taming the Torrent: A Practical Approach to Reducing Cross-ISP Traffic in Peer-to-Peer Systems[END_REF]. Biased neighbor selection is based on the information that is collected from DNS lookups on popular CDNs names. The similarity of the lookups of two peers determines their level of proximity.

In [START_REF] Piatek | Pitfalls for ISP-friendly P2P design[END_REF], Piatek et al. present three pitfalls to ISP-friendly P2P design. One of them concerns the conflicting interest that different Tier ISPs have while inter-domain traffic is reduced causing less costs for some and less revenues for others . Wang et al. in [START_REF] Wang | On the locality of BitTorrent-based video file swarming[END_REF] examine the different contents and peer properties in regards to the locality issues. They conclude that the peers belonging to a few large AS clusters are more eligible to be affected by a locality mechanism; thus, a selective locality mechanism is more promising to optimize the overhead and the robustness of BitTorrent. Lehrieder et al. in [START_REF] Lehrieder | Can P2P-Users Benefit from Locality-Awareness?[END_REF] investigate the way BNS and BU mechanisms affect the performance of the users. For scenarios with homogeneous peer distributions and all peers having the same access speed a win-no lose situation arises, i.e. reduction of transit inter-domain trafficno deterioration of performance of users. Changing the percentage of local peers used for either BNS or BU, they argue that the actual impact for a specific peer depends heavily on that percentage as well as the topology used.

Locality-aware mechanisms: BNS-BU

In this section we briefly present the two main approaches of locality-awareness, Biased Neighbor Selection (BNS) and Biased Unchoking (BU) [START_REF] Bindal | Improving traffic locality in bittorrent via biased neighbor selection[END_REF], [START_REF] Oechsner | Pushing performance of Biased Neighbor Selection through Biased Unchoking[END_REF] since we build our collaborative mechanisms on top of their combination (referred to as BNS-BU), as implemented by SmoothIT [START_REF]SmoothIT Simple Economic Management Approaches of Overlay Traffic in Heterogeneous Internet Topologies[END_REF]. Both approaches are based on the existence of an overlay server that resides in each AS and accepts from peers, lists with remote peers acquired from a tracker. Its main role is to rank the remote peers in the list according to locality (same AS with the requesting peer, i.e. local ones), peering agreements and proximity (AS hops away from requesting peer's AS) [START_REF]SmoothIT Simple Economic Management Approaches of Overlay Traffic in Heterogeneous Internet Topologies[END_REF]. Thus, the overlay server maps a specific value to every local peer, forming the highest or 1 st -value group and another value to every peer that belongs to the peering ASes, forming the 2 nd -value group. The rest of the peers are ranked according to the proximity of their ASes based on BGP hops. More AS hops mean that the peers belong to smaller-value groups.

BNS enables a peer that had already received a ranked list from the overlay server to connect to the most preferable peers. In our implementation, as also implemented in [START_REF] Oechsner | Pushing performance of Biased Neighbor Selection through Biased Unchoking[END_REF], 90% of a peer's neighbors are chosen based on their ranking. The peer starts connections to the 1 st -value group until it reaches the threshold of 90%. If the 1 stvalue group contains fewer peers than those needed to reach 90%, then the peer iteratively connects to peers from the next value group, i.e. from the peering AS or 2 nd -value group, then from the ASes one hop away etc. After reaching 90% of the connections, it randomly chooses the remaining neighbors from the rest of the groups.

In BU a peer chooses to unchoke one of his interested (in the currently available chunks) neighbors that belong to the highest-value group, i.e. to the same AS according to the metrics that obtained from the ranked list. If there are no interested peers in this group, then the peer chooses randomly from the next one.

Simulation Setup

In this section we present the basic configuration of our simulations that we used to compare the BNS-BU mechanism with our variations that introduce collaboration between ISPs from the same or different Tiers and with Splitting of Chunks approach.

In Figure 1 we defined the topology for our simulations. Each AS is distinguished through an identification code, which consists of a number that indicates the Tier that this ISP belongs to, and a letter that distinguishes it from others of the same Tier. There are eight Tier 3, three Tier 2 and two Tier 1 ISPs. Tier 2 ISPs have twice as many peers as Tier 3 ones, a set up that realistically reflects Internet. To be able to show the function of the collaboration mechanisms we introduced five peering agreements (links) between ISPs of the same Tier. Furthermore each ISP contains an overlay entity that except for ranking the remote peers of a requesting peer is aware of the business relationships of the ISP and adjusts its policy to the various ranking approaches analyzed in the next session. Moreover, this server assists peers to select which part of the content will download from each peer in the Splitting of Chunks approach. This topology is rich and representative enough to motivate our mechanisms and better exploit their potential by employing the business relations among ISPs of two different Tiers; this would not have been possible with a topology comprising two Tiers only. At the same time the topology is simple enough for the results to be easy to analyze and comprehend. In our experiments we used the SmoothIT simulator, which is based on Protopeer [START_REF]Protopeer[END_REF]. In order to incorporate the approaches introduced in this paper, we extended the simulator accordingly. The peers are connected to the ASes with access speed equal to 16Mbps for download and 1Mbps for upload, roughly the average speed values of DSL lines today. The network delay among all peers is 10msec regardless their physical location. All inter-domain links have symmetrical capacities, while the access links of peers constitute the only bottlenecks in the network. All peers exchange a file whose size is 154.6MB. For simplicity reasons we simulate one single swarm for evaluating our mechanisms. Peers arrive in the swarm following a deterministic distribution. Every 30 and 60 sec Tier 2 and Tier 3 ISPs respectively acquire one more peer. Also, all peers after downloading the whole file, they seed it for 3 minutes before they exit the system. Thus, as measured during the simulations, the swarm contains about 100 to 200 peers on average, a typical size for mediumsized swarms, as reported in [START_REF] Hoßfeld | Measurement of BitTorrent swarms and their AS topologies[END_REF].

The main metrics of interest are the mean inter-domain traffic exchanged between ISPs 2a and 3a and between ISPs 1a and 2a, as well as the mean download times of the peers in 3a and 2a. The former is used to assess the savings for the ISPs, while the latter to assess the impact of the mechanism on the user performance. We calculated the mean values per minute for 10 runs of each experiment and the confidence intervals for a confidence level of 95%. The size of confidence intervals was below 6% of the corresponding mean value.

Collaborative BNS-BU approaches

Approach

Transit agreements between ISPs are used in order to provide connectivity to the rest of the Internet. Peering agreements on the other hand, help ISPs to reduce their transit inter-domain traffic and, therefore, the implied costs, which are comparatively greater than the cost of maintaining a peering link [START_REF] Wang | On the locality of BitTorrent-based video file swarming[END_REF]. In this paper we focus on transit and peering agreements between different or same Tier ISPs.

In this section we propose the modification of the BNS-BU approach in such a way that takes into consideration the business relationships of the ISPs in ranking the peers in a list upon such a request. To explain this better, let us assume that the overlay entity returns to the requesting peer a pair of values i.e. {remote peer IP address, remote peer group value} (a, g), one for each peer in the list. Thus, the requesting peer uses g to identify the group to which remote peer a belongs, as mentioned in Section 3. The overlay entity will map the highest g to local peers (relatively to the requesting peer), the second higher g to peers from the peering AS and then classifies the rest of the peers according to BGP hops; more hops away means smaller values. Nevertheless, if two ASes are the same number of hops away, this does not necessarily indicate that the exchange of traffic with each one of them will cost the same. For example, a peer in 2a will receive the same g value (thus, forming one group) for peers from 3c, 3d, and 2c. However, exchanging traffic with 3c and 3d is cheaper than exchanging traffic with 2c, since, as shown in Figure 1, 2a and 2b have a peering link with each other. Preferably the peer could connect to as many as possible peers from 3c and 3d before connecting to 2c. This knowledge that results from the business agreements of the ISPs, is not available explicitly to ISP 2a, but since 2a and 2b collaborate with each other, they can exchange the preference values (from where this knowledge is extracted) that the overlay entity of each ISP gives to other ASes. In such cases peer selection can be optimized using the knowledge regarding the business relationships among ISPs in order for groups to be formed differently. We propose two collaborative approaches that take advantage of this knowledge, referred to as Collaborative BNS-BU and Layered Collaborative BNS-BU.

Collaborative BNS-BU takes into consideration the business relationships of the ISPs in order to form the groups of peers differently from BNS-BU. In the 1 st -value group belong local peers or peers from the peering AS, thus forming a larger group than in BNS-BU. The 2 nd -value group consists of peers from the customer ASes of the ISPs. Larger groups were chosen in order to provide peers with more resources, boosting this way their performance. In case that ISPs 2a and 2b collaborate using this approach, their 1 st -value group consist of peers from 2a and 2b while the 2 nd -value group is formed by peers from the customer ASes, i.e. 3a, 3b, 3c, 3d. The rest of the groups are formed using AS hops. Tier 3 ISPs, when collaborate with each other cannot affect much the grouping since they know only their own business relationships as opposed to the Tiers above. Thus only the highest-value group of locals and peers from peering ASes is formed and the rest stay unaffected. On the other hand, if Tier 3 overlay entities collaborate with Tier 2 one, the 2 nd -value group of Tier 3 ISPs 3a and 3b consists of peers from 2a, 2b, 3c and 3d.

Layered Collaborative BNS-BU uses a slightly refined technique in order to form as many groups as possible according to the business relationships. This approach differs from the previous one in the number of groups. Thus, under this mechanism a peer first connects to all resources found locally before it chooses a peer from the next group, i.e. from the peering ISP. Thus, the first group, as formed in the Collaborative BNS-BU case, is split in two groups, exactly as in the plain-BNS-BU. The 2 nd -value group of the previous approach is split to multiple smaller groups according to BGP hops. Smaller groups are used in order to further promote proximity. Indeed, due to such small groups, a peer will connect to all of the peers in a 'closer' group before moving to the next one. As an example, a peer in ISP 2a would receive the following group of peers: 1 st group -local peers, 2 nd group -peers from 2b, 3 rd group -peers from customers of 2a (3a, 3b) and 4 th group -peers from the customers of 2b (3c, 3d).

The rest of the ASes are formed into groups according to the BGP hops. It is worth noticing that for Tier 3 ISPs this approach forms groups that are identical to the plain-BNS-BU groups unless cross-Tier collaboration exists (e.g. Tier 2-Tier 3).

Experimental Evaluation

In Table 1 we present the effect of the aforementioned approaches to the transit interdomain traffic (in MB/s) of 1a2a and 2a3a links, as well as to the download times (in min) that peers in ISPs 2a and 3a experience. Each column of the table corresponds to a different scenario; BNS-BU, Collaborative BNS-BU and Layered Collaborative BNS-BU. Each scenario is separated to multiple columns, each one corresponding to groups of simulations; for each group a different pair of ISPs runs the specific scenario. For each scenario the rest of the ISPs run BNS-BU since we consider that is in the interest of ISPs to run those two algorithms. For example, Collaborative BNS-BU Tier 2 means that ISPs 2a and 2b use the Collaborative BNS-BU approach while all other ISPs run BNS-BU. Collaborative BNS-BU Tier 3 means that Tier 3 ISPs 3a and 3b only use the specific approach. Tier 2 & Tier 3 refers to the case where 2a and 2b as well as their customers follow the specific approach. Each row comprises the mean values of a specific metric, i.e. the mean inter-domain traffic 1a2a, the mean inter-domain traffic 2a3a, and the mean download times in 2a and in 3a. 1, when only ISPs 2a and 2b run Collaborative BNS-BU (Collaborative BNS-BU Tier 2), they manage to reduce their transit inter-domain traffic by 26% essentially without affecting peers' performance, thus attaining a winno lose situation. Traffic between 2a and 3a and download times for peers in 3a are marginally affected (1.6% and 1.1% respectively). Larger download times for peers in 3a are caused by the use of BNS-BU mechanism. Thus, for Collaborative BNS-BU Tier 2 there is a win-no lose situation for ISPs in both Tiers (2a and 3a). For ISPs 3a and 3b, the transit inter-domain traffic is not significantly affected (Collaborative BNS-BU Tier 3); at the same time this has very little effect on peers' performance in both Tier ISPs and on the inter-domain traffic 1a2a. However, if ISPs 3a and 3b run Collaborative BNS-BU and 3c and 3d do so too, then Tier 2 ISPs 2a and 2b have a clear incentive to also run Collaborative BNS-BU. Indeed, this extra collaboration between them will improve the transit inter-domain traffic 1a2a by 44% and considerably improve the download times of peers in 2a (30.5%), (see column Collaborative BNS-BU Tier 2&3 in Table 1). Since in this case Tier 3 ISPs are indifferent in adopting the approach, ISP 2a can incite it to its customers by sharing its own benefits with them. Similar results are obtained from the implementation of the Layered Collaborative BNS-BU for Tier 2 ISPs and for Tier 2 & 3 ISPs, due to the large amount of resources from the local and the peering ISPs. However, download times deteriorate slightly more in this case, due to the extra constraints imposed by the finer layering. Thus, we conclude that especially large ISPs, such as Tier 2 ones, gain from deploying Collaborative algorithms for BNS-BU approaches due to fact that their peers can find larger amounts of resources locally, from their peering ISP and their customers ISPs; thus, inter-domain traffic exchanged through links for which the Tier 2 ISPs are charged can be reduced.

Splitting of Chunks

Approach

On top of the aforementioned mechanisms we develop an innovative traffic management approach, referred to as Splitting of Chunks. This mechanism is based on the collaboration of ISPs that have a peering agreement with each other; this provides them the opportunity to further collaborate in order to reduce the redundancy in the downloading content from non-local peers (or ISPs). The proposed mechanism suggests that the peering ISPs can share costs by deciding to split and download different parts of content through their transit links and then exchange the rest of the parts via their peering link. Indeed, as each peering ISP will download different chunks using its transit link, it will be charged less by the ISP of the upper Tier.

Peering ISPs first decide which chunks of the content will download from remote ASes. The chunks can be partitioned in two subsets of equal size according to their ids, e.g. in even and odds or first half and second half or any other similar way. The rest of the chunks that each ISP does not download from the remote ASes will be retrieved from the peering link or from local peers. As in the plain BNS-BU, the peer may identify its neighbors by the ranked list of peers that it retrieves from the overlay server. Since we consider that the peers already run BNS-BU algorithms only few modifications have to be implemented. In particular, the ranked list needs to contain another field, which indicates the type of the chunks (or in other words the set of ids) that the peer is allowed to download from every peer in the list. In our evaluation we split the chunks according to even and odd ids. In this case the list contains triplets of {address -group's value -chunkTypeID}, (a, g, c). Thus, the querying peer uses g to identify proximity of peer a for BNS and BU algorithms and c to identify which chunks it can download from this particular peer. Let us suppose that ISPs 3a and 3b (as in Figure 1) are collaborating using the proposed mechanism and have decided that peers from 3a will download the even chunks of the content (c=2) while peers from 3b the odd ones (c=1). Then a peer from 3a receives three triplets, one for a peer from 3a, (a 1 , g 1 , c 1 ), one for a peer from 3b (a 2 , g 2 , c 2 ) and one for a peer from 2a (a 3 , g 3 , c 3 ). The first peer belongs to 3a, thus g 1 =1 and c 1 =0, which indicates that a 1 peer is local and the requesting peer can download every chunk therefrom. For the second peer (in 3b) g 2 =2 and c 2 =0, which indicates that a 2 peer belongs to a peering ISP and the peer can download every chunk too. Finally for the third peer (in 2a) g 3 =3 and c 3 =2, which indicates that a 3 peer belongs to an ISP 1 hop away and the peer can download only even chunks. Also in order for a peer to download content in accordance to Splitting of Chunks, two extra modifications have to be introduced. In particular, the peer once acquiring the message with the list of the available chunks of a neighbor, it has to decide if it is interested in any of the chunks this neighbor has (and eventually download them), as normally happens in BitTorrent mechanism. Therefore it needs to check whether the neighbor possesses any of its missing chunks and also if those chunks belong to the subset of chunks that the field c indicates for that neighbor. If it does so, then the peer declares its interest to that neighbor and requests the specific chunks.

Experimental Evaluation

In this section, we present the experimental performance of Splitting of Chunks mechanism and its comparison to BNS-BU mechanism with or without collaboration between ISPs. In the first set of simulations, we run Splitting of Chunks on top of BNS-BU combination mechanism in order to evaluate our approach. The columns of Table 2 present the different scenarios; BNS-BU and Splitting of Chunks. BNS-BU runs in all ISPs of our topology while there are different set of experiments for Splitting of Chunks. SC Tier2 refers on the sets of experiments where only 2a and 2b run Splitting of Chunks. Respectively, SC Tier 3 refers to the sets of experiments where 3a and 3b support this approach while in SC Tier 2 & Tier 3, 2a, 2b, 3a and 3b support it. For all experiments the rest of the ISPs in our topology support BNS-BU. The rows of Table 2 comprise the mean traffic volume for inter-domain links 1a2a and 2a3a and the mean download times for peers that belong to 2a and 3a ASes.

In SC Tier 2 scenario, ISP 2a manages to reduce the inter-domain traffic exchanged with its transit ISP (1a) by 15.6%. The traffic exchanged via the transit link with its customers remains unaffected (~1%) as well as the download times for peers in 2a and 3a (<4%). Also, the inter-domain traffic 2a3a is slightly reduced too. Thus, if ISP 2a runs Splitting of Chunks, there is a win-no lose situation, since it reduces transit traffic without affecting the performance of its users. At the same time there is a winno lose situation for its customer ISPs, since the action of ISP 2a affects neither their traffic nor their users' performance. In fact, ISP 2a would not like to have caused a significant reduction of the transit traffic of its customers, because this would affect adversely its own revenue. From Tier 3 ISPs' (3a and 3b) perspective, in case they agree to support the Splitting of Chunks approach, they reduce almost 30% their inter-domain traffic exchanged with their transit ISP. On the other hand, the performance of their users is strongly deteriorated and thus it is highly unlikely for them to proceed with such an approach. In fact, even if Tier 2 ISPs proceed in adopting Splitting of Chunks, Tier 3 ones will not make the same decision, despite the significant gain in their transit interdomain traffic, since their users' performance is still strongly affected. To reach safe conclusions according to the problem that Tier 3 ISPs face, we conducted experiments using also Collaborative BNS-BU only in Tier 3 ISPs 3a and 3b. In a similar way is not in the interest of a small Tier 3 ISP to proceed to such a collaborative approach, due to the additional delays in download times that its users are experiencing.

Since the introduction of Splitting of Chunks in Tier 2 ISPs may be considered as applicable and promising, we continue our experimental analysis by introducing also Collaborative BNS-BU and Layered Collaborative BNS-BU in Tier 2 ISPs and combining these approaches with Splitting of Chunks. In Table 3 The effect of Splitting of Chunks on top of Collaborative BNS-BU, either with or without layers, is almost the same. The new approach results in an inter-domain traffic reduction about 9% compared to Collaborative BNS-BU and 33% compared to BNS-BU, without essentially affecting users' performance in both Tiers. Thus, Tier 2 ISPs that have a peering agreement can adopt Splitting of Chunks on top of any BNS-BU approach that they follow. The first column of each group comprises the corresponding BNS-BU that 2a, 2b and their customers run. The second, third and fourth column refers to Splitting of Chunks approach when only Tier 2 ISPs 2a and 2b, Tier 3 ISPs 3a and 3b and Tier 2 & 3 ISPs 2a, 2b, 3a and 3b run respectively but all of the aforementioned ISPs and their customers run Collaborative BNS-BU; this is different from the corresponding scenario of Table 3, where only 2a and 2b run Collaborative BNS-BU. Also the rest of the ISPs run BNS-BU. When only Tier 2 ISPs 2a, 2b run Splitting of Chunks on top of Collaborative BNS-BU, they manage to reduce their transit inter-domain traffic by 30% (60% compare to BNS-BU) essentially without affecting peers' performance, thus attaining a win-no lose situation. Traffic between 2a and 3a and download times for peers in 3a are marginally affected (3% and 3.9% respectively, although download times are better). Thus, there is a win-no lose situation for ISPs in both Tiers. Tier 3 ISPs will not adopt Splitting of Chunks as in the previous scenarios, due to slower download times of their users. In case that Tier 2 ISPs already deploy Splitting of Chunks on top of Collaborative BNS-BU, Tier 3 ISPs are indifferent in adopting the approach. However, in the case where all adopt Splitting of Chunks we observe the lowest value of inter-domain traffic 1a2a (34%, 63% compared to Collaborative BNS-BU and plain BNS-BU respectively). Again win-no lose situations arise between Tier 2 ISPs and their users and also between Tier 2 ISPs and their customers ISPs. Therefore, ISP 2a may ask its customers to follow this approach sharing the benefits with them. The same observations are applicable to the case of Layered Collaboration BNS-BU. Besides comparing mean download times, we have also measured the difference between the 95 th percentile value of each scenario and BNS-BU; for all scenarios (except for SC Tier 3 approaches), was below 3%. We also have run experiments where the two large peering ISPs and their customers, have a different amount of peers in the swarm. We have reached the same conclusions as before, though the download times of the peers were deteriorated slightly more due to the lack of resources in the peering ISP.

Thus, we conclude that even in case of a different approach such as Splitting of Chunks, large ISPs gain from deploying it due to fact that their peers can find larger amounts of resources locally or from the customers of their ISPs and thus interdomain traffic exchanged through costly transit links can be reduced.

Conclusions and Further Work

In this paper, we introduce and evaluate collaborative variations of the BNS-BU (Biased Neighbor Selection -Biased Unchoking) locality promotion approach, namely Collaborative and Layered Collaborative, BNS-BU, as well as the Splitting of Chunks approach. All of them exploit the business relationships between ISPs of either the same or different Tiers in order to reduce the costly transit inter-domain traffic. By means of simulations, we show that large ISPs (Tier 2 in our simulations) can attain this goal, while in general not deteriorate the performance of their users. Indeed, in case peering Tier 2 ISPs collaborate with each other and with their customer ISPs, running Collaborative BNS-BU, a win-win situation for the large ISPs and their users is arising, without affecting the transit inter-domain traffic and the performance of the users of Tier 3 ISPs. The introduction of Splitting of Chunks on top of the aforementioned scenario leads to additional reduction of the transit interdomain traffic of Tier 2 ISPs, but just maintains user performance, thus leading to a win-no lose situation. In general, we conclude that large ISPs have the incentives to collaborate with each other, creating large clusters within which they promote locality without affecting the performance of their users, while they can further benefit if they provide their customers ISPs with the incentive to collaborate with them. In future research, we plan to focus on the case of P2P Video-on-Demand applications, and consider different topologies and set-ups for our simulations, e.g. asymmetric cases.

Fig. 1 .

 1 Fig. 1. Topology used in Simulation

Table 1 .

 1 Collaborative BNS-BU approaches

	Metric /	BNS-	Collaborative BNS-BU	Layered Collaborative BNS-BU
	Scenario	BU	Tier 2	Tier 3	Tier 2&3	Tier 2	Tier 2&3
	Traffic 1a2a (MB/s)	1.09	0.8	1.01	0.61	0.8	0.63
	Traffic 2a3a (MB/s)	11.11	11.29	11.03	11.54	11.02	10.86
	DT 2a (min)	2.92	2.99	2.98	2.03	3.06	3.03
	DT 3a (min)	8.95	8.85	9.01	9.11	8.96	9.06
	As shown in Table

Table 2 .

 2 Splitting of Chunks comparison with BNS-BU mechanism

	Metric / Scenario	BNS-BU	SC Tier 2	SC Tier 3	SC Tier 2 & 3
	Traffic 1a2a (MB/s)	1.09	0.92	2.2	1.69
	Traffic 2a3a (MB/s)	11.11	10.99	7.84	7.74
	DT 2a (min)	2.92	3.04	3.00	2.99
	DT 3a (min)	8.95	9.25	11.19	11.28

  we present the previous results for BNS-BU, Collaborative BNS-BU, Layered Collaborative BNS-BU and the Splitting of Chunks approach on top of those algorithms. The first column of the table comprises BNS-BU scenario. The second and the third column refer to two scenarios based on Collaborative BNS-BU in Tier 2 ISPs 2a and 2b (second column) and Splitting of Chunks on top of Collaborative BNS-BU in Tier 2 ISPs 2a and 2b (third column). In the last two columns we replace Collaborative BNS-BU with Layered Collaborative BNS-BU. The rest of the ISPs run BNS-BU.

Table 3 .

 3 Splitting of Chunks combined with BNS-BU collaboration approaches in Tier 2 ISPs can be expected to implement Splitting of Chunks on top of Collaborative BNS-BU approaches adopted only by them, we also have to investigate the reaction of Tier 3 ISPs. In Table4there are two groups of experiments; the one with Collaborative BNS-BU and the second with Layered Collaborative BNS-BU.

	Metric / Scenario	BNS-BU	Collaboration BNS-BU SC Tier 2 Tier 2	Layered Collaboration BNS-BU SC Tier 2 Tier 2
	Traffic 1a2a (MB/s)	1.09	0.8	0.73	0.8	0.74
	Traffic 2a3a (MB/s)	11.11	11.29	11.16	11.02	11.26
	DT 2a (min)	2.92	2.99	2.97	3.06	3.03
	DT 3a (min)	8.95	8.85	8.88	8.88	9.02
	Since Tier 2

Table 4 .

 4 Splitting of Chunks combined with BNS-BU collaboration approaches in all Tiers

			Collaboration		Layered Collaboration
	Metric / Scenario	BNS-Tier BU	Tier 2 SC	Tier 3 SC	Tier 2&3 SC	Tier 2&3 BNS-BU	SC Tier 2	SC Tier 3	SC Tier 2&3
		2&3
	Traffic 1a2a (MB/sec)	0.61	0.43	0.8	0.4	0.63	0.61	0.89	0.41
	Traffic 2a3a (MB/sec)	11.54	11.9 8.17	11.8	10.86	11.05	7.69	11.15
	DT 2a (min) 3.02	2.99 2.95	2.98	3.03	3	2.94	2.93
	DT 3a (min) 9.11	8.75 11.1	8.89	9.06	9.06	11.31	8.82

Acknowledgments. This work has been performed in the framework of the EU ICT Project SmoothIT (FP7-2007-ICT-216259). The authors would like to thank all SmoothIT partners for useful discussions on the subject of the paper. Also, this work has been partly funded by the European Social Fund and National Resources Ministry of Education -HERAKLEITOS II Programme).