Laureen Ribassin-Majed

Catherine Hill

Rachid Lounes

Efficacy of Vaccination against HPV infections to prevent cervical cancer in France

Keywords: Human papillomavirus, vaccine, cervical cancer, modelling Human papillomavirus (HPV) types 16 and 18 cause 70% of cervical cancers, and currently

two vaccines protecting against these types are available [START_REF] Schiffman | Human papillomavirus and cervical cancer[END_REF] . In a previous paper, we estimated the long-term effect of HPV vaccination on the risk of cervical cancer in the French population using mathematical modeling [START_REF] Ribassin-Majed | Efficacy of vaccination against HPV infections to prevent cervical cancer in France: present assessment and pathways to improve vaccination policies[END_REF] . Several vaccination scenarios were tested, including different vaccination coverage rates of females alone or in conjunction with males.

In the first scenario, which is based on the vaccination campaign initiated in France in 2007, 30% of females aged 14 to 19 years were vaccinated annually, resulting in a 60% cumulative vaccination coverage rate among 14 to 19 year old females 6 years after the beginning of the vaccination campaign. A catch-up program was also included with an annual vaccination rate of 10% among females aged 20 to 24 years.

Using this scenario, the model predicted an 83% reduction in cervical cancer incidence 50 years after vaccination initiation. The following scenarios were also considered: extending vaccination: (1) to males, (2) to females under 14; and scenarios with (3) vaccination among 14 to 24 year-old females (annual rate of 80%), (4) vaccination among 14 to 24 year-old females and males (annual rate of 80%). Greater reductions in cervical cancer incidence of 92% to 98% were predicted.

Since the publication of this paper, new vaccination coverage data have become available in France [START_REF] Fonteneau | Estimation of vaccination coverage in France through the Permanent Beneficiaries Sample (EGB): exemple of measles, hepatitis B and human paillomavirus vaccination[END_REF] . The aim of the present paper is to estimate the impact of HPV vaccination on cervical cancer incidence and mortality in France given the current vaccination coverage using the same method. This method was derived from the mathematical theory of epidemics developed by Kermack and McKendricks in 1927 [START_REF] Kermack | A Contribution to the Mathematical Theory of Epidemics[END_REF] . In recent decades, extensions based on dynamic models have been developed to assess HPV vaccination strategies [START_REF] Jiang | A critical review of cost-effectiveness analyses of vaccinating males against human papillomavirus[END_REF] . The mathematical model that we developed consists of a system of differential equations that simulate the spread of HPV infection and the progression to cervical cancer. This transmission dynamic model simulates the transitions from the three states: susceptible, infected and diseased [START_REF] Kermack | A Contribution to the Mathematical Theory of Epidemics[END_REF][START_REF] Brauer | Mathematical Epidemiology Lecture Notes in Mathematics[END_REF] , and takes into account heterosexual transmission of HPV 16/18. The model is stratified on vaccine status (vaccinated /not vaccinated), age (14 to 19 and 5-year age groups from 20 to 84), and sexual activity based on the number of sexual partners in the last 12 months (0, 1, 2-3 or 4+ partners). Vaccination coverage was measured by the annual rate of vaccination. For more details about the complete list of parameters, calibration details, and discussion of model structure, see Ribassin-Majed et al. [START_REF] Ribassin-Majed | Efficacy of vaccination against HPV infections to prevent cervical cancer in France: present assessment and pathways to improve vaccination policies[END_REF] .

The vaccination scenarios analyzed are presented in Table 1. The first scenario is based on the present vaccination coverage in France, which is restricted to females aged 14 to 19, with a cumulative vaccination coverage rate of 40%. In the second hypothetical scenario, males aged 14 to 19 are also vaccinated with the same 40% cumulative vaccination coverage rate. In scenarios 3 and 4, a coverage rate of 50% is assumed, respectively among females alone and among both males and females, with a 5% coverage catch-up program for individuals aged 20 to 24 years. In scenario 5, vaccination of females less than 14 years of age is considered with a coverage rate of 46%, which is based on the hepatitis B vaccination coverage rate observed in France. In our model, individuals who enter the model at age 14 or younger are assumed to not be sexually active. Scenario 5 assumes that 46% of females entering the study are already protected by the vaccine and cannot be infected. The predictions at 20 and 50 years following vaccination initiation are studied to evaluate the theoretical impact of vaccine coverage on the reduction of cervical cancer incidence causally associated with HPV 16/18. When vaccination against infection is available, the spread of the epidemic depends on the vaccination coverage, and there is a threshold coverage beyond which the epidemic dies out.

We have shown previously that a time lapse of 100 years is sufficient to observe the equilibrium of the model [START_REF] Ribassin-Majed | Deterministic modelling for transmission of Human Papillomavirus 6/11: impact of vaccination[END_REF] . Thus, we present also the predictions at 100 years following vaccination initiation.

Results

Our model predicts a 48% reduction in cervical cancer incidence and a 27% reduction in cervical cancer mortality 50 years following vaccination initiation on the basis of the current vaccination coverage rate (Table 1). These results are based on the hypothesis of constant vaccination coverage over a period of 50 years. Given that not all women with cervical cancer die from the disease and that the effect of vaccination on mortality is generally observed later than the effect on incidence, the impact of vaccination on cervical cancer mortality is much less pronounced compared to that on cervical cancer incidence.

Vaccinating males with the same coverage rate as that of females (scenario 2) would reduce the incidence of cervical cancer after 50 years by an additional 14% and reduce cervical cancer mortality by an additional 7%, from a reduction of 27% to a reduction of 34%.

The analysis of scenarios 3 and 4 showed a substantially greater reduction in cervical cancer incidence compared to scenarios 1 and 2. If vaccinations are restricted to only females (scenario 3), a 65% reduction in cervical cancer incidence is expected 50 years after initiation of vaccination, and the additional vaccination of males (scenario 4) leads to a 78% reduction in cervical cancer incidence after 50 years.

The reduction in cervical cancer incidence estimated by scenario 5 is greater than the reduction estimated by scenario 1, with a 75% reduction in cervical cancer incidence and a 46% reduction in cervical cancer mortality. These reductions in incidence and mortality are similar to those obtained by scenario 4, where a high vaccination coverage rate is achieved in both sexes.

In Table 1, reductions in cervical cancer incidence predicted 100 years after the launch of vaccination are not equal to 100%. The vaccination coverage proposed by scenarios 1 to 3 is not sufficient to extinguish the epidemic. In the last scenario, vaccination in both genders leads to a reduction of cervical cancer incidence of 97%, which is close to the disease-free equilibrium. If more than half of males and females aged 14 to 19 years were vaccinated against HPV (scenario 4), cervical cancer cases caused by HPV 16/18 would become very rare.

Discussion

The incidence of cervical cancer causally associated with HPV 16/18 will be reduced by 48% after 50 years if the vaccination coverage rate remains around 40% and continues to be restricted to females. This is less than our previous estimation of an 83% reduction 2 , because the observed cumulative vaccination coverage rate of 40% among females aged 14 to 19 is much less than the 60% hypothesized in our previous analysis. These findings have important implications for public health and could serve to inform HPV vaccination initiatives.

Targeting younger females could lead to further reductions in cervical cancer incidence after 50 years, as shown by our analysis of vaccinating females less than 14 years of age (scenario 5). In France, the target age for HPV vaccination was recently lowered from 14 years to 11 years of age. Compliance has been shown to be higher among younger girls; thus, this new schedule could lead to increased vaccination coverage in the future. In France, vaccination against hepatitis B is proposed to 11 year old children, and the Health Authority has reported a vaccination coverage rate of 46% 3 .

In some countries, school-based programs for HPV vaccination have achieved higher vaccination coverage. In Australia, coverage of 80% has been reached among females and a large reduction in the incidence of genital warts has already been observed (the quadrivalent vaccine used also protects against genital warts) 8 . However, the impact of vaccination on cervical cancer incidence will be observed in several decades, given the long time lag between HPV infection and cervical cancer.

New findings also suggest that HPV vaccination with two doses of vaccine instead of the recommended three doses is sufficient to ensure protection [START_REF] Romanowski | Immunogenicity and safety of the HPV-16/18 AS04-adjuvanted vaccine administered as a 2-dose schedule compared with the licensed 3-dose schedule: results from a randomized study[END_REF] . A reduction in the number of required doses would improve compliance with the vaccination schedule. Expanding the vaccination to males would also significantly improve the reduction in cervical cancer incidence and therefore in mortality.

Table 1 :

 1 Human Papillomavirus Vaccination scenarios and consequences on HPV 16 and/or HPV 18 associated cervical cancer incidence and mortality in France Estimated, used as input for the dynamic modeling. ‡ Proportion of individuals in the age group who received three vaccine doses. * Compared to no vaccination. CH and RL declared no conflict of interest. LM has served as occasional consultant for Sanofi Pasteur MSD, no other relationships or activities that could appear to have influenced the submitted work. Ethical approval: None required.

			Sex of vaccinated population (scenario number)
		Female	Female & Male	Female	Female & Male	Female
		(1)	(2)	(3)	(4)	(5)
	Age of vaccinated population in years		Annual Vaccine coverage †
	<14	0%	0%	0%	0%	46%
	14 to 19	11%	11%	17%	17%	11%
	20 to 24	0%	0%	2.2%	2.2%	0%
			Cumulative Vaccine coverage ‡
	<14	0%	0%	0%	0%	46%
	14 to 19	40%	40%	50%	50%	40%
	20 to 24	0%	0%	5%	5%	0%
	Number of years after		Reduction in cervical cancer incidence*
	vaccination initiation
	20	14%	17%	21%	25%	24%
	50	48%	62%	65%	78%	75%
	100	66%	88%	83%	97%	91%
			Reduction in cervical cancer mortality*
	20	1%	2%	3%	4%	3%
	50	27%	34%	38%	49%	46%
	100	44%	66%	61%	83%	74%
	† Funding: None
	Competing interests:

Acknowledgements: the authors would like to thanks Benoit Bobillot for his comments and Nita-Hanh Nguyen for her assistance.

Abstract for submission

Two vaccines against human papillomavirus (HPV) are available to prevent cervical cancer and anogenital cancers. Both vaccines protect against HPV types 16 and 18, which cause 70% of cervical cancers. In a previous paper, we had estimated the efficacy of vaccination against HPV 16/18 infections to prevent cervical cancer in the French population, using modeling with a dynamic model that simulates the transitions from the three states: susceptible, infected, and diseased.

The aim of this short paper is to update our estimation of the impact of HPV vaccination on cervical cancer incidence and mortality in France based on current vaccination coverage data.

Several vaccination scenarios are evaluated: the current vaccination coverage, hypothetical scenarios including vaccination of males, and/or different target age groups among females.

The incidence of cervical cancer due to HPV 16/18 would be halved after 50 years if the vaccine coverage remains around 40% and remains restricted to females 14 to 19 years old. A larger reduction in cervical cancer incidence is predicted by scenarios including vaccination of males or vaccinating females before age 14.


Abbas Bradai
email: bradai@labri.fr

Toufik Ahmed

Raouf Boutaba
email: rboutaba@uwaterloo.car5ahmed@uwaterloo.ca

Reaz Ahmed

Efficient Content Delivery Scheme for Layered Video Streaming in Large-Scale Networks

Keywords: Content distribution, bandwidth allocation, scheduling, P2P, Layered video, QoS 1

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Besides, using Peer-to-Peer overlay has become more and more popular approach for streaming video content over the Internet due to its high scalability and facility of deployment. In P2P streaming, peers actively contribute their resources (mainly upload bandwidth) by forwarding their available content to their connected peers. Since the cumulative available resources in this approach grow with the user population, this approach can scale with the number of joining peers in the session. Thus, streaming a layered video over P2P architecture is promising approach for scalable video delivery to a large number of heterogeneous receivers [START_REF] Guo | Peer-to-peer live video distribution under heterogeneous bandwidth constraints[END_REF][3] [START_REF] Ramzan | Peer-to-peer streaming of scalable video in future internet applications[END_REF]. An example of such architecture is provided in Figure 1. In this example the video source streams a layered video composed of three layers. The peers subscribe to number of layers depending on their capacities and each receiver peer becomes in its turn sender peer by serving one or many layers. In P2P video streaming systems, the content retrieval mechanism allows a user to receive streaming data blocks (chunks) from other peers using the constructed overlay. This mechanism plays a leading role in the video streaming process and its efficiency influences the global performance.

Efficient chunks scheduling and appropriate bandwidth allocation are the two significant challenges of the content retrieval mechanism for real-time P2P streaming systems. The two components cannot be dissociated each from the other. Indeed, a good exploitation of the sender peers' bandwidth cannot be reached without optimized scheduling scheme. Reciprocally, an efficient scheduling algorithm cannot achieve a good throughput without appropriate sender peers' bandwidth allocation mechanism.

While considering the dynamicity of peers in terms of joining/leaving the network, the heterogeneity of peers and their need for bandwidth, an efficient and dynamic mechanism for bandwidth allocation is required to ensure the timely availability of the streaming content and acceptable quality level for peers while fully taking advantage of the overall bandwidth in the network.

In the context of pull-based layered streaming over P2P architecture, a peer commonly requests video layers from different upstream peers, and each upstream peer shares its upload bandwidth among different downstream peers serving different layers. Consequently, resolving bandwidth conflicts among peers in order to maximize the benefits of both upstream and downstream peers is a very challenging problem, because of the layers importance, their dependencies and the peers' priorities.

On the other hand, the scheduling task is complicated in the context of layered video streaming since chunks received after their playback deadline are not played and considered as useless chunks. In addition, chunks of higher layers received without their corresponding chunks from higher layers are not played also and considered as useless too.

Moreover, selfishness of peers in P2P networks is inevitable [START_REF] Park | A Game Theoretic Analysis of Incentives in Content Production and Sharing over Peer-to-Peer Networks[END_REF]. Therefore, a key research question to consider when designing streaming system in P2P architecture is: "How to exploit and manage the selfishness of peers in order to reduce the global streaming cost while satisfying the peers quality level requirements and priorities?"

Most related works considered one or two of the three components of the content delivery mechanism of the P2P layered streaming systems: bandwidth allocation, the chunks scheduling or the incentives. But no one considered the three issues all together, which is particularly challenging for efficient P2P streaming. Hence, the main challenge in this work is how to allocate the upstream bandwidth among its downstream peers (see Figure 2) while fully taking advantage of the available bandwidth in the network and handling the peers selfishness to ensure the better video quality for all peers.

In our previous work [START_REF] Bradai | On the Optimal Scheduling in Pull-based Real-Time P2P Streaming Systems: Layered and Non-Layered Streaming[END_REF], we presented an efficient chunks scheduling mechanism for P2P layered streaming systems. In this work, we mainly focus on the bandwidth allocation and the incentive mechanisms.

CONTRIBUTIONS

Recently there have been significant research efforts on designing P2P architectures by addressing the selfishness of peers. They can be categorized into two main approaches: "non-strategic behavior approach" such as [START_REF] Ma | A Game Theoretic approach to Provide Incentive and Service Differentiation in P2P Networks in Proc[END_REF][8] [START_REF] Cui | Optimal Resource Allocation in Overlay Multicast[END_REF] and "strategic behavior approach" such as [10][11]. In the former, each peer is considered as a potential game player aiming at maximizing its utility regardless of the behavior of other peers, while in the later each peer aims at maximizing its utility taking into consideration the actions of the other peers. In this paper, we propose a novel strategic and incentive model for efficient bandwidth allocation in P2P layered streaming networks.

Our main contributions in this paper are as follows:

1) Auction game model for bandwidth allocation in P2P layered streaming is proposed. The players in this game are the upstream peer which sell its upload bandwidth and on the hand the downstream peers which bids for. The proposed model is content aware and an auction game is set up for each layer. 2) Water filling algorithm based downstream peer bidding strategy is proposed. It aims to request the stream from the best links in terms of QoS metrics such as packet loss ratio and end to end delay. 3) A theoretical study of the proposed mechanism is provided and the Nash equilibrium of the system is proved. 4) Extensive simulations are conducted to show the performance enhancement of our mechanism using SVC video sequences and real P2P streaming system traces.

This paper extends our previous work [START_REF] Bradai | Differentiated Bandwidth Allocation in P2P Layered Streaming[END_REF] in many ways. It provides a more detailed description of the problem at hand and our solution approach including a mathematical analysis. In this regard, we provide a detailed proof of Nash equilibrium of our system. It also presents a new incentive mechanism to motivate peers to share their bandwidth. Moreover, new extensive simulations are performed to evaluate the effectiveness of our proposal under different network and streaming conditions, comparing with state of the art and other proposed strategies, using real world streaming systems traces.

PAPER ORGANIZATION

The rest of the paper is organized as follows. Section 2 introduces the background and discusses related work. Section 3 presents the system model for layered P2P streaming and problem formulation. Section 4 describes our proposed bandwidth allocation and discusses its Nash equilibrium. Section 5 presents briefly the scheduling mechanism. Section 6 presents our comparative evaluations and results. Finally, section 7 concludes this paper.

RELATED WORK

In the literature, content delivery mechanisms in P2P streaming [START_REF] Karunakar | Scalable video delivery over peer-to-peer network[END_REF] systems can be classified to three main A number of studies investigated different bandwidth allocation strategies and their impact on network performance and on end users satisfaction.

Authors in [START_REF] Bradai | Differentiated Bandwidth Allocation in P2P Layered Streaming[END_REF][11] [START_REF] Manzillo | CLOSER: A Collaborative Locality-Aware Overlay SERvice[END_REF] studied the impact of peers' upload bandwidth and established conditions for universal streaming for churnless systems. Furthermore, measurement studies and implementations [16][17] confirmed that bandwidth has a big impact on streaming quality for P2P streaming systems. Authors in [START_REF] Li | Inside the new Coolstreaming: principles, measurements and performance implications[END_REF] studied the Coolstreaming system by exposing its design rationale. They showed that there is a highly distorted resource distribution in such systems and the performance is mostly affected by the system dynamics.

Recently, researchers have studied bandwidth allocation for improving streaming quality in more challenging P2P networks such as multi-overlay, multi-sources and multi-swarm P2P streaming systems. Wu et al. [START_REF] Wu | Dynamic Bandwidth Auctions in Multi-overlay P2P streaming with Network Coding[END_REF] studied the bandwidth contest among coexisting overlays and proposed an auction-based solution. Liang and Liu [START_REF] Liang | Optimal Resource Allocation in Multi-Source Multi-Swarm P2P Video Conferencing Swarms[END_REF] studied optimal bandwidth sharing in multiple video conferencing swarms systems. They dynamically share a pool of helpers between swarms to address the intra and inter-swarms bandwidth shortage. However, none of these works have taken into consideration the properties of layered video streaming, and its potential benefits for providing personalized and customized video quality while coping with the bandwidth fluctuation problem.

For chunks scheduling, many valuable mechanisms have been proposed [START_REF] Zhou | Optimal Scheduling for Multiple Description Video Streams in Wireless Multihop Networks[END_REF]- [23][24]. 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] Lee | Reliability Analysis of a Multiview Multi-Description Video Streaming System[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 data-driven 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] 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. Zhang et al. [START_REF] Zhang | Time-Stamped Equal Size Segmentation and Chunk Scheduling Algorithms for SVC Based P2P Streaming Systems[END_REF] propose SVC content segmentation algorithm to overcome the problem of equal playback length segmentation. The proposed mechanism splits each layer into chunks with equal size and tags each chunk with a time-stamp according to its playback deadline. Based on these time stamps, they propose a scheduling algorithm and organize the buffer into two stages: Elementary Layers and Excess Layers in order to adapt to the dynamic network conditions. However, authors do not explain how the upload peer's bandwidth is allocated.

To handle the free riding phenomenon [START_REF] Ma | Incentive and service differentiation in P2P networks: a game theoretic approach[END_REF] in P2P networks, two categories of incentive mechanisms have been considered in the state of the art: rating and monetary payment [START_REF] Park | Pricing and incentives in peer-to-peer networks[END_REF]. In the rating category, each peer is rated regarding its upload history or downloads actions. Based on that, the supplying peer decides the amount of allocated bandwidth for the requester peer [START_REF] Habib | Incentive mechanism for peer-to-peer media streaming[END_REF]- [START_REF] Zhao | A mathematical framework for analyzing adaptive incentive protocols in P2P networks[END_REF]. This approach presents mainly two drawbacks. Firstly, some malicious peers could have more allocated bandwidth from the network by providing false ratings for other peers [START_REF] Rückert | Quality adaptation in P2P video streaming based on objective QoE metrics[END_REF]. Secondly, it penalizes peers of low bandwidth capacity in the network [START_REF] Park | Pricing and incentives in peer-to-peer networks[END_REF]. In the monetary payment category [START_REF] Qiu | Modeling and performance analysis of bitTorrent-like peer-to-peer networks[END_REF], the peers pay for their download and are rewarded for their upload. A virtual currency or even real currency could be used for payment. In this work, we adopt a credit-based incentive mechanism to incite peers collaboration. It is a virtual currency payment incentive mechanism, in which the peers are paid for sharing their upload bandwidth. In their tour, they use the earned credit to buy their need in download bandwidth.

To our knowledge, the most closely related work to ours is the one of Wu et al. in [START_REF] Wu | Dynamic Bandwidth Auctions in Multi-overlay P2P streaming with Network Coding[END_REF]. They coordinate multiple streams as an auction game, where each peer participates in media distribution by bidding for and selling bandwidth. Their strategy is not appropriate for scalable streams as each stream is considered as an isolated stream without any relationship with other streams. We argue that there exists inherent content priority among layers. In addition, in WU approach the receiver side is not considered, to request content a simple scheduling algorithm is considered. Moreover, they only consider a scenario where the total upload bandwidth in the network is always sufficient to support all peers' requirements in all the overlays.

We note that our work does not focus particularly on the incentive mechanism, but on a combined design of bandwidth allocation, chunk scheduling with incentives in P2P layered streaming. In the following section we present the model of our system and we detail the problem of bandwidth allocation and scheduling for P2P layered streaming.

SYSTEM MODEL AND PROBLEM STATEMENT

In this section, we first present an overview of the proposed delivery system model and considered assumptions, and then formulate the problem we would like to solve of layered streaming in P2P layered streaming systems, in its different aspects: bandwidth allocation, chunks scheduling and incentives.

SYSTEM MODEL AND NOTATION

Scalable video codecs, such as SVC [START_REF] Cheng-Hsin | Optimal Coding of Multilayer and Multiversion Video Streams[END_REF], allow a video to be encoded into a base layer and several enhancement layers. The scalability of SVC is three-dimensional: quality, spacial and temporal. The quality scalability determines the video SNR (Signal to Noise Ratio); the spatial scalability determines the resolution of video in terms of height and width; and the temporal scalability determines the frame rate of the video. In our model we assume that the layered stream is encoded into M layers at the source peer {l 0 , l 1 … l M-1 }, with l 0 representing the base layer and l 1 … l M-1 representing the enhancement layers such that l 1 is the first enhancement layer, l 2 the second enhancement layer, etc.

We assume that each video layer l i is distributed with a transmission rate of b i . Thus, each peer can subscribe to a particular video layer depending on its download capacity and other parameters such as its processing capability, preferences, etc. The decided quality should be dynamically adjusted to the available upload bandwidth in the receiver side. If the available upload bandwidth is not known a priori, the receiver peer should ask for the maximum quality. The chunks are then requested and delivered according to their priority in terms of layer importance and play back deadline. This will give the possibility to receive a suitable quality according to the available bandwidth. This issue was discussed in detail in our previous work [START_REF] Bradai | An efficient playout smoothing mechanism for layered streaming in P2P networks[END_REF]. [START_REF] Bradai | An efficient playout smoothing mechanism for layered streaming in P2P networks[END_REF] Of course, contextual information such as users' preferences and terminal capabilities can also be used to determine the requested quality level.

We consider an overlay network composed of n peers relayed by a set of application-layer links k i,j (link between downstream peer i and its upstream peer j). So, the topology of the overlay can be modeled as a directed weighted graph G= (S, L, K) where S denotes the set of upstream peers (called Seeders in some architecture), L the set of downstream peers (typically referred to as Lechers) and K the set of links.

To represent a practical network setting, we limit the upload and download capacity of any peer i by u i and di respectively. Therefore, each peer can only provide limited service for its downstream peers, and make a limited layer subscription as well.

For the reader's convenience, Table 1 summarizes the notations used throughout this paper. Bandwidth allocated to the downstream peer i by its upstream peer j , Bandwidth requested by the downstream peer peer i to its upstream peer j to acquire layer k , Unit price that the downstream peer i is willing to pay for the upstream peer j to acquire bandwidth for layer k Maximum layer available at peer i Peer i's upload bandwidth allocated to layer k

L j

Set of downstream peers connected to upstream peer j

S i

Set of upstream peers of the peer i T i Initial budget allocated to peer i Q j Quality level j, i.e, layers: l 0 , l 1 , …, l j

In the following sub sections, we present the bandwidth allocation problem and the chunks scheduling problem in the context of P2P layered streaming.

BANDWIDTH ALLOCATION PROBLEM STATEMENT

Through the following example we illustrate the problem of bandwidth allocation in P2P layered streaming. Suppose each upstream peer allocates its upload bandwidth fairly between its direct downstream peers. In Figure 3, the numbers on the arcs represent the distribution of the upstream upload bandwidth on their respective downstream peers by adopting this strategy. Peers 1, 2, 3 and 4 can get 100, 140, 90 and 40 kbps respectively. Suppose that the original stream is encoded into one base layer and one enhancement layer, with each layer rate at 50 kbps (i.e. b 0 =b 1 =…= b M = 50kbps). Clearly, downstream peers 1 and 2 can access the base layer and enhancement layer l 1 , while downstream peer 3 can get only the base layer and downstream peer 4 can't get any layer. In this case the unused bandwidth w is:

w = u + u + u -l * b + l * b + l * b + l * b + l * b = 120 Kbps
An optimized allocation strategy could be the one represented in Figure 4, where downstream peers 1, 2 and 3 can get layers l 0 and l 1 and peer 4 can get the base layer l 0 . The unexploited bandwidth in this case is 20kbps instead of the 120 kbps in the first strategy.

u A =100 u B =150 u C =120 d 1 =150 d 2 =150 d 3 =100 d 4 =100 l 0 +l 1 l 0 +l 1 l 0 ∅ ∅ ∅ ∅ A B C 1 2 4
u A =100 u B =150 u C =120 d 1 =150 d 2 =150 d 3 =100 d 4 =100
l 0 +l 1 l 0 +l 1 l 0 l 0 +l 1 l 1 , …, l j ), we seek the most optimal possible solution which allocates the upload bandwidth U in such a way that takes better advantage of the available bandwidth and maximizes the total system utility in terms of downstream peers' quality level satisfaction.

Taking better advantage of the available bandwidth means reducing the amount of unused data due to either over-allocating bandwidth to peers or receiving layers without their corresponding lower layers. The systemlevel utility optimization can be formulated as:

)*+ ,-$ % - %∈' --. / * 0 / /12 3 /1 4∈5 6 (1)
Subject to:

-$ % 7 7 ≤ $ % (for all i ∈ S) (2)
And Where 9 4 represents the maximum layer played by peer j, and $ % 7 represents the peer i upload bandwidth allocated to the layer k.

Equation ( 2) ensures that the upload bandwidth of the upstream peer i is not violated, and equation [START_REF] Liu | LayerP2P: using layered video chunks in P2P live streaming[END_REF] ensures that the download capacity of a peer j is not violated.

In pull-based P2P streaming systems, it is up to the receiver peer to request video data from the sender peer.

Hence, after that the upstream peers allocate its bandwidth, the downstream peer request the video chunks using a scheduling mechanism. The problem of chunk scheduling is briefly introduced in the next subsection. We note that the adopted scheduling mechanism was presented in our previous work [START_REF] Bradai | On the Optimal Scheduling in Pull-based Real-Time P2P Streaming Systems: Layered and Non-Layered Streaming[END_REF].

CHUNKS SCHEDULING PROBLEM STATEMENT AND BUFFER STRUCTURE

In pull-based P2P streaming systems, it is up to the downstream peer to request the video chunks, which depend on the links capacity allocated in the bandwidth allocation phase. 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 5) 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 5), 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

-. / * 0 / /12 3 /1 ≤ : 4 (3)
are re-requested if not received.

Figure 5: Sliding window mechanism

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 5 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.

In the following section we present our solution for efficient layered streaming over P2P networks. We detail the bandwidth allocation mechanism with incentives and we overview the chunkd scheduling mechanism presented in detail in our previous work [START_REF] Bradai | On the Optimal Scheduling in Pull-based Real-Time P2P Streaming Systems: Layered and Non-Layered Streaming[END_REF].

BANDWIDTH ALLOCATION MECHANISM

We propose a sender peer bandwidth allocation for mesh pull-based architectures. In this section, we develop the sender side bandwidth allocation strategy. The sender peer allocates its bandwidth periodically (long-term allocation), and it is up to the receiver peers to request the appropriate chunks. Figure 6 summarizes the relationship between the bandwidth allocation module and the chunks scheduling module.

The scheduling module aims to better request the chunks in timely and efficiently manner depending on the available bandwidth in the neighbors. The bandwidth is allocated by the sender peer using the bandwidth allocation module. The main goal of the bandwidth allocation module is to allocate the sender peers upload bandwidth in such a way that ensures a minimum quality level to all peers and higher quality if the residual bandwidth allows, while differentiating the service quality received by the peers based on their bandwidth contribution in the network. To do so, the allocation process is performed layer by layer, starting from the lower to the higher layers. Each sender peer tries first to ensure the base layer for all of its neighbors, and then, if bandwidth remains, allocates it for the higher layers.

Bandwidth allocation for a certain layer is modeled as a set of dynamic auctions organized by the upstream peers in order to give rise to competition for its upload bandwidth u j .

In this work we adopt the English auction [START_REF] Coppinger | DUTCH AND SEALED[END_REF], where the auctioneer opens the auction by announcing an initial price and then accepts progressively higher bids from interested buyers. The players in these auctions are the downstream peers. Indeed, each downstream peer, having an initial budget T i , submits bids to all its downstream peers in order to purchase bandwidth. Consequently, each downstream peer can participate in different independent parallel auctions A j . The upstream peers aim to maximize their profit, and allocate their upload bandwidth for the higher bidder downstream peer.

We note that the proposed bandwidth allocation mechanism is executed periodically in order to deal with the bandwidth fluctuation. In addition, the mechanism is triggered by an upstream peer in the case of new peer joining the system in order to allocate a bandwidth to the new arriving peer. Similarly, in the case of peer living the system (peers churn), the mechanism is called in order to re-allocate the bandwidth consumed by this peer to the remaining downstream peers. Thus, the proposed mechanism allows to regulate the bandwidth allocation and deal with the extreme situations, namely the flash crowd phenomena where peers join the system massively and suddenly, and leave it in the same manner.

In the following sub-sections, we detail the bandwidth allocation process. We start by giving an overview of the proposed mechanism then we detail the per-layer allocation process.

CREDIT-BASED INCENTIVE MECHANISM

To avoid selfishness or free-rider, we introduce a credit-based incentive mechanism. It is on the common sense that the peer using the bandwidth should be charged and the peer providing the bandwidth should be rewarded. Credit represents a kind of virtual currency that can only be used in P2P networks for payment. If the peer requests a video layer from the neighbor, it has to pay for it in credits. For example, when player j receives its bandwidth assignment ; %4 / from peer i, it pays an amount < %4 / x ; %4 / of credits to peer i.

correspondingly, the credits of peer i is increased with equivalent amount. In this way, the peer is motivated to share the bandwidth to earn credits. In the following sub-section we present the bandwidth allocation mechanism along with incentives.

BANDWIDTH ALLOCATION: A CONTENT-AWARE APPROACH

In order to guarantee a minimum quality level for all downstream peers and respect the layers dependency, every upstream peer should start by allocating bandwidth for the base layer, then for the enhancement layers in an ascending order. In our model, every upstream peer organizes an auction to distribute bandwidth needed for the base layer. Then, if there is still remaining bandwidth, it organizes another auction to sell bandwidth for the first enhancement layer, the second enhancement layer, and so on. In the receivers' side, the peers participate in auctions depending on the quality level they need. A peer requiring a quality level 2 will participate in a set of auctions organized by its upstream peers to distribute bandwidth for base layer (l 0 ), for the first enhancement layer (l 1 ) and for the second enhancement layer (l 2 ). We note that an upstream peer does not start allocating bandwidth for an upper layer, until there is no request for the current layer from their downstream peers (i.e., until the downstream peers' requests are satisfied or their budget is exhausted).

The auction game to distribute bandwidth for certain layer l i is illustrated in layer k and = %,4 7 be the unit price that the downstream peer is willing to pay for that bandwidth. The bid of the downstream peer i can be expressed by the tuple > %,4 7 = 0 %,4 7 , = %,4 7 .

In this section we modeled the bandwidth allocation problem in P2P layered streaming as a set of auction games, where items to sell are the upload bandwidths, and where the sellers are the upstream peers and the buyers are the downstream peers. We discuss in the following the allocation strategies of the upstream peers and the bidding strategies followed by the downstream peers.

Upstream peers' bandwidth allocation strategy

An upstream peer starts allocating bandwidth primarily to the lower layers then to the upper layers in ascending order. It executes the algorithm presented in Algorithm 1.

Algorithm 1 : Allocation strategy-global algorithm . 7 = .

While > 0 @+: ≤ Auction (. 7 )

$ % = $ % -$ % 7 . 7 = . 7A

End while

where $ % 7 represents the total bandwidth allocated for layer k to all downstream peers of peer i and . 2 % is the maximum layer available in peer i.

In the following, we detail the strategy of the upstream peer within the auction game to allocate bandwidth for a layer k.

In auction B 4 7 , organized by peer j to allocate bandwidth for layer k, the seller j aims to maximize its revenue by selling its bandwidth at the best price. Given the downstream peers' bids > %,4 7 = 0 %,4 7 , = %,4 7 , the upstream peer j aims to maximize:

)@; -0 %,4 7
%∈5 3 * = %,4 7 (4)
Subject to

-0 %,4 7 ≤ $ 4 %∈5 3 (5)
Where L j denotes the set of downstream peers connected to the upstream peer j.

In order to maximize its revenue, the upstream peer adopts the best offer auction strategy: it starts first by serving the downstream peer, willing to pay the highest price. Once it is served and if there is still remaining bandwidth, the downstream peer proposing the second highest price will be served and so on.

The allocation strategy of the bandwidth for a layer k is performed in many rounds as shown in Algorithm 2.

Algorithm 2 : Per layer bandwidth allocation strategy 1) Receive bids from downstream peers

2) Allocate bandwidth to the downstream peer willing to pay the highest price 3) While there is still remaining bandwidth serve the downstream peer willing to pay the next highest price 4) Notify the allocated bandwidth to all the downstream peers involved in the auction 5) Receive new bids from downstream peers (having sufficient budget) whose bandwidth request is not satisfied. Go to 2

Downstream peers' bidding strategy

A critical question is how much bandwidth a down-stream peer requests to each of its upstream peer 0 %,4 7 and at what price = %,4 7 . The ultimate goal of the downstream peer is to minimize the bidding cost and thereby the streaming cost. The bidding price can be mapped as in a real-world auction to the items' purchase prices which reflect the competition degree on these items. Indeed, we believe that requesting a stream from the less loaded upstream peers, allows to reduce the delay, since it reduces peer congestion by balancing the load over the concerned peers. In addition, load balancing in the streaming overlay allows to minimize the impact of peer churn.

The streaming cost can be modeled as the transport cost of the purchased items. In the context of P2P streaming, reducing the streaming cost is equivalent to receiving the stream over the best links, that is the links with lowest delay, lowest bit error rate, etc. As such, the goal of the downstream peer is to get bandwidth from less loaded upstream peers (lowest price) and through the best links (lowest streaming cost).

In our system, the downstream peer starts first by requesting bandwidth for the lower layers, and then incrementally for the enhancement layers, by joining the corresponding auctions organized by the upstream peers in this order. This strategy allows requesting primarily bandwidth for the lower layers over the best links and then the enhancement layers over the remaining links. Hence, lower layers have more chance to be received by the downstream peers, and consequently more chance to be decoded properly. In contrast, if the upper layers are those prioritized, the decoding of the stream becomes impossible if the corresponding lower layers are missing and the throughput of the system will degraded as a consequence.

Formally, in each auction organized by an upstream peer j to allocate bandwidth for layer k, the downstream peer aims to minimize the bidding cost. That means:

min -G0 %,4 7 * = %,4 7 H 4∈I J (6)
Subject to:

-0 %,4 7 ≥ 0 7 4∈I J

Where S i denotes the set of upstream peers of peer i. Condition (6) ensures that the downstream peer i gets the necessary bandwidth to play layer k.

In addition to the bidding cost, the downstream peer also aims at minimizing the streaming cost from each of its upstream peer j, denoted as L %,4 0 %,4 7 . Therefore, the bidding strategy of downstream peer i, to acquire bandwidth for layer k, can be seen as an optimization of the overall cost problem:

min -M0 %,4 7 * = %,4 7 + L %,4 G0 %,4 7 HN 4∈I J (8)
Subject to

-0 %,4 7 ≥ 0 7 4∈I J (9) 0 %,4 7 ≥ 0 (10)
In practice, we consider the streaming cost function L %,4 as a non-decreasing function depending on 0 %,4 7 , strictly convex and twice derivable.

In the following we present the bidding strategy of the peer to set the requested bandwidth (0 %, 4 7 ) and the bidding unit price (= %,4 7 ).

Peer's strategy to set the requested bandwidth (O

P,Q R )
Given the bid price = 4 7 in an auction organized by the upstream peer j to allocate bandwidth for layer k, the downstream peer i aims to optimize the overall cost by adjusting the requested bandwidth 0 %,4 7 from each downstream peer. Hence, the goal of the downstream peer is to minimize the global marginal cost M i defined as the change in total cost that arises when the requested quantity changes by one unit [START_REF] White | Effective Marginal Costing: Know Your Resource Needs[END_REF].

Let S % be the overall cost at the downstream peer i, i.e.,

S % = -M0 %,4 7 * = %,4 7 + L %,4 G0 %,4 7 HN 4∈I J (11)
The corresponding marginal cost is: Since the streaming cost function E i,j is strictly convex, the second derivative

T2 J TU J,3 V T WW X J,3 MU J,3 V N TU J,3 V is strictly positive.
Consequently, the marginal cost M i increases with the increase of the bandwidth request 0 %,4 7 .

To efficiently solve this optimization problem we adopt the water-filling algorithm [START_REF] Boyd | Convex Optimization[END_REF]. To set the bandwidth quantity (to request from an upstream peer j), the downstream peer iapplying the water-filling algorithmsets 0 %,4 7 to 0 for all Y ∈ Z % , then identifies the upstream peer Y having the lowest marginal cost 9 %,4 [ and increases its demand 0 %,4 [ 7 until the marginal cost becomes equal to the next highest marginal cost 9 %,4 \ , corresponding to the upstream peer j1 (Figure 8). The downstream peer i increases then fairly 0 %,4 [ 7 and 0 %,4 \ 7 until their corresponding marginal cost 9 %,4 [ and 9 %,4 \ meet the next highest marginal cost 9 %,4 ] corresponding to the upstream peer j2 (Figure 9), and so on. The downstream peer carries out this mechanism with all of its upstream peers until it obtains the bandwidth that it requests for layer k (0 7 ). After defining the bandwidth request strategy of the downstream peer, the next question is how the downstream peer sets the unit price that it will announce to the upstream peer j?

In the downstream strategy (4.2.2), we have seen that the upstream peer aims to maximize its benefits by selling its bandwidth at the higher price. The collected amount will constitute its budget _ % 7 to buy bandwidth from other peers.

When the downstream peer i joins the auction organized by an upstream peer j, first, it sets its price bid to one unit (i.e. = %,4

1). Using the water-filling algorithm described earlier, it computes the optimal quantity of bandwidth 0 %,4 7 to request from each upstream peer j, and submits bids accordingly. After the upstream peers allocate their upload bandwidth using the strategy described above, it proposes the bandwidth @ %,4 7 to the corresponding downstream peers. On receiving the proposed bandwidth, the downstream peer determines its behavior in the next round of auctions, using the following algorithm: b. Using the water-filling algorithm, decide the quantity of bandwidth 0 %,4 7 to request from j

3) Send new bids (0 %,4 7 , = %,4 7) to the upstream peer It is clear in this algorithm that the reference price p `a b assigned to the downstream peer allows to differentiate between the downstream peers according to their priorities.

CONVERGENCE TO NASH EQUILIBRIUM

Our mechanism for bandwidth allocation can be modeled as a non-cooperative game where the players are the downstream peers in the set L, the strategies are the bids (0 %,4 7 , = %, 4 7 ) and the cost function of a player i is the overall streaming and bidding cost C i . Formally, we consider the finite game Γ = < L, D, C> where:

-L denotes the set of players (downstream peers) -D denotes the set of strategies, i.e. D = (D 1 , D 2 … D i ), where D i = (> %, 7 , > %,c 7 …> %, 4 7 ) is the tuple of bids submitted by the player to its upstream peers.

-C denotes the set of costs: C = (c 1 , c 2 … c i ), where c i is the overall cost at player i as defined in [START_REF] Takahashi | Bandwidth Allocation by Using Generalized Vickrey Auction[END_REF].

Theorem

The formulated auction game for bandwidth allocation in layered P2Pstreaming leads to a Nash equilibrium.

Proof

A detailed proof the theorem is provided in the annex.

CHUNKS SCHEDULING MECHANISM

The main goal of the scheduling mechanism is to efficiently request the missing chunks in the receiver peer buffer. 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 links 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< X , is a function of how close a chunk is to its playback deadline; the second one, the layer priority < d , is a function of how many underlying layers are necessary to decode a particular chunk. Using these two functions, we can define our priority function < %4 as:

< %4 < X G_ % -e 4 % H f< 5 G. 4 H (13)
where _ % denotes the current time in the peer i, e 4 % 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, < X G_ % -e 4 % H evaluates < X at a time interval equal to the remaining time that chunk j has until its playback deadline at peer i, and < d G. 4 H evaluates < d at an integer proportional to the number of underlying layers needed to decode chunk j.

After defining the chunks priority function, we model the chunk scheduling in layered P2P streaming systems as assignment problem. Where a set of chunks are to be assigned to a set of neighbors. The main goal is to maximize the chunks priority sum. For that purpose we define the decision variable R ah b , a Boolean variable that indicates whether the peer i requests the chunk j from the neighbor k:

i %4 7 j
1 if peer * requests chunk Y from neighboor s, 0 otherwise.

We now present the core of our chunk scheduling heuristic. Using < %4 as defined in [START_REF] Karunakar | Scalable video delivery over peer-to-peer network[END_REF], 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 (14)
where M a denotes the set of chunks that peer i requires from the overlay, and N a 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 ≤ ∑ ∈ (15) 1 ≤ ∑ ∈ i N k k ij R (16)
Where w % 7 denotes the download capacity of the link between the receiving peer i and its neighbor k.

We proposed a solution of this optimization problem in [START_REF] Bradai | On the Optimal Scheduling in Pull-based Real-Time P2P Streaming Systems: Layered and Non-Layered Streaming[END_REF] based on the Hungarian algorithm [START_REF] Harold W Kuhn | The Hungarian method for the assignment problem[END_REF] to get the optimal solution.

PERFORMANCE EVALUATION

After presenting the different component of the video streaming system that we propose, namely the bandwidth allocation and the chunks scheduling mechanism. We present in this section the performance evaluation of our system through simulation using a real P2P streaming systems traces and real video. The simulations were performed using the Matlab-Simulink [START_REF]SIMULINK[END_REF].

SIMULATION SETUP

In this sub section we present the network topology, the overlay construction mechanism and the video parameters used in our simulations.

Network Topology

We used the BRITE universal topology generator [START_REF] Medina | BRITE: Universal Topology Generation from a User Perspective[END_REF] to provide a model for the physical network topology.

All autonomous systems 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 download bandwidth of peers varies from 256 kbps to 2 Mbps and is uniformly distributed throughout the network. We introduced sudden bandwidth changes in the network by varying the capacity of peers; this allowed us to observe the effectiveness of our proposed streaming system.

OVERLAY NETWORK CONSTRUCTION

In order to construct a randomly connected mesh-based overlay [START_REF] Magharei | Understanding mesh-based peer-to-peer streaming[END_REF], each peer contacts a centralized directory server (Tracker) for a list of the supplying peers, and randomly selects some of them to establish the neighbor relationship and then maintain a neighbor list. When a peer intends to leave, it sends a message to all its neighbors, notifying the cancelation of it from their neighbor lists.

We emulate peer dynamics based on traces collected from a real-world P2P live streaming system [START_REF] Liu | Substream trading: towards an open P2P live streaming system[END_REF].

When the number of peers rises between two consecutive time intervals, we schedule a corresponding number of peer join events during the interval; when the number of peers decreases, peer departure events are scheduled for a corresponding number of randomly selected peers. Upon arrival, each peer acquires a set of initial upstream peers. The node upload capacities are emulated using values from the traces. The distribution of the peers upload capacity and the portion of their contribution is provided in [START_REF] Liu | Substream trading: towards an open P2P live streaming system[END_REF].

Video parameters

We used in our simulation the standard test video sequence "Bus" at CIF resolution (352×288), 30 frames per second, at 500 kbps by using the SVC reference software (JSVM 8.8). We fixed a GOP structure of 32

Evaluation Metrics

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

-Average Peak Signal to Noise Ratio (PSNR), measured as follows: For each played video we measure the peer PSNR as the average of all layers PSNR, and then we compute the average peer PSNR;

-Upload bandwidth utilization: defined as the ratio of the requested bandwidth over the overall allocated upload bandwidth;

-Useless chunks ratio, defined as the ratio of the decoded chunks to the oval alla received chunks; and -Number of Rounds to reach the equilibrium

The chosen metrics reflect the key features of perceived video quality and the effective bandwidth allocation and utilization of the available network capacity.

We generate various network topologies of different sizes, different upstream peers' connectivity degrees (defined as the number of downstream peers connected to the same upstream peer), and different streaming rates.

We use the following function to measure the streaming cost:

L %,4 G0 %,4 7 H = 0 %,4 7 ; %,4 -0 %,4 7
Where x i,j is the available bandwidth between the downstream peer i and its upstream peer j. This function represents the ratio of the peer i requested bandwidth from peer j, to the residual free bandwidth of link m i,j . It expresses the utilization ratio of the link. Indeed, a link with low utilization ratio is considered as a good link since it presents low delay and low bit error rate, because of the low occupation of the intermediate routers'

queues. It is worth noting that we choose this streaming cost function as an example to perform our simulation. Any other function to evaluate the streaming cost of a link, satisfying the conditions of convexity and derivability mentioned in 4.2.2, can be used.

PROTOCOLS FOR COMPARISON

First, we compare the performance of our proposed mechanism with two pioneering streaming protocols, namely WU approach [START_REF] Wu | Dynamic Bandwidth Auctions in Multi-overlay P2P streaming with Network Coding[END_REF] and layerP2P streaming protocol [START_REF] Liu | LayerP2P: using layered video chunks in P2P live streaming[END_REF]. Then, we perform an in-depth evaluation of the performance of our mechanism in terms of the number of rounds to reach the equilibrium and the appropriate network configuration.

We note that LayerP2P adopt the downstream fair bandwidth allocation strategy, where the upload bandwidth is allocated fairly between the downstream peers. That means each upstream peer i splits its bandwidth fairly between all the downstream peers connected to it, i.e. Where : 4 denotes the bandwidth allocated to the downstream peer j and y % is the set of downstream peers of peer i. Furthermore, LayerP2P scheduling mechanism gives more importance to the base layer comparing to the enhancement layers.

Figure 10: Bandwidth allocation strategy in LayerP2P

RESULTS AND DISCUSSION

In order to objectively interpret the video quality results issued from our proposed system and the two others systems, we measure in addition to the videos PSNR, the corresponding utilized bandwidth as well as the ratio of useless chunks. Indeed, the bandwidth utilization metric shows the effectiveness of the bandwidth allocation mechanism in terms of the amount of bandwidth allocated to each peer, while the useless chunks ratio measure the utility of the allocated bandwidth.

Impact of Neighbors density

Firstly, we study the impact of neighbor density on the received video quality. We fixed the streaming rate to 1.2 Mbps, and the overlay size to 1000 peers.

Figure 11 represents the variation of the PSNR while increasing the neighbors' density defined as the average number of peer neighbors.

The general trend for the three approaches is the increase of video PSNR with the increase of the neighbors' density. This is because low neighbor density leads to low probability to get the appropriate chunks, mostly for the upper layers that are infrequent in the network due to the layered stream nature. Conversely, increasing the neighbor density leads to increased chance to get the appropriate chunks, and consequently increased the video PSNR.

We note that WU approach performs the worst PSNR among the three approaches. This is due to the fact it does not take into consideration the layers importance and dependency of layers in the layered stream.

Indeed, in WU approach an overlay is constructed each layer. Each layer is requested from an overlay and no coordination is performed between the different overlays. Consequently the amount of decodable received chunks is more and more small.

LayerP2P performs higher PSNR degree since more importance is given to lowers layers in the scheduling process. But, the static downstream peers' fair approach adopted by LayerP2P may allocate bandwidth to peers that do not need it (peers with low capacities). Consequently, a part of the bandwidth is wasted. In our system the bandwidth allocation is performed taking into consideration the downstream peers' needs in terms of layers. In addition, the upload bandwidth is dynamically allocated, starting with the most important layers (lower layers), then the less important ones (higher layers). Furthermore, our scheduling mechanism requests the lower layers chunks first, and more importance is given to urgent chunks among them. All these justify the higher PSNR values of our system comparing with the two other approaches Figure 12 shows that the WU approach outperforms LayerP2P in terms of bandwidth utilization. We explain this by the fact that parallel auction games are set-up in WU approach to acquire the bandwidth for the different layers, while is LayerP2P, the bandwidth is fairly allocated to peers which may not necessary use it.

This is why LayerP2P has the worst bandwidth utilization ratio.

However, when investigating the useless chunks ratio (see Figure 13), we can see clearly that the useless chunks portion is more important in WU approach since no coordination is performed when requesting bandwidth for different layers. Consequently, even the WU make use of more allocated bandwidth, but the useless requests are higher comparing to P2Player. Thus the video quality in P2Player is better than WU, which is confirmed in Figure 11. Still our proposed system performs the best bandwidth utilization, thanks to upstream strategy to allocate the bandwidth based on the downstream request. In addition, the useless chunks ratio is the lowest among the three approaches, and this is due to layers incremental bandwidth allocation and the performance of the scheduling mechanism.

Finally, we note that our system provide acceptable video quality (PSNR > 30dB) even in low neighbors densities (5 neighbors). We remind that a PSNR between 30 and 40 shows that the video quality is of a good enough.

In LayerP2P the quality is acceptable only when the neighbors' density is greater or equal to 20 neighbors.

However, the video quality is always less than the threshold 30 dB in WU approach. For different values of the streaming rate, we measure the Average PSNR, the bandwidth utilization and the useless chunks ratio. The obtained results are shown in Figure 14, Figure 16 and Figure 16.

In Figure 14 we depict the average PSNR while varying the streaming rate. As a first observation, we can see that in low streaming rate the videos PSNR is rather of high values comparing with the high streaming rates situation.

Indeed, according to the peers capacity distribution presented in Table 2, for streaming rate of 300kbps, 90% of the peers in the system (download capacity >=300kbps) can have all the 6 stream layers. This ensures a good proliferation of the layers in the network, and consequently increases the probability to get the requested layers. However, when the streaming rate increases, we observe a drop in video PSNR. This is valid for all the studied strategies. Increasing the streaming rate leads to a reduction in the proportion of high quality level peers in the network. For instance for streaming rate of 1800kbps, only 6% of peers (>1500kbps) can get all the layers.

Consequently the higher layers become increasingly scarce. This means that the probability to get these layers decreases, in turn reducing the video quality level for higher quality level peers.

As a second observation, we can see that the proposed system outperforms the other systems and for all streaming rates situations. Moreover our system delivers an acceptable quality video even in extreme streaming conditions (1800kbps). We explain this by the fact that it allocates the bandwidth not only following the peers' needs but also respecting the layers dependency, i.e., the most important layers first then the less important ones, which results in high bandwidth utilization (Figure 16). In addition it allocates the best links to the most important layers. In this way the number of useless chunks is reduced (Figure 16) and thereby the video PSNR is increased.

In depth study of the proposed system

In this section we study in depth the different aspects of our proposed system. First, we study the impact of incentives on the received quality by a peer. Then, we study the impact of peers' capacity on the overall received video quality. Finally, we study the performance of our system in terms of number of rounds to reach the equilibrium in different network configurations.

In the following, for the sake of simplicity, the video is encoded into 3 layers: a base layer l 0 and two enhancement layers l 1 and l 2 ; each of them streamed at 250kbps (global streaming rate is 750kbps). The network is composed of 1000 peers; each of them connected to 10 neighbors.

a) Incentives and the video quality

Figure 17 shows the impact of the shared bandwidth by a peer on the video quality that he received, measured by PSNR for each layer. The peers are divided into four groups in accordance with the range of the bandwidth that they shared. It is observed that the received video quality at the peers who shared more bandwidth is obviously better than at peers who shared less bandwidth and this for each layer. The reason is that the more bandwidth the peer shares, the more credit he gets, the best links he gets the bandwidth from.

Consequently higher resulting video PSNR. We remember that getting the stream from the best link, means less packet loss ratio, lower delay, etc. which leads to better PSNR value.

We note also that the PSNR of the lower layers is always better than those of the higher layers. This is naturally explained by the incremental bandwidth allocation approach that we adopt. The downstream peer request first the lower layers (from the best links), than the higher layers (from less good links). We now study the impact of the network configuration on the average PSNR of the received video. We vary the proportion of high capacity peers having the capability to get layer l 2 from 5% to 50%. The goal of this experiment is to investigate the impact of high capacity users in the network on the received quality in our system. The goal is also to identify the best network configuration in terms of peers' capacity in order to ensure a good quality of service for the end users.

In Figure 19, we can see that the average PSNR of base layer (l 0 ) and the first enhancement layer (l 1 ) is always of high values (>=29) regardless of the network configuration. This is due to the fact that our proposed system allocates first the lower layers from the best links. In addition, all peers of the network use the lower layers to decode the stream. Consequently the lower layers are more prevalent in the network.

However the PSNR of the second enhancement layer l 2 is correlated with the proportion of high capacity peers in the network. At 5% of high capacity peers in the network, the PSNR of l 2 is 20 dBs. This PSNR is acceptable (>=30) only when the proportion of these peers in the network is up or equal to 20%. This can be naturally explained by the presence of the higher layers in the neighborhood. A low proportion of high capacity peers results in a scarce presence of the upper layers in the neighborhood, and consequently limited propagation of these layers to the high capacity peers. We continue investigating network configuration for our streaming system, and we study the number of rounds to reach the equilibrium in varying network size and for different network configuration in terms high capacity peers (noted Q2) ratio in the network.

We observe that the number of rounds to reach the equilibrium increases with the increase in network size, which can be explained by the increase of competition for bandwidth. Moreover, when increasing the number of downstream peers of Q 2 from 20% to 50%, the number of rounds necessary to allocate the bandwidth increases by 40%, while the gain in PSNR of the received video is all most null as shown in Figure 19.

From Figure 19 and Figure 20, it is evident that increasing the number of high capacity peers in the network leads to significant increase in necessary rounds to reach the system's equilibrium, without real enhancement in the resulting video quality. We conclude also that 10% to 20% of high capacity peers in the network ensures a good quality level as well as less rounds to reach the equilibrium.

CONCLUSION

This paper introduced a novel bandwidth allocation mechanism for layered video streaming in P2P networks.

The proposed mechanism allocates appropriate bandwidth to the appropriate peers while ensuring a minimum quality level to all peers. Each upstream peer organizes a set of auctions to sell its bandwidth, an auction for each layer, starting with the lower layers. In this manner the lower layers are transmitted through the best links, consequently increasing the system throughput.

To study the effectiveness of the proposed mechanism, we performed extensive simulations and we compared the performance of our mechanism with two other approaches. Specifically, we evaluated several essential metrics. First, we evaluated the PSNR of the resulting video. The results show that our proposed mechanism outperforms the two other approaches and ensures always a good video quality (PSNR > 30dBs)

even in low network densities and in extreme streaming rate conditions. Second, we the effectiveness of the proposed incentive mechanism and we study in depth the performance of our proposed system to depict the optimal network configuration for better outcomes.

Based on these findings, we can conclude that bandwidth allocation in P2P streaming systems should be dynamic and should be aware of the needs of neighboring peers, not only in terms of download bandwidth but also in terms of video layers. They should also be aware of the layers' importance, making sure that the most important layers are conveyed over the most reliable links.

As future work, we plan to study techniques to predict the peers' requirements in terms of video quality based on their history, their social relationships, etc. in order to reduce the overhead due to the auction mechanisms.

ANNEX: THEOREM PROOF

The basic idea behind the proof is to demonstrate the Nash equilibrium [START_REF] Chen | Settling the Complexity of Two-Player Nash Equilibrium[END_REF] of each auction B % 7 , and then derive the Nash equilibrium of the whole system. The proof of the Nash equilibrium in B % 7 can be reduced to the proof of the existence of a fixed point for the transfer function describing the evolution of the auction states from an auction round to another. After that we can conclude that our system presents a Nash equilibrium point, which is the set of Nash equilibrium points of all the auctions B % 7 .

We start first by proving the existence of a Nash equilibrium in each auction game B % 7 organized to allocate bandwidth for layer k. Then we derive the Nash equilibrium of the whole system.

The proof of existence of a Nash equilibrium in B % 7 can be reduced to the proof of the existence of a fixed point [START_REF] Agarwal | Fixed point theory and applications[END_REF] for a certain function z: > → > where B defines the bidding configuration of our game in a certain round of the auction.

According to Brouewer fixed point theorem [START_REF] Agarwal | Fixed point theory and applications[END_REF], a fixed point exists for a continuous function z of a convex compact set to itself.

Figure 1 :

 1 Figure 1: Example of P2P layered streaming architecture

Figure 2 :

 2 Figure 2: Example of upstream peer bandwidth allocation problem

  categories: a) bandwidth allocation mechanisms, b) chunks scheduling mechanisms, and c) Incentive mechanisms.

Figure 3

 3 Figure 3 represents part of an overlay composed of three upstream peers A, B and C with upload capacity u i of 100, 150 and 120 kbps respectively, and four downstream peers 1, 2, 3 and 4 with download capacity di of 150, 150, 100 and 100 kbps respectively.

Figure 3 :Figure 4 :

 34 Figure 3: Example of native bandwidth distribution in P2P layered streaming

Figure 6 :

 6 Figure 6: Bandwidth allocation and chunks scheduling modules interaction

Figure 7 .

 7 In this figure, three parallel auctions are organized by upstream peers A, B and C in order to allocate their upload bandwidths u A , u B and u C respectively for layer l i . The downstream peer 1, connected to upstream peers A, B and C, participates in auctions A 1 , A 2 and A 3 organized by the three upstream peers. While the downstream peer 4 participates only in auction A 3 organized by C (since peer 4 is connected only to C).

Figure 7 :

 7 Figure 7: Auctions example Let 0 %,47 be the bandwidth requested by the downstream peer i to its upstream peer j to acquire bandwidth for

Figure 8 :Figure 9 : 4 . 2 . 2 . 2

 894222 Figure 8: Peer i Water filling algorithm example (Step 1)

Algorithm 3: Bidding algorithm 1 )

 1 Receive bandwidth allocation and current prices from upstream peers.2) For each upstream peer:If requested bandwidth 0 %,47 from an upstream peer j is not satisfied:a. Increase the price = %,47 by one unite within the reference price = `% 7

Figure 11 :

 11 Figure 11: Average PSNR Vs. Neighbors' densityIn order to investigate in depth the obtained PSNR performance of the three approaches, we measured for the same scenarios, the bandwidth utilization, that means the ratio of the requested bandwidth over the allocated bandwidth, and the useless chunks ratio among the requested bandwidth. The results are represented in Figure12and Figure13respectively.

Figure 12 :Figure 13 : 6 . 4 . 2

 1213642 Figure 12: Bandwidth utilization Vs. Neighbors' density

Figure 14 :Figure 16 :

 1416 Figure 14: Average PSNR vs. streaming rate Figure 15: Bandwidth utilization vs. streaming rate

Figure 17 :

 17 Figure 17: Average received quality of peers with different shared bandwidth

Figure 18 :Figure 19 :

 1819 Figure 18: Average PSNR Vs. network configuration

Table 1 :

 1 Notation table

	S	Set of upstream peers
	L	Set of downstream peers
	K	Set of application links
	l i b i	Video layer i, i ∊ {0, 1, 2…, M-1}, the stream is encoded into M layers: l 0, l 1, … l M-1 Bit rate of layer l i
	pr

j Priority of downstreal peer j u i Upload bandwidth capacity of peer i d i Download bandwidth capacity of peer i

Table 2 :

 2 frames. If not specified otherwise, the stream is composed of 6 layers. A base layer at 200 kbps and each enhancement layer is encoded at 100 kbps. The stream is subdivided into Chunks of 1s. Peers' upload bandwidth distribution

	Total upload capacity (kbps)	256 320 384 448 512 640 768 1024 >1500
	Distribution (%)	10	14	9	12	3	2	6	38	6
	Contributed upload bandwidth (kbps) 150 250 300 350 400 500 600 800 1000

From the definition of the upstream peer's bidding strategy (cf. section 4.2.2), we derive that the set of possible strategies B i of a player i is a finite set since the price is bounded by = `% 7 and the requested bandwidth is bounded by 0 %, 4 7 . From this we derive that the set of strategies B is compact … (a)

Each biding strategy > %,4

From (a) and (b) we conclude that the set of strategies B is a non-empty convex and compact set. Let's now define the function z and prove its continuity.

The price adjustment algorithm described in 4.1.2.2 defines a mapping function }: < 7 → < % 7 where < 7

denotes the matrix of biding prices sent by downstream peers to their upstream peers and < % 7 denotes the vector of price bids of each downstream peer i to its upstream peers:

The water-filling algorithm described earlier defines a mapping function ": P % 7 → β % 7 where β % 7 denotes the set of downstream peer i bandwidth request to its upstream peers: β % 7 = {b %,4 7 , ∀Y ∈ S % }

We define the mapping function: φ: (β, P) → (β, P) where β denotes the matrix of downstream peer's bandwidth request to its upstream peers. This function maps the bidding configuration of the auction from one round to the following round.

We start by showing the continuity of the function ". Based on the water-filling algorithm, the optimal marginal cost is continuous on <, i.e., for each < % 7 ∈ < the water filling algorithm associates an optimal marginal cost.

In addition the inverse streaming cost function L %,4 ‡ is continuous on < since L is convex and twice derivable.

We conclude that the function " is continuous.

Let us now show the continuity of the function }. We can see clearly in the price adjustment strategy of the downstream peer described in Algorithm 2 that the two possible actions for the downstream peer is that for each system bidding configuration either it increases the price < %, 4 7 or freezes it. From that we derive the continuity of function }. So we show the continuity of } and g, consequently the continuity of z.

z is a continuous function from a convex compact set > to itself, so it has a fixed point as given by the Brouewer fixed point theorem. Thus, we show the existence of the Nash equilibrium for our auction mechanism.

Since our system is composed of a set of auctions B % 7 to allocate bandwidth for a layer k. And we proved the Nash equilibrium of any of the auctions. We can conclude that our system presents a Nash equilibrium point, which is the set of Nash equilibrium points of all the auctions.