Hadrien Godard

Sourour Elloumi

Amélie Lambert

Jean Maeght

Manuel Ruiz

Novel Approach Towards Global Optimality of Optimal Power Flow Using Quadratic Convex Optimization

Optimal Power Flow (OPF) can be modeled as a nonconvex Quadratically Constrained Quadratic Program (QCQP). Our purpose is to solve OPF to global optimality. To this end, we specialize the Mixed-Integer Quadratic Convex Reformulation method (MIQCR) to (OPF). This is a method in two steps. First, a Semi-Definite Programming (SDP) relaxation of (OPF) is solved. Then the optimal dual variables of this relaxation are used to reformulate OPF into an equivalent new quadratic program, where all the non-convexity is moved to one additional constraint. In the second step, this reformulation is solved within a branch-and-bound algorithm, where at each node a quadratic and convex relaxation of the reformulated problem, obtained by relaxing the non-convex added constraint, is solved. The key point of our approach is that the lower bound at the root node of the branch-and-bound tree is equal to the SDP relaxation value.

We test this method on several OPF cases, from two-bus networks to more-than-a-thousand-buses networks from the MAT-POWER repository. Our first results are very encouraging.

I. INTRODUCTION

The Optimal Power Flow (OPF) problem deals with determining power production at different nodes of an electric network where a production cost is minimized. If we model this network with an AC framework, the optimization problem is quadratic and non-convex [START_REF] Low | Convex relaxation of optimal power flow[END_REF].

(OPF) can be solved with general purpose solvers such as Baron [START_REF] Tawarmalani | Sahinidis A polyhedral branch-and-cut approach to global optimization[END_REF]. A branch-and-bound algorithm specialized to (OPF) has been introduced in [START_REF] Gopalakrishnan | Global optimization of Optimal Power Flow using a branch & bound algorithm[END_REF] using the SDP rank relaxation [START_REF] Lavaei | Zero duality gap in optimal power flow problem[END_REF] as a lower bound provider. More recently [START_REF] Kocuk | Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem[END_REF] introduces an SOCP-based branch-and-bound algorithm.

Our goal is to design a branch-and-bound algorithm that closes the gap between lower and upper bounds. The lower bound is obtained with the rank relaxation and the upper bound is obtained with a feasible point computed, for instance, by an interior point method. It has been already observed that this gap is quite small for (OPF) instances as these lower and upper bounds are very sharp in general [START_REF] Josz | Ac power flow data in matpower and qcqp format: itesla, rte snapshots, and pegase[END_REF].

To this end, we work on a specialization of MIQCR [START_REF] Billionnet | Extending the QCR method to general mixed-integer programs[END_REF], [START_REF] Billionnet | Exact quadratic convex reformulations of mixed-integer quadratically constrained problems[END_REF], [START_REF] Elloumi | Global solution of nonconvex quadratically constrained quadratic programs[END_REF] which is a method designed to solve non-convex and mixed integer quadratic programs to global optimality. MIQCR works in two steps: first a semi-definite relaxation is used to reformulate the problem into another quadratic program. Then this reformulated problem is solved within a branchand-bound framework where at each node a quadratic and convex program is solved to get a local lower bound. A key advantage of this method is that it requires the solution of only one SDP relaxation as a preprocessing step. Then, the 1 R&D Division, RTE (French TSO), Paris La Défense, France 2 CEDRIC, CNAM, 292 rue Saint-Martin, 75003, Paris, France 3 UMA, ENSTA, 828 Boulevard des Marchaux, 91120, Palaiseau, France strength of this SDP lower bound is captured onto quadratic and convex programming. However, the solution of this large SDP is the bottleneck of MIQCR when handling larger instances. The contribution of this paper is a specialization of MIQCR to (OPF) where we prove that we can reach the strengthened lower bound of the MIQCR method by solving a smaller semidefinite relaxation than in the original approach.

In this paper, we adapt method MIQCR to the OPF problem. In Section 2, we recall the formulation of the OPF problem as a quadratic program. In Section 3 we introduce the semidefinite relaxation used in our algorithm, known as the rank (or Shor) relaxation of the OPF problem [START_REF] Lavaei | Zero duality gap in optimal power flow problem[END_REF]. We also give in this section a new proof of the strong duality of the rank relaxation. Then, in Section 4 and in Section 5, we present our contribution: the specialization of MIQCR to solve the OPF problem. In Section 4, we prove that solving a smaller SDP relaxation than in the original MIQCR approach is sufficient to reformulate the OPF problem and to attain the sharp rank relaxation bound at the root node of the branch-and-bound tree. Indeed, solving the dual of the rank relaxation is equivalent to finding the best quadratic reformulation of an OPF problem among the MIQCR family of reformulations. Moreover, in Section 5, we present a branch-and-bound framework to solve the reformulated problem. Finally, in Section 6, we illustrate our method by computational experiments on small and mediumsized instances of OPF problems. Section 7 draws a conclusion.

NOTATIONS

• i is the complex number whose real part is null and imaginary one equals one.

• S m (R) is the set of symmetric matrices on R m . • 0 m is the zero matrix of size m.
• Id m is the identity matrix of size m.

• λ min (M ) is the smallest eigenvalue of a symmetric matrix M . • v(P ) is the optimal value of an optimization problem (P ).

• < A, B > is the canonic scalar product between matrices A and B. • |E| is the cardinal of a set E.

II. A QUADRATIC FORMULATION OF THE OPF PROBLEM

Driving power flows from producers to consumers in an electric network constitutes the OPF problem. Usually the amount of consumed electric power is known at each node of the network. On the contrary the production is unknown and OPF deals with determining its value. The goal is to minimize electric power production costs under the constraint that the demand is satisfied at each node, and that active and reactive powers are box constrained for each production unit. Because real electric transmission networks work with alternative current, one must consider voltage at each node in order to compute where the power flows through the network.

Engineering limits such as bounds on voltage magnitude are also considered as constraints. See the bus injection model in [START_REF] Low | Convex relaxation of optimal power flow[END_REF] for more precisions on this topic.

We only consider a cost linearly linked to the power produced at each unit. Note that a linear cost on the power production handles the case where one tries to minimize losses on the network. The following program is a classic model for the (OPF) problem:

                         min V ∈C n ,P G ∈R n g ,Q G ∈R n g c ′ P G (1) s.t. P G i + iQ G i = V * Y i V, i ∈ N G , (2)
-P D i -iQ D i = V * Y i V, i ∈ N D , (3)
P min i ≤ P G i ≤ P max i , i ∈ N G , (4)
Q min i ≤ Q G i ≤ Q max i , i ∈ N G , ( 5
) (V min i ) 2 ≤ |V i | 2 ≤ (V max i ) 2 , i ∈ N. ( 6
)
Where N is the set of network nodes and n their number. N G , respectively N D , is the set of production, respectively consumption, nodes and n g = |N G |. Variables V are the complex voltages of network buses. Variables P G are the generated active powers at production buses. Variables Q G are the generated reactive powers at production buses. c is the vector of linear costs, where c i is the production cost at node i ∈ N G . Y i is the complex admittance matrix at node i ∈ N . P min and P max are lower and upper bounds on active generated powers. Q min and Q max are lower and upper bounds on reactive generated powers. V min and V max are lower and upper bounds on voltage magnitudes.

The objective function (1) is linear relatively to active produced powers P G . Constraints (2) (resp. (3)) are power balance equations at production (resp. consumption) nodes. Constraints (4), (resp. ( 5)), are bounds on active (resp. reactive), produced powers. Constraints (6) are bounds on voltage magnitudes.

Substituting voltages to other variables, from equations (2), one can see that (OPF) can be modeled as a pure quadratic program, without linear terms, in the real and imaginary parts of voltages.

To simplify the notations, we rewrite the above problem in a more abstract style as the following quadratically constrained quadratic program with 2n variables (OP F ):

(OP F )      min x∈R 2n x t Cx s.t. x t A k x ≤ b k , k ∈ K.
Variables x are the real and imaginary parts of the voltage at each network node. C ∈ S 2n (R). K is the set of constraints indices. At each node there are two constraints that bound the voltage magnitude, and four other constraints that model the complex power balance. Hence, the number of constraints is 6n

. ∀k ∈ K, A k ∈ S 2n (R) and b k ∈ R.
The objective function and the constraints are convex if and only if matrices C and A k are positive semi-definite (PSD) which is not the case for (OP F ).

In this formulation with continuous variables there are no natural lower and upper bounds on variables x. However to perform a spatial branch-and-bound algorithm, initial lower and upper bounds (ℓ and u) on each variable are needed.

To obtain such bounds one can use the fact that the modulus of each complex voltage is upper-bounded. Those upper-bounds are also at the heart of the proofs of Propositions 1 and 2.

Suppose that x i is the real part of the complex voltage at node i, and x i+n its imaginary part. By Constraints (6), we have:

x 2 i + x 2 i+n ≤ (V max i ) 2 . ( 7
)
It follows that:

-V max i ≤ x i ≤ V max i and -V max i ≤ x i+n ≤ V max i .
Below, we take:

ℓ i = ℓ i+n = -V max i , (8)
u i = u i+n = V max i , (9) ℓ
≤ x ≤ u.

III. THE RANK RELAXATION OF OPF

In this section we recall the rank relaxation of (OP F ), that we call (SDP ):

(SDP )          min X∈S2n(R) < C, X > s.t. < A k , X >≤ b k , k ∈ K X 0.
The dual of (SDP ) is:

(DSDP )                max α∈R |K| k∈K -b k α k s.t. C + k∈K α k A k 0, α k ≥ 0, k ∈ K.
where α k is the dual variable associated with constraint k.

Strong duality for feasible OPFs has been already proved (see for instance [START_REF] Josz | Application of polynomial optimization to electricity transmission networks[END_REF]). In this paper, we propose another proof based on the fact that the modulus of each complex voltage is bounded. Parts of this proof will be used later to demonstrate Proposition 2.

Proposition 1: If (OP F ) is feasible, there is no duality gap between (SDP ) and (DSDP ). In other words, strong duality holds for the rank relaxation of feasible OPF problems.

Proof: We first prove that if (OP F ) is feasible then (SDP ) is feasible too. Indeed from each feasible solution x to (OP F ) one can build a feasible solution X = xx t to (SDP ).

Let us now prove that (DSDP ) is strictly feasible, i.e. finding α > 0 satisfying C + k∈K αk A k ≻ 0.

In the following we assume that the elements of K are integers from 1 to |K|, and that the n first elements of K are the indices of voltage magnitude upper-bound constraints [START_REF] Gopalakrishnan | Global optimization of Optimal Power Flow using a branch & bound algorithm[END_REF] on the n network nodes. For k from 1 to n: all entries of A k are zeros except the k-th and (k +n)-th entries of the diagonal, which are equal to 1. It follows that k=1,...,n A k = Id 2n .

For k > n : take αk = 1 > 0. Consider the matrix

C ′ = C + k>n αk A k .
For k from 1 to n : take αk = µ ≥ 1 + max(0, -λ min (C ′ )) > 0.

Then:

C + k∈K αk A k = C + k=1,..,n αk A k + k>n αk A k = C ′ + µId 2n ≻ 0.
As α has positive entries and C + k∈K αk A k ≻ 0, (DSDP ) is strictly feasible.

To sum up, (SDP ) is feasible, (DSDP ) is strictly feasible, so strong duality holds.

We have shown that strong duality holds for the rank relaxation of (OP F ), using the fact that the modulus of each complex voltage is bounded. This is a special case of ball constraints on an optimization problem with complex variables, see [START_REF] Josz | Application of polynomial optimization to electricity transmission networks[END_REF] to get more details on this subject.

(SDP ) relaxation of (OP F ) is known to give a sharp lower bound. We want to point out that we study transmission networks which are not tree networks and are highly meshed. Moreover we do not have a sufficient number of phase-shiftertransformers on network to use results from [START_REF] Sojoudi | Network topologies guaranteeing zero duality gap for optimal power flow problem[END_REF]. Thus rank relaxation does not necessarily lead to an optimal solution.

In the next sections, we present a branch-and-bound algorithm that starts with this sharp lower bound which is based at each node on a quadratic and convex relaxation of (OP F ).

IV. AN EQUIVALENT FORMULATION TO (OP F )

The first step of MIQCR consists in reformulating a QCQP like (OP F ) into an equivalent quadratic problem that has a quadratic and convex objective function, linear constraints, and additional variables Y that are meant to satisfy quadratic constraint Y = xx t .

Let S ∈ S 2n (R) + be a positive semi-definite matrix. We reformulate (OP F ) as:

(OP FS)                min x∈R 2n ,Y ∈S 2n (R) x t Sx+ < C -S, Y > s.t. < A k , Y >≤ b k , k ∈ K Y = xx t , ( 10
) ℓ ≤ x ≤ u.
Observe that the reformulated objective and constraints functions have the same value as the original ones for a same x if Constraints [START_REF] Josz | Application of the Moment-SOS Approach to Global Optimization of the OPF Problem[END_REF] are satisfied. Moreover, the new objective function is convex since matrix S is positive semi-definite. The constraints are now linear, and thus convex. This is why, this reformulation is called a quadratic and convex reformulation.

In (OP F S ) only Constraint ( 10) is non convex. In a way, all the non-convexity has been moved into this constraint.

To solve (OP F S ) to global optimality MIQCR uses a branchand-bound algorithm where, at each node, we relax Constraint [START_REF] Josz | Application of the Moment-SOS Approach to Global Optimization of the OPF Problem[END_REF] and add the linear McCormick inequalities ( 11)-( 14) [START_REF] Mccormick | Computability of global solutions to factorable nonconvex programs: Part I -Convex underestimating problems Mathematical Programming[END_REF] to tighten the relaxation.

Therefore, at the first node of the branch-and-bound, the quadratic and convex relaxation (OP F S ) is solved.

(OP F S )                          min x∈R 2n ,Y ∈S 2n (R) x t Sx+ < C -S, Y > s.t. < A k , Y >≤ b k , k ∈ K Y ij ≤ u j x i + ℓ i x j -ℓ i u j , (i, j) ∈ E (11) Y ij ≤ ℓ j x i + u i x j -u i ℓ j , (i, j) ∈ E (12) Y ij ≥ u j x i + u i x j -u i u j , (i, j) ∈ E (13) Y ij ≥ ℓ j x i + ℓ i x j -ℓ i ℓ j , (i, j) ∈ E. ( 14
)
where ℓ, u are defined as in ( 8) and ( 9) and E = (i, j) ∈ {1, . . . , 2n} 2 : i ≤ j . Notice that in practice, the full variables matrix Y is not considered. Coefficient Y ij is considered if and only if the entry (i, j) is non zero in a matrix among {C, A 1 , . . . , A |K| }.

Every positive semi-definite matrix gives a different reformulation. In the particular case where S = 0 2n , the objective function is linear. It is the linearization of (OP F ). For example the Baron solver [START_REF] Tawarmalani | Sahinidis A polyhedral branch-and-cut approach to global optimization[END_REF] relies on this linearization within a branch-and-bound framework.

We are now interested in finding a "best" matrix S, i.e. a matrix S which gives the largest lower bound at the root node of the branch-and-bound tree. That is to say, a matrix S which maximizes the value of (OP F S ). More formally we want to solve: max

S 0 v(OP F S ).
It is proved in [START_REF] Billionnet | Exact quadratic convex reformulations of mixed-integer quadratically constrained problems[END_REF] that a best matrix S * can be computed from optimal dual variables of a semi-definite relaxation of (OP F ) which is (SDP ) but with additional constraints and variables to raise the McCormick's inequalities.

In this paper, we characterize (SDP ), which does not contain the McCormick inequalities, as the relaxation that can be used to compute a best positive semi-definite matrix. The fact that the McCormick inequalities are redundant in the (SDP ) relaxation is a significant result and is the main difference between Proposition 2 and the result in [START_REF] Billionnet | Exact quadratic convex reformulations of mixed-integer quadratically constrained problems[END_REF]. As a consequence, to reformulate (OP F ), we have to solve a problem with a smaller size than the one solved in the original method MIQCR. Moreover, we prove that the optimal value of this "best" quadratic and convex relaxation is equal to the optimal value of (SDP ).

Proposition 2: Let α * be an optimal solution to (DSDP ), take:

S * = C + k∈K α * k A k ,
If ℓ and u are defined by ( 8) and ( 9) we have:

v(SDP ) = v(max S 0 v(OP F S )) = v(OP F S *
). Proof: For each PSD matrix S, let us introduce the optimization problem:

(LRS)      min x∈R 2n ,Y ∈S 2n (R) x t Sx+ < C -S, Y > s.t. < A k , Y >≤ b k , k ∈ K (LR S )
is the relaxation of (OP F S ) where inequalities ( 11)-( 14) have been dropped. Thus, it is a relaxation of (OP F S ).

The proof is divided in two parts.

• First we prove that:

v(DSDP ) = v(max S 0 v(LR S )) = v(LR S * ).
Let us rewrite the dual of the SDP relaxation by introducing a slack matrix S:

(DSDP )            max S 0,α≥0 k∈K -b k α k s.t. S = C + k∈K α k A k .
For a given S 0, the optimization problem in α is a linear program. We replace it by its LP-dual and obtain the equivalent problem:

     max S 0 min Y < C -S, Y > s.t. < A k , Y >≤ b k , k ∈ K.
Now we can observe that as S is positive semi-definite, one can add x t Sx to the objective function together with variables x. Indeed x will be equal to 0 in any optimal solution. Therefore:

v(DSDP ) = v      max S 0 min x,Y x t Sx+ < C -S, Y > s.t. < A k , Y >≤ b k , k ∈ K.
We have proved:

v(DSDP ) = v(max S 0 v(LR S )) = v(LR S * ).
• Now, in the second part, we prove that:

∀S 0, v(OP F S ) ≤ v(SDP ) ≤ v(OP F S * ).
From the first part, and by Proposition 1, it follows that v(SDP ) = v(LR S * ), and, as (LR S * ) is a relaxation of OP F S * :

v(SDP ) = v(LR S * ) ≤ v(OP F S * ).
Let us now prove that:

∀S 0, v(OP F S ) ≤ v(SDP ).
Let X be a solution to (SDP ). Let us show that (x = 0, Ȳ = X) is a feasible solution to (OP F S ) with a lower objective value.

The inequalities < A k , Ȳ >≤ b k , k ∈ K are trivially satisfied. Let us now prove that ( 11)-( 14) are satisfied. Which amounts to prove:

Xi,j ≤ V max i V max j , (i, j) ∈ E, (15) Xi,j ≥ -V max i V max j , (i, j) ∈ E. ( 16
)
When i = j, as X 0, then for all i ∈ {1, . . . , 2n}, Xi,i ≥ 0. Moreover, from [START_REF] Gopalakrishnan | Global optimization of Optimal Power Flow using a branch & bound algorithm[END_REF]:

∀i ∈ {1, . . . , n} : Xi,i + Xi+n,i+n ≤ (V max i ) 2 .
And therefore:

Xi,i ≤ (V max i ) 2 and Xi+n,i+n ≤ (V max i ) 2 . ( 17
)
When

(i = j), as X 0, Xi,i Xj,j -X2 i,j ≥ 0. From (17), it follows that X2 i,j ≤ (V max i ) 2 (V max j
) 2 . Then ( 15) and ( 16) are satisfied. Let us now compare the objective solution values of X and (x, Ȳ ):

< C, X > -x t S x-< C -S, Ȳ >=< S, X >≥ 0
as S and X are PSD. Therefore (x, Ȳ ) has a lower solution value than X.

To sum up for any PSD matrix S, (OP F S ) has a lower optimal solution value than (SDP ). We can now conclude that v(OP F S * ) = v(SDP ) and that S * maximizes the value of (OP F S ).

Remark 1: In the proof above, we demonstrate that any solution of (SDP ) "satisfies" the McCormick inequalities. This is because bounds ℓ and u were obtained with constraints [START_REF] Gopalakrishnan | Global optimization of Optimal Power Flow using a branch & bound algorithm[END_REF] which are in (SDP ). See Section II.

Remark 2: The optimal matrix S * is not unique, other matrices may give a root node relaxation with the same value.

Proposition 2 ensures that the lower bound obtained at the root node of our branch-and-bound framework is equal to the rank relaxation bound. For many test cases, this bound seems to be very sharp [START_REF] Josz | Ac power flow data in matpower and qcqp format: itesla, rte snapshots, and pegase[END_REF]. To solve (SDP ) and compute S * matrix, one can use the solver introduced in [9], [START_REF] Molzahn | Implementation of a large-scale optimal power flow solver based on semidefinite programming[END_REF].

Those results allow us to build the following algorithm to solve the OPF problem to global optimality:

1) Solve the rank relaxation and deduce optimal dual variables α * . 2) Define the PSD matrix

S * = C + k∈K α * k A k . 3) Solve (OP F S *
) within a branch-and-bound algorithm.

V. SOLUTION WITHIN A BRANCH-AND-BOUND ALGORITHM

In the previous section we showed how to build an "optimal" reformulation of (OP F ) in the sense that it maximizes the lower bound at the root node of our branch-and-bound tree. In this section we describe the second step of the MIQCR method: the solution within a branch-and-bound algorithm. This algorithm is used to solve (OP F S * ) and hence (OP F ).

Let us recall that a branch-and-bound is an enumeration tree used to solve an optimization problem. Each node of the tree represents a sub problem of the original one. There are multiple ways to divide the original problem into sub problems. The classic way is to divide each variable interval into different subintervals, those branch-and-bound algorithms are called spatial branch-and-bound. We choose to implement this type of branch-and-bound, that is why we need bounds ℓ and u on variables x. To sum up, at each node we modify values of ℓ and u to build the sub problem.

A branch-and-bound implementation is defined by:

• Actions performed at each node of the tree,

• Next node selection strategy.

A. How to deal with a node ?

At each node we solve (OP F S * ) where bounds ℓ and u are different. This change modifies the relaxation value since ℓ and u are involved in the McCormick inequalities ( 11)-( 14). We recall that this relaxation is convex and quadratic and that it gives a lower bound of the node subproblem.

Next step depends on the result of the node relaxation:

• If the relaxation is infeasible: the branch is pruned.

• If the lower bound from relaxation is greater than the best current upper bound: the branch is pruned. • If the solution (x, Ȳ ) from the relaxation satisfies constraint (10): x is then a solution of (OP F ), the branch is pruned and the upper bound is potentially updated. • Else: two new nodes are built as children of the current node. About branching: To build two children nodes from a parent node, a branching variable (x b ) and a branching value (x s b ) are chosen.

Variable selection strategy: x b is chosen among variables (i b , j b ) that violate the most Equality (10) (for the Euclidian norm).

Interval division: x s b is chosen between the middle of the current interval of variable x b (denoted x m b ) and xb , the value of x b in the node relaxation solution. Let δ be a parameter between 0 and 1:

x s b = δx b + (1 -α)x m b .
Lower bounds on the local optimal solution value are computed at each node, however we need to find upper bounds and we cannot rely on relaxations results to do so. That is why every three nodes, a heuristic, consisting in finding a point satisfying first order optimality conditions of (OP F ), is launched.

B. How to select the following node ?

At each node is attached a potential which is the lower bound found at its parent node. At this node the relaxation value cannot be lower than this potential.

Our next node selection strategy is designed as a "best-first" strategy. Indeed we want to see the global lower bound of the tree (which is the minimum among the potentials of the leafs in the tree) increase. To do so, we select the node with the lowest potential as the following node to handle.

Branch-and-bound algorithm is terminated when the relative difference between the lowest upper bound (the best feasible solution) and the global lower bound is less than an ǫ-value.

VI. NUMERICAL EXPERIMENTS

To illustrate our method, we present results on a batch of 20 OPF instances involving networks from 2 to 1354 nodes. All these instances come from the MATPOWER repository [START_REF] Zimmerman | MAT-POWER: Steady-State Operations, Planning, and Analysis Tools for Power Systems Research and Education[END_REF], except the "WB" and "LMBM" instances that come from [START_REF] Bukhsh | Local Solutions of the Optimal Power Flow Problem[END_REF].

In our experiments (as in [START_REF] Josz | Ac power flow data in matpower and qcqp format: itesla, rte snapshots, and pegase[END_REF]) we do not consider any constraints on current magnitudes, and we only consider the linear part on the active power cost.

For each instance, we launch our implementation of MIQCR along with the Baron solver [START_REF] Tawarmalani | Sahinidis A polyhedral branch-and-cut approach to global optimization[END_REF], keeping default options.

For MIQCR, the rank relaxation is solved with the Mosek solver [START_REF] Mosek | The MOSEK optimization software[END_REF] and a chordal decomposition to exploit the problem sparsity. The quadratic and convex relaxation at each branchand-bound node is solved with the Xpress [START_REF]Xpress[END_REF] solver. Heuristic performed at each three nodes is based on the solution of the first order optimality conditions of (OP F ) with the Knitro solver [START_REF] Byrd | Knitro: An integrated package for nonlinear optimization[END_REF], [12]. To perform computation we use the following parameters:

Absolute feasible tolerance for the heuristic 10 -5 Final ǫ gap 10 -5 δ parameter to perform branching 0.5

Hence a 0% gap means that the gap is under the ǫ parameter value. The choice of δ = 0.5 came after some numerical experiments along with the reading of [START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF].

Table 1 presents numerical results where each line refers to one OPF test case. In the first column, each instance name contains the number of nodes in the associated electric network. We recall that in (OP F ) the number of real variables is twice the number of nodes. For each solver, the Root gap column gives the relative gap between the best known solution for the instance and the lower bound found at the root node of the branch-and-bound tree, i.e., if the best known solution is denoted by U B and the lower bound by LB, the gap equals UB-LB UB . The Gap-Time column gives the execution time if global optimality is reached within five minutes of computation, if this is not the case, this column gives the relative final gap between the best known solution and the final lower bound.

On small test cases (under 10 nodes) the gap is closed within the branch-and-bound tree by both solvers, except for 9mod instance where MIQCR fails. We observe that the root gap of MIQCR is very tight. This reflects the quality of the SDP rank relaxation lower bound as already observed by several authors [START_REF] Josz | Ac power flow data in matpower and qcqp format: itesla, rte snapshots, and pegase[END_REF], [START_REF] Lavaei | Zero duality gap in optimal power flow problem[END_REF]. On the contrary, the root gap obtained with the Baron solver [START_REF] Tawarmalani | Sahinidis A polyhedral branch-and-cut approach to global optimization[END_REF] is often very large for instances with more than 10 nodes. Moreover its root gap is not improved during the five minutes of branch-and-bound computation.

Notice that a feasible solution is always found for each test case by MIQCR, and may be improved within the branch-andbound. For instance, for case300 first upper bound found equals 475783 and it is improved to 475462.2 during branch-andbound tree iterations.

In [START_REF] Josz | Application of the Moment-SOS Approach to Global Optimization of the OPF Problem[END_REF], authors successfully use the Lasserre hierarchy [START_REF] Lasserre | Convexity in semialgebraic geometry and polynomial optimization[END_REF] to also solve smallest instances of (OPF) problems to global optimality. Although their method can be extended to deal with some well-conditioned larger instances [START_REF] Josz | Application of polynomial optimization to electricity transmission networks[END_REF], [START_REF] Josz | Moment/sum-of-squares hierarchy for complex polynomial optimization[END_REF], it fails with largest generic ones.

VII. CONCLUSION

In this paper we show how to adapt the MIQCR method to the OPF problem. We prove that the well-known rank relaxation is sufficient to build an "optimal" quadratic reformulation of (OP F ). This result can be extended to each quadratic problem with complex variables whose magnitudes are upper-bounded.

When solving this optimal reformulation within a branchand-bound framework, we can close the gap between rank relaxation and known feasible solutions.

First numerical results are encouraging. Future work consists in a specialization of the branch-and-bound framework in order to close the gap by raising the lower bound in larger instances of the OPF problem. To do so we will focus on bound tightening techniques.

TABLE I RESULTS

 I ON 20 OPF TEST CASES, WITH A TIME LIMIT OF 300S


Jeremy Attard
email: jeremy.attard@cpt.univ-mrs.fr

The Dressing Field Method of Gauge Symmetry Reduction: Presentation and Examples

Keywords: Mathematics Subject Classification (2010). Primary 53Z05. Keywords. Gauge theory, Symmetry reduction, Spontaneous symmetry breaking, Higgs mechanism, Twistors

This paper is a presentation of a recent method of gauge symmetry reduction, distinct from the well-known gauge fixing, the bundle reduction theorem or even the Spontaneous Symmetry Breaking Mechanism (SSBM). Given a symmetry group G acting on a fiber bundle and its naturally associated fields (Ehresmann (or Cartan) connection, curvature, etc.) there are situations where it is possible to erase (in whole or in part) the G-action by just reconfiguring these fields, i.e. by making a mere change of field variables in order to get new composite fields on which G (or a subgroup) does not act anymore. Two examples are presented in this paper: the re-interpretation of the BEGHHK (Higgs) mechanism without calling on a SSBM, and the top-down construction of Tractor and Twistor bundles and connections in the framework of conformal Cartan geometry.

Introduction

The fundamental interactions are described in the framework of gauge theories, the geometric content of which is a principal fibre bundle P over a smooth (spacetime) manifold M , with structure Lie group G, together with associated vector bundles E = P × ρ V where ρ is a representation of G on the vector space V. A (classical) matter field is then represented by a section ξ of E, while the interacting bosons fields are connections ω on P , and act on matter fields via the associated covariant derivative Dξ = dξ + ρ(ω)ξ. The curvature associated to a connection ω will be denoted Ω := dω + 1 2 [ω, ω]. These notations will be used throughout the paper.

The central notion of a gauge theory is that of local symmetry. The latter is implemented by the local action of G, i.e. by the action of the (infinite dimensional) gauge group G = {g : M → G}.

Fields ξ and connections ω transform under the action of g ∈ G as ω g = g -1 ωg + g -1 dg and ξ g = ρ(g) -1 ξ. Knowing this, one can then write a physical theory by choosing a functional integral S[ω, ξ] which has the property to be invariant under this action. The theory is said to be gauge invariant. The physical meaning of this feature is that two fields in the same gauge orbit are physically equivalent, i.e. are indistinguishable by any physical experiment. The gauge symmetry is the translation of an intrinsic mathematical redundancy of our formalism.

The description of fundamental interactions on which modern physics is built reduces, then, to the choice of symmetry Lie groups. Electroweak and strong interactions are ruled by the Lie group U (1) × SU (2) × SU (3). Regarding the gravitational interaction, the fundamental symmetry group of General Relativity (GR) is the group of diffeomorphisms of the base manifold.

Let us remark that one can also write GR under the form of a gauge theory 1 , in which is added a local symmetry ruled by the local action of the Lorentz group SO [START_REF] Masson | A remark on the spontaneous symmetry breaking in the standard model[END_REF][START_REF] Attard | Tractors and Twistors from conformal Cartan geometry: a gauge theoretic approach[END_REF]. This can be done in the framework of Cartan geometry.

Although the symmetry group G is central and unavoidable in the construction of a gauge theory, one often needs to reduce its action, i.e. passing to a theory with less symmetry. There can be several reasons for that. For example, for a quantization purpose: the gauge symmetry group produces infinities in the path integral over all fields. Also, e.g. in the case of the electroweak sector of the Standard Model (SM) (G = U (1) × SU (2)), the constraint imposed by the symmetry group is such that mass terms are not allowed, a priori, in the action. Thus, since massive particles are observed, one has to find a way to re-write the same theory but with a smaller symmetry group.

There exists many well-known ways of reducing a symmetry. The simplest is gauge fixing: since all fields in a given gauge orbit are equivalent, one just can choose a particular one -which renders the computations easier, for example; the physical results should be, by definition, independent of the choice of gauge. Another one, which applies in the case of the electroweak sector, as one shall see, is the spontaneous symmetry breaking. In this case, the symmetry reduction is thought as a physical phenomenon, like a phase transition, induced by the fact that the ground state has less symmetry than the theory of which it is a solution.

The recent method of symmetry reduction presented in this paper is called the dressing field method. It is a systematic way of finding, if they exist, new fields which are invariant under the action of the gauge group G or one of its subgroup. This method turns out to be a mere change of field variables. This change is performed with the help of a dressing field u which does not, in general, belong to the gauge group G. Thus, it is neither a gauge transformation nor a gauge fixing: the new field variables, called composite fields, belong in general to representation spaces -for the action of the remaining gauge (sub)group -different than the original variables.

The aim of the present paper is first to present in a nutshell the formalism of the method and then to give two examples of application. The first one is the reinterpretation of the spontaneous symmetry breaking in the electroweak sector of the SM as being a dressing field symmetry reduction. This gives a new physical interpretation to the BEGHHK (Higgs) mechanism. The second one is the reconstruction of Twistors (and Tractors), in the field of conformal geometry, starting from the conformal Cartan geometry and applying the dressing field to erase a part of the conformal group to end up with the transformations found in the usual constructions. This offers a new insight into the geometric nature of these objects. These are examples among many others. The interested reader will find a more complete and detailed presentation of the dressing field method and its applications in [START_REF] Attard | The dressing field method of gauge symmetry reduction: a review with examples Journal of Geometric Method in Modern Physics[END_REF].

The dressing field method in a nutshell

The elements of the gauge group G can also be seen as G-valued fields defined on P . Such an element g is then transformed under the action of another element h as g h = h -1 gh. Let K be a subgroup of G, possibly G itself. A dressing field is a locally defined G-valued field u on P , which transforms under a gauge transformation k ∈ K as u k = k -1 u. Thus, u / ∈ G. The existence of such a field ensures that the following composite fields:

• ω u := u -1 ωu + u -1 du, • Ω u := u -1 Ωu, • ξ u := ρ(u) -1 u,
are then K-gauge invariant as it can be checked by a straightforward computation. The fact that these fields are now K-invariant is interpreted saying that actually, the subgroup K does not act anymore on the fields.

Thus, if one re-writes the theory (i.e. the gauge invariant action S[ω, ξ]) in the new variables, one gets a theory for which the K-symmetry has been erased. It is a mere reconfiguration of the fields which redistributes the degrees of freedom of the theory. The latter are computed as follows: let #TOT, #Φ, #G and #(Θ = 0) be respectively the total number of degrees of freedom, the degrees of freedom related to the fields (ω and ξ) of the theory, the dimension of the symmetry group G, and the number of constraint equations. Then:

#TOT=#Φ-#G-#(Θ = 0).
For example, if the operation of dressing leaves invariant the constraint equations, in the new variables the theory will have less symmetry and then necessarily "less fields", i.e. less degrees of freedom coming from the fields.

Let us present now the two examples announced in the introduction.

3. The Higgs mechanism of the SM as a dressing field reduction.

In the Standard Model, the electroweak sector is governed by the symmetry group G = U (1) × SU (2). The SU (2)-symmetry prevents the action from having mass terms for the weak bosons. Thus, one has to find a way to erase the SU (2)-symmetry. Let us present first the usual version, as developed by many authors in the 60's. Then, one presents another interpretation, developed in [START_REF] Masson | A remark on the spontaneous symmetry breaking in the standard model[END_REF], based on the dressing field method.

Usual Viewpoint

The idea is to suppose the existence of a complex scalar field Φ :

M → C 2 embedded in the potential V (Φ) = -µ 2 Φ † Φ -λ(Φ † Φ) 2
, with λ > 0, which spontaneously gets the value Φ min which minimises the potential V (Φ). This value depends on the form of the potential, i.e. of the sign of µ 2 . For µ 2 > 0, Φ min = 0 and the choice Φ = 0 is unique, and viewed as a point in C 2 , it is still SU (2)-invariant. However, for µ 2 < 0, Φ min = 0, and Φ has to "make a choice" (hence the term spontaneous) between a subset of correponding points in C 2 . It turns out that a particular point is no more SU (2)-invariant, and this phenomenon breaks the symmetry. The scalar field then reads Φ = Φ min +H, and the fluctuation H is interpreted as a particle, the Higgs particle which has been discovered in the LHC in 2012. The constant part Φ min couples with other fields, giving them mass. Thus, the generation of masses in the usual viewpoint is deeply related to the SU (2)-symmetry breaking. One shall see now that it is actually possible to reinterpret the Higgs mecanism without calling on a spontaneous symmetry breaking, but merely by viewing it as a dressing.

SU (2)-erasing without symmetry breaking

Let us take the same initial data as in the usual viewpoint. We are going to show that SU (2) is actually always erasable by a dressing, u, built out of the scalar field Φ.

The first step is to write the polar decomposition of Φ as an element of C 2 : there exists u ∈ SU (2) such that Φ = uη, with η = 0 ||Φ|| , with

||Φ|| 2 := Φ † Φ ∈ R + .
Due to the gauge transformation of Φ under SU (2) (as a scalar doublet), the new variable η is invariant under SU (2), and u transforms as: u → β -1 u, with β ∈ SU (2). Thus, u is a dressing field. From this point, we already know that it is possible to erase the SU (2)-symmetry by dressing, whatever the value of µ 2 is. η = u -1 Φ is the SU (2)-invariant composite field which takes the place of the original scalar field. Now, one can generate masses for the weak fields by making η fluctuating around its value which minimises V (η). For µ 2 > 0, η min = 0 and mass terms are identically zero. For µ 2 < 0, η min = 0, and moreover, there is no more actual "choice": η being a positive real number, V (η) is now a mere onevariable real valued function. Thus, the term "spontaneously" is no more relevant. Writing η = η min + H leads to the same conclusions as in the usual viewpoint.

The only difference is in the physical interpretation: here, one has seen that the generation of masses is totally decorelated from the symmetry breaking. The latter is not seen as a physical phenomenon which historically occured. Rather, the original SU (2)-symmetry appears to be an artefact due to field variables in which the theory is originally written, and can be structurally erased by using new field variables. The dressing field method is a systematic way of finding such new field variables which simplify the theory.

Let us now present another example for which the dressing field method applies: the top-down construction of Twistor (and Tractor) bundles and connections.

Twistors as composite fields from conformal Cartan geometry

The whole construction being technical, one only sketches it. The interested reader is highly recommended to take a look at [START_REF] Attard | Tractors and Twistors from conformal Cartan geometry: a gauge theoretic approach[END_REF] (Tractors) and [START_REF] Attard | Tractors and Twistors from conformal Cartan geometry: a gauge theoretic approach[END_REF] (Twistors).

The usual bottom-up construction

Twistors are for conformal geometry what spinors are for Lorenztian geometry. These objects are usually obtained following a "bottom-up construction" over a conformal manifold (M, [g]), where [g] = {λg, λ ∈ C ∞ (M, R + * )}, for a Lorentzian metric g. As in Penrose's work, for example ( [START_REF] Penrose | Twistor algebra[END_REF], [START_REF]Penrose Twistor quantization and curved space-time[END_REF]), one takes a C 2 -valued field ω B which satisfies the Twistor equation:

∇ AA ω B - 1 2 δ B A ∇ CA ω C = 0
, and then constructs a closed system by introducing another

C 2 -valued field π A := i 2 ∇ CA ω C : • ∇ AA ω B + i 1 2 δ B A π A = 0, • ∇ AA π B -iP AA BB ω B = 0,
with P AA BB corresponding to the Schouten tensor P ab = -1 2 (R ab -1 6 Rg ab ). One then encompasses the whole construction in the new definitions:

• Z α := (ω B , π A ) ∈ C 4 , • ∇ T AA Z α = 0 with ∇ T AA := ∇ AA I 4 + 0 iδ B A -iP AA BB 0 ,
where ∇ T AA is the Twistor connection and Z α is a C 4 -valued Twistor. By construction, these equations are conformally invariant (i.e. well-defined on (M, [g])). Yet, the objects like ∇ T AA and Z α are conformally covariant, and one can compute the corresponding transformation laws under a conformal rescaling of the metric. One can then consider a general Twistor Z α , i.e. an object such that ∇ T AA Z α does not necessarily vanish, and which transforms with the same laws, which are:

Ẑα = I 2 0 iΥ AA I 2 Z α and ∇ T AA Z α = I 2 0 iΥ AA I 2 ∇ T AA Z α under g µν → z 2 g µν , with Υ AA corresponding to Υ a = ∂ a ln(z).
Twistors are thus sections of a vector bundle with fibre C 4 , transforming under the action of a certain group represented by elements of the form I 2 0 iΥ AA I 2

. One now presents another construction which is based on the dressing field method.

A top-down construction via dressing field method

A Cartan geometry over a manifold M is a way of implementing local external symmetries (like Lorentz, projective, ...) in the form of usual internal ones.

It is used to write gravitation theories (i.e. theories in which the geometry of the base manifold is dynamic) in the form of usual gauge theories. From a mathematical point of view, a Cartan geometry expresses a given geometric structure over M into the form a principal bundle endowed with a so-called Cartan connection, slightly different from the usual notion of Ehresmann connection.

For example, the data of a Lorentzian metric on a manifold M is equivalent to the data of a torsionfree Cartan connection over a H-principal bundle, H being the Lorentz group. Following the same idea, a conformal manifold (M, [g]) can be seen as a normal conformal Cartan connection over a H-principal bundle P , with H defined as follows. Let G := SO(2, 4)/(±I) be the conformal group, and M 0 := S 1 × S 3 /Z 2 the conformal compactification of Minkowski spacetime, which is homogeneous with respect to the action of G. The corresponding Lie group H is then the stabilizer of a point of M 0 . One takes then the complex C 4 -representation of these groups. A Twistor should be a section of the associated vector bundle P × H C 4 , where H is the complex representation of H. It turns out that as it stands, the structure does not reproduce the Twistor space and connection, for it does not imply the same transformation law.

To recover it, one has to apply the dressing field method, with dressing fields built out of the conformal Cartan connection. In doing so, one can erase some parts of the original structure group H, and end up with composite fields which transform under a modified transformation law corresponding to the residual action of H. Twistors as previously defined then appear from this construction, with a slight modification: the residual symmetry group does not act (on the composite fields) through a representation of the Weyl group R * + , but via something more complicated called a 1 -α-cocyle, see [START_REF] Attard | Tractors and Twistors from conformal Cartan geometry: a gauge theoretic approach[END_REF], sections 4.2.2.

The fact is that in our procedure, no arbitrary choice is made: one just takes the "rigid" normal conformal Cartan geometry and applies to it the dressing field method. Everything is "already there". One is just playing with objects which naturally belong to the geometry. On the contrary, in the usual construction, some ansatz are taken to simplify the transformation laws, rendering the construction more arbitrary, even if it remains, of course, totally coherent.

Finally, let us remark that the same thing has been done also for Tractors, which appear to be merely the real version of Twistors ([2]).

Conclusion

In this presentation of the dressing field method, it has been shown that it can apply in a quite wide range of different cases. Once one works on a principal bundle equiped with a connection (of Erhesmann or Cartan type), one can try to investigate if it is possible to build a dressing field out of the fields to erase the action of the symmetry group or one of its subgroups. A first hint can be given by counting how are initially distributed the degrees of freedom, and how/if they could be distributed differently. Then, if the answer is positive, one can start to search for a field transforming on the right way to be a dressing field.

More than just giving a way of simplifying the writing of physical theories, it often offers a new insight into some already known constructions. In the case of the SM, it gives a natural and new interpretation of the generation of masses. In the case of Twistors (or even Tractors), it offers a new view of the geometric nature of these objects and of their underlying structure.

In the sense of using a connection on a fibre bundle.

Acknowledgments

This paper stems from a joint work of the author and his colleague Jordan François and his supervisors Serge Lazzarini and Thierry Masson. Many thanks go to Jordan François and Serge Lazzarini for having read this paper and suggested useful corrections.


Antoine Saverimoutou
email: antoine.saverimoutou@orange.com

Bertrand Mathieu
email: bertrand2.mathieu@orange.com

Sandrine Vaton
email: sandrine.vaton@imt-atlantique.fr

Web View: Measuring & Monitoring Representative Information on Websites

Keywords: Web Browsing, Web Monitoring, QoE, QoS

Web browsing is a fast-paced and changing domain which delivers a wide set of services to end-users. While endusers' QoE (Quality of Experience) is the main focus of large service companies and service providers, websites' structure on the one hand change relentlessly. There is therefore a strong need to measure the temporal quality of web browsing by using user-representative web browsers, different Internet protocols and types of residential network access. We present in this paper our tool, Web view, which performs automated desktop web browsing sessions where each measurement provides 61 monitoring parameters. An analysis of 8 Million different measurements of web pages' homepage indicate which and how different parameters can impact today's web browsing quality. Web measurement campaigns conducted since February 2018 are represented through a monitoring website. Our analysis and monitoring of measurements on a 10-month period show that Google Chrome brings increased web browsing quality.

I. INTRODUCTION

Web browsing is the most important Internet service and offering the best experience to end-users is of prime importance. The Web was originally meant to deliver static contents but has dramatically changed to dynamic web pages offering built-in environments for education, video streaming or social networking [START_REF] Ihm | Towards understanding modern web traffic[END_REF]. Content is nowadays served over different Internet protocols, namely HTTP/1.1, HTTP/2 (Version 2 of the HyperText Transfer Protocol) [START_REF] Belshe | Hypertext Transfer Protocol Version 2 (HTTP/2)[END_REF] or QUIC (Quick UDP Internet Connections) [START_REF] Iyengar | QUIC: A UDP-Based Multiplexed and Secure Transport[END_REF] where the latter is paving its way to standardization. Network operators and service providers on the other hand bring along innovative networking architectures and optimized CDN (Content Delivery Networks) to enhance the offered QoS (Quality of Service). Focused at measuring the induced quality when performing web browsing, the W3C (World Wide Web Consortium) and research community have also brought along different web metrics providing information regarding when and what objects are downloaded. Various tools have also been laid out by the research community to measure web browsing quality but are either not embarked with latest updated browsers, cannot execute JavaScript which is nowadays the de facto web technology or collect a limited amount of measurement and monitoring parameters. Wanting to objectively quantify and qualify web browsing, there is a clear need to finely reproduce an enduser environment and habitual actions. Our first contribution in this paper is to present our tool, Web View which performs automated web browsing sessions and collects 61 different quality indicators for every measurement. Our second contribution is to present the different parameters that can increase or decrease web browsing quality upon different browsers. Last but not the least, we present through our monitoring website the temporal evolution of a set of websites and how different residential network access and Internet protocols can leverage web browsing quality. The paper is structured as follows: We first go through in section II the existing web metrics and related work meant to quantify and qualify web browsing, followed by section III which describes our tool, Web View. Through section IV we expose the different parameters that can increase or impact web browsing quality following different web browsers. Section V presents our monitoring website and we finally conclude in section VI.

II. BACKGROUND AND RELATED WORK

Policies and processing algorithms used by web browsers to render web pages are different among them. In order to bring uniform benchmarking indicators, standardization bodies such as the W3C, in collaboration with large service companies have brought along a set of web metrics to better measure web page loading. The Page Load Time1 (PLT) is the time between the start of navigation and when the entire web page has been loaded. The Resource Timing2 provides information upon the downloaded resources unit-wise, such as the transport protocol used, size and type of the downloaded object or some low level networking information. The Paint Timing3 exposes the First Paint (FP) which is the time for a first pixel to appear on the end-user's browser screen since web navigation start. The Above-The-Fold (ATF) [START_REF] Grigorik | Above the fold time: Measuring web page performance visually[END_REF] exposes the time needed to fully load the visible surface area of a web page at first glance. The Speed Index and RUM (Real User Monitoring) expose a score representing the visible surface area occupancy of a web page. The TFVR (Time for Full Visible Rendering) [START_REF] Saverimoutou | Web browsing measurements: An above-the-fold browser-based technique[END_REF] is an ATF browser-based technique which is calculated by making use of the web browser's networking logs and processing time.

To measure QoE during web browsing sessions, several tools have been developed by the research community. FPDetective [START_REF] Acar | Fpdetective: dusting the web for fingerprinters[END_REF] uses a PhantomJS 4 and Chromium based automation insfrastructure, OpenWPM [START_REF] Englehardt | Online tracking: A 1-million-site measurement and analysis[END_REF] performs automated web browsing driven by Selenium5 while supporting stateful and stateless measurements and the Chameleon Crawler6 is a Chromium based crawler used for detecting browser fingerprinting. XRay [START_REF] Lécuyer | Xray: Enhancing the web's transparency with differential correlation[END_REF] and AdFisher run automated personalization detection experiments and Common Crawl7 uses an Apache Nutch based crawler. All these tools (among others) have largely contributed to the research field but when wanting to objectively quantify and qualify web browsing, latest onmarket web browsers, different Internet protocols and network access need to be used. We have thus developed our own tool, Web View (where the root architecture is the same as OpenWPM), which offers fine-grained information through the latest implemented web metrics by different web browsers and data obtained from network capture and web browser's HAR 8 . We also collect information on remote web servers spreaded all over the globe, the downloaded objects' type, size and Internet protocols through which they are downloaded at different stages of the web page loading process.

While some research work [START_REF] Seufert | Studying the impact of HAS qoe factors on the standardized qoe model P.1203[END_REF], [START_REF] Sackl | Quantifying the impact of network bandwidth fluctuations and outages on web qoe[END_REF] provide headlines how to better qualify user-experience, other studies investigate the impact of different Internet protocols on web browsing quality [START_REF] Cook | QUIC: Better For What And For Whom?[END_REF], [START_REF] Ruth | A first look at QUIC in the wild[END_REF], [START_REF] Kakhki | Taking a long look at QUIC: an approach for rigorous evaluation of rapidly evolving transport protocols[END_REF], [START_REF] Zimmermann | How HTTP/2 pushes the web: An empirical study of HTTP/2 server push[END_REF]. Other research studies question the versatility and objectiveness of the PLT to measure end-user's QoE [START_REF] Bocchi | Measuring the quality of experience of web users[END_REF], [START_REF] Kelton | Improving user perceived page load times using gaze[END_REF], [START_REF] Hobfeld | Speed index: Relating the industrial standard for user perceived web performance to web qoe[END_REF], [START_REF] Varvello | EYEORG: A platform for crowdsourcing web quality of experience measurements[END_REF] putting emphasis that what the enduser sees on its screen should be primarily measured. While [START_REF] Varvello | Is the web HTTP/2 yet?[END_REF] presents through a website the evolution of the HTTP/2 protocol in today's Web, to the best of our knowledge, no public monitoring website focused at web browsing quality exists, which we present in this paper. When studying web browsing quality, the induced quality delivered by different web browsers, Internet protocols, network bandwidths and types of websites need to be taken into account.

III. OUR TOOL

Web View9 offers 61 different indicators when performing automated web browsing sessions in graphical or headless mode on unitary or list of websites' main web page. Measurement campaigns can be performed upon a wide set of customizable parameters such as a requested Internet protocol, use of different real on-market web browsers, select a specific device network interface and use different types of ad blockers.

Our tool embarks the Google Chrome browser (v.63 or v.68) and the Mozilla Firefox browser (v.62).

A. What information Web View collects?

Among the different collected parameters, Web View offers networking and web browser's processing time and finegrained information on the different remote web servers serving contents. While Google Chrome supports HTTP/1.1, HTTP/2 and QUIC, the Mozilla Firefox browser does not support the QUIC protocol. Service providers or corporate companies might disable certain Internet protocols in their network and content servers might deliver contents to endusers through a specific Internet protocol; thus increasing the need to study induced web browsing quality following different Internet protocols. When performing automated web browsing sessions, requesting HTTP/1.1 deactivates the HTTP/2 and QUIC protocol in the browser; when requesting HTTP/2, QUIC is deactivated but fallback to HTTP/1.1 is allowed (not all content-servers are HTTP/2-enabled); when requesting QUIC, we allow fallback to HTTP/1.1 and HTTP/2 for non-UDP web servers; when requesting QUIC Repeat, we favor 0-RTT UDP and 1-RTT TCP by firstly performing a navigation to the website, close the browser, clear the resources' cache but keep the DNS (Domain Name System) cache and navigate once more to the website where measurements are collected. The resources' cache is always emptied at the start and end of web browsing sessions and a timeout of 18 seconds is set. The tool collects 4 different loading times for each measurement, namely the FP, TFVR, the processing time and the PLT. Real network traffic is also collected from which is investigated the corresponding DNS time for the main web page domain and through the collected HAR is assessed the overall number of objects downloaded and their MIME (Multipurpose Internet Main Extensions) type. From the exposed remote servers' IP address correlated to MaxMind10 database is identified the continents from which these resources are downloaded (in HTTP or HTTPS), the number of domains serving the contents and the category of the website as referenced by Alexa. As per the different collected timings, which indicate a web page loading progression through time, the number of resources downloaded in these lapses of time are assessed as well as the Internet protocol through which they are delivered.

B. How Web View collects information?

Automated web browsing sessions can be conducted on unitary, a list of pre-defined websites or by indicating the Top N Alexa websites. If an integer N is specified, the Alexa Plugin module automatically retrieves the list of Top N Alexa websites to be assessed. The Test Configuration module verifies the correctness of all the input parameters before starting the measurement campaign. The Test Engine module two-fold purpose is to We present in this section the analysis of 8 Million different measurements 12 collected from 68 different websites (from the Top 50 Alexa websites and 18 additional websites put forth by the ARCEP 13 ) since February 2018. We take into consideration 11 https://grafana.com/ 12 https://webview.orange.com/public/sampleDataset.zip 13 Independent French agency regulating telecommunications in France. A. Which browser should deliver enhanced user-experience? Different benchmarking tools are available in order to define which browser can bring better experience in terms of responsiveness, graphics performance, latency and throughput. As illustrated in Table I, 5 different web browsers have been benchmarked by 10 benchmarking techniques and the browser obtaining the highest score is considered as delivering best user-experience. When assessing the responsiveness of web applications through Speedometer, Google Chrome v.70 wins by delivering increased speed of the DOM APIs, JavaScript engine and CSS style resolution. When assessing graphics performance through MotionMark, Google Chrome v.68 has higher scores (Firefox is slower at image processing and drawing canvas line segments). Through JetStream, Firefox v.64 delivers best latency and throughput scores. Basemark identifies Chrome v.63 as starting up the fastest and using least computing power.

Putting apart web browser versions, the overall benchmarking match between Chrome and Firefox is declared as a 5-5 draw where each assessed web browser functionality can outperform the other through different benchmarking tools.

B. Impact of web browsers on the Page Load Time

Websites are all disparate among them and can be hosted by different web servers all over the globe. Our measurements being made from a fixed location (France), taking into account the main web page geographic location is of prime importance. As depicted in Fig. 1, PLT times range from 216.05 ms to 17859 ms. When the main web page is located in North America less than 25% of the measurements have a PLT less than 2274.2 ms when using Chrome v.63, 3041.7 ms when using Chrome v.68 and 3570.3 ms when using Firefox v.62. Due to increased functionalities of Chrome v.68 versus Chrome v.63, on average 3 more resources are downloaded Among the measured websites, 61.02% are Google websites and when using Chrome, although the resources' cache is emptied, an average number of 3 resources (Google favicon and css) are pre-fetched. When these 3 resources are needed on a web page, Chrome v.68 loads these objects from its cache, reducing its overall networking time.

C. Impact of requested protocol on TFVR

The TFVR which provides the loading time of the visible portion of a web page is correlated to the end-user's browser window size. When performing automated web browsing sessions, four different window sizes are assessed and when a main web page is located in North America, with a window size of 1920x1080, less than 75% of the websites have a visible portion less than 81.26%.

HTTP/1.1 When requesting HTTP/1.1 as shown in Fig. 2a, less than 80% of the websites have a TFVR less than 3301 ms with a Chrome v.63, less than 5600 ms with a Chrome v.68 and less than 7021 ms with a Firefox v.62. While Chrome v.68 downloads on average 3 more resources compared to Chrome v.63, the TFVR is higher. On the other hand, Firefox v.62 downloads 4 more resources compared to Chrome v.68 (no pre-fetching from Google web servers at startup) which increases its processing and networking time. QUIC Repeat When requesting QUIC Repeat through Chrome v.63, for less than 80% of the measured websites, the TFVR is decreased by 25.58% (from 3496.23 ms to 2601.76 ms) compared to requesting the QUIC protocol. This decrease is mainly due to no DNS lookups and non-UDP enabled web servers downloading objects in 1-RTT. On the other hand, Firefox does take advantage of the 1-RTT TCP and the overall networking times are reduced, but the processing times are increased due to the selected window size of 1400x900, where the css-transformed elements take more time to be processed.

Requesting QUIC Repeat favors the download of objects in 0-RTT UDP and 1-RTT TCP. While Chrome brings increased web quality, the Firefox web browser does not support the QUIC protocol and only benefits from 1-RTT TCP.

D. Impact of the network access

Web metrics bring along web page loading times as a whole, composed of networking time (time to download objects from remote content servers) and processing time (time for the corresponding web browser to parse and render elements).

1) Networking time: The Fig. 3 illustrates the overall networking time when a web page is fully loaded through the Chrome v.63 web browser and requesting the HTTP/2 protocol. While main web pages located in North America and Europe take full advantage of the increased bandwidth when moving from ADSL to FIBER, main web pages located in 2) Processing time: The Fig. 4 illustrates the overall processing time when requesting HTTP/2 through Chrome v.63. With the increase in use of JavaScript in web pages' structure, the corresponding network access has a direct impact on the processing time. When objects are downloaded through higher bandwidths, the blocking and waiting time is reduced; downloaded objects can be processed faster. When a main web page is located in North America, the processing time is reduced on average by 26.13% from ADSL to WIFI and by 7.56% from WIFI to FIBER. When a main web page is located in Asia, the processing time reduction is mean when moving from ADSL to WIFI.

The perceived end-user's web browsing quality is tightly linked to the used network access. Increased bandwidth reduces accordingly networking and processing time.

V. MONITORING WEB BROWSING QUALITY

Monitoring websites over long periods of time can shed more light on websites' structure evolution, from which continent objects are downloaded or loading times at different hours of the day. We highlight in this section through our monitoring website, the implications of the requested protocol, network access and used web browser since February 2018 on web browsing quality.

B. Can websites' performance be assessed on the fly?

Through our monitoring website, an end-user can graphically verify on the fly the different loading times of web pages when requesting an Internet protocol following a specific network access. The Fig. 6 illustrates the PLT of the website baidu.com from October 13 to October 23 2018 when requesting HTTP/1.1 through Chrome v.68. From October 13 to October 17 (06H00 UTC), the average PLT is 4516.2 ms and abruptly decreases to 1712.9 ms (decrease of 62.1%) from Fig. 7: Continent-wise downloaded objects for baidu.com October 17 (07H00 UTC) to October 23. Through the different monitoring panels, an end-user can see that the number of downloaded objects or FP stays the same. When scrolling through the other panels, we can see that the processing time decreases accordingly (although the objects' MIME types stay the same). When investigating from which continent the resources are downloaded, depicted in Fig. 7, we can identify that during the period October 13 to October 17, on average 18 objects are downloaded from Asia, but in the period October 18 to October 23, on average 12 objects are downloaded from Europe and 6 objects from Asia. The decrease in PLT (networking and processing time) is thus due to resources being delivered from Europe instead of Asia.

Our monitoring website helps in monitoring a set of websites by assessing the web page loading times, number of objects downloaded, from where objects are downloaded and also helps in troubleshooting end-users' web browsing quality.

VI. CONCLUSION

In this paper we have shown the importance of performing automated web browsing sessions through real on-market different web browsers, use different Internet protocols and user-representative residential network access to bring light on the parameters which can increase or decrease web browsing quality. Our monitoring website helps in monitoring a set of websites and the induced temporal web browsing quality i.e the remote websites' structure evolution, through which Internet protocol the objects are delivered and from where they are downloaded. Among the measured websites, 61.02% are Google websites and when using Google Chrome, an average of 3 resources are pre-fetched on the browser's startup, thus decreasing the overall download time and through benchmarking techniques, Google Chrome is best at graphical rendering and contributes at increased web browsing quality (compared to Mozilla Firefox).

Measurements have been performed in France and an ongoing and future work is to perform measurements from different locations all over the globe. The used web browsers will also be updated to Chrome v.70 and Firefox v.64 and new browsers such as Brave or Safari will be introduced, together with MOS (Mean Opinion Score) studies.

  initialize and collect measurements' data. Upon the selected web browser, the Test Initialization sub-module calls the corresponding web driver, loads the ad blocker standalone if requested and sets the different desired options e.g activating the QUIC protocol, setting the browser window-size, select the corresponding device network interface, etc. The Data Collection sub-module retrieves measurements' data which is then handed to the Data Computation & Interpretation module to perform additional assessment. The Test Execution & Display Module executes the measurement of a specific website through the desired web browser in graphical or headless mode and retrieves the corresponding HAR file. In parallel through a JavaScript, different web browsing embedded metrics (FP, DOM, PLT) exposed by the browser are retrieved and the TFVR is calculated. The Data Computation & Interpretation module then performs further computation on the obtained web browsing results. From the obtained HAR file, information regarding the different remote web servers serving contents is calculated, namely through which protocol is every resource downloaded or the continent from which they are delivered. The Results Visualization module automatically parses collected data to a JSON Grafana 11 format and is uploaded to our monitoring website. The Data Storage module then compresses all measurements which are uploaded to a remote server. IV. MEASURING WEB BROWSING QUALITY Automated web browsing sessions are performed 24/7/365 by five different desktop machines (CPU Intel Core i5 and 8 Go RAM) under Ubuntu 16.0.4 over three different residential network access, i.e ADSL (10Mbps down, 1Mbps up), WIFI (200Mbps down, 160Mbps up) and FIBER (800Mbps down, 300Mbps up). Google Chrome v.63 and v.68 is driven by Chromedriver and Mozilla Firefox v.62 driven by Geckodriver.

Fig. 1 :

 1 Fig. 1: Observed PLT from different web browsers

Fig. 2 :(Fig. 3 :

 23 Fig. 2: TFVR loading time upon requested protocol with window size 1400x900

QUIC

  Fig.2b depicts the TVFR when requesting the QUIC protocol and less than 80% of the websites have a TFVR less than 3496.23 ms with Chrome v.63, less than 4902.87 ms with Chrome v.68 and less than 6915 ms with Firefox v.62. While Chrome v.63 negotiates QUIC version 37-39 and Chrome v.68 negotiates QUIC v.43 with remote UDP-enabled web servers, the Firefox web browser does not support QUIC and a fallback is automatically made to HTTP/2.

Fig. 4 :Fig. 5 :

 45 Fig. 4: Processing time when requesting HTTP/2 through Google Chrome v.63

Fig. 6 :

 6 Fig. 6: Website baidu.com PLT over time

TABLE I :

 I Web browser obtaining highest score provides increased efficiency upon different benchmarking techniques

https://www.w3.org/TR/navigation-timing/

https://www.w3.org/TR/resource-timing-2/

https://www.w3.org/TR/paint-timing/

http://phantomjs.org/

https://www.seleniumhq.org/

https://github.com/ghostwords/chameleon

https://commoncrawl.org/

HTTP Archive

https://webview.orange.com/WebViewArchi

http://www.maxmind.com

ACKNOWLEDGEMENT

This work is partially funded by the French National Research Agency (ANR) BottleNet project, No ANR-15-CE25-0013-001.


Web Browsing Measurements: An Above-The-Fold Browser-Based Technique Antoine Saverimoutou, Bertrand Mathieu Orange Labs Lannion, France Email: {antoine.saverimoutou,bertrand2.mathieu}@orange.com

Sandrine Vaton

Institut Mines Telecom Atlantique Brest, France Email: sandrine.vaton@imt-atlantique.fr Abstract-Web browsing is the most important Internet service, and offering the best performance to end-users is of prime importance. The World Wide Web Consortium (W3C) has brought along the Page Load Time (PLT) metric as a QoE (Quality of Experience) and QoS (Quality of Service) benchmarking indicator, which is nowadays the de facto web metric used by researchers, large service companies and web developers. Although alternative web metrics have been introduced to measure part of the loading process, the techniques used need additional computing power and timings are not offered in real-time. In order to provide real-time fined-grained timings during web browsing measurement campaigns, we present in this paper the TFVR (Time for Full Visual Rendering), a technique being browser-based to calculate the Above-The-Fold (ATF) offering the loading time of the visible portion at first glance of a web page. The TFVR exposes fine-grained timings such as networking and processing time for every downloaded resource. Based on a measurement campaign on top 10,000 Alexa websites, we have been able to better quantify and identify web page loading inefficiencies through a tool we have designed, namely, MORIS (Measuring and Observing Representative Information on webSites).

Keywords-Web metrics, Web browsing, Performance, QoE, QoS

I. INTRODUCTION

Web browsing needs to offer optimal experience during endusers' web navigation process. The Web was originally meant to deliver static contents being mainly texts and images, but evolved drastically towards dynamic web pages, composed of various types of objects (images, scripts, audio, video, etc.) delivered by CDNs (Content Delivery Networks) by a plethora of web servers. Through time proxy-based networking architectures as well as new transport protocols, HTTP/2 [START_REF] Belshe | Hypertext Transfer Protocol Version 2 (HTTP/2)[END_REF] and QUIC (Quick UDP Internet Connections) [START_REF] Iyengar | QUIC: A UDP-Based Multiplexed and Secure Transport[END_REF] have been introduced in the whole process. In order to benchmark QoE and QoS, the W3C has brought along the PLT (Page Load Time). This de facto used web metric by researchers or industries has nevertherless started being put into question lately as it offers overall loading times during web browsing measurements and is inadequate to measure dynamic web pages, particularly when benchmarking QoE. In order to measure web pages' loading, the ATF, SpeedIndex, RUM (Real User Monitoring) or Paint Timing API have been introduced, but there still exists inefficiencies either regarding the techniques used to calculate these metrics limiting real-time measurements or not universely implemented by web browsers. In order to ease the calculation of these aforementioned techniques, we present in this paper an ATF-browser based metric, namely the TFVR (Time for Full Visual Rendering) which measures the needed time to load the visible portion of a web page, being browser and web page type (static or dynamic) independent, calculated in real-time by using the browser's DOM (Document Object Model). Futhermore, through the browser's exposed networking logs, the TFVR offers rich information regarding the DNS, request, response and processing time as an overall timing or in a unit-wise manner for each downloaded and processed resource in this time gap. This paper is structured as follows: We first remind in section II the existing web metrics and related works meant to measure web page load timings. Then we present in section III the identified limits of these web metrics and in section IV we present how the TFVR works, its implementation and how is exposed the rich-information. In section V we expose the results obtained when using the TFVR to benchmark QoE and QoS and finally conclude in section VI.

II. BACKGROUND AND RELATED WORK

Every browser uses distinct processing algorithms and policies to render web pages and standardization bodies such as the W3C or large services companies have brought along a set of web metrics to better qualify and quantify web browsing.

The PLT [START_REF] Wang | Navigation Timing[END_REF] is the time between the start of navigation until the load event (onLoad) kicks in, meaning, as defined, that the web page has been entirely loaded. The Performance Timeline [START_REF] Ilya Grigorik | Performance Timeline[END_REF] provides a unifying interface with Navigation Timing exposing timings regarding web page navigation and load events while the Resource Timing provides information regarding the collected resources such as the protocol used, initiator or networking information (which may be null if a distant server does not provide a Time-Allow-Origin HTTP header). The Paint Timing API [START_REF] Panicker | Paint Timing[END_REF] exposes the First Paint (FP) which is the moment when anything being different prior to the navigation process appears on the screen. The web measurement community and large services companies have brought along the ATF [START_REF] Brutlag | Above the Fold Time: Measuring Web Page Performance Visually[END_REF] exposing the needed time to respectively load the visible surface area of a web page at first glance without scrolling. The Speed Index exposes a score representing the visible surface area occupancy of Previous work on web browsing measurement is mostly dealt at investigating the performance of internet protocols on specific websites, trusting the PLT offered by the browser. Cook and al. [START_REF] Cook | QUIC: Better For What And For Whom?[END_REF] studied the impact of using different internet protocols with regards to network conditions (wifi, ADSL or mobile networks) and measured the perceived QoE. Megyesi and al. [START_REF] Megyesi | How Quick is QUIC?[END_REF] compared the performance of internet protocols, with respect to web pages being different in size and number of objects. Other research work [START_REF] Biswal | Does quic make the web faster?[END_REF], [START_REF] Sackl | Quantifying the impact of network bandwidth fluctuations and outages on web qoe[END_REF], [START_REF] Shade | HTTP/2 Semantics Using The QUIC Transport Protocol[END_REF], [START_REF] Zimmermann | How HTTP/2 pushes the web: An empirical study of HTTP/2 server push[END_REF], [START_REF] Varvello | Is the web http/2 yet?[END_REF] compared the performance of internet protocols and their corresponding adoption rate, looking into the resultant bandwidth and impact of adblockers or advertisements on end-users' QoE. These studies do trust the PLT offered by the browser although websites have been changing their inner structure and only an overall loading time as a whole is offered. But additional studies did start to question the versatility and objectiveness of the PLT to measure end-user's QoE [START_REF] Bocchi | Measuring the quality of experience of web users[END_REF], [START_REF] Kelton | Improving user perceived page load times using gaze[END_REF], [START_REF] Varvello | Eyeorg: A platform for crowdsourcing web quality of experience measurements[END_REF] putting emphasis that what the user really sees should be measured in order to better benchmark QoE and QoS and thus demystify web page abandonment.

III. IDENTIFICATION OF ACTUAL WEB METRICS

INEFFICIENCIES

Automated web measurement campaigns have been conducted over a 4 months period over the top 10,000 Alexa1 websites through a tool, that we have designed, namely MORIS which is a user-orientated measurement tool to better qualify and understand the perceived QoE and QoS. We present in this section the inefficiencies observed from 25 different web pages (each having an average number of 527 measurements) which are static or dynamic, representative of the different types of websites belonging to different categories (e.g News, Recreation, Kids and Teens, Science, Sports, etc.).

A. The Page Load Time

While smartphones, tablets, laptops or desktop screens all come in different sizes, we have been measuring the PLT timings with respect to different screen sizes as per Fig. 1. The Fig. 1a shows the mean PLT of 10 websites over a set of browser window sizes. Fig. 1b on the other end shows that as per the end-user's browser window size and corresponding web page overall surface area, the visible portion (visible surface area at first glance without scrolling) of the website itself increases proportionally. Unfortunately the PLT does not take into account this fact as the web metric is defined to measure the overall loading process. The PLT as measured is constant over time, except some fluctuations due to networking conditions. When trying to measure finely end-user's QoE, the PLT does not evolve as much through the eyes of the end-user.

B. The Above-the-Fold

Through our tool, we have been measuring the ATF, as proposed in the literature, i.e by performing a recording of the web browsing session in different video formats, extracted the screenshots and analyzed the changes in pixels, leading to the visible loading time. We have also implemented the process of ATF estimation by retrieving the screenshots automatically performed by the Google-Chrome browser (since chrome v.60 and exposed through chrome devtools [START_REF] Devtools | [END_REF]) to lift up the burden of making video recordings. An analysis of these two methods did bring some irregularities:

Processing time: To detect accurately the pixels change from screenshots, the higher the video quality illustrating the loading process, the more accurate the pixels' comparison will be, which firstly requires external tools for video recording ATF under and over estimation: The estimation process needs to firstly classify pixels as being static or dynamic ones in order to obtain the ATF cut-off [START_REF] Brutlag | Above the Fold Time: Measuring Web Page Performance Visually[END_REF], which may be subjective on the long run and dependent on the quality of the screenshots.

Types of web pages: Web pages on the other hand can be static or dynamic. Fig. 2 depicts the mean web page loading times through a Google-Chrome browser with window size 1920x1080, where Fig. 2c (namely w3schools.com) represents a static website mainly composed of texts and static images and Fig. 2a and 2b dynamic websites. We compared the ATF estimated timings obtained by comparing screenshots from video (frame rate 30 and libx264 codec) and screenshots retrieved from the chrome devtools which bring along close estimations. As per Fig. 2c, where all events are fired before the onLoad event, the ATF estimation represents in the case of using an adblocker 63% of the PLT and 76% of the overall web page is visible at first glance to the end-user. The Fig. 2a (namely youtube.com) represents a dynamic web page where all events are fired before the onLoad event, composed of texts, images and scripts. When retrieving screenshots from chrome devtools, we simply take into consideration the onLoad event exposed by the browser but in the case of extracting screenshots from a video, 45 seconds of additional video was taken due to the presence of dynamic advertising fields. The Fig. 2b (namely forgeofempires.com) represents a dynamic web page where events are fired after the onLoad event, with a permanent web page visible portion of 100%.

While the exposed browser-PLT is 700 ms, this timing only exposes the time needed to download a main asynchronous javascript (identified through the browser's HTTP Archive).

C. The Real User Monitoring

The RUM main aim is to calculate the SpeedIndex but can also be used for the ATF estimation by making use of the browser-exposed DOM information. During our measurement campaign, we have also used the RUM and in the case where we had static websites or dynamic websites having all events fired before the onLoad event, the estimations only had an average difference of 10% compared to the classical ATF estimation technique. But the RUM uses the Resource Timing API (resources downloaded in the PLT gap time) to identify the list of resources to be looked into the DOM information and in the case that events are fired after the onLoad event, the estimation is totally innacurate. When performing web browsing measurements for ryanair.com, the RUM exposes an ATF estimation of 400 ms for the web page, not taking into account resources downloaded after the onLoad event and rendered in the visible portion of the web page.

IV. TFVR: TIME FOR FULL VISUAL RENDERING

We present in this section how our proposed technique yields more representative timings and its implementation details. To calculate the TFVR, our tool through Selenium [18] drives real on-market browsers where a simple javascript code is sent to the browser's command line during a web browsing session. We first retrieve the FP timing, indicating the starting time of the visible rendering process. We then calculate in real-time on-the-fly the visible portion of the web page as per the end-user's browser window size (innerWidth and innerHeight) versus the web page scrollable size (scrollWidth and scrollHeight) which represents the surface area where all objects are to be visually rendered. The entire list of resources downloaded during the navigation session for the web page is obtained from the browser's networking logs netmonitor.har for the Mozilla-Firefox browser taking into consideration all events fired before and after the onLoad event (we purposely do not use the Resource Timing API which only exposes events loaded before the onLoad). The main web page code is then parsed to retrieve the needed resources on the webpage (since resources may also be downloaded for further navigation process being stored in the browser's cache and unnecessary on the first instance [START_REF] Wang | Demystifying page load performance with wprof[END_REF]). We then retrieve the DOM browser-exposed information through getElementsByTagName(" * "). By crossmatching the resources' uri from the networking logs and web page code, we obtain a precise list of resources to be rendered by the browser for the entire web page.

Images Each object to be painted is referenced with its url name baseURI, width (innerWidth), height (innerHeight) and (x,y) coordinates through offsetTop and offsetWidth. The coordinates together with the object width and height brings along a rectangle which can be assessed if being in the visible surface area. We thus obtain through time the rendering times for each resource to be displayed in the visible portion of the browser window. Texts and scripts These resources are not rendered visually, so we retrieve their processing time through the devtools Performance tab where each resource is referenced by its url name baseURI. By adding this processing time information to exposed network logs offered by the browser, we obtain the neworking and processing time for all the resources needed to render the visible portion of the web page. The TFVR calculation process only represents a mean extra computational time of 0,156 seconds and processing time of 0,014%. The TFVR calculation is totally opaque to the end-user and has no incidence on the web browsing measurement process since no external tool or storage capabilities is needed. Furthermore, the TFVR provides networking time as well as processing time for each resource thus improving QoE and QoS benchmarking and allows troubleshooting.

V. RESULTS

We expose in this section the results covering 47,291 measurements representing automated web browsing of 25 distinct websites through our tool MORIS in headless mode, where all cookies are deleted and cache emptied at the start of every measurement. These web browsing measurements have been conducted in Lannion (France) all day round, with or without adblocker (Adblock Plus v3.27), with different window sizes (360x640, 962x620, 1600x900 and 1920x1080), using HTTP/1.1, HTTP/2 or QUIC protocol, different network access (ADSL, Wifi and Fiber), collected by three different machines with Intel Core i5 and 8Go RAM. Our tool MORIS written in python is driven by chromedriver2 v2.37, geckodriver3 v0.19, Chrome v64, Firefox v58 and Selenium v3.4.

A. The TFVR

The Fig. 3 and4 represent the web browsing loading times for youtube.com and forgeofempires.com made with the Google-Chrome browser, window size 962x901, using Ad-Block Plus, preferred internet protocol being QUIC (fallback to HTTP/1.1 or HTTP/2 is allowed if a distant host can not reply in QUIC) and fiber network access (96,7Mb/s down, 84,9Mb/s up). Events before onLoad. As depicted in Fig. 3, the PLT covers all events triggered before the onLoad event, and the FP is 909,2 ms where 10 resources (1 html, 2 css, 1 xml and 6 images) are downloaded in this time interval. An end-user sees at first glance without scrolling the web page 47% of its contents which is visually rendered in 770,6 ms (17 resources Events after onLoad. As depicted in Fig. 4, the PLT offered by the browser is not representative since the PLT is exposed as being 1915 ms, where 4 resources compose the FP of 200,7 ms (1 html, 1 css, 1 xml and 1 javascript). The javascript downloads 3 more resources in the FP-PLT lapse of time (1 image and 2 asynchronous javascripts) and these asynchronous javascripts are fired after the onLoad event. By comparing the network logs from devtools, we easily identify that more resources are needed by the browser so that visible portion of the website is rendered. In this case, the PLT is 43,9% short and does not take into consideration the additional download of 290 resources (networking time of 938,6 ms and processing time of 562,2 ms) needed to fully render the visible portion of the website. Through our measurements, we could easily identify other websites (e.g adidas.co.uk, ryanair.com, blog.me, etc.) where the PLT timing is inacurate and where the TFVR provides representative timings.

B. Internet protocols distribution

When performing web browsing measurements, it is important to take into account the internet protocols being used since some large service companies firewalls or network operators do block some internet protocols (e.g QUIC on UDP). We have thus conducted experiments based on HTTP/1.1 (deactivating HTTP/2 and QUIC), HTTP/2 (deactiving QUIC) and QUIC, by allowing a fallback to a subsequent internet protocol if a distant content server can not dialogue in a specific protocol (e.g activating QUIC allows a fallback to HTTP/2 and HTTP/1.1). Fig. 5 shows the internet protocols through which the resources are downloaded on Google-Chrome when calculating the TFVR and PLT for the website android.com with a wifi network access (15,7Mb/s down, 1.1Mb/s up). The Fig. 5a shows the internet protocols through which the resources are delivered during the TFVR time lapse and further helps to understand the obtained timings when multiplexing, pipelining of the resources or delivery through TCP or UDP happen. The Fig. 5b shows as a whole the resources delivery through specific internet protocol during the PLT lapse of time. We have also been able to identify through the TFVR timings that following the end-user's network access (namely fiber access), extra resources can be downloaded by the browser, stored in the cache for further web browsing on the same domain.

C. Impact of internet protocols on QoE

When measuring the QoE of end-users, it is important to be able to detect bottlenecks during web page loading. As depicted in Fig. 6 the preferred internet protocol has an impact on the end-user's QoE. This measurement has been performed on the website facenama.com with an ADSL network access (20,1Mb/s down,2,7Mb/s up), involving 529 distinct measurements (after removing the 5 th and 95 th percentile). When taking the average TFVR (Fig. 6a) into consideration, the offered timing is 2252,4 ms (when preferred protocol QUIC, 1% H1, 2% H2 and 47% HQ for the 35 downloaded resources) and the mean PLT (Fig. 6b) is 8264,6 ms (when preffered protocol is QUIC, 10% H1, 4.29% H2 and 85,71% HQ for the 70 downloaded resources) with window size 1600x900. The contents are delivered over 5 different content servers (with same authoritative servers) located in Asia, and allows QUIC to perform better due to a 1-RTT (First requests are always performed in HTTP/2). Thanks to the TFVR, offering networking and processing timings for each resource, we can easily identify the bottleneck in this case which is two resources (advertisements) delivered over HTTP/1.1 with a DNS and response time of 1200 ms and processing time of 120 ms, thus having a mean FP of 1800 ms.

D. Browsers

When performing measurements on the Google-Chrome browser, at the launch of the browser itself, mandatory resources needed by Google services are downloaded before the navigation start. When performing our measurements on the website google.com or youtube.com we could identify from browser's networking logs that an average number of 5 resources were loaded from the browser's cache. The TFVR helps to identify these situations where a comparison between the number of resources needed to render a web page might be totally different when using different web browsers. This behavior has also been identified with Mozilla-Firefox when accessing Mozilla services, which confirm that each browser has a different policy when delivering contents to end-users. In order to be representative in our exposed timings, these resources downloaded by the browser before the navigation start are also exposed as having a processing time but no networking time.

VI. CONCLUSION

In this paper, we have highlighed the importance of measuring web browsing sessions as per what an end-user sees at first glance on a web page without scrolling. We have also presented a measurement technique which is browserbased, offering timings in real-time as per real on-market browsers, and take advantage of the rich-information exposed by the browser itself. The TFVR as opposed to actual ATF measurement techniques offers representative timings as a whole regarding the visible web page loading process but also exposes fine-grained information regarding the networking and processing times of every downloaded resource. The TFVR also helps in identifying any bottleneck during the loading process as we also expose network timings. Our future work will be dealt in making the TFVR calculation available through a plugin for Chrome and Firefox browser and we will be performing additional web browsing measurement campaigns at different geographic locations to better investigate endusers' QoE and QoS.

  Fig. 1: PLT vs Browser window sizes

Fig. 2 :

 2 Fig. 2: ATF vs PLT

Fig. 3 :

 3 Fig. 3: TFVR for youtube.com

Fig. 4 :

 4 Fig. 4: TFVR for forgeofempires.com

Fig. 5 :

 5 Fig. 5: Protocol distribution android.com

Fig. 6 :

 6 Fig. 6: Measurements facenama.com

https://www.alexa.com/

https://sites.google.com/a/chromium.org/chromedriver/

https://github.com/mozilla/geckodriver

ACKNOWLEDGEMENT

This work is partially funded by the French ANR BottleNet project, No ANR-15-CE25-0013-001.