Irinel-Constantin Morȃrescu
email: constantin.morarescu@ensem.inpl-nancy.fr

César-Fernando F Méndez-Barrios

Silviu-Iulian Niculescu
email: silviu.niculescu@lss.supelec.fr

Keqin Gu

I.-C Morȃrescu

Stability Crossing Boundaries and Fragility Characterization of PID Controllers for SISO Systems with I/O Delays

Keywords: PID, Delay, SISO, Fragility, Geometry I. INTRODUCTION

This paper focuses on the closed-loop stability analysis of single-input-single-output (SISO) systems subject to input (or output) delays in the presence of PID-controllers. More precisely, using a geometric approach, we present a simple and user-friendly method for the closed-loop stability analysis as well as for the fragility of such PID controllers. The proposed approach is illustrated on several examples encountered in the control literature.

can be attributed to their particular distinct features: simplicity and easy implementation. A long list of PID tuning methods for controlling industrial processes can be found in the literature, see, e.g., [START_REF] O'dwyer | PI and PID controller tuning rules for time delay process: a summary[END_REF], [START_REF] Aström | PID Controllers: Theory, Design and Tunning[END_REF], [START_REF] Silva | PID Controllers for Time Delay Systems[END_REF], to cite only a few. For further discussions in the case of systems with I/O delays, we refer to [START_REF] Silva | PID Controllers for Time Delay Systems[END_REF], [START_REF] Zhong | Robust control of time-delay systems Springer[END_REF], and the references therein. This paper focuses on the design of PID controllers for SISO systems in the presence of I/O delays. The problem received a lot of attention in delay free systems, see, e.g., [START_REF] Keel | Robust, Fragile or Optimal[END_REF] (robustness techniques design leading to fragile controllers), [START_REF] Ho | Non Fragile PID Controller Design[END_REF] (non-fragile PID control design procedure), [START_REF] Alfaro | PID Controller's Fragility[END_REF] (appropriate index to measure the fragility of PID controllers). In this context of delay free systems, some remarks concerning the controller robustness via coprime factorization and robustness optimization tools can be found in [START_REF] Mäkilä | Comments on: Robust, Fragile, or Optimal[END_REF], [START_REF] Keel | Author's Reply[END_REF]. However, there exists only a few results in the delay case as, for example, [START_REF] Silva | PID tuning revisited: Guaranteed stability and non-fragility[END_REF], where only (stable) first-order systems were considered, the authors in [START_REF] Melchor-Aguilar | Robust non-fragile PI controllers for delay models of TCP/AQM networks[END_REF] proposed a non-fragile controller design for a linearized TCP/AQM model, more recently, based on the D-composition method, the properties regarding the increase in the number of unstable poles across the boundary of the PID gain were studied in [START_REF] Saeki | Properties of Stabilizing PID Gain Set in Parameter Space[END_REF],whereas in [START_REF] Hohenbichler | All stabilizing PID controllers for time delay systems[END_REF], the lines that contain the boundary of the stabilizing gain set for the ID (integral-derivative) plane are obtained, finally, based on the extension of the Hermite-Biehler theorem, in [START_REF] Ou | Low-Order Stabilization of LTI Systems With Time Delay[END_REF] a method to compute the set of stabilizing PID gain is obtained, but it requires much computation.

In this paper, inspired by the geometric ideas developed by Gu et al. [START_REF] Gu | On stability crossing curves for general systems with two delays in[END_REF] we start by developing a simple method to derive the stability regions in the gain parameters space of a PID-controller for a SISO system subject to (constant) time-delay. And next, we propose a simple algorithm to analyze the fragility of a given PID-controller for any SISO system subject to I/O delays.

The method is based on the Implicit Function Theorem [START_REF] Guggenheimer | Differential geometry[END_REF] and related properties, and requires three "ingredients": (i) the construction of the stability crossing boundaries (surfaces) in the parameter-space defined by "P" (proportional), "I" (integral) and "D" (derivative) gains, (ii) the explicit computation of the crossing direction (towards stability or instability) when such a surface is traversed, (iii) finally, the explicit computation of the distance of some point to the closest stability crossing boundaries.

In the procedure above, the first step sends back to the D-decomposition method suggested by Neimark [START_REF] Neimark | D-subdivisions and spaces of quasi-polynomials[END_REF] in the 40s (see [START_REF] Michiels | Stability and stabilization of time-delay systems. An eigenvalue-based approach[END_REF] for further comments) or to the parameter space approach (see, for instance, [START_REF] Ackermann | Robust control. The parameter space approach[END_REF], [START_REF] Bhattacharyya | Robust control. The parametric approach[END_REF] or [START_REF] Silva | PID Controllers for Time Delay Systems[END_REF] and the references therein). In the sequel, the stability crossing boundaries (surfaces for PID, curves for PI or PD controllers) represent the collection of all points for which the corresponding characteristic equation of the closed-loop system has at least one root on the imaginary axis. These boundaries define a "partition" of the parameter-space in several regions, each region having a constant number of unstable roots for all the parameters inside the region. Next, using an argument based on implicit function theorem one derives if a region has more or fewer unstable roots compared with its neighboring regions. This allows to detect the regions with no unstable roots which correspond to controller gains guaranteing the stability of the closed-loop system. This methodology has also advantages from the robustness point of view. Precisely, choosing controller gains inside a stability region and far from all the stability crossing boundaries that bound the region, the stability of the closed-loop system is ensured even for some small bounded variations of the controller gains.

The remaining part of the paper is organized as follows: the problem formulation and the class of systems under consideration are presented in Section II. The procedure to derive the stability crossing boundaries is described in Section III. In Section III-A we derive the frequencies for which a crossing surface may be traversed and in Section III-B we classify the boundaries obtained in III. Section III-C present the methodology which enables us to derive if crossing a stability surface in a given direction the closed-loop system gains or looses some unstable roots. In Section IV, the algorithm to analyze the fragility of a given PID controller is presented. Section V presents some illustrative examples and concluding remarks end the paper.

II. THE FREQUENCY MODEL

For the sake of brevity, let us consider now the class of strictly proper SISO open-loop systems with I/O delays given by the transfer function:

G(s):= P (s) Q(s) e -sτ = c T (sI n -A) -1 be -sτ , (1)
where A, b, c T is a state-space representation of the open-loop system. As mentioned in the Introduction, our aim is two-fold. First, design a PID controller

C(s) = k 1 + T d s + 1 T i s = k p + k d s + k i s (2)
that stabilizes the plant (1). Our second goal, is to derive an appropriate PID controller (k * p , k * d , k * i ) and the largest positive value d such that the controller (2) stabilizes the system (1) for any k p , k d and k i , as long as

k p -k * p 2 + (k d -k * d ) 2 + (k i -k * i ) 2 < d.
It is clear that the closed-loop dynamics is characterized by the equation:

1 + G(s)C(s) = 0, (3)
which rewrites as:

f (s; k p , k d , k i ) := 1 G(s) + k p + k d s + k i s = 0. (4)
Our approach follows the lines presented in [START_REF] Méndez-Barrios | On the Fragility of PI Controllers for Time-Delay SISO systems -16th Mediterranean Conference on Control and Automation[END_REF], [START_REF] Morȃrescu | Stability crossing curves of SISO systems controlled by delayed output feedback[END_REF]- [START_REF] Morȃrescu | On the geometry of PI controllers for SISO systems with input delays -IFAC Workshop on Time Delay Systems[END_REF]. More precisely, we want to derive the stability crossing boundaries T which is the set of parameters (k p , k d , k i ) ∈ R 3 + such that (4) has imaginary solutions. As the parameters (k p , k d , k i ) cross the stability crossing boundaries, some characteristic roots cross the imaginary axis.We also consider

Ω = {ω ∈ R | ∃(k p , k d , k i ) ∈ R 3 + such that f (jω; k p , k d , k i ) = 0}
the set of frequencies where the number of unstable roots of (4) changes. The set Ω will be called stability crossing set.

III. STABILITY CROSSING CHARACTERIZATIONS

Considering that Ω is known, the stability crossing boundaries are simply characterized by: Proposition 1: The stability crossing boundaries associated to (4) are described as follows:

         k p = -ℜ Q(jω) P (jω) e jωτ k i = k d ω 2 + ωℑ Q(jω) P (jω) e jωτ
, ∀ω ∈ Ω.

(

) 5
Remark 1: For any fixed ω * ∈ Ω, one obtains a section of a stability crossing surface which consists in a straight line parallel to the (k d , k i ) plane and passing through the point

-ℜ Q(jω) P (jω) e jωτ , 0, ωℑ Q(jω) P (jω) e jωτ
. The slope of this line in the (k d , k i ) plane is always positive and is given by ω 2 .

Remark 2: From the Proposition 1 it is clear that k i = 0 represents a boundary.

Remark 3: Let the relative degree of the system (1) be ρ = 1. Then, the closed-loop system

(1) becomes a system of neutral-type (see, e.g., [START_REF] Hale | Introduction to Functional Differential Equations[END_REF], [START_REF] Michiels | Stability and stabilization of time-delay systems. An eigenvalue-based approach[END_REF]) and

k p , q n p n-1 , ki and k p , - q n p n-1 , ki
belong to the stability crossing surfaces. Here, p n-1 and q n represent the leading coefficients of the polynomials P (s) and Q(s), respectively.

A. Stability crossing sets

In the sequel, we present a practical methodology to derive the stability crossing set. For the sake of brevity, we suppose the following technical assumption is satisfied:

Assumption 1: There exist some bounds k * p , k * p , k * d , k * d and k * i , k * i of the controller gains.
These bounds can be arbitrarily fixed and, in principle, they are chosen by the designer according to the physical constraints of the model/controller. In this context, when Assumption 1 holds, the section of the stability crossing surface obtained for a fixed ω ∈ Ω reduces to a segment (see Remark 1).

Proposition 2: Consider that Assumption 1 holds. Then the stability crossing set Ω is a union of bounded intervals consisting in all frequencies that simultaneously satisfy the following conditions:

         k * p ≤ -ℜ Q(jω) P (jω) e jωτ ≤ k * p ∃ k * d ≤ k d ≤ k * d s.t. k * i ≤ k d ω 2 + ωℑ Q(jω) P (jω) e jωτ ≤ k * i . (6)
Remark 4: Propositions 1 and 2 lead to the following algorithm to determine both the stability crossing set Ω and the stability crossing boundaries T :

• Step 1: One solves the system k * p ≤ -ℜ 1 G(jω)
≤ k * p getting a union of intervals. • Step 2: For all ω derived at the previous step one computes k p and derive the equation of the line (k d , k i ) given by the second equation in (5).

• Step 3: Finally, one keeps only those frequencies ω for which the line (k d , k i ) derived at the previous step intersects the rectangle

[(k * d , k * i ); (k * d , k * i ); (k * d , k * i ); (k * d , k * i )]
. Consider now, that either k d or k i is fixed. Let us also denote by T h , h ∈ {i, d} the crossing curve when d or i is fixed and consider the following decomposition into real and imaginary parts:

R 0 + jI 0 = j ∂f (s; k p , k h ) ∂s s=jω , (7)
R 1 + jI 1 = - ∂f (s; k p , k h ) ∂k h s=jω , (8)
R 2 + jI 2 = - ∂f (s; k p , k h ) ∂k p s=jω . (9)
Then, since f (s; k p , k h ) is an analytic function of s, k p and k h , the implicit function theorem indicates that the tangent of T h can be expressed as

   dk p dω dk h dω    =   R 2 R 1 I 2 I 1   -1   R 0 I 0   = 1 R 1 I 2 -R 2 I 1   R 1 I 0 -R 0 I 1 R 0 I 2 -R 2 I 0   , (10)
provided that

R 1 I 2 -R 2 I 1 = 0. (11)
It follows that T h is smooth everywhere except possibly at the points where either [START_REF] Hale | Introduction to Functional Differential Equations[END_REF] is not satisfied, or when

dk p dω = dk h dω = 0. ( 12
)
Remark 5: If ( 12) is satisfied, then straightforward computations show us that R 0 = I 0 = 0.

In other words, s = jω is a multiple solution of [START_REF] Mäkilä | Comments on: Robust, Fragile, or Optimal[END_REF].

B. Classification of the stability crossing boundaries

It is worth noting here that k p , k d and k i continuously depend on ω. Therefore, in order to classify the stability crossing boundaries we will first classify the intervals belonging to the stability crossing set. Precisely, a deeper analysis of Proposition 2 allows us to say that ω * is an end of an interval belonging to Ω if and only if one of the following condition is satisfied:

• Type 1: -ℜ 1 G(jω * ) = k * p , where k * p is either k * p = k * p or k * p = k * p .
In this case, ω * ∈ Ω and the stability crossing surface approach a segment parallel to the (k d , k i ) plane given by k p = k * p and

k i = k d • (ω * ) 2 + ω * ℑ 1 G(jω * ) , k * d ≤ k d ≤ k * d , k * i ≤ k i ≤ k * i • Type 2: - 1 ω * ℑ 1 G(jω * ) = k * d .
In this case ω * ∈ Ω and the stability crossing surface ends

in the point -ℜ 1 G(jω * ) , - 1 ω * ℑ 1 G(jω * )
, 0 , included in the (k p , k d ) plane.

• Type 3:

ω * ℑ 1 G(jω * ) = k * i .
In this case ω * ∈ Ω and the stability crossing surface ends in

the point -ℜ 1 G(jω * ) , 0, ω * ℑ 1 G(jω * )
, included in the (k p , k i ) plane.

Similarly to [START_REF] Gu | On stability crossing curves for general systems with two delays in[END_REF], we classify the stability crossing boundaries in 8 types in function of the kind of the left and right ends of the corresponding frequency crossing interval. Precisely, we say that a crossing surface is of type ab, a, b ∈ {1, 2, 3} if it corresponds to a crossing interval (ω l , ω r ) with ω l of type a and ω r of type b. Let us notice that generally the intervals (ω l , ω r ) are closed.

C. Crossing direction

As explained in [START_REF] Cooke | On zeroes of some transcendental equations[END_REF], [START_REF] Walton | Direct method for TDS stability analysis[END_REF], a pair of imaginary zeros (s, s) of the characteristic equation f (s; k p , k d , k i ) = 0 cross the imaginary axis through the gates -jω , jω respectively, as (k p , k d , k i ) moves from one side of a stability crossing surface to the other side. The direction of crossing may be calculated using implicit function theorem as described in [START_REF] Gu | On stability crossing curves for general systems with two delays in[END_REF], [START_REF] Morarescu | Stability crossing curves of shifted gamma-distributed delay systems[END_REF]. Precisely, the characteristic equation f (s; k p , k d , k i ) = 0 defines an implicit function s of variables k p , k d and k i . The definition of f (s; k p , k d , k i ) given by ( 4) allows us to compute the following partial derivatives:

∂s ∂k p = s 2 G 2 (s) k i G 2 (s) -k d s 2 G 2 (s) + s 2 G ′ (s) , ∂s ∂k d = s 3 G 2 (s) k i G 2 (s) -k d s 2 G 2 (s) + s 2 G ′ (s) , ( 13
)
∂s ∂k i = sG 2 (s) k i G 2 (s) -k d s 2 G 2 (s) + s 2 G ′ (s)
.

Let ( kp , kd , ki ) a point belonging to a stability crossing surface and let s = j ω, ω > 0 be the corresponding imaginary zero of the characteristic equation. Let x = (x p , x d , x i ) be a unit vector that is not tangent to the surface. Let us also use the following notation

-→ k = (k p , k d , k i ) and -→ k * = ( kp , kd , ki ).
Proposition 3: A pair of zeros of (4) moves from the left half complex plane (LHP) to the right half complex plane (RHP) as (k p , k d , k i ) moves from one side of a stability crossing surface to the other side through ( kp , kd , ki ) in the direction of x if

ℜ ∂s ∂k p x p + ∂s ∂k d x d + ∂s ∂k i x i s=jω, -→ k = -→ k * > 0. ( 14
)
The crossing is from the RHP to the LHP if the inequality ( 14) is reversed.

IV. FRAGILITY ANALYSIS OF PID CONTROLLERS

Consider now the PID fragility problem, that is the problem of computing the maximum controller parameters deviation without loosing the closed-loop stability. In other words, given the parameters

(k * p , k * d , k * i )
such that the roots of the closed-loop characteristic equation:

Q(s) + P (s) k * p + k * d s + k * i s e -sτ = 0, (15)
are located in C -(that is the closed-loop system is asymptotically stable), find the maximum parameter deviation d ∈ R + such that the roots of (3) stay located in C -for all controllers (k p , k d , k i ) satisfying:

(k p -k * p ) 2 + (k d -k * d ) 2 + (k i -k * i ) 2 < d.
This problem can be more generally reformulated as: find the maximum parameter deviation d such that the number of unstable roots of (3) remains unchanged.

First, let us introduce some notation:

T = N l=1 T l , T l = (k p , k d , k i ) ω ∈ Ω l , --→ k(ω) = (k p (ω), k d (ω), k i (ω)) T , -→ k * = k * p , k * d , k * i T , -→ k ab (ω) = (k a (ω), k b (ω)) T , -→ k * ab = (k * a , k * b ) T ,
where a, b ∈ {p, i, d}. Let us also denote d T = min l∈{1,...,N } d l , where

d l = min (kp,k d ,k i )∈T l (k p -k * p ) 2 +(k d -k * d ) 2 +(k i -k * i ) 2 .

A. PI-PD Controller Fragility

Let

k d = k * d ∈ R or k i = k * i ∈ R
d * pi = min |k * i |, min ω∈Ω f pi -→ k pi (ω) - -→ k * pi . (16)
PD-Controller: Let

k i = k * i be fixed, then d * pd = d * pd = min k d∞ , k * p -k p (0) , min ω∈Ω f pd -→ k pd (ω) - -→ k * pd , (17) with,
k d∞ =    min k * d -qn pm , k * d + qn pm if m = n -1 ∅ if m < n -1
and Ω f ab , a, b ∈ {p, i, d} is the set of roots the function f ab : R + → R,

f ab (ω) -→ k ab (ω) - -→ k * ab , d -→ k ab (ω) dω , (18)
where " •, • " means the inner product.

B. DI Projection

Let k p = k * p ∈ R be fixed, we have the following result: Proposition 5: The maximum parameter deviation from (k * d , k * i ), without changing the number of unstable roots of the closed-loop equation ( 3) can be expressed as:

d * di = min    |k * i |, min ω ℓ ∈Ω k * p    ω 2 ℓ k * d -k * i +ω ℓ ℑ Q(jω ℓ ) P (jω ℓ ) e jω ℓ τ (ω ℓ ) 4 + 1       , (19)
where Ω k * p is the set of roots of the function

f k * p : R × R + → R, f k * p k * p , ω k * p + ℜ Q(jω) P (jω) e jωτ . ( 20
)
Remark 6: Observe that (20) has an uncountable number of solutions, however in Proposition 5 we have considered the set including the corresponding (k * d , k * i ) points.

C. PID Fragility Algorithm

In order to obtain the obtain the PID fragility we present the following algorithm:

• Step 1: Let k * pid ∈ R 3 be
ω ℓ ∈Ω θ    (ω ℓ ) 2 k * d -k * i + ω ℓ ℑ Q(jω ℓ ) P (jω ℓ ) e jω ℓ τ (ω ℓ ) 4 + 1    . • Step 5: If d * θ < d cos θ then set d = d * θ
/ cos θ and go to step 2. Otherwise continue to step 2.

• Step 6: If θ = π 2 , the procedure is finish and d is the PID fragility for the controller k * p , k * d , k * i .

V. ILLUSTRATIVE EXAMPLES

In order to motivate the previous results, we consider in the sequel some numerical examples.

A. PID fragility analysis

Example 1: Consider the following system [START_REF] Ou | Low-Order Stabilization of LTI Systems With Time Delay[END_REF]:

G(s) = s 3 -4s 2 + s + 2 s 5 + 8s 4 + 32s 3 + 46s 2 + 46s + 17 e -s . (21)
By choosing k * p ∈ 0, 9 2 , we obtain the stability region depicted in Fig. [START_REF] Morȃrescu | On the geometry of PI controllers for SISO systems with input delays -IFAC Workshop on Time Delay Systems[END_REF]. Example 2 (unstable, non-minimal phase system): Consider the following plant [START_REF] Méndez-Barrios | On the Fragility of PI Controllers for Time-Delay SISO systems -16th Mediterranean Conference on Control and Automation[END_REF],

Controller

G(s) = s -2 s 2 -1 2 s + 13 4 e -1 2 s . (22)
The interest in the analysis of this system, remains in the fact that the closed-loop plant becomes a system of Neutral-Type. Now, applying the same procedure as before, and considering k * p ∈ (0.32595, 1.625) we obtain the following stability region.

For the fragility analysis, lets consider the controller k * p , k * d , k * i = 5 8 , - [START_REF] Neimark | D-subdivisions and spaces of quasi-polynomials[END_REF].

B. Stability crossing boundaries classification

  be fixed, we have the following result: Proposition 4: The maximum parameter deviation, without changing the number of unstable roots of the closed-loop equation (3) can be expressed as: PI-Controller: Let k d = k * d be fixed,

Fig. 1 .Fig. 2 .

 12 Fig.1. The PID stability region for kp ∈ 0,9 2 .

Fig. 3 .

 3 Fig. 3. The PID stability region of Neutral-Type .

Fig. 4 .

 4 Fig. 4. PID-fragility for the controller k * p , k * d , k * i = 5 8 , -1 10 , -2 5 .

Example 3 :

 3 Finally, lets consider the SISO plant[START_REF] Bajcinca | Computation of stable regions in PID parameter space for time-delay systems[END_REF],G(s) = -s 4 -7s 3 -2s + 1 (s + 1) (s + 2) (s + 3) (s + 4) (s 2 + s + 1) rectangle: 0 ≤ k p ≤ 5, -12 ≤ k i ≤ 5, 0 ≤ k d ≤ 10, we obtain the following cases: Based in these results, the table III classifies the cases cited above.

Fig. 5 .

 5 Fig. 5. Boundary classification Type 1 for the system (23).

Fig. 6 .

 6 Fig. 6. Stability crossing boundaries classification for the system (23). (Upper) Type 2. (Lower) Type 3.

  Solve f k * p k *pθ , ω = 0 and denote by Ω θ the set of solutions.

	fixed. Then, set d = min d * pi , d * pd , d * di .
	• Step 2: Sweep over all θ ∈ -π 2 , π 2 and compute k * pθ = k * p + d sin θ.
	• Step 4: Compute,
	d * θ = min

• Step 3:

  1 10 , -2 5 , leading to the results summarized in TableII. Figure4illustrate such a results.

TABLE II PID

 II FRAGILITY FOR THE EXAMPLE

TABLE III CLASSIFICATION

 III INTERVALS TYPE FOR THE SYSTEMS[START_REF] O'dwyer | PI and PID controller tuning rules for time delay process: a summary[END_REF].

	Interval	Classification
	[0.37823, 3.16356]	Type 11
	[0.37823, 0.89290]	Type 12
	[0.37823, 0.41294]	Type 13
	[0.89290, 3.16356]	Type 21
	[0.41294, 3.16356]	Type 31
	[0.41294, 0.89290]	Type 32


Lina Maria Rojas-Barahona

Thierry Bazillon
email: thierry.bazillon@univ-avignon.fr

Matthieu Quignard
email: matthieu.quignard@loria.fr

Fabrice Lefevre
email: fabrice.lefevre@univ-avignon.fr

Using MMIL for the High Level Semantic Annotation of the French MEDIA Dialogue Corpus. *

The MultiModal Interface Language formalism (MMIL) has been selected as the High Level Semantic (HLS) formalism for annotating the French MEDIA dialogue corpus. This corpus is composed of human-machine dialogues in the domain of hotel reservation and tourist information. Utterances in dialogues have been previously annotated with a concept-value flat semantics for studying and evaluating spoken language understanding modules in dialogue systems. We are now interested in investigating the use of more complex representations to improve the understanding capability. The MMIL intermediate language is a high level semantic formalism that bears relevant linguistic information, from syntax up to discourse. This representation should increase the expressivity of the current annotation though at the expense of the annotation process complexity. In this paper we present our first attempt in defining the annotation guidelines for the HLS annotation of the MEDIA corpus and its effect on the annotation process itself, revealed by annotators' disagreements due to the different levels of hierarchy and the granularity of the features defined in MMIL.

Introduction

MMIL is an ontology-oriented representation language that has been used in several natural language processing (NLP) applications, [START_REF] Denis | Extending MMIL semantic representation: Experiments in dialogue systems and semantic annotation of corpora[END_REF]. It permits the integration of divergent resources in distributed systems as well as the representation of various levels of linguistic analysis. In this work we are particularly interested in exploring the representation of these linguistic levels for analyzing utterances in the context of human-machine interactions. To be able to evaluate the representation on a large set of data the French MEDIA dialogue corpus is used, [START_REF] Bonneau-Maynard | Semantic annotation of the french media dialog corpus[END_REF]. The MEDIA corpus collects about 70 hours of spontaneous speech in the task of hotel room reservation and tourist information. It has been created using a Wizard-of-Oz technique, as a consequence, the utterances are made of many disfluencies, hesitations, false starts, truncations or fillers words (e.g., euh or ben). Thus, the syntactic analysis is relevant for keeping valuable information for further processing (e.g., reference resolution). The semantics describe fine grained predicates, arguments and features based on the domain knowledge. Similarly, the possibility of link references for pragmatic analysis and the representation of the illocutionary force of utterances are relevant to improve the understanding in NLP applications. We selected MMIL for the semantic annotation because it supports the representation of all these features.

Although these features enrich the semantic annotation of utterances in the corpus, they also increase the complexity of the annotation and compromise the agreement between annotators. The possibility of representing different instantiations in MMIL has been the main cause of disagreement between annotators. On the one hand, linguists tend to annotate the surface form of the utterance. On the other hand, application designers are more biased towards its canonical representation by keeping relevant task oriented actions and features. The trade-off between these two lines of representation is significant for building appropriately the annotation guidelines for the semantic annotation. The annotation would keep the most valuable information in a multilevel representation for enhancing the understanding capability of NLP applications. In this paper we introduce briefly MMIL and we describe the annotation methodology and the inter-annotation agreement.

The High Level Representation

MMIL permits the representation of communicative actions that are represented as components. A component is a structure that gathers the communicative event and its propositional content. Components are made up of two main types of entities: events, which are entities anchored in the time dimension, and participants, which are entities not bounded by time. Entities are linked together by relations and are described by sets of features (i.e. pairs of attribute-value), [START_REF] Denis | Extending MMIL semantic representation: Experiments in dialogue systems and semantic annotation of corpora[END_REF]. Every component has a unique communicative event with the illocutionary force represented by means of the dialogueAct feature. The propositional content is represented as a main event with its arguments, which can be either events or participants, linked to the communicative event by a relation propContent. In this representation, predicates are usually represented as events and predicate arguments are usually represented as participants. Relations between participants and events usually describe the thematic roles.

French: "/ 1 euh vous venez de dire que précédemment qu' il n' a y avait plus de chambres disponibles à ces dates et maintenant vous en avez/ 2 donc je voulais juste m' assurer qu' au Novotel vous avez bien une chambre double euh pour un couple avec un enfant avec une baignoire dans la chambre euh il me il me faut un Parc Ãȃ proximité et euh cent dix euros maximum la nuit est-ce-que vous pouvez vérifier" English:"/ 1 um you just said earlier that there are not more rooms available on these dates and now there are/ 2 so I just wanted to be sure that you have at the Novotel a double room for uh a couple with one child with a bath in the room uh I need a park nearby and uh hundred and ten euros up at night is that you can check" of a misunderstanding of the first segment ("/ 1 " in Figure 1). Right: this component is a request acknowledgment, representing the second segment("/ 2 " in Figure 1). Note that events are exemplify by square boxes while participants are exemplify by ellipses.

Let us focus on the MMIL representation for a typical utterance of the MEDIA corpus, given in Figure 1. In this utterance the user first announces an inconsistency, then asks for clarification. Thus, two MMIL components with different communicative actions, inform and request acknowledgment, have been used, as shown in Figure 2. The component on the left has a main event that describes the misunderstanding expressed in the first segment 1 of the utterance. It is represented by the ontological concept "Understand" and by the syntactic feature polarity with the negative value. It also contains a coordinated entity mirroring an adversative coordination between two events, state. The event state represents the status of something, therefore the negated state event can be understood as "there are not more rooms available on these dates" while the positive state represents "now there are". The participants symbolize the arguments "rooms" and "dates" respectively. The component on the right expresses the clarification request of the second segment. It verifies the status of the hotel with the specific constraints.

The Annotation Methodology

In the process of defining the annotation guidelines, we elaborated a specification document that describes the representation of dialogue acts, events and exemplifies the high-level semantics. Moreover, it delves into the methodology that might be applied for the automatic and manual annotation. Afterwards, a linguist expert and a project designer were in charge of defining the annotation guidelines. For this purpose, they annotated manually a subset of utterances which were supposed to be representative of the most complex aspects of the HLS annotation, in terms of their semantic constituents. 330 utterances were selected. They are all directly related to the reservation task (first two rows in Figure 4) and mostly occurred in the first 3 turns of the dialogues when the user is describing his goal, defined as an overall objective along with a set of constraints. Hereafter, we present the preliminary evaluation of the experts' agreement on these utterances.

The annotation process has been supported by an annotation tool: ATool. It accesses two knowledgebases, one for the MMIL formalism and the other for the MEDIA domain. The latter is adapted from the MEDIA evaluation campaign, [START_REF] Bonneau-Maynard | Results of the french evalda-media evaluation campaign for literal understanding[END_REF]. ATool permits annotators to navigate through utterances, while displaying the MMIL representation. Annotators can design the MMIL components graphs, define the MMIL entities by associating features, values and segment. ATool will suggest the possible features and values for the MMIL formalism and for the domain according to the knowledge-bases ensuring the integrity of the constructed MMIL components in the annotation.

The MEDIA corpus is rich in expressions that evoke several communicative actions. Figure 4 shows a few examples. For the purpose of the task, we are interested in the underlying meaning of sentences, thus politeness and indirectness are discarded from the HLS representation. For this reason, in requests the speaker is the patient, while the hearer is the agent (see Figure 4). Because when translating the utterance into its deep instantiation, the speaker will benefit from the execution of the action, while the hearer has the obligation to perform the action. All the expressions in the corpus that bear the semantics of "command for a reservation" (e.g., je veux réserver, je souhaite réserver, je voudrais faire une réservation, j'aimerais faire une réservation, all equivalent to I would like to reserve), have been normalized with the deep component shown in Figure 3, exemplifying unequivocally the user's desire to request for a reservation. The possible arguments and roles have been detailed in the domain knowledge-base. As a consequence the knowledge-base defines relations between hotels, rooms, customers, prices, equipments, services, locations and dates. Besides, the grammatical relations and features, such as coordination, have been defined in the MMIL knowledge-base. Coordination is indicated with the "coordtype" feature and it is used in cases of conjunction (je veux une chambre simple et deux chambres double, I want a single room and two double bedrooms), disjunction (Paris ou en proche banlieue, in Paris or suburbs) or adversation (en ville mais pas trop loin de la mer, in the city but not too far from the sea).

For annotating events we can find the main verb in the utterance and represent it as the main event in MMIL by following a domain-specific classification of verbs, from which Figure 4 shows some equivalences among dialogue acts and verbs. For each participant or event, several features can be 1 Segments are sequence of words that are depicted as "/i", where i is the number of the segment. added. The most important of them are "object type" (for participants) or "event type" (for events), which specify their ontological concepts. They may be réserver (reserve), hôtel (hotel), chambre (room), périodedetemps (time), ville (city), person, adulte (adult), enfant (child), localisationnommée (places), among others. There are more specific features, for instance, the journey dates, hotel features (e.g., name, standing, services, etc). Some of these features have predefined values, such as the gender of an object (either masculine or feminine). On the other side, features such as cardinality, have not predefined values, in that case, the annotator has to manually indicate the correct value.

Obviously, the annotation task difficulty increases with the utterance's complexity. The representation is rather tedious to define in elliptical utterances, such as multiple reservations, in which implicit and explicit information must be taken under consideration. Furthermore, the MMIL formalism does not support the association of discontinuous segments to entities, generating some imprecisions in the HLS annotation. For instance, in je voudrais une chambre pour deux personnes euh simple (I would like a room for two people uh simple),"une chambre" (a room) and "simple" should be linked to an unique participant, having as object type ("Room") and as type of room "simple". However, given that the speaker has not mentioned "simple"right after "chambre", there is a new element imbricated between them: "pour deux personnes". As a result, the annotator must integrate the subsegment 'pour deux personnes" in the "Room" participant. Even though this subsegment is also associated to the "Personne" participant.

Results

When analyzing the sample of 330 utterances that were annotated, we found a perfect agreement between annotators in the detection of dialogue-acts, main events, as well as main arguments. In constrast, when measuring fine-grained features inside components we found eight types of disagreement, namely conjunctions, disjunctions, creation of participant for simple features, groups of features inside entities, features of entities, values of features, relation names and relation among entities. The most frequent cases concern the first two, which refer to coordination: conjunctions (20%) and disjunctions (5%). The inter-annotator agreement for the coordinate entities was computed, obtaining the kappa measure, [START_REF] Carletta | Assessing agreement on classification tasks: the kappa statistic[END_REF], of 0.25 for conjunctions and 0.15 for disjunctions, meaning a fair and slight agreement respectively. Although the other cases were less frequent, the inter-annotator agreement was even lower, indicating no agreement.

In spite of the disagreement, when measuring the global similarity between the MMIL components created by both annotators we found a high score of 98%. This metric measures the graph similarity by computing the similarity between entities and relations, including the fine-grained features inside entities. The speech-act, main-event and main arguments are in compliance with the specifications in both annotations. These issues show that the disagreement cases were less frequent. So far, annotators have not being so rigourous when segmenting the text inside features. Therefore, segmentation needs to be checked in both annotations. After this experiment, we are defining the final certified annotation and deriving the annotation guidelines formally.

Discussion

Defining the annotation guidelines for high level semantic representation is controversial. The multiple features that can be represented in the selected MMIL formalism, as well as the multiple instantiations offer different possibilities for representing the same utterance. In general representing spoken utterances is cumbersome, because of the linguist phenomena present in spontaneous speech. As a consequence, annotators have to deal not only with the explicit, but also with the implicit information, and in some cases the representations might be subjective. For these reasons, we defined the standard for the annotation, and based on it, we carried out an annotation experiment on a sample of 330 complex utterances, directly related to the reservation task; involving two annotator profiles i.e., a linguist and a project designer. Afterwards, we measured the similarity between the annotated MMIL components and the inter-annotation agreement obtaining a 98% of similarity and only eight major cases of disagreement, coordination discrepancy being the most frequent. Right now, we are refining the final annotation guidelines based on these results. This first experiment analyzes the most complex and numerous utterances in the corpus covering reservation requests and affirmations. Subsequently, misunderstanding, questions and clarifications will be analyzed following the same methodology. As a result, we will be able to reduce the disagreement between annotators in order to produce the annotation of the whole MEDIA corpus, which will be made freely available to the research community.

Figure 1 :Figure 2 :

 12 Figure 1: Example of a complex utterance of the MEDIA Corpus.

Figure 4 :

 4 Figure 4: Some of the observed dialogue acts and main events with their arguments in the corpus.

  Left: the Table displays the number of utterances by annotator for the listed cases. Annotator 1, is the liguist expert, Annotator 2 is the project designer. Right: fhe Table shows the number of utterances with a completely discrepant annotation: different features for same entities, different values for same features, different relation between same entities and entities related differently in a component.

	Case	Annotator 1	Annotator 2	Case	Discrepancy
	Conjunctions	68	56	Features	4
	Disjunctions	18	10	Features' values	5
	Part. for simple feats.	11	0	Name of relations.	5
	Grouping feats.	0	2	Relation among entities.	2
	Figure 5:

* This work is supported by the French Agence Nationale de la Recherche (ANR) and is part of the Project PORT-MEDIA (www.port-media.org).


Ashwin Rao

Yeon-Sup Lim

Chadi Barakat

Arnaud Legout

Don Towsley

Walid Dabbous

Network Characteristics of Video Streaming Traffic

Keywords: Video streaming 1, Streaming strategies, YouTube, Netflix, Silverlight, HTML5, Flash. Service YouTube Netflix Container Flash HTML5 Flash HD Silverlight Internet

Video streaming represents a large fraction of Internet traffic. Surprisingly, little is known about the network characteristics of this traffic. In this paper, we study the network characteristics of the two most popular video streaming services, Netflix and YouTube. We show that the streaming strategies vary with the type of the application (Web browser or native mobile application), and the type of container (Silverlight, Flash, or HTML5) used for video streaming. In particular, we identify three different streaming strategies that produce traffic patterns from non-ack clocked ON-OFF cycles to bulk TCP transfer. We then present an analytical model to study the potential impact of these streaming strategies on the aggregate traffic and make recommendations accordingly.

INTRODUCTION

The popularity of video streaming has considerably increased in the last decade. Indeed, recent studies have shown that video streaming is responsible for 25-40% of all Internet traffic [START_REF]Global internet phenomena report[END_REF][START_REF] Maier | On Dominant Characteristics of Residential Broadband Internet Traffic[END_REF]. The two dominant sources for video streaming traffic in North America are Netflix and YouTube [START_REF]Global internet phenomena report[END_REF]. YouTube is also the most popular source of video streaming traffic in Europe and Latin America [START_REF]Global internet phenomena report[END_REF][START_REF] Maier | On Dominant Characteristics of Residential Broadband Internet Traffic[END_REF].

Despite this popularity, little is known about the strategies used by YouTube and Netflix to stream their videos. These strategies might have a fundamental impact on the network traffic. TCP is used to transport this traffic, but if this traffic is rate controlled by the application, and this rate is lower than the end-to-end available bandwidth, the traffic characteristics will not be the one of a standard TCP flow. This might have an impact on the network and the traffic coming from other applications. In addition, most of the streaming sessions are interrupted due to lack of interest [START_REF] Finamore | YouTube Everywhere: Impact of Device and Infrastructure Synergies on User Experience[END_REF][START_REF] Gill | Youtube Traffic Characterization: A View From the Edge[END_REF][START_REF] Huang | Can internet video-on-demand be profitable?[END_REF]. Because of this, the streaming strategies may have a significant impact on the network traffic. Indeed, the amount of video downloaded but not watched is an overhead for the network.

In this paper, we present an in depth network traffic analysis of YouTube and Netflix. In particular, we consider the impact of the application (Web browsers and the applications for mobile devices), and the container (Flash [START_REF]Adobe Flash Video File Format Specification[END_REF], HTML5 [START_REF] Hickson | HTML5: A vocabulary and associated APIs for HTML and XHTML[END_REF], Silverlight [4]), on the characteristics of the traffic between the source and the viewer. Then we present a mathematical model to evaluate the impact of the streaming strategy on the aggregate data rate of video streaming traffic. Our contributions are the following:

1)We identify three different streaming strategies with fundamentally different traffic properties ranging from bulk TCP file transfer to non-ack clocked traffic.

2) We detail the network traffic characteristics of the three streaming strategies currently used by YouTube and Netflix.

3)We show that the streaming strategy depends on the application and the container used to stream videos. Therefore, the increased adoption of one could have a significant impact on the network traffic characteristics. For instance, following a massive adoption of HTML5 instead of Flash, or an increase in the usage of mobile applications.

4) We derive a mathematical model to evaluate the impact of the streaming strategies on the stochastic properties of the aggregate video streaming traffic. Our model can be used to dimension the network for video streaming. In particular, it sheds light on the importance of the different video streaming parameters for traffic engineering. For example, we show that an increase in the video encoding rates shall produce smoother aggregate video streaming traffic. We also present the video streaming parameters that can be adapted to minimize the amount of unused bytes on user interruptions due to lack of interest.

The remainder of the paper is organized as follows. In Section 2 we provide an overview of video streaming. We then present the three different streaming strate-1 gies we identified in Section 3. We discuss the datasets and measurement techniques in Section 4. We detail the network characteristics of the streaming strategies used by YouTube and Netflix in Section 5. In Section 6 we present our model and discuss the potential impact of these streaming strategies on the aggregate video streaming traffic. We discuss the related work in Section 7 and present our conclusions in Section 8.

VIDEO STREAMING BACKGROUND

Video streaming enables viewers to start video playback while the content is being downloaded. The two dominant sources for video streaming traffic in the Internet are Netflix and YouTube [START_REF]Global internet phenomena report[END_REF]. Users can view Netflix and YouTube videos either on PCs, using a Web browser, or on mobile devices, using a Web browser or a mobile application. A mobile application is the native Netflix or YouTube application running on mobile devices. In this paper, for the mobile devices, we exclusively consider the native YouTube and Netflix applications for the iOS and Android devices.

YouTube, one of the most popular sites for user generated videos, supports two containers for video streaming, Adobe Flash [START_REF]Adobe Flash Video File Format Specification[END_REF] and HTML5 [START_REF] Hickson | HTML5: A vocabulary and associated APIs for HTML and XHTML[END_REF]. Adobe Flash, henceforth referred to as Flash, is the default container when YouTube is accessed via a PC. Users need to install a proprietary plugin for viewing Flash videos. HTML5 supports videos that do not require any proprietary plugins. HTML5 is the default container when YouTube videos are streamed using the native mobile application for Android and iOS. Recently, YouTube has started supporting High Definition (HD) streaming. The default container for HD videos is Flash.

Netflix uses Microsoft Silverlight [4] to stream videos. As of today, Netflix does not support any other containers for video streaming even though Netflix is leveraging HTML5 for streaming. While streaming to a Web browser requires a Silverlight plugin, the mobile devices require the native Netflix application.

Netflix and YouTube use TCP to stream videos. During a typical streaming session, apart from the video content, the streaming servers send other auxiliary data. For example, the auxiliary data includes details of related videos and advertisements. In this paper, we restrict ourselves to the TCP connections that are used to transfer the video content. We are interested in these TCP connections because these connections contribute to the bulk of the traffic generated by video streaming.

STREAMING STRATEGIES

In this section, we present the three different streaming strategies that we identified using the experiments described in Section 5. Our goal here is to synthesize the main characteristics of those strategies and present some of their advantages and disadvantages.

B u f f e r i n g

Cycle Duration

A v e r a g e r a te d u r in g s te a d y s ta te

S t e a d y S t a t e

Figure 1: Phases of video download. Video streaming begins with a buffering phase followed by a steady state phase. Cycles of ON-OFF periods in the steady state phase are used to limit the download rate.

During a typical streaming session, the video content is transferred in two phases: a buffering phase followed by a steady state phase. During the buffering phase, the data transfer rate is limited by the end-to-end available bandwidth. In Figure 1, the slope of the line during the buffering phase is the end-to-end available bandwidth. The video player begins playback when a sufficient amount of data is available in its buffer. Video playback does not wait for the buffering phase to end.

In the steady state phase, the average download rate is slightly larger than video encoding rate. We call the ratio of the average download rate during the steady state phase and the video encoding rate the accumulation ratio. An accumulation ratio of at least one is desirable because an accumulation ratio lower than one can cause the video playback to interrupt due to empty buffers. An accumulation ratio larger than one implies that the amount of video content present in the players buffer increases during the steady state phase, which improves the resilience to transient network congestion.

The average download rate in the steady state phase is achieved by periodically transferring one block of video content. These periodic transfers produce cycles of ON-OFF periods. During each ON period, a block of data is transferred at the end-to-end available bandwidth that can be used by TCP; the TCP connection is idle during the OFF periods. The slope of the download amount during the ON periods in Figure 1 represents the end-to-end available bandwidth. We call the amount of data transferred in one cycle the block size.

The buffering phase ensures that the player has a sufficient amount of data to compensate for the variance in the end-to-end available bandwidth during video playback. The reduced transfer rate in the steady state phase ensures that the amount of video content does not overwhelm the video player while keeping the amount of buffered data during the buffering phase constant or increasing. The reduced data transfer rate is important for mobile devices which may not be able to store the entire video. We also believe that the reduced rate during the steady state phase reduces the load on the streaming infrastructure. The reduced load can increase the number of videos that can be streamed in parallel.

We use the existence of the steady state phase and the technique used to throttle the data transfer rate in the steady state phase to identify the underlying streaming strategy. We observe the following three streaming strategies for Netflix and YouTube videos.

1) No ON-OFF Cycles. For this streaming strategy, all data is transferred during the buffering phase. As a consequence, we do not observe a steady state phase for this streaming strategy. An advantage of this strategy is that it requires no complex engineering at the server and the client. The video streaming session can be considered as a simple file transfer session. One disadvantage of this strategy is that it can overwhelm the player and cause a large amount of unused bytes if users interrupt the video playback.

2) Short ON-OFF cycles. We define this streaming strategy as the periodic transfer of blocks of size less than 2.5 MB (called an ON period) followed by an idle period (called the OFF period). The goal of this streaming strategy is to maintain an accumulation ratio which is slightly larger than one. This is achieved by a periodic transfer of a block of data followed by an OFF period. An OFF period is observed only when the average data transfer rate is smaller than the end-to-end available bandwidth. We do not observe OFF periods, and short ON-OFF cycles, when the end-to-end available bandwidth is less than or equal to the average data transfer rate. This strategy ensures that the client is not overwhelmed by the amount of data sent by the server.

3) Long ON-OFF cycles. This streaming strategy produces a traffic pattern that resembles the periodic execution of buffering phases following long idle periods. The primary difference between this strategy and the strategy of short ON-OFF cycles is the amount of data transferred in a cycle. The amount of data transferred during the ON periods for this strategy is larger than 2.5 MB. For a given average rate during the steady state phase, the cycle duration for the strategy of long ON-OFF cycles is longer than the cycle duration for the strategy of short ON-OFF cycles. This streaming strategy is a hybrid of the no ON-OFF cycles and short ON-OFF cycles streaming strategies.

METHODOLOGY

We now present the six datasets used in our measurements and the technique used to capture the TCP packets while streaming the videos in each dataset.

Dataset

We first created four datasets of YouTube videos and two datasets of Netflix videos. The YouFlash, YouHtml, YouHD, and YouMob dataset contain YouTube videos while the NetPC and the NetMob dataset contain Netflix videos.

For the YouFlash, YouHD, YouHtml, and YouMob dataset, we respectively searched for Flash videos, HD videos, HTML5 videos, and videos that can be played by the native iOS and Android application. The You-Flash and YouHD datasets respectively contain randomly selected 5000 Flash videos and 2000 HD videos. The YouHtml dataset contains 2500 videos from the YouFlash dataset and 500 videos from the YouHD dataset; these videos can be played using the HTML5 player. For the YouMob dataset, we searched for videos using the native YouTube application on an iPad.

The videos in the YouFlash and YouHD datasets have encoding rates from 0.2 Mbps to 1.5 Mbps, and 0.2 Mbps to 4.8 Mbps respectively. The videos in the YouFlash dataset have a default resolution of either 240p or 360p while videos in the YouHD dataset have a default resolution of 720p. The videos in the You-Flash and YouHD dataset are streamed using Flash as the default container. The encoding rate of videos in the YouHtml and YouMob dataset is from 0.2 Mbps to 2.5 Mbps, 0.2 Mbps to 2.7 Mbps respectively. When using the HTML5 container to stream videos to PCs, YouTube uses 360p as the default resolution; users need to manually switch to a higher resolution such as 720p for viewing the video in HD. As it is currently not possible to view HD videos using HTML5 on PCs without manual intervention, we believe that the fraction of users viewing HD videos using HTML5 on PCs will be small. In this paper, for PCs, we restrict our study to Flash videos played at the default resolution, HD videos streamed using Flash, and HTML5 videos streamed at the default resolution of 360p. We use the default setting because Finamore et al. [START_REF] Finamore | YouTube Everywhere: Impact of Device and Infrastructure Synergies on User Experience[END_REF] observed that users use the default player configuration while streaming YouTube videos. We henceforth refer to videos in the YouFlash dataset as Flash videos, videos in the YouHD dataset as HD videos, and videos in the YouHtml dataset as HTML5 videos.

For Netflix datasets, we collected the list of 11208 videos available for watching instantly as of 20-May-2011. Then, we randomly selected 200 videos from this list for the NetPC dataset. For the NetMob dataset we randomly selected 50 videos from NetPC dataset.

Measurement Technique

We now present the list of software tools used for our measurements. We used Internet Explorer 9 [2], Mozilla Firefox 4.0 [5], and Google Chrome 10.0 [3] (henceforth referred to as Chrome) for streaming videos on PCs. These three browsers have a combined usage share of more than 80% [1]. For Flash videos, we installed the Flash plugin 10.2 in each of these browsers. For Netflix videos, we installed Microsoft Silverlight 4.0.60310. For HTML5 videos, we installed the webM codec in Internet Explorer as YouTube uses webM [7] as the default codec used for HTML5 videos. Firefox and Chrome have a built-in support from webM. We used tcpdump [6] on Linux and windump [8] on Windows to capture the packets exchanged between the web browser and the streaming servers. To study the streaming strategies used for mobile applications, we used an Android (version 2.2) smart-phone and an iPad (iOS version 4.2.1). We used the native YouTube and Netflix applications, developed by YouTube and Netflix respectively for these mobile devices.

We captured the packets exchanged during video streaming in the following manner. When a PC was used for streaming videos, we serially iterated through the list of videos in each dataset and performed the following steps for each video. We first started tcpdump, or windump depending on the operating system, to capture the packets exchanged. We then started a web browser and loaded the URL of a video on the same machine to start the video streaming session. We stopped the streaming session and the packet capture after 180 seconds. For native mobile applications we first started the packet capture on a machine that can access the packets exchanged between the mobile application and the streaming server. We then started the video streaming. We stopped the packet capture and streaming after 180 seconds.

We performed our measurements from the following four locations.

1) A 100 Mbps wired connection connected to the Internet through a 500 Mbps link. We refer to this network as the Research network in the rest of the paper.

2) A 54 Mbps Wi-fi connection behind a ADSL router with typical download rate of 7.7 Mbps and an upload rate of 1.2 Mbps. This network is referred to as the Residence network in the rest of the paper.

3) A 100 Mbps wired connection connected to the Internet through a 1 Gbps link. We refer to this network as the Academic network in the rest of the paper.

4) A 100Mbps wired connection behind a cable modem connected to the Comcast ISP; we observe a typical download rate of 20Mbps and an upload rate of 3Mbps in this network. We refer to this network as the Home network in the rest of the paper.

The Research and the Residence networks are based in France, while the Academic and the Home networks are based in the United States of America. The YouTube measurements were carried out from each of these four locations. The Netflix measurements were carried out only in the Academic and Home networks because Netflix currently does not stream videos to France. For the native mobile applications, the YouTube measurements were carried out in the Research network by using a 54 Mbps Wi-fi connection; the Netflix measurements were carried out using a 54 Mbps Wi-fi connection in the Academic network. The YouTube measurements were carried out from 01-Feb-2011 to 30-May-2011. The Netflix measurements were carried out from 20-May-2011 to 14-Jun-2011.

MEASUREMENT RESULTS

The goal of this section is to present an in depth analysis of YouTube and Netflix traffic and to show that the video streaming traffic generated by YouTube and Netflix can be classified in the three streaming strategies discussed in Section 3.

Table 1 summarizes our finding on the strategies used to stream Netflix and YouTube videos. While using the Flash container, we observed that the applications do not throttle the rate of data transfer; rate control if any is performed by the YouTube servers. Therefore, in Table 1, the streaming strategy is independent of the application used for Flash videos and HD videos. For HTML5 videos, we observed that the YouTube servers do not explicitly control the data transfer rate. Because, the applications use their own techniques to throttle the data transfer rate, we observe that the streaming strategies for HTML5 videos depend on the application used. We observed that Netflix uses short ON-OFF cycles for streaming videos to PCs irrespective of the web browser. However, the streaming strategies differ for the native mobile applications; we observe short ON-OFF cycles for iPad and long ON-OFF cycles for Android.

To characterize the traffic we use three different metrics: the amount downloaded during the buffering phase, the blocks size, and the accumulation ratio. To compute the accumulation ratio we need the encoding rate of the videos. For videos using the Flash container, we obtain the video encoding rate from the header of the video file being streamed. For HTML5 videos, YouTube uses webM as the default codec. During our measurements, we were unable to determine the encoding rate of HTML5 videos because we observed an invalid entry for the frame rate in the header of the webM files. Therefore, we estimate the encoding rate of HTML5 videos by dividing the Content-Length present in the HTTP response by the duration of the video. For Netflix videos, we do not use the accumulation ratio because the encoding rate used by Netflix depends on the end-to-end available bandwidth [START_REF] Akhshabi | An experimental evaluation of rate-adaptation algorithms in adaptive streaming over http[END_REF].

In this section, we first detail the streaming strategies used by YouTube and Netflix in Section 5.1 and Section 5.2 respectively. We then discuss the implications of these strategies in Section 5.3.

YouTube Streaming Strategies

We now detail the buffering phase and the steady state phase of the three streaming strategies used by YouTube.

Short ON-OFF cycles

We observe short ON-OFF cycles for Flash videos regardless of the browser used, and for HTML5 videos when Internet Explorer is used.

In Figure 2, we present a representative trace observed while streaming one Flash video and one HTML5 video; the videos were streamed using Internet Explorer (IE) in the Research network. For both the videos, in Figure 2(a), we observe a buffering phase followed by a steady state phase. During the steady state phase the download amount increments in short steps. We present the evolution of the TCP receive window for the two streaming sessions in Figure 2(b). In this figure we observe that the TCP receive window periodically becomes empty when streaming the HTML5 video. This implies that Internet Explorer throttles the download rate of the HTML5 video by periodically pulling data from the TCP buffers. In Figure 2 serve such explicit rate control by Internet Explorer when streaming the Flash video. This implies that, for the Flash video, the YouTube servers throttle the rate of data transfer by periodically pushing the video content. We observe this behavior for Flash videos regardless of the browser. We do not present the supporting figures due to space constraints.

We now detail the buffering phase and the steady state phase when YouTube videos are streamed using the strategy of short ON-OFF cycles. We use the videos in the YouFlash and YouHtml dataset for these measurements. i) Buffering Phase. In Figure 3(a) we observe that for most of the videos in the YouFlash dataset, YouTube sends approximately 40 seconds worth of playback data during the buffering phase. The playback time is calculated by dividing the amount downloaded during the buffering phase by the video encoding rate. We present the cumulative distribution (CDF) of the playback time in Figure 3(a). The steep slope for the distribution of the playback time is because of the strong correlation (correlation coefficient = 0.85) between the video encoding rate and the amount downloaded during the buffering phase.

For the Residence and the Academic networks, in Figure 3(a), we observe a smaller amount of buffering. The smaller amount could be an artifact of our technique used to measure the amount downloaded during the buffering phase; we consider the start time of the first OFF period as the end of the buffering phase. This technique is sensitive to packet losses and we observed higher packet retransmissions, median of 1.02% and 0.76% respectively, in the Residence network and the Academic network.

For HTML5 videos, in Figure 3(b) we observe that the amount of data downloaded during the buffering phase is not strongly correlated to the video encoding rate (correlation coefficient = 0.41). The results pre- In summary, we observe that the YouTube servers push 40 seconds of playback data during the buffering phase for Flash videos. For HTML5 videos, Internet Explorer typically downloads from 10 MB to 15 MB during the buffering phase. Therefore, the buffering phase for HTML5 videos streamed to Internet Explorer can be more aggressive. For example, for a video encoding rate of 1 Mbps, 10 MB corresponds to 80 seconds of playback time. ii) Steady State Phase. We now show that YouTube servers periodically transfer 64 kB blocks during the steady state phase to attain an accumulation ratio of 1.25 for Flash videos. In Figure 4(a) we present the distribution of the block sizes observed while streaming videos in the YouFlash dataset; we observe that 64 kB is the dominant block size in each network. The smaller block sizes observed in the Residence and Academic networks are because of packet losses that cause TCP retransmission timeouts. We observe block sizes larger than 64 kB when retransmissions due to packet losses merge multiple short ON-OFF cycles to form a larger ON-OFF cycle. In Figure 4(b) we observe an accumulation ratio of approximately 1.25 for the majority of the streaming sessions in each network. For HTML5 on Internet Explorer, in Figure 5(a) we observe that 256 kB is the dominant block size in each network. As in the case of Flash videos, packet losses cause the block sizes to increase or decrease when Internet Explorer is used to stream HTML5 videos. In Figure 5(b) we present the distribution of the accumulation ratio when Internet Explorer is used to stream HTML5 videos. In this figure, we observe a wide range of accumulation ratios. We believe this wide range is an artifact of our technique, or the technique used by the media player, to determine the encoding rate of HTML5 videos. The mean and median accumulation ratio across all the measurements presented in Figure 5(b) is 1.06 and 1.04 respectively.

In summary, Flash videos, and HTML5 videos on Internet Explorer, use short ON-OFF cycles. The dominant block size for Flash videos is 64 kB and it is 256 kB for HTML5 on Internet Explorer.

Long ON-OFF cycles

In Figure 6(a) we present a representative trace for the long ON-OFF cycles. We observe OFF periods in the order of 60 seconds during this measurement which was carried out in the Research network using the Chrome browser. We observe that the TCP receive window periodically becomes empty in Figure 6(a). This shows that Chrome throttles the data transfer rate by periodically pulling large blocks of data resulting in long ON-OFF cycles. We make similar observations when HTML5 videos are streamed using the native YouTube application for Android devices.

We now present our observations on the buffering phase and the steady state phase when long ON-OFF cycles are used to stream YouTube videos; we used the videos in the YouHtml and YouMob dataset for our measurements. i) Buffering Phase. During our measurements we observed that the amount downloaded during the buffering phase by Chrome and Android is independent of the video encoding rate. In each network, we observe a scatter plot similar to the one presented for Internet Explorer in Figure 3(b). We do not present these figures due to lack of space. We observe that while Chrome typically downloads between 10 MB and 15 MB during the buffering phase, the native YouTube application for Android downloads from 4 MB to 8 MB during the buffering phase. ii) Steady State Phase. In Figure 6(b) we present the distribution of the block sizes when long ON-OFF cycles were observed when streaming YouTube videos. In this figure we observe block sizes larger than 2.5 MB for most of the streaming sessions; the measurements carried out in the Research network using Chrome and Android are presented as Rsrch. (Cr), and Rsrch. (And.), respectively in Figure 6(b).

We observe a mean and median accumulation ratio of 1.34 and 1.29 for Chrome, and 1.24 and 1.15 for Android in the Research networks. We do not present these results because we observe a wide range of accumulation ratios. We believe this wide range to be an artifact of our estimation process of the video encoding rate.

In summary, Chrome and Android periodically pull blocks that have a size larger than 2.5 MB to throttle the download rate in the steady state phase.

Combination of ON-OFF Strategies

We now use two videos from the YouMob dataset to show that iPad uses more than one strategy for streaming YouTube videos; we call these two videos Video1 and Video2.

For Video1, in Figure 7(a), we observe periodic buffering followed by short ON-OFF cycles. Further, we observe that 37 different TCP connections were successively used for the data transfer in the first 60 seconds. For each connection, the HTTP GET request contained the range of data requested for a given connection. The amount of data transferred in each TCP connection varied from 64 kB to 8 MB. In comparison, for Video2, we observe short ON-OFF cycles in Figure 7(a); only one TCP connection was used to transfer the video contents.

In Figure 7(b) we observe that the block size used during a streaming session depends on the video encod- ing rate. A given YouTube video may be available in multiple resolutions and the native YouTube application chooses a resolution according to available network and device capabilities [START_REF] Finamore | YouTube Everywhere: Impact of Device and Infrastructure Synergies on User Experience[END_REF]. This implies that streaming strategies for mobile devices with large screens such as the iPad may depend on end-to-end available bandwidth. The measurements presented in Figure 7(b) were carried out in the Research network which has sufficient bandwidth for streaming high resolution videos.

In summary, we observe that the streaming strategy depends on the encoding rate, and the end-to-end available bandwidth, for an iPad.

No ON-OFF Cycles

We observe the streaming strategy of no ON-OFF cycles when neither the server nor the client limit the rate of data transfer. The whole video is downloaded during the buffering phase; such video streaming sessions do not contain a steady state phase. This streaming strategy is observed for the following two cases: HTML5 videos on Firefox, and for Flash HD videos.

In Figure 8 we observe that the download rate for HD videos is not correlated to the encoding rate. We make a similar observation for HTML5 videos on Firefox. The measurements presented in Figure 8 were carried out in the Research network. We made similar observations for the other networks used in our measurements. To ensure that this behavior is not due to a large buffering phase, we selected 50 HD videos and 50 HTML5 videos from the YouHD and YouHtml dataset that have a duration larger than 1200 seconds. For each of these videos, we did not observe a steady state phase during the entire streaming session.

Discussion on ACK Clocks

TCP is an ack-clocked protocol [START_REF] Jacobson | Congestion Avoidance and Control[END_REF]. The ACK clock enables the TCP source to estimate the end-to-end available bandwidth before sending a packet. This estimate is used to determine the size of the TCP congestion window. Allman et al. [START_REF] Allman | RFC5681: TCP Congestion Control[END_REF] suggest that the TCP congestion window be reset after idle periods in the order of a retransmission timeout. This reset ensures that the TCP source does not overwhelm the network with- out probing the end-to-end available bandwidth.

In Figure 9 we present the distribution of the amount of data received during the first round-trip time of the ON periods in the Research Network. This amount is a conservative estimate of the TCP congestion window at the beginning of an ON period. For short ON-OFF cycles we observed OFF periods of duration between 0.2 seconds to 5 seconds while for the long ON-OFF cycles we observed OFF periods up to 80 seconds long. In Figure 9 we observe that the congestion window is not reset after the OFF periods. For example, for Flash videos, we observe that the entire block of 64 kB is sent without probing the end-to-end available bandwidth. The curves in Figure 9 represent the minimum of the TCP congestion window and the block size used during the steady state phase. Because the block size depends on the streaming strategy, and thus the application, we observe different curves for each application in Figure 9.

This observation is important as the absence of an ack-clock can increase the loss rate in the networks.

Netflix Streaming Strategies

We now use one video from the NetPC dataset and one video from the NetMob dataset to provide an overview of the strategies used to stream Netflix videos. Figure 10(a) presents the evolution of the download amount for the first 100 seconds from the beginning of video download. In Figure 10(a) we observe short ON-OFF cycles when Web browsers and the native application for the iPad is used to stream the Netflix videos. In Figure 10(b), we observe long ON-OFF cycles when Netflix videos are viewed using the native mobile application for Android. The measurements presented in Figure 10 were carried out in the Academic Network.

We now use the videos in NetPC and NetMob dataset to study the buffering and steady state phases.

Buffering Phase

In Figure 11, we observe that the amount downloaded during the buffering phase depends on the application, Web browser (for PCs) or the native mobile application. In Figure 11(a), for PCs we observe download amounts in the order of 50 MB; however, for the native iPad application we observe download amounts in the order of 10 MB. We now present a possible reason for this behavior. Each Netflix video is available in different encoding rates. Akhshabi et al. [START_REF] Akhshabi | An experimental evaluation of rate-adaptation algorithms in adaptive streaming over http[END_REF] show that when a Netflix streaming session begins, the video fragments of all the available encoding rates are downloaded during the buffering phase. We hypothesize that the encoding rates for an iPad may be selected from a subset of available encoding rates. In Figure 11(b) we observe that the amount of data downloaded during the buffering phase by the native Android application is in the order of 40 MB. This is significantly larger than what we observe for the native iPad application.

Steady State Phase

In Figure 12(a) and Figure 12(b) we observe that the block sizes used to stream Netflix videos depend on the application, Web browser or the native mobile application. For example, we observe large blocks when Netflix videos are streamed using the native Android application. These large blocks produce long ON-OFF cycles such as those observed in Figure 10(b). For the strategy of short ON-OFF cycles, we observe that the majority of the blocks have a size smaller than 2.5 MB. These blocks are however slightly larger than the 64 kB and 256 kB blocks we observed when short ON-OFF cycles were used to stream YouTube videos.

During our measurements we observed that Netflix uses a large number of TCP connections to transfer the video contents to PCs and the iPad. We are currently not able to speculate the reasons for this behavior. We observed ack-clocks when a new connection was used to send a block of data; we did not observe ack-clocks when a connection was used to send more than one block. We observe ack clocks when Netflix videos are streamed using the native mobile application for Android. We have not presented these results due to lack of space.

Discussion

In this section we detail the network characteristics of YouTube and Netflix traffic and show that strategies used to stream YouTube and Netflix videos depend on the application and the container. For the Flash container, we observe the streaming strategy is independent of the application used. This is because the applications do not control the data transfer rate; rate control, if any, is performed by the YouTube servers. However the YouTube servers do not limit the data transfer rate when streaming HTML5 videos; each application uses its own strategy to stream HTML5 videos. We therefore observe a wide range of patterns for the buffering phase and the steady state phase for HTML5 videos. When Netflix videos are streamed to Web browsers we observe the same streaming strategy regardless of the of the Web browser. However, the strategy is different for the native mobile application for the Android device and the iOS device.

In Table 2 we summarize the difference between the three streaming strategies.

Of the three streaming strategies we identified, the streaming strategies of no ON-OFF cycles is a TCP file transfer. Therefore, we believe that this strategy requires no complex engineering at the application layer. The other two streaming strategies, short ON-OFF cycles and long ON-OFF cycles, explicitly restrict the data transfer rate at the application layer. We therefore believe that engineering is required at the application layer for the strategies of short ON-OFF cycles and long ON-OFF cycles.

The strategies of short ON-OFF cycles and long ON-OFF cycles achieve their goals by restricting the amount downloaded during the buffering phase followed by restricting the data transfer rate according to a desired accumulation ratio. A small accumulation ratio and buffering amount is desirable because it reduces the amount of unused bytes in the buffers of the players. This is also important for mobile devices that may have storage constraints. The amount of unused bytes is also important because recent studies have shown that users tend to interrupt the video download due to lack of interest [START_REF] Finamore | YouTube Everywhere: Impact of Device and Infrastructure Synergies on User Experience[END_REF][START_REF] Gill | Youtube Traffic Characterization: A View From the Edge[END_REF][START_REF] Huang | Can internet video-on-demand be profitable?[END_REF]. The strategies of short ON-OFF cycles and long ON-OFF cycles limit the data transfer rate at the application layer. We show that the traffic characteristics while using these strategies might not be the one of a standard TCP flow. For example, we show the absence of ack-clocks in the TCP connections used to stream Netflix and YouTube videos.

We can therefore conclude that migration from one application to another, or from one container to another, can impact the aggregate video streaming traffic. For example, migration from Flash to HTML5, and increase in the usage of mobile devices are two possibilities that cannot be ruled out. We present a mathematical model to study this impact in the following section.

MODEL FOR AGGREGATE VIDEO TRAFFIC

In Section 5.1 and Section 5.2, we show that the application and the container determine the strategy to stream videos. In this section, we present a mathematical model to express the stochastic properties of the aggregate video streaming traffic as a function of the video parameters. Our model can be used to dimension the network and quantify the impact of migrating from one strategy to another. We first develop our model for the case of users that do not interrupt the video download. We then study the impact of user interruption due to lack of interest on the accumulation ratio and the amount of data downloaded in the buffering phase. We then quantify the amount of bandwidth wasted when users interrupt the video download due to lack of interest.

For our model, we assume that the video streaming sessions arrive according to a homogeneous Poisson process with rate λ. We use the measurements performed by Yu et al. [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF] for the Poisson assumption of the arrival rate 2 . Let T n , n ∈ Z, denote the arrival time of the n-th video. We assume that n-th video is streamed at a fixed encoding rate, e n , and has a fixed duration Table 3: Variables used in the model. Therefore, when users do not interrupt the video downloads, we conclude the following:

1. Equations ( 3) and (4) can be used to dimension the network for video streaming. A simple rule would be to set the bitrate of links carrying video streaming traffic to E[R(t)]+α √ V r , where α ≥ 1 is a constraint on the tolerable bandwidth violations.

2. The mean and variance of the aggregate data rate of video streaming traffic are independent of the underlying streaming strategies used, and hence the required bandwidth. This is important as video services, where the users are expected to view the whole video and not interrupt the video download, can safely select a streaming strategy that can be optimized for other goals such as server load without overwhelming the network.

3. An increase in the video encoding rate, for example when YouTube increases the default video resolution, shall increase the aggregate rate of video traffic. However, because the variance is a linear function of the video encoding rate, the aggregate traffic shall be smoother than the aggregate traffic observed at lower encoding rates.

Video Download with Interruptions

Users can interrupt a streaming session due to various reasons such as poor playback quality or lack of interest in the given video. When a user interrupts the video download due to lack of interest, the data downloaded but not used by the player is wasted. The wastage of network resources can be quantified using the amount of unused bytes. The amount of unused bytes due to lack of interest is important because Gill et al. [START_REF] Gill | Youtube Traffic Characterization: A View From the Edge[END_REF] observe that 80% of the video interruptions in a campus network are due to lack of user interest. According to Finamore et al. [START_REF] Finamore | YouTube Everywhere: Impact of Device and Infrastructure Synergies on User Experience[END_REF], 60% of the YouTube videos are watched for less than 20% of their durations. Similarly, Huang et al. [START_REF] Huang | Can internet video-on-demand be profitable?[END_REF] show that viewing time decreases as the duration of the video increases.

We now present the impact of the buffering amount and the accumulation ratio on the amount of unused bytes. We assume that the user interrupts the download of the n-th video after time τ n from the start of the video playback. We further assume that the amount downloaded in the buffering phase is B n , B n ≥ 0, and the time required for downloading this amount is negligible. If G n is the average download rate in the steady state phase, then the amount of data that can be downloaded up to time τ n is B n + G n τ n . We keep denoting the encoding rate and duration of the n-th video as e n and L n respectively. Thus, the interruption of the n-th video shall take place before the whole video has been downloaded only if

e n L n > B n + G n τ n ≥ e n τ n .
(5)

We now assume the download rate of the n-th video is limited by the accumulation ratio k n =

G n e n , k n ≥ 1. We also assume that τ n = β n L n , where β n , β n < 1, is the fraction of the n-th video watched before interruption. Equation ( 5) can now be written as

e n L n > B n + e n k n β n L n ≥ e n β n L n . (6)
When B n = e n B ′ n , where B ′ n is the amount of playback time buffered in the buffering phase, the left hand side of Equation ( 6) can be written as

B ′ n < L n (1 -k n β n ). (7)
In Section 5.1.1 we observed a buffering of 40 seconds worth of playback, and an accumulation ratio of 1.25 for Flash videos. When a user interrupts the video download after watching 20% of the video, substituting B ′ n = 40 seconds, k n = 1.25, and β = 0.2 yields L n = 53.3 seconds. This implies that, assuming a fast buffering, YouTube Flash videos that have a duration smaller than 53.3 seconds will be downloaded before the viewers have seen 20% of the video.

We now use the amount of unused bytes to obtain the average bandwidth wasted due to user interruption. When the n-th user interrupts the video download at time τ n , then the amount of bytes downloaded is min(B n + G n τ n , e n L n ). The total amount of bytes consumed by the player up to time τ n is e n τ n . Therefore, the amount of unused bytes is min(B n + G n τ n , e n L n )e n τ n , and the average bandwidth wasted is given by

In summary, Equation (7) provides a condition to limit the amount of unused bytes when users interrupt the video download due to lack of interest. Equations ( 8) and ( 9) can be used to compute the amount of bandwidth wasted due to user interruptions.

RELATED WORK

Maier et al. [START_REF] Maier | On Dominant Characteristics of Residential Broadband Internet Traffic[END_REF], and Labovitz et al. [START_REF] Labovitz | Internet inter-domain traffic[END_REF], show that video streaming contributes to 25-40% of all HTTP traffic. Due to its growing popularity, video streaming has received considerable attention in the last few years.

A significant amount of research has been on the video contents characterization on YouTube and on viewing patterns on YouTube. Cha et al. [START_REF] Cha | I Tube, You Tube, Everybody Tubes: Analyzing the Worlds Largest User Generated Content Video System[END_REF] study the popularity of videos and propose caching techniques to enhance the user experience. Zink et al. [START_REF] Zink | Characteristics of youtube network traffic at a campus network -measurements, models, and implications[END_REF] study the viewing patterns in a campus network and suggest proxy caches for enhancing the user experience and reducing the network traffic. Gill et al. [START_REF] Gill | Youtube Traffic Characterization: A View From the Edge[END_REF] study the viewing patterns in a campus network and show that 80% of user interrupts in their campus were due to lack of user interest. Similarly, Finamore et al. [START_REF] Finamore | YouTube Everywhere: Impact of Device and Infrastructure Synergies on User Experience[END_REF] show that 60% of the YouTube videos are watched for less than 20% of their duration.

These works are orthogonal to ours. Indeed, we focus on the network traffic characterization of YouTube and Netflix, not on the content characterization.

Plissonneau et al. [START_REF] Plissonneau | Revisiting web traffic from a DSL provider perspective: the case of YouTube[END_REF], Saxena et al. [START_REF] Saxena | Analyzing video services in web 2.0: a global perspective[END_REF], and Alcock et al. [START_REF] Alcock | Application flow control in youtube video streams[END_REF] observe rate limitations on YouTube traffic. They do not identify the streaming strategies discussed in our paper. Akhshabi et al. [START_REF] Akhshabi | An experimental evaluation of rate-adaptation algorithms in adaptive streaming over http[END_REF] only observed a rate limitation in the steady state phase for Netflix. Saxena et al. [START_REF] Saxena | Analyzing video services in web 2.0: a global perspective[END_REF] show that the YouTube videos streamed using the servers of Google have a buffering phase, whereas the legacy servers of YouTube do not show this buffering phase. Alcock [START_REF] Alcock | Application flow control in youtube video streams[END_REF] only characterized the strategy for short ON-OFF cycles for Flash videos on YouTube.

To the best of our knowledge, we are the first to identify and characterize the three streaming strategies used by YouTube and Netflix. Moreover, we derive a mathematical model to study the aggregate traffic due to video streaming. Therefore, our work enhances significantly previous knowledge on video streaming.

CONCLUSION

In this paper, we present an in depth traffic characterization of Netflix and YouTube. We identify three different streaming strategies with fundamentally different traffic properties. We show that Netflix and YouTube adapt the streaming strategy depending on the application and the container used. This is a concern as it means that a sudden change of application or container in a large population might have a significant impact on the network traffic. Considering the very fast changes in trends this is a real possibility, the most likely being a change from Flash to HTML5 along with an increase in the use of mobile devices.

We derive a model for the aggregate traffic generated by the different streaming strategies. We use this model to show that streaming videos at high resolutions can result in smoother aggregate traffic while at the same time linearly increase the aggregate data rate due to video streaming. We also show how the amount buffered and the accumulation ratio can be adapted considering the user interruptions due to lack of interest.

However, we did not consider the impact of the three different streaming strategies on the network loss rate. We believe that it will have less impact than the wasted bandwidth due to lack of users interest that we studied in this paper. It is anyway a possible area of improvement.

  Short ON-OFF cycles.

Figure 2 :

 2 Figure2: Short ON-OFF cycles. The evolution of the TCP receive window shows that YouTube servers explicitly limit the download rate of Flash videos.

  (b), we do not ob-

Figure 3 :

 3 Figure3: Amount downloaded during the buffering phase. For Flash videos, approximately 40 seconds worth of playback is downloaded in the buffering phase. The buffering amount and the video encoding rate is weakly correlated for HTML5 videos.

Figure 4 :

 4 Figure 4: Steady State for Flash Videos. The server periodically transfers 64 kB of data to attain an accumulation ratio of 1.25 (average download rate in steady state phase is 1.25 times the video encoding rate).

Figure 5 :

 5 Figure 5: Steady State for HTML5 videos on Internet Explorer. A significant number of blocks have a size of 256 kB. A wide range of accumulation ratios is observed while streaming HTML5 videos using Internet Explorer.

Figure 6 :

 6 Figure 6: Long ON-OFF cycles. Long ON-OFF cycles are produced when blocks of large sizes are transferred in the steady state phase. Chrome browser periodically pulls large blocks resulting in long ON-OFF cycles.

Figure 7 :

 7 Figure 7: Different streaming strategies for YouTube videos on iPad.

Figure 9 :

 9 Figure 8: No ON-OFF Cycles.

Figure 10 :

 10 Figure 10: Streaming Strategies used by Netflix. Short ON-OFF cycles for PCs and iPad. Long ON-OFF cycles used for the Android application.

Figure 11 :

 11 Figure 11: Buffering Amount. Netflix transfers multiple copies of the same video content at different encoding rates during the buffering phase.

  Long ON-OFF.

Figure 12 :

 12 Figure 12: Distribution of block sizes for Netflix videos. The block sizes during Netflix streaming sessions depend on the application used.

E

  [R ′ (t)] = λE[min(B n + G n τ n , e n L n ) -e n τ n ]. (8)When the accumulation ratio of the n-th video is k n and the user interrupts the video after viewing β n fraction of the video, then substitutingB n + G n τ n = e n B ′ n + e n L n k n β n in Equation (8) yields E[R ′ (t)] = λE[e n ]E[min(B ′ n + k n β n L n , L n ) -β n L n ].

Table 1 :

 1 Streaming Strategies. Short, Long, and No respectively stand for the strategies of short ON-OFF cycles, long ON-OFF cycles, and no ON-OFF cycles. Streaming strategy depends on the combination of browser and container.

Table 2 :

 2 Comparison of streaming strategies.

	Strategy	No ON-OFF	Long ON-OFF	Short ON-OFF
	Engineering	Not	Explicit support at Ap-
	Complexity	required	plication Layer
	Receive buffer occupancy	Large	Moderate	Small
	Unused bytes on user interruption	Large amount	Moderate amount	Small amount

This is the author version of the paper accepted for publication at ACM

CoNEXT 2011, December 6-9 2011.

Given the fact that users watch the videos in series, it is easy to prove that the Poisson assumption is not needed at the video level. It is enough to have the Poisson assumption at the user level, which is very likely to be the case given the human nature of this activity.

ACKNOWLEDGMENT

The research leading to these results has received funding from the The French National Research Agency (ANR) -Connect project (www.anr-connect.org).

This work was supported by the ARO under grant MURI W911NF-08-1-0233. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied of the ARO.

(length), L n ; the size of the n-th video is S n = e n L n . We also assume that the network is over provisioned: the end-to-end available bandwidth is larger than the video encoding rate for each video streaming session. This hypothesis is validated by our measurements presented in Section 5.1.1. Indeed, for the videos in You-Flash dataset we observed an accumulation ratio larger than one, which implies that the download rate, and hence the end-to-end available bandwidth, is larger than the video encoding rate.

Video Download without Interruptions

We now model the aggregate data rate of video streaming traffic when users do not interrupt the video download. We first examine the strategy of no ON-OFF cycles where the whole video is downloaded at the end-to-end available bandwidth. We assume the time required to download the n-th video is D n . For the nth video, the video download is active at time t when

the download rate of the n-th video at time t; X n (t) = 0 when t < T n and t > T n + D n . Let R(t) denote the aggregate data rate of the video streaming traffic at time t.

According to Barakat et al. [START_REF] Barakat | A flow-based model for internet backbone traffic[END_REF], the mean and variance of the aggregate data rate are:

(1)

respectively When the download rate of the n-th video is a constant G n , substituting D n = S n G n , S n = e n L n , and 1) and (2) yields:

Equations ( 3) and (4) give the mean and variance of the aggregate data rate of video streaming traffic when the strategy of no ON-OFF cycles is used to stream videos. We now show that when users do not interrupt the video download, the mean and variance of the data rate are independent of the streaming strategy used. Let D ′ n (> D n ) denote the time required to download the video when the video contents are downloaded using either the short ON-OFF cycles or the long ON-OFF cycles streaming strategy. For the n-th video, the download rate is G n during the ON periods and 0 in the OFF periods. If the download rate does not change during the data transfer, then Dn 0

which leads to the same variance as in Equation (4). Using the same argument and the framework in Barakat et al. [START_REF] Barakat | A flow-based model for internet backbone traffic[END_REF], one can extend this result to higher moments of the aggregate traffic.