extfieldsofstudy:
Computer Science
Mathematics

text:
Minimizing weighted sum download time for one-to-many file transfer in peer-to-peer networks

This paper considers the problem of transferring a file from one source node to multiple receivers in a peer-to-peer (P2P) network. The objective is to minimize the weighted sum download time (WSDT) for the one-to-many file transfer. Previous work has shown that, given an order at which the receivers finish downloading, the minimum WSD can be solved in polynomial time by convex optimization, and can be achieved by linear network coding, assuming that node uplinks are the only bottleneck in the network. This paper, however, considers heterogeneous peers with both uplink and downlink bandwidth constraints specified. The static scenario is a file-transfer scheme in which the network resource allocation remains static until all receivers finish downloading. This paper first shows that the static scenario may be optimized in polynomial time by convex optimization, and the associated optimal static WSD can be achieved by linear network coding. This paper then presented a lower bound to the minimum WSDT that is easily computed and turns out to be tight across a wide range of parameterizations of the problem. This paper also proposes a static routing-based scheme and a static rateless-coding-based scheme which have almost-optimal empirical performances. The dynamic scenario is a file-transfer scheme which can re-allocate the network resource during the file transfer. This paper proposes a dynamic rateless-coding-based scheme, which provides significantly smaller WSDT than the optimal static scenario does.

I. Introduction
P2P applications (e.g, [1], [2], [3], [4]) are increasingly popular and represent the majority of the traffic currently transmitted over the Internet. A unique feature of P2P networks is their flexible and distributed nature, where each peer can act as both a server and a client [5]. Hence, P2P networks provide a cost-effective and easily deployable framework for disseminating large files without relying on a centralized infrastructure [6]. These features of P2P networks have made them popular for a variety of broadcasting and file-distribution applications [6] [7] [8] [9] [10] [11] [12].
Specifically, chunk-based and data-driven P2P broadcasting systems such as CoolStreaming [7] and Chainsaw [8] have been developed, which adopt pull-based techniques [7], [8]. In these P2P systems, the peers possess several chunks and these chunks are shared by peers that are interested in the same content. An important problem in such P2P systems is how to transmit the chunks to the various peers and create reliable and efficient connections between peers. For this, various approaches have been proposed including tree-based and data-driven approaches (e.g. [10] [13] [14] [15] [16] [17] [18]).
Besides these practical approaches, some research has begun to analyze P2P networks from a theoretic perspective to quantify the achievable performance. The performance, scalability and robustness of P2P networks using network coding are studied in [19] [20]. In these investigations, each peer in a P2P network randomly chooses several peers including the server as its parents, and also transmits to its children a random linear combination of all packets the peer has received. Random linear network coding [21] [22] [23], working as a perfect chunk selection algorithm, makes elegant theoretical analysis possible. Some other research investigates the steady-state behavior of P2P networks with homogenous peers by using fluid models [24] [25] [26].
In a P2P file transfer application (e.g, BitTorrent [1], Overcast [12]), the key performance metric from an end-user's point of view is the download time, i.e., the time it takes for an end-user to download the file. In [9], Li, Chou, and Zhang explore the problem of delivering the file to all receivers in minimum amount of time (equivalently, minimizing the maximum download time to the receivers) assuming node uplinks are the only bottleneck in the network. They introduce a routing-based scheme, referred to as Mutualcast, which minimizes the maximum download time to all receivers with or without helpers. This paper also focuses on file transfer applications in which peers are only interested in the file at full fidelity, even if it means that the file does not become available to all peers at the same time. In particular, this paper considers the problem of minimizing weighted sum download time (WSDT) for one-to-many file transfer in a peer-to-peer (P2P) network.
Consider a source node s that wants to broadcast a file of size B to a set of N receivers i ∈ {1, 2, · · · , N} in a P2P network. Our model assumes that the source uplink bandwidth constraint U s , the peer uplink bandwidth constraints U i , and the peer downlink bandwidth constraints D i are the only bottlenecks in the network. Limited only by these constraints, every peer can connect to every other peer through routing in the overlay network.
In order to understand the fundamental performance limit for one-to-many file transfer in P2P networks, it is assumed that all nodes are cooperative, and a centralized algorithm provides the file-transfer scenario with the full knowledge of the P2P network including the source node's uplink capacity , and the weights, downlink capacities, and uplink capacities of peers. The cooperative assumption holds in many practical applications, for example, in closed content distribution systems where the programs are managed by a single authority.

II. Main Contribution
The general problem of minimizing WSDT divides into an exhaustive set of cases according to three attributes. The first attribute is whether the allocation of network resources is static or dynamic. In the static scenario, the network resource allocation remains unchanged from the beginning of the file transfer until all receivers finish downloading. The dynamic scenario allows the network resource allocation to change as often as desired during the file transfer.
The second attribute is whether downlink bandwidth constraints are considered to be unlimited (i.e. D i = ∞) or not (i.e. D i ≤ ∞). Most research in P2P considers the download bandwidth constraints to be unlimited because the uplink capacity is often several times smaller than the downlink capacity for typical residential connections (e.g., DSL and Cable).
However, consideration of downlink bandwidth constraints can be important. The downlink capacity can still be exceeded when a peer downloads from many other peers simultaneously, as in the routing-based scheme proposed in [27].
The third attribute is whether we consider the special case of sum download time (i.e. W i = 1 for all i) or the general case of weighted sum download time which allows any values of the weights W i .
With these cases in mind, here is an overview of the results presented in this paper. For the static scenario that considers download bandwidth constraints D i ≤ ∞ and allows any values of W i , Section III uses a time-expanded graph and linear network coding to show that the minimum WSDT and the corresponding allocation of network resources may be found in polynomial time by solving a convex optimization problem. We also present a lower bound on minimum WSDT that is easily computed and turns out to be tight across a wide range of parameterizations of the problem.
While the minimum WSDT for the static scenario may be found in polynomial time using the approach of Section III, that approach is sufficiently computationally intensive that Sections IV and V provide lower complexity alternatives. In some cases, the lower complexity approaches are exactly optimal. For the remaining cases, the lower bound of Section III shows that their performance is indistinguishable from the lower bound and hence closely approach optimality across a wide range of parameterizations.
Sections IV and V build on the foundation of the Mutualcast algorithm [9]. Mutualcast is a static rate allocation algorithm designed to minimize the maximum download time to all peers in the case where D i = ∞. Section III concludes by showing that Mutualcast achieves that section's lower bound when W i = 1 for all i and therefore minimizes sum download time as well as maximum download time.

Inspired by this result, Section IV proposes a generalization of this algorithm, Extended
Mutualcast, that minimizes sum download time even when the download bandwidth constraints D i are finite and distinct from each other. When uplink bandwidth resources are plentiful, Extended Mutualcast also minimizes weighted sum download time regardless of weights because each receiver is downloading content as quickly as possible given its download bandwidth constraint and the upload bandwidth constraint of the source.
It is notable that Mutualcast and Extended Mutualcast achieve their optimal results while utilizing only depth-1 and depth-2 trees. Inspired by this fact and the technique of rateless coding, Section V attacks the general problem of minimizing weighted sum download time(WSDT) by proposing a convex optimization approach that assumes only trees of depth one or two. Then, Section V proposes a simple water-filling approach using only depth-1 and depth-2 trees. While the optimality of this approach is not proven, Section V-E shows that its performance matches that of the lower bound of III for a wide variety of parameterizations. Thus this water-filling approach provides a simple algorithm that empirically achieves the lower bound on WSDT for all cases of the static scenario across a wide range of parameterizations.
Turning our attention to the dynamic scenario, Wu et al. [27] demonstrate that given an order in which the receivers finish downloading, the dynamic allocation (neglecting downlink bandwidth constraints) that minimizes WSDT can be obtained in polynomial time by convex optimization and can be achieved through linear network coding. They also propose a routing-based scheme which has almost-optimal empirical performance and demonstrate how to significantly reduce the sum download time at the expense of a slight increase in the maximum download time.
Dynamic schemes can reduce the minimum sum download time to approximately half that of the static case, at least when downlink capacities are considered to be infinite [27]. Essentially, [27] shows that to optimize WSDT the network resource allocation should remain constant during any "epoch", a period of time between when one receiver finishes downloading and another finishes downloading. Thus, one optimal solution for the dynamic scenario is "piecewise static". However, [27] leaves the proper selection of the ordering as an open problem and does not address the finite downlink capacities D i < ∞ or the general case of weighted sum download time which allows any values of the weights W i .
Section VI provides a practical solution for the dynamic scenario. Specifically, it provides an approach the ordering problem left open by [27] by reformulating the problem as that of determining the weights that should be assigned during each static epoch so as to produce the piecewise static solution that minimizes the WSTD (according to the original weights).
This approach handles both finite downlink capacities D i < ∞ and the general case of weighted sum download time which allows any values of the weights W i . A key result of this section is that, regardless of how the overall weights W i are set, the "piecewise static" solution may be obtained by finding the appropriate weights for each epoch and solving the static problem for that epoch. Furthermore, during any epoch the appropriate weights of all peers are either 1 or zero with the exception of at most one "transitional" peer whose weight can be anywhere between zero and 1. Neglecting the "transitional" node, the ordering problem becomes approximately one of choosing which peers should be served during each epoch. Having resolved the ordering problem in this way, the simple water-filling approach of Section V provides the rate allocations for the source and for each peer during each of the piecewise-static epochs. Thus this section provides a complete solution for the dynamic scenario. Because the selection of the ordering and the rate allocation are both close to optimal, we conjecture that the overall performance of this solution is close to optimal across a wide range of parameterizations.
Section VIII delivers the conclusions of this paper.

III. Convex Optimization of WSDT in the Static Case
This section considers a static P2P network in which the source node with uplink bandwidth U s seeks to distribute a file of size B so as to minimize the weighted sum of download times given a static allocation of resources. The static scenario assumption also indicates that no peer leaves or joins during the file transfer. There are N peers who want to download the file that the source node has. Each peer has weight W i , downlink capacity D i and uplink capacity U i , for i = 1, 2, · · · , N. It is reasonable to assume that D i ≥ U i for each i = 1, · · · , N since it holds for typical residential connections (e.g., Fiber, DSL and Cable).
In case of D i < U i for some i, we just use peer i's part of the uplink capacity which equals to its downlink capacity and leave the rest of the uplink capacity unused.
The uplink and downlink capacities of each peer are usually determined at the application layer instead of the physical layer, because an Internet user can have several applications that share the physical downlink and uplink capacities. The peer weights depend on the applications. For broadcast applications such as CoolStreaming [7] and Overcast [12]in which all peers in the P2P network are interested in the same content, all peer weights in the content distribution system can be set to 1. In multicast applications such as "Tribler" [28] peers called helpers, who are not interested in any particular content, store part of the content and share it with other peers. Assign weight zero to helpers, and weight 1 to receivers. In some applications, P2P systems partition peers into several classes and assign different weights to peers in different classes.
Denote the transmission rate from the source node to peer j as r s→j and the transmission rate from peer i to peer j as r i→j . The total download rate of peer j, denoted as d j , is the summation of r s→j and r i→j for all i = j. Since the total download rate is constrained by the downlink capacity, we have As a notational convenience, we also denote r j→j as the transmission rate from the source node to peer j so that The total upload rate, denoted as u j , is constrained by the uplink capacity. Hence, we also have u j = i =j r j→i ≤ U j for all j = 1, · · · , N. One example of the peer model is shown in Fig. 1. The downlink capacity and uplink capacity of peer 1 are D 1 and U 1 respectively. Thus, the total download rate r s→1 + 4 i=2 r i→1 = 4 i=1 r i→1 has to be less than or equal to D 1 , and the total upload rate 4 i=2 r 1→i has to be less than or equal to U 1 .

A. The Time-Expanded Graph
As one of the key contributions of [27], Wu et al. used a time-expanded graph to show how the dynamic scenario decomposes into epochs. This section applies the time-expanded graph approach provided in [27] to the static case.
To obtain the time-expanded graph for a P2P network with N peers, we need to divide the time into N epochs according to the finishing times of the peers. One peer finishes downloading at the end of each epoch so that the number of epochs is always equal to the number of peers. Let ∆t i denote the duration of the i-th epoch. Hence, i receivers finish downloading by time t i = i k=1 ∆t k . If peers i and i + 1 finish downloading at the same time, ∆t i+1 = 0.
Each vertex in the original graph G corresponds to N vertices, one for each epoch, in the time-expanded graph G (N ) as follows: We begin with the original P2P graph G with node set V = {s, 1, · · · , N} and allowed edge set E. For each v ∈ V and each n ∈ {1, · · · , N}, G (N ) includes a vertex v (n) corresponding to the associated physical node v in the n-th epoch. For each e ∈ E going from u to v and each n ∈ {1, · · · , N}, G (N ) includes an edge e (n) going from u (n) to v (n) corresponding to the transmission from u to v during the n-th epoch.
The subgraph G (n) = (V (n) , E (n) ) for n = 1, · · · , N characterizes the network resource allocation in the n-th epoch. To describe a rate allocation in the original graph G, edges are typically labeled with the rate of information flow. However, since each epoch in the timeexpanded graph G (N ) has a specified duration, each of the N edges in the time-expanded graph corresponding to an edge in G is labeled with the total amount of information flow across the edge during its epoch. This is the product of the flow rate labeling that edge in the original graph G and the duration of the epoch.
The time-expanded graph also includes memory edges. For each v ∈ V and each n ∈ {1, · · · , N − 1}, there is an edge with infinite capacity from v (n) to v (n+1) . These memory edges reflect the accumulation of received information by node v over time.
As just described, the time-expanded graph not only describes the network topology, but also characterizes the network resource allocation over time until all peers finish downloading in a P2P network. As shown in [27] by Wu et al., even in the dynamic scenario the network resource allocation can remain static throughout each epoch without loss of optimality. In this section, we apply the time-expanded graph to the static scenario in which the rate allocation remains fixed for the entire file transfer.
As an example, consider the following scenario. A P2P network contains a source node seeking to disseminate a file of unit size (B = 1). Its upload capacity is U S = 2. There are three peers {1, 2, 3} with upload capacities U 1 = U 2 = U 3 = 1 and download capacities   with rate 1 to peer 2 but does not transmit to any other peers. Peers 2 and 3 transmit with rate 1/2 to Peer 1, but do not transmit to any other peers.  An example P2P graph G. Edges are labeled with the rate allocation r i→j that minimizes the sum of the download times. (3) (2) (2) (1) (1)  epochs have zero duration.

B. Transmission Flow Vectors and a Basic Network Coding Result
In Section III-A there was a tacit assumption that all of the information received by a peer is useful. For example, we assumed that the information relayed from peer 2 to peer 1 did not repeat information sent from the source to peer 1.
In the examples of Section III-A, one can quickly construct simple protocols that ensure that no critical flows are redundant.
In this subsection, we review a general result that uses network coding theory to show that there is always a way to ensure that no critical flows are redundant.
The total flow supported by f is e∈Out  Table I. Examining Table I verifies that the flow conservation constraint (3) is satisfied and that the total flow supported is equal to 1 file.
The following lemma states that a given fixed flow (or flow rate) can be achieved from the source to all destinations as long as there is a feasible flow vector supporting the desired flow from the source to each destination. i.e. We can achieve this flow to all destinations with network coding without worrying about possible interactions of the various flows..
where f i is a flow from s to i with flow r. Furthermore, if (4) holds, there exists a linear network coding solution.

C. A Convex Optimization
Given an order in which the peers will finish downloading, say peer i finishes at the end  and only if the following system of linear inequalities has a feasible solution: where c u is the uplink capacity of peer u, and f i is a flow from first-epoch source node s (1) to node i's termination-epoch node i (k i ) with flow rate B.
As an example, the epoch durations of Fig. 3 are feasible because each of the flow vectors (one example was given in Table I) satisfy the feasibility constraints of Lemma 2.
Let t j denote the download time to peer j for j = 1, · · · , N. Given a static network resource allocation r i→j , (i, j ∈ {1, · · · , N}) as shown for example in Fig. 2, the maximum flow to peer j, denoted as r j , is equal to the minimum cut between source node s and peer j in the rate-allocation graph (i.e. a graph such as Fig. 2, not the time-expanded graph).
This follows from the Max-Flow-Min-Cut Theorem. Hence, t j ≥ B r j , ∀j.
From applying network coding results such as Lemma 1 to the rate allocation graph alone, we cannot conclude much about feasible download times since Lemma 1 addresses only the feasibility of the same flow to all destinations. However, by applying Lemma 1 to the timeexpanded graph we can show that t j = B r j can be achieved simultaneously for all j = 1, · · · , N. Lemma 3 below states this result.
Lemma 3: Given a static network resource allocation r i→j , (i, j = 1, · · · , N), for a P2P network, the only Pareto optimal (smallest) download time vector is t j = B r j for j = 1, · · · , N, where r j is the minimum cut from the source node s to peer j.
Proof: It has been shown that t j ≥ B r j for j = 1, · · · , N. Hence, it is sufficient to show that t j = B r j for j = 1, · · · , N is achievable. Without loss of generality, assume that r 1 ≥ r 2 ≥ · · · ≥ r N > 0. Construct a static scheme (i.e. a time-expanded graph G (N ) ) as follows: (4) Flow capacity of edge j (k) → j (k+1) is infinity for j = 1, · · · , N and k = 1, · · · , N − 1; (5) The destination nodes in the time-expanded graph are node i (i) for i = 1, · · · , N. In other words, peer i finishes at the end of i-th epoch.
According to the constructions (1) and (5), the download time to peer i is t i = i k=1 ∆t k = B r i . According to the constructions (2) and (3), in the subgraph G (k) , the maximum flow from s (k) to i (k) is equal to r i ∆t k for all i, k = 1, · · · , N. Therefore, in this time-expanded graph G (N ) , the maximum flow from source node s to node i (i) is greater than or equal to where r i→j (i, j = 1, · · · , N) represents the network resource allocation and f (k) i→j (i, j = 1, · · · , N) is a flow from the source node s to peer k.
By Lemma 3, the minimum WSDT is the solution to the convex optimization of minimizing (8)(9)(10)(11)(12)(13)(14)(15). Thus, we can conclude the following theorem: Theorem 1: Consider multicasting a file with size B from a source node s to peers {1, · · · , N} in a P2P network with both uplink and downlink capacity limits. The minimum weighted sum downloading time for the static scenario and the corresponding optimal static allocation can be found in polynomial time by solving the convex optimization of minimizing N k=1 W k B/r i subject to the constraints (8-15).
Theorem 1 gives a solution to the most general static case that we are considering in this paper. However, it can be extended further by adding other linear network constraints (e.g. edge capacity constraints), which are not a concern of this paper.

D. The Uplink-Bandwidth-Sum Bound
For a P2P network with a source node and N peers, the convex optimization in Theorem 1 has N 3 + N 2 + N variables and 2N 3 + 3N 2 + N + 1 linear constraints. The complexity for the interior point method to solve this convex optimization is O((N 3 ) 3.5 ) [29].
Even though the convex optimization can be solved in polynomial time, its complexity is still too high for practical applications when N is large. Hence, bounds on the minimum WSDT and static schemes having network resource allocations that may be computed with low complexity are desired. In this subsection, we provide an analytical lower bound to the minimum WSDT with O(N 2 ) complexity for computing both the bound itself and the associated rate allocations.
Consider the cut of {V \ i} → {i} for any static allocation r i→j i, j ∈ {1, · · · , N}, the maximum flow rate from the source node s to peer i, r i , is limited by Consider the cut of {s} → {1, · · · , N}, r i is also bounded by Inequalities (16) and (20) indicate that the downloading flow rate for peer i is limited by peer i's downlink capacity and the source node's uplink capacity respectively. These two constraints are not only valid for the static scenario but also for dynamic scenarios.
Inequality (19) shows that the sum of the downloading flow rates for all peers is bounded by the total amount of the network uplink resource. Again, this constraint holds in both the static and dynamic cases.

Because all feasible sets of {r
where only r i (i = 1, · · · , N) are the variables. Empirical experiments presented in Section V-E show that this lower bound is tight for most P2P networks.
The minimization problem (21) is a convex optimization. Its optimal solutions are also the solutions to the associated Karush−Kuhn−Tucker (KKT) conditions [29]. The KKT conditions for problem (21) are Solving the KKT conditions yields the following optimal solution for {r i }: where R is chosen such that The lower bound to the WSDT for the static scenario is then with r * i as specified in (27).
For the special case where W i = 1 and D i = ∞ (i = 1, · · · , N), the solution given in (27) becomes and the lower bound to the minimum WSDT is Mutualcast [9] was designed to minimize the maximum download time for the case where However, since Mutualcast can achieve the download time of B min(Us, for all peers, it achieves the lower bound of (29) for the W i = 1 case. This fact shows both that the lower bound of (29) is tight when W i = 1 and D i = ∞ and that Mutualcast minimizes sum download time as well as the maximum download time when D i = ∞.

Case
The concluding paragraph of Section III-D stated that Mutualcast minimizes the sum download time for the case where D i = ∞. In this section we extend Mutualcast to provide an algorithm we call Extended Mutualcast that handles finite constraints on D i (possibly delivering different rates to different peers) while still minimizing the sum download time.

A. Mutualcast
Mutualcast delivers the same rate to every peer. Assuming D i = ∞, Mutualcast can support peers with any rate R ≤ min(U s , Given an ordering of the peers. (Without loss of generality, assume the order is 1, · · · , N.) 3: for i = 1 to N do 4: Mutualcast delivers information to all peers at the same rate. As described in Algorithm 1 the highest rate that Mutualcast can deliver is Consider two examples with ten peers, one in which R = U s and one in which R = First is an example where R = U s . Note that in general it is not possible for any peer to receive information at a rate higher than U s . Let U s = 1, U i = 1 for all ten peers, and D i = ∞ for all ten peers. Mutualcast achieves R = U s = 1 by having nine peers receive rate 1/9 from the source and forward at that rate to the nine other peers. One peer receives no information directly from the source because by the time the Mutualcast algorithm gets to that peer, the source upload bandwith has been used up.
For an example where R = , a larger U s is necessary. Let U s = 10, U i = 1 for all ten peers and D i = ∞ for all ten peers. Mutualcast achieves R = In the first part of the Mutualcast algorithm, all ten peers receive rate 1/9 from the source and relay at that rate to the nine other peers. At this point there remains 80/9 of source upload bandwidth, which is distributed evenly so that each peer receives a rate of 8/9 directly from the source that it does not relay. In total, each peer receives rate 2 which is comprised of rate 1 from other peers, rate 1/9 from the source that it relays to the other peers, and rate 8/9 from the source that it does not relay.
The basic Mutualcast algorithm does not consider download constraints. The slight modification of Mutualcast given below includes download bandwidth constraints D i in the simplest possible way. Note that if all peers are to receive at the same rate, that rate must be less than the smallest download constraint. This is reflected in line 1 of Algorithm 2.
As with the original Mutualcast, Algorithm 2 delivers the same rate to every peer. This alone is enough to prevent it from minimizes the sum download time in general when there are download constraints. However, it will turn out to be an important component of Extended Mutualcast, which is an algorithm that does minimize the sum download time under general download constraints.

B. Extended Mutualcast
Setting W i = 1 for all i in (27) produces the following lower bound on the sum download time when both upload and download constraints are considered: where where R is chosen such that This lower bound can be achieved by a routing-based scheme that we call Extended Mutualcast.
Consider a P2P network with constraints on peer uplink bandwidth and peer downlink bandwidth. Without loss of generality, assume that D 1 ≤ · · · ≤ D N . Hence,D 1 ≤ · · · ≤ D N ≤ U s and r * 1 ≤ · · · ≤ r * N . The network resource allocation and the routing for Extended Mutualcast are provided in Algorithms 3 and 4 respectively.

5:
Apply Algorithm 2 with rate R to the network. 9: for Step i = 1 to j do 10: Successively apply Algorithm 2 with rateD i −D i−1 (D 0 0) to the network with the source node s and the ordered peers {i, · · · , N}. Note that with each successive application of Algorithm 2, the values of r i→j accumulate.

11:
end for 12: Step j + 1: Apply Algorithm 2 one final time with rate R −D j to the network with the source node s and the ordered peers {j + 1, · · · , N}. Again, the values of r i→j accumulate. 13: else if R ≥D N then 14: 15: for Step i = 1 to N do 16: Successively apply Algorithm 2 with supporting rateD i −D i−1 to the network with the source node s and the ordered peers {i, · · · , N}. Note that with each successive application of Algorithm 2, the values of r i→j accumulate.

17:
end for 18: end if Algorithm 4 Routing Scheme for Extended Mutualcast 1: Given R and r * i (i = 1, · · · , N) from (33-36). 2: Given the network resource allocation r i→j (i, j = 1, · · · , N) by Algorithm 3 where r i→i r s→i ≥ r i→j . (This routing scheme is based on that network resource allocation.) 3: Partition the whole file into many chunks. 4: if R ≤D 1 then

5:
Apply the routing scheme of Mutualcast [9]. That is, for each i = 1, · · · , N and some j = i, accumulatively route r i→j R fraction of all chunks from the source node to peer i, and then copy and route them from peer i to other peers. Accumulatively route the rest of the chunks are from the source node to all peers directly. 6: else ifD j < R ≤D j+1 for j = 1, · · · , N − 1. then

8:
Until peers {j + 1, · · · , N} finish downloading. 9: for Step i = j to 1 do 10: In Step i, the interesting chunks are those peer i hasn't received.

12:
Until peer i finishes downloading.

14:
Note that prior to Step i, none of the peers 1, · · · , i contain the interesting chunks broadcast during Step i. 15: end for 16: else if R ≥D N then 17: for Step i = N to 1 do 18: In Step i, the interesting chunks are those peer i hasn't received.

20:
Until peer i finishes downloading. The network resource allocation for Extended Mutualcast (Algorithm 3) is obtained by successively applying Algorithm 2 to the P2P network or part of the P2P network. The network resource allocation by Algorithm 3 has r s→i ≥ r i→j for all i, j. The flow rate to peer i, r i , is then equal to its download rate N j=1 r j→i . The routing scheme for Extended Mutualcast (Algorithm 4) guarantees that the entire flow rate r i is useful. For the Extended Mutualcast rate allocation, r i = min(R,D i ) so that the lower bound (33-36) on sum download time is achieved. Theorem 2 formally states and proves this fact.  (Achievability) It is sufficient to show that (a) Extended Mutualcast is applicable to any P2P network, and (b) Extended Mutualcast provides a static scenario in which the flow rate from the source node to peer i is r * i of (33-36). (To Show (a)) It is sufficient to show that in Algorithm 3, the rate for each applied Algorithms 2 is attainable. In other words, each rate for the applied network is less than or equal to the minimum of the source node's uplink capacity and the total uplink resource over all of the peers.
Hence, the rate R is attainable for Algorithm 2 in Line 4, Algorithm 3.
• IfD j < R ≤D j+1 , consider the worst case of D i = R for i = j + 1, · · · , N and U s = R. In this case, we have Denote U Hence, Algorithm 2 in Step 1 is feasible. Suppose Algorithm 2 is feasible for Step 1 to Step n (1 ≤ n ≤ j). Then U (i) which indicates that Algorithm 2 for Step 1 to Step i fully deploys the uplink resources of peers 1, · · · , i.

Now consider Algorithm 2 for
Step n + 1, the supporting rate isD n+1 −D n . The source node's uplink is R −D n . The total uplink resource is where (43) follows from (40), and (45) follows from (39). Hence, the rateD n+1 −D n is less than or equal to the total available uplink resource (42) divided by the number of peers, N − n. We also can see thatD n+1 −D n is less than or equal to the available source node's uplink bandwidth, R −D n . Therefore, Algorithm 2 for Step n + 1 is also feasible. By induction, Algorithm 2 is feasible for every step.
Consider the worst case of For this worst case, Algorithm 2 in Line 14 is feasible following an argument similar to that for the case ofD j < R ≤D j+1 . Therefore, Extended Mutualcast in Algorithm 3 is applicable to any P2P network.
(To Show (b)) From Algorithms 2 and 3, Extended Mutualcast constructs a static scenario with r s→i r i→i ≥ r i→j for i, j = 1, · · · , N, and N j=1 r j→i ≥ min(R,D i ) = r * i . Hence, the maximum flow from the source node to peer i is larger than or equal to N j=1,j =i min(r s→j , r j→i ) + r s→i (49) Therefore, Extended Mutualcast provides a static scenario in which the flow rate from the source node to peer i is r * i of (33-36).
Theorem 2 showed that Extended Mutualcast minimizes the sum download time for any static P2P network. When the total uplink bandwidth resource is sufficiently abundant, Extended Mutualcast also minimizes the weighted sum download time for any set of weights because all peers are downloading at their limit ofD i . Corollary 1 formally states and proves this fact.
Corollary 1: Consider multicasting a file with size B from a source node s to peers {1, · · · , N} in a P2P network with constraints on peer uplink bandwidth and peer downlink i , the set of the flow rates r i =D i (i = 1, · · · , N) is attainable. Hence, the minimum weighted sum download time for the static scenario is for any given weights W i . Mutualcast and Extended Mutualcast construct only two types of trees to distribute content. The first type is a depth-1 tree as shown in Fig. 6(a). The source node s broadcasts content to all peers directly with rate r (1) s→i , i = 1, · · · , N. The second type is a depth-2 tree as shown in Fig. 6(b). The source node distributes content to peer i with rate r (2) s→i , and then peer i relays this content to all other peers.

Proof: (Achievability) Note that when
In Mutualcast, the rates r (1) s→i are constrained to be equal for all i. Also, for a fixed i,  r (2) s→i = r i→j for all j ∈ {1, · · · , N}; j = i. These constraints on the network resource allocation simplify the mechanism design and allow a simple routing-based scheme. These two constraints together ensure that each peer downloads content at the same rate. However, to optimize WSDT peers surely need to download content and different rates.
In Section IV we saw that peers needed to download content at different rates to minimize the sum download time with peer downlink bandwidth constraints. The Extended Mutualcast algorithm provided a way to serve the peers at different rates corresponding to their download bandwidth constraints so as to minimize the sum download time. However, Extended Mutualcast required successive applications of Mutualcast which led to a complicated routing protocol.
In order to serve peers at different rates to minimize WSDT and still maintain a simple mechanism design, we apply the technique of rateless coding at the source node. A rateless code is an erasure correcting code. It is rateless in the sense that the number of encoded packets that can be generated from the source message is potentially limitless [30]. Suppose the original file size is B packets, once the receiver has received any B ′ packets, where B ′ is just slightly greater than B, the whole file can be recovered.
Fountain codes [30], LT codes [31], and raptor codes [32] are rateless erasure codes. LT codes have linear encoding complexity and sub-linear decoding complexity. Raptor codes have linear encoding and decoding complexities. The percentage of the overhead packets goes to zero as B goes to infinity. In practice, the overhead is about 5% for LT codes with file size B ≃ 10000 [30]. This sub-section focuses on applying rateless erasure codes for P2P file transfer instead of designing rateless erasure codes. Hence, we assume the overhead of the applied rateless erasure code is zero for simplicity. We note that if redundancy does not need to be limitless, there are solutions that provide zero overhead [33].

A. The Rateless-Coding-Based Scheme
We propose a rateless-coding-based scheme that constructs the two types of trees in Fig. 6 to distribute the content as did Mutualcast and Extended Mutualcast. The source node first partitions the whole file into B chunks and applies a rateless erasure code to these B chunks producing a potentially limitless number of chunks.
For the depth-1 tree, the source node broadcasts different rateless-coded chunks directly to each peer. For the depth-2 trees, The source node sends different rateless-coded chunks to each peer, and then that peer relays some or all of those chunks to other some or all of the other peers. A key point is that every chunk transmitted by the source is different from every other chunk transmitted by the source. This condition guarantees that all chunks received by a peer are useful (because they are not a repetition of a previously received chunk). Hence, a peer can decode the whole file as long as it receives B coded chunks.
The rateless-coding-based scheme allows peers to download content at different rates with a simpler mechanism than the routing-based approach of Extended Mutualcast. Peers don't have to receive exactly the same chunks to decode the whole file. Hence, the two types of tree structures can be combined as one tree structure with depth 2, but without the constraint that the rate from the peer to its neighbors has to equal the rate from the source to the peer.
The source node sends coded chunks to peer i with rate r s→i = r (1) s→i + r (2) s→i , and peer i relays some of them to peer j (j = i) with rate r i→j ≤ r s→i . Note that the values of r i→j do not even need to be the same for a fixed value of i and different values of j.
Another benefit of applying a rateless coding approach is that it is robust to packet loss in the Internet if we allow some extra rate for each user.
Assuming rateless coding at the source node and constraining the P2P network to include only depth-2 trees as discussed above, the network resource allocation that minimizes WSDT can be obtained by solving the following convex optimization problem.
where r i→i r s→i . The complexity for the interior point method to solve this convex optimization is O((N 2 ) 3.5 ) [29].
For the case of W i = 1, D i = ∞, the optimal resource allocation is, of course, the same as that of Mutualcast. For other cases, we provide a network resource allocation that we have not proven to be optimal. We will see in Section V-E that its performance achieves the lower bound (29) across a wide range of parameterizations.

Consider a P2P network in which peer uplink bandwidth is constrained but
achieves the minimum WSDT with flow rates r i = U s for all i = 1, · · · , N. (This is the case discussed at the end of Section IV.) Otherwise, consider the following water-filling-type solution: where R is chosen such that The potential suboptimality of this approach comes from the subtraction of max k (r k ) on the right side of (54) which does not appear in (28). Note that when max(r k ) ≪ U s + N i=1 U i (this is true for large N),r i is close to r * i corresponding to the lower bound (27).
We now show that the proposed suboptimal network resource allocation ensures that the flow rate to peer i is larger than or equal tor i of (53). Hence, the WSDT for the proposed suboptimal resource allocation is very close to the lower bound to the minimum WSDT for large networks.
First assign the rates for the depth-2 trees with and where c is chosen to be the largest possible value satisfying Plugging (55) (56) into (57) (58), and obtain If c = Us α max(r k ) , then the depth-2 trees have already fully deployed the source node's uplink. The rate assignment for depth-2 trees is the network resource allocation for the rateless-coding-based scheme.
If c = 1, then the depth-2 trees have fully deployed all peers' uplinks, but not the source node's uplink. Hence, we can further deploy the rest of the source node's uplink to construct the depth-1 tree. After constructing the depth-2 trees, the flow rate to peer i is The rest of the source node's uplink is The optimal depth-1 tree can be obtained by the convex optimization The optimal solution to the problem (60) is and where R is chosen such that The complexity of calculating this suboptimal network resource allocation is O(N 2 ). Note that when W i = 1 for all i = 1, · · · , N, this suboptimal network resource allocation is the same as that of Mutualcast, and hence, this network resource allocation is optimal for this case. For general weight settings, this network resource allocation guarantees that the flow rate to peer i is larger than or equal tor i , which is stated in the following theorem.
Theorem 3: For P2P networks with peer uplink constraints but no peer downlink constraints (i.e. D i = ∞), the network resource allocation determined by (55) (56) (59) (61) and (62) ensures that the WSDT N i=1 W i B/r i is less than or equal to the WSDT associated to (53), i.e., N i=1 W i B/r i .
Proof: If c = Us α max(r k ) , the flow rate to peer i is where (67) follows fromr k ≤D k ≤ U s . If c = 1, a feasible solution to problem (60) is For this feasible solution, the total flow rate to peer i with the depth-1 tree and the depth-2 trees is Denote γ = α + (U s − α max(r k )) 1 N k=1r k . We have Some of these steps are justified as follows: • (70) follows from the fact that all uplink resource is deployed; Therefore, γ ≥ 1. Hence, which indicates that this feasible solution r i to the problem (60) provides a WSDT less than or equal to N i=1 W i B/r i . Hence, the network resource allocation determined by (55) (56) (59) (61) and (62) also provides a WSDT less than or equal to N i=1 W i B/r i .

C. Resource Allocation with Peer Downlink Constraints
Now we consider P2P networks with both peer uplink bandwidth constraints and peer downlink bandwidth constraints. The idea of the resource allocation for these P2P networks is the same as that for P2P networks without downlink constraints. The details are provided as follows: i , from Corollary 1, Algorithm 3 provides the optimal network resource allocation.
where R is chosen such that First construct the depth-2 trees with rates in (55) and (56), where c is still chosen to be the largest possible value. However, for general P2P networks, the constraints on c are not only (57) (58), but also After constructing the depth-2 trees, the flow rate to peer i is β i . The used source node's uplink is cα max(r k ). If cα max(r k ) < U s , we can further use the rest of the source node's uplink to distribute content through the depth-1 tree. The optimal resource allocation for the depth-1 tree can be obtained by the convex optimization The optimal solution to the problem (78) is andr where R is chosen such that The complexity of calculating this resource allocation is O(N 2 ).

D. Routing-Based Depth-2 Scheme
So far, this section has provided a family of rateless-coding-based schemes for P2P filetransfer applications. In this subsection, we introduce a routing-based scheme. This routingbased scheme is a further extension to Extended Mutualcast. This scheme also applies the tree structures in Fig. 6 to distribute content. The constraints on the network resource allocation for this scheme are r (1) and where (k 1 , · · · , k N ) is the order in which the peers finish downloading. In the rest of this subsection, we assume the order is (1, · · · , N) for simplicity. These constraints are stricter than those of the rateless-coding-based scheme, and they are introduced to simplify the routing scheme. In particular, given the order of (1, · · · , N) in which peers finish downloading, the proposed routing-based scheme ensures that at any time in the scheme, peer i has all packets received by peers i + 1, · · · , N for all i = 1, · · · , N − 1. This condition can be achievable if the network resource allocation satisfies (81) and (82). For the routing-based scheme, when peer i finishes downloading, the scheme starts to only broadcast the chunks which peer i + 1 hasn't received, called interesting chunks. With this condition, the interesting chunks are also new to peers i+ 2, · · · , N. The details of the routing-based scheme is given in Algorithm

5.
Algorithm 5 Routing-Based Scheme 1: Given the order in which the peers finish downloading. Assume the order is (1, · · · , N) for simplicity.

5:
At the beginning of Step i, peer 1, · · · , i finish downloading. 6: In Step i, only broadcast the chunks which peer i doesn't have, called interesting chunks. Note that all peers i, · · · , N don't contain the interesting chunks.

7:
Distribute interesting chunks along the depth-1 tree and the depth-2 trees according to the network resource allocation.

8:
For the depth-1 tree , the set of chunks sent to peer i contains the set of chunks sent to peer j for i < j.

9:
For the depth-2 tree in Fig. 6(b), the set of chunks from peer i to peer k contains the set of chunks from peer i to peer j for k > j. Peer i only keeps the set of chunks sent to peer i − 1 for i = 2, · · · , N.

10:
The above two chunk selection constraints guarantee that peers i, · · · , N don't contain the interesting chunks in Step i for i = 1, · · · , N.

11:
Until peer i receives all interesting chunks and finishes downloading.

12: end for
The optimal network resource allocation for this routing-based scheme can be obtained by the convex optimization of minimizing N i=1 W i B/r i subject to the constraints (81) (82), nodes' uplink and downlink constraints, and the flow rate expression s→1 . The complexity for the interior point method to solve the problem is O((N 2 ) 3.5 ). For the case of W i = 1 and D i = ∞, the optimal network resource allocation is the same as that of Mutualcast. For the case of W i = 1 or U s + N i=1 U i ≥ N i=1D i , by Theorem 2 and Corollary 1, Algorithm 3 provides the optimal network resource allocation.
For general cases with U s + N i=1 U i < N i=1D i , we provide a suboptimal network resource allocation for this routing-based scheme. Consider the water-filling-type solution in (76).
Without loss of generality, assume thatr 1 ≥ · · · ≥r N , and give the ordering (1, · · · , N) in which the peers finish downloading. First construct the depth-2 trees with rates in (55) and (56), where c is still chosen to be the largest possible value satisfying (57) (58) and (77).
After constructing the depth-2 trees, the effective flow rate to peer i is wherer 0 r 1 . The download rate (used downlink) for peer i is c(αr i +r 1 −r i N k=1r k −r i U i ). Note that the effective flow rate is smaller than the download rate for peer i. This is because peer i only keeps a subset of chunks received from the source node. For this reason, parts of peer i's downlink and the source node's uplink are wasted. The total amount of the wasted uplink is The used source node's uplink is cαr 1 . If cαr 1 < U s , we can further use the rest of the source node's uplink to distribute content through the depth-1 tree. The constraints on the resource allocation for the depth-1 tree are (81), LetŴ i = min k≤i (W k ). LetD i = min k≤i (D k −β k ). A sub-optimal network resource allocation for the depth-1 tree is and The complexity of calculating the suboptimal resource allocation for the routing-based scheme is O(N 2 ).

E. Simulations for the Static Scenario
This subsection provides the empirical WSDT performances of the rateless-coding-based scheme, the routing-based scheme, and compares them with the lower bound to the WSDT.
In all simulations, the file size B is normalized to be 1. This subsection shows simulations for 6 cases of network settings as follows: • Case I: U i = 1, D i = ∞ for i = 1, · · · , N; • Case II: U i = 1, D i = 8 for i = 1, · · · , N; where δ(·) is the indicate function.
Consider small P2P networks with N = 10 peers. The performances of sum download time versus U s for these 6 cases are shown in Fig. 7. The performances of WSDT versus U s with weight W i = i/N (i = 1, · · · , N) are shown in Fig. 8. The performances of WSDT versus U s with weight W i = 1 + δ(i > N/2) (i = 1, · · · , N) are shown in Fig. 9. In all these simulations, the weighted sum download times of the rateless-coding-based scheme and the routing-based scheme achieve or almost achieve the lower bound.
Consider large P2P networks with N = 1000 peers. The performances of sum download time versus U s for these 6 cases are shown in Fig. 10. The performances of WSDT versus U s with weight W i = i/N (i = 1, · · · , N) are shown in Fig. 11. The performances of WSDT versus U s with weight W i = 1 + δ(i > N/2) (i = 1, · · · , N) are shown in Fig. 12. In all these simulations, the weighted sum download times of the rateless-coding-based scheme and the routing-based scheme also achieve or almost achieve the lower bound.
We also simulated for many other network settings and weight settings. In all these simulations, the rateless-coding-based scheme achieves or almost achieves the lower bound to the WSDT. Hence, the lower bound to the WSDT is empirically tight, and the rateless-codingbased scheme has almost-optimal empirical performance. The routing-based scheme also has near-optimal empirical performance. However, for few cases there are clear differences between the performance of the routing-based scheme and the lower bound.

VI. The Dynamic Scenario
The dynamic scenario is allowed to re-allocate the network resource during the file transfer, in particular, whenever a peer finishes downloading, joins into the network, or leaves from the network.

A. A Piece-wise Static Approach to the General Dynamic Case
Wu et al. [27] show that to optimize WSDT the network resource allocation should be dynamic, but may remain constant during any "epoch", a period of time between when one receiver finishes downloading and another finishes downloading. Thus, one optimal solution for the dynamic scenario is "piecewise static".
As an example of how a "piecewise static" dynamic allocation can reduce the WSDT, consider the example for which we studied static allocations in Section III-A. Recall that   this example which is 1.75. For comparison, the optimal static solution, which we saw in Section III-A had an only slightly larger sum download time of 1.8. This simple example shows that a dynamic rate allocation can reduce WSDT. In certain cases the benefit can be significant. Dynamic schemes can reduce the minimum sum download time to approximately half that of the static case, at least when downlink capacities are considered to be infinite [27].

B. A Rateless-coding Approach to Dynamic Allocation
Wu et al. [27] propose a dynamic routing-based scheme. This scheme first deploys all uplink resource to fully support the first K peers until they finish downloading, where K is appropriately chosen. After that, the scheme deploys all uplink resource to fully support the next peer until it finishes downloading, an so forth. Inspired by the work [27], we propose a  dynamic rateless-coding-based scheme for P2P networks with both peer uplink bandwidth constraints and peer downlink bandwidth constraints. This scheme is applicable for dynamic P2P networks in which peers may even join or leave the network.
The key idea of this dynamic rateless-coding-based scheme is similar to that of the dynamic routing-based scheme in [27]. In particular, in each epoch, the scheme deploys all uplink resource to fully support several chosen peers. The details of the dynamic rateless-codingbased scheme are provided in Algorithm 6.
Algorithm 6 provides the structure of the dynamic rateless-coding-based scheme. Because the peers always receive independently generated rateless coded chunks in the static ratelesscode scheme, the dynamic rateless-coding-based scheme is also applicable for dynamic P2P network. As long as a peer receives enough rateless coded chunks 1 , it can decode the whole  Select a set of peers and reset peers' weights. (The peer selection algorithm and the weight setting are addressed in Section VI-C)

4:
Apply the static rateless-coding-based scheme based on the new weights until a peer finishes downloading, joins into the network or leaves from the network. 5: end while file. The key issue is how to set the peers' weights in each epoch. Since the weight setting and the static rateless-coding-based scheme in the current epoch will influence the dynamic scheme in the following epoches, the problem of setting weights is very complicated. We will address this problem in Section VI-C and show that this problem is approximately equivalent to selecting a set of peers to fully support.

C. A Solution to the Ordering Problem
Wu et al. [27] demonstrate that given an order in which the receivers finish downloading, the dynamic allocation (neglecting downlink bandwidth constraints) that minimizes WSDT can be obtained in polynomial time by convex optimization and can be achieved through linear network coding. However, [27]  The simulations for the static scenario in Section V-E show that the WSDT of static rateless-coding-based schemes are very close to that of the lower bound (27,29). Hence, the flow rates r i in (27) are achievable or almost achievable by the static rateless-coding-based (3) (2) (2) (1) In the following discussion, we assume that any set of flow rates r i (i = 1, · · · , N) satisfying the above constraints is achievable by the static rateless-coding-based scheme.
Consider one epoch of the dynamic rateless-coding-based scheme. Suppose there are N peers in the network in the current epoch. Peer i (i = 1, · · · , N) has uplink capacity U i , downlink capacity D i and B − q i B received rateless-coded chunks. Suppose the static rateless-coding-based scheme supports peer i with flow rate r i (i = 1, · · · , N) based on a weight setting. In order to find the optimal weight setting for the current epoch, we study the necessary conditions for the flow rates r i (i = 1, ·, N) to be optimal.
Let us first focus on two peers in the network, say peer 1 and peer 2. The total amount of the uplink resource supporting peer 1 and peer 2 is s = r 1 + r 2 . If the flow rates r i for i = 1, · · · , N is optimal, then the flow rates r 1 and r 2 are also the optimal resource allocation for peers 1 and 2 given that the flow rates r i for i = 3, · · · , N are fixed. Now consider a suboptimal scenario in which the uplink resource with the amount of s serves peers 1 and 2, and the rest of the uplink serves other peers in all of the following epoches. This suboptimal scenario provides a WSDT close to the minimum WSDT if s ≪ U s + N i=1 U i (this is true for large N). Hence, we consider this suboptimal scenario and address the necessary conditions for r 1 and r 2 to be the optimal resource allocation for peers 1 and 2.
If q 1 B r 1 ≤ q 2 B r 2 , then peer 1 finishes downloading before peer 2 does. After peer 1 finishes downloading, peer 1 acts as a source node and hence the total amount of the source nodes' uplink is U s + U 1 , and peer 2 is supported by the uplink resource with the amount of s.
Hence, the WSDT for peers 1 and 2 is and ).
Note that the sign of ∆ 1 r 1 does not depend on r 1 . Hence, the optimal solution to r 1 is either r 1 = r 2 q 1 /q 2 (peer 1 and peer 2 finish at the same time) if −W 1 − W 2 + sW 2 min(s,D 2 ,Us+U 1 ) ≥ 0, or r 1 = min(s,D 1 ) (peer 1 is fully supported) if −W 1 − W 2 + sW 2 min(s,D 2 ,Us+U 1 ) < 0. Similarly, if q 1 B r 1 ≥ q 2 B r 2 , then peer 2 finishes downloading before peer 1 does. The WSDT for peers 1 and 2 is and ).
Note that the sign of ∆ 2 r 2 does not depend on r 2 eithter. Hence, the optimal solution to r 2 is either r 2 = r 1 q 2 /q 1 (peer 1 and peer 2 finish at the same time) if −W 2 −W 1 + sW 1 min(s,D 1 ,Us+U 2 ) ≥ 0, or r 2 = min(s,D 2 ) (peer 2 is fully supported) if −W 2 −W 1 + sW 1 min(s,D 1 ,Us+U 2 ) < 0. Therefore, the optimal resource allocation for peer 1 and peer 2 is achieved when one of the peers is fully supported, or they finish at the same time.

Lemma 4:
Given that the flow rates to peer i for i = 3, · · · , N are fixed, and the amount of uplink resource supporting peer 1 and peer 2 is s. If the optimal resource allocation for peer 1 and peer 2 is achieved when they finish at the same time, then both peer 1 and peer 2 are fully supported.
Proof: LetD + 1 = min(s, D 1 , U s + U 2 ) andD + 2 = min(s, D 2 , U s + U 1 ). According to the above discussion, the optimal resource allocation for peer 1 and peer 2 is achieved when they finish at the same time if and only if s ≥D 1 +D 2 , or ∆ 1 r 1 ≥ 0 and ∆ 2 r 2 ≥ 0. If s ≥D 1 +D 2 , then r 1 =D 1 , r 2 =D 2 , and hence, peers 1 and 2 are fully supported.
Multiply the above two inequalities and obtain Therefor, peer 1 and peer 2 are also fully supported.

Corollary 2:
Given that the flow rates to peer i for i = 3, · · · , N are fixed, and the amount of uplink resource supporting peer 1 and peer 2 is s. The optimal resource allocation for peer 1 and peer 2 is achieved when one of them is fully supported or both of them are fully supported.

Corollary 3:
The optimal network resource allocation in each epoch of a dynamic scenario is only obtained when some peers are fully supported, at most one peer is partially supported, and the other peers are not supported.
Proof: (proof by contradiction) If two peers are partially supported, say peer 1 and peer 2 are partially supported, then the resource allocation for peer 1 and peer 2 is not optimal by Corollary 2.
By Corollary 3, the optimal weight setting in each epoch is W = 1 for the fully supported peers, 0 ≤ W ≤ 1 for the partially supported peer, and W = 0 for other peers. Hence, the problem of optimizing the weight setting is approximately equivalent to selecting a set of peers to fully support.
Now study the necessary conditions for a peer selection to be optimal in a similar way.
Suppose that the amount of uplink resource supporting peer 1 and peer 2 is s, and the flow rates to peer i for i = 3, · · · , N are fixed.
If s < q 1 +q 2 q 1D 1 and s < q 1 +q 2 q 2D 2 , then peer 1 finishes downloading if peer 1 is fully supported, or peer 2 finishes downloading if peer 2 is fully supported. When peer 1 is fully supported, the WSDT for peer 1 and peer 2 is ∆ 1 in (89) with r 1 =D 1 . When peer 2 is fully supported, the WSDT for these two peers is ∆ 2 in (91) with r 2 =D 2 . Hence, we have Therefore, it is better to first fully support peer 1 if W 2 q 2 < W 1 q 1 when s < q 1 +q 2 q 1D 1 and s < q 1 +q 2 q 2D 2 .
and q 1 +q 2 q 1D 1 < s < q 1 +q 2 q 2D 2 , then peer 2 always finishes downloading before peer 1 does. In this case, it is better to first fully support peer 1 if ∆ 2 r 2 > 0, i.e., and q 1 +q 2 q 2D 2 < s < q 1 +q 2 q 1D 1 , then peer 1 always finishes downloading before peer 2 does. In this case, it is better to first fully support peer 1 if ∆ 1 r 1 < 0, i.e., These discussions are concluded in the following theorem.
Theorem 4: Given that the amount of uplink resource supporting peer i and peer j is s, and the flow rates to peer k for k = i, j are fixed. The optimal resource allocation for peer i and peer j is to fully support peer i (i.e., Corollary 4: Consider a peer selection for a dynamic scenario which selects peer i to fully support and peer j to not support. This peer selection is optimal only if Proof: When peer i is fully supported and peer j is not supported, s = r i + r j =D i . Plugging s =D i into (96) and obtain (97).
Define the binary relation ≻ on {1, · · · , N} as i ≻ j if (97) is satisfied. Denote a peer selection as (I, J) where I is the set of fully supported peers and J is the set of unsupported peers. (I, J) is optimal only if i ≻ j for any i ∈ I and j ∈ J. For general P2P networks, finding the optimal (I, J) is computational impossible because the binary relation ≻ is not transitive, which means Define the binary relation on {1, · · · , N} as i j if W i q i ≥ W j q j . The binary relation is an approximation to the binary relation ≻. i j is equivalent to i ≻ j when It can be seen by plugging (98)  Let B−q i B (0 < q i ≤ 1)be the number of chunks that peer i has received for i = 1, · · · , N.

VII. Simulations of the Dynamic Scenario
The dynamic rateless-coding-based scheme is feasible to both static P2P networks and dynamic P2P networks. Consider a type of dynamic P2P networks which any peer leaves from as it finishes downloading, and no peer joins into. This section provides the empirical WSDT performances of the dynamic rateless-coding-based scheme for static P2P networks and dynamic P2P networks with peer leaving, and compares them with those of the the static scenario for static P2P networks. In all simulations, the file size B is normalized to be 1. This section shows simulations for Cases I,II,IV, and VI investigated in V-E.
Consider median-size P2P networks with N = 100 peers. The performances of sum download time versus U s for the 4 cases are shown in Fig. 14. Fig. 15    the static scenario for Cases II, IV and VI, respectively. The WSDT of the dynamic scheme with peer leaving can be as small as 0.71, 0.82, and 0.86 of the minimum WSDT for static scenarios for Cases II, IV and VI, respectively. These largest improvements in percentage of deploying the dynamic scheme is obtained when the source node can directly support tens of the peers.
The performances of WSDT versus U s with weight W i = i/N (i = 1, · · · , N) are shown in Fig. 16. Fig. 17 shows the relative value of the WSDT. For Case I, the sum download times of the dynamic rateless-coding-based scheme and the dynamic scheme with peer leaving can be even less than half of the minimum sum download time for the static scenario for a broad range of the source node uplink U s . This is because the peers with largest weight finish downloading first in the dynamic scheme. The WSDT of the dynamic scheme can be as small as 0.48, 0.49, and 0.58 of the minimum WSDT for the static scenario for Cases II,   and VI, respectively. Note that for Case VI, the WSDT of the dynamic scheme with peer leaving is larger than that of the static scenario for small U s . This is because the peers with larger uplink resource also have larger weight, and they finish downloading and leave from the network first.
The performances of WSDT versus U s with weight W i = 1 + 99δ(i > N/2) (i = 1, · · · , N) are shown in Fig. 18. Fig. 19 shows the relative value of the WSDT. For Case I, the sum download times of the dynamic rateless-coding-based scheme and the dynamic scheme with peer leaving is around half of the minimum sum download time for the static scenario for a broad range of the source node uplink U s . The WSDT of the dynamic scheme can be as  and VI, respectively. The WSDT of the dynamic scheme with peer leaving can be as small as 0.64, 0.64, and 0.63 of the minimum WSDT for the static scenario for Cases II, IV and VI, respectively. Note that for this weight setting, the WSDT of the dynamic scheme with peer leaving is always smaller than that of the static scenario for Case VI. This is because the gain by finishing peers with larger weight is more than than the loss by the peers with larger uplink resource leaving from the network.
Consider large P2P networks with N = 1000 peers. The performances of sum download time versus U s for the 4 cases are shown in Fig. 14. Fig. 15 shows the relative value of the

VIII. Conclusion
This paper considers the problem of transferring a file from one source node to multiple receivers in a P2P network with both peer uplink bandwidth constraints and peer downlink bandwidth constraints. This paper shows that the static scenario can be optimized in polynomial time by convex optimization, and the associated optimal static WSDT can be  achieved by linear network coding. Furthermore, this paper proposes static routing-based and rateless-coding-based schemes that closely approach a new lower bound on performance derived in this paper.
This paper also proposes a dynamic rateless-coding-based scheme, which provides significantly smaller WSDT than the optimal static scheme does. A key contribution for the dynamic scenario is a practical solution to the ordering problem left open by Wu. Our solution is to recast this problem as the problem of identifying the peer weights for each epoch of the "piecewise static" rate allocation.
The deployment of rateless codes simplifies the mechanism of the file-transfer scenario, enhances the robustness to packet loss in the network, and increases the performance (without considering packet overhead). However, there still exist several issues for rateless-coding- The optimal download time region (set of optimal download times) for one-to-many file transfer in a P2P network can be characterized by a system of linear inequalities. Hence, minimizing the WSDT for all sets of peer weights leads to the download time region. The set of peer weights can also be assigned according to the applications. For instances, for a file transfer application with multiple classes of users, assign a weight to each class of users.
For an application with both receivers and helpers, assign weight zero to helpers and positive weights to receivers. Hence, the results of this paper in fact apply directly to one-to-many file transfer applications both with and without helpers.


RegMT System for Machine Translation, System Combination, and Evaluation

We present the results we obtain using our RegMT system, which uses transductive regression techniques to learn mappings between source and target features of given parallel corpora and use these mappings to generate machine translation outputs. Our training instance selection methods perform feature decay for proper selection of training instances, which plays an important role to learn correct feature mappings. RegMT uses L2 regularized regression as well as L1 regularized regression for sparse regression estimation of target features. We present translation results using our training instance selection methods, translation results using graph decoding, system combination results with RegMT, and performance evaluation with the F1 measure over target features as a metric for evaluating translation quality.

Introduction
Regression can be used to find mappings between the source and target feature sets derived from given parallel corpora. Transduction learning uses a subset of the training examples that are closely related to the test set without using the model induced by the full training set. In the context of statistical machine translation, translations are performed at the sentence level and this enables us to select a small number of training instances for each test instance to guide the translation process. This also gives us a computational advantage when considering the high dimensionality of the problem as each sentence can be mapped to many features.
The goal in transductive regression based machine translation (RegMT) is both reducing the computational burden of the regression approach by reducing the dimensionality of the training set and the feature set and also improving the translation quality by using transduction.
We present translation results using our training instance selection methods, translation results using graph decoding, system combination results with RegMT, and performance evaluation with the F 1 measure over target features as a metric for evaluating translation quality. RegMT work builds on our previous regression-based machine translation results (Bicici and Yuret, 2010) especially with instance selection and additional graph decoding capability. We present our results to this year's challenges.
Outline: Section 2 gives an overview of the RegMT model. In section 3, we present our training instance selection techniques and WMT'11 results. In section 4, we present the graph decoding results on the Haitian Creole-English translation task. Section 5 presents our system combination results using reranking with the RegMT score. Section 6 evaluates the F 1 measure that we use for the automatic evaluation metrics challenge. The last section present our contributions.

Machine Translation Using Regression
Let X and Y correspond to the sets of tokens that can be used in the source and target strings, then, m training instances are represented as (x 1 , y 1 ), . . . , (x m , y m ) ∈ X * × Y * , where (x i , y i ) corresponds to a pair of source and target language token sequences for 1 ≤ i ≤ m. Our goal is to find a mapping f : X * → Y * that can convert a source sentence to a target sentence sharing the same meaning in the target language ( Figure 1). Figure 1: String-to-string mapping.
We define feature mappers Φ X : The ridge regression solution using L 2 regularization is found by minimizing the following cost: Two main challenges of the regression based machine translation (RegMT) approach are learning the regression function, h : F X → F Y , and solving the pre-image problem, which, given the features of the estimated target string sequence, h(Φ X (x)) = Φ Y (ŷ), attempts to find y ∈ Y * : y = arg min y∈Y * ||h(Φ X (x)) − Φ Y (y)|| 2 . Preimage calculation involves a search over possible translations minimizing the cost function: (2)

L 1 Regularized Regression
String kernels lead to sparse feature representations and L 1 regularized regression is effective to find the mappings between sparsely observed features.We would like to observe only a few nonzero target coefficients corresponding to a source feature in the coefficient matrix. L 1 regularization helps us achieve solutions close to permutation matrices by increasing sparsity (Bishop, 2006) (page 145). In contrast, L 2 regularized solutions give us dense matrices. W L 2 is not a sparse solution and most of the coefficients remain non-zero. We are interested in penalizing the coefficients better; zeroing the irrele-vant ones leading to sparsification to obtain a solution that is closer to a permutation matrix. L 1 norm behaves both as a feature selection technique and a method for reducing coefficient values.
Equation 3 presents the lasso (Tibshirani, 1996) solution where the regularization term is now the L 1 matrix norm defined as W 1 = i,j |W i,j |. W L 2 can be found by taking the derivative but since L 1 regularization cost is not differentiable, W L 1 is found by optimization or approximation techniques. We use forward stagewise regression (FSR) (Hastie et al., 2006), which approximates lasso for L 1 regularized regression.

Related Work:
Regression techniques can be used to model the relationship between strings (Cortes et al., 2007). Wang et al. (2007) applies a string-to-string mapping approach to machine translation by using ordinary least squares regression and n-gram string kernels to a small dataset. Later they use L 2 regularized least squares regression (Wang and Shawe-Taylor, 2008). Although the translation quality they achieve is not better than Moses (Koehn et al., 2007), which is accepted to be the state-of-the-art, they show the feasibility of the approach. Serrano et al. (2009) use kernel regression to find translation mappings from source to target feature vectors and experiment with translating hotel front desk requests. Locally weighted regression solves separate weighted least squares problems for each instance (Hastie et al., 2009), weighted by a kernel similarity function.

Instance Selection for Machine Translation
Proper selection of training instances plays an important role for accurately learning feature mappings with limited computational resources. Coverage of the features is important since if we do not have the correct features in the training matrices, we will not be able to translate them. Coverage is measured by the percentage of target features of the test set found in the training set. For each test sentence, we pick a limited number of training instances designed to improve the coverage of correct features to build a regression model. We use two techniques for this purpose: (1) Feature Decay Algorithm (FDA), which optimizes source languge bigram coverage to maximize the target coverage, (2) dice. Feature decay algorithms (FDA) aim to maximize the coverage of the target language features (such as words, bigrams, and phrases) for the test sentences. FDA selects training instances one by one updating the coverage of the features already added to the training set in contrast to the features found in the test sentence.
We also use a technique that we call dice, which optimizes source language bigram coverage such that the difficulty of aligning source and target features is minimized. We define Dice's coefficient score as: where C(x, y) is the number of times x and y cooccurr and C(x) is the count of observing x in the selected training set. Given a test source sentence, S U , we can estimate the goodness of a training sentence pair, (S, T ), by the sum of the alignment scores: where X(S U ) stores the features of S U and Y (x) lists the tokens in feature x. The difficulty of word aligning a pair of training sentences, (S, T ), can be approximated by |S| |T | . We use a normalization factor proportional to |T | log |S|.
The details of both of these techniques and further results can be found in (Bicici and Yuret, 2011).

Moses Experiments on the Translation Task
We have used FDA and dice algorithms to select training sets for the out-of-domain challenge test sets used in (Callison-Burch et al., 2011). The parallel corpus contains about 1.9 million training sentences and the test set contain 3003 sentences. We built separate Moses systems using all of the parallel corpus for the language pairs en-de, de-en, enes, and es-en. We created training sets using all of the features of the test set to select training instances. The results given in Table 1 show that we can achieve similar BLEU performance using about 7% of the parallel corpus target words (200,000 instances) using dice and about 16% using FDA. In the out-of-domain translation task, we are able to reduce the training set size to achieve a performance close to the baseline. We may be able to achieve better performance in this out-of-domain task as well as explained in (Bicici and Yuret, 2011).

Graph Decoding for RegMT
We perform graph-based decoding by first generating a De Bruijn graph from the estimatedŷ (Cortes et al., 2007) and then finding Eulerian paths with maximum path weight. We use four features when scoring paths: (1) estimation weight from regression, (2) language model score, (3) brevity penalty as found by e α(l R −|s|/|path|) for l R representing the length ratio from the parallel corpus and |path| representing the length of the current path, (4) future cost as in Moses (Koehn et al., 2007) and weights are tuned using MERT (Och, 2003) on the de-en dev set. We demonstrate that sparse L 1 regularized regression performs better than L 2 regularized regression. Graph based decoding can provide an alternative to state of the art phrase-based decoding system Moses in translation domains with small vocabulary and training set size.

Haitian Creole to English Translation Task with RegMT
We have trained a Moses system for the Haitian Creole to English translation task, cleaned corpus, us-ing the options as described in section 3.1. Moses achieves 0.3186 BLEU on this task. We observed that graph decoding performs better where target coverage is high such that the bigrams used lead to a connected graph. To increase the connectivity, we have included Moses translations in the training set and performed graph decoding with RegMT. RegMT with L 2 regularized regression achieves 0.2708 BLEU with graph decoding and lasso achieves 0.26 BLEU.
Moses makes use of a number of distortion parameters and lexical weights, which are estimated using all of the parallel corpus. Thus, our Moses translation achieves a better performance than graph decoding with RegMT using 100 training instances for translating each source test sentence.

System Combination with RegMT
We perform experiments on the system combination task for the English-German, German-English, English-Spanish, and Spanish-English language pairs using the training corpus provided in WMT'11 (Callison-Burch et al., 2011). We have tokenized and lowercased each of the system outputs and combined these in a single N -best file per language pair. We use these N -best lists for reranking by RegMT to select the best translation model. Feature mappers used are 2-spectrum counting word kernels (Taylor and Cristianini, 2004).
We rerank N -best lists by a linear combination of the following scoring functions: 1. RegMT: Regression based machine translation scores as found by Equation 2.
2. CBLEU: Comparative BLEU scores we obtain by measuring the average BLEU performance of each translation relative to the other systems' translations in the N -best list.
3. LM: We calculate 5-gram language model scores for each translation using the language model trained over the target corpus provided in the translation task.
Since we do not have access to the reference translations nor to the translation model scores each system obtained for each sentence, we estimate translation model performance (CBLEU) by measuring the average BLEU performance of each translation relative to the other translations in the N -best list. Thus, each possible translation in the N -best list is BLEU scored against other translations and the average of these scores is selected as the CBLEU score for the sentence. Sentence level BLEU score calculation avoids singularities in n-gram precisions by taking the maximum of the match count and 1 2|s i | for |s i | denoting the length of the source sentence s i as used in (Macherey and Och, 2007). Table 2 presents reranking results on all of the language pairs we considered, using RegMT, CBLEU, and LM scores with the same combination weights as above. We also list the performance of the best model (Max) as well as the worst (Min). We are able to achieve close or better BLEU scores in all of the listed systems when compared with the performance of the best translation system except for the ht-en language pair. The lower performance in the ht-en language pair may be due to having a single best translation system that outperforms others significantly. This happens for instance when an unconstrained model use external resources to achieve a significantly better performance than the second best model. 2 nd best in Table 2 lists the second best model's performance to estimate how much the best model's performance is better than the rest. BLEU en-de de-en en-es es-en ht-en Min .1064.1572.2174.1976.2281Max .1727.2413 .3708 2 nd best . 1572.2302.3301 .2973.3288 Average .1416.1997.292 .2579.2993Oracle .2529.3305 .4265 .4233 .4336 RegMT .1631.2322  RegMT model may prefer sentences with lower BLEU, which can sometimes cause it to achieve a lower BLEU performance than the best model. This is clearly the case for en-de with 1.6 BLEU points difference with the second best model performance and for de-en task with 1.11 BLEU points difference. Also this observation holds for en-es with 0.74 BLEU points difference and for ht-en with 4.2 BLEU points difference. For es-en task, there is 0.36 BLEU points difference with the second best model and these models likely to complement each other.
The existence of complementing SMT models is important for the reranking approach to achieve a performance better than the best model, as there is a need for the existence of a model performing better than the best model on some test sentences. We can use the competitive SMT model to achieve the performance of the best with a guarantee even when a single model is dominating the rest (Bicici and Kozat, 2010). For competing translation systems in an on-line machine translation setting adaptively learning of model weights can be performed based on the previous transaltion performance (Bicici and Kozat, 2010).

Target F 1 as a Performance Evaluation Metric
We use target sentence F 1 measure over the target features as a translation performance evaluation metric. We optimize the parameters of the RegMT model with the F 1 measure comparing the target vector with the estimate we get from the RegMT model. where BER is the balanced error rate, prec is precision, and rec is recall. The evaluation techniques measure the effectiveness of the learning models in identifying the features of the target sentence making minimal error to increase the performance of the decoder and its translation quality. We use gapped word sequence kernels (Taylor and Cristianini, 2004) when using F 1 for evaluating translations since a given translation system may not be able to translate a given word but can correctly identify the surrounding phrase. For instance, let the reference translation be the following sentence: a sound compromise has been reached Some possible translations for the reference are given in Table 3 together with their BLEU (Papineni et al., 2001) and F 1 scores for comparison. F 1 score does not have a brevity penalty but a brief translation is penalized by a low recall value. We use up to 3 tokens as gaps. F 1 measure is able to increase the ranking of Trans 4 by using a gapped sequence kernel, which can be preferrable to Trans 3 .
We note that a missing token corresponds to varying decreases in the n-gram precision used in the BLEU score. A sentence containing m tokens has m 1-grams, m − 1 2-grams, and m − n + 1 n-grams. A missing token degrades the performance more in higher order n-gram precision values. A missing token decreases n-gram precision by 1 m for 1-grams and by n m−n+1 for n-grams. Based on this observation, we use F 1 measure with gapped word sequence kernels to evaluate translations. Gapped features allows us to consider the surrounding phrase for a missing token as present in the translation.
Let the reference sentence be represented with a b c d e f where a-f, x, y, z correspond to tokens in the sentence. Then, Trans 3 has the form a b x y f, and Trans 4 has the form a c y f. Then, F 1 ranks Trans 4 higher than Trans 3 for orders greater than 3 as there are two consecutive word errors in Trans 3 . F 1 can also prefer a missing token rather than a word error as we see by comparing Trans 4 and Trans 5 and it can still prefer contiguity over a gapped sequence as we see by comparing Trans 5 and Trans 6 in Table 3.
We calculate the correlation of F 1 with BLEU on the en-de development set. We use 5-grams with the F 1 measure as this increases the correlation with 4gram BLEU. Table 4 gives the correlation results using both Pearson's correlation score and Spearman's correlation score. Spearman's correlation score is a better metric for comparing the relative orderings.

Metric
No gaps Gaps Pearson .8793 .7879 Spearman .9068 .8144 Table 4: F 1 correlation with 4-gram BLEU using blended 5-gram gapped word sequence features on the development set.

Contributions
We present the results we obtain using our RegMT system, which uses transductive regression techniques to learn mappings between source and tar-  get features of given parallel corpora and use these mappings to generate machine translation outputs. We also present translation results using our training instance selection methods, translation results using graph decoding, system combination results with RegMT, and performance evaluation with F 1 measure over target features. RegMT work builds on our previous regression-based machine translation results (Bicici and Yuret, 2010) especially with instance selection and additional graph decoding capability.