Fatima Zohra Kaddour

Emmanuelle Vivier

Mylene Pischella

Lina Mroueh

Philippe Martins

Power Control in Opportunistic and Efficient Resource Block Allocation Algorithms for Green LTE Uplink Networks

Keywords: Energy Efficiency, Power control, Resource Block allocation, SC-FDMA, LTE. UE CQI UE Radio Resource allocation

The energy efficiency in wireless networks is currently a central concern of research. We propose in this paper a new energy efficiency scheme which allocates the mobile's transmission power in function of the allocated Resource Blocks (RB) and the channel conditions of the user on the allocated RBs. We focus on the energy efficiency of the Opportunistic and Efficient Resource Block Allocation (OEA) algorithm and its variant adapted to the Quality of Service (QoS) of the traffics: the QoS based OEA for LTE uplink networks. The OEA and the QoS based OEA allocate the RBs to UEs efficiently and with respect to the SC-FDMA constraints, such that, for one user, contiguous RB are allocated, and the same Modulation and Coding Scheme (MCS) is used over the whole allocated RBs. Once RBs are allocated to UEs, power control is then applied to the mobile's transmission power considering the MCS used and the channel conditions. This energy efficiency allows users to achieve the same throughput than before the power control and does not affect the MCS selection established at the RB allocation step. This new scheme allows the transmission of a high number of bits per Joule.

I. INTRODUCTION

Nowadays, the telecommunications and information communities are facing a more and more serious challenge with the increasing traffic requirements in current and next generation mobile networks associated with the popularity and enhacend functionalities of smart terminals. Then the energy consumption of wireless communication networks and the relevant global CO 2 emission show continuous growth for several years. It has been pointed out that currently 3% of the world-wide energy is consumed by the information and communication technology infrastructure that causes about 2% of the world-wide CO 2 emissions [START_REF]e Mobility European Technology Platform, 1st International Workshop on Green Wireless 2008[END_REF]. Energy costs to the mobile's operators a half of the operating expenses [START_REF] Release | [END_REF]. Moreover, improving the energy efficiency as the resource efficiency is not only beneficial for the global environment, but also makes commercial sense for telecommunication operators supporting sustainable and profitable business. Within the framework of green communications, a number of technical approaches are investigated in the literature. We focus on the energy efficient wireless transmission techniques on uplink 3rd Generation Partner Project (3GPP) Long Term Evolution (LTE) networks. The 3GPP standard adopted, for the LTE networks, the Orthogonal Frequency Division Multiple Access (OFDMA) and the Single Carrier Frequency Division Multiple Access (SC-FDMA) for both downlink and uplink respectively. The relevance of the SC-FDMA on the uplink is that in addition to the OFDMA advantages, the SC-FDMA generates a low Peak to Average Power Ration (PAPR), by considering the whole allocated Resource Blocks (RB) as a single carrier. The reduction of the PAPR can be more than 25% compared to the OFDMA technique [START_REF] Myung | Single Carrier Orthogonal Multiple Access Technique for Broadband Wireless Communications[END_REF]. This advantage not only leads to the decrease of the equalizer complexity and the cost of the mobile terminal by the same way, but also to the decrease of the mobile energy consumption. Using the SC-FDMA technique on the uplink is an encouraging start but it can not increase much the mobile battery life. Therefore, saving the battery life of the mobile's terminal becomes the central concern of the researchers. Works on this scope focus on: (i) maximizing the available energy and (ii) minimizing the energy consumption. The available energy can be increased by (a) the battery capacity improvement which is, unfortunately, not sufficient and is limited due to design aspect, and (b) using the surrounding energy sources, such as kinetic, thermal, and solar energy [START_REF] Joseph | Energy harvesting projects[END_REF]. The mobile's energy consumption can be minimized by first, optimizing the hardware energy consumption, such as choosing power efficient components and applying power management like performing sleep modes for inactive hardware [START_REF] Lioumpas | Uplink scheduling for Machine-to-Machine communications in LTE-based cellular systems[END_REF] or the Discontinuous Reception (DRX) in idle mode [START_REF] Fowler | Study on power saving based on radio frame in LTE wireless communication system using DRX[END_REF]. The second solution to minimize the mobile's energy consumption is the adjustment of the mobile's parameters, like the brightness display and the processor speed for some applications. In the radio access network, the power consumption reduction is performed by a power control of the mobile's transmission power. However, reduction on the mobile transmission power could lead to low user's Signal to Interference plus Noise Ratio (SINR) and a low individual throughput. Therefore, the power control should take into account the required SINR which allows the User Equipment (UE) to use the same Modulation and Coding Scheme (MCS) and reach the same throughput as before power control application. This study focuses on the energy efficiency of the terminals performed by a power control of the UE's transmission power considering the Resource Block (RB) allocation policy and the MCS used by each UE. We study the energy efficiency according to the Opportunistic and Efficient RB Allocation (OEA) algorithm and the Quality of Service (QoS) based OEA algorithm which is adapted to the QoS traffic, proposed in our previous work [START_REF] Kaddour | Opportunistic and Efficient Resource Block Allocation Algorithms for LTE Uplink Networks[END_REF]. The paper is organized as follows. Section II presents the system model. In Section III, we define the proposed energy efficiency scheme including the RB and the power allocation methods. Simulation parameters are summarized in Section IV. Section V shows the numerical results and a comparison in terms of energy efficiency with other reference RB allocation algorithms. Finally, Section VI concludes the paper.

II. SYSTEM MODEL

We consider an uplink LTE network composed of 19 hexagonal cells. Each cell is provided with a tri-sectored eNodeB (eNB). We allocate at each sector a different bandwidth B (i.e. we adopt a 1×3×1 frequency reuse pattern), corresponding to N RB available RBs. The proposed energy efficiency scheme is divided into two entities: (i) the RB allocation, and (ii) the power control, as shown in Figure 1. The RB allocation entity allocates the RBs to the UEs in function of their Channel Quality Identifier (CQI). One RB consists of 84 Resource Elements (REs) corresponding to N RB sc = 12 subcarriers of 15 kHz width each and N RB symb = 7 SC-FDMA symbols in the normal prefix cyclic case [START_REF]Evolved Universal Terrestrial Radio Access (E-UTRA); User Equipment (UE) radio transmission and reception[END_REF]. On the uplink, the CQI is evaluated by the dint of the Reference Signals (RS) which are sent at each time slot in the 4th SC-FDMA symbol [START_REF] Nam | Evolution of reference signals for LTE-advanced systems[END_REF]. The RS use 14% of the total number of REs. Then, the number of REs used for data transmission in one RB is equal to 72 and the real throughput (i.e. considering the MCS selection) that can be achieved by each user k can be computed as:

R k = c∈A k 72 T s BRE k | A k | (1)
where, T s is the time slot duration equivalent to 0. In case of frequency and time correlated fast fading and for a given RB, the SINR level of each UE is computed at each RE (i, j) (with 1 ≤ i ≤ N RB symb and 1 ≤ j ≤ N RB sc ), as:

SINR (i,j) k = P (i,j) k T x G t G r (θ k )Λ N + I (i,j) ( 2
)
where Λ is the total channel gain, expressed as:

Λ = G c (r k ) A (i,j) f 2 A (i,j) s (3)
G c (r k ) is the path loss depending of r k , the distance between the user k and the eNB.

A (i,j) s
is the random shadowing over one RE which follows a log-normal distribution with parameter σ s and A (i,j) f is the time-frequency correlated coefficients fast fading.

P (i,j)
k T x is the transmission power of user k over one resource element. Since the power is equally divided over all the resource elements of one RB, P (i,j) k T x can be expressed as:

P (i,j) k T x = P k T x N U L symb N RB sc | A k | (4)
with P k T x the mobile's transmission power, set at its maximum before the power control (i.e. P k T x equal to P max ). The mobile's transmission antenna gain and the eNB antenna reception gain are denoted respectively as G t and G r . The eNB antenna reception gain G r depends on θ k , angle between UE k and eNB antenna boresight. N is the thermal noise in the considered subcarrier and I (i,j) is the ICI level at each resource element (i, j) obtained by Monte Carlo simulations.

The signal to interference plus noise ratio over one RB c for user k is computed using the mean instantaneous capacity method defined in [START_REF] Ramadas | Wimax system evaluation methodology[END_REF]. It is denoted the effective SINR (SINR eff k ) and is computed as follows:

SINR c eff k = 2 C k /N U L symb -1 (5)
with C k the theoretical Shannon capacity over the whole RB, computed as:

C k = 1 N RB sc N U L symb i=1 N RB sc j=1 log 2 1 + SINR (i,j) k (6)
The effective signal to interference plus noise ratio computed for each user k and over each RB c (SINR c eff k ) will be used as a metric for the RB allocation algorithm detailed in the next section.

III. ENERGY EFFICIENCY SCHEME

The LTE uplink radio resource management includes the RBs and the power allocation, which can be performed: (i) conjointly, or (ii) separately. The conjoint manner is proposed in [START_REF] Sokmen | Uplink Resource Allocation Algorithms for Single-Carrier FDMA Systems[END_REF], where the Binary Integer Programming (BIP) is used to optimally minimize the total power expenditure subject to the rate constraints. The authors consider the contiguity constraint directed by the SC-FDMA technique but compute the total mobile throughput using the theoretical upper bound (i.e. the Shannon capacity). The BIP is commonly proposed as an optimal solution for resource allocation in wireless network, but this method is NP hard. Since the radio resource management occurs at each transmission time interval (which is equal to 1 ms), using the optimal method becomes irrelevant and would cost a lot in terms of computational complexity in the context of freen communications, which motivated us to use a heuristic in allocating the RBs and the mobile's transmission power.

The proposed energy efficiency method allocates the mobile's transmission power after the RB allocation. The power control applied to the mobile's transmission power on the allocated RBs ensures the throughput maximization while minimizing the mobile's power consumption without disrupting the RB allocation, the QoS or the MCS selected. The two steps: (i) RB allocation and (ii) the power control, are described as follows:

A. RB allocation step

For RBs allocation, we use the Opportunistic and Efficient RB Allocation algorithm. We consider that there are N U E users able to transmit their data. Thus, we define K the set of users able to be scheduled

K = {1, • • • , k, • • • , N U E and C the set of free RBs C = {1, • • • , c, • • • , N RB }.
The OEA algorithm aims to maximize the aggregate throughput of the network by allocating efficiently the resource blocks.

max N U E k=1 R k (7)
where R k is the total individual throughput of user k over the whole allocated RBs, and is computed using Equation 1. The maximization problem is subject to: 1) the exclusivity of the allocated RBs:

N U E k=1 x c k = 1 ∀c ∈ C (8)
2) the contiguity constraints:

x j k = 0 ∀j > c + 2 if x c k = 1 and x c+1 k = 0 (9)
3) the MCS robustness:

BRE k = min c∈A k BRE c k ( 10
)
where, x c k is equal to 1 if the RB c is allocated to UE k, and equal to 0 otherwise and BRE c k is the number of bit per RE allowed for UE k on each allocated RB c.

Actually, the algorithm respects by the SC-FDMA constraints. It allocates exclusively adjacent RBs to the same UE (by Formulas 8 and 9) and ensures the MCS robustness (by Formula 10). To maximize the aggregate throughput, the algorithm uses as a metric the effective SINR experienced by each user over each RB. It searches first the pair (UE-RB) which maximizes the metric, then extends the allocation to the adjacent RBs. The RBs expansion allocation is done if and only if the individual throughput of the UE increases. To adapt the OEA algorithm to the QoS required by users, we fix a maximum number of allocated RBs per UE which satisfies its QoS requirements. The RBs allocation expansion is performed as long as this maximum number of allocated RBs per UE is not reached. More important step, which is often neglected in the literature, is the update of the metric before each RBs allocation expansion. The update of the metric considering the update of the mobile's transmission power per RB (using Equation 4), allows us to recursively compute the correct value of individual throughput, the parameter which is based on the expansion decision of the RB allocation.

B. Power control step

Since each mobile user k has its set of allocated RBs A k , the second step determines the appropriate transmission power. It allows the UE to use the same MCS as before the power control and to reach the same throughput. To use a given MCS, the UE must experience in the whole allocated RBs a SINR level higher than the minimum SINR range of the used MCS (SINR M CS,k ) in dB. To ensure user k to use the same MCS as the one used before the power allocation, we define an SINR target (SINR T g ) in dB as:

SINR T g = SINR M CS,k +∆ SINR (11)
where, ∆ SINR is an SINR margin in dB. The new mobile's transmission power per RB P e k allocated to UE k and which allows it to reach the target SINR and achieve the same throughput than the one achieved before the power control, is expressed as:

P e,k = P k Tx | A k | SINR T g SINR eff k ,min (12)
where, SINR eff k ,min is the minimum effective SINR experienced by the UE k on the whole allocated RBs:

SINR eff k ,min = min c∈A k SINR c eff k (13)
The MCS robustness is guaranteed by the SINR eff k ,min based power control.

IV. SIMULATION PARAMETERS

To evaluate the performance of the proposed resource allocation algorithm, we evaluate the mobile's energy consumption saving obtained thanks to power control. Our study focuses on the RB and power allocation to one sector of the central cell users. We compare the OEA algorithm performance with the literature reference's RB allocation algorithms, such as: the Heuristic Localized Gradient Algorithm (HLGA), the Frequency Domain Packet Scheduling -Largest Metric value First algorithm (FDPS-LMF) and the Recursive Maximum Expansion algorithm (RME) proposed respectively in [START_REF] Al-Rawi | Opportunistic Uplink Scheduling for 3G LTE Systems[END_REF], [START_REF] Lee | Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE Uplink[END_REF] and [START_REF] De Temiño | Channel-aware scheduling algorithms for sc-fdma in lte uplink[END_REF].

The simulation parameters are taken from the LTE standards. The performance evaluation is studied in low and high loaded network. Then, the total number of pedestrian users per sector varies between 5 to 80 UEs per sector while a bandwidth B = 5 MHz is allocated to each sector. This correspond to N RB = 25 available RBs per sector. We consider an infinite backlogged traffic, in which, for each user, there is always available data for transmission. The target Bit Error Rate (BER) is equal to 10 -6 and the throughput is computed using the MCS lookup table from [START_REF] Jar | Throughput Maximization for LTE Uplink via Resource Allocation[END_REF], restrictted to the MCS listed in Table I respecting the MCS robustness. The path loss is modeled by the Okumura Hata model [START_REF] Okumura | Field Strength and its Variability in VHF and UHF Land-Mobile Radio Service[END_REF] where the carrier frequency is set to 2.6 GHz, the eNB height is at 40 m and the UE height at 1.5 m. The remaining simulation parameters are summarized in Table I

V. PERFORMANCE EVALUATION

The objective of the proposed energy efficiency method is to allocate both RBs and the mobile's transmission power efficiently, which allows users to benefit from a higher throughput without wasting RB while radiating at a lower power and increasing the mobile's battery life. Figure 2 shows the aggregate throughput of the central cell while varying the network's load (i.e. varying the number of UE from 5 to 80, which corresponds to a number of UE per number of RBs ratio of 20% to 320%). Since the number of UEs per sector and the number of served UEs increase, the aggregate throughput per sector increases whatever the used RB allocation algorithms. We notice that the OEA algorithm reaches its objective and maximizes the aggregate throughput. Its achieves more than 2 Mbps at low loaded network (when there are only 5 UEs per sector) and 6.5 Mbps at highly loaded network (80 UE per sector). The QoS based OEA algorithm achieves a lower aggregate throughput than OEA algorithm, due to the low target throughput fixed at 300 kbps. Then, the QoS based OEA algorithm allocates an adequate number of RBs to UEs which allows them to achieve the target throughput unlike the OEA algorithm, where an UE can be allocated all the RBs that maximize its individual throughput depending on its channel conditions even if it takes all the available RBs allocated to the sector N RB . The HLGA and the FDPS-LMF algorithms achieve a lower aggregate throughput than QoS based OEA algorithm one. Since the RB allocation policy of the HLGA and the FDPS-LMF algorithms is similar, except for the allocation of the remaining RBs, we note a small difference between their total aggregate throughput. The aggregate throughput gap between HLGA and FDPS-LMF is notable at low load because there are more remaining RBs and the HLGA, by allocating the remaining RBs to users which satisfy the contiguity constraints whatever their SINR level, decreases the aggregate throughput. The lower aggregate throughput is given by the RME since it allocates a lot of RBs more RBs per UE without any SINR update before the end of the RB allocation. The resulting SINR value computed at the end of the process, id often even too low to unsure the minimum MCS. The HLGA, FDPS and RME also achieve a lower aggregate throughput than the OEA and the QoS based OEA algorithms due to their negligence of the metric update at each RB allocation expansion and the MCS robustness constraints.

Figure 3 and 4 represent respectively, the energy efficiency of the transmitted data before and after the power control. The energy efficiency of the transmitted data in bits per Joule is defined by the ratio between the number of data transmitted in one second and the necessary consumed energy for transmission in one second. Before the power control, all the mobiles transmit at their maximum power P max . Since the OEA and the QoS based OEA algorithms achieve a higher throughput, then they achieve a higher energy efficiency. They reach respectively 3.5 10 6 and 2.4 10 6 bits/J at low load, while the RME, FDPS-LMF and the HLGA do not exceed 8 10 5 bits/J. In highly loaded networks, the energy efficiency decreases for the five algorithms to reach 7.5 10 5 bits/J for the OEA algorithm and 7 10 5 bits/J for the QoS based OEA algorithm, 5 10 5 bits/J for both HLGA and FDPS-LMF algorithms and 2 10 5 bits/J for the RME algorithm. Unlike the maximum transmission power case, the energy efficiency curves increase when the network load increases after applying power control. In case of highly loaded networks the number of allocated RBs to each UE is low, due to the high number of UEs, which makes the power control more efficient. The number of bits transmitted per one Joule achieves 180 Mbits and 170 Mbits for the QoS based OEA and the OEA respectively. The curves are not smoothed as before the power control curves, because the power allocation depends on the minimum SINR range of the used MCS which is not linear. Figure 5 shows the average mobile's transmission power in dBm. The thick line corresponds to the mobile's maximum transmission power set to 21dBm (i.e. 125 mW). The minimum observed mobile's transmission power is about 17 dBm, which is higher than the lower bound of the transmission power equal to -48 dBm allowed by the 3GPP standard [START_REF]Evolved Universal Terrestrial Radio Access (E-UTRA); User Equipment (UE) radio transmission and reception[END_REF]. We notice that the RME does not decrease a lot the mobile's transmission power still due to the high number of allocated RBs. The algorithms which allow a lowest mobile's transmission power are the HLGA, the FDPS-LMF and the QoS based OEA. This large power reduction is explained by the number of RBs allocated to each UE. Actually if | A k | is low, P k T x is high and the power control according to the SIN R T g is more efficient. In Figure 6, we represent the ratio of saved energy after the power control. The RME algorithm saves only from 2% to 25% of the mobile's transmission power depending to the network load, where the QoS based OEA algorithm saves from 28% to 65% of the mobile's transmission power, which allows it to increase even more the mobile's battery life.

VI. CONCLUSION

In this paper, we investigate the energy consumption problem of the wireless network and more specifically the energy efficiency on the LTE uplink network, which leads to an increase of the LTE mobile's battery's life. We propose a new energy efficiency scheme which depends on the resource block allocation algorithms. The proposed radio resource allocation algorithm allocates first the resource blocks to the UEs, using the Opportunistic and Efficient RB Allocation algorithm and the QoS based Opportunistic and Efficient RB Allocation algorithm, to allocate the RB to the active users. The RBs are first allocated to UEs according to their channel conditions and respecting the SC-FDMA constraints; then we apply a power control to the mobile's transmission power which reduces the mobile's radiated power without affecting the MCS selection and the individually reached throughput. To evaluate the performances of the proposed energy efficiency scheme obtained by the OEA and the QoS based OEA, we compare the saved energy after power control when the RME, FDPS-LMF and the HLGA algorithms are used for the RB allocation. The numerical results show that the OEA algorithms achieve the higher number of bits per Joule and in case of QoS traffic, the QoS based OEA allows to save more than half of the mobile's energy. In future work, we will compare the proposed energy efficiency scheme with the optimal one, using the binary integer programming method.

Fig. 1 .

 1 Fig. 1. Energy efficiency scheme

Fig. 2 .

 2 Fig. 2. Aggregate throughput

Fig. 3 .Fig. 4 .

 34 Fig. 3. Average energy efficiency before power control

Fig. 5 .

 5 Fig. 5. Average mobile's transmission power per UE

Fig. 6 .

 6 Fig. 6. Saved power (W)

  .

	Cellular layout	Hexagonal grid,19 tri-sector cells.
	Max/ Min UE-BS distance	1000 m/30 m
	Carrier frequency	2.6 GHz
	System bandwidth	B = 5 MHz per sector ⇒ N RB = 25
	FFT size	512
	Subcarrier spacing	15kHz
	Time slot duration	Ts = 0.5 ms
	Target Throughput	300 kbps
	SINR margin ∆ SINR	0.3
	Radio channel gain	Okumura Hata for urban areas:
		Gc(r θ jc θ 3dB	) 2 , β]
		θ 3dB = 70 • , β = 20 dB
	User power class	Pmax = 21 dBm (125 mW)
	User antenna gain	Gt = 0 dBi
	Rayleigh fading	coef corr = 0.5,
		UE velocity = 3 km/h
	Log-normal shadowing	σs = 5 dB
	MCS setting	QPSK 1/2, 2/3, 3/4
		16 QAM 1/2, 2/3, 3/4
		64 QAM 1/2, 2/3, 3/4
		TABLE I
	SIMULATION PARAMETERS

jc ) = 10 -a/10 * r -b/10 jc a = 136.7 and b = 34.4

BS antenna pattern

Gr(θ jc ) = -min[12 * (


Brahim Tlili
email: tlili_brahim@yahoo.fr

Corinne Nouveau
email: nouveau@cluny.ensam.fr

Yacine Benlatreche
email: yacine.benlatreche@cluny.ensam.fr

Nasri Mustapha
email: nasri.mustapha@enit.tn.fr

Michel Lambertin
email: lambertin@cluny.ensam.fr

Hardness and scratch response of PVD multilayer coatings

Keywords: Adhesion, multilayer, nanoindentation, scratch-tests, PVD adhérence, multicouche, nano-indentation, scratch-tests, PVD

In the present investigation, novel Cr/CrN, CrN/CrAlN and Cr/CrN/CrAlN multilayered coatings thin films have been developed by dual RF magnetron sputtering. They consist of superposing Cr, CrN and CrAlN layers of 50-500nm thick, up to a total thickness of 0.45-1µm. These coatings were grown on AISI4140 steel samples. The mechanical properties of these coatings were studied by scratch-tests and nano-indentation measurements. The hardness of the films reaches 15.8 GPa for a Cr/CrN multilayered coating sputtered at a bias voltage of -900V. High peak load tests were used to estimate the film adhesion on steel substrates; critical loads (Lc 2 ) of 11N showed weak adhesion properties of the film. Moreover, an inventory of the major scratch-tests failure modes was established, which were classified into plastic deformation and different forms of cracking, spallation and coating perforation events. No evidence of interfacial failure(s) of the sub-layers was observed after the adhesion and nanoindentation tests.

Introduction

Among many ways to enhance the mechanical properties of hard coatings, one is to deposit multilayer structures. A simple way is to produce metal/metal nitride multilayers. Unlike other multilayer systems (e.g.TiN/NbN) just one target is needed and the film sequence is dictated only by switching the reactive gas inlet. The first step in this regard is an interlayer of metal between the steel substrate and the hard coating, which is widely used to enhance adhesion [START_REF] Han | The effect of Cr interlayer on the microstructure of CrN coatings on steel[END_REF]. One of the first metal nitride/metal multilayers studied was the TiN/Ti system [START_REF] Larsson | Deposition and mechanical properties of multilayered PVD Ti---TiN coatings[END_REF]. There are also reports on the CrN/Cr system [START_REF] Lousa | Multilayered chromium/chromium nitride coatings for use in pressure die-casting[END_REF][START_REF] Polini | on the use of CrN/Cr and CrN interlayers in hot filament chemical vapour deposition (HF-CVD) of diamond films onto WC-Co substrates[END_REF]. The main advantage of such a sequence is an increase of fracture toughness while retaining the hardness. The soft (metallic) layers act as barriers for crack propagation [START_REF] Larsson | Deposition and mechanical properties of multilayered PVD Ti---TiN coatings[END_REF]. Another advantage is the relief of internal stress, which enhances adhesion. For multilayers with individual layer thickness in the range of 10 nm, an increase of microhardness has been reported [START_REF] Lousa | Multilayered chromium/chromium nitride coatings for use in pressure die-casting[END_REF]. In this paper, several multilayer coatings were deposited with various superposed Cr, CrN and CrAlN interlayers. Two basic mechanical properties were measured (adhesion and hardness) and a comparison was done between all multilayer coatings.

2 Experimental procedure

Coating deposition

Multilayer coatings were deposited on mechanically polished steel (AISI 4140) substrates by using a dual RF magnetron sputtering system (NORDIKO type 3500-13, 56 MHz) equipped with two targets of high purity (Cr of 99.995 % and Al of 99.999 %). Before deposition the substrates were ultrasonically cleaned and, in situ, sputter etched in a pure argon atmosphere. To improve corrosion resistance and adhesion, a metallic Cr layer with a thickness of about 50 nm was deposited prior to the deposition of the ceramic CrN one. The total thickness of the coatings varies from 0.5 to 1.5 µm. The deposition conditions such as target power, bias voltage, rotational velocity of the substrateholder and deposition time are illustrated in table 1. The deposition temperature was around 200°C.

Tableau 1. Deposition conditions

Nitrogen of very high purity was introduced into the vacuum chamber as the reactive gas. The residual pressure was 10 -6 mbar. The distance between the target and surface backing was 10 cm. Previous to the deposition operation, the surface backings and targets were further etched by an argon ions bombardment during 5 min.

PVD-interlayer material

CrAlN/CrN/Cr coatings 1µm thick or CrN/Cr ones overall 0.5µm thick were deposited on AISI4140 samples using a PVD method. During the initial stage of the PVD process, a thin metallic Cr layer (≤50nm) was deposited. The CrN/Cr or CrAlN/CrN/Cr interlayers can be defined as a sort of graded coating. In fact, the bi-layer CrN/Cr or three-layer CrAlN/CrN/Cr were achieved by progressively decreasing the argon concentration inside the deposition chamber from 100% to 80% of the gas mixture, and increasing the nitrogen content. As a result, the resulting CrN or CrAlN layers are progressively poorer in nitrogen going towards the outermost layers. However, when 20% of argon is completely replaced by nitrogen in the gas mixture, a resulting layer of metallic-Cr is superimposed on the underlying graded CrN one.

Hardness measurements

The testing device is a micro-indenter Fischerscope H100 XYp (maximum load of 1 N, load resolution of 0.02 mN, depth resolution of 2 nm). Indentation consists in continuously applying a load to a specimen via a sharp Vickers pyramid indenter (angle face-to-face of 136°) and to continuously monitors the depth of penetration in the sample. The force is generated electromagnetically and incrementally increased stepwise up to the peak load of 1, 10, 100 or 1000 mN. The calibration procedure follows the requirements of standard ISO-14577.

Scratch-tests

Scratch-test is nowadays the most commonly method used to evaluate the adhesion of the coating/substrate interface. The method is repeatable and capable of generating stresses, which exceed the interfacial bond strength of thin layers. In the scratch-test, a diamond stylus (Rockwell -tip radius 200 μm) is drawn over the sample surface under a stepwise or continuously increasing normal force (20N) until a particular failure of the coating occurs and the coating detaches. The normal load at which this happens is called the critical load L c expressed in Newton (N). To determine the critical load, light (LM) or scanning electron microscopy (SEM), acoustic emission (AE) and frictional force measurement are used. Coating detachment at the critical load is a quantification of the adhesion. Three critical loads (L C1 , L C2 and L C3 ) were determined from a set of three scratches on each specimen (Figure . 1). L C1 is the load at which cohesive failures occurred; L C2 is the load corresponding to first occurrence of adhesive failure (i.e., the load at which the substrate was first exposed); and L C3 is the load at which the coating was completely removed from the scratch track. The specimen surface and diamond tip were cleaned with isopropanol before each scratch. Although acoustic emission and frictional force were recorded during the tests, the critical loads were determined by optical microscopy.

Coatings

Results and discussion

Hardness and elastic modulus evaluated by nanoindentation measurements

Hardness tests of the deposited multilayer coatings were made in the 'load-unload' mode, in which loading of the indenter with a specified force takes place, holding it for the predetermined time, and then the indenter load force is released (Figure . 2). When carrying out the test, one can observe not only plastic deformation of the material but also its elastic deformation. Microhardness determined by this way is called dynamical micro-hardness (Figure .3). The precise meter circuit allows registering the depth of the created imprint while loading or unloading the indenter. With the use of the Hardness Fischerscope H100 XYp, which is part of the ultramicrohardness tester, and the dependency between the load and the depth of the indenter into the examined coating, the Young's modulus as the stiffness of coatings are summarized in table 2. The stiffness of the examined coatings is between 2.5-3N/μm, whereas Young's modulus is between 208-260 GPa (Figure . 4). The presence of three regimes can be identified in figure . 3. For example, for an indentation depth (d) greater than 10% of the coating thickness, the Vickers hardness value steadily decreases towards the substrate value with increasing indentation depth or equivalently increasing indentation load in the case of multilayer coatings (CrAlN/CrN). In the opposite side, for indendation depth greater than 40%, the hardness starts increasing dramatically with decreasing indentation depth or equivalently decreasing load. The results obtained here in respect of the variation of hardness with the composition of the coating are consistent with the only available data of Barshilia et al. [START_REF] Baragetti | Variables affecting the fatigue resistance of PVDcoated components[END_REF] and Okumiya [START_REF] Okumiya | Mechanical properties and tribological behavior of TiN-CrAlN and CrN-CrAlN multilayer coatings Surf[END_REF]. The Young's modulus, also known as the modulus of elasticity (E), is difficult to determine due to the low thickness of the coatings. On the other hand, its value has a strong influence on the contact stress field, coating delamination and detachment, coating fracture, residual stress state within the coating, etc. The second critical load Lc 2 is the point at which the damage becomes continuous and complete delamination of the coating starts; the first appearance of cracking chipping, spallation and delamination outside or inside the track with the exposure of the material substrate -the first adhesion-related failure event. After this point, all of the acoustic emission, friction force signals become noisier [START_REF] Sergici | Scratch testing of coatings[END_REF][START_REF] He | effect of prior plasma nitriding applied to a hot-work tool steel on the scratch-resistant properties of PACVD TiBN and TiCN coatings[END_REF]. The summary results are presented in table 2.

Adhesion evaluated by scratch-tests

Employment of the additional thin (Cr) interlayer in monolayers improves adhesion of the nitride coating to the substrate, as it counteracts propagation of cracks and reduces stresses in the coating/substrate zone.

In general, the adhesion between the PVD coatings and substrate is physical adhesion because of low deposition temperature. A crack was initiated along the scratch track at a certain load, and was followed by a complete delamination leading to failure of the coating.

Tableau 2. Mechanical properties of the multilayers.

Influence of interface design. As the scratch-test is a complex test procedure, the adhesion between coating and substrate plays a dominant role.

Quantitative results are available as shown in figure 8. The results from light microscopy could be confirmed in this case by the on-line measurements of AE and F t which is not the case in general.

Investigations on coating substrate compounds having the same covering layer CrAlN/CrN but different interfacial layers show that critical loads detected by first delaminations change in practice. L c increases with more complex interface design.

Conclusions

Scratch testing is one of the most used techniques to evaluate adhesion of tribological hard coatings. This and the increasing demand for universal test methods that can be used in industrial applications have led to many publications in this field. Since the test procedure of the scratch-test is almost standardized, a standardized evaluation method is open for discussion [START_REF] Davies | Methods of testing the adhesion of metal coatings to metals[END_REF]. One of the most interesting points is the discussion on the definition of the critical load L c . The previous results showed the following:

• Stress states, mechanisms of failure and aspects of damage must not be mixed in interpretation of scratch-tests.

• The optical inspection (microscopy) shows in contrast to online recording definitely the kind of damage. AE and F t can only confirm the results from the optical observation.

• Weak adhesion of the coatings deposited to the substrate should be connected with the existence of the interface and the difference in surface roughness from the pure metal and the PVD coatings. This may be attested by the critical load Lc 2 , which is in the range 2.

Figure 1 .

 1 Figure 1. Worn surface micrographs of multilayer coatings CrN/CrAlN deposited on AISI 4140 steel and tested at 20N showing critical loads L C1 , L C2 and L C3 .

Figure 2 .

 2 Figure 2. Typical loading-unloading curves for Cr/CrN, CrN/CrAlN and Cr/CrN/CrAlN multilayer coatings.

Figure 3 .

 3 Figure 3. Variation of nanoindentation hardness with indenter depth for the Cr/CrN, CrN/CrAlN and Cr/CrN/CrAlN multilayer coatings.

Figure 4 .

 4 Figure 4. Young's modulus of the Cr/CrN, CrN/CrAlN and Cr/CrN/CrAlN multilayer coatings.

  How evaluate then the results of the scratch-tests? Two basically different results are normally available: on the one hand the mentioned detection of cracks and delaminations looking at the scratch by microscopy after the test procedure and on the other hand the recorded signals of tangential force (F t ) and acoustic emission (AE) during scratching. Carrying out the test in practice, the question of the definition of cracks and delaminations is still open, as is the question of the evaluation of the F t and AE plots. Also not clear is the correlation between the on-line plots and the aspects of damage[START_REF] Mats Larsson | Per Hedenqvist, Sture Hogmark, deposition and mechanical properties of multilayered PVD Ti-TiN coatings[END_REF]. The critical load values Lc 1 of Cr/(Cr,N), Cr/CrN/Cr(Al,N) and CrN/Cr(Al,N) multilayer coatings are 8.5, 5 and 1.3 N respectively. The adhesion value for Cr/CrN and Cr/CrN/Cr(Al, N) multilayer coatings are increased remarkably in comparison of CrN/Cr(Al, N) one. As far as Cr/ (Cr, N) coatings, the microstructures and properties of substrate and coatings have huge difference. During deformation, the stress will e concentrated in the boundary between substrate and coatings. It results in the coating cracking and the adhesion strength decreasing. The sharp interface between the coating and the substrate may be eliminated by introducing the concept of gradient and multilayer. For CrN/Cr (Al,N) multilayer coating, interface in PVD CrN/Cr(Al,N) multilayer coating are sites for energy dissipation. The interface can then relax the stress of the coating. Moreover, the interface between Cr and CrN layers would absorbs the energy of micro cracks propagation and prevents them during coating deformation. It is possible that the direction of micro cracks propagation changes and is along the interface when the micro cracks propagate to the interface. The values of the critical load Lc 2 characterized by adhesion of the examined multilayer coatings to the AISI4140 substrate, is caused mainly by the forces of adhesion and has been determined using the scratch-test with a linear growing load (Figure. 5-7).

Figure 5 .

 5 Figure 5. Plot of the dependence of the acoustic emission and friction force from the scratch path for the CrN/Cr coating deposited onto a AISI4140 substrate.

Figure 6 .Figure 7 .

 67 Figure 6. Plot of the dependence of the acoustic emission and friction force from the scratch path for the CrAlN/CrN coating deposited onto a AISI4140 substrate.

Figure 9

 9 illustrates the first delaminations of the multilayer coatings CrN/Cr, CrAlN/CrN and CrAlN/CrN/Cr.

Figure 8 .

 8 Figure 8. Critical loads for different evaluation methods over three types of interface. On the one hand the aspects of damage can be similar, even if the critical load is different (see CrN/Cr and CrN related to CrAlN), and on the other hand the optical images show that similar values for the first delaminations, when having an identical interface (pure chromium), could be very different in size having different intermediate layer (see CrN/Cr and CrN/Cr related to CrAlN).

Figure 9 .

 9 Figure 9. First delaminations for the multilayer coatings: (A) CrN/Cr, (B) CrAlN/CrN/Cr and (C) CrAlN/CrN

  5-11 N, depending on the coating type. • Mechanism of the PVD coatings failure revealed by the adhesion test is connected with the arc shaped cracks caused by tension and spalling occurring at the bottom of the developing scratch. • Cr/CrN/CrAlN and Cr/CrN multilayer coatings exhibits approximately identical performance but different failure forms in scratch-tests. Nevertheless the performance of Cr/CrN/CrAlN multilayer coating in scratch-tests is superior than that of CrN/CrAlN coating due to the better adhesion of Cr/CrN multilayer coating. • The hardness of Cr/CrN and Cr/CrN/CrAlN multilayer coatings is increased due to interface hardening. The adhesion value of Cr/CrN and Cr/CrN/CrAlN multilayer coating is better than that of CrN/CrAlN coating because the interfaces between Cr and CrN layer relax the stress during coating deformation.


Lionel Mercury
email: lionel.mercury@univ-orleans.fr.

Niels Tas

Michael Zilberbrand
email: michaelz20@water.gov.il.

Confined water in complex networks: unifying our understanding of pore water and solutes at all scales

Confined water in complex networks: unifying our understanding of pore water and solutes at all scales

Lionel Mercury, Niel Tas, Michael Zilberbrand

The arid regions experience geopolitical and sociological problems which are related to the lack of water. Yet, it is wellknown that some residual water remains inside the thinner part of the porous space in the soil, possibly being supported by a non-rainfall recharge linked to dew formation. This residual non-evaporating liquid resides in an unsaturated zone which is occluded in pores and channels, can be stabilized in various ways, such as by capillary bridges concavely curved towards the atmosphere, by tiny filled porous spaces (solid-liquid-solid confinement) or by deposition on solid surfaces as adsorbed thin films (solid-liquid-air confinement). The properties of the liquid in each of these situations are of special interest for the management of the mobility and retention of this residual water. Indeed, the pathway to recharge water down to the aquifers through this unsaturated zone is notoriously complex, also because structural and textural heterogeneities occur that result in preferential flow coexisting with almost immobile water. Even deeper, in the saturated zone, it remains still a challenge to safely predict the reactive pathway of water-rock-pollutant interactions in natural settings, because of a similar complexity in the relationship between the structure of the hosting porous network, and the reactive and migrating properties of the guest fluids. With such a wide background, the general aim of the workshop was:

-To define and discuss the different angles of view towards confinement and capillarity, with particular emphasis on the practical consequences in terms of mass balance and flux in real channels and pores, either of synthetic or of natural materials; -To bring together a number of leading scientists in the field of the theoretical description, experimental investigation, and/or phenomenological modeling and to have an inter-disciplinary exchange around the good, the bad, and the ugly in each conceptual frame. Altogether 30 participants from 11 countries attended the 5 day workshop. Some additional colleagues working at the University Ben Gurion of the Negev, quite close to the workshop venue, attended some of the sessions. The main feature of this group was its large interdisciplinarity: the scientific fields encompassed nano/micro-fluidics, fundamentals of surface forces, fluid physics, porous materials science, tree physiology, soil hydrodynamics and chemistry, reactive transport in aquifers. This scientific scope allowed the group to tackle the "confinement, phases, network, triangle" at different scales with very different approaches. The main goal of the present book of proceedings is to reflect the inter-disciplinary exchanges experienced by the participants: sharing common knowledge from such different points of view that, sometimes, it could be felt like different topics. The book is organized thematically into four parts. The first is a general introduction to the surface forces which are clearly the nutshell of the special physics arising around interfaces and inside restricted spaces. The second part focuses on pore water flow at different scales, either to describe its special features in restricted spaces or to define the properties that cause the liquid to remain immobile ("Flow: from nanoto mega-scale"). The third part deals with the corresponding topic of the solute movement and behavior under the same surface forces fields, introducing the strong effect of coulombic forces in the discussion ("Ions, hydration and transport"). The fourth part starts the study of phase transitions with the liquid-vapor phase transition of superheated liquid. Superheating is a common event in natural thin channels and pores, especially under arid conditions, and the end of this metastable state is reached through an explosive boiling (known as cavitation), which is of fundamental and naturalistic value ("In-channels/pores cavitation"). The fifth and last part goes beyond to the solid-liquid phase transitions and their specific behavior when a growing crystal is confined in a thin channel or pore and brought in nanometric proximity to the host solid ("Crystallization under confinement"). Each part is briefly introduced by commenting the logics of the different contributions with respect to the workshop guidelines and the global questioning in the corresponding communities. In the rest of this foreword, we would like to describe how the workshop itself was organized and which lessons we learnt from this experience.

Scientific program

The introductory lecture was delivered by Jacob Israelachvili, worldwide renowned for his in-depth researches on surfaces and interfacial forces, on both experimental and theoretical points of view. He presented the static (interaction) and dynamic (viscous) properties of water adjacent to single mineral surfaces (solid-liquid interface) as well as of water confined between two such surfaces. This topic allowed him to open the discussion on the main force fields able to modify the classic behavior of liquids, which are the direct or indirect causes of many phenomena, further elaborated during the workshop.

The seven other keynote lectures structured the program according to one thematic session per half-day or day. The Tuesday was devoted to the nano-scale (properties and mechanisms), in direct continuation of Israelachvili's lecture. The first half-day (keynote speaker: Sumita Pennathur) focused on nanofluidics and especially on the role of electrokinetics. In this and subsequent sessions the dynamic and static behavior of water confined in synthetic pores were discussed, and many direct consequences or associated phenomena were developed: dissolution in nanochannels, electrocavitation (induced by electro-osmotic flow), proton release and pH of the in-filling liquid, ion or molecule transport, elastocapillary pressure and the deformation of the channel host, seismoelectric effect. The second half-day (keynote speaker: O. Vinogradova) dealt with the surface forces, not as a general topic but related to diverse practical situations: slip on superhydrophobic surfaces, the stability of confined electrolyte solutions, and the computer simulations of solid/liquid interfaces with clay, cement, and polymer membranes. The Wednesday (keynote speaker: Dani Or) focused on the pore scale processes, especially on the conceptual modeling of the gas-liquid (evaporation, water flow and retention, fingering) and solid-liquid equilibria (pressure solution) in natural pores. Key observation was, that moving from the designed "pure" materials to the complexity and heterogeneity of natural samples, requires to develop a simplified sketch of the studied volume, only capturing the relevant features to account for the evolution through time.

The Thursday was entitled "Pore/channel to network", progressively shifting to a global grasp of 3d materials and the role and properties of the in-filling fluids. The first half-day (keynote speaker: Michael Steiger) was essentially focused on salt crystallization in pores with the important issue of the location and the dynamics of the precipitation, but also the way salts can colonize in-pore spaces. The special behavior of hydrates in pores was studied, with the pore size effect but also the role of the metastable solids. The second half-day (keynote speaker: John Sperry), was related to the cavitation events in nature (trees xylem, soil channels, mud volcanoes). This topic was approached by measurements inand ex-situ, by analogous experiments in labs and by thermodynamic calculations (equation of state). The last half-day was devoted to the reactive transport issue, especially connected to the correct way to involve local heterogeneities (pore spaces, chemical composition, water state) in the modeling of extended natural media.

Discussions

The format of the workshop did deviate from conventional scientific congresses that mainly present validated results to its natural audience ("the community"). Here, the speakers tried to present a state-of-the-art of questions and methods in their area, while presenting their own approaches and originality. That resulted in the presentation of many ongoing investigations, making the debate less affirmative but more reflective for many participants, even those belonging to the speaker fields. The workshop also offered to many of us a chance to see phenomena closely related to our own, but from different angles of view, described in different vocabularies and studied by different methodologies. The focus of the event was to encourage fruitful discussions hence all participants were introduced at the beginning of the symposium, with their expertise and their special interests. The lectures were held in an informal atmosphere making it easy to intervene during the talk with commentaries or questions. The timing was consequently difficult to follow, with lively exchanges of ideas and opinions amongst the participants, during the talks and the question times. It was especially noticeable that the general interest for each other did not fade through the whole period of the workshop despite the broad range of topics. The discussions in the technical sessions after the presentations did highlight some main topics, which will be summarized in the following.

Outcomes

During the entire symposium it became obvious that the different communities are speaking different "languages". The gap between the micro/nanofluidics community and the natural pore sciences community for example was quite clear, despite the fact that they share work on channels filled with liquids. The real difference stems from their requisites and goals. The nanofluidics community works with well-designed systems and pure materials and targets a global understanding of these exact systems as well as the phenomena arising inside. The natural pores sciences try first to understand which features are essential (in which perspective?), to afterwards simplify the original (too complex) case studies in such a way that they can be quantitatively modeled. The game is then to test the initial assumptions by matching the results of simulations or modeling with practical observations or measurements. We could as well highlight the gap between the theoreticians and the naturalists, linked to the distinction between possible theoretical states (physical chemistry) and practical states (natural observations). These two distinctions, and all the new concepts learnt when listening to colleagues from other scientific areas, made the workshop interesting for every participant, lively and interactive. Meanwhile, the multidisciplinarity caused a sort of limitation to define immediate practical outcome(s), though the cross-fertilization was felt very useful by all the participants. Upscaling the nano-processes and considering how they can act in natural settings at local (centimetric) and regional (megametric) scales were defined as one of the main challenges of further research. At the final round table, the participants expressed full satisfaction to have attended the workshop, predominantly because it broadened their scientific knowledge, and improved their networking. The informal setting, the opportunity to have discussions with colleagues from different, yet related, disciplines were often outlined in after-workshop messages, as well as the chance to gain new perspectives on research, especially by meeting potential collaborators. Despite this positive feeling, many participants were reluctant to build a proceedings book, because the workshop also highlighted the differences and the barriers from one community to the other.

Most of the participants agree that in the future the impact of confinement, superheating and capillarity on a better understanding of the natural phenomena should be developed. The studies that coupled different properties, like the cavitation processes (in nanochannels, membranes, glass capillaries, xylems, soil pores, …), the special nanoscale transport properties (related to the electrical double layer), the deformations due to the elastocapillary pressure (again, in different materials), the interplay between the chemical composition of the filling liquids and the surface forces, attracted much attention. Also critical is the use of well-defined nanochannels, not only to understand fundamental properties but also to serve as analogous materials to measure and quantify parameters specific to their scale. This knowledge could be embedded in renewed large-scale modelling. The nanochannels are known as key elements in "Lab on a chip" systems, but the workshop made clear to the participants that they could constitute "Nature on a chip" model systems as well. The major outcome of the workshop was that the participants experienced the gap between fundamental science and research applied to natural sciences, and that the different communities talked to each other. By doing that, they started to learn each other's "languages" and were introduced to the problems and needs of the others. The event was an excellent start of a multi-disciplinary effort to develop cross-fertilization between physics, chemistry, biology, soil and earth sciences.

Conclusion

Eventually, we hope that the present proceedings book will reflect the valuable experience we lived through during this workshop, and will give a clear impression to readers of the richness gained by crossing disciplines to go in the Terra incognita area "where nobody feels comfortable", as one of the participants summed up. This workshop was supported mainly by the NATO (grant ESP.MD.ARW 984162), but benefited as well of supports from the french ANR (Agence Nationale de la Recherche; grant CONGE BLAN-61001 & ANR-10-LABX-100-01), the French embassy in Israel, the MESA+ Institute for Nanotechnology (The Netherlands), and the University of Orléans (France).

Most of the participants at the top of the Masada fortress, close to the workshop venue: (from left to right) John Sperry, Sumita Pennathur, Itai Cohen, Dani Or (front), John Selker (rear), Brian Berkowitz, Olga Vinogradova (front), Leo Pel (rear), Michael Zilberbrand (kneeling), Michael Steiger, Attila Imre, Teemu Hölltä, Harvey Scher, Dag Kristian Dysthe, Rosa Espinosa (kneeling), Yuri Aristov, Chuanhua Duan (kneeling), Niels Tas, Rohit Karnik (kneeling), Jan Eijkel, Yukiko Oka (kneeling), Lionel Mercury, Andrey Kalinichev, Isabelle Bergonzi, Arnault Lassin, Vladimir Shilov, Shmuel Assouline, Marc Prat, Larissa Sologubovskaja.


Jiayi Liu

Gwendal Simon

Fast Near-Optimal Algorithm for Delivering Multiple Live Video Channels in CDNs

Content Delivery Networks (CDNs) are confronted with a sharp increase in traffic related to live video (channel) streaming. Previous theoretical models that deal with streaming capacity problems do not capture the emerging reality faced by today's CDNs. In particular, a modern CDN has to deliver a large set of independent non-divisible data streams, which need to be either delivered in whole, or not delivered at all. This constraint is not addressed in previous works.

In this paper we identify a new, discretized streaming model for live video delivery in CDNs. For this model we formulate a general optimization problem and show that it is NP-complete. Then we study a practical scenario that occurs in real CDNs. We present a fast, easy to implement, and near-optimal algorithm with performance approximation ratios that are negligible for large network. To our knowledge, these are the first results for the discretized streaming model, and have both practical and theoretical importance in a topic of growing criticality.

I. INTRODUCTION

In today's Internet, a small set of companies-referred to as Content Delivery Network (CDN) providers -handle the majority of video traffic on behalf of content producers. The techniques used by these companies to deliver terabytes of data per second are mainly exposed by reverse-engineering studies [START_REF] Torres | Dissecting Video Server Selection Strategies in the YouTube CDN[END_REF]. In comparison to the importance of video traffic today, the amount of research related to live video delivery in CDN infrastructures has stayed remarkably low.

The previous theoretical works related to live streaming in CDNs have highlighted the main characteristics of these networks, in particular the 3-tier topology (origin servers, reflectors and edge-servers) [START_REF] Nygren | The Akamai network: a platform for high-performance internet applications[END_REF], and the restriction on the upload capacity of the equipment [START_REF] Zhou | Minimizing Server Throughput for Low-Delay Live Streaming in Content Delivery Networks[END_REF][START_REF] Adler | Algorithms for optimizing the bandwidth cost of content delivery[END_REF]. The goal of these previous works is to reduce the transmission cost of video delivery. However, modern CDNs rely on edge-servers that are located within the network of Internet Service Providers (ISPs), and on peering agreements with these ISPs [START_REF]Netflix Open Connect Peering Guidelines[END_REF]. As a matter of fact, the bandwidth cost to make the traffic transit across different networks has significantly decreased [START_REF] Krogfoss | Analysis: Content peering and the internet economy[END_REF], to a point that it is no longer the main issue.

The major concern today is the growth in the volume of video traffic, and the capacity problem that this growth produces [START_REF] Ingram | You think the internet is big now? akamai needs to grow 100-fold[END_REF]. In addition, the development of dynamic rateadaptive streaming techniques (e.g. MPEG DASH standard) accelerates the stress on the CDN. With such techniques, up to a dozen of representations of the same video stream are available at the server(s). Clients dynamically choose representation according to the accepted resolutions of their devices and their network capacity. This technique puts much stress on the infrastructure, since for a single channel the whole set of representations (with an aggregated bit-rate over 30 Mbps) should be delivered to the edge-servers.

The streaming capacity of networks has been addressed in a series of recent works [START_REF] Sengupta | Peerto-peer streaming capacity[END_REF][START_REF] Zhao | The streaming capacity of sparselyconnected P2P systems with distributed control[END_REF], which aim to determine the maximum bit-rate that can be delivered to all nodes in a network. Some algorithms, mostly based on network coding, obtain near-optimal performances in terms of bandwidth utilization [START_REF] Niu | Asymptotic optimality of randomized peer-to-peer broadcast with network coding[END_REF]. Unfortunately, these solutions are unrealizable in a CDN due to two main reasons. First, they rely on heavy computations which are intractable in the CDN hardware (although the equipment have a very large bandwidth, their computing capabilities are quite small [START_REF]Netflix Open Connect Peering Guidelines[END_REF]). Second, the model used in these works is idealized since it assumes one infinitely divisible data stream, whereas the data that has to be delivered is a large set of distinct non-divisible streams (either representations, or bundles of representations). Each stream has to be either delivered in its entirety, or not delivered at all. Discretized streaming is a more suitable model for multiple live video channels in modern CDNs. The main challenge is to determine a delivery scheme that maximizes the number of delivered streams in a 3-tier network that is constrained by the capacity of its inner equipment. We give a formal formulation of the general problem for this model and prove that it is NP-complete. This is the first contribution in this paper.

Then, we provide a solution that meets the demands of CDN providers. We consider a practical scenario, which corresponds to today's CDN implementation of live streams. We present an algorithm, which is fast, easy to implement, and near optimal. We provide formal theoretical approximation bounds, which are shown to be negligible for the regarded configuration. The algorithm represents the major contribution of this paper. To our knowledge, today's CDN providers apply ad-hoc delivery techniques. Our algorithm is thus the first scientific reference for optimal delivery in the discretized streaming model.

The remainder of the paper is as follows. In Section II, we introduce the discretized streaming model and define the problem. Then, in Section III we provide an ILP formulation of the problem and prove that it is NP-complete. In section IV, we overview the rationale behind the network configuration and describe our near-optimal algorithm for the scenario. Section V evaluates the performance of the proposed algorithm. Related work is presented in Section VI. Finally, Section VII discusses the theoretical results and concludes the paper.

II. SYSTEM MODEL AND PROBLEM DEFINITION

A CDN is composed of a set of communication devices and a set of directed communication links. There are three types of communication devices, also referred to as nodes, in a CDN: a relatively small number of sources (origins), a medium size network of reflectors, and a large number of edge servers. The sources receive and transcode the raw video channels into a set of live representations; the reflectors deliver the representations to the CDN edges, and the edge servers offer the received representations to the clients inside their respective ISPs. In what follows we present our model of live streaming in a CDN, which is followed by a detailed optimization problem formulation.

A. Live video streaming in a CDN

The topology of a CDN is modeled by a directed graph G = (V, E), where V represents the communication devices, and E represents the communication links. Let V S , V R , V E ⊂ V be the set of sources, reflectors and edge servers, respectively. There are three types of possible connections in E: E SR connects sources to reflectors, E RR allows communication between reflectors, and E RE delivers the representations to the edge servers. They are formally defined as:

E SR ={(u, v) : u ∈ V S , v ∈ V R } E RR ={(u, v) : u, v ∈ V R } E RE ={(u, v) : u ∈ V R , v ∈ V E }.
The live streams consist of l different channels. The raw video of each channel is transcoded into k representations, where the bit-rate of the i-th representation, 1 ≤ i ≤ k, is λ i . For simplicity of notation hereafter we denote by [m] the integer interval {1, . . . , m}. Also, let d ij be the i-th representation of the j-th channel, i ∈

[k], j ∈ [l].
The delivery of a representation

d ij , i ∈ [k], j ∈ [l]
, from the source nodes to the edge servers is carried out through a set, T ij , of node-disjoint subtrees of G. Each tree in T ij , also referred to as the delivery tree, has one of the source nodes as its root and edge servers as its leafs. We denote by T ij s the delivery tree of d ij rooted at s ∈ V S . For convenience, let V (T ) and E(T ) denote the node and edge sets of tree T , respectively.

Note that every forwarding node v, either source or reflector, can participate in the delivery of multiple representations. However, for any representation d ij , i ∈ [k], j ∈ [l], v can be a part of only a single delivery tree in T ij . In addition, every forwarding node v ∈ V S ∪V R is also limited by the total outbound bit-rate (capacity) it can support, c(v). Let D(v) be the set of representations forwarded by v, v ∈ V S ∪ V R . Then,

i∈[k] λ i • |{j : d ij ∈ D(v)}| ≤ c(v).
Like all previous works [START_REF] Zhou | Minimizing Server Throughput for Low-Delay Live Streaming in Content Delivery Networks[END_REF][START_REF] Adler | Algorithms for optimizing the bandwidth cost of content delivery[END_REF][START_REF] Andreev | Algorithms for constructing overlay networks for live streaming[END_REF], we consider that the outbound capacity of equipment is the only constraint.

B. Problem definition

Ultimately we would like every edge server to receive all the representations it requires. This however might not be possible due to the outbound capacity constraints at the forwarding nodes, and thus the CDN may support the delivery of only a subset of representations for each edge server. In such case, the CDN provider leverages statistics to prioritize the delivery [START_REF] Nygren | The Akamai network: a platform for high-performance internet applications[END_REF]. The preferences of edge servers in respect to the available representations is captured in a utility score, such that α ij u is the utility score that edge server u assigns to representation d ij . To evaluate the performance of a delivery scheme, the idea is thus to evaluate a utility score function α u (X u ) for each edge server u ∈ V E as follows:

α u (X u ) = i∈[k] j∈[l] α ij u x ij u
where X u is an indicator matrix of size k × l such that x ij u has a value of 1 if u receives d ij and 0 otherwise. Our objective in this paper is to study the Maximum Average Utility Score (MAUS) problem, which essentially is the maximization of the average utility score function of the edge servers, as summarized below.

Problem II.1 (MAUS). Given the topology and capacity constraints of a CDN, find delivery tree sets, {T

ij } i∈[k],j∈[l] , such that u∈V E α u (X u ) is maximized.

III. FORMULATION AND PROBLEM COMPLEXITY

We now discuss the complexity of Problem II.1. We provide an ILP formulation and then show that it is NP-complete.

A. ILP formulation

We use the notation introduced in Section II and extend it by defining two new variables, y and h. Let

T ij s ∈ T ij , i ∈ [k], j ∈ [l]
, be a delivery tree. Then, for every edge (u, v) ∈ E, y ijs u,v is an indicator variable such that:

y ijs u,v = 1 if (u, v) ∈ E(T ij s ), 0 otherwise. For nodes u, v ∈ V such that (u, v) / ∈ E we define y ijs u,v = 0. For every node v ∈ V , h ijs v is an upper bound on the depth of v in T ij s , i.e. h ijs u,v = ≥ depth of v in T ij s , if (u, v) ∈ E(T ij s ), = ∞, otherwise.
To ease the notation, let us define I ijs v (U ) to be the sum of y variables that correspond to incoming edges into v ∈ V from the nodes in U ⊆ V , i.e.

I ijs v (U ) = u∈U y ijs u,v .
Similarly, let O ijs v (U ) be the sum of y variables that correspond to outgoing edges from v to nodes in U , i.e.

O ijs v (U ) = u∈U y ijs v,u .
In the ILP formulation, we omit the use of set membership indication ∈ for the main notations. Whenever we write ∀i, ∀j, ∀s, ∀r, ∀u, and ∀v, we imply ∀i ∈

[k], ∀j ∈ [j], ∀s ∈ V S , ∀r ∈ V R , ∀u ∈ V E , and ∀v ∈ V , respectively. 1 ILP formulation: MAUS max. u∈V E k i=1 l j=1 α ij u x ij u (1)
s.t. x ij u ≤ s∈V S I ijs u (V R ) ∀i, j, u (2)
I ijs r (V S ∪ V R ) ≤ 1 ∀i, j, s, r (3)
I ijs u (V R ) ≤ 1 ∀i, j, s, u (4)
k i=1 l j=1 O ijs s (V R )λ i ≤ c(s) ∀s (5) k i=1 l j=1 s∈V S O ijs r (V R ∪V E )λ i ≤ c(r) ∀r (6)
h ijs s = 0 ∀i, j, s (7)
h ijs r + 1 -h ijs v ≤ |V |(1 -y ijs r,v ) ∀i, j, r, v (8)
O ijs r (V R ∪V E ) ≤ |V |(I ijs r ({s}∪V R )) ∀i, j, s, r (9) I ijs r ({s}∪V R ) ≤ O ijs r (V R ∪V E ) ∀i, j, s, r (10)
The constraints in (2) ensure that the indicator variables x have non-zero values only if there are incoming edges in the respective trees. Constraints in (3)-( 4) guarantee that every node has only one parent in every delivery tree. Cycles are avoided in ( 7)- [START_REF] Sengupta | Peerto-peer streaming capacity[END_REF]. The capacity restrictions are enforced in ( 5)- [START_REF] Krogfoss | Analysis: Content peering and the internet economy[END_REF]. Finally, in ( 9)- [START_REF] Niu | Asymptotic optimality of randomized peer-to-peer broadcast with network coding[END_REF] we require that reflector nodes have outgoing edges in delivery trees iff there is an incoming edge.

B. NP-completeness

Let DMAUS be the decision version of the MAUS problem.

Problem III.1 (DMAUS). Given topology and capacity constraints of a CDN, and a real number B, do there exist delivery tree sets, {T

ij } i∈[k],j∈[l] , such that u∈V E α u (X u ) ≥ B?
Clearly DMAUS is in NP. We now show that DMAUS is NP-hard by a reduction from 3-SAT. Recall that an instance of the 3-SAT problem consists of n variables, z 1 , . . . , z n , and m clauses, C 1 , . . . , C m , where each clause

C j = (y 1 j ∨ y 2 j ∨ y 3 j ), j ∈ [m], has exactly three literals.
Given an instance of the 3-SAT problem we construct an instance of the DMAUS problem. Let G 3SAT = (V, E) be the topology of a CDN. We define V to be (i) a single source node, V S = {s}, (ii) 3n reflectors that are partitioned into two sets, V R = Z ∪A, such that |Z| = n and |A| = 2n, (iii) and m edge servers V E = {u 1 , . . . , u m }. The node set Z = {v 1 , . . . , v n } represents the variables of the 3-SAT instance, the nodes in The edge set E is composed of n links between s and the nodes in Z, 2n links that connect Z to A, and 3m links between A and the edge server nodes. More specifically,

A = {v t 1 , v f 1 , . . . , v t n , v f n } represent
E ={(s, v) : v ∈ Z} ∪ {(v i , v t i ), (v i , v f i ) : i ∈ [n]} ∪ {(v t i , u j ) : i ∈ [n], j ∈ [m], z i is a literal in C j } ∪ {(v f i , u j ) : i ∈ [n], j ∈ [m]
, zi is a literal in C j } For example, see Fig. 1. The capacities of the nodes are defined as follows:

c(s) = n and ∀i ∈ [n], c(v i ) = 1 and c(v t i ) = c(v f i ) = m.
We set the number of channels and representations to 1, and the utility score of receiving the single available representation at every edge server u ∈ V E is α 11s u = 1. Finally, the value B is chosen to be m.

s v 1 v t 1 v f 1 v 2 v t 2 v f 2 v 3 v t 3 v f 3 v 4 v t 4 v f 4 C 1 C 2 C 3 Fig. 1: Graph associated with 3-SAT (x 1 ∨ x 2 ∨ x 3 ) ∧ (x 1 ∨ x 2 ∨ x 4 ) ∧ (x 2 ∨ x 3 ∨ x 4 )
We now show that there is a solution to the 3-SAT problem iff there is a solution to the DMAUS problem. Due to space constraints we provide only a brief outline of the proof.

Let φ be a satisfying assignment for the 3-SAT problem instance. We incrementally construct the delivery tree T 11 s = (V 11 s , E 11 s ). At first V 11 s = {s} and E 11 s = ∅. Then, if there exists an edge server u j / ∈ V 11 s , we pick one of the literals in C j that have a true assignment in φ (since φ is a satisfying assignment, there must be at least one such literal). W.l.o.g. let z i be a literal in C j and φ(z i ) = true. We add to the tree the nodes v i , v t i , u j and the edges (s, v i ), (v i , v t i ), and (v t i , u j ). Note that some of the nodes or the edges might already exist in the tree, so we just add the missing ones. These steps never violate the capacity constraints, as for any v i ∈ Z, at most one outgoing edge, either

(v i , v t i ) or (v i , v f i )
, can be added to E 11 s , which depends on the assignment φ (the first in case φ(z i ) = true, and the latter otherwise). It is easy to conclude that T 11 s is a delivery tree rooted at s and has all the nodes V E as its leafs, and thus the utility score function has a total score of m. The feasibility of each step follows directly from the definition of the CDN topology, G 3SAT .

In the opposite direction, let T 11 s be a solution to the DMAUS problem (as there is only one representation, one channel and one source node, the solution is a single delivery tree). We construct φ by iterating over the nodes in V E . For every u j ∈ V E , if v t i is the parent of u j in T 11 s we define φ(z i ) = true, and φ(z i ) = f alse otherwise. Note that due to capacity constraints, it is impossible that both v t i and v f i are in T 11 s , and thus the assignment is feasible, i.e. the same variable will never be assigned both true and f alse. After the iteration ends, if there are any undefined variables, we set their values to true. What remains to be shown is that φ is a satisfying assignment. For every clause C j , j ∈ [m], there must exist a literal which corresponds to the father of u j in T 11 s (due to the construction of G 3SAT ) and has a true assignment in φ (due to the iterative definition of φ), and thus C j is true.

IV. HOMOGENEOUS BUNDLE DELIVERY

As the above NP-completeness claim implies, it is currently impossible to implement an optimal solution for the general case. Thus, we focus on a practical scenario, which, as far as we understood from our discussions with CDN stakeholders, corresponds to today's CDN implementation. For this practical scenario, we propose a near optimal greedy algorithm which produces delivery trees for every channel.

A. Practical bundle delivery in CDN

In practical CDNs, one can assume that every reflector is connected to any other reflector by a direct link, i.e. for any u, v ∈ V R and u = v, it holds (u, v) ∈ E RR . This can be justified by the fact that the links between reflectors are essentially international connections in the public Internet backbone, where any equipment is virtually connected to any other equipment. In fact, the specifications of the CDN Federation [START_REF] Bertrand | Use Cases for Content Delivery Network Interconnection[END_REF][START_REF] Faucheur | CDN Federations: Lessons from the CDN Federation Pilot Phase 2[END_REF] impose full connectivity between the hosts of every member CDN. In what follows we describe a fundamental and popular CDN scenario, named Homogeneous Bundle Delivery.

For services which are based on DASH, today's CDNs do not deliver each representation individually. Instead, they gather all representations of a given channel into one bundle, and deliver the whole bundle from the source(s) to the edge server(s). Due to the fact that the majority of transcoders are the same, all bundles have roughly the same size, which simplifies the delivery management.

An example of this scenario is as follows: the client of a large-scale CDN is a prominent over-the-top (OTT) service provider, which diffuses a TV package to a large audience. Every channel is bundled, with a total rate of λ. The number of channels l ranges typically from 20 to 150. All the edge servers are expected to receive all the bundles in the same way, i.e. α j u = 1 for every u ∈ V E and j ∈ [l] (note the slight change of notation due to the bundling of representations). For a fixed rate data stream, the capacity constraint of every node is essentially an upper bound on the number of simultaneous bundles that the node can support. For simplicity let b v = ⌊c(v)/λ⌋ be the number of bundles that can be supported by any v ∈ V S ∪ V R . As previously we use the indicator variables

x j u , u ∈ V E , j ∈ [l],
which have the value of 1 if the edge server u receives the bundle of the j-th channel. Our objective for this scenario can be summarized as follows:

max j∈[l] u∈V E x j u .

B. The algorithm

For simplicity of exposition, and following our assumption of full connectivity between the source and reflector nodes (E SR ), we can assume there is a single super-source s * with b s * = s∈V S b s . Note that any solution for the case of having a single super-source can be easily converted into a solution with multiple sources by distributing the load among the sources according to their upload capacities.

The algorithm BUNDLE-DELIVERY (see below) is composed of two phases. First (step (2)), we iteratively construct one delivery tree T j for every channel j, j ∈ [l]. Second (step (3a)), we provide a local improvement for potentially unused capacity. The first phase is further divided into two parts: first we decide which reflectors V j ⊆ V R will be part of T j (the loop in step (2c)); then, we generate the tree T j in step (2f).

The main idea of the algorithm is to have as few reflectors in the delivery trees as possible. By doing so we aim to reduce the capacity "wasted" on inter-reflector communication. We also avoid using nodes with residual capacity of 1 in the first phase since they can forward a bundle to only one node. Instead, we use 2-hop connections in the second phase to utilize their capacity.

There are two main sets of variables in the algorithm. For every node v ∈ V R we use b j v , 0 ≤ j ≤ l, to denote the residual forwarding capacity of node v after the construction of trees T 1 , . . . , T j , i.e. the capacity which remains at v to forward bundles for channels j + 1, . . . , l after it has already forwarded the bundles for channels 1, . . . , j. We also define f j v , for every v ∈ V R , j ∈ [l], to be the number of bundles forwarded by v in T j , i.e. the number of children v has in T j . After V j is determined, these variables are updated according to the forwarding capacity used by each node in V j . The formal definition of BUNDLE-DELIVERY follows. We now explain steps (2f) and (3a) in detail.

Algorithm: BUNDLE-DELIVERY 1) Initialize ∀v ∈ V R : b 0 v ← b v and j ← 1. 2) While ∃v ∈ V R : b j-1 v ≥ 2, b s * ≥ j, and j ≤ l: a) Initialize V j ← ∅ and U j = {u : b j-1 u ≥ 2}. b) Initialize ∀v ∈ V R : f j v ← 0. c) While v∈V R f j v < |V j | + |V E | -1 and U j = ∅: i) Extract from U j a node u * with maximum forward- ing capacity, i.e. b j-1 u * = max u∈U b j-1 u . ii) f j u * ← min{b j-1 u * , |V E | + |V j | -v∈Vj f j v }. iii) Add u * to V j . d) Update ∀v ∈ V R : b j v = b j-1 v -f j v . e) Update j ← j + 1.
f) Generate a tree T j based on the nodes V j .

3) If not all edge servers receive all channel bundles and b s * > l then: a) Use two-hop connections to deliver additional channel bundles.

Generating a tree. For every channel j, T j is a tree which is rooted at s * , has V j as its intermediate nodes, and some or all of V E as its leafs. The out-degree of every node v ∈ V j in T j is exactly f j v . The topology of the tree can be arbitrary with a single constraint, that the super-source has exactly one child in T j . Although the topology of T j has no effect on the number of leafs in T j , which is ( v∈Vj f j v -|V j | + 1) as we show later, we would ultimately like the tree to have the minimum possible height to minimize the number of hops from the super-source node to the leafs. For that purpose we construct T j in the following way. First connect s * to the node v with maximum value of f j v in V j . Then, connect v to f j v nodes with the next highest values of f j in V j , and repeat this process for every node in V j \{v} according to decreasing value of f j until all the nodes in V j have a parent in T j . In the end of this process, some nodes will have an out-degree less than the corresponding value of f j . Connect these nodes to a subset of edge servers, yet to be included in T j , such that the degree of those nodes will match their f j values (Lemma IV.1 below shows that it is always possible).

Fig. 2 shows an example of tree generation. The node-set V j is composed of two nodes: u and v with f j u = 3, and f j v = 2 (Fig. 2(1)). As u has a higher forwarding capacity than v, it is connected to s * and v is set as the child of u (Fig. 2(2)). At this point the out-degrees of u and v are 1 and 0, respectively, which are less than their forwarding capacities in T j . Thus, both u and v are connected to 2 edge servers each (Fig. 2(3)).

(1)

s * u v (2) s * u v (3) s * u v Fig. 2: T j generation: V j = {u, v}, f j u = 3, f j v = 2.
Using two-hop connections: After step (2), the source node might have some unused forwarding capacity. As we show later, if not all edge servers receive every channel bundle, then every reflector v ∈ V R has a forwarding capacity of b j * v ≤ 1, where j * is the last channel for which a tree T j is constructed (the last execution of the step ( 2)). We use reflectors with nonzero forwarding capacity to deliver additional channel bundles to edge servers that are yet to receive them in a two-hop fashion

s * → v → u, where v ∈ V R with b j * v = 1, and u ∈ V E such that u is not a leaf in T i .
Let j * be the last channel for which a delivery tree T j * was constructed. It is easy to observe that the trees generated in every step (2f) are feasible delivery trees rooted at s * , where T j delivers the j-th channel bundle, j ∈ [j * ]. The forwarding capacity upper bound is enforced for the super-source in step (2) for the reflectors in steps (2(c)ii,2d). Moreover, as we show in Lemma IV.1 below, all the leafs in T j are edge server nodes.

Lemma IV.1. In every constructed tree T j there are exactly

v∈Vj f j v -(|V j |-1) leafs and v∈Vj f j v -(|V j |-1) ≤ |V E |.
Proof: Note that for any T j , j ∈ [l], the root s * has exactly one child. Therefore, |V j | -1 nodes have a parent node which is a reflector. According to step (2f), every reflector v ∈ V j has an out-degree of f j v in T j . Thus, we can conclude that in T j a total of |V j | -1 forwarding capacity is used to deliver the channel bundle between reflector nodes, which results in

T j having v∈Vj f j v -(|V j | -1) leaf nodes. Steps (2c,2(c)ii) enforce the inequality v∈Vj f j v -(|V j | -1) ≤ |V E |
, and therefore we can conclude that step (2f) is feasible, i.e. it is always possible to connect a reflector v to some edge server, yet to be in T j , to fill the out-degree of v in T j .

C. Performance analysis of BUNDLE-DELIVERY

Running time. The algorithm BUNDLE-DELIVERY has three main steps.

Step (1) is simple initialization and takes O(|V R |) time to execute. In step [START_REF] Nygren | The Akamai network: a platform for high-performance internet applications[END_REF] we need to maintain the information about the residual forwarding capacity at every reflector. This can be easily implemented by using an ordered list. At first the reflectors are sorted in decreasing order according to their initial forwarding capacity (b 0 v , v ∈ V R ). Then, during the execution of the inner loop in step (2(c)ii), for every j ∈ [l] at most one node in V j will not use all of its forwarding capacity in T j . Removing all the nodes except for, possibly, the last one, and moving the last one in the ordered list according to its updated residual capacity, takes O(|V R |) time. Clearly the use of the ordered list allows an easy implementation of the collection of nodes U j , as we are only interested in the information about the residual capacities in decreasing order. Tree generation itself takes linear time in

|V j | + |V E |. Thus, the total running time of the second step is O(|V R | log |V R | + l • V R + |V E |). Finally, the third step takes O(b s * + |V R | + |V E |) time. To conclude, the running time of BUNDLE-DELIVERY is O(|V R | log |V R | + l • V R + |V E | + b s * ).
Approximation ratio. In our analysis we ignore step (3a) of the algorithm as it has no direct effect on the performance bounds, but rather serves as a local improvement, which may or may not occur. Let S and S * be the values of the solution obtained by BUNDLE-DELIVERY and the optimal one, respectively. The next lemma shows that either the unused capacity of every reflector is at most 1 or S = S * .

Lemma IV.2. At the end of the execution of

BUNDLE- DELIVERY it holds that if ∃u ∈ V R : b j * u > 1 then S = S * . Proof: Suppose that after the construction of T j * there exists a node u ∈ V R such that b j * u > 1.
Clearly, u ∈ U j for every j ∈ [j * ] as the residual forwarding capacity b (•) u can only decrease in subsequent executions of step [START_REF] Nygren | The Akamai network: a platform for high-performance internet applications[END_REF]. There are two possible cases during the construction of T j : Case 1: Node u was chosen in step (2(c)i). Then since b j * u > 1 we can conclude that f j u = |V E | + |V j | -v∈Vj \{u} and u is the last node to be added to V j . Case 2: Node u was not chosen in step (2(c)i). Then, the loop (2c) ended due to equality v∈Vj f j We are now ready to prove the main theorem of this section. We make a reasonable assumption that it is possible to deliver at least one channel to all the edge servers, i.e. S * ≥ |V E |. Proof: We start by drawing an upper bound on the optimal solution. The number of edge servers that can potentially be reached by all the reflectors is at most v∈V R b v . However, some of the capacity needs to be used to maintain the delivery trees (source-reflector, and reflector-reflector connections). In the best case scenario (in terms of "wasted" capacity), every node is used in only one tree, and b s * reflectors have s * as their parent in one of the delivery trees. Thus,

v = |V E | + |V j | -1. Thus, for every j ∈ [j * ] the equality v∈Vj f j v -(|V j | - 1) = |V E |
S * ≤ v∈V R b v - |V R | + b s * .
Next we analyze the solution produced by BUNDLE-DELIVERY. If there exists a node v ∈ V R such that b j * v > 1 (recall that T j * is the last tree to be constructed), then according to Lemma IV.2, S = S * . Otherwise, for every

v ∈ V R , b j * v ≤ 1. Let x = |{v : b v > 1, b j * v = 1}|
be the number of nodes that had their residual bundle capacity reduced to 1 during the execution of the algorithm, and y = |{u : b u = 1}| be the number of nodes with bundle delivery capacity of 1 prior to the execution of the algorithm. Hence the total forwarding capacity used in all the delivery trees (before step (3a), j∈[j * ] v∈Vj f j v = v∈V R b v -(x + y). Note that when a node u * is selected to be added to V j , j ∈ [j * ], in step (2(c)i) it cannot be used again unless it was the last node to be added to T j (due to the computation of the forwarding capacity f j u * ). Thus, the total number of reflectors in all the delivery trees is the number of potentially participating nodes (v ∈ V R , with b v > 1) plus at most j * -1 times a node might appear in two and more trees (due to the partial assignment of f ). Formally, j∈

[j * ] |V j | ≤ |V R | -y + j * -1.
Based on Lemma IV.1 and the above we can now derive lower bound for our solution. As discussed in the beginning of this section we ignore step (3a) in our evaluation (it can only improve the lower bound of S * ).

S = j∈[j * ]   v∈Vj f j v -(|V j | -1)   = j∈[j * ] v∈Vj f j v - j∈[j * ] (|V j | -1) ≥ v∈V R b v -(x + y) -(|V R | -y + j * -1) + j * = v∈V R b v -|V R | -x + 1
As we derived in Lemma IV.2, when a partial forwarding capacity f j v < b j-1 v is assigned to some v ∈ V j , j ∈ [j * ], the delivery tree T j has |V E | leafs. As we already stated in this proof, at most one node can be assigned a partial forwarding

S/S * ≥ S * -x -b s * + 1 S * = 1 - x + b s * -1 S * = 1 - 1 |V E | - b s * -1 S * ≥ 1 -(b s * /|V E |).

V. EVALUATION

We now evaluate the approximation ratio, S/S * of the BUNDLE-DELIVERY algorithm proposed in Section IV. For small instances, S * is obtained by the implementation of the ILP model in IBM ILOG CPLEX software. Due to the complexity of the model, for large instances, we computed S * according to the upper bound given in the proof of Theorem IV.3. We simulated a CDN network with 1 source, x edge servers (x between 10 and 100,000), and the number of reflectors can supply 90% of the required bandwidth to deliver 50 channels. Each channel contains 8 representations. The bit-rate of the representations follows recommendations from Apple HTTP Live Streaming [START_REF] Apple | Using http live streaming[END_REF]: {150, 240, 440, 640, 1240, 1840, 2540, 4540} kbps. Source and reflector capacity is set to 1 Gbps.

The results are shown in Figure 3. For small networks (Figure 3(a)), edge servers receive 44 channels on average in the optimal solution. The result obtained by the BUNDLE-DELIVERY algorithm is slightly below. For large networks (Figure 3(b)), the BUNDLE-DELIVERY algorithm achieves an approximation ratio of 1-10 -3 . For networks with 1,000 edge servers, the ratio S/S * is at least 0.999056, and starting from x = 10,000 it is above 0.999906.

VI. RELATED WORK

In what follows we survey some of the relevant literature in related areas. Streaming in CDN networks. A surprisingly low amount of work are related to live streaming in CDN networks. The earliest work [START_REF] Andreev | Designing overlay multicast networks for streaming[END_REF][START_REF] Almeida | Minimizing delivery cost in scalable streaming content distribution systems[END_REF] did not deal with multiple streams, which is the main challenge in our work. The most recent work [START_REF] Adler | Algorithms for optimizing the bandwidth cost of content delivery[END_REF][START_REF] Andreev | Algorithms for constructing overlay networks for live streaming[END_REF] consider the lack of resources and multiple streams, however their objective is to reduce the bandwidth cost subject to the resource constraints. This objective is outdated since CDNs and ISPs develop peering agreements, which reduce the importance of the bandwidth cost. Finally, the relation between edge servers and end users in the context of DASH is studied in [START_REF] Liu | Rate adaptation for dynamic adaptive streaming over http in content distribution network[END_REF][START_REF] Cicco | Feedback control for adaptive live video streaming[END_REF]. These work complement our work, which focuses on the CDN infrastructure. Multi-tree Packing Delivery. Bounded tree packing problems have been studied in the context of peer-assisted systems [START_REF] Rahimi | On fair and optimal multisource ip-multicast[END_REF][START_REF] Sweha | AngelCast: Cloud-based Peer-Assisted Live Streaming Using Optimized Multi-Tree Construction[END_REF]. The problem is to minimize the amount of additional resources to serve all peers in a peer-to-peer system. This problem is different in CDNs, which are self-sustained networks; missing resources cannot be compensated, but rather need to be used in the best possible way. Numerous work have studied multi-tree packing for peer-to-peer application-layer multicast protocols (see [START_REF] Hosseini | A survey of application-layer multicast protocols[END_REF] for a survey). The goal here is to span all nodes under application-related optimization objective (e.g., to minimize tree height, or to reduce controlling overhead). Streaming capacity in node-capacitated networks. The problem of maximizing the rate of the data stream, subject to the upload capacities of the nodes has been addressed under different models [START_REF] Sengupta | Peerto-peer streaming capacity[END_REF][START_REF] Zhao | The streaming capacity of sparselyconnected P2P systems with distributed control[END_REF]. These work are motivated by the development of peer-to-peer networks. Again, the network and the delivery objectives differ. More important, these work do not address the problem of discretized streaming, and they do not deal with the delivery of particular channels. The maximization of channel utility scores is a major difference between these work and ours, which prevents the use of network coding techniques. Bounded-degree Trees. The minimum Bounded Degree Spanning Tree (BDST) problem aims to determine a minimumcost spanning tree while no node should have more than m children (see [START_REF] Goemans | Minimum bounded degree spanning trees[END_REF]), which is NP-complete for any m ≥ 2. Related variations of this problem feature non-uniform degree bounds [START_REF] Könemann | Primal-dual meets local search: approximating MSTs with nonuniform degree bounds[END_REF]. Our problem formulation differs since, first, consider an unweighted graph, and second, these work aim at spanning all nodes in the network while optimizing an objective function, while we aim at maximizing the number of spanned nodes under a node degree constraint. The only related work in this aspect is [START_REF] Blum | New metaheuristic approaches for the edgeweighted -cardinality tree problem[END_REF], which study the minimum spanning tree with at least k nodes in a weighted graph, but this work do not target the maximal k. Furthermore, these work do not deal with packing several trees and the resource allocation problem that such packing introduces.

VII. CONCLUSIONS AND FUTURE WORK

In this paper we introduced the discretized streaming model, which represents multiple rate-adaptive video channels delivery in today's CDNs. We first formulated a general optimization problem for prioritized live video delivery which we showed to be NP-complete. Then, we focused on a realistic scenario. The CDN provider is in charge of delivering the representations of each channel as one bundle. We developed a fast and simple algorithm which guarantees a solution which is at least 1 -(b s * /|V E |) times the optimal solution. To the best of our knowledge, this is the first result for the discretized streaming model

As future direction for this work it would be interesting to propose solutions for the general problem. In addition, the overall performance can benefit from non-centralized computation of delivery trees. Finally, it is of great importance to explore the computation of the utility score, which is influenced by a large number of parameters, especially in the context of DASH where the demand from clients may change very quickly.

  the two possible values of these variables, and the edge servers represent the m clauses. Overall |V | = 1 + 3n + m.

1 u≥ 2 )

 12 holds and due to Lemma IV.1 the number of leafs in T j is |V E |. Taking a closer look at the conditions in the main loop (2) we can see that j * = min{l, s * } (as for any j ∈ {0, 1, . . . , j * + 1}, b j-, and as a result S = |V E | • min{l, s * }. On the other hand, we have S ≤ S * ≤ |V E | • min{l, s * }. Therefore, S = S * .

Theorem IV. 3 .

 3 Under the assumption that S * ≥ |V E | it holds that S/S * ≥ 1 -(b s * /|V E |).

Fig. 3 :

 3 Fig. 3: Evaluation

We use i, j, s, r, u, and v to refer to representations, channels, sources, reflectors, edge servers, and general nodes, respectively.

ACKNOWLEDGMENT

We thank Dr. Hanan Shpungin for his contribution and French Ministry of Industry for the funding of Zewall project.