Delia Ciullo
email: delia.ciullo@inria.fr

Valentina Martina
email: valentina.martina@polito.it

Michele Garetto
email: michele.garetto@unito.it

Emilio Leonardi
email: emilio.leonardi@polito.it

Giovanni Luca Torrisi
email: torrisi@iac.rm.cnr.it

Asymptotic properties of sequential streaming leveraging users' cooperation

Keywords: Stochastic models, cooperative networking, Video-On-Demand modèles stochastiques, réseau coopératif, Vidéo à la Demande

We consider a communication system in which a given digital content has to be delivered sequentially at constant rate to a set of users who asynchronously request it according to a Poisson process. Users can retrieve data: i) from one or more sources that statically store the entire content; ii) from users who have previously requested the content, and contribute (for limited time) a random amount of upload bandwidth to the system. We propose a stochastic fluid framework that allows characterizing the aggregate streaming rate necessary at the sources to satisfy all active requests. In particular, we establish the conditions under which the system becomes asymptotically scalable as the number of users grows. Our theoretical results apply to increasingly popular Video-on-Demand systems exploiting users' cooperation.

Introduction

Online streaming over the Internet is becoming the dominant way of distributing multimedia contents to large populations of users. According to recent forecasts [START_REF]Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update[END_REF], video traffic is expected to exceed 90% of all global consumer Internet traffic by 2016, posing a tremendous challenge to both content providers and network operators.

The current approach to handle the increasing demand of bandwidth-hungry contents in the Internet is based on Content Delivery Networks (CDNs): thanks to the proliferation of proxy servers, contents are "moved" close to the users, significantly reducing the Internet core traffic and improving the perceived quality of service (e.g., the latency). However, any solution based on CDNs has severe limitations in terms of scalability: indeed, the aggregate resources required at data centers (bandwidth/storage/processing), and the corresponding costs incurred by content providers, inevitably scale linearly with users' demand and data volume. Content providers are thus forced to continuously upgrade their Content Delivery Network (CDN) infrastructure, or acquire additional resources from cloud services.

The only scalable solution proposed so far to distribute multimedia contents at massive scale is to exploit users' cooperation: while they retrieve and watch contents, users contribute their resources (bandwidth/storage/processing) to the system, thus offloading the servers [START_REF] Huang | Can Internet Video-on-Demand Be Profitable?[END_REF][START_REF] Huang | Challenges, Design and Analysis of a Large-scale P2P VoD System[END_REF].

On the other hand, streaming architectures which primarily rely on users' cooperation can hardly guarantee the strict quality-of-service requirements of multimedia contents (e.g., in the case of online video a steady download rate no smaller than the playback rate is necessary for a smooth watching experience). For these reasons, user-assisted architectures should be supported by properly dimensioned CDNs (or cloud services) that intervene whenever the resources provided by users are not enough to satisfy the current demand.

In our work, we are specifically interested in characterizing the additional bandwidth that servers must supply (in addition to the bandwidth contributed by the users) to guarantee ideal service to all users (i.e., requests are immediately satisfied and contents can be enjoyed without interruption till the end).

In this paper, we focus on a single content (e.g., a video), and we theoretically analyse the communication system that allows this content to be sequentially delivered to an arbitrarily large number of users, who contribute a random amount of upload bandwidth while they stay in the system. Our main contribution is a stochastic analytical framework that allows us to derive general upper and lower bounds to the additional bandwidth requested from the servers to guarantee constant download rate to all users. In particular, our bounds permit tightly characterizing the asymptotic system behavior as the number of users increases.

We observe that the mathematical formulation of the system considered in this paper has been already proposed in the literature [START_REF] Huang | Can Internet Video-on-Demand Be Profitable?[END_REF][START_REF] Wu | Exploring the Optimal Replication Strategy in P2P-VoD Systems: Characterization and Evaluation[END_REF]. However in previous work authors have resorted to Monte-Carlo approaches to evaluate it. To the best of our knowledge, we are the first to provide an analytical characterization of the solution and rigorously prove its asymptotic properties in the large users limit.

One of our main finding is that the conditions under which the system becomes scalable (i.e., the bandwidth requested from the servers does not increase with the number of users) depend critically on the underlying assumptions about the video request process. In particular, we will consider both the case in which the video request rate is constant, and the case of a newly introduced video whose popularity changes over time, determining a non-homogeneous video request rate. We find that completely different conditions on the system parameters must be satisfied in the above two cases to guarantee the scalability of the video distribution as the system size increases.

As another contribution, we propose a methodology to derive exact estimate of the bandwidth requested from the servers under the assumption that the user upload bandwidth is exponentially (or more generally phase-type) distributed.

Although we restrict our attention to a single video, our theoretical analysis provides the building block to assess the performance of general user-assisted Video-On-Demand (VoD) systems, in which users browse an online catalogue of available videos and asynchronously issue requests to watch a given content. We remark that VoD systems should not be confused with websites offering live streaming service, where users join the distribution of a given TV channel at random points in time, but users connected to the same channel watch the content almost synchronously.

We emphasize that our analysis is orthogonal to two ongoing streams of theoretical research: the one targeting optimal replication strategies and push/pull schemes for content (re)placement [START_REF] Borst | Distributed Caching Algorithms for Content Distribution Networks[END_REF][START_REF] Suh | Push-to-Peer Video-on-Demand system: design and evaluation[END_REF][START_REF] Tan | Optimal Content Placement for Peer-to-Peer Video-on-Demand Systems[END_REF], and the one dealing with practical issues related to chunk scheduling [START_REF] Bonald | Epidemic Live Streaming: Optimal Performance Trade-Offs[END_REF] and peer selection [START_REF] Liu | Performance Bounds for Peer-Assisted Live Streaming[END_REF]. This will become clear later on in the paper.

The paper is organized as follows. In Sect. 2 we describe the system model; in Sect. 3 we present our stochastic fluid framework to characterize the instantaneous bandwidth requested from the servers, as function of the average number of users present in the system at a given time. The obtained results are then exploited in Sect. 4 to analyse the asymptotic behavior of the system as the number of users increases, under both constant and time-varying video popularity. In Sect. 5 we give an overview of the related literature. We conclude the paper in Sect. 6.

Model

System assumptions

In our system users run applications that allow them to browse an online catalogue of videos. When a user selects a video, we assume that the request is immediately satisfied and the selected video can be watched uninterruptedly till the end, i.e., the system is able to steadily provide to the user a data flow greater than or equal to the video playback rate. Users contribute their upload bandwidth to the video distribution, thus they can retrieve part of the video (or even the entire video) from other peers1 , saving servers' resources.

We focus on a given video of size L bytes. We assume that the video is downloaded by each user at constant rate d bytes/s, greater than or equal to the playback rate. Let τ d = L/d be the time needed to download the whole video. In general, the download rate of a peer could be adapted over time, and made dependent on certain peer's characteristics (such as its upload bandwidth). By assuming a constant download rate d at each user we greatly simplify the analysis, while obtaining a conservative prediction with respect to the case in which the download rate can be adapted over time maintaining an average value equal to d.

The amount of upload bandwidth with which users contribute to the redistribution of the video, instead, may or may not be under the control of the system. In our analysis, we assume that the upload bandwidth available at a peer is a random variable with a given distribution. This way, we encompass both the realistic case of users with heterogeneous Internet connections (i.e., ADSL, fiber, LAN) and cross-traffic fluctuations, and the case in which the peer upload bandwidth allocated to the given video is tuned by the system (such as in universal streaming architectures). More specifically, the amount of upload bandwidth with which users contribute at a given time to the redistribution of the considered video is modeled as a random variable U with cumulative distribution function F U () and mean U . The random variables denoting the instantaneous upload bandwidths of the users are assumed to be i.i.d. (independent and identically distributed).

Users dynamics

We need to incorporate in our analysis a model describing how peers join the distribution of the considered video, and when and how they leave the system, stopping to contribute their upload bandwidth. To this aim, we adopt a flexible model that allows to consider a non-stationary video request process. In particular, we assume that the arrival process of requests for the considered video follows a time-varying Poisson process of intensity λ(t). Assuming that at a given time the arrival process is Poisson is reasonable, since users behave independently of each other, and their requests are immediately satisfied. On the other hand, a video (e.g., a typical movie) can be long enough that the rate at which it is requested varies significantly during the playing time, due to daily traffic fluctuations, or rapidly-changing video popularity. By considering a non-homogeneous Poisson process of video requests with time-varying intensity λ(t), we account for quite general non-stationary conditions.

As soon as users issue their request to watch the considered video, they start downloading it and assisting other peers. We define as activity period the duration of the interval during which a peer contributes its upload bandwidth to the distribution of the video, starting from the instant at which the video has been requested. Activity periods of the users are highly heterogeneous, as observed in several measurement studies [START_REF] Huang | Challenges, Design and Analysis of a Large-scale P2P VoD System[END_REF]: some users stop watching the video after a very short time since the beginning, because they realize they are no longer interested in it; most users who decide to watch the video shut down the computer/Internet-TV towards the end of it; some of them keep the application running for prolonged time after the end of the video; those running set-top-boxes can be considered to be always active and serving other peers (as long as the set-top-box keeps a copy of the considered video, contributing to its distribution).

We account for general user behavior assuming that the activity period of a user is described by an arbitrary random variable T with finite mean T and complementary cumulative distribution function G T (). The activity periods of the users are assumed to be i.i.d.

It follows from our assumptions that the number of active users N (t) at time t is distributed as the number of customers in an M/G/∞ queue with time-varying arrival rate, hence it follows a Poisson distribution with time-varying mean N (t) given by

N (t) = t -∞ λ(z)G T (t -z) dz (1)
In our analysis we need to distinguish two classes of active users: those who are still downloading the video, and those who have completed the download (referred to as seeds in the following). The number of downloading peers at a given time instant t, denoted by N d (t), follows a Poisson distribution of mean N d (t) given by

N d (t) = t t-τ d λ(z)G T (t -z) dz (2)
Then, standard properties of Poisson processes allow to say that the number of seeds at time t, N seed (t), follows a Poisson distribution of mean N seed (t) = N (t) -N d (t).

We define as instantaneous system load γ(t) the quantity

γ(t) = d • N d (t) U • N (t) (3)
which is the ratio between the average amount of data rate requested at time t by downloading peers and the average upload rate provided by all active users at time t. Borrowing the terminology adopted in previous work [START_REF] Huang | Can Internet Video-on-Demand Be Profitable?[END_REF][START_REF] Wu | Exploring the Optimal Replication Strategy in P2P-VoD Systems: Characterization and Evaluation[END_REF] we say that at time t the system operates in deficit mode if γ(t) > 1, in balanced mode if γ(t) = 1, and in surplus mode if γ(t) < 1.

We denote by T d = τ d 0 G T (z) dz the average time spent downloading the video by a user. Note that, in general, T d can be shorter than τ d due to peer churn (premature abandons). We define as per-user system load γ p the quantity instantaneous system load at time t f ∼ g f ∈ Θ(g), i.e., f is bounded both above and below by g asymptotically which is the ratio between the average amount of data that is downloaded by a peer, and the average amount of data that a peer is able to offer to other peers. Note that by construction γ p is equal to the (constant) instantaneous system load γ(t) in the case of a time-invariant user arrival process.

γ p = d • T d U • T (4)

Performance metrics

A fundamental goal of a VoD system is to minimize the bandwidth requested from the servers. To save server bandwidth, the system tries to exploit the upload capacity of the peers as much as possible, under the strict constraints of video distribution (i.e., maximum delay, minimum rate). Let S(t) be the random variable denoting the additional bandwidth that the servers must supply at time t to satisfy all active downloads of the considered video. Let F S (w) be the cumulative distribution of S(t). At last, we denote by S(t) the mean of S(t). Since in practice there are multiple videos to be served concurrently by the system, statistical multiplexing arguments suggest that a good design goal is to minimize the mean value S(t) of the servers bandwidth required by a single video. Therefore, this will be the main metric that we will look at in our performance analysis. Table 1 summarizes the notation of our model.

Analysis

Preliminaries

In our analysis we take a snapshot of the system at an arbitrary instant t, and seek to characterize the random variable S(t) denoting the instantaneous bandwidth requested from the servers at time t. This quantity depends on the instantaneous number of downloading users N d (t) and on the instantaneous number of seeds N seed (t). Indeed, let S d (t) be the aggregate bandwidth requested by the downloading users at time t, and let S seed (t) =

Nseed(t) i=1

U i be the aggregate upload bandwidth offered by the seeds at time t. The bandwidth requested from the servers at time t is given by the difference between the bandwidth requested by the downloading users and the bandwidth offered by seeds, provided that such difference is positive:

S(t) = max{0, S d (t) -S seed (t)}. (5)
Under our system assumptions, both N d (t) and N seed (t) have a Poisson distribution, which is completely characterized by its mean. It follows that S(t) is essentially a function of the mean value N d (t) of downloading users at time t and of the mean value N seed (t) of seeds at time t:

Inria S(t) = f N d (t), N seed (t) .
In this section, to simplify the notation, we will drop the dependency of all variables on time, focusing our attention on the random variable

S = f (N d , N seed ) max{0, S d -S seed } (6)
representing the bandwidth requested from the servers in the presence of a generic average number N d of downloaders and a generic average number N seed of seeds (both Poisson distributed). Notice that S completely characterizes the system performance under constant video request rate, since in this case the average number of downloaders/seeds does not vary over time. The extension of the analysis to time-varying video request rate will be done in Section 4.

To analyse variable S in (6), we first observe that S seed = Nseed i=1 U i is simply characterized as a compound Poisson random variable whose moment generating function is

E[e zSseed ] = e N seed (φU (z)-1) (7)
where φ U (z) E[e zU ] is the moment generating function of the peer upload bandwidth U , which is supposed to be known. In particular, the average of S seed is S seed = N seed U . Notice also that S seed is independent from S d . We will denote by F Sseed () its cumulative distribution function.

The main challenge of our analysis is thus the characterization of the bandwidth S d requested by the downloading users.

Universal lower bound

Focusing on S d , we first condition it on the number of downloading users, defining

S d (k) (S d | N d = k) (8)
An easy lower bound to S d (k) can be obtained assuming that the upload bandwidth of each downloading user can always be fully utilized by the system, irrespective of the arrival time of the user into the system. We obtain

S d (k) ≥ max{d, k d - k i=1 U i } ≥ k d - k i=1 U i and thus E[S d (k)] ≥ k(d -U ). Deconditioning with respect to k we obtain E[S d ] ≥ N d (d -U ).
At last, we can obtain a lower bound to the average server bandwidth S requested from the servers, since by construction

S = E[max{0, S d -S seed }] ≥ max{0, E[S d -S seed ]} ≥ max{0, N d (d -U ) -N seed U } = max{0, d N d -U N } (9)
which provides a universal lower bound to S for any chunk distribution scheme. The above lower bound is trivially zero for γ<1, whereas it is equal to d N d -U N for γ ≥ 1.

Upper bounds

An upper bound to the bandwidth requested from the servers can be obtained assuming that all peers download the video chunks sequentially. We observe that many implemented applications inspired by BitTorrent allow also non-sequential chunk dissemination in a swarm-like fashion, although this is typically only enabled within a limited portion of the video to meet the hard delay constraints of individual chunks. Actually, an almost in-order download is the only choice when the download rate d is close to the video playback rate (and the start-up delay is small).

Besides being analytically tractable (as we will see), the sequential download is also simple to implement in a peer-assisted VoD system, as it does not require the complex chunk/peer selection mechanisms which are necessary in BitTorrent-like swarms. In any case, the main point is that the server bandwidth required under sequential download is an upper bound to the bandwidth required by a more general (nonsequential) download scheme.

Below we show how to obtain analytical upper bounds to S, the average of S, in the case of sequential download, obtaining upper bounds valid for any distribution scheme.

We start looking at quantity S d (k) defined in [START_REF] Tan | Optimal Content Placement for Peer-to-Peer Video-on-Demand Systems[END_REF]. We observe that, if all peers download the video sequentially at common rate d, a peer can only redistribute video pieces to peers arrived later on in time.

When there is only one downloading user, we trivially have S d (1) = d. If there are two downloaders, the first arrived makes its entire upload bandwidth available to the second, and we have

S d (2) = d + max{0, d -U 1 } = max{d, 2d -U 1 }
where d represents the external bandwidth necessary to sustain the download of the first arrived peer and max{0, d -U 1 } represents the bandwidth needed to sustain the download of the second arrived peer.

When there are three downloaders, the last arrived can exploit the upload bandwidth of the second plus the residual upload bandwidth of the first, i.e., a total upload rate of U 2 + max{U 1d, 0}. Summing up the download rates needed by the three peers, we obtain

S d (3) = d + max{0, d -U 1 } + max{0, d -U 2 -max{U 1 -d, 0}} = d + max{0, d -U 1 } + max{0, min{2d -U 1 -U 2 , d -U 2 }} = max{S d (2), 3d -U 1 -U 2 } (10)
The last equation descends from the fact that if

d -U 2 < 2d -U 1 -U 2 then d -U 1 > 0 and thus max{0, d -U 1 } + max{0, min{2d -U 1 -U 2 , d -U 2 }} = max{0, d -U 1 , 2d -U 1 -U 2 }.
In general the k-th downloader (assuming downloaders to be numbered in order of arrival) can receive the content from every other downloader preceding it. However, if the preceding peers are not able to fully support the download of the k-th downloader (i.e., if k-1 i=1 U ikd < 0), the missing bandwidth must be provided either by servers or by seeds. We obtain the following recursive equation for S d (k):

S d (k) = d k = 1 max{S d (k -1), kd - k-1 j=1 U j } k > 1 (11)
If we iterate back up to S d (1) we can obtain an explicit expression for S d (k) in terms of the upload bandwidths of peers U i , for i < k, and of the download rate d, as:

S d (k) = d + max 0, d -U 1 , 2d -(U 1 + U 2 ), 3d -(U 1 + U 2 + U 3 ), . . . , (k -1)d - k-1 i=1 U i = d + max 1≤j≤k-1 0, j i=1 (d -U i ) (12)
We emphasize that (12) has already been obtained in [START_REF] Huang | Can Internet Video-on-Demand Be Profitable?[END_REF][START_REF] Wu | Exploring the Optimal Replication Strategy in P2P-VoD Systems: Characterization and Evaluation[END_REF]. However in previous work authors have resorted to Monte-Carlo approaches to evaluate it.

Inria

To proceed in the analysis, we define the auxiliary variable Z d (k):

Z d (k) max 1≤j≤k j i=1 (d -U i ) (13)
where

Z d (k) = 0 if k = 0. Then S d (k) can be expressed in terms of Z d (k -1) according to S d (k) = d + max{0, Z d (k -1)}. (14)
Now, Z d (k) can be regarded as the maximum value (up to time k) reached by a unidimensional random walk with increments X i = d -U i . Thus we can exploit the existing literature on random walks, and especially their application to risk theory, to characterize the distribution of Z d (k).

For our purposes, we need the following classic result, known as the Lundberg's inequality (see for example [START_REF] Asmussen | Applied Probability and Queues[END_REF]).

Lemma 1. (Lundberg inequality) Consider a sequence of i.i.d. variables (X i ) i≥1 , satisfying the fol- lowing three properties: i) E[X 1 ] < 0; ii) P(X 1 > 0) > 0; iii) E[e tX1 ] is finite in a neighborhood of the origin. Define the r.v. Q(k) k i=1 X i , k ≥ 1, Q(0) 0.
Then, denoting θ * the strictly positive solution of E[e θ * X1 ] = 1, which exists unique under i), ii), and iii), we have, for all n ≥ 1:

P( max 1≤k≤n Q(k) > w) ≤ e -θ * w , ∀w ≥ 0. (15)
Remark: condition iii) requires X 1 to be light-tailed (i.e., to have a tail that decays at least exponentially fast).

For completeness, in Appendix A we report a proof of Lemma 1 based on a Martingale approach. Lundberg inequality can be generalized and adapted to our context, to obtain an upper bound to P(S d > w): Theorem 1. Assume the following properties hold for

U : i) U > 0, ii) E[e tU ] is finite in a neighborhood of the origin, iii) F U (w) > 0 for every w > 0. For ǫ ∈ [(U -d) + , U ), define A d -U + ǫ (note that max{0, d -U } ≤ A < d).
Let θ * be the unique strictly positive solution of the equation E[e θ(d-U -A) ] = 1. For any w ≥ 0, it holds

P(S d > w) ≤ min C 2 e -θ * (w-d) , C 3 w ≥ d C 1 0 ≤ w < d,
where

C 1 1 -e -N d , C 2 e -θ * A e -N d (e N d e θ * A -N d e θ * A -1) and C 3 1 -e -N d -N d e -N d .
A detailed proof of Theorem 1 is reported in Appendix B. Observe that, when d < U , we can obtain an upper bound on P(S d > w) applying the Lundberg inequality to P(S d (k) > w) for any k. Instead, when d > U , since E[d -U i ] > 0, we cannot apply Lundberg inequality directly to P(S d (k) > w). Therefore we need to define an auxiliary sequence of random variables, tightly related to S d (k), on which Lundberg bound can be applied. Then we can derive a bound on P(S d (k) > w). The approach of the auxiliary sequence of variables is generalized also to the case d < U , to obtain a possibly tighter upper bound.

Exploiting the result in Theorem 1, we derive an upper bound to the average bandwidth S d requested by the downloading peers: Corollary 1. The average bandwidth requested by downloading peers satisfies:

S d ≤ C 1 d + C 3 (w * -d) + C 3 /θ * if C 2 > C 3 C 1 d + C 2 /θ * o.w. ( 16
)
where w *

1 θ * log C2 C3 + d.
The proof of Corollary 1 can be found in Appendix C. Remark: note that (1) and ( 16) hold under an arbitrary choice of ǫ ∈ [(Ud) + , U ). The tightest bound is obtained by minimizing the expressions (1) and ( 16) with respect to ǫ.

From Corollary 1 it immediately follows that the average bandwidth requested by downloaders is finite even when the average number of downloaders diverges (i.e., N d → ∞), provided that d < U . Indeed, by selecting ǫ = Ud (and thus A = 0), we obtain

S d ≤ d + 1 θ * , being θ * the unique positive solution to E[e θ(d-U ) ] = 1.
By taking into account also the impact of the seeds, we obtain an upper bound to the average bandwidth requested from the servers, according to (6):

Theorem 2. The following bound holds for the average bandwidth requested from the server:

S ≤ min C 1 F Sseed (d)d+C 2 e θ * d θ * E[e -θ * Sseed ], C 1 F Sseed (d)d+C 3 2 θ * +w * -S seed +E[e θ * Sseed ]e -θ * w * /θ * (17) where w * = 1 θ * log C2 C3 + d.
The proof of Theorem 2 is reported in Appendix D.

Exact solutions

In this section we describe a methodology to obtain an exact solution of ( 12) when the upload bandwidth distribution is exponentially or phase-type distributed. The first step consists in deriving an integral equation satisfied by the cumulative distribution function of the quantity Z d (k) defined in [START_REF] Qiu | Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks[END_REF]. Observe that Z d (k) can be written as:

Z d (k) = max d -U 1 , max 2≤j≤k j i=2 (d -U i ) + d -U 1 .
Now since the U i are i.i.d., we can permute the indices i of (U i ) i≥1 , obtaining a new random variable Ẑd (k) defined as

Ẑd (k) max d -U k , max 1≤j≤k-1 j i=2 (d -U i ) + d -U k
which has the same distribution of Z d (k). Note that Ẑd (k) can be written as:

Ẑd (k) = max d -U k , Ẑd (k -1) + d -U k . ( 18
)
Denoting by F Z (w | k) the cumulative distribution function of Z d (k) (and thus of Ẑd (k)), we have:

F Z (w | k) = P( Ẑd (k) ≤ w) = P max d -U k , Ẑd (k -1) + d -U k ≤ w (19)
We now condition on the value assumed by X k d -U k :

F z (w | k) = ∞ -∞ P max X k , Ẑd (k -1) + X k ≤ w | X k = α dF X k (α) = w -∞ P Ẑd (k -1) + α ≤ w dF X k (α) = w -∞ F Z (w -α | k -1) dF X k (α). (20)

Inria

Observing that by construction F Z (α | 1) = F X k (α), from (20) we get:

F Z (w | k) = w -∞ F Z (w -α | k -1) dF Z (α | 1) (21)
Explicit solutions of the above functional equation can be given when the peer upload bandwidth is phase-type distributed. In particular, in the case of peer upload bandwidth exponentially distributed, we obtain (see Appendix E):

F Z (w | k) = F Z (d | k)e w-d U I w<0 + I w>kd + e w-d U k i=0 (-1) i F Z (d | k -i) (w -id) i U i i! e -id/U I id≤w≤kd , (
P(S d (k) > w) = 1 -F Z (w -d | k -1) if w ≥ d 1 if w < d (23)
Finally, we can derive the average server bandwidth S d requested by the downloading peers, and the average server bandwidth S requested from the servers.

In the case d < U , since the sequence of increasing random variables Z d (k) converges w.p.1 to a finite random variable Z d (∞) (as direct consequence of Lemma 1), we can find the distribution of Z d (∞) from the stationary version of (21). We state this result in the following theorem.

F Z (w | ∞) = w -∞ F Z (w -α | ∞) dF X (α) (24)
When the U k are exponentially distributed the solution of (24) can be obtained following the approach described in Appendix E, obtaining:

F Z (w | ∞) = F Z (d | ∞)e w-d U I w<0 + F Z (d | ∞)e w-d U ∞ i=0 (-1) i (w -id) i U i i! e -id/U I w>id where F Z (d | ∞) = lim k→∞ 1 k i=0 (-1) i [(k-i)d] i i! e (k-i)d/U
Notice that Z d (∞) provides a tight bound to the distribution of the server bandwidth requested by a large number of downloading users, when the system operates in the surplus mode. We emphasize that the approach described in Appendix E can be generalized in a rather straightforward way to obtain the exact solution of ( 21) and (24) under any phase-type distribution of peers upload bandwidth. On this regard, recall that any distribution whose moment generating function is finite in a neighborhood of the origin (i.e., it is light-tailed) can be approximated by a phase-type distribution with an arbitrary degree of accuracy (see [START_REF] Asmussen | Applied Probability and Queues[END_REF]Ch.4]). Thus the methodology presented in this section can be applied to derive analytical approximations of the bandwidth requested from the servers in the case in which the peer upload bandwidth is arbitrarily distributed.

As a concluding remark, we wish to emphasize that upper bounds obtained in Section 3.3 and exact solutions presented in this section are complementary tools for the analysis of peer-assisted VoD systems properties. Indeed, the upper bounds presented in Section 3.3 provide very general and easy-to-handle expressions from which we can derive qualitative/asymptotic properties of the system. The methodology described in this section provides more accurate estimates (which are exact for phase-type distributions) of the bandwidth requested from the servers, but are computationally more expensive, especially for large numbers of users.

Numerical Illustration

We provide a graphical illustration of our results considering a scenario in which the video request rate is constant, and the average activity period of the users is twice the time spent downloading the movie, representing users who tend to keep their application/devices active after watching the movie. Notice that in this case N d = N seed . We normalize the parameters d = 1 and T d = 1, and thus we set T = 2. UB -γ p = 0.9 exact -γ p = 0.9 UB -γ p = 0.7 exact -γ p = 0.7 lower bounds Figure 1 reports on a log-log scale the average server bandwidth S as function of the average number of users N , for different values of the per-user system load γ p . The peer upload bandwidth is exponentially distributed with mean U = 1/(2γ p ). We compare the upper bound (17) (labeled UB) with the exact solution presented in Section 3.4. We also report for γ p > 1 the lower bound [START_REF] Bonald | Epidemic Live Streaming: Optimal Performance Trade-Offs[END_REF].

Comparing the upper bound with the exact solution, we observe that, although the bound can be pessimistic up to a factor about 4, the bound captures well the qualitative behavior of the exact curve.

As expected, in the deficit mode (γ p > 1) the server bandwidth diverges for increasing number of users. Moreover, the upper bound becomes asymptotically tight to the lower bound, which grows linearly with the number of users. This interesting property will be proved in the next section.

In the surplus mode, instead (γ p < 1), the server bandwidth achieves a maximum for a given number of users, and then decreases to zero as N → ∞. This is another fundamental asymptotic property of our system, which will be proved in the next section.

To show the impact of peer bandwidth heterogeneity, we consider the same scenario as before, keeping the load fixed to γ p = 0.9 (surplus mode), and varying the coefficient of variation (CV) of the upload bandwidth distribution of the users. In particular, we assume that the upload bandwidth is distributed according to a second-order hyper-exponential distribution with balanced means, which could well describe the situation in which we have many peers with low upload bandwidth (e.g., behind ADSL lines) and few peers with large upload bandwidth (e.g., connected with fiber or LAN). We observe the strong impact of the CV on the resulting server bandwidth. Since γ p = 0.9 < 1 (surplus mode), we expect that S goes to zero as N → ∞ (as predicted by Theorem 4 in the next section). However, it is interesting to observe that the maximum value of S is achieved for quite large number of users (in the order of thousands) for large values of the CV. Again, the analytical upper bound follows well the qualitative behavior of the system, in all considered cases.

Asymptotic analysis

The numerical results reported in the previous section suggest interesting asymptotic properties of our system as the number of users grows large. In this section, we will precisely characterize how the average bandwidth requested from the servers scales as we increase the number of users, i.e., when λ → ∞.

We will first consider the simpler case in which the video request rate is constant, i.e., λ(t) = λ, referred to as time-invariant video popularity. Then, we will analyse a scenario in which the video request rate varies over time, referred to as time-varying video popularity. We will see that, while in the deficit mode the above two cases scale in a similar way, in the surplus mode the asymptotic system behavior is radically different. In particular, different conditions on the system parameters must be satisfied in the two considered scenarios to achieve scalability as the users population size increases.

Time-invariant video popularity

The asymptotic system behavior in this case is characterized by the following fundamental result: Theorem 4. Assume U not constant. Then, as λ → ∞, the following asymptotic regimes hold for any chunk distribution scheme: For γ p < 1 and, additionally T > T d , the average bandwidth requested from the servers tends to zero, i.e., lim λ→∞ S = 0. For γ p > 1, the average bandwidth requested from the servers grows linearly with the number of users. In particular, lim λ→∞ S

(N d d-U N ) = 1.

RR n°8183

The proof of Theorem 4 can be found in Appendix F. Notice that for γ p > 1 the upper bound becomes asymptotically tight to the lower bound [START_REF] Bonald | Epidemic Live Streaming: Optimal Performance Trade-Offs[END_REF], as observed in the numerical example in Figure 1.

Theorem 4 suggests that, for very popular contents (large number of users concurrently watching the same video), a peer-assisted video distribution is scalable, provided that the system is in surplus mode (i.e., γ p < 1) and users stay in the system, on average, for a time larger (by an arbitrarily small constant) than the time needed to download the whole video (T > T d ). This holds for any chunk distribution scheme, including the simple sequential scheme.

In the deficit mode, i.e., γ p > 1, the system is obviously not scalable, since an additional bandwidth at least equal to the bandwidth deficit (N d d-U N ) must be provided by servers. However, in this case there is (asymptotically) no gain in adopting a non-sequential chunk delivery scheme with respect to the simple sequential download. Indeed, as the number of users grows large, the system in which users download the content sequentially performs as well as an ideal (unfeasible for VoD applications) system in which the content can be downloaded in arbitrary order.

Time-varying video popularity

In this section we extend the asymptotic analysis to a scenario in which the video request rate varies over time, while still letting the average number of users downloading the video grow to infinity. In particular, we assume that the arrival process of requests for the considered video follows an non-homogeneous Poisson process with intensity λ(t) = Λq(t), where q(t) is a shaping function modeling the popularity evolution of a video inserted into the catalogue at time t = 0.

Without loss of generality, we assume q(t) to be an integrable function such that ∞ 0 q(t) dt = 1 and q(t) = 0 for all t < 0. By so doing, Λ becomes equivalent to the average overall number of times that the video is requested during its lifetime in the system. The asymptotic analysis is then performed by letting Λ → ∞.

We characterize the system performance in terms of the average amount of data V that servers must supply to satisfy all requests for the considered video:

V = ∞ 0 S(t) dt.
Our main results are summarized in the following: Theorem 5. Consider a bounded, integrable popularity function q(t) having finite mean, i.e., ∞ 0 tq(t) dt < ∞. If d < U , we distinguish the following three cases:

• if q(t) has an heavy tail, i.e., ∃ T 0 , K > 0 and α > 1 such that q(t) < Kt -(α+1) for t > T 0 , then the average amount of data requested from the servers is V = O(Λ 1/α ) as Λ → ∞.

• if q(t) has an exponential tail, i.e., ∃ T 0 , K > 0 and α > 0 such that q(t) < Ke -αt for t > T 0 , then V = O(log Λ) as Λ → ∞.

• if q(t) has finite support, i.e., ∃ T 2 > 0 such that q(t) = 0 for all t > T 2 , then

V = O(1) as Λ → ∞.
On the other hand, when d > U , V grows linearly with Λ for any function q(t), i.e., V = Θ(Λ), Λ → ∞.

A detailed proof of Theorem 5 is reported in Appendix G. In the following we just sketch the rationale of the proof.

First of all, from (2) we compute the following upper bound to the average number of downloading users at time t,

N d (t) ≤ Λ t (t-τ d ) + q(z) dz (25)
Inria obtained considering the worst case in which users remain in the system at least for a period equal to the downloading time τ d (i.e., G T (z) = 1 for all z < τ d ). Given the bound on S(t) in ( 17), we compute V as the sum of two contributions:

V = T1 0 S(t) dt + ∞ T1 S(t) dt,
where T 1 is a threshold defined as T 1 max{t : N d (t) > 1}. Note that the average number of downloaders N d (t) can be arbitrarily large for t ∈ (0, T 1 ), while this number becomes negligible for t > T 1 . When d < U , we found that the first integral is bounded above by T 1 . When the popularity distribution has an exponential decreasing tail, the most significative contribution is given by the first integral (i.e., by T 1 ) which scales logarithmically with Λ. When the popularity distribution is heavy-tailed, the two integrals give the same contribution, asymptotically.

We emphasize that the results in Theorem 5 differ substantially from those stated in Theorem 4. Indeed, in the case of time-invariant video popularity the scalability of the system is governed by the system load γ p . Notice that in this case the system can be in surplus mode (γ p < 1) even when d > U , since the system can also efficiently exploit the upload bandwidth offered by the seeds. In the case of time-varying video popularity, instead, the scalability of the system is governed by the relationship between U and d: if d > U , the system cannot scale to large number of users, no matter how long users stay available in the system as seeds, after watching the movie. If d < U , the scalability of the system depends on the tail behavior of the popularity shape function: the faster the tail decreases, the smaller the data volume requested from the servers. In particular we have shown that, at least in the case of a popularity function with finite support, the data volume requested from servers remains bounded as Λ → ∞. More in general, the data volume V is sublinear in Λ.

Related Work

We restrict ourselves to mentioning theoretical performance studies of content distribution systems leveraging users' cooperation, which are closely related to our work.

Stochastic fluid models for classical peer-assisted file distribution systems, such as Bit-Torrent (in which the content can be enjoyed by users only after completing the download), have been proposed for both transient and steady-state regimes [START_REF] Yang | Service Capacity of Peer to Peer Networks[END_REF][START_REF] Qiu | Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks[END_REF], but they are not directly applicable to streaming systems. In [START_REF] Parvez | Analysis of BitTorrent-like Protocols for On-Demand Stored Media Streaming[END_REF], authors adapt the fluid model in [START_REF] Qiu | Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks[END_REF] to VoD systems, investigating the impact of different piece selection policies (rarest-first and in-order) on download latency and startup delay, in the case of users with homogeneous bandwidth. In contrast to [START_REF] Parvez | Analysis of BitTorrent-like Protocols for On-Demand Stored Media Streaming[END_REF], we focus on the scalability of VoD systems with strict service guarantees and heterogeneous user upload bandwidths.

A stochastic fluid approach to analyse peer-assisted video distribution has been proposed in [START_REF] Kumar | Stochastic Fluid Theory for P2P Streaming Systems[END_REF] in the context of live streaming, in which (heterogeneous) peers download and playback content synchronously. Here we apply the stochastic fluid approach to VoD streaming systems, whose dynamics are quite different from live streaming, since users can watch the video asynchronously.

The mathematical formulation [START_REF] Yang | Service Capacity of Peer to Peer Networks[END_REF] for the server bandwidth needed by a VoD system based on sequential delivery, appeared in [START_REF] Huang | Challenges, Design and Analysis of a Large-scale P2P VoD System[END_REF], in which authors resort to a Monte Carlo approach to get basic insights into the system behavior (like surplus and deficit modes).

The same formulation [START_REF] Yang | Service Capacity of Peer to Peer Networks[END_REF] has been considered in [START_REF] Wu | Exploring the Optimal Replication Strategy in P2P-VoD Systems: Characterization and Evaluation[END_REF], where authors explore by simulation the effectiveness of different replication strategies to minimize the server load in the slightly surplus mode, as well as distributed replacement algorithms to achieve it. To the best of our knowledge, we are the first to analytically study the stochastic process [START_REF] Yang | Service Capacity of Peer to Peer Networks[END_REF], establishing its connection with random walks and risk theory.

An alternative analysis of equation ( 12), based on a second-order gaussian approximation, has been proposed in [START_REF] Ciullo | Performance Analysis of Nonstationary Peer-assisted VoD Systems[END_REF] to obtain an efficient methodology to evaluate the performance of both stationary and non-stationary systems.

In [START_REF] Fan | Balancing Throughput, Robustness, and In-Order Delivery in P2P VoD[END_REF], a per-chunk capacity model is developed to show the tradeoff that exists between system throughput, sequentiality of downloaded data and robustness to heterogeneous network conditions. Optimal content placement strategies to maximize the upload capacity of (homogeneous) set-top-boxes (and thus minimize the servers workload) in VoD systems have been recently investigated in [START_REF] Tan | Optimal Content Placement for Peer-to-Peer Video-on-Demand Systems[END_REF] under manyuser asymptotic.

Conclusion

We have developed a stochastic fluid methodology to derive analytical upper bounds to the bandwidth requested from the servers in an ideal streaming system leveraging the upload bandwidth of the users, studying the performance achieved by the simple sequential distribution scheme. Our bounds hold under the only assumption that the upload bandwidth distribution of peers is light-tailed. We have also proposed an analytical methodology to exactly estimate the bandwidth requested from servers when user upload bandwidth is phase-type distributed. Besides being analytically tractable, the simple sequential delivery scheme is also an attractive solution in real systems, for two main reasons: i) it allows users to immediately start watching the requested movie; ii) it is simple to manage and control. Moreover, we have proved that the sequential delivery scheme leads to an asymptotically optimal exploitation of the peers' upload bandwidths as the number of users grows large. Indeed, our bounds tightly characterize the asymptotic performance of large-scale peer-assisted content distribution systems employing both sequential and non-sequential delivery schemes.

B Proof of Theorem 1

Define X i d -U i -A, for all i ≥ 1 and Q(k) k i=1 X i . Since max{0, d -U } ≤ A < d we have E[X i ] < 0 and P(X i > 0) > 0.
Note that by [START_REF] Qiu | Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks[END_REF], Z d (0) = 0, while, for k > 0, it holds:

Z d (k) = max 1≤j≤k j i=1 (d -U i ) ≤ max 1≤j≤k j i=1 (d -U i ) + (k -j)A = max 1≤j≤k Q(j) + kA. For k > 0 P(Z d (k) > w + kA)≤ P( max 1≤j≤k Q(j) + kA > w + kA) ≤ e -θ * w ,
and then

P (Z d (k) > w) ≤ e -θ * w e θ * kA . By (14), S d (k) = d+max{0, Z d (k-1)}. It is easy to prove that the event {max{0, Z d (k -1)} > w ′ } is equal to the event {Z d (k -1) > w ′ }, for all w ′ ≥ 0. Therefore, P(S d (k) > w) = P (Z d (k -1) > w -d)
for all w ≥ d and P(S d (k) > w) = 1 for w < d. Thus, for w < d it holds

P (S d > w) = ∞ k=1 P(S d (k) > w)P(N d = k) = ∞ k=1 P(N d = k) = 1 -P(N d = 0) = 1 -e -N d = C 1 .
On the other hand, for w ≥ d, we have

P (S d > w) = ∞ k=1 P(S d (k) > w)P(N d = k) = ∞ k=1 P (Z d (k -1) > w -d) N d k e -N d k! ≤ P (Z d (0) > w -d) N d e -N d + e -θ * (w-d) e -N d e -θ * A ∞ k=2 (e θ * A N d ) k k! = e -θ * (w-d) e -N d e -θ * A ∞ k=2 (e θ * A N d ) k k! = C 2 e -θ * (w-d) .
Moreover, if w ≥ d, we can get another simple bound as follows:

P (S d > w) = ∞ k=1 P(S d (k) > w)P(N d = k) = ∞ k=1 P (Z d (k -1) > w -d) N d k e -N d k! = ∞ k=2 P (Z d (k -1) > w -d) N d k e -N d k! ≤ ∞ k=2 N d k e -N d k! = 1 -e -N d -N d e -N d = C 3 . Therefore P(S d > w) ≤ min C 2 e -θ * (w-d) , C 3 w ≥ d C 1 0 ≤ w < d

C Proof of Corollary 1

We compute the average bandwidth requested by downloading users:

S d = ∞ 0 P (S d > w) dw ≤ d 0 C 1 dw + ∞ d min C 2 e -θ * (w-d) , C 3 dw,

Inria

where the last inequality follows from Theorem 1. The quantity min C 2 e -θ * (w-d) , C 3 is equal to C 3 if w < w * = (1/θ * ) log C2 C3 + d. Thus, if w * > d we have:

S d ≤ d 0 C 1 dw + w * d C 3 dw + ∞ w * C 2 e -θ * (w-d) dw = C 1 d + C 3 (w * -d) + C 2 e -θ * (w * -d) /θ * = C 1 d + C 3 (w * -d) + C 3 /θ *
where the last equality comes from the fact that C 3 = C 2 e -θ * (w * -d) by the way we defined w * .

On the other hand, if w * ≤ d, we have:

S d ≤ d 0 C 1 dw + ∞ d C 2 e -θ * (w-d) dw = C 1 d + C 2 /θ * .
Note that w * > d if, and only if, C 2 > C 3 . Thus, we have:

S d ≤ C 1 d + C 3 (w * -d) + C 3 /θ * if C 2 > C 3 C 1 d + C 2 /θ * o.w.

D Proof of Theorem 2

We compute the average bandwidth requested from the servers (S). For every x > 0 we have:

P(S > x) = P(S d > S seed + x) = ∞ 0 P(S d > w + x|S seed = w) dF Sseed (w) ≤ max{0,d-x} 0 C 1 dF Sseed (w) + ∞ max{0,d-x} dF Sseed (w) min{C 3 , C 2 e -θ * (w-d+x) } ≤ max{0,d-x} 0 C 1 dF Sseed (w) + ∞ 0 dF Sseed (w)C 2 e -θ * (w-d+x) = C 1 F Sseed (max{0, d -x}) + C 2 E[e -θ * Sseed ]e -θ * (x-d) = C 1 F Sseed (d -x) + C 2 E[e -θ * Sseed ]e -θ * (x-d) Note that the quantity F Sseed (max{0, d -x}) is always equal to F Sseed (d -x): indeed if d -x ≤ 0, then F Sseed (d -x) = F Sseed (0) = 0, since S seed is a positive random variable. Finally, S = ∞ 0 P(S > x) dx ≤ ∞ 0 C 1 F Sseed (d -x) dx + ∞ 0 C 2 E[e -θ * Sseed ]e -θ * (x-d) dx = d -∞ C 1 F Sseed (y) dy + ∞ 0 C 2 E[e -θ * Sseed ]e -θ * (x-d) dx ≤ C 1 F Sseed (d)d + C 2 e θ * d E[e -θ * Sseed ]1/θ * (26)
Observe that, if C 2 ≫ C 3 , i.e., w * ≫ d, the above bound becomes weak. Thus, we obtain a tighter bound in this case using a different approach:

S = ∞ 0 [0,∞) P (S d > w + x)F Sseed (dw)dx = [0,∞) F Sseed (dw) ∞ w P (S d > z)dz = [0,d] F Sseed (dw) ∞ w P (S d > z)dz + (d,∞) F Sseed (dw) ∞ w P (S d > z)dz = [0,d] F Sseed (dw) d w P (S d > z)dz + ∞ d P (S d > z)dz + (d,∞) F Sseed (dw) ∞ w P (S d > z)dz ≤ [0,d] F Sseed (dw) C 1 (d -w)+ ∞ d min{C 3 , C 2 e -θ * (z-d) }dz + (d,∞) F Sseed (dw) ∞ w min{C 3 , C 2 e -θ * (z-d) }dz = C 1 F Sseed (d)d -C 1 [0,d] wF Sseed (dw) + F Sseed (d) ∞ d min{C 3 , C 2 e -θ * (z-d) }dz + (d,∞) F Sseed (dw) ∞ w min{C 3 , C 2 e -θ * (z-d) }dz = C 1 F Sseed (d)d -C 1 [0,d] wF Sseed (dw) + F Sseed (d) w * d min{C 3 , C 2 e -θ * (z-d) }dz + F Sseed (d) ∞ w * min{C 3 , C 2 e -θ * (z-d) }dz + (d,w * ] F Sseed (dw) ∞ w min{C 3 , C 2 e -θ * (z-d) }dz + (w * ,∞) F Sseed (dw) ∞ w min{C 3 , C 2 e -θ * (z-d) }dz = C 1 F Sseed (d)d -C 1 [0,d] wF Sseed (dw) + C 3 (w * -d)F Sseed (d) + C 2 e -θ * (w * -d) θ * F Sseed (d) + (d,w * ] F Sseed (dw) ∞ w min{C 3 , C 2 e -θ * (z-d) }dz + C 2 e θ * d θ * (w * ,∞) e -θ * w F Sseed (dw) (27) Note that, if w < w * : ∞ w min{C 3 , C 2 e -θ * (z-d) }dz = w * w min{C 3 , C 2 e -θ * (z-d) }dz + ∞ w * min{C 3 , C 2 e -θ * (z-d) }dz = C 3 (w * -w) + C 2 e -θ * (w * -d) θ * (28)
Combining ( 27) e (28) we obtain: In this section we derive the solution of (21) for the case in which the bandwidths U are exponentially distributed. The same approach can be extended to the case in which the bandwidth U has a general phase-type distribution.

S ≤ C 1 F Sseed (d)d -C 1 [0,d] wF Sseed (dw) -C 3 F Sseed (d)d+
-C 3 (d,w * ] wF Sseed (dw) = -C 3 w(F Sseed (w) -1)| w * d -+ w * d (1 -F Sseed (w)) dw = -C 3 w * (F Sseed (w * ) -1) -(F Sseed (d -) -1) • d + ∞ 0 (1 -F Sseed (w)) dw - d 0 (1 -F Sseed (w)) dw - ∞ w * (1 -F Sseed (w)) dw ≤ C 3 w * -w * F Sseed (w * ) + F Sseed (d)d -d -S seed + d + ∞ w * (1 -F Sseed (w)) dw ≤ C 3 w * -w * F Sseed (w * ) + F Sseed (d)d -S seed + E[e θ * Sseed ]
When the bandwidth is exponentially distributed we have: dF Z (α | 1) = 1 U e -d-α U I α≤d dα. Thus, from (20), we have

F Z (w | k) = w -∞ F Z (w -α | k -1) 1 U e -d-α U I α≤d dα = min{w,d} -∞ F Z (w -α | k -1) 1 U e -d-α U dα (30)
If w < d, making the substitution y = wα in the integral, we obtain:

F Z (w | k) = e w-d U U ∞ 0 F Z (y | k -1)e -y U dy.
Note that the integrand function does not depends on w, thus the whole integral can be regarded as a constant. Moreover, notice that

1 U ∞ 0 F Z (y | k -1)e -y U dy = F Z (d|k). (31)
Thus, it holds:

F Z (w | k) = e w-d U F Z (d | k) ∀w ≤ d (32)
Now consider equation (30) when d ≤ w ≤ 2d:

F Z (w | k) = e w-d U U ∞ w-d F Z (y | k -1)e -y U dy = e w-d U U ∞ 0 F Z (y | k -1)e -y U dy -e w-d U U w-d 0 F Z (y | k -1)e -y U dy. (33)
Note that the first term in the sum is equal to e

w-d U F Z (d | k).
For the second integral, since d ≤ w ≤ 2d, variable y is such that 0 < y < wd < d. Thus, using (31) we can write: (

) RR n°8183 34
Thus, for d ≤ w ≤ 2d, we obtain

F Z (w | k) = e w-d U F Z (d | k) - (w -d) U e w-2d U F Z (d | k -1).
F Z (w | k) = e w-d U F Z (d | k)- (w -d) U e w-2d U F Z (d | k-1)+ (w -2d) 2 2U 2 e w-3d U F Z (d | k-2) 2d ≤ w ≤ 3d (

F Proof of Theorem 4

By virtue of Theorem 2, we have

S ≤ C 1 F Sseed (d)d + C 2 e θ * d E[e -θ * Sseed ]/θ * S up,1 . (36)
Moreover, the first term in the sum above goes to zero, as λ → ∞. Indeed, since lim λ→∞ N d = ∞, we have C 1 → 1 as λ → ∞, and the claim follows noticing that F Sseed (d) tends to zero, as λ → ∞ (i.e., the mean number of seeds N seed and their offered bandwidth tend to infinity). We first consider the case γ p < 1. If d ≤ U , by Theorem 1, ǫ may be freely chosen in the interval [Ud, U ). We set ǫ = Ud, obtaining A = 0. For the second term in the sum (36), note that due to

A = 0 we have C 2 = e -N d (e N d -N d -1) = 1 -e -N d N d -e -N d . So, using again lim λ→∞ N d = ∞, we deduce that C 2 → 1 as λ → ∞.
Combining this with the relations:

E[e -θ * Sseed ] = e λT seed (φU (-θ * )-1) and φ U (-θ * ) -1 < 0 (this latter inequality holds since φ U (-θ * ) = E[e -θ * U ] < 1), we easily have that even the second term in the sum (36) tends to zero as λ → ∞. Consequently, for γ p < 1 and d ≤ U , we get lim λ→∞ S up,1 = lim λ→∞ S = 0. Now, suppose d > U . Since U is not constant the equation in z: e -zǫ E[e z(U -U1) ] = 1 has a unique solution, say θ * (ǫ). The properties of the function ǫ → θ * (ǫ) are given in Proposition 1 below. For λ large, consider the sequence {ǫ λ } ⊂ (0, U ) defined by

ǫ λ := (θ * ) -1 (λ -1/2 ).
Note that by Proposition 1 ǫ λ → 0 and θ(ǫ λ ) → 0, as λ → ∞. Furthermore λθ * (ǫ λ ) → ∞ as λ → ∞. We neglect again the first term in (36), and we obtain 2 S up,1 ∼ C 2 e θ * d E[e -θ * Sseed ]/θ * = C 2 e θ * d e λT seed (φU (-θ * )-1) /θ * . We can say that S up,1 → 0 if and only if log S up,1 → -∞. Thus, we consider log S up,1 ∼ log C 2log θ * + θ * d + λT seed (φ U (-θ * ) -1).

Using the Taylor expansion (and neglecting the term e -θ * A that tends to 1 as λ → ∞), we obtain that

log C 2 ≤ -θ * A + N d (e θ * A -1)
as λ → ∞. Using the Taylor expansion as λ → ∞, and the choice of ǫ λ above (thus θ * A → 0 and θ * ≥ λ -1/2 ), we have

log S up,1 ≤ -θ * A + N d (e θ * A -1) -log θ * + θ * d + N seed (φ U (-θ * ) -1) ≤ λT d (θ * A + o(θ * A)) -log(θ * ) + λT seed (-U θ * + o(θ * )) ∼ λT d θ * A -log(θ * ) -λT seed U θ * ≤ λθ * (T d A -T seed U ) -1/2 log λ → -∞
since in the regime γ p = T d d U T < 1, the quantity T d A -T seed U is negative. Therefore, the theorem follows.

We now consider the case γ p > 1. By Theorem 2 we have that

S ≤ C 1 F Sseed (d)d + C 3 2 θ * + w * -S seed + E[e θ * Sseed ]e -θ * w * /θ * S up,2 . (37)
In (37) we can neglect the term C 1 F Sseed (d)d ∼ 1. Note that as λ → ∞, C 3 ∼ 1. Thus, we obtain:

S up,2 = 2 θ * + w * -S seed + E[e θ * Sseed ]e -θ * w * /θ * The quantity w * , as λ → ∞ becomes w * = (1/θ * ) log(C 2 /C 3 ) + d ∼ N d A ∼ λT d (d -U ).
Therefore, as λ → ∞, it is easy to prove that log E[e θ * Sseed ]e -θ * w * /θ * → -∞; as before, we can conclude that E[e θ * Sseed ]e -θ * w * /θ * → 0.

Finally, we obtain, for λ → ∞,

S up,2 ∼ -S seed + w * + 1/θ * ∼ λ(-T seed U + T d (d -U )) + λ 1/2 ∼ λ T d (d -U ) -(T -T d )U = λ(T d d -U T ),
or, equivalently:

lim λ→∞ S up,2 (N d d -U N ) = 1.
Note that the quantity N d d -U N is a lower bound for S, as described in [START_REF] Bonald | Epidemic Live Streaming: Optimal Performance Trade-Offs[END_REF]. Therefore, necessarily

lim inf λ→∞ S (N d d -U N ) ≥ 1.
Recalling that S ≤ S up,2 , we obtain,

1 ≤ lim λ→∞ S (N d d -U N ) ≤ lim λ→∞ S up,2 (N d d -U N ) = 1
and the theorem follows.

Proposition 1. If d > U , then the equation in z E[e z(U -U1-ǫ) ] = 1 admits a unique solution for ǫ ∈ (0, U ). Furthermore, θ * (ǫ) = arg z>0 (e -zǫ E[e z(U -U1) ] = 1) is strictly increasing and C 1 on the interval (0, U ). Finally, it holds lim ǫ→0 θ * (ǫ) = 0.

Proof. We define the function f (z, ǫ) = E[e z(U -U1-ǫ) ]. Observe that f (z, ǫ) is analytic in the domain z ≥ 0 and ǫ ≥ 0, as immediate consequence of the fact that U -U 1 ≤ U < ∞.

Observe also that i) f (0, ǫ) = 1 and f ′ (0, ǫ) = -ǫ < 0 for any ǫ > 0

; ii) f (z, ǫ) is convex in z, since ∂ 2 f (z,ǫ) ∂z 2 = E[(U -U 1 -ǫ) 2 e z(U -U1-ǫ) ] > 0; iii) lim z→∞ f (z, ǫ) = ∞ for any ǫ < U . This because, for all c ∈ R, f (z, ǫ) = ∞ -∞ e z(U -w-ǫ) dF U (w) ≥ c -∞ e z(U -w-ǫ) dF U (w) ≥ e z(U -c-ǫ) Pr(U 1 < c). Since ǫ < U , there exists a > 1 such that (U -ǫ)/a > 0. Defining c = (U -ǫ)/a, we have e z(U -c-ǫ) → ∞ while Pr(U 1 < c) > 0.
As a consequence of i) , ii) and iii), recalling that f (z, ǫ) is continuous w.r.t. z for any ǫ ≥ 0 and z ≥ 0 there is a unique solution θ * (ǫ) = arg z≥0 (e -zǫ E[e z(U -U1) ] = 1).

The regularity of θ * (ǫ) with respect to ǫ immediately follows by the implicit function theorem. At last the monotonicity of θ * (ǫ) can be derived again from the implicit function theorem, according to

which dθ * (ǫ) dǫ = - ∂f (θ * (ǫ),ǫ) ∂ǫ ∂f (z,ǫ) ∂z | z=θ * (ǫ) . Note indeed that ∂f (θ * (ǫ),ǫ) ∂ǫ < -θ * (ǫ)f (θ * (ǫ), ǫ) < 0 ∀ǫ > 0, while ∂f (z,ǫ) ∂z | z=θ * (ǫ) > 0 by construction, since f (z, ǫ) is convex w.r.t. z and f (z, ǫ) < 1 for 0 < z < θ * (ǫ) and f (z, ǫ) > 1 for z > θ * (ǫ).
At last, it is immediate to see that also for ǫ → 0 θ * (ǫ) → 0, in light of the fact that f (0, 0) = 1, and f (z, 0) > 1 for z > 0.

As immediate consequence of the fact that θ * (ǫ) is strictly increasing (and thus invertible) and continuous over the domain (0, U ) with lim ǫ→0 θ * (ǫ) = 0, we have that the following proposition holds.

G Proof of Theorem 5

We first focus on the case d < U . Using the bound in ( Now we can compute an upper bound to the data volume requested from servers over time as:

V ≤ (d + 1 θ * )e θ * d ∞ 0 min{1, N d (t)}e -N seed (t)(1-φU (-θ * )) dt (40)

Inria

In order to compute V , we define T 1 as the temporal threshold such that T 1 sup{t : N d (t) > 1}, where T 1 ≡ 0 if N d (t) < 1 for all t ≥ 0. Thus, we compute Recall that N d (t) t (t-T d ) + Λq(z)G T (tz) dz. Now, we define Q(t) = t (t-T d ) + G T (tz)q(z) dz, thus N d (t) = ΛQ(t). We know that Q(t) > 0 ∀t and Q(t) → 0 for t → ∞. By the definition of T 1 we know that N d (T 1 ) = 1, thus we have

T 1 = T 1 (Λ) = Q -1 1 Λ . ( 43
)
Since Q(t) → 0 as t → ∞, it can be easily shown that

Q -1 (1/Λ) = T 1 (Λ) → ∞ as Λ → ∞.
We first consider the case 0 < q(t) < Kt -(α+1) for t > T 0 , K > 0 and α > 1. Thus, for all t > max{T 0 , T d } we have:

N d (t) ≤ Λ t (t-T d ) + q(z) dz ≤ Λ t (t-T d ) Kz -(α+1) dz ≤ ΛKt -α N * d (t) (44)
We define the time instant T * 1 max{t : N * d (t) ≥ 1}; thus, T * 1 is such that N * d (T * 1 ) = 1. We obtain T * 1 ∼ Λ 1/α . It is easy to see that since for all t > max{T 0 , T d } it holds N d (t) ≤ N * d (t), we have that T 1 (Λ) < T * 1 (Λ). Moreover, since Λ → ∞, it exists Λ 0 such that for all Λ > Λ 0 , it holds T 1 (Λ) > T 0 . We conclude T 1 (Λ) > T 0 , and thus T * 1 (Λ) > T 0 , as Λ > Λ 0 . Finally, from (41) and (42) we obtain an upper bound to the average data volume requested from the servers: We consider now the case where q(t) has a finite support, i.e., there exists an instant T 2 ≥ T d such that q(t) = 0 for all t > T 2 . We observe that T 2 is a constant as Λ → ∞, otherwise q(t) would not have finite support. We conclude that both T 1 and T 2 are constant in Λ.

V = (d + 1/θ * )e θ * d (V 1 + V 2 ) ≤ (d +
Therefore, in this case we obtain the bound

V = (d + 1/θ * )e θ * d (V 1 + V 2 ) ≤ (d +

  22) where I is the indicator function. In (22) the constants F Z (d | k) can be obtained imposing the condition F Z (kd | k) = 1 for all k, as shown in Appendix E. From F Z (d | k) we immediately obtain P(S d (k) > w):

Theorem 3 .

 3 Under the condition d < U , the cumulative function of Z d (∞) satisfies the stationary version of (21), i.e.,

  users UB -γ p = 1.3 exact -γ p = 1.3 UB -γ p = 1.1 exact -γ p = 1.1

Figure 1 :

 1 Figure 1: Average server bandwidth S versus the average number of users N , for different values of the per-user system load γ p , in the case d = 1, T d = 1, T = 2, and exponentially distributed upload bandwidth.

Figure 2 :

 2 Figure 2: Average server bandwidth S versus the average number of users N , for different values of the coefficient of variation (CV) of user upload bandwidth, in the case d = 1, T d = 1, T = 2, γ p = 0.9.

+C 2 eF 1 -

 21 -θ * (w * -d) θ * Sseed (w * ) + C 3 w * F Sseed (w * ) -C 3 (d,w * ] wF Sseed (dw) + C 2 e θ * d θ * (w * ,∞) e -θ * w F Sseed (dw) F Sseed (w)) dw ≤ d and the Chernoff bound (1 -F Sseed (w)) ≤ E[e θ * Sseed ]e -θ * w , the integral -C 3 (d,w * ] wF Sseed (dw) in (29) becomes:

∞w≤ C 1 F 3 e≤ C 1 F 3 e= C 1 F 1 θ≤ C 1 F 2 θ

 13131112 * e -θ * w dw = C 3 w *w * F Sseed (w * ) + F Sseed (d)d -S seed + E[e θ * Sseed ]e -θ * w * /θ * Noting that in (29) -C 1 d 0 wF Sseed ( dw) ≤ 0, and that by definition of w * , C 2 e -θ * (w * -d) = C 3 , we Inria have:S ≤ (C 1 -C 3 )F Sseed (d)d+C 3 F Sseed (w * )/θ * + C 3 w * + F Sseed (d)d -S seed + E[e θ * Sseed ]e -θ * w * /θ * + C 2 e θ * d θ * (w * ,∞) e -θ * w F Sseed (dw) Sseed (d)d+C 3 1/θ * + w * -S seed + E[e θ * Sseed ]e -θ * w * /θ * + C θ * w * θ * (e -θ * w F Sseed (w)| ∞ w * -+ θ * ∞ w * e -θ * w F Sseed (w)dw) Sseed (d)d+C 3 1/θ * + w * -S seed + E[e θ * Sseed ]e -θ * w * /θ * + C θ * w * θ * (-e -θ * w * F Sseed (w * -) + θ * (w * ,∞)e -θ * w dw) Sseed (d)d+C 3 * + w * -S seed + E[e θ * Sseed ]e -θ * w * /θ * -F Sseed (w * -)/θ * + 1/θ * Sseed (d)d+C 3 * + w * -S seed + E[e θ * Sseed ]e -θ * w * /θ * E Derivation of the exact solution in (22)

FU

  Z (y | k -1)e -y U dy = e F Z (d | k -1)e -y U dy = (w-d) U e w-2d U F Z (d | k -1).

  Now considering 2d ≤ w ≤ 3d, we can still use (33) to express F Z (w | k) in terms of F Z (y | k -1) over a domain in which y ≤ wd ≤ 2d. Again we know explicitly the expression of F Z (w | k) over the considered domain in terms of the two constants F Z (d | k -1) and F Z (d | k -2). It turns out:

  35)Proceeding in a similar way we can express F Z (w | k) for any w ≤ kd in terms of the constantsF Z (d | 1). . . F Z (d | k), while for w > kd we have trivially F Z (w | k) = 1.The constantsF Z (d | k) can be obtaining forcing F Z (kd | k) = 1. Indeed, by imposing F Z (w | 1) | w=d = 1 we immediately obtain F Z (d | 1) = 1. Imposing F Z (w | 2) | w=2d =1 we obtain an algebraic linear equation between F Z (d | 2) and F Z (d | 1), from which we can derive F Z (d | 2). In general imposing F Z (w | k) | w=kd = 1 we obtain a linear algebraic equation containing all constant F Z (d | i) with i ≤ k. This equation can be exploited to derive F Z (d | k) as function of F Z (d | i) with i < k.

Proposition 2 .

 2 Provided that d > U , and U not constant, the image of θ * (ǫ) for 0 < ǫ < U is the open interval (0, δ), with δ = lim ǫ→U θ * (ǫ).

  [START_REF] Fan | Balancing Throughput, Robustness, and In-Order Delivery in P2P VoD[END_REF]:S(t) ≤ C 1 (t)F Sseed (d)d + C 2 (t) e θ * d θ * E[e -θ * Sseed ](38)withA = d -U + ǫ, C 1 (t) = 1e -N d (t) , C 2 (t) = e -θ * A e -N d (t) (e N d (t)e θ * A -N d (t)e θ * A -1).Since d < U , from Corollary 1 we can set A = 0, and we getC 1 (t) ≤ min{1, N d (t)} C 2 (t) = 1 -N d (t)e -N d (t)e -N d (t) ≤ 1e -N d (t) ≤ min{1, N d (t)} By using the Chernoff bound F seed (d) ≤ E[e -θ * Sseed ]e θ * d in (38), we obtain S(t) ≤ min{1, N d (t)}(d + 1/θ * )E[e -θ * Sseed ]e θ * d = min{1, N d (t)}(d + 1/θ * )e -N seed (t)(1-φU (-θ * )) e θ * d(39)

V 1 T10 1 ( 2 ∞

 112 min{1, N d (t)}e -N seed (t)(1-φU (-θ * )) dt = T1 0 e -N seed(t)(1-φU (-θ * )) dt ≤ T T1 min{1, N d (t)}e -N seed (t)(1-φ U (-θ * )) dt = ∞ T1 N d (t)e -N seed(t)(1-φU (-θ * )) dt ≤ ∞ T1 N d (t) dt (42) We obtain the bound V = (d + 1/θ * )e θ * d (V 1 + V 2 ) ≤ (d + 1/θ * )e θ * d (T 1 + ∞ T1 N d (t) dt).

1 T1* 1 N 1 -T 1 ) + ΛT * 1 1

 11111 1/θ * )e θ * d (T 1 + ∞ T1 N d (t) dt) ≤ (d + 1/θ * )e θ * d (T 1 + T * N d (t) dt + ∞ T d (t) dt) ≤ (d + 1/θ * )e θ * d (T 1 + (T * -α /(α -1)) = (d + 1/θ * )e θ * d (Λ 1/α + Λ 1/α /(α -1)) ∼ Λ 1/α , Λ → ∞.(45)

  1/θ * )e θ * d (T 1 + T2+T d T1 N d (t) dt) ≤ (d + 1/θ * )e θ * d (T 1 + (T 2 + T d -T 1 )) = (d + 1/θ * )e θ * d T 2 = Θ(1) when Λ → ∞.

1 2 . 2 2 . 3 3 . 2 3 . 3 3 . 4

 12223323334 System assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Users dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Performance metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Universal lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Exact solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.5 Numerical Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 Asymptotic analysis 13 4.1 Time-invariant video popularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Time-varying video popularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2004 route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr

Table 1 :

 1 Notation

	Symbol	Definition
	d	user download rate
	U	average user upload bandwidth
	T d	average time spent downloading the video (s)
	T	average user activity period (s)
	λ(t)	arrival rate of new requests for the video at time t
	N (t)	average number of users at time t
	N d (t)	average number of downloading users at time t
	N seed(t) average number of seeds at time t
	S d (t)	average bandwidth requested by downloading users at time t
	Sseed(t)	average bandwidth offered by seeds at time t
	S(t)	average bandwidth requested from the servers at time t
	γ(t)

RR n°8183

In this paper we use the terms peer and user interchangeably.Inria

With abuse of notation we will use the expression f ∼ g to indicate that f ∈ Θ(g), i.e., f is bounded both above and below by g asymptotically Inria

A Proof of Lemma 1

Consider a sequence of i.i.d. variables (X i ) i≥1 , satisfying the three properties: i) E[X 1 ] < 0; ii) P(X 1 > 0) > 0; iii) E[e tX1 ] is finite in a neighborhood of the origin. Define

Define the filtration F 0 := {∅, Ω}, F k := σ{X 1 , . . . , X k }, k ≥ 1 (i.e. the σ-algebra generated by {X 1 . . . X k }). Consider the r.v.

where the infimum is equal to ∞ if {k ≥ 1 : Q(k) > w} = ∅. Note that τ w is the first time at which the process Q(k) exceeds the quantity w.

Let θ * be such that E[e θ * X1 ] = 1. It can be proved that under the three conditions described above, there exists a unique θ * > 0. It can be easily checked that the process {e θ * Q(k) } is an F k -martingale. Therefore, using the stopping theorem (note that τ w is an F k -stopping time) the process {e θ * Q(k∧τw) } is an F k -martingale, for each w > 0.

Consequently, we have

where the first inequality follows by Fatou's lemma. We conclude that

We now consider a popularity distribution with an exponential decreasing tail. Thus, ∃ T 0 such that for all t > T 0 , q(t) ∼ e -αt , α > 0 . In this case we have

We obtain again that the quantity T 1 is such that N d (T 1 ) = 1, i.e., T 1 (Λ) ∼ log Λ. Finally, we obtain the following upper bound to the average amount of data requested from the servers:

and thus

Now we consider the case d > U . In can be easily shown that V ∼ Λ under both the considered popularity distributions. We first note that, since the average number of users in the system grows asymptotically linearly with Λ, this linear behavior is a trivial upper-bound for the average data volume requested from the servers. We consider the following lower-bound:

Integrating the previous lower-bound, and noting that by definition, N seed (t) = 0 for t < T d , we obtain

The last line follows noting that the integral is a positive quantity that does not depend on Λ and d > U in this case. Since we have proven that V is bounded above and below by a quantity that grows asymptotically as Λ, we can conclude that V = Θ(Λ) when d > U for any choice of the shaping function q(t) modeling the video popularity. Inria