Glauber D Gonc ¸alves
email: ggoncalves@dcc.ufmg.br

Anna Guimarães

Alex Borges Vieira

Ítalo Cunha
email: cunha@dcc.ufmg.br

Jussara M Almeida
email: jussara@dcc.ufmg.br

Using Centrality Metrics to Predict Peer Cooperation in Live Streaming Applications

Keywords: Peer-to-peer live streaming, centrality metrics, cooperation level

The lack of cooperation in Peer-to-Peer (P2P) applications poses serious challenges to the quality of service provided to their clients, specifically in P2P live streaming applications given their strict real-time constraints. We here investigate the potential of exploiting topological properties of the P2P overlay network to predict the level of cooperation of a peer, measured by the ratio of the upload to the download traffic during a pre-defined time window. Using data collected from SopCast, we first show that centrality metrics provide good evidence of a peer's cooperation level in the system. We then develop a regression-based model that is able to estimate, with reasonable accuracy, the level of cooperation of a peer in the near future given its centrality measures in the recent past. Our proposed strategy complements existing incentive mechanisms for cooperation in P2P live streaming, and can be applied to detect non-cooperative peers.

Introduction

The peer-to-peer (P2P) architecture has emerged as a cost-effective platform for live video streaming on the Internet. Indeed, various P2P live streaming applications, such as SopCast, PPLive, and UUSee 1 , have already reached the mark of millions of registered users [START_REF] Hei | A measurement study of a large-scale p2p iptv system[END_REF]. Such systems are composed of clients (peers) that collaborate to disseminate the live media content by establishing partnerships and organizing themselves into an overlay network on top of the real computer network. A peer may request (and receive) chunks of the live media from its partners, thus releasing the central server from the responsibility, and ultimately from the associated costs, of serving all participant clients.

Given this architecture, the proper operation of P2P applications and ultimately the quality of service provided to the clients depend heavily on peer cooperation. However, a number of previous studies have already detected the presence of non-cooperative peers, also known as free riders, which download content from their partners but do not upload the received content to other peers [START_REF] Adar | Free Riding on Gnutella[END_REF]. The lack of cooperation may be caused by both opportunistic users, who consciously choose not to upload content to others, and by P2P protocols that induce unbalanced data exchanges among partners. The presence of non-cooperative peers may greatly degrade the overall system performance [START_REF] Xia | Discovering Free-Riders Before Trading: A Simple Approach[END_REF], particularly in P2P live streaming applications due to their strict time constraints [START_REF] Karakaya | Free Riding in Peer-to-Peer Networks[END_REF]. For example, peers may experience video interruptions due to the lack of partners from which to download the live content, whereas altruistic peers, i.e., peers that upload more content than they received, thus serving multiple partners, may be overloaded with data requests and become unsatisfied with the system. Thus, maintaining estimates of the current level of cooperation among peers helps P2P application managers to identify potentially non-cooperative peers as well as altruistic overloaded peers, guiding them into future actions to guarantee the expected quality of service.

In this paper, we investigate whether the topological properties of a peer in the overlay network are related to its level of cooperation in P2P live streaming applications. In particular, we assess the potential benefit of exploiting centrality metrics to dynamically predict the level of cooperation of each peer. A peer's cooperation level is defined by the ratio of the total upload to the total download traffic the peer exchanged with its partners. Since a peer's cooperation level may change over time throughout the live transmission, it should be estimated periodically, during specific time windows.

Our study relies on data collected from one of the currently most popular P2P live applications, i.e., SopCast, using a large number of PlanetLab machines. It encompasses two main steps. We first show that centrality metrics [START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF] are reasonably strongly correlated with the peer's cooperation level and thus might be used to distinguish noncooperative peers, i.e., peers that upload less than download, from the others. Moreover, we also show that a peer's centrality remains reasonably stable over consecutive 60-second time windows. Motivated by these findings, we then develop a regressionbased model to predict the level of cooperation of a peer in the following time windows given its centrality measures collected in the last window. Using our collected data, we show that our approach can produce reasonably accurate predictions.

There are various techniques for detecting non-cooperative peers [START_REF] Azzedin | Trust-Based Taxonomy for Free Riders in Distributed Multimedia Systems[END_REF][START_REF] Guerraoui | LiFTinG: Lightweight Freerider-Tracking Protocol in Gossip[END_REF][START_REF] Li | Flight-Path: Obedience vs. Choice in Cooperative Services[END_REF] and incentivizing peer cooperation [START_REF] Chatzidrossos | Server guaranteed cap: An incentive mechanism for maximizing streaming quality in heterogeneous overlays[END_REF][START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF][START_REF] Silverston | Towards an Incentive Mechanism for Peer-to-Peer Multimedia Live Streaming Systems[END_REF] in live streaming applications. Our motivation for investigating the benefit of exploiting centrality metrics for that purposes lies in the observation that many P2P live applications keep a centralized server (tracker) that periodically receives control messages from each peer. In such messages, peers might include a list of their current partners [START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF], based on which the tracker could reconstruct the overlay topology and compute each peer's centrality. Moreover, some techniques collect the ratio of upload to download periodically from peers and use authentication mechanisms to be robust to malicious peers, which increases communication and computation overhead in the system. We believe that our strategy might be jointly applied with such techniques by complementing them and reducing their overhead [START_REF] Chatzidrossos | Server guaranteed cap: An incentive mechanism for maximizing streaming quality in heterogeneous overlays[END_REF][START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF].

The rest of the paper is as follows. Section 2 discusses related work. Our SopCast data collection methodology is described in Section 3. The level of cooperation among SopCast peers is analyzed Section 4, whereas its correlation with peer centrality is discussed in Section 5. Section 6 presents our regression-based model, whereas related practical issues are discussed in Section 7. Section 8 concludes the paper.

Related Work

Low cooperation in P2P systems, or free riding, was first analyzed in the Gnutella file sharing system [START_REF] Adar | Free Riding on Gnutella[END_REF]. Since then, various studies have addressed the problem [START_REF] Azzedin | Trust-Based Taxonomy for Free Riders in Distributed Multimedia Systems[END_REF][START_REF] Guerraoui | LiFTinG: Lightweight Freerider-Tracking Protocol in Gossip[END_REF][START_REF] Locher | Free Riding in BitTorrent is Cheap[END_REF][START_REF] Xia | Discovering Free-Riders Before Trading: A Simple Approach[END_REF]. Most notably, incentive mechanisms that rely on bilateral peer contribution, such as Bittorrent's tit-for-tat [START_REF] Cohen | Incentives Build Robustness in BitTorrent[END_REF] and further improvements [START_REF] Levin | BitTorrent is an Auction: Analyzing and Improving Bittorrent's Incentives[END_REF][START_REF] Xia | Discovering Free-Riders Before Trading: A Simple Approach[END_REF], have been widely applied in file sharing systems. However, tit-for-tat may not be effective in live streaming because video segments become obsolete over time, which in turn prevents some peers from sharing every segment received [START_REF] Silverston | Towards an Incentive Mechanism for Peer-to-Peer Multimedia Live Streaming Systems[END_REF].

FlightPath [START_REF] Li | Flight-Path: Obedience vs. Choice in Cooperative Services[END_REF] is a P2P live streaming application with an incentive mechanism that uses tit-for-tat but also adds a relaxation parameter for the benefit of peers that are unable to contribute in a balanced way. Silverston et al. [START_REF] Silverston | Towards an Incentive Mechanism for Peer-to-Peer Multimedia Live Streaming Systems[END_REF] proposed a different incentive mechanism where peers unable to serve data should answer with pointers to other peers that are able to serve. Chatzidrossos et al. [START_REF] Chatzidrossos | Server guaranteed cap: An incentive mechanism for maximizing streaming quality in heterogeneous overlays[END_REF] argued that many noncooperative peers are unable to upload as much data as they download due asymmetric DSL or HSDPA connections. To maximize the social welfare, they proposed to reserve a fraction of server upload bandwidth to altruistic peers that upload more data than they download. Our model could be used by such incentive mechanisms to identify non-cooperative and altruistic peers, enabling the application to redirect traffic in its network. More than that, in the case of the incentive mechanism proposed by Silverston et al., our model can indicate the amount of data a peer can serve in the near future based on its predicted cooperation level.

LiFTinG [START_REF] Guerraoui | LiFTinG: Lightweight Freerider-Tracking Protocol in Gossip[END_REF] is a technique for tracking free riders that consists of a series of checking and cross-checking operations performed by peers to verify whether data requests are served by their partners and whether the partners forwarded received data to their own partners. Failed verifications decrease the score of a peer, and peers with low score may be considered suspect and be banned from the system. Azzedin [START_REF] Azzedin | Trust-Based Taxonomy for Free Riders in Distributed Multimedia Systems[END_REF] proposed that peers keep a black list of untrustworthy contributors and send information about corrupted content received from their partners to monitoring peers. This information is then used to detect free riders and content polluters (i.e., peers that inject corrupted data in the system). Our model may be used by trust systems as an additional information source: peers reporting cooperation levels significantly higher than what the model predicts based on their out-degrees can be put in a list of suspect peers to check.

More related to our work is the centralized version of the Contracts incentive mechanism [START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF]. Contracts uses estimates of each peer's cooperation level to restructure the overlay such that altruistic peers are placed closer to the video source, thus having a better quality of service. At each peer, Contracts collects cryptographic receipts for uploaded data and sends them periodically to the tracker. The tracker processes receipts to compute each peer's cooperation level, which incurs in high processing cost. Our method could help reducing communication and computational overhead incurred by Contracts, as discussed in Section 7.

SopCast Data Collection Methodology

Our study relies on a set of traffic logs collected from SopCast, a currently very popular P2P live streaming application. SopCast maintains a number of channels, each one transmitting live content over its own P2P overlay network, independent from the others. The SopCast P2P architecture is based on a data-driven mesh network [START_REF] Zhang | CoolStreaming/DONet: A Data-Driven Overlay Network for Efficient Live Media Streaming[END_REF], in which clients (peers) establish partnerships among themselves building a mesh like overlay network. A server, which generates the content, splits the media into chunks and transmits them over the network. To receive the live content, a peer explicitly requests each needed chunk from one of its partners. SopCast keeps a list of public channels but also allows the creation of private live channels, accessible to a restricted set of clients.

To collect data from SopCast, we used a set of PlanetLab machines [START_REF] Chun | PlanetLab: An Overlay Testbed for Broad-Coverage Services[END_REF] acting as both regular SopCast clients and data crawlers. Our crawling strategy follows the one used in [START_REF] Tang | Topology Dynamics in a P2PTV Network[END_REF], where each crawler collects and stores data regarding all packets it exchanges with its partners, and these traces are later merged to reconstruct the overlay network. We chose to collect data from a private channel of our own, restricting the clients to our PlanetLab crawlers, so as to be able to collect a complete view of the overlay network and compute exact measures of the centrality and cooperation level of each peer.

To build our private SopCast channel, we set up a server to encode and transmit a 1hour 280 kbps video. We performed 6 experiments in November 2011. For each experiment, all crawlers joined the SopCast channel at the same time and remained connected through an initial 5-minute interval. Afterwards, our crawlers start mimicking the behavior of real peers by dynamically leaving and rejoining the channel (i.e., churn). The churn model adopted was based on a previous characterization of the dynamic behavior of real SopCast clients on a popular public channel [START_REF] Vieira | Characterizing Sop-Cast Client Behavior[END_REF]: each peer remains connected in the channel for a certain period ON of time; afterwards, it leaves the system remaining inactive for a period OF F of time after which it rejoins the channel. According to our analyses of real data collected during various transmissions, ON times are well modeled by a Weibull distribution with parameters α = 2.032 and β = 0.233, whereas OF F times follow an Exponential distribution with parameter λ = 0.0542 . While connected to the channel, each crawler uses Wireshark3 to collect all SopCast related traffic.

During our experiments, we used the largest number of crawlers possible, which varied between 350 and 450 stable PlanetLab nodes. We also checked clock drift among crawlers to guarantee that time differences could be neglected (less than 1 second).

Each crawler collected the timestamp (at the 1-second granularity) and the size of each packet sent (received) to (from) other SopCast clients. As our focus is on data packet exchanges, we only stored information for packets containing at least 1300 bytes, a threshold selected based on previous studies of SopCast and PPLive [START_REF] Hei | A measurement study of a large-scale p2p iptv system[END_REF][START_REF] Tang | Topology Dynamics in a P2PTV Network[END_REF].

For each experiment, once the monitoring period finished, we merged the log files created by all crawlers to reconstruct the overlay network during the experiment. We discarded an initial 5-minute warm-up phase, analyzing only data collected afterwards (during peer churn). We used the time information and the source and destination IP addresses of each packet to reconstruct the SopCast overlay network as a sequence of snapshots. More specifically, we took consecutive snapshots of the network, each one built from data collected during a pre-defined time window with duration W . In the following, we analyze peer cooperation level for all time windows of all 6 experiments.

Peer Cooperation in SopCast

To analyze peer cooperation in SopCast during our experiments, we start by defining the cooperation level of peer i during time window t, denoted CL(t, i), as the ratio between the total number of bytes uploaded and downloaded by i during t.

We then analyze CL values as a function of the time window duration W . In practice, we want a duration that is neither too short nor too long, so as to smooth out great variations at very short time scales while still capturing dynamic peer properties over the course of a transmission. We tested with W equal to 2, 30, 60 and 90 seconds. As an example, Figure 1(a) shows the CL values of a selected peer measured over consecutive windows, for W equal to 2 and 30 seconds. The peer's CL fluctuates greatly for W =2, whereas for W =30 the curve shows a much smoother behavior. We quantify this variability with the coefficient of variation (CV) (i.e., the ratio of the standard deviation to the mean) of all measured CL values. Figure 1(b) shows the distributions of CVs, computed for each peer across all time windows in our experiments, for each duration W . Clearly, the variability is greater for W =2, whereas for W ≥30, the distributions are very close to each other. Thus, we focus on W equal to 30, 60, and 90 seconds.

We now analyze the distribution of CL values across all peers during all time windows of all experiments. Figure 1(c) shows CL values with logarithmic scale on the x-axis. Note that the distributions are very similar for W equal to 30, 60, and 90 seconds. Indeed, 2% of the measured CL values are greater than 10 for all three values of W . In general, we observe two extreme peer behaviors. On one side, there are few altruistic peers that upload much more than they download. On the other side, there are many non-cooperative peers that upload much less than they download. In particular, Figure 1(c) shows that 34% of all measured CL values are below 0.1, corresponding to very uncooperative peers which, despite downloading the complete video, forwarded no more than one-tenth of it to their partners. These results illustrate how unbalanced load distribution is in SopCast.

Considering as non-cooperative during time window t a peer i with CL(t, i) < 1 (as in [START_REF] Locher | Free Riding in BitTorrent is Cheap[END_REF]), Figure 1(c) shows that, during a time window, the SopCast network contains around 87% of non-cooperative peers, on average. Even if we assume a stricter definition, with a non-cooperative peer i being such that CL(t, i) < 0.5 (or CL(t, i) < 0.2), the fraction of non-cooperative peers during a window t is 79% (56%), still quite large. These observations indicate that it is very likely that SopCast does not implement any load balancing mechanism among peers, as already observed for PPLive [START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF]. The lack of such mechanism is a concern because cooperative peers (particularly very altruistic peers) may find themselves discouraged to participate in the network due to the high bandwidth consumption. Moreover, the large presence of non-cooperative peers may lead to extra delays, stream interruptions, and ultimately system collapse [START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF].

Peer Centrality and Cooperation Level

Our goal in this paper is to assess the potential benefit of using a peer's centrality measures to predict its cooperation level in the near future. More specifically, we want to assess the accuracy of using centrality measures of peer i during window t to predict its CL value in window t + 1. This idea rely on two hypotheses: (1) a peer's centrality is correlated with its CL, and (2) a peer's centrality remains roughly stable over consecutive windows. We here investigate whether these hypotheses hold in our dataset.

We consider 3 commonly used centrality metrics, namely, out-degree, closeness, and betweenness, taking normalized measures so as to make them comparable across different time windows during which the number of clients in the network may change. The out-degree of a peer i during window t, denoted by d(t, i), is the number of partners to which i uploaded media chunks during t. We define normalized out-degrees as d(t, i) = d(t, i)/(|P(t)| -1), where P(t) is the set of network peers during t. The closeness of peer i during t, c(t, i), is the inverse of the average shortest path length between i and all the other peers in the network during window t [START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF]. Let δ(t, i, j) be the length of the shortest path between nodes i and j during t, then c(t, i) = (|P(t)| -1)/ j∈P(t) δ(t, i, j). Note that c(t, i) ∈ (0, 1] regardless of network size, being already normalized. The betweenness of peer i during t, b(t, i), is the fraction of all shortest paths connecting pairs of nodes in the network that pass through i. Let σ(t, j, k) be the number of shortest paths between nodes j and k during t and σ(t, j, k, i) be the number of those paths that pass through i, then b(t, i) = i,j,k∈P(t),i =j =k σ(t, j, k, i)/σ(t, j, k). Betweenness values increase with the number of pairs in the network, so we normalize them by the number of pairs of peers excluding i, which gives b(t, i) = 2b(t, i)/((|P(t)| -1)(|P(t)| -2)) [START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF].

We disregard edge direction to compute closeness and betweenness, as Freeman [START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF]. Edge directions could partition the graph and lead to inconsistencies when computing these 2 metrics. In particular a peer that uploads more than it downloads could become unreachable from the majority of peers in the network, be traversed by few shortest paths, and have low betweenness. We only consider the direction of the edge to compute out-degree because in this case, direction captures information about the data flow.

We analyze the relationship between each centrality metric and cooperation level using the Spearman correlation coefficient, which is a non-parametric measure of statistical dependence [START_REF] Kendall | Rank Correlation Methods[END_REF]. We compute the correlation between peer centrality and CL for each time window. Figure 2 shows the distributions of the Spearman coefficients for all time windows in all experiments for different values of W . For all three metrics, window duration has small impact on the correlation coefficients, which are strictly positive and usually larger than 0.5. Thus, all three metrics may be useful to predict CL values. However, out-degree clearly has a significantly stronger correlation. We also analyze the capacity of each centrality metric to distinguish non-cooperative peers (i.e., with CL<1) from cooperative peers (i.e., with CL ≥1). Figure 3 shows the distributions of closeness, betweenness, and out-degree for these two sets of peers over all time windows for W =60. Results for other values of W are quantitatively similar, being thus omitted. All three metrics have very distinct distributions for cooperative and non-cooperative peers: non-cooperative peers tend to have much smaller closeness, betweenness, and out-degree. Once again out-degree stands out as the most discriminative metric. Figure 3 also shows the distributions for stricter definitions of non-cooperative peers with CL<0.5 and for cooperative peers with CL≥2. The same trend holds, providing further evidence that centrality metrics, in particular out-degree, may be useful to predict, with reasonable accuracy, peer cooperation levels.

We now turn to our second hypothesis, and analyze the difference between each peer's centrality in two windows t and t + k, for positive k. We focus only on outdegree as, according to Figures 23, it is the most promising metric. Figure 4 shows the distributions of the differences of normalized out-degrees over all peers in all windows for various values of k and W = 60s. Note that out-degrees remain reasonably stable for small values of k (e.g., k ≤ 8). For instance, for 80% of the peers analyzed over pairs of windows that are 8 minutes apart from each other (k = 8), the difference in the normalized out-degree is less than 4% of the total number of peers in the network. Thus, peer centrality remains reasonably stable across a few successive time windows.

Predicting a Peer's Cooperation Level

Given our findings in the previous section, we now study whether the centrality of a peer measured in window t can help us predict its cooperation level in window t + 1. By visual inspection, we identified that a peer's CL is a non-linear, monotonically increasing function of each considered centrality metric. This led us to evaluate nonlinear regression models for computing CL. Let m(t, i) denote a (normalized) centrality metric (out-degree, betweenness, or closeness). We evaluated polynomial and exponential models of the forms:

CL(t + 1, i) = 4 j=0 a j m j (t, i) and CL(t + 1, i) = a 0 + a 1 m(t, i) + be m(t,i) .
In both cases, we considered functions of a single centrality metric as well as functions combining multiple metrics. We computed model parameters a j and b using curvilinear regression [START_REF] Jain | The Art of Computer Systems Performance Analysis:Techniques for Experimental Design, Measurement, Simulation, and Modeling[END_REF], where one applies a linear transformation to the predictor and response variables, i.e., m(t, i) and CL(t, i), and then computes the parameters minimizing the sum of squared residual errors. The estimates are produced in successive time windows as follows: model parameters a j and b are computed based on centrality and CL values measured in window t -1, the model is applied using peer's centrality measured during window t, and its accuracy is evaluated by comparing, for each peer, the predicted CL against the CL measured in the next time window t + 1. We quantify prediction accuracy using the prediction error CL(t + 1, i) -CL(t + 1, i). Negative CL(t + 1, i) are truncated to zero, as negative cooperation does not make sense.

In the interest of space, we present a summary of our findings in the evaluation of the various models tested. As expected from the results in Figures 2 and3, the models using out-degree have higher prediction accuracy among the three centrality metrics. Moreover, the exponential models usually have lower prediction accuracy as they systematically underestimate the cooperation level of altruistic peers, whereas cubic and quadric models have accuracy equivalent to quadratic models. Thus, we opted for the latter (simpler) ones. Finally, the intercept a 0 is usually statistically equivalent to zero, which is intuitive, as a peer's contribution is zero when it is not in the network (i.e., m(t, i)=0). Thus, we focus our following discussion in our best-performing model 4 :

CL(t + 1, i) = a 1 d(t, i) + a 2 [d(t, i)] 2 .
( We start analyzing the accuracy of our model by plotting, for each peer i and window t, the measured and predicted cooperation levels. Figure 5 shows results for all peers and windows with W =60. The trend towards linearity is clear: a Pearson correlation coefficient [START_REF] Jain | The Art of Computer Systems Performance Analysis:Techniques for Experimental Design, Measurement, Simulation, and Modeling[END_REF] ρ=0.87 indicates strong positive correlation. Similarly, we obtained ρ equal to 0.90 and 0.84 for W equal to 30 and 90 seconds. Despite producing errors in a few cases, most predictions have reasonable accuracy. Indeed, Figure 6 shows the distributions of errors computed over all peers and windows, for W equal to 30, 60 and 90. To improve readability, we group prediction errors based on the measured cooperation level: predictions for non-cooperative peers with CL < 1, predictions for cooperative peers with 1 ≤ CL < 10, and predictions for very altruistic peers with CL ≥ 10.

In general, the first two sets of curves show that prediction errors are very concentrated around zero and that the choice of W has little impact on them, although W might impact whether the model tends to overestimate or underestimate the cooperation level. For instance, considering the predictions for non-cooperative peers (CL<1), around 68%, 67% and 66% of the predictions are reasonably accurate, falling within ±0.2 of the measured CL values for W equal to 30, 60 and 90 seconds, respectively. However, the fraction of predictions that underestimate the measured CL tends to be larger for larger W . For example, Figure 6(a) shows that the fraction of negative errors (i.e., underestimates) is 84% for W =90, but only 64% for W =30. Similarly, most predictions for peers with 1 ≤ CL < 10 are within 2 units of the measured values. Indeed, 76%, 71% and 66% of the model errors fall in this range for W equal to 30, 60 and 90 seconds. However, unlike observed for non-cooperative peers, the model tends to underestimate the real CL values more for larger W .

The predictions for the very altruistic peers are somewhat less accurate: around 55%, 48% and 43% of the errors are within 5 units of the measured CLs for W equal to 30, 60 and 90 seconds. The smaller number of very altruistic peers in the network (2%) makes it hard to build a model that is very accurate for such peers compared to the other two groups. We note, however, that our model is able to correctly identify most very altruistic peers: around 85% of the predictions for these peers produced CL estimates that fall in the expected range (i.e., CL ≥ 10), and most remaining CL estimates fall between 1 and 10. It is also able to identify most cases of non-cooperation: only 3% of predictions for peers with CL < 1 had CL > 1. In future work, we intend to exploit other topological properties to improve the prediction for very altruistic peers.

So far, we have discussed the accuracy of the regression model when parameters a j are computed at each window t given the centrality measures collected during that window. We now consider the case where the model parameters are computed using data collected at window t and applied at the following k windows, i.e., t + 1, t + 2, • • • , t + k. Note that we still collect centrality measures at each window and use them to predict cooperation levels during the next window. Our goal is to analyze the sensitivity of the model to the frequency at which it must be calibrated (i.e., parameters must be recomputed), where k defines the time interval between two consecutive calibrations.

Figure 7 shows the distributions of prediction errors for various values of k and W =60. Once again, we show results separately for each range of measured CLs. The impact of k on the errors can be barely noticed, particularly for CL<10 (Figures 7(ab)). This implies that model parameters can be computed once and applied repeatedly for the following 16 minutes, at least. The model is a little more sensitive to long calibration periods when estimating the CL of very altruistic peers (Figure 7(c)). For this range, the errors tend to increase slightly for k>16. This is because some very altruistic peers experience frequent changes in their centrality measures. We conjecture that such changes might be due to the policy, adopted by many current applications, of peers randomly selecting new neighbors every so often [START_REF] Guerraoui | LiFTinG: Lightweight Freerider-Tracking Protocol in Gossip[END_REF][START_REF] Zhang | CoolStreaming/DONet: A Data-Driven Overlay Network for Efficient Live Media Streaming[END_REF]. Chances are that a peer that loses some of its partners ends up creating new partnerships with such very altruistic peers, as they are more willing to accept them. However, even for very altruistic peers, the impact of increasing k to 16 on model accuracy is small and might be acceptable.

Practical Considerations

Our results in Section 6 indicate that centrality metrics, notably out-degree, may be used to predict a peer's cooperation level with reasonable accuracy. We now address three factors that impact its practical deployability: how to collect inputs for model calibration and application, processing overhead at the tracker, and robustness to malicious nodes.

To build (calibrate) and apply our model, a central participant must collect each peer's out-degree and cooperation level. This could be performed by the tracker which, in many current P2P applications, already periodically receives control messages from all peers. Indeed, we observed, during our SopCast experiments, control message exchanges between peers and the tracker every 2 minutes. A peer could piggyback the list of its current partners in these control messages, which would suffice for the tracker to compute the whole overlay topology. Such piggybacking would incur in a small bandwidth overhead as peers usually have only a few tens of partners [START_REF] Hei | A measurement study of a large-scale p2p iptv system[END_REF] (15.65 on average in our SopCast experiments), each of which could be represented by only 4 bytes. For the sake of illustration, if there are 10,000 pairs in the network informing their partners every 2 minutes, the aggregate overhead at the tracker is only 5Kbps.

This overhead is small given that the knowledge of the overlay topology is of interest to system administrators, who are often concerned about the traffic between peers, and thus is expected from a well monitored system. Indeed, in some applications [START_REF] Zhang | CoolStreaming/DONet: A Data-Driven Overlay Network for Efficient Live Media Streaming[END_REF], peers already periodically exchange information that provide a partial view of the network. In such systems, the partnership information could be collected by a few monitoring peers (as in [START_REF] Azzedin | Trust-Based Taxonomy for Free Riders in Distributed Multimedia Systems[END_REF]) which jointly could reconstruct the complete network.

The second required input, each peer's cooperation level, could be sent to the tracker by the peer itself, at the cost of extra 4 bytes, or, alternatively, peers could send their upload to each partner, which induces an overhead equivalent to that of the list of partners. However, note that, this could be performed at longer intervals, since, according to Figure 7, model calibration at each 16 minutes still yields reasonably accurate results.

Calibrating the prediction model at the tracker requires few computational resources, as the out-degree requires no extra computation once the topology is available, and the regression algorithms to compute parameters a 1 and a 2 are efficient [START_REF] Jain | The Art of Computer Systems Performance Analysis:Techniques for Experimental Design, Measurement, Simulation, and Modeling[END_REF]. For example, we can calibrate our model in GNU R for one million of peers in about 3 seconds.

Regarding malicious peers, we note that one peer alone would not be able to deceive the system, as a partnership must be reported by both communicating peers. Moreover, as discussed in [START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF], a collusion attack by peers trying to appear as more cooperative than they really are could be detected as these peers would appear as a cluster in the overlay. A collusion of peers to promote a single peer is harder to detect. One approach is to analyze the history of partnerships of a peer to identify bias, as proposed by Guerraoui [START_REF] Guerraoui | LiFTinG: Lightweight Freerider-Tracking Protocol in Gossip[END_REF]. Another approach against malicious peers is to use cryptographically-signed messages, like in Contracts [START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF], to allow the server to verify partnerships and cooperation levels reported by peers. In this case, our model could be used jointly with Contracts, reducing the volume of cryptographic receipts and thus computational and communication costs. Instead of collecting cryptographic receipts for each sequence of packets exchanged, as originally proposed, the tracker could infer the authenticity of the out-degree collected from each peer by first checking the reports of communicating peers, and requesting cryptographic receipts only to audit lying or omissive peers.

Finally, one question that may arise is why not simply send the measured CL values directly to the tracker instead of relying on centrality measures to predict them. The main reasons for not doing that are: (1) partnership information is already available or could be easily obtained by the tracker in most current applications, and (2) frequently sending measured CL values, either aggregate values (as used here) or per-partner values, would possibly incur in extra communication overhead, if authentication mechanisms are applied (as in [START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF]), or be less resilient to lies and collusion attacks, otherwise.

Conclusions and Future Work

We investigated the correlation between a peer's cooperation level CL and its centrality in the overlay network of a P2P live streaming application. Using data collected from SopCast, we first showed that three centrality metrics, namely out-degree, closeness, and betweenness, are significantly correlated with CL, although the former presents stronger correlations and is able to better discriminate non-cooperative and cooperative peers. We then proposed a non-linear regression model that uses previous measures of out-degree to predict the peer's CL value in the near future. Our model produces reasonably accurate estimates in most cases, being able to correctly identify 97% of the non-cooperative peers and 85% of the very altruistic peers. Thus, it can be applied jointly with existing techniques, providing evidence to help identify such peers and to drive incentive mechanisms that rely on estimates of peer cooperation [START_REF] Chatzidrossos | Server guaranteed cap: An incentive mechanism for maximizing streaming quality in heterogeneous overlays[END_REF][START_REF] Piatek | Contracts: Practical Contribution Incentives for P2P Live Streaming[END_REF].

Future directions include analyzing our model under approximate inputs, larger and dynamic client populations, and collusion attacks.

Fig. 1 .

 1 Fig. 1. Peer Cooperation Level (CL) for Various Window Durations (W ).

Fig. 2 .Fig. 3 .

 23 Fig. 2. Distributions of Spearman Correlation Between Centrality and Cooperation Level (CL)

Fig. 4 .

 4 Fig. 4. Differences in Normalized Peer Out-Degree for Windows t and t + k (W =60). Fig. 5. Predicted vs. Measured CL (W =60)

Fig. 5 .

 5 Fig. 4. Differences in Normalized Peer Out-Degree for Windows t and t + k (W =60). Fig. 5. Predicted vs. Measured CL (W =60)

(a) CL < 1 (b) 1 ≤ 10 Fig. 6 .

 11106 Fig. 6. Distribution of Prediction Errors for Various Ranges of Measured Cooperation Levels

10 Fig. 7 .

 107 Fig. 7. Distribution of Prediction Errors as Function of Model Calibration Period k (W = 60s)

The Probability Density Functions are: pX (x) = αβx β-0 e -αx β I (0,∞) (x) for Weibull, and pX (x)= λe -λx for Exponential.

http://www.wireshark.org

This model has the advantages of taking only a peer's out-degree as input and requiring calibrating only two parameters. This reduces the computational cost, compared to, e.g., a model that requires computing betweenness, which has complexity O(V E) for a network with V nodes and E edges[START_REF] Brandes | A Faster Algorithm for Betweenness Centrality[END_REF], and might have limited practical deployability.

This work is supported by the INWeb (MCT/CNPq grant 57.3871/2008-6), and by the authors grants from CNPq and FAPEMIG 1 http://www.sopcast.com, http://www.pptv.com, and http://www.uusee.com.


Yuedong Xu
email: yuedong.xu@gmail.com

Eitan Altman
email: eitan.altman@inria.fr

Rachid El-Azouzi
email: rachid.elazouzi@univ-avignon.fr

Salah Eddine Elayoubi
email: salaheddine.elayoubi@orange.com

Majed Haddad

QoE Analysis of Media Streaming in Wireless Data Networks

Keywords: Media streaming, Quality of Experience, Starvation Probability, Prefetching Delay, Ballot Theorem

The purpose of this paper is to model quality of experience (QoE) of media streaming service in a shared fast-fading channel. In this context, the arrival and the service processes of the playout buffer do not have the same job size. We present an analytical framework based on Takács Ballot theorem to compute the probability of buffer starvation and the distribution of playback intervals. We model the arrival processes of Proportional Fair and Round Robin schedulers, and feed them into this framework to study the impact of prefetching on the starvation behavior. Our simulations match the developed model very well if the base station knows the playback rate and the channel gain. Furthermore, we make an important observation that QoE metrics predicted by users are very sensitive to the measurement error of arrival process.

Introduction

With the widespread use of smart phones, Http streaming service is become more and more popular on cellular networks. In contrast to the rapid growth of users and traffic load, the bandwidth provision usually lags behind. Under this context, media servers and network operators face a crucial challenge on how to avoid the degradation of user perceived media quality, namely quality of experience (QoE). The most undesirable case is the interruption of playback when users watch videos or listen to music. The primary goal is to avoid the starvation of playout buffer or to reduce the frequency of starvation. One feasible way is to introduce a start-up (also called prefetching) delay before playing the stream, and a rebuffering delay after each starvation event. After a number of media frames accumulate in the buffer, the media player starts to work. However, a large delay may impair the user perceived streaming quality, which demands an appropriate setting of content prefetching.

In this work, we evaluate the impact of prefetching thresholds on the starvation probability and the playback interval in a cellular downlink system. We aim to answer the following questions: 1) how can we model the starvation behavior in a playout buffer whose arrival and service processes work at different levels (e.g. arrival at the bit level and service at the video frame level); 2) how efficient can a user predict its starvation behavior based on local measurement of arrival process. In our setting, mobile users experience Rayleigh fast-fading. The base station adopts proportional fair (PF) or round-robin (RR) algorithms to schedule a user for transmission in each slot. To carry out the analysis, we first model the playout buffer as a GI/D/1 queue whose arrival process is determined by the wireless scheduler. Then, a probabilistic framework is proposed to compute the starvation probability and the playback interval based on Takács Ballot theorem [START_REF] Takács | Ballot Problems[END_REF]. In comparison with recent works [START_REF] Hao Luan | Impact of network dynamics on users' video quality: analytical framework and QoS provision[END_REF][START_REF] Liang | Effect of delay and buffering on jitter-free streaming over random VBR channels[END_REF][START_REF] Parandehgheibi | Avoiding Interruptions a QoE Reliability Function for Streaming Media Applications[END_REF][START_REF] Xu | Probabilistic Analysis of Buffer Starvation in Markovian Queues[END_REF], we consider a network with shared resource, instead of a single streaming session. The arrival process and the departure process do not work at the same granularity of jobs. The Ballot theorem approach provides a simple way to compute the starvation behaviors.

Our study leads to the following interesting observation. The QoE metrics predicted by a user are very sensitive to the estimation error of arrival process. Especially, the prediction is not meaningful in the heavy traffic regime (i.e. arrival rate approaches service rate). This phenomenon implies that autonomous QoE optimization of mobile users may not perform well in a wireless downlink.

The rest of this work is organized as follows. In section 2, we characterize the QoE metrics in a Wireless fading environment. Section 3 presents a probabilistic framework for QoE analysis. In section 4 we present numerical studies. Section 5 concludes this paper.

Media Streaming Service and Quality of Experience

In this section, we present a GI/D/1 queue model for persistent media streaming service, and define a set of metrics for the user perceived streaming quality.

The wireless downlink is shared by multiple elastic flows that can be http media streams, ftp downloading, or other real-time services with flow control. The system architecture with N streaming users is shown in Fig. 1. Mobile users request streaming service from media servers, and the media streams are transmitted by the base station over a fast fading channel. The streaming system in Fig. 1 is composed of two types of buffers, the wireless buffer at the base station as well as the playout buffer at the user side. We assume that the media streams always have backlogged packets in the wireless buffer. This assumption holds due to two reasons. First, the online movies are usually very large, ranging from 100MB to 1GB. Second, most of Internet streaming servers use HTTP protocol (over TCP) to deliver streaming packets. TCP congestion control mechanism exploits the available bandwidth by pumping as more packets as possible to the wireless buffer. Therefore, we can simply regard the wireless buffers to be always saturated. The wireless buffer and the playout buffer work in a tandem way, which means that the departure process of a user in the former is exactly the arrival process in the latter. However, they work at different time scales and at different layers. The wireless buffer works at the bit level due to the bit loading in the lower layers, and the playout buffer functions at the video frame level. The playout buffer at a mobile user stores packets transmitted over the wireless channel. The streaming packets are reassembled into groups of pictures namely "frames" according to the codec of source coding. The size of a frame depends on streaming quality, e.g. a high-definition (HD) video requiring more bits to render each frame. When the media player starts, those frames are served with a deterministic rate. Here, the term "frame rate" refers to the number of pictures that are displayed per second (e.g. 24fps, 25fps, and 30fps). We define P-slot D p as the constant service interval in the playout buffer. For a playback rate 25fps, the duration of a P-slot is 40ms. Let Q(t) be the number of frames at time t in the playout buffer and A(t) be the arrival rate of frames. Then, the playout buffer is modeled as a GI/D/1 queue,

Q(t + 1) = [Q(t) -1] + + A(t + 1), (1)
where [x] + denotes the maximum between 0 and x. The general arrival process A(t) is determined by the throughput distribution of a particular flow at the wireless buffer. The maximum buffer size is assumed to be large enough so that the whole media file can be stored without packet drops. When Q(t) is below a certain threshold, the media player halts. We call this event a starvation. Without loss of generality, we set the starvation threshold to be 0 frame at the beginning of each P-slot. The starvation property (e.g. probability or frequency) is an important measure of the quality of experience for media streaming services. To avoid starvation, a prefetching stage is introduced by almost all the commercial streaming applications. When a streaming session is initiated, the media player starts to play until the number of accumulated frames reaches a certain value called start-up threshold. One extreme strategy is to download the whole video file before watching. However, the prefetching may cause a long initial waiting time called start-up delay, which is usually unwanted. Therefore, an appropriate choice of the start-up threshold is vital to the users' quality of experience. For a long video stream, starvation events can take place more than once. If the streaming service interrupts during its playing, the media server restarts after a number of packet arrivals. We call this threshold rebuffering threshold, and the induced time rebuffering delay. The streaming provider can either set the same value for the rebuffering and the start-up thresholds, or tune the rebuffering threshold adaptively. Our study in this work is concentrated on long media streams, in which N flows are either persistent or coexisting for a long period. The QoE metrics include the startup delay, the rebuffering delay, the starvation probability, and the continuous playback interval. Similar metrics has been used in [START_REF] Dobrian | Understanding the Impact of Video Quality on User Engagement[END_REF] to reveal the interplay between QoE and user satisfaction.

Probabilistic Framework For Analyzing QoE

Preliminaries: Transmissions over a Rayleigh Fading Channel

We consider the media streaming service over a single-cell wireless downlink using HSDPA or EV-DO1 . The base station is transmitting to a set of mobile users denoted by N = {1, 2, • • • , N }. The wireless channel is shared by all the mobiles where time slot is the allocable resource. We denote by D s the duration of a scheduling slot (S-slot). In general, D s is smaller than D p , (e.g. D s = 2ms [START_REF] Bonald | Opportunistic Scheduling of Voice and Data Traffic in Wireless Networks[END_REF]). Define an integer K := D p /D s (if D p /D s is not an integer, our method still applies with slight modification). The wireless channel is assumed to undergo a Rayleigh fast fading due to the mobile environment. This assumption enables us to treat the SNRs of a user to be independent and identically distributed (i.i.d.) in different time slots (see e.g. [START_REF] Combes | Cross-layer analysis of scheduling gains: Application to LMMSE receivers in frequency-selective Rayleigh-fading channels[END_REF]).

Denote by Γ the symbol of SNR and by γ i the value of user i's SNR. Then, γ i is a random variable with the probability density function given below

g Γ (γ i ) = 1 γi exp(- γ i γi ), ( 2
)
where γi is the average SNR of user i. The BS decides not only the user for transmission, but also the modulation and coding scheme (MCS). To help the BS determine the appropriate MCS, each user measures its channel quality and feedbacks channel quality information (CQI) to the BS. We adopt the square M-ary quadrature amplitude modulation (M-QAM) with M = 2 2r , r = 0, 1, 2, • • • , r, where r is the highest modulation order (or equivalently the maximum information bits in each signal). The case r = 0 means that the transmission fails. Given the fact that the loaded bits take all values between 0 and r, the SNR is partitioned into r + 1 disjoint regions. Denote by R r the SNR region of the r th rate. Denote by b r the lower boundary of R r that has 0 [START_REF] Chang | Cross-layer QoS Analysis of Opportunistic OFDM-TDMA and OFDMA Networks[END_REF].Thus, R r is written as [b r , b r+1 ). In this paper, the BER requirement is taken as 10 -5 . Let B be the spectrum frequency in Hz. If user i is scheduled in a S-slot with modulation M = 2 2ri(t) at time t, the number of transmitted bits is 2Br i (t)D s .

= b 0 < b 1 < • • • < b r+1 := ∞. The boundary b r is obtained by b r = -2 3 (ln(5BER))(2 2r -1)
In the past decade, a large body of scheduling algorithms have been proposed for various design purposes. Here, we look into two representative schedulers, the SNR-based proportional fairness (PF in abbreviation) [START_REF] Combes | Cross-layer analysis of scheduling gains: Application to LMMSE receivers in frequency-selective Rayleigh-fading channels[END_REF][START_REF] Choi | Cell-throughput analysis of the proportional fair scheduler in the single-cell environment[END_REF] and the round robin (RR) algorithms.

PF Scheduling: PF scheduler selects the user i * with the highest relative SNR for transmission, that is,

i * = arg max i∈N γ i γi , ∀i ∈ N . ( 3
)
We consider a heterogeneous scenario in which different users have different average SNR values due to different path losses. When PF scheduling is adopted, the user with the highest relative SNR is selected for transmission. Then, we obtain the following probability

P{user i scheduled |γ i = γ} = P{ γ γi > γ j γj , ∀j ∈ N \ i} = ( 1 -exp(- γ γi ) ) N -1 .
We denote by γ * i the SNR of user i if it is scheduled. Its distribution is calculated by:

P{γ * i < Γ } = ∫ Γ 0 1 γi exp(- γ γi ) ( 1 -exp(- γ γi ) ) N -1 dγ = 1 N ( 1 -exp(- Γ γi ) ) N .
Denote by β * i,r the probability that user i is scheduled with rate r, (r ≥ 1). Then, β * i,r is obtained by

β * i,r = P {b r ≤ γ * i < b r+1 } = 1 N (1 -exp(- b r+1 γ )) N - 1 N (1 -exp(- b r γ )) N .
Let β * i,0 be the probability that user i is not scheduled, or the SNR of user i is below b 1 . Then, the equality β * i,0 = 1 -∑ r r=1 β * i,r holds. Given the probability of using r-QAM modulation, we can derive the p.g.f. of U by

Φ i U (z) = β * i,0 + r ∑ r=1 β * i,r • z r . ( 4
)
The p.g.f. in (4) yields the expectation and the variance

µ = r ∑ r=1 rβ * i,r and σ 2 = r ∑ r=0 β * i,r (r -µ) 2 . ( 5
)
The p.g.f. Φ W (z) is obtained by convoluting Φ U (z) for K times. Applying our derivations in section 3, we can obtain the QoE metrics of a streaming user with PF scheduling.

Round Robin Scheduling:

We consider a simplified scenario where a P-slot is evenly divided into N S-slots. Denote by β r the probability of SNR within R r . Then,

β r = exp ( - b r γ ) -exp ( - b r+1 γ ) , r = 0, 1, • • • , r. (6)
Therefore, the probability generating function is given by

Φ U (z) = (1- 1 N + β 0 N ) + r ∑ r=1 β r N • z r . ( 7
)
The expectation and the variance of U are obtained by

µ = r ∑ r=1 rβ r N and σ 2 = (1- 1 N + β 0 N )µ 2 + r ∑ r=1 β r N (r -µ) 2 . ( 8
)

Interaction Between Scheduler and Playout Buffer

We define a set of random variables to measure the user throughput in bits/Hz per S-slot. Let the i.i.d. random variable U (s) denote the modulation scheme at the S-slot s. The number of bits transmitted in S-slot s is U (s) × 2BD s . We denote by W the sum of U (s) in K S-slots, i.e. W := ∑ K s=1 U (s). The volume of the transmitted bits in a P-slot is W (s)×2BKD s . Let V k record the transmitted bits in k P-slots, i.e., V k := ∑ k t=1 W (t). Recall that Φ U (z) is the p.g.f of U that depends on the used scheduler, as detailed previously . Due to the i.i.d. property, the probability generating function of W , Φ W (z), is

Φ W (z) = [Φ U (z)] K , ( 9
)
and that of V k , Φ V k (z), is

Φ V k (z) = [Φ W (z)] k . ( 10
)
Denote by µ and σ the mean and the standard deviation of U , respectively. Then, W has a mean Kµ and a standard variation √ Kσ. Similarly, the mean and the standard deviation of V k are kKµ and √ kKσ. We further define new variables as follows:

ϕ U (j) = P{U = j}, ϕ V (k, j) = P{V k = j}, ϕ W (j) = P{W (t) = j}, F U (x) = P{U ≤ x}, F W (x) = P{W ≤ x}, and F V (k, x) = P{V k ≤ x}.
In what follows, we define a constant c := 2BD s /d where d is the video frame size in bits. Define a new variable ρ := cKµ as the traffic load.

The p.g.f. of V k is obtained from k convolutions of W . The r.v. W takes integer values from 0 to K r. Then, V k takes values from 0 to kK r. As k is large, it needs a heavy computation to obtain ϕ V (k, j). When k is large enough, we can approximate V k by a diffusion process according to Donsker's theorem [START_REF] Donsker | Justification and extension of Doob's heuristic approach to the KolmogorovCSmirnov theorems[END_REF],

V k ≈ kKµ + √ Kσ • B(k) + o( √ k), ( 11
)
where B(k) is a standard Brownian motion and the symbol ≈ denotes "has approximately the same distribution as". We define X for the frame arrival to the playout buffer in each P-slot. Denote Y k := ∑ k t=1 X(t) to be the total frame arrivals in k P-slots. In a P-slot, W takes integer values in the set [0, K r]. Define a constant R := ⌈cK r⌉. The r.v. X(t) takes values from 0 to R. The exact distributions of X and Y k are intractable because the number of arrived media frames can be a fractional value in reality. Even if the distribution of X is known, it is still complicated to obtain the distribution of Y k for large k. To carry out our analysis, we make two important assumptions:

-The r.v., X(t), is i.i.d. at all time t; -The stochastic process {Y k } has

Y k ≈ Ỹk = ckKµ + cσ √ K • B(k) + o( √ k), ( 12
)
where { Ỹk : k > 0} is the approximated diffusion process.

By simplifying the arrival process to the playout buffer, we can approximate the probability mass function by

P{ Ỹk = y} ≈ Φ Ỹ (k, y) = 1 √ 2πkKcσ exp ( - (y -ckKµ) 2 2kK(cσ) 2
) .

(13)

Computing Playback Interval: A Ballot Theorem Approach

In this paper, we consider the scenario of infinite size of media files. Because a "tagged" user is examined, the user index is dropped in all r.v.s. Given the rebuffering threshold, we are interested in the probability distribution of continuous playback interval T I (in P-slots). Let P-slot 1 be the starting point of time axis when media player resumes. We denote by P ns (l, x r ) the probability of no starvation in the duration [1, l],

Pns(l, xr) = P{ t ∑ s=1 X(s) -(t -xr) > 0, ∀ xr ≤ t < l}. ( 14
)
An intuitive explanation of eq.( 14) is the following. The prefetched x r frames will be served in x r P-slots. If there is no new arrival, i.e. ∑ xr s=1 X(s) = 0, the media player meets with an empty buffer at the beginning of slot x r +1, thus causing a starvation event. Therefore, ∑ xr s=1 X(s) must be greater than 0 if there is no starvation. Similarly, we can replace x r by an arbitrary t, (t > x r ).

The direct computation of P ns involves a number of complicated iterative equations. We hereby adopt the famous Ballot theorem for a combinatorial analysis. The version of most referenced Ballot theorem is developed by Takács [START_REF] Takács | Ballot Problems[END_REF].

Theorem 1. (Takács Ballot Theorem) If X(1), X(2), • • • , X(L) are cyclically interchangeable random variables taking on nonnegative integer values summing to k, then

P { t ∑ s=1 X(s) < t, ∀ t ∈ [1, l] } = [l -k] + l , (t > xr). ( 15
)
The Takács Ballot Theorem presents a probability that the number of departures is larger than that of arrivals in all l slots. Because X(s) is i.i.d. at different time s, it is cyclically interchangeable. Suppose that the starvation event happens after the media player has worked for t slots, t > x r . The total number of consecutive departure slots is t-1, and the total number of arrivals is t-1-x r . We create a backward time axis where the starvation event happens at slot 1.

The number of departures is always greater than that of arrivals. Otherwise, the starvation event has already taken place. Hence, according to Takács Ballot theorem, the probability of the departure process leading the arrival process is

P { t ∑ s=1 X(s) < t, ∀t ∈ [1, l] } = xr t-1 . ( 16
)
Therefore, the probability that the first starvation takes place at slot t is

Ps(t) = xr t-1 • P{ t-1 ∑ s=1 X(s) = t-1-xr}, (t ≥ xr + 1) ≈ xr t-1 • P{ Ỹt-1 = t-1-xr} = xr t-1 • Φ Ỹ (t-1, t-1-xr) (17) = xr t-1 • 1 √ 2π(t -1)Kcσ exp ( - (t-1-xr -c(t -1)Kµ) 2 2(t -1)K(cσ) 2 ) = xr √ 2π(t -1) 3 Kcσ exp ( - ((t-1)(1 -cKµ) -xr) 2 2(t -1)K(cσ) 2 ) . ( 18
)
The approximation in eq.( 17) means that the actual frame arrival process is replaced by the corresponding Brownian motion. Eq.( 18) yields the c.d.f. of continuous playback interval

P{T I ≤ l} = l ∑ t=xr+1 P s (t) = l ∑ t=xr+1 x r √ 2π(t -1) 3 Kcσ exp ( - ((t-1)(1 -cKµ) -x r ) 2 2(t -1)K(cσ) 2 ) . ( 19
)
The starvation probability of an infinite file size is equivalent to P{T I ≤ ∞}. According to Lemma 1 in [START_REF] Xu | Probabilistic Analysis of Buffer Starvation in Markovian Queues[END_REF], eq.( 19) with l = ∞ is further approximated by

P tot s (∞) := { 1 if ρ < 1; exp ( 2xr(1-cKµ) K(cσ) 2 ) otherwise . ( 20
)
The probability of starvation is determined by the start-up threshold x r and the traffic load ρ. If ρ is less than one, the starvation is inevitable. For ρ > 1 and x r is large enough, the starvation probability is negligible. The probability of no starvation P ns is the complement of P tot s . Next, we compute the average playback interval by

E[T I ] = ∞ ∑ t=xr+1 (t -1) • P s (t) ≈ x r (1 -cKµ) , if cKµ < 1. ( 21
)
The analysis of above approximation can be found in the technical report [START_REF] Xu | QoE Analysis of Media Streaming in Wireless Data Networks[END_REF]. If E[T I ] is infinitely large, the starvation event takes place only in the beginning.

Computing Start-up/Rebuffering Delays

The start-up delay T p denotes the number of minimum required P-slots to have Y Tp ≥ x p . Its cumulative probability distribution is expressed as

P{T p < t} = P{Y t ≥ x p } ≈ ∫ xp 0 1 √ 2πtKcσ exp ( (x -cKµt) 2 2tK(cσ) 2 ) dx. ( 22
)
The expected start-up delay, E[T p ], is easily obtained as the busy period of GI/G/1 queue,

E[T p ] = x p E[X] = x p cKµ . ( 23
)
Similarly, we can compute the distribution of rebuffering time T r .

Prediction of the starvation behavior by the user

The computation of eq.( 19),( 20) and ( 21) relies on µ and σ that are only accessible to the BS. An important question is how a user predicts the starvation behavior based on local measurement of arrival process. Define a time window T W in P-slots. A user records the complete frame arrival at each P-slot of the time window T W . We construct a r.v. X and a stochastic process { Ȳk : k > 0}. The r.v. X characterizes the frame arrival to the playout measured by the user, and the r.v. Ȳk := ∑ k t=1 X(t). Let μ and σ2 be the mean and the variance of X.Therefore, Φ Ỹ (t-1, t-1-x r ) in eq.( 18) is substituted by Φ Ȳ (t-1, t-1-x r ).

Given the i.i.d. assumption of X, Ỹk can be approximated by the Brownian motion Ȳk ≈ k μ + √ kσ • B(k) for large k. The media player can use eq.( 20) and (21) to predict the starvation probability and the expected playback interval respectively. We only need to substitute cKµ by μ, and substitute √ Kcσ by σ.

Simulation

The main goal of this section is to validate the accuracy of QoE model. Due to the page limit, our simulation is confined to the network where the users have same average SNR and the BS adopts PF scheduler. (More simulation studies can be found in the technical report [START_REF] Xu | QoE Analysis of Media Streaming in Wireless Data Networks[END_REF].) The frequency width of wireless channel is set to 2MHz. The base station adopts the proportional fair algorithm to schedule users every 2ms. 4-QAM, 16-QAM and 64-QAM modulation schemes are adopted. We assume that the durations of all video streams are large enough.

Each stream has a playback rate of 300Kbps and a frame rate of 25fps. For each scenario, we conduct three hundreds of simulation runs. The first set of experiments demonstrate the c.d.f. of playback interval for different values of user population and average SNR. For each set of parameters, we compare the c.d.f. curves obtained from the model at the BS side, the model at the receiver side, and the simulation. The model at the BS side is computed by eq.( 19). The model at the user side is also obtained from eq.( 19), but with substitutions of cKµ by μ and √ Kcσ by σ. The time window of measuring the arrival process is set to 200 P-slots (equivalent to 8s). We plot the c.d.f. of playback intervals with x r = 100 and x r = 200 in Fig. 2. The wireless channel is shared by 20 homogeneous users, and the average SNR of a user is 10 dB. The average number of frame arrival is 0.73 per P-slot so that the starvation event happens for sure. Fig. 2 exhibits a very good matching between the playback interval model computed by the BS and the simulation. However, the model based on user measurements is far away from accuracy. Our simulations provide an important insight that the QoE prediction at the user side might not work very well. The second set of experiments evaluate the average playback interval when user number and the average SNR change. In Fig. 3, the number of users increases from 16 to 40, the average playback interval reduces. We have two observations here. One is that the slop of decrease is much more prominent in the range 16 ≤ N ≤ 24 than that in the range 26 ≤ N ≤ 40. Here, the expected frame arrival rate is 0.619 frame per P-slot at N = 24 and 0.897 frame per P-slot at N = 16. The other observation is that the average playback interval predicted by a user is not accurate at N = 16. The predicted value is very sensitive to the measurement error when the frame arrival rate is close to 1.

The third set of experiments explore the behavior with respect to the rebuffering threshold. We only compare the model at the BS side and the simulation. Fig. 4 illustrates the probability of future starvation after the current rebuffering. Since the starvation happens certainly with ρ ≤ 1, we only consider the case where ρ is slightly greater than 1. Suppose that a cell has 19 homogeneous users with average SNR of 12dB. The frame arrival rate computed from the model is 1.0492 frames per P-slot. We compare the probability of starvation computed from (20) and that of simulation. Our experiments validate the accuracy of the asymptotic starvation probability and startup delay. The figure 4 also shows that the average startup delay increases linearly with the rebuffering threshold, with a perfect match between simulation and model.

Conclusion and Future Work

We analyzed the starvation behavior for users experiencing Rayleigh fading in a wireless channel. The arrival and the service processes of a playout buffer do not function at the same job size, nor at the same time scale. We use Takács Ballot Theorem to compute the metrics related to buffer starvation in a very simple way. When the knowledge of arrival process is complete (e.g. at the BS side), our model matches the simulation result very well. When the arrival process is measured by the playout buffer, the prediction of starvation behavior is inaccurate. Hence, our study suggests that the BS, instead of autonomous users, should be responsible for the QoE optimization. In the future, we aim at assessing the impact of flow dynamics on finite video streams and at developing QoE optimization schemes that take into account the dynamic flow arrivals and departures.

Fig. 1 .

 1 Fig. 1. Media streaming system in wireless cellular networks

InaccurateFig. 2 .

 2 Fig. 2. CDF of playback interval: N = 20 and γ = 10dB

Fig. 3 .

 3 Fig. 3. Average playback interval with different user numbers: γ = 10dB

Fig. 4 .

 4 Fig. 4. Probability of Starvation and Average Start-up Delay

Our analysis can be easily extended to 3G long term evolution (LTE) networks if time slot is substituted by OFDMA resource block.

Acknowledgements: This work was supported by a contract with Orange Lab, Issy Les Moulineaux. The authors would like to thank the anonymous reviewers for their valuable comments to improve the quality of the paper.