Thomas Stoll
email: thomas.stoll@univ-lorraine.fr

ON SIMULTANEOUS DIGITAL EXPANSIONS OF POLYNOMIAL VALUES

.

Introduction

Let q ≥ 2. Then we can express n ∈ N uniquely in base q as n = j≥0 n j q j , n j ∈ {0, 1, . . . , q -1}. (1) Denote by s q (n) = j≥0 n j the sum of digits of n in base q. The sum of digits of polynomial values has been at the center of interest in many works. We mention the (still open) conjecture of Gelfond [START_REF] Gelfond | Sur les nombres qui ont des propriétés additives et multiplicatives données[END_REF] from 1967/68 about the distribution of s q of polynomial values in arithmetic progressions (see also [START_REF] Drmota | The sum of digits function of polynomial sequence[END_REF][START_REF] Mauduit | La somme des chiffres des carrés[END_REF][START_REF] Stoll | The sum of digits of polynomial values in arithmetic progressions[END_REF]) and the fundamental work of Bassily and Kátai [1] on central limit theorems satisfied by s q supported on polynomial values resp. polynomial values with prime arguments.

In 1978, Stolarsky [START_REF] Stolarsky | The binary digits of a power[END_REF] examined the pointwise relationship between s q (n h ) and s q (n), where h ≥ 2 is a fixed integer. In particular, he used a result of Bose and Chowla [2] to prove that (2) lim sup

n→∞ s 2 (n h ) s 2 (n) = ∞.
Hare, Laishram and Stoll [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF] generalized (2) to an arbitrary polynomial P (X) ∈ Z[X] of degree h ≥ 2 in place of X h , and to base q in place of the binary base. Moreover, they showed that on the other side of the spectrum,

(3) lim inf n→∞ s q (P (n)) s q (n) = 0, confirming a conjecture of Stolarsky.

From another point of view, not much is known about the pointwise relationship between the sum-of-digits of the values of two distinct fixed

The second author was supported by the Agence Nationale de la Recherche, grant ANR-10-BLAN 0103 MUNUM.

integer-valued polynomials P 1 (X), P 2 (X). Building up on work by Drmota [START_REF] Drmota | The joint distribution of q-additive functions[END_REF], Steiner [START_REF] Steiner | On the joint distribution of q-additive functions on polynomial sequences[END_REF] showed that the distribution of the two-dimensional vector (s q (P 1 (n)), s q (P 2 (n))) n≥1 obeys a central limit law (in fact, his results apply for general vectors and general q-additive functions). However, there are no local results available, such as an asymptotic formula or even a non-trivial lower estimate for [START_REF] Drmota | The sum of digits function of polynomial sequence[END_REF] #{n < x :

s q (P 1 (n)) = k 1 , s q (P 2 (n)) = k 2 },
where k 1 and k 2 are fixed positive integers.

The purpose of the present work is to extend both ( 2) and ( 3), and to make a first step towards understanding [START_REF] Drmota | The sum of digits function of polynomial sequence[END_REF].

Our main result is as follows:

Theorem 1.1. Let P 1 (X), P 2 (X) ∈ Z[X] be polynomials of distinct degrees h, l ≥ 1 with P 1 (N), P 2 (N) ⊂ N. Then s q (P 1 (n)) s q (P 2 (n)) n≥1 is dense in R + .
Remark 1. The proof extends to strictly q-additive functions in place of the sum-of-digits function s q (we need, however, the condition that the weight attached to the digit q -1 is positive, cf. (16)). Recall that a strictly qadditive function f is a real-valued function f defined on the non-negative integers which satisfies f (0) = 0 and f (n) = j≥0 f (n j ), where the n j are the digits in the q-adic expansion (cf. ( 1)).

We first state some notation that is used throughout the paper. For integers a, b with b < a we will write [b, a] for the set of integers {b, b + 1, . . . , a}. For sets A and B, we write mA

= {a 1 + • • • + a m : a i ∈ A, 1 ≤ i ≤ m} and A + B = {a + b : a ∈ A, b ∈ B}.
For the sake of simplicity, we allow all constants to depend on q without further mentioning. Since we fix q already in the beginning there is not much harm to do so.

Proof of the main result

The proof of Theorem 1.1 will proceed in several steps. We first address the case P 1 (X) = X h , P 2 (X) = X l which can be dealt with in a well arranged manner. The key idea in the proof is that [START_REF] Gelfond | Sur les nombres qui ont des propriétés additives et multiplicatives données[END_REF] s q (q u ) = 1, s q (q u -1) = (q -1)u, so that the first value is independent of u (and negligable, as u → ∞) and the second one increases as u increases. In order to exploit this, we construct in Section 2.1 a polynomial p(X) and determine the number of negative coefficients in p(X) t for t ≥ 2. In Section 2.2 we then show that, given a real number r ∈ (0, 1), we can choose the parameters of the polynomial in such a way that the ratios of the numbers of negative coefficients of p(X) h and p(X) l approximate r arbitrarily well. In Section 2.3 we link this ratio to the ratio of the sum-of-digits function under question and show that we obtain the same limit. The final section (Section 2.4) concerns the generalization to arbitrary polynomials P 1 (X), P 2 (X).

2.1. Construction of the polynomial p(X). In this section we construct the polynomial p(X) which we will use later to approximate a given positive real ratio r. To clarify the underlying idea, we recall the method that has been used to prove (3) in [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF] in the case of a monomial P (X) = X h . First, the authors defined the polynomial

p(x) = q k x 4 + q k x 3 -x 2 + q k x + q k
for some (sufficiently large) fixed integer k. This polynomial has one negative coefficient and has the property that all coefficients in the expansion of p(x) h are positive for each fixed h ≥ 2 (each negative contribution to the coefficients is compensated by a large positive weight corresponding to the weights q k ). They then calculated s q (p(q u )) and s q (p(q u ) h ). Since there is a negative coefficient in the expansion of the first value, this tends by [START_REF] Gelfond | Sur les nombres qui ont des propriétés additives et multiplicatives données[END_REF] to infinity for u → ∞. On the other hand, again by ( 5), the second value is bounded for u → ∞, and the result follows.

For a general ratio r we have to make it possible to generate negative signs and to control them at the same time. In this section we prove the following lemma.

Lemma 2.1. Let a, b, k, t ∈ N with a > b > a/2 > 0, t ≥ 2 and (6) a b < t + 1 t . Set A 1 = [0, a -b], A 2 = [a -b + 1, b -1], A 3 = [b, a]
and define the polynomial p(X) ∈ Z[X] by

(7) p(X) = q k i∈A 1 X i - i∈A 2 X i + q k i∈A 3 X i .
Denote by C(p) the number of negative coefficients in the expansion of p(X), and by C(p t ) the number of negative coefficients in the expansion of p(X) t . Then there exists k 0 = k 0 (t, a) such that for all k ≥ k 0 ,

C(p t ) = t((t + 1)b -ta -1).
Moreover, if (t -1)a + b -1 ≥ tb then all coefficients in the expansion of p(X) t are nonzero.

Proof. We first determine the sign structure of the coefficients in the expansion of p(X) t . For 0 ≤ i ≤ t set (8)

Q i = iA 1 + (t -i)A 3 = [(t -i)b, ta -ib].
By [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF] the sets Q i , 1 ≤ i ≤ t, are pairwise disjoint. We claim that there exists an integer k 1 (t, a) > 0 such that for k ≥ k 1 (t, a) all the coefficients of p(X) t of the powers

X m with m ∈ t i=0 Q i
are positive. To see this, we note that the positive coefficients of p(X) that contribute to X m have total weight at least q tk , whereas the total contribution to X m of terms that involve at least one negative coefficient of p(X) is O t,a (q (t-1)k ) (where the implied constant depends on t and a). Therefore, for each t and a there is k 1 (t, a) > 0 such that for all k ≥ k 1 (t, a) the coefficients of p(X) t belonging to powers of the sets Q i are positive. For 0 ≤ i ≤ t -1, we call

G i = [1 + max Q i+1 , -1 + min Q i ] = [ta -(i + 1)b + 1, (t -i)b -1] the gap between Q i+1 and Q i . Each G i contains (9) (t -i)b -1 -(ta -(i + 1)b + 1) + 1 = (t + 1)b -ta -1 integers. Consider the coefficients of X m with m ∈ t-1 i=0 G i .
We claim that for sufficiently large k all these coefficients have negative sign. Since the Q i 's are disjoint, for each X m with m ∈ t-1 i=0 G i there must be a contributing term that involves at least one coefficient attached to some power with exponent in A 2 . We use a similar argument as above: The total contribution from coefficients that involve ≥ 2 terms from A 2 is O t,a (q (t-2)k ). On the other hand, the total weight of those contributions that involve exactly one coefficient from A 2 is (in modulus) at least q (t-1)k . Therefore, there exists an integer k 2 (t, a) > 0 such that for all k ≥ k 2 (t, a) the contributions of the terms that use exactly one term from A 2 are dominating.

The negative coefficients originate from terms that use one, three etc. factors with exponents in A 2 . In order to pin down those terms with negative coefficients, we need only consider those negative coefficients that use exactly one factor from A 2 . We define

N i = iA 1 + A 2 + (t -1 -i)A 3 , 0 ≤ i ≤ t -1.
This simplifies to (10)

N i = [(a -b -1) + (t -1 -i)b, i(a -b) + b -1 + (t -1 -i)a].
In order to completely fill the gaps between two blocks of positive coefficients by negative ones, we suppose that for all i with 0

≤ i ≤ t -1, max N i ≥ min Q i and max Q i+1 ≥ min N i .
It is a straightforward calculation that both inequalities reduce to the same inequality, namely,

(t -1)a + b -1 ≥ tb. ( 11
)
The statement of the lemma now follows from (11) and (9).

2.2.

The number of negative coefficients of p(X) h and p(X) . The aim of this section is to prove the following result.

Lemma 2.2. Let h, l ≥ 1, h = l. Then the sequence C(p h ) C(p l ) a>b>a/2>0 is dense in R + .
Proof. We first consider the case when h > l ≥ 1. Define the functions

f (a, b) = h l • (h + 1) -h a b (l + 1) -l a b and f * (a, b) = h l • (h + 1) -h a b -1 b (l + 1) -l a b -1 b .
First suppose that r = r 1 r 2 ∈ (0, 1) is a given rational number and set (12)

a 0 = r 2 h(h + 1) -r 1 l(l + 1), b 0 = r 2 h 2 -r 1 l 2 .
It is a straightforward calculation to check that a 0 and b 0 satisfy

a 0 > b 0 > a 0 /2 > 0, (13)
a 0 b 0 < h + 1 h < l + 1 l and (14) b 0 -1 ≥ max a 0 2 , hb 0 -(h -1)a 0 , lb 0 -(l -1)a 0 .
The same is true for a 0 replaced by a 0 N and b 0 by b 0 N with N ≥ 1. Set a = a 0 and b = b 0 in Lemma 2.1 and write p = p 0 for the resulting polynomial. Then for sufficiently large k, all gaps in p 0 (X) h and p 0 (X) l are filled with powers having negative coefficients and

C(p h 0 ) C(p l 0 ) = f * (a 0 , b 0 ). Since f (a 0 , b 0 ) = r 1 r 2 this implies that lim N →∞ f * (a 0 N, b 0 N ) = f (a 0 , b 0 ) = r 1 r 2 ,
which proves that (C(p h )/C(p l )) is dense in (0, 1). Now, suppose that 1 ≤ l < h and let r = r 1 r 2 ∈ Q + . Denote by ν the minimal positive integer such that (15) r := r h + 1 l + 1

-ν ∈ (0, 1).

Let a 0 , b 0 the integers corresponding to r from the discussion before. Define p0 (X) = p 0 (X),

pi+1 (X) = pi (X)(1 + X h deg pi +1 ), 0 ≤ i ≤ ν -1.
From this definition we see that C(p h i+1 ) = (h + 1)C(p h i ) and hence C(p h ν ) = (h + 1) ν C(p h 0 ). We therefore get

C(p h ν ) C(p l ν ) = (h + 1) ν C(p h 0 ) (l + 1) ν C(p l 0 ) = (h + 1) ν (l + 1) ν f * (a 0 , b 0 )
and, as before, lim

N →∞ (h + 1) ν (l + 1) ν f * (a 0 N, b 0 N ) = r, as wanted.
We have now shown that (C(p h )/C(p l )) is dense in R + whenever h > l ≥ 1. This implies that (C(p l )/C(p h )) is dense in R + and this finishes the proof of the lemma.

2.3.

The case of monomials. We now turn our attention to the ratio s q (n h )/s q (n l ).

Lemma 2.3. Let h, l ≥ 1, h = l. Then the sequence

s q (n h ) s q (n l ) n≥1 is dense in R + .
Proof. We use the well known splitting property of the sum-of-digits function (see, for example, [6, Proposition 2.1] for a proof): For all m 1 , u ≥ 1 and 1 ≤ m 2 < q u we have s q (m 1 q u + m 2 ) = s q (m 1 ) + s q (m 2 ), ( 16)

s q (m 1 q u -m 2 ) = s q (m 1 -1) + (q -1)u -s q (m 2 -1).
We apply (16) successively to the terms in the expansion of p(q u ) h and p(q u ) l , respectively, and get

lim u→∞ s q (p(q u ) h ) s q (p(q u ) l ) = lim u→∞ s q (p(q u ) h ) u • u s q (p(q u ) l ) = (q -1)C(p h ) (q -1)C(p l ) = C(p h ) C(p l ) .
Since by Lemma 2.2 this ratio is dense in R + , the result follows.

2.4. The case of general polynomials P 1 (X), P 2 (X). We are now ready to prove Theorem 1.1 in its generality.

Proof of Theorem 1.1. Without loss of generality, we can assume that both P 1 (X) and P 2 (X) have positive coefficients since otherwise there exists n 0 = n 0 (P 1 , P 2 ) such that both P 1 (n + n 0 ) and P 2 (n + n 0 ) only have positive coefficients. We construct p(X) as before with the monomials X h , X l in place of P 1 (X), P 2 (X). For t ≥ 1 consider

P (X) = t j=0 c j X j , c j > 0, 0 ≤ j ≤ t.
We claim that for sufficiently large k the polynomial P (p(X)) has the same sign structure in its expansion as p(X) t . First, we know that our construction fills up completely the gaps between Q i+1 (p(X) t ) and Q i (p(X) t ) for any sufficiently large (fixed) k. Moreover, recall that we have shown that for 1 ≤ j ≤ t and 0 ≤ i ≤ j, the total weight attached to each power X m with m ∈ Q i (p(X) j ) (resp. G i (p(X) j )) is at least q jk (resp. is O a,j (q (j-1)k )). Now, the relations ( 8), [START_REF] Stoll | The sum of digits of polynomial values in arithmetic progressions[END_REF] and a comparison of the interval bounds imply that for all i, j and v with 0 ≤ i ≤ t -1, 1 ≤ j ≤ t -1 and 0

≤ v ≤ j, G i (p(X) t ) ∩ Q v (p(X) j ) = ∅.
This means, that P (p(X)) has at least the same number of powers with negative coefficients as p(X) t . On the other hand, if Q i (p(X) t ) ∩ G v (p(X) j ) = ∅ then, as the weight associated to elements of Q i (p(X) t ) is dominant, we can find a sufficiently large k such that the coefficients to powers X m for m ∈ 0≤i≤t Q i (p(X)) are positive. This shows, in particular, that for sufficiently large k the number of negative coefficients in the expansions of P 1 (p(X)) (resp. P 2 (p(X))) is C(p h ) (resp. C(p l )) and the same proof as in the case of monomials as given before can be applied.

Acknowledgment

The second author wants to thank Kevin G. Hare (University of Waterloo) for several discussions on this problem. The authors are grateful to the referee to her/his valuable comments that have led to an improved exposition of the result.


Abbas Bradai
email: bradai@labri.fr

Ubaid Abbasi
email: abbasi@labri.fr

Raul Landa
email: rlanda@ee.ucl.ac.uk

Toufik Ahmed

An Efficient Playout Smoothing Mechanism for Layered Streaming in P2P Networks

Keywords: Peer-to-Peer (P2P) Network, layered streaming, smoothing, scheduling, quality of experience (QoE)

Layered video streaming in peer-to-peer (P2P) networks has drawn great interest, since it can not only accommodate large numbers of users, but also handle peer heterogeneity. However, there's still a lack of comprehensive studies on chunk scheduling for the smooth playout of layered streams in P2P networks. In these situations, a playout smoothing mechanism can be used to ensure the uniform delivery of the layered stream. This can be achieved by reducing the quality changes that the stream undergoes when adapting to changing network conditions. This paper complements previous efforts in throughput maximization and delay minimization for P2P streaming by considering the consequences of playout smoothing on the scheduling mechanisms for stream layer acquisition.

The two main problems to be considered when designing a playout smoothing mechanism for P2P streaming are the fluctuation in available bandwidth between peers and the unreliability of user-contributed resourcesparticularly peer churn. Since the consideration of these two factors in the selection and scheduling of stream layers is crucial to maintain smooth stream playout, the main objective of our smoothing mechanism becomes the determination of how many layers to request from which peers, and in which order.

In this work, we propose a playout smoothing mechanism for layered P2P streaming. The proposed mechanism relies on a novel scheduling algorithm that enables each peer to select appropriate stream layers, along with appropriate peers to provide them.

In addition to playout smoothing, the presented mechanism also makes efficient use of network resources and provides high system throughput. An evaluation of the performance of the mechanism demonstrates that the proposed mechanism provides a significant improvement in the received video quality in terms of lowering the number of layer changes and useless chunks while improving bandwidth utilization.

INTRODUCTION

Over the past few years, layered video streaming has emerged as a promising approach for distribution of multimedia content in P2P networks. The usefulness of layered video coding arises from its ability to support large number of users, while simultaneously handling client heterogeneity in terms of download bandwidth, terminal capabilities and user preferences. With layered video coding, the original video is partitioned into multiple layers, which are then transmitted independently. This allows peers with high capacity to receive all layers of the video and enjoy maximum quality, while peers with lower capacity receive a subset of layers and experience reduced quality.

In order to support layered video streaming in P2P networks, three essential components need to be considered: overlay construction, content delivery and content adaptation. The first two are basic building blocks in most peer-to-peer systems, and as such have received ample attention from the research community. However, in order to tackle heterogeneity in terms of terminal capabilities, network conditions and user preferences, content adaptation is rapidly becoming a core component for such systems. Traditionally, the overlay construction component deals with the selection of appropriate neighbors for the retrieval of content, and the content delivery component is responsible for the requesting and transport of content chunks from the chosen overlay neighbors. In this work we present innovations on both the content adaptation component and its relationship with overlay construction and content delivery. To this end, we consider the appropriate layer selection for layered streaming systems and how to request the chunks of those layers from the overlay neighbors.

The design of algorithms that optimally perform these tasks is non-trivial, especially when uniform, high quality playback is desired. Of the many engineering challenges posed by such design, one of the most important is the fluctuation in available bandwidth between peers. On one hand, the delivery of maximal video quality to the user provides a rationale for the algorithm to aggressively select higher quality layers when sufficient bandwidth becomes available. On the other hand, if this bandwidth is only available for a brief period, the algorithm will soon be forced to fall back to selecting lower quality layers, leading to an undesirable fluctuation in user QoE (Quality of Experience). Therefore, a playout smoothing mechanism must balance the aggressiveness with which it uses bandwidth when it becomes available, and the conservativeness with which it maintains a stable user QoE.

In non-layered streaming, there's almost no difference between high delivery ratio and high throughput, because there is no inter-layer dependency. This is not the case in layered streaming. For instance, under certain bandwidth conditions, the following two scenarios can result in the same throughput, but not the same quality: [START_REF] Zhang | On the Optimal Scheduling for Media Streaming in Data-driven Overlay Networks[END_REF] to select many layers, experiencing low delivery ratio for each one of them, and (2) to select fewer layers, but experiencing a higher delivery ratio for each one of them. It's obvious that although the same throughput is achieved by both methods, the former one is undesirable due to its low delivery ratio for each layer. This problem is further compounded because of inter-layer dependencies:

Since enhancement layers are only useful if lower layers are present, losses at the lower layers can severely degrade system performance and lead to wasted system resources if enhancement layers are selected for which the corresponding lower layers are missing. We will refer as useless chunks to these upper layer chunks that cannot be correctly decoded because some lower layer chunks are missing.

In order to ensure effective bandwidth utilization, the scheduling mechanism should also take into consideration the availability of chunks in the overlay neighbors as well as the link capacity between the receiver peer and its neighbors. The challenge is, then, to find an effective scheduling algorithm that provides stable QoE while fully taking advantage of the available network capacity. In this work, we present a mechanism which achieves the following design objectives:

Smoothing: To design a quality adaptation mechanism with the ability to control the level of smoothness.

Having such a tuning capability, one can tune the quality adaptation mechanism for layered video encoding to minimize the effect on the perceived quality by adding and dropping layers and switching gracefully from one quality level to another.

Efficiency: To design a better scheduling mechanism to ensure the best use of the available download bandwidth in different links taking into consideration the chunks availability in the neighborhood, the urgency of chunks, and the dependencies between layers. The main goal of our scheduling algorithm is to minimize the useless chunk ratio by introducing a priority mechanism for proper delivery of different layers. Thus, the sequence in which chunks of different layers are requested is a critical issue and should be tackled by an efficient scheduling mechanism.

In our work we focus on the bandwidth variation problem and its impact on the quality level fluctuation in layered P2P streaming. We posit that, in addition to content availability on neighbors, the maximum achievable quality level depends critically on the available download bandwidth on the receiver peer.

Hence, we propose an algorithm to select the maximum quality level based on the available bandwidth. This is by efficiently requesting chunks from neighbors while at the same time maintaining a satisfactory level of video smoothness.

We continue with our presentation as follows. First, we present a mechanism for smooth selection of appropriate layers considering the available bandwidth fluctuations in the network. Then, we propose a chunk prioritization strategy that considers the urgency of chunks and the dependencies between the layers to which they belong. We then model chunk scheduling as an assignment problem, and propose an algorithm for its solution that takes into account both the available bandwidth and chunk availability for each peer. The rest of this paper is structured as follows: section II reviews the related work in the area of layered streaming in P2P networks. In order to understand the problem of smoothing and scheduling in layered streaming, we describe problem statement in section III. In section IV, we present the proposed mechanism of playout smoothing for layered streaming in P2P networks. Section V provides the detailed performance analysis of our proposed mechanism. At last, section VI briefly concludes the work.

II. RELATED WORK

There have been numerous efforts in the design and evaluation of layered video streaming systems in the last decade. In addition to its promise in handling client heterogeneity, layered video has recently received attention as an application layer solution to the limited deployment of IP-multicast. We now present some of these works, and contrast them with the one presented in this paper.

To handle changing networks dynamics, several layered streaming systems have been proposed video stream from multiple congestion controlled senders, and is able to support a spectrum of noninteractive streaming applications. However, PALS didn't consider the smoothing problem due to bandwidth variation, nor the assignment of chunk requests to appropriate peers. Another example is [START_REF] Hossain | On the Optimality of Layered Video Streaming Rate in a P2P Mesh Network[END_REF] that focused on combining the benefits of network coding with layered streaming to mitigate the inherent challenges in unstructured P2P systems. The work focuses on the average quality satisfaction of the peer, but does not consider the degradation in user's quality of experience (QoE) due to variation in quality levels.

[1][2][2][4][5][5].
Recently, Fernandes et al. [START_REF] Fernandes | An adaptive-predictive architecture for video streaming servers[END_REF] proposed a mechanism for scalable streaming of stored video over the networks with explicit feedback notification. The mechanism considers the unpredictability of the available rate in order to determine the output sending rate target. The authors discussed the possibility of smoothing the information received from the transport layer before making any decision concerning the sending rate. The authors provide a solution to the problem of accommodating the mismatch between the available bandwidth variability and the encoded video rate variability.

Another contribution to the area is [START_REF] Hu | Mesh-based peer-to-peer layered video streaming with taxation[END_REF], in which the authors proposed a taxation-based P2P layered streaming design including layer subscription strategy and mesh topology adaptation. The taxation mechanism is devised to strike the right balance between social welfare and that of individual peers.

Although the work considers the strategy for layer selection, it mainly focuses on fairness in P2P systems.

In [START_REF] Nguyen | Quality-and Context-aware Neighbor Selection for Layered Peer-to-Peer Streaming[END_REF] [START_REF] Zhou | A Simple Model for Analyzing P2P Streaming Protocols[END_REF] and Round Robin (RR) [START_REF] Lu | Research and Design on Peer Selection Strategy of P2P Streaming[END_REF]. Apart from empirical studies, some works use queuing models for scheduling [START_REF] Guo | AQCS: Adaptive Queue-based Chunk Scheduling for P2P Live Streaming[END_REF]. The algorithm proposed in [START_REF] Rajendran | Optimizing the Quality of Scalable Video Streams on P2P Networks[END_REF] minimizes the base layer losses, but it assumes equal rates for the base and enhancement layers. This model of video is rather ideal and can be approximated only by fine grained scalability (FGS). Furthermore, a few theoretical studies tackle the optimal stream scheduling. Most of these works are under restrictive hypothesis or computationally expensive. In [START_REF] Baccichet | Low-delay Peer-to-Peer Streaming using Scalable Video Coding[END_REF] a scheduler has been proposed to maximize the video quality by prioritizing the most important chunks.

This strategy is particularly suited for push-based, tree-structured overlays. The scheduling mechanism proposed in LayerP2P [START_REF] Xiao | On Optimal Scheduling for Layered Video Streaming in Heterogeneous Peer-to-Peer Networks[END_REF] is able to save base layer losses to the detriment of the enhancement layers.

Authors propose to categorize chunks request into two types: regular requests and probing requests. The regular request concerns the requests of layers lower than or equal to a threshold l n , which are firstly assigned to different suppliers based on random scheduling algorithm (that authors believe it achieves a high system throughput) without any prioritization among different layers. Secondly, the probing requests (layer greater than l n ) are sent to the suppliers layer by layer, in ascending manner. The quality threshold l n and the maximum quality level to be requested are decided based of the available download capacity on the receiver peer, by consequence it follows the bandwidth fluctuation without any smoothing mechanism.

The authors in [START_REF] Zhou | Optimal Scheduling for Multiple Description Video Streams in Wireless Multihop Networks[END_REF] propose an optimal scheduling strategy to minimize the overall video distortion, but the approach is strongly related to the Multiple Description (MD) coding, which is less efficient compared with layered coding [START_REF] Zhou | Optimal Scheduling for Multiple Description Video Streams in Wireless Multihop Networks[END_REF]. Zhang et al. [START_REF] Zhang | Optimizing the throughput of data-driven peer-to-peer streaming[END_REF] have discussed the scheduling problem in datadriven streaming systems. They define a utility for each chunk as a function of its rarity, which is the number of potential senders of this chunk, and its urgency, which is the time difference between the current time and the deadline of this chunk. They then use this model to transform the chunk scheduling problem into a min-cost flow problem. This algorithm, however, is computationally expensive and may not be feasible for live video streaming systems subject to strict deadlines on computationally-constrained devices.

Szkaliczki et al. [START_REF] Szkaliczki | Piece Selection Algorithm for Layered Video Streaming in P2P Networks[END_REF] also address the chunk selection problem in streaming layered video content over peer-to-peer networks. The authors present a number of theoretical solutions to maximize the utility function of chunks that exist in the literature. However, their proposed solutions rely on the definition of chunk utility functions whose objective definition may be difficult in real-life scenarios.

III. PROBLEM STATEMENT

One of the problems in assessing the performance of a video delivery scheme is the lack of a good metric that captures the user's perception of video quality. It is generally observed that it is visually more pleasing to watch a video with consistent, lower quality than one with higher but varying quality [START_REF] Zink | Subjective Impression of Variations in Layer Encoded Videos[END_REF].

However, reducing the quality to a bare minimum by following a strictly conservative approach is undesirable, as it fails to adequately take advantage of available overlay resources. The objective of the layer selection mechanism presented in next sections is to optimize the perceived video quality, while at the same time ensuring the smooth delivery of the layered stream. To explain our smoothness criterion, we direct the reader to Figure 1, which exemplifies two possible approaches to stream smoothing for a given available bandwidth profile. In both Figure 1(a) and Figure 1(b), raw stream attempts to precisely track the changing available bandwidth. As a result, the QoE of the user may be severely degraded, especially when there is a drop from a high quality level to a much lower one (as in the case of time slot t 1 and t 4 ). In comparison, the smoothed stream depicted in Figure 1(a) reduces the size of the jump from higher to lower quality level.

The objective here is to ensure a gradual change in quality levels, rather than subjecting the user to widely varying QoE. This technique is referred to as amplitude reduction. An alternative technique is shown in The playout smoothing mechanism should take into consideration two additional factors. Firstly, the smoothing mechanism should neither be too conservative (sacrificing higher quality to achieve long term smoothness) nor too aggressive (sacrificing better smoothness to better take advantage of short-term available bandwidth). Secondly, the smoothing mechanism should also take into the consideration the extra delay for the user that may experience as a side-effect of the smoothing algorithm. This extra-delay may adversely affect the liveness of the stream, thus making it unsuitable for live streaming applications.

Thus, a playback smoothing mechanism should apply both amplitude and frequency reduction to achieve a good tradeoff between user QoE and bandwidth efficiency while incurring low processing delay. Once the playout smoothing mechanism has selected a target quality level, the next step for the algorithm is to decide the order in which the chunks of the selected layers are requested, and from which neighbor peers.

This must be done in such a way that all higher layer chunks available in the decoding buffer can be decoded before their playback deadline expires. If, for any reason a higher layer chunk is acquired and is not decoded on time, resources have been wasted on it, and it is considered a useless chunk. In addition, the playout smoothing mechanism must also utilize available system resources efficiently.

To better explain the problem of scheduling, we assume a mesh-based pull approach in which the receiver side buffer is organized into a sliding window (Figure 2) containing chunks of different layers.

The chunks beyond the playhead position are denoted as the exchanging window; only these chunks are requested if they have not been received yet (the chunks whose deadline has passed will not be requested). Each peer periodically announces the chunks that it holds to all its neighbors by sending a buffer map (Figure 3), a bit vector in which each bit represents the availability of a chunk in the sliding window. Periodically, each peer sends requests to its neighbors for the missed chunks in its exchanging window. As long as its request remains in the exchanging window, chunks are re-requested if not received. Of course, upper layer chunks received without the corresponding lower layer chunks are not decodable (and are considered useless, as described earlier). Thus, the chunks having time stamp T = 5 in Figure 3 are not played, because the base layer was not received.

In order to increase the throughput of the system, our approach aims to take full advantage of the download bandwidth of peers by maximizing the number of chunks that are requested within each scheduling period. Figure 4 illustrates an example of the optimal scheduling problem in terms of bandwidth utilization. For simplicity, in this example we consider a single-layer stream. Peer 1 is the receiving node, and it requests missing chunks from its neighbor peers 2, 3 and 4. Each neighbor advertises the chunks that it holds using a buffer-map. The numbers on the arcs denote the units of bandwidth that the neighbor peer is willing to provide to the receiver node (peer 1) in terms of chunks per unit time. An optimal scheduling scheme for this example is represented in Figure 5, where rows represent the peers and the columns represent the chunks. Chunk 1 is requested from peer 4, chunks 2 and 3 from peer 2, and chunks 4 and 5 from peer 3. This strategy takes full advantage of the available bandwidth of the network. In Figure 6, we represent the result of Round Robin scheduling strategy [START_REF] Lu | Research and Design on Peer Selection Strategy of P2P Streaming[END_REF] applied to the same example. In this case, only 4 chunks out of the total of 5 can be requested in a single time unit. The basic idea of our proposed mechanism is to select the appropriate enhancement layers based on the current quality level and an estimation of the available bandwidth for next time period. In addition, for each chunk belonging to a selected layer, we will define a priority on the basis of its playback deadline and its dependencies with other layers. This priority will then be used to guide chunk scheduling by requesting those chunks with higher priority first.

IV. SCHEDULING FOR SMOOTH LAYERED STREAMING

In this section, we present the core concepts behind our proposed mechanism. We assume a chunkbased, mesh-based pull approach in which chunks are the basic unit of data exchange in the network; each chunk carries information for a given video segment at a given layer. The receiver peer requests content from its neighbors according to the basic architecture depicted in Figure 7. As shown, our proposed scheduling mechanism can be decomposed into two functions: smoothing and scheduling. First, the smoothing function defines the layers to be requested, taking into account the estimated available bandwidth at the receiver peer. In practice, this function operates over two distinct time horizons. The first one, which we will call the initial quality smoothing function, is invoked only once at the beginning of the session, and is responsible for the definition of the complete set of layers that the algorithm will consider at execution time. The second time horizon, which we will call the runtime quality smoothing function, is used during the execution of the algorithm to select, according to measured bandwidth variations, between the set of layers defined at startup.

Once the selection of appropriate layers for the next time period is performed, the scheduling function is then responsible for requesting the necessary chunks to achieve the selected quality level. To this end, this function assigns chunks with priorities according to their playback deadline and layer dependency.

The output of this module is a chunk to peer assignment matrix as shown in Figure 7. The following subsections describe both modules in greater detail.

A. The Smoothing Function

The core objective of the smoothing function is to select which layers will be requested during next time period in order to simultaneously reduce the quality variability for the layered stream (to increase overall QoE) while increasing the overall stream throughput (both to increase overall quality and better make use of available network bandwidth). We will achieve this by first deriving a tradeoff quality level that reduces variability while increasing overall quality, subject to the constraint that the bandwidth required for achieving this quality level should not exceed the available bandwidth at the receiver peer.

We consider a discrete-time model, where each time slot represents an arbitrary number of video chunks. Let represent the selected tradeoff quality level at time t, and the smoothing window size.

In order to provide the smoothing algorithm with relevant information regarding video chunks, we divide the receiver side exchanging window into the following three different intervals (see Figure 8). Of course, due to changing network conditions, the maximum capability information obtained as a result of this initial layer selection process is not sufficient for most practical scenarios. Hence, the runtime quality smoothing function dynamically adjusts layer selection to implement both amplitude and frequency reduction according to variations in available network bandwidth. To implement amplitude reduction, first we estimate the download bandwidth of the receiving peer, and then request the missing chunks according to their priorities as described in next section. For the bandwidth estimation, we aim to utilize an Auto Regressive Integrated Moving Average (ARIMA) time series model that, given information up to time t-1, provides a forecast for time t. The classical approach by Box and Jenkins for modeling and forecasting ARIMA time series is performed in three steps [START_REF] Box | Time series analysis: forecasting and control[END_REF]. First, model identification is used to estimate a model structure by using autocorrelation (ACF) and partial-autocorrelation (PACF)

Playing

                                                                        0 . . . 0
functions to expose dependencies among data. In this case, the major task is to transform a non-stationary series into a stationary one. Once model identification is done, a parameter estimation method is used to fit the identified model to the observed data. This is done by determining the coefficients of the linear model. The last step is then the prediction of future values. For simplicity in our evaluation, we used the bandwidth samples from the last smoothing window to estimate the bandwidth in the next time period.

These available bandwidth values change as the sliding window proceeds.

The estimated bandwidth allows us to select the appropriate quality levels for next time period taking into consideration the amplitude variation. Conversely, to implement frequency reduction, we calculate the quality level that can be sustained for previous smoothing window, and use it to select the quality level for the next one.

We now present our algorithms for both amplitude and frequency reduction, and then a hybrid approach that provides the benefits of both.

i. Amplitude Reduction

The objective of amplitude reduction is, essentially, the reduction in the size of jumps between quality levels. If we assume that quality level jumps are a random variable, this is essentially equivalent to reducing their dispersion around the mean. Therefore, when measuring jump size, we consider the mean quality level achieved during the previous smoothing window. In particular, is defined as:

= ∑ (1)
Where t c is the current playhead position in the video, S W is the size of smoothing window, while L j is the quality level achieved at time period j. The average run metrics can be explained using Figure -9. In this figure, the average run for the time period t 6 can be calculated as We use the average quality in our algorithm for selecting the quality level for next time period, as shown in Figure -10. Our algorithm relies on the mean deviation to decide the quality level at time .

We define as:

= | -1 -|, (2)
Where is the tradeoff quality level at the previous time -1. Let # denote available download bandwidth of the receiver peer at time t, and # $ the estimated bandwidth at time t. Further, let % be the maximum quality that could be sustained with a bandwidth of # $ , and let & ' represent the quality level which can be achieved using the remaining bandwidth in the period t. Then, the following algorithm can be used to calculate the tradeoff quality at the current time .

Smooth layered stream Procedure

if (# % ≥ # -1 * = min( % , -1 + ) else = min( % + 1 , -1 )

end if

Figure-10: Smooth layered stream procedure

The algorithm for amplitude reduction takes two distinct cases into account. Whenever there is an expected increase in available bandwidth, the algorithm provides an increase in the quality level without violating the available bandwidth constraint at the receiving peer. The remaining available bandwidth is used to acquire the chunks in the prefetching buffer. In case of an expected decrease in available bandwidth, the algorithm reduces the amplitude by utilizing the already available chunks. Thus, the algorithm for amplitude reduction focuses on stepwise increase in order to reduce the jump when bandwidth decreases.

ii. Frequency Reduction

The objective of a frequency reduction mechanism is to reduce the number of quality level changes in the layered stream that can occur as a result of varying available bandwidth at the receiver peer. In this case, our objective will be to maintain the same quality level within a particular smoothing window. The frequency reduction mechanism is initialized by selecting the lowest quality for the first smoothing window. Then, the remaining available bandwidth is utilized to acquire the future chunks (these are of course stored in the prefetching buffer). The frequency reduction mechanism can be explained using Figure 11.

In Figure 11(a), the algorithm is initialized with the lowest quality level for the first smoothing window ( = 0 ∀ ∈ [ 4 , 5 ]). The remaining available bandwidth can then be used to prefetch chunks which may be useful during the second smoothing window ( ∈ [ 7 , ]). At the end of first smoothing window, the highest selected quality level in the prefetching buffer is 1. If the # $ as estimated from data in [ 4 , 5 ] is sufficient to acquire all the missing chunks for layer 1, then the quality level will be increased The main idea behind the frequency reduction algorithm is to initiate the quality level at 0 (equivalent to the base layer only) in the first smoothing window, and then use the remaining bandwidth to decide the quality level of the next smoothing window in a conservative manner, acquiring all lower layer chunks before than the higher layer ones. Thus the frequency smoothing mechanism ensures a constant quality level for each smoothing window. The bandwidth change in current smoothing window will ultimately affects the quality level in next smoothing window.

iii. Hybrid approach

The amplitude and frequency reduction mechanisms described earlier focus only on a single aspect of smoothing. We now propose a hybrid approach that provides the benefits of both the amplitude and frequency reduction mechanisms described earlier. To describe this approach, we label each smoothing window with an integer k, so that ( ) denotes the constant stream quality selected for smoothing window k. Our hybrid approach is based on the frequency reduction mechanism presented earlier but also implementing amplitude reduction between successive smoothing windows. We define ( ) as the quality level difference between the current and the previous smoothing windows, as (see Figure 12)

( ) = | ( ) -( -1)|. (3)
Then, the quality level for the k + 1 smoothing window can be calculated with

( + 1) = ' ( + 1) + :( ), (4)
Where ' ( + 1) is the quality level that is available at the beginning of smoothing window + 1 due to prefetching, and : is chosen so that | ( + 1) -( )| ≤ with respect to the maximum quality level allowed by B < $ at the beginning of smoothing window + 1. The appropriate value of : limits the change in the quality level among two successive smoothing windows.

Figure 12: Hybrid approach

B. The Scheduling Function

The main goal of the scheduling function is to efficiently request the missing chunks in the exchanging window of the receiver peer. This can be achieved by requesting the higher priority chunks before the lower priority chunks while at the same time taking full advantage of the available network capacity.

Since, this scheme will closely depend on the definitions of these priorities, we now explain how they are calculated.

Intuitively, it seems clear that since chunks are useless if they are not decoded by their playback deadline, the priority of each chunk should be closely related to how close they are to it. Another issue to consider is the dependency between layers; a higher layer chunk received without its corresponding lower layer chunks will not be decoded. To factor these two variables into our priority model, we will define two functions. The first one, the emergency priority= > , is a function of how close a chunk is to its playback deadline; the second one, the layer priority= ? , is a function of how many underlying layers are

( -1) ( ) ( + 1) ( )
necessary to decode a particular chunk. Using these two functions, we can define our priority function = @ as:

= @ = = > (A @ -B @ * + C= ? ( *

where A @ denotes the current time in the peer i, B @ denotes the playback deadline of chunk j in peer i, L j denotes the stream layer to which chunk j belongs, and θ is a parameter that can be adjusted for different layers prioritization strategies. Hence, = > (A @ -B @ * evaluates = > at a time interval equal to the remaining time that chunk j has until its playback deadline at peer i, and = ? ( * evaluates = ? at an integer proportional to the number of underlying layers needed to decode chunk j.

Different values of θ can be used to implement different protocol behaviors. A small θ leads to the prioritization scheme represented in Figure 13(a), also called conservative chunk scheduling, where the receiver always requests chunks of lower layers first; a large θ leads to the aggressive chunk scheduling scheme represented in Figure 13(b), where chunks are requested on the basis of their timestamp only.

Intermediate values of θ lead to tradeoffs between these two extremes; a particular example of this is shown in Figure 13(c). We continue the presentation of our scheduling algorithm by defining R EF G , a Boolean variable that indicates whether the peer i requests the chunk j from the neighbor k:

H @ = I 1, if peer N requests chunk S from neighbor , 0,
otherwise.

We now present the core of our chunk scheduling heuristic. Using = @ as defined in ( 5), we propose the aggregate priority Π @ of peer i as a figure of merit for our scheduling algorithm:

∑ ∈ ∈ = Π i i N k M j k ij ij i R P , ( 6
)
where U @ denotes the set of chunks that peer i requires from the overlay, and V @ denotes the overlay neighbors of peer i. Using this figure of merit, our scheduling problem can be formulated for each peer i as:

Maximize:

п i Subject to: k i M j k ij C R i ≤ ∑ ∈ (7) 1 ≤ ∑ ∈ i N k k ij R (8)
Where X @ denotes the download capacity of the link between the receiving peer i and its neighbor k. Our scheduling mechanism will therefore maximize a figure of merit that trades off chunk urgency with stream quality, subject to a constraint on total link capacity [START_REF] Fernandes | An adaptive-predictive architecture for video streaming servers[END_REF]. Equation ( 8) ensures that a receiver peer does not request a chunk j from more than one neighbor. That means a chunk is not requested more than once. Usually, each chunk is requested from a single neighbor, unless it is not available in the neighborhood. In this case it can't be requested.

This optimization problem can be naturally transformed into an Assignment Problem (AP) [START_REF] Pentico | Assignment problems: A golden anniversary survey[END_REF] where a set of missed chunks b∈U @ in peer i are to be assigned to a set V @ of its neighbors. The assignment itself is captured with H @ , the cost function for this assignment is -Π @ , and the feasibility conditions of the problem are ( 7) and [START_REF] Hu | Mesh-based peer-to-peer layered video streaming with taxation[END_REF]. Therefore, in this case the set of chunks can be understood as a set of tasks which should be assigned to a set of agents (neighbors peers) while optimizing the overall cost, which refers to the priority sum of the chunks. In its original version, the AP involves assigning each task to a different agent, with each agent being assigned at most one task, i.e. one-to-one assignment. Since we want to assign one or more chunks to each neighbor, we will use an alternative formulation, the Generalized Assignment Problem (GAP) [START_REF] Nauss | Solving the generalized assignment problem : An optimizing and heuristic approach[END_REF], that considers one-to-many assignment (multiple tasks can be assigned to the same agent). We therefore model the scheduling problem in layered streaming as a GAP, scheduling m chunks to n nodes (m ≥ n). This can be represented by the assignment matrix shown in Figure 14.

Chunk Node 1 2 … m-1 m 1 Pi1 Pi2 … Pi(m-1) Pim 2 Pi1 Pi2 … Pi(m-1) Pim … … … … … … n-1 Pi1 Pi2 … Pi(m-1) Pim n Pi1 Pi2 … Pi(m-1) Pim Figure 14: Assignment matrix-GAP
The GAP is known to be NP-hard problem [START_REF] Nauss | Solving the generalized assignment problem : An optimizing and heuristic approach[END_REF]. In the following section, we propose a novel heuristic to approximate its solution, and use it to perform chunk scheduling in Pull-based P2P streaming systems.

Algorithm

In order to construct a solution for the scheduling problem in layered streaming, modeled as GAP, we

Peers' reliability consider an arbitrary algorithm (let say algorithm A) to provide solutions (approximate or otherwise) for small versions of the knapsack problem (e.g. the Harmony-search algorithm [START_REF] Geem | A new heuristic optimization algorithm: harmony search[END_REF]). As a first step, we reorganize the rows of the assignment matrix based on neighbors' reliability (Figure 14) in order to assign chunks to the more reliable nodes first. Then, we perform the recursive procedure shown below. Of course, j is initialized to 0 as part of the algorithm setup. In this algorithm, V @ denotes the list of peer i's neighbors.

Assignment_Matrix_Line_Processing

1. Run the Algorithm A on the row j with respect to the capacity X @ of node k and chunk size r. This will give the set of chunks from the most reliable peer that has not been considered yet, and which maximize aggregate priority. Let S j be this solution, i.e. set of selected chunks returned.

if S < |V @ | (Termination condition)

j = j + 1. (Increment the indicator variable j, so that recursive calls to this function will consider the next row of A).

-Perform Assignment_Matrix_Line_Processing(j) and let ′ be the returned The availability of high speed computing allows processing the huge dataset for ARIMA to build a statistical model [START_REF] Hyndman | Minimum Sample Size Requirements for Seasonal Forecasting Models[END_REF], however, in this work we only consider the traffic samples for last smoothing window thus reducing the overhead of processing large amount of data. The ARIMA model is lightweight in memory and calculation cost and even used in sensor devices. The model buildup process may take relatively high memory and computational overhead, but the process is done by the receiver peer, which usually has high computational and storage capability [START_REF] Yeow | Energy efficient multiple target tracking in wireless sensor networks[END_REF].

In addition, our scheduling algorithm is based on a powerful knapsack algorithm, mainly the Harmony search algorithm. The results obtained using the HS algorithm may yield better solutions than those obtained using current algorithms [START_REF] Lee | A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice[END_REF], such as conventional mathematical optimization algorithms or genetic algorithm based approaches. The study performed in [START_REF] Lee | A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice[END_REF] suggests that the HS algorithm is potentially a powerful search and optimization technique for solving complex engineering optimization problems.

Finally, the amount of data processed in each scheduling period is very low. Indeed, the exchanging window size is very low, and the maximum number of neighbors considered in the simulation is not more than 30 neighbors, consequently the scheduling matrix size is small, and can be proceeded in very short time.

V. PERFORMANCE EVALUATION

In this section, we present the performance evaluation of our proposed playout smoothing mechanism for layered streaming (referred as SmoSched in the simulations). We first need to define the relevant metrics that reflect the key features of perceived video quality and the effective utilization of the available network capacity.

We focus mainly on two important points: first, we evaluate the performance of smoothness for our proposed mechanism, mainly in terms of layers changes and stalling events. Secondly, we evaluate the throughput of the system in terms of bandwidth utilization, useless chunks and delivery ratio.

A. Metrics

We consider the following metrics for the performance evaluation of our proposed mechanism.

Number of layer changes during video playback:

We measure the average number of changes in the quality level during the video playback.

Stalling Events: We are interested in the average number and duration of stalling events that occur during video playback due to the unavailability of the content. The shorter the stalling event, the better is the session quality.

Bandwidth utilization:

The effective utilization of the available bandwidth is an important consideration in P2P streaming. It measures the effective bandwidth used over the total available bandwidth in the network.

Useless chunks ratio:

It represent the number of chunks that arrive at each peer after their playback deadline over the total number of encoded chunks.

Delivery ratio at layer l:

It is defined as the average delivery ratio at layer l among all the peers that can play layer l. A chunk of layer l is considered as properly received if and only if all the related chunks of lowers layers to l are already received before their playback deadline.

B. Evaluation

Here we present our simulative evaluation for the proposed mechanism. The goal of this study is to observe the behavior of the metrics discussed. To effectively evaluate the performance of each component and compare it with different existing techniques, we perform the evaluation into two steps.

a) Scenario 1

In this scenario, we evaluate the metrics which had considerable importance in observing the behavior of smooth layered stream. This includes layer changes and stalling events. We compare the proposed mechanism with LayerP2P [START_REF] Xiao | On Optimal Scheduling for Layered Video Streaming in Heterogeneous Peer-to-Peer Networks[END_REF] discussed earlier. We used the BRITE universal topology generator [START_REF] Lee | A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice[END_REF] in the top-down hierarchical mode to map the physical network. The network topology consists of autonomous system (AS) and fixed number of routers. All AS are assumed to be in the Transit-Stub manner. Each topology consists of 8 autonomous systems each of which has 625 routers. This gives us about 20000 links in the topology. The delay on inter-transit domains and intra-transit domains are assumed to be 90 ms and 40 ms respectively, while delay on stub-transit is assumed to be 30 ms and intrastub transit links are randomly chosen between 5ms and 30ms.The incoming bandwidth of peers varies between 512 kbps to 2Mbps and is uniformly distributed throughout the network. The video is composed of 4 layers streamed at 1Mbps. We introduced sudden bandwidth change in the network by varying peer's capacity. This allows us to observe the effectiveness of smoothing mechanism.

Results and Discussion

Figure 16 shows the number of layer changes at different intervals for both mechanisms in an overlay composed of 300 peers. The objective was to minimize the number of layer changes that occurs due to changing network condition. The simulations are performed for different values of : while keeping into consideration bandwidth constraint B < $ . The interval on x-axis represents the time after which the bandwidth change occurs. It is observed that layer changes decreases by increasing the interval. Thus, it is found that bandwidth change has an obvious effect on the variation of the quality. Our proposed mechanism has very fewer layer changes due to the smoothing mechanism which adjusts the quality level for each smoothing window. As a result, the frequent changes in the quality level are minimized. Comparatively, LayerP2P system has higher number of quality changes due to the absence of an efficient smoothing mechanism. Figure 17 shows the comparison for useless layer ratio at different network size configurations. The higher layers which are selected and are not decoded due to the sudden decrease in bandwidth results in useless layers. Our proposed mechanism ensures the moderate selection of higher layer when a bandwidth increase occurs. Instead of allocating all the available bandwidth for acquiring maximum quality, it focuses on allocating the available bandwidth for the prefetching buffer. The moderate layer selection allows the scheduling mechanism to acquire the chunks of selected layer without violating the bandwidth constraint. As a result the selected layers are effectively decoded. The LayerP2P mechanism has higher useless layer ratio because there is aggressive selection of layers without taking into consideration the bandwidth constraint.

Figure 18 shows the average number of stalling events for both mechanisms. The stalling of video stream occurs due to the unavailability of selected layer chunks at that particular time period. The maximum number of stalling event in our case was not more than 6. However, there is a huge variation of stalling events in case of LayerP2P. Moreover the average duration of stalling event is lower in our proposed mechanism as shown in Figure 19. In order to evaluate the other smoothing strategies discussed earlier, namely amplitude reduction and frequency reduction, we consider a video stream composed of 8 layers (each layer is streamed at 100 kbps) under bandwidth variation (from 100 kbps to 900 kbps). The duration of the video is 400 seconds and the smoothing window size is 15 seconds. amplitude reduction algorithm on the row stream. In this case we note that the fluctuation of the quality is drastically reduced, and the user can enjoy a relative stable video quality comparing to row stream.

Indeed, this figure shows that the quality level change does not exceed 1 level in most cases. However, they could be a fluctuation of the quality within a short time period (from second 100 to 150 for example).

In Figure 24, we apply the frequency reduction algorithm on the same row stream. We note that the quality level is stable at least for a smoothing window, however we note some big jump in the quality level in some cases (jump of 2 layers from 170s to 180s for example). This is why we have proposed a hybrid smoothing solution which combines the benefits of the amplitude reduction and the frequency reduction algorithms.

b) Scenario 2

In this scenario, we evaluate the efficient delivery of the content considering the availability of the content among the neighbors and their corresponding bandwidth capacity. For that purpose, we focus on the different metrics including bandwidth utilization, useless chunks ratio and delivery ratio at different layers.

We perform extensive simulations using an overlay in which each peer has varying number of neighbors. We compare the performance of our algorithm with three classic scheduling methods described earlier, namely Random strategy (RND), Local Rarest First (LRF) and Round Robin (RR). We consider three categories of peers: 40% of users with 512Kbps, 30% with 1Mbps and 30% with 2Mbps, and for all users, the upload bandwidth capacity is half of the download bandwidth. We set the emergency priority defined in (5) as = > (A @ -B @ * = 10 ^_` a b `c

and we set the layer priority as = ? ( * = 10 (? ? b ) in order to ensure that the lower layers have much larger priority than the upper layers. For four methods, we adopt the conservative approach (Figure described in section IV. That's why we set the parameter θ to a very low value θ =10 -L .

Results and Discussion

In Figure 25, we study the performance of our mechanism in terms of bandwidth utilization and we examine the effect of the neighbor density. It is observed that our proposed mechanism outperforms the three other scheduling schemes and ensures more than 90% of bandwidth utilization, while the LRF scheme allows the maximum bandwidth utilization of 88%. The RND method shows the worst result (up to 71%). On the other hand, we note that the bandwidth utilization for all the schemes increases with the increase in the number of neighbors (for maximum 15 neighbors). This is due to the increase of the chunks availability in the neighborhood. The stable behavior is observed when the number of neighbors for a peer is greater than 15. We conclude that, for the considered overlay, the average of 15 neighbors per peer is enough to ensure the chunks availability. Moreover, we are interested on the impact of the streaming rate on the bandwidth utilization. The results are presented in Figure 26. We note that the general trend is the decreases in bandwidth utilization with the increasing streaming rate. This can be explained by the fact that when the streaming rate is high, a missed chunk has less chance to be rescheduled before its playback deadline. Nevertheless, our proposed mechanism outperform the three others mechanisms and allows a gain up to 25%. This is due to the fact that our mechanism tries to fully take advantage of the available bandwidth in the neighbor, using the assignment mechanism.

In Figure 27 and Figure 28, we evaluate the useless chunks ratio according to the neighbor's density and the streaming rate respectively. It is observed in Figure 27 that the useless chunks ratio decreases with the increasing number of neighbors. This decrease of useless chunk ratio is due to the higher probability of getting the requested chunks from the large pool of neighboring peers. Moreover, our mechanism tries to find the good tradeoff between the chunks availability in order to request the right chunk from the right neighbor. That's why the useless chunks ratio is low in proposed mechanism compared to the others systems.

In Figure 28, we evaluate the useless chunks ratio with the varying streaming rate. It is found that the useless chunks increase with the increase of the streaming rate. However, the proposed mechanism still outperforms the existing systems. Figure 29 describes the delivery ratio at each layer. We encode the video into 12 layers and set the rate of each layer at 100 Kbps. We note that our proposed mechanism is fairly good. In lower layers, delivery ratio is approximately 1 and in higher layers it is also above 0.9. The RR has much more better delivery ratio at lower layers than higher layers but, the delivery ratio for all layers is not as good as the proposed mechanism. We note that the LRF strategy has even higher delivery ratio than the RR strategy.

Finally, the random strategy has the poorest performance. As shown in Figure 29, our proposed mechanism outperforms other strategies with a gain of 10%-50% in most layers.

In order to show the importance of varying number of layers, we encode the video into 6 layers. In Figure 30, we note that the delivery ratio of each layer is nearly similar to that in 12 layers encoding scenario. Our mechanism is still the best among all the three others methods. However, we note that the delivery ratio of all the methods is little higher than in the case of 12 layers. This is due to the fact that encoding the video into six layers allow peers to allocate all their bandwidth to lower layers, however in the second case, some bandwidth will be dedicated to the higher layers (higher than 6).

Figure 1 :

 1 Figure 1: Variation in quality level

Figure 1 (

 1 Figure 1(b), where smoothing focuses on reducing the number of quality changes from 4 in Figure 1(a) to

Figure 2 :

 2 Figure 2: Sliding window mechanism Figure 3: Buffer map structure

Figure 4 :Figure 5 :

 45 Figure 4: Example of the optimal chunk scheduling problem

Figure 7 :

 7 Figure 7: Workflow of proposed playout smoothing mechanism

  It contains a number of possibly useful chunks which can be prefetched in future for decoding the content.

Figure 8 :

 8 Figure 8: High level overview of sliding window at receiver peer As stated previously, the smoothing function operates over two disjoint time horizons: Initial startup (the initial quality smoothing function) and real-time adaptation (the runtime quality smoothing function).The startup function is invoked only once, and it is responsible for selection of appropriate layers in the beginning of the session. It is designed in such a way that each peer can determine the highest quality level it can achieve before starting to play the layered video stream. The purpose of this function is to initialize the quality smoothing function with important information regarding the user context. The important considerations for this determination are user preferences, terminal capabilities, link capacity and video decoder processing power. Using different types of user metadata, we can filter out those layers that are not compatible with user request. The provisioning of metadata is out of the scope of this paper and not considered in this work.

Figure - 9 :

 9 Figure -9: Illustration of Average run metrics

for the next smoothing window and = 1 ∀Figure 11 :

 111 Figure 11: Frequency reduction mechanism

Figure 13 :

 13 Figure 13: Scheduling strategies in case of layered streaming

Figure 15 :

 15 Figure 15: Assignment matrix line processing algorithm

Figure 16 :

 16 Figure 16: No. of Layer Changes Figure 17: Useless layer ratio

Figure 18 :

 18 Figure 18: Average duration of stalling events Figure 19: Average No. of stalling events

Figure 20 :

 20 Figure 20: Relative Received layer ratio

Figure 21 :Figure 23 :

 2123 Figure 21: bandwidth variation Figure 22: Row stream

Figure 25 :Figure 26 :

 2526 Figure 25: Bandwidth utilization Vs. Neighbor density

Figure 27 :Figure 28 :

 2728 Figure 27: Useless chunks ration Vs. Neighbor density

Figure 29 :

 29 Figure 29: Delivery ratio (12 layers) Figure 30: Delivery ratio (6 layers)

  t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10 t 11 Time

	Layers
	Previous Smoothing	Smoothing window
	window
	Playhead position	(a)
	Played chunk	Selected chunk

  t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 17 Time

	Layers
	Smoothing window	Smoothing window	Prefetching buffer
	(1)	(2)
	3
	2
	1
	0
		Playhead
		position

VI. CONCLUSION

In this paper, we propose a playout smoothing mechanism for layered streaming in P2P network that selects appropriate stream layers while minimizing the number of layer changes and achieve high delivery ratio. Firstly, we proposed the mechanism for amplitude and frequency reduction in layered streaming.

We then combine the benefits of both mechanisms in hybrid approach. The proposed mechanism first selects the appropriate layers and then schedules those layers to the appropriate neighbors thus effectively utilizing the available capacity of the network.

To study the effectiveness of the proposed mechanism, we performed the simulation and compared the proposed mechanism with different existing systems. We studied different metrics that are essential in determining the performance of our proposed playout smoothing mechanism. The results demonstrate the optimality and the effectiveness of the solution.

The main limitation of SmoSched is the amount of delay introduced by the frequency reduction component, in particular, the smoothing window size parameter. As future work, we plan to study techniques to achieve a trade-off between the smoothing quality and the liveness of the stream by acting on the smoothing window size.