Keywords: Coevolutionary algorithms, bilevel optimization, algorithm design and implementation, parallel algorithm, vehicule routing problem Agorithmes co-évolutionnaires, optimisation bi-niveau, conception et implémentation d'algorithme, algorithme parallèle, problème de tournées de véhicules

This article presents CoBRA, a new parallel coevolutionary algorithm for bi-level optimization. CoBRA is based on a coevolutionary scheme to solve bi-level optimization problems. It handles population-based metaheuristics on each level, each one cooperating with the other to provide solutions for the overall problem. Moreover, in order to evaluate the relevance of CoBRA against more classical approaches, a new performance assessment methodology, based on rationality, is introduced. An experimental analysis is conducted on a bi-level distribution planning problem, where multiple manufacturing plants deliver items to depots, and where a distribution company controls several depots and distributes items from depots to retailers. The experimental results reveal significant enhancements with respect to a more classical approach, based on a hierarchical scheme.

Introduction

Bi-level optimization problems allow to model a large number of real-life applications, with a hierarchical structure between two decision makers. It includes companies which have to face a legislator and security constraints [START_REF] Erkut | Solving the hazmat transport network design problem[END_REF], companies trying to predict consumer reaction [START_REF] Didi-Biha | Path-based formulations of a bilevel toll setting problem[END_REF], or a supply chain where a company has to predict its supplier reaction to determine the real cost of its decision [START_REF] Calvete | A Multiobjective Bilevel Program for Production-Distribution Planning in a Supply Chain[END_REF].

Meta-heuristics are a class of approximate algorithms focusing on finding good-quality solutions for large-size and complex problems, in a reasonable time [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF]. While most of the existing literature about bi-level optimization focuses on small-size linear problems (see for example [START_REF] Anandalingam | A solution method for the linear static stackelberg problem using penalty functions[END_REF][START_REF] Eichfelder | Multiobjective bilevel optimization[END_REF]), many real-life applications involve large-size instances and complex NP-hard problems, justifying the use of meta-heuristics. Meta-heuristics for bi-level optimization can be divided in two main classes. On the one hand, hierarchical algorithms try to solve the two levels sequentially, improving solutions on each level to get a good overall solution on both levels. Such algorithms include the repairing algorithm [START_REF] Koh | Solving transportation bi-level programs with differential evolution[END_REF], which considers the lower-level problem as a constraint and solve it during the evaluation step, or the constructing algorithm [START_REF] Li | A hierarchical particle swarm optimization for solving bilevel programming problems[END_REF] which applies two improving algorithms on a population, one for each level, sequentially until meeting a stopping criterion. On the other hand, coevolutionary algorithms maintain two populations, one for each level, and try to improve it separately, while exchanging periodically information to keep an overall view on the problem, like in [START_REF] Oduguwa | Bi-level optimisation using genetic algorithm[END_REF]. In cooperative coevolution, different sub-populations evolve a part of the decision variables, and complete solutions are built by means of a cooperative exchange of individuals from sub-populations [START_REF] Potter | Cooperative coevolution: An architecture for evolving coadapted subcomponents[END_REF].

This article focuses on a coevolutionary approach. Sub-problems involved in bi-level optimization can be tackled by meta-heuristics. Finding a good way to combine two meta-heuristics in order to solve a bi-level optimization problem would give a general methodology for bi-level optimization. First, we introduce a new algorithm, the Coevolutionary B i-level method using Repeated Algorithms (CoBRA). This coevolutionary meta-heuristic is able to face general bi-level optimization problems, possibly involving complex large-size problems. Next, we introduce a new method for performance assessment, the rationality, able to more fully grasp the bi-level aspect of the problems than the Pareto efficiency. Rationality is based on the proximity from the optimum of the lower-level variables with the corresponding upper-level variables fixed. At last, to evaluate the performance of CoBRA against classical hierarchical approaches, we give an experimental analysis on a bi-level transportation problem involving a supply chain, the bi-level multiple depot vehicle problem introduced in [START_REF] Calvete | A Multiobjective Bilevel Program for Production-Distribution Planning in a Supply Chain[END_REF]. This analysis includes the modeling of the problem, the instantiation of CoBRA on it and the study of the results with respect to the rationality metrics.

The paper is organized as follows. Section 2 gives the necessary background on bi-level optimization. Section 3 presents the new coevolutionary algorithm proposed in the paper for bi-level optimization, namely CoBRA. In Section 4, we discuss the issue of assessing the performance of approximate algorithms in bi-level optimization. The bi-level transportation problem under investigation in this paper is presented in Section 5, both in a single-objective and a multiobjective formulation. The experimental analysis of CoBRA is given Section 6. At last, the final section concludes the paper and gives directions for further research.

INRIA 2 Bi-level Optimization

In this section we introduce a general bi-level optimization problem, and give a quick overview of state-of-the-art meta-heuristics for bi-level optimization.

General Principles of Bi-level Optimization

Bi-level optimization problems may be defined by the tuple (S, F, f ) where S represents the set of feasible solutions, F the objective function(s) of the upperlevel, and f the objective function(s) of the lower-level. For any x ∈ S we separate the upper-level variables and the lower-level variables, respectively in x u and x l .

We define, for every x u fixed, the set of rational reactions R(x u ) as the set of x l optimal in f .

R(S, f, x u ) = min x l f (x = (x u , x l )) = (f 1 (x), f 2 (x), . . . , f n (x)) s.t. x ∈ S
The bi-level problem consist in finding the solution x ∈ S which is optimal with respect to f for x u fixed and, respecting this constraint, optimal in F .

BP (S, F, f) =        min F(x) x ∈ S s.t. x = (x u , x l ) x l ∈ R(S, f, x u )
Those problems induce a hierarchy between two decision makers:

The leader, who chooses the upper part of the decision variables, x u , and who tries to optimize F (x).

The follower, who chooses the lower part of the decision variables, x l , and who tries to optimize f (x).

The leader decides first. Then, the follower, knowing the leader decision, has to decide, in the view of optimizing its own objective function(s) f , without regarding the upper objective function(s) F . To optimize his choice, the leader then has to predict the follower reaction. This hierarchy can conduct to a higher complexity than both sub-problems. For instance, a NP-hard problem can be obtained from two linear problems [START_REF] Ben-Ayed | Computational difficulties of bilevel linear programming[END_REF]. This definition of bi-level optimization corresponds to the optimistic case, where the leader can "choose" the (x u , x l ) couple in the set of (x u , x l ) ∈ S where x l ∈ R(x u ): the reaction has to be optimal, but if several reactions are optima (i.e. |R(x u )| > 1) the leader has the last word. There exists a pessimistic case [START_REF] Loridan | Weak via strong stackelberg problem: New results[END_REF] which is not treated in this paper, where x l is chosen as the leader worst case scenario in the set of rational responses.

Meta-heuristic Approaches for Bi-level Optimization

Meta-heuristics are approximate algorithms which allow to tackle large-size problem instances by delivering satisfactory solutions in reasonable time [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF]. Due to their complexity, most bi-level optimization problems are tackled by approaches which involve a model reformulation masking the bi-level aspect of the problem (see [START_REF] Anandalingam | A solution method for the linear static stackelberg problem using penalty functions[END_REF][START_REF] Eichfelder | Multiobjective bilevel optimization[END_REF][START_REF] Fliege | Multicriteria approach to bilevel optimization[END_REF][START_REF] Lv | A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming[END_REF]), or involve meta-heuristics. Evolutionary algorithms are meta-heuristics mimicking the species evolution. We will use in this article several terms related to evolutionary algorithms: an individual is a feasible solution, a population is a set of individuals, a mutation is the creation of a new individual from an existing one, generally keeping some properties. A cross-over is the creation of individual(s), called offspring, from several other individuals called parents. The process of applying cross-over and mutation operators to a population in order to create a new population is called generation. On each generation, a selection step consists in selecting individuals to meet defined goals. Evolutionary algorithms consist in creating multiple generations and applying selections until a stopping criterion is met (Fig. 1). The reader is referred to [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF] for more details about population-based meta-heuristics and evolutionary algorithms.

In this paper, we focus on coevolutionary approaches, a sub-group of metaheuristics extending the evolutionary scheme. Coevolutionary algorithms consists in associating several evolutionary algorithms and applying transformations, such as mutation and cross-over, to distinct populations. A coevolution operator is then regularly applied between sub-populations to keep a global view on the whole problem. Oduguwa and Roy described BiGA [START_REF] Oduguwa | Bi-level optimisation using genetic algorithm[END_REF], a coevolutionary algorithm to solve bi-level problems.

BiGA starts by initializing two distinct sub-populations using a heuristic, pop u for the upper level and pop l for the lower, then the upper part of the solutions is copied from pop u to pop l . Then during a parametrized number of generations, a selection process based on the respective level fitness values is applied on both sub-populations, followed by a mutation/crossover step. Then the sub-populations are evaluated, sorted, and coevolved, by copying the upper (resp. lower) variables to the lower (resp. upper) sub-population. At last, an archiving process occurs, before looping again to the selection step. The pseudo-code of BiGA is given in Algorithm 1.

General Principles

Most of literature works focus on linear bi-level problems (ie: formed with two linear sub-problems) or lower-level problems solvable in a reasonable amount of time. They use this property to discard the bi-level aspect of the problem. This article tries to define a more general methodology to solve bi-level optimization problems. The complexity of the considered problems lead us to consider the use of meta-heuristic, to obtain good-quality solutions in a reasonable amount of time.

We introduce a meta-heuristic, CoBRA, a coevolutionary bilevel method using r epeated algorithms. Extending Oduguwa and Roy's BiGA [START_REF] Oduguwa | Bi-level optimisation using genetic algorithm[END_REF], it is a coevolutionary meta-heuristic consisting in improving incrementally two different sub-populations, each one corresponding to one level, and periodically exchanging information with the other.

CoBRA Components

In order to instantiate CoBRA to solve a bi-level optimization problem, generic and problem-specific components have to be defined. Generic components, which can correspond to both sub-problems, consist in choosing the following: An improvement algorithm for each level, to improve the solutions on its level. We use, for single-objective levels, a classic evolutionary algorithm, and, for multi-criterion levels, NSGA-II. Those algorithms are classic population-based meta-heuristic approaches [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF].

A coevolution strategy to decide how populations should exchange information.

An archiving strategy to record the best solutions on every level, and to prevent the coevolution to change completely the sub-populations on a single generation.

A stopping criterion to decide when the algorithm should stop.

Problem specific components still have to be designed to use CoBRA: Initialization operators, generally heuristics, which create a base population to begin the search process.

Variation operators, level-specifics, which are then used by the improvements algorithms.

Evaluation operators, corresponding to the f and F functions from the bi-level optimization model.

General Algorithm

CoBRA is a coevolutionary algorithm using for each level a different population, and a different archive (Algo. 2). At each iteration, we apply the improvement algorithms, we archive the best solutions obtained, then we apply a selection operator to keep a constant size to the archive and to the populations. The final iteration step is then to coevolve the two sub-populations. Once the stopping criterion is met, CoBRA returns the lower-level archive.

Extending the BiGA approach, CoBRA involves several differences from the former:

1. The main difference is that CoBRA applies a complete algorithm, possibly iterating a certain number of generations, over each main algorithm iteration, instead of just applying variation operators. Evaluation process occurs during those improvement algorithms.

2. The coevolution process is not necessarily elitist: default coevolution strategy (Algo. 3) randomly coevolves solutions with each other.

3. The selection operations and the archives take place right after the improvement.

Data

RR n°7741

4 Performance Assessment and Bi-level Optimization

In this section, we introduce two new metrics for assessing the performance of heuristics on solving bi-level optimization problems.

Motivations

Being a problem with two different objective functions, a natural approach to tackle bi-level optimization problems would be to use a Pareto-based multicriteria approach. However bi-level optimization problems have a different structure. A good solution considering a similar problem approximating the Pareto frontier could be of bad quality in the bi-level way. Bi-level optimization aim at identifying solutions in the form (x u , x l ) which give good upper objective vectors, while being near the optimum regarding the lower objective for x u fixed. This leads to the existence of good quality solutions not being on the Pareto frontier, and solutions on the Pareto frontier not necessarily being good quality solutions. Fig. 3 gives an example of objective functions giving a bi-level solution corresponding to a dominated solution in the Pareto sense. F and f are respectively the upper and the lower-level objective functions to be minimized, the leader chooses in {d,e,f} and the follower in {a,b}. The Pareto front would be composed of {(d,a),(f,a)} while the bi-level solution is (e,a). We introduce the notion of rationality which correspond to the difficulty to improve a solution (x u , x l ), with x u fixed, according to the lower-level objective function. A rational solution is a solution where the follower reaction is rational, seeking for the optimality of its own objective function(s). We introduce two different rationality metrics, the direct one and the weighted one.

INRIA

Rationality

Direct Rationality

The direct rationality measure corresponds to the difficulty of improving a solution without regarding the actual improvement: we simply consider the "improvability". To evaluate it for a population, we apply a parametrized number of time a "good" lower-level algorithm, and count how many times the algorithm did improve the solution (Algo. 4).

Weighted Rationality

The weighted rationality is another rationality measure working on the same principle as the direct rationality with the difference that, instead of counting how many times the algorithm was able to improve the solution, we also consider how much it was improved. Being able to improve a fitness by 0.001 or by 1000 does not give the same result to the rationality, whereas the direct approach would consider both as the same (Algo. 5). For bi-level optimization problems involving a multi-objective lower-level sub-problem, we used the multiplicative -indicator, an indicator to compare sets of objective vectors [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF].

Data: AlgoLow,

Discussion

The weighted rationality metric was introduced to compare results for a bi-level optimization problem composed with a hard lower-level problem. All the tested algorithms giving a bad direct rationality, we noticed that some algorithms were still doing better and were far nearer to the optimal on the lower-level than others. The weighted rationality is able to differentiate such algorithms. We can note that those methods are not absolute, in the sense that we have to compare the algorithm using another algorithm, thus introducing a bias. Those measures compare the capacity of a meta-heuristic to use improvement algorithms, but do not actually compare the overall capacity to tackle the problem. To this end, we have to ensure that none of the tested algorithms is biased toward the improvement used by the rationality evaluation.

Application to Bi-level Transportation

In this section we define a bi-level transportation problem, involving two different companies in a supply chain: the leader transports goods from depots to retailers answering to the retailers demand, and a follower manages plants producing goods for the leader. The leader starts by deciding which depots should deliver goods, then the follower decides how to manufacture the goods, both decisions influencing the overall cost of solutions. Two variants of this problem are here considered, a single-objective one, and a multi-objective one.

A Bi-level Multi-depot Vehicle Routing Problem

The first problem, introduced by Calvete and Galé [START_REF] Calvete | A Multiobjective Bilevel Program for Production-Distribution Planning in a Supply Chain[END_REF], consists of a bi-level problem where the leader controls a fleet of vehicles to deliver items from several depots to retailers, on the same principle as the classical multi-depot vehicle routing problem (MDVRP). The follower controls a set of plants, and has to produce the items and deliver them to the depots according to the demand of the retailers it serves, thus answering a flow problem. The leader tries to minimize the total distance of his routes and the buying cost of the resources (depending on the lower-level decision). The follower minimizes the production cost and the distance traveled by the produced goods. The follower has to directly transport from plants to depots.

Problem Description

Let K, L, R and S denote the sets of plants, of depots, of retailers and of vehicles, respectively. Let E be the edge set between retailers and depots, b r the demand of retailer r, c a i,j the cost of transporting from depots or retailers i to j for the leader, c b k,l the cost to buy and unload a unit produced in plant k into depot l for the leader, and c c k,l the operational cost for plant k to produce and deliver to depot l for the follower.

The upper objective function is to minimize the sum of deliver costs from depots to retailers and buying from plants .

F(x, y) = s∈S (i,j)∈E c a i,j x s i,j + k∈K l∈L c b k,l y k,l

INRIA

with x the leader variables representing the routes chosen to deliver retailers, and y the follower variables representing the affectation of plants to depots. Then, the lower-level objective function is to minimize the sum of costs of producing items in plants and delivering it to depots.

f(x, y) = k∈K l∈L c c k,l y k,l
The leader and follower follow a hierarchical order, where the leader choose routes, creating a demand for the depots corresponding to the retailers to be delivered, and where the follower has to respond to this new demand by associating a part of his plant production to depots.

k∈K y k,l ≥ s∈S l r∈Rs b r , ∀l ∈ L
Several other VRP-related constraints are omitted to improve readability. See [START_REF] Calvete | A Multiobjective Bilevel Program for Production-Distribution Planning in a Supply Chain[END_REF] for more details about the problem.

Solution Representation

In the optic of doing an evolutionary algorithm, a solution representation was necessary. Using a generic bi-level representation, we had to decide a representation for each level. For the upper-level, we use a permutation: every retailer and every route (each route being associated to a depot) has an attributed number. The route numbers in the permutation determine the routes start, and every retailers represent in order the actual route (Fig. 4). This representation facilitate the solution integrity, and suppress the need to check the number of routes and the "one visit per retailer" constraint. We use for the lower-level problem a more classical double matrix M, M a b representing the ratio of production sent from a to b. The quantity effectively sent is scaled down at the evaluation step if the sum of a column are over 1, and rounded down if not integer. This indirect representation permits to use classical algorithms without much adaptation work.

Problem Instances

Two sets of instances1 were generated to experiment the CoBRA efficiency. S 1 consist of instances created from MDVRP instances following the modus operandi described in [START_REF] Calvete | A Multiobjective Bilevel Program for Production-Distribution Planning in a Supply Chain[END_REF]. We add as many plants as there are depots randomly located on the map. Then we set their maximal production to ensure that the instance is feasible. c b and c c follows a method described in [START_REF] Calvete | A Multiobjective Bilevel Program for Production-Distribution Planning in a Supply Chain[END_REF]. Set S 1 contains 10 instances created from the 10 instances provided by Cordeau [START_REF] Cordeau | A tabu search heuristic for periodic and multi-depot vehicle routing problems[END_REF]. The second set S 2 consists of the same instances in which a higher fixed number of plants of 50 was added. Those instance parameters are described in Table 1.

c c k,l y k,l , k∈K l∈L c d k,l y k,l c d k,l
being another operational cost of plant k, to produce and delivering a unit of good to depot l, similar to c c . While the leader still have to chose how to deliver products from depots to retailers, the follower has to respond to a biobjective problem, his goal being to find solutions which are Pareto efficient (see [START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF] for details on Pareto efficiency). We kept the same sets of instances as in BiMDVRP, to which we added the c d cost independently generated on the same way as the c c one.

Experimental Analysis

In order to evaluate the relevance of CoBRA for bi-level optimization, we conduct in this section an experimental analysis against a repairing algorithm, a classical approach which consider the lower-level optimality condition as a constraint, and simply try to find the best upper-level variable while "repairing" the lower-level one at the evaluation step.

Experimental Design

We conduct a two-part experimental analysis. In the first part, we apply the two algorithms on the bi-level multi-depot vehicle routing problem (BiMDVRP). We ran CoBRA and the repairing algorithm for BiMDVRP on S 1 , and for M-BiMDVRP on S 1 and S 2 . We run both of the algorithms 30 times with different seed values, since both algorithms use stochastic components.

Both algorithms use the same components (i.e. the improvement algorithms, the stopping criterion, the variation operators and the initializers). The reparation algorithm does not use any archiving or coevolution operator, and a different evaluation operator which apply a lower-level improvement algorithm before evaluating a solution. Once the stopping criterion is met, we evaluate the population with respect to three criteria: the population average upper-level fitness value, the direct rationality, the weighted rationality.

CoBRA instantiation for BiMDVRP an M-BiMDVRP

To use CoBRA on the BiMDVRP problem, several problem-specific components have to be chosen.

Upper-level Problem-related Components

For the MDVRP upper problem we use a combination of three variation operators:

RBX [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF] is a cross-over operator copying routes from a parent, and then completing the offspring with routes from the other parents by removing visited retailers.

SBX [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF] is a cross-over operator creating a new route, by taking half of a route starting from a single depot in each parents, keeping the order of each half, and then completing the offspring with the other routes and removing visited retailers.

Or-opt [START_REF] Or | Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking[END_REF] is a mutation operator taking several retailers from a route and putting it in another. This operator changes the number of route which neither of the SBX and RBX can do.

Operators are applied on solutions uniformly chosen in the population.

Lower-level Problem-related Components

For the lower-level problem we use a combination of two operators:

UXover [START_REF] Deb | Simulated binary crossover for continuous search space[END_REF] is a crossover operator choosing elements uniformly for each parent solution matrix and putting it in the offspring.

Uniform mutation [START_REF] Deb | A combined genetic adaptive search (geneas) for engineering design[END_REF] is a mutation operator that add a parametrized real value r lmut ∈ [-0.5, 0.5] to each element of the solution matrix with a p lmut probability.

Stopping Condition

The algorithm uses three stopping criteria, one for each improvement algorithm and one for the overall algorithm. Improvement algorithms use a generational stopping criterion which continue for a fixed number p g of generations. The overall algorithm uses a lexical continuator which continue until no better solution is found for a fixed parameter p l of generations, by using a lexical comparator (i.e. by comparing sequentially the objective values on each level).

Selection Operators

The algorithm uses three selection operators to choose which solution to keep from a generation to the next one, one for each improvement algorithm, and one for the overall algorithm. We use on both improvement algorithms a deterministic tournament, which randomly selects two solutions from the population and keep the best one. For the overall algorithm we use a survive-and-die replacement politic, which keeps a parametrized proportion of the best solutions n sad from the last generation, and apply a deterministic tournament on the remaining part of the population in order to generate the next generation.

INRIA

Archiving Strategy

The algorithm uses archives to keep record of the best solutions found over all generations. We define two different archive strategies depending on the number of lower-level objective function:

Single-objective lower-level strategy. We use a straight-forward archive that keeps the n best found solutions according the the level fitness value

Multi-objective lower-level strategy. The upper-level archive keeps the same strategy than in the single-objective case. The lower-level archive, at the insertion of a new individual i, starts by deleting any solution Paretodominated by i then inserts i if it's not dominated by any individual from the archive. If the archive size goes over n, we remove from the archive the worst elements according to the upper-level fitness values until the archive size returned under n.

Numerical Parameters

To use those components and CoBRA, the following parameters have to be set:

n: the populations size, set to 100 r lmut : the uniform mutation adding parameter, set to 0.5 p lmut : the uniform mutation probability parameter, set to 0.1 p g : the number of generations each improvement generates, set to 10 p l : the number of generations CoBRA continues without improvement, set to 100 n sad the proportion of best solutions that are kept from the last generation, set to 0.8

Experimental Results

BiMDVRP

Table 2 shows numerical results for CoBRA and the repairing algorithm on instances from S 1 . Here are displayed the average upper-level fitness value, and the best fitness value obtained in the lower-level archive, as well as the direct rationality metric value. Since direct rationality was enough to rank the algorithms, the weighted measure was not used.

CoBRA has a significantly better score for the rationality, on all the instances. For both algorithms, rationality is not related to the instance size. The repairing algorithm is doing better for the upper-level fitness value.

M-BiMDVRP

Tables 3 and4 show the experimental results over the sets S 1 and S 2 , respectively. The average and the best upper-level fitness values obtained in the lower archive, and the weighted rationality measure are given. Direct rationality did not permit to significantly decide between the coevolutionary and the hierarchical approach.

Both algorithms obtain similar upper-level fitness values. CoBRA is still having a better rationality. The rationality gap between CoBRA and the repairing algorithm increases with the instance size. The number of evaluations done by the algorithms are shown on Figure 5. The repairing algorithms needs a lot more evaluations, impairing the computational cost of the approach.

Discussion

CoBRA has a significant advantage in terms of rationality for all the runs we performed, while it does not always give a better upper-level fitness value. Rationality indicates the quality of the reaction predicted by the algorithm. A bad prediction is likely to lead to a bad solution: once applied to a real-life situation the follower will have greater chances to chose a better reaction for his own objective function(s), degrading the solution quality for the leader. Since CoBRA has a better rationality, we can better predict the outcome of the decisions. Thus we can conclude that CoBRA is more adapted to the bi-level aspect of the problem.

An explanation why the hierarchical algorithm does not select the more rational response would be that once an irrational solution x = (x u , x l ) is obtained, through a badly done reparation, which gives a better upper-level fitness value than the more rational response x = (x u , x l ), the overall algorithm will have a tendency to discard x and keep x. We can conclude that the reparation approach needs either a good lower-level heuristic, an exact lower-level algorithm, or some properties over the problem (such as a strong correlation between the two levels) to be able to produce rational responses. This is the reason why the coevolution allows CoBRA to get a better rationality, even with a hard multiobjective lower-level sub-problem. We can conclude that the coevolutionary approach can give a significant enhancement for this problem. In this paper, we described CoBRA, a new general methodology to solve bilevel optimization problems. We introduced the concept of rationality for bilevel optimization problems and two new metrics to compare the performance of heuristics for such purpose. Using those two metrics, we compared CoBRA against a classical hierarchical approach on a bi-level optimization problem of production/transportation in its single-objective and multi-objective variants.

INRIA

Experimental results showed a significant advantage to the CoBRA approach in tackling the bi-level multiple depot problem against a classical hierarchical approach.

As future work, it would be interesting to look up a possible integration of diversification principles into CoBRA. In the bi-level problems where the lowerlevel is multi-objective, a large number of solutions can be Pareto-equivalent at a given time, the archive being truncated according the upper-level of the solution considered. Instead of considering the upper-level fitness values in the lower-level archive, it could be more efficient to keep a good diversity in the archive. This would give the opportunity for the algorithm to escape from local optima easier. Furthermore, the design of CoBRA is intrinsically parallel, since two sub-populations evolve independently, so that parallel computation would improve the performance in terms of computational time.

Figure 1 :

 1 Figure 1: General scheme of an evolutionary algorithm.

Figure 2

 2 Figure 2 illustrates the outline of CoBRA.

Figure 2 :

 2 Figure 2: CoBRA outline.

Figure 3 :

 3 Figure 3: Example of lower-level and upper-level objective functions whose optimal solution is dominated in terms of Pareto dominance.

Figure 4 :

 4 Figure 4: Example of a VRP with 7 retailers, 2 depots, and 2 routes per depot, from the permutation [5, 4, 2, 9, 7, 6, 10, 1, 3, 8]. Squares are for depots {a,b}, circles for retailers {1,2,3,4,5,6,7}.

Figure 5 :

 5 Figure 5: Average number of evaluations required by CoBRA and the repairing algorithm on M-BiMDVRP instances from Set S 2 .

Table 1 :

 1 Description of S 1 and S 2 instances, R corresponding to the number of routes by depot.

	Instance	Depot	R	Plants (S 1 )	Plants (S 2 )	Retailer
	bipr01	4	1	4	50	48
	bipr02	4	2	4	50	96
	bipr03	4	3	4	50	144
	bipr04	4	4	4	50	192
	bipr05	4	5	4	50	340
	bipr06	4	6	4	50	288
	bipr07	6	1	6	50	72
	bipr08	6	2	6	50	144
	bipr09	6	3	6	50	216
	bipr10	6	4	6	50	288
	5.2 A Multi-objective Bi-level Multi-depot Vehicle Rout-
	ing Problem
	The multi-objective bi-level multi-depot routing problem (M-BiMDVRP) is a
	variant of the BiMDVRP where the follower minimizes two costs instead of
	just one distance between plants and depots, aiming at finding a Pareto front
						INRIA

Table 2 :

 2 Average upper-level fitness value, best upper-level fitness value and weighted rationality value for BiMDVRP instances from S 1 .

		Averaged fitness	Best fitness	Direct rationality
	Instance	CoBRA	Repair	CoBRA	Repair	CoBRA	Repair
	bipr01	1883	1848	1676	1626	0.6	7.5
	bipr02	4049	3338	3718	2880	1.3	5.4
	bipr03	6058	5849	5604	4712	2.7	23.5
	bipr04	7172	7368	6568	6051	1.9	19.9
	bipr05	9750	8535	9493	7179	0.6	5.4
	bipr06	15237	11637	14837	9656	0.7	5.9
	bipr07	3165	2917	2851	2453	0.9	1.5
	bipr08	7207	5348	6801	4736	2.2	22.9
	bipr09	9825	8326	9343	7042	2.0	22.2
	bipr10	14418	12413	13419	12412	0.6	13.5

Table 3 :

 3 Average upper-level fitness value, best upper-level fitness value and weighted rationality value for M-BiMDVRP instances from S 1 .

		Average Fitness	Best Fitness	Weighted rationality
	Instance	CoBRA	Repair	CoBRA	Repair	CoBRA	Repair
	mbipr01	3151	3570	2930	3002	0.66	21.50
	mbipr02	5980	6559	5729	5792	4.83	140.50
	mbipr03	11459	12369	10887	11230	77.49	562.76
	mbipr04	12985	14346	12568	13158	6.84	195.84
	mbipr05	16067	16872	15317	15982	1.82	52.89
	mbipr06	19408	21291	18523	20079	158.02	839.89
	mbipr07	5195	5790	4915	4758	8.71	253.39
	mbipr08	10566	11691	9943	10543	21.36	106.70
	mbipr09	15948	17519	15330	16247	41.13	727.62
	mbipr10	20849	22798	20361	21523	86.45	1040.10

Table 4 :

 4 Average upper-level fitness value, best upper-level fitness value and weighted rationality value for M-BiMDVRP instances from S 2 .

		Averaged fitness	Best fitness	Weighted rationality
	Instance	CoBRA	Repair	CoBRA	Repair	CoBRA	Repair
	mbipr01	3187	3630	2912	3155	16.69	67.52
	mbipr02	6155	6798	5808	6236	25.61	89.10
	mbipr03	11226	12390	10865	11544	31.55	197.58
	mbipr04	13703	14934	13240	14113	27.18	208.44
	mbipr05	15349	16773	14753	16092	111.10	357.05
	mbipr06	19894	21986	19314	21132	45.41	306.62
	mbipr07	5243	5849	4796	5239	18.86	82.46
	mbipr08	10598	11649	10131	10866	15.02	198.85
	mbipr09	15862	17517	15357	16535	21.61	229.93
	mbipr10	20747	22843	20207	22019	39.43	349.27

RR n°7741

Benchmark files are publicly available on the paradiseo website in the problems section at the following URL: http://paradiseo.gforge.inria.fr/index.php?n=Problems.Problems.RR n°7741

http://www.inria.fr ISSN 0249-6399


EvalSVC -An evaluation platform for Scalable Video Coding transmission

Tien Anh Le, Hang Nguyen, Hongguang Zhang

Abstract-Scalable Video Coding is the latest extension of the famous Advance Video Coding standard. The main advantage of SVC is that it can provide scalability for visual services which are serving customers with heterogeneous network conditions and terminals' capabilities. Nevertheless, the multimedia service research community and industry have not been able to fully utilize the entire potential of this video coding standard extension. One important reason is because of the lack of an evaluation tool-set and platform widely available for usage in the designing, evaluating as well as deploying processes of SVC-based visual services. EvalSVC aims to fill this gap and fosters SVC-based applications and research in multimedia services. It is capable of evaluating the enhanced features (such as spatial, temporal, SNR, and combined scalability) of SVC bit-streams transmitting over real or simulated networks. This tool-set is publicly available.

Index Terms-Scalable video coding; video evaluation platform; QoS Metrics and Measurement; simulation platform;

I. Introduction H .264/MPEG-4 Advance Video Coding (AVC) [1] is a very famous video compression standard. Its compression ratio has enabled many video communication services (such as video conferencing, video surveilance or video-phony...). However, a fatal limitation of this standard is that it is not scalable enough for many services. Once a source video stream has been encoded with AVC, that encoded bit-stream will remain the same throughout the communication process. Encoding parameters of the encoded bit-stream (such as bit-rate, frame-rate, screen size, SNR...) will be determined at the beginning of the communication session by senders and receivers (mostly by receivers). However, those senders and receivers may have different screen sizes, different computational capabilities, network conditions (such as bandwidth, delay, jitter...) may change during the communication session. In those cases, in order for the AVC encoded bit-stream to be consumed adaptively at each and every receiver, there must exist middle-boxes in the communication network to convert the incoming AVC encoded bit-streams into various output bit-streams which are suitable for each receiver. This causes a huge delay in the communication session and single points of failure in the communication network. Otherwise the bit-stream will be stuck at bottle-necks and the entire video communication session will be broken. All of these problems make AVC not scalable enough for many video communication services. People are now working and entertaining in a "3-screen"

Authors are with the Department of Wireless Networks and Multimedia Services, Telecom Sud Paris, France, 91000. Phone: +33 (0)1 60 76 66 63, Fax: +33 (0)1 60 76 45 78, E-mail: tien anh.Le@it-sudparis.eu. This work was supported in part by CAM4Home, an European project.

world. These screens are different in their computational capacities, screen resolutions, and communication bandwidths. A much better solution than AVC is to use Scalable Video Coding (SVC). SVC has been standardized as an extension of the AVC standard since 2007 [START_REF] Schwarz | Overview of the scalable video coding extension of the H. 264/AVC standard[END_REF]. The main idea of this extension is to apply multi-layer coding into the AVC codec. This is not a totally new idea since people had attempted to implement this idea from prior international video coding standards such as H.262/MPEG.2 Video, H.263 and MPEG.4 Visual [START_REF] Schwarz | Overview of the scalable video coding extension of the H. 264/AVC standard[END_REF]. However, the most challenging problem is that, the scalability used to come with a huge increase in computational complexity. SVC has succeeded in providing scalability with an affordable computational cost. SVC encodes an input video stream into a multi-layer output bit-stream comprising of a base layer and several enhancement layers. Within those layers, the base-layer is encoded with a basic quality to guarantee that it can be consumed by the weakest receiver of the entire communication group. This base-layer is usually protected while being transmitted over the network by QoS assured transmission methods or Forward Error Correction (FEC) algorithms. For the purpose of backward compatibility, the base-layer must be recognized by all conventional H.264 decoders. Enhancement layers, when received at the receivers together with the base-layer, can enhance the overall-quality of the bit-stream. Especially, when all enhancement layers are received in-order at the receiver together with the base layer, the bit-stream will achieve its original encoded quality. However, when real conditions (such as bandwidths, delays, or displaying screen sizes) do not allow, upper layers can be discarded along the transmission link or at any middle box (relaying entities) for the bit-stream to be fit-in with those conditions without corrupting the video communication session. Video services using SVC have been launched since the standardization of the SVC codec. In order to evaluate those services, designers and researchers are really in-need of a video transmission evaluation tool which is specially tailored for the evaluation of SVC encoded video transmissions over a real or simulated network. So far, the research community depends on Evalvid [START_REF] Klaue | Evalvid-a framework for video transmission and quality evaluation[END_REF] for measuring the objective QoS-related parameters of the under-layer networks (such as loss-rate, delays, jitter...), as well as evaluating both the subjective (using Mean Opinion Score -MOS) and objective (Peak Signal to Noise Ratio -PSNR) video quality metrics. Evalvid has supported only up to the H.264 video codec. In [START_REF] Ke | An evaluation framework for more realistic simulations of MPEG video transmission[END_REF], the connecting interface of Evalvid was extended to replace its simple error simulation model by a more general network simulator like NS-2 so that researchers and designers can plug their own network architectures in to evaluate. However, none of the above has taken SVC and its metrics into the evaluation. In section 2, we will take a look at the existing video evaluation systems such as Evalvid and its extension (My-Evalvid). Section 3 will introduce scalable video coding emphasizing on the different characteristics of SVC toward AVC and some challenging problems to be overcome in order to integrate SVC into the existing video evaluating platforms. In section 4, we will evaluate performances of a SVC video transmission systems using realistic simulation network conditions with the help of our EvalSVC evaluation platform. Section 5 will conclude and open some possible future works based on this framework.

II. Evalvid and its extension

Prior to Evalvid, other publicity available video evaluation tools [START_REF] Wolf | Video quality measurement techniques[END_REF] [START_REF] Wu | On end-to-end architecture for transporting MPEG-4 video over the Internet[END_REF] were struggling with synchronized frames between the sender and the receiver sides meaning that they could not evaluate the video quality in case of frame drops or frame decoding errors. Evalvid, with a modular structure design, overcame this major problem. The main components of the Evalvid video evaluation framework (Fig. 1) are as follows:

Source: This can be a raw source video file or raw video stream captured from a working camera. Normally, an YUV file format is used as it is the common video format supported by almost all video capturing devices. Video encoder and video decoder: Evalvid only supports a single layer video coding (mostly AVC). Video sender (VS): After being compressed by a video coder, the video bit-stream will be fed to the video sender block of Evalvid. The main job of VS is to segment large video frames (or more precisely in AVC, Network Abstraction Layer -NAL frames) into a number of smaller UDP packets before feeding them to a real or simulated network. VS also logs video frame number, frame type, frame size, number of segmented UDP packet, and timestamps down to a video trace file. With the help of a TCP dumping tool, the video bit-stream sent by VS also generates a sender trace file. The video trace file and the sender trace file will then be used in the video evaluation step. In order for VS to send a video bit-stream to the network, it needs hinting information of that bit-stream. The hinting information can be obtained by using the MP4Box tool of the GPAC framework [START_REF] Feuvre | GPAC: open source multimedia framework[END_REF]. That hint track also creates RTP (Real Time Protocol) packetization and payload format information based on the IETF's recommendations (RFCs) and/or standards of the video encoder (for the H.264 encoder, MP4Box uses RFC 3984 [START_REF] Wenger | RTP payload format for H. 264 video[END_REF]). MP4Box will also integrate that hint track and the video track into one common ISO compatible video file. Evaluate Trace (ET): The evaluation process takes place at the sender's side. By using the video trace file, the sender trace file collected from the sender's side and a receiver trace file collected at the receiver's side, ET has the information about the timestamps, the packet ID, and the packet payload size. Based on this information, ET calculates the frame/packet loss and the frame/packet jitter for each frame type (I, B, P). Since a frame is comprised of several packets, it is considered lost when the packet loss rate over-floats a limit which a particular decoder can afford. Delay and jitter are also calculated. A very important function of ET is that it tries to reconstruct an output bitstream at the receiver from trace files and the original encoded video bit-stream at the sender's side. Video evaluation (PSNR and MOS blocks): Mainly, there are two approaches to measure digital video quality. They are subjective and objective quality metrics. For subjective measurement, Evalvid uses Mean Opinion Score (MOS) [START_REF] Rec | Methods for subjective determination of transmission quality[END_REF], which scales the human quality impression on the video from bad (0) to excellent [START_REF] Wolf | Video quality measurement techniques[END_REF] spond to the decoded (YUV) frame with the same number. FV fixes this issue, by matching display (YUV) frames to transmission (coded) frames. In [START_REF] Ke | An evaluation framework for more realistic simulations of MPEG video transmission[END_REF], NS-2 has been integrated into Evalvid. By doing that, it has brought a huge libraries of network protocols and simulations into the video evaluation platform. Fig. 2 shows interfaces between Evalvid and NS-2 which has been developed in [START_REF] Ke | An evaluation framework for more realistic simulations of MPEG video transmission[END_REF]. Here, the sender trace file generated by VS will be used as the input for the NS-2 based simulation script. The MyTrafficTrace agent extracts the frame type and the frame size of the video trace file, fragments the video frames into smaller segments, and sends these segments to the lower UDP layer at the appropriate time according to the user settings specified in the simulation script file. The original FV was only capable of fixing the difference between the sending and decoding orders. If there is a corrupted frame, FV can partly fix it by simply truncating it or replacing it with a null frame so that the decoder can still recognize the frame as a decodable one. However, when a decodable frame depends on a previous frame to be decoded (as in the case of B frames depending on I and P frames, P frames depending on I and previous P frames to be decoded) and that previous frame was corrupted, then FV cannot do anything. FV was also further developed to solve this problem.

III. SVC and its RTP payload

Scalable Video Coding was standardized as an extension of H.264/AVC. Deriving from H.264/AVC, it maintains the concepts of using a Video Coding Layer (VCL) and a Network Abstraction Layer (NAL) [START_REF] Schwarz | Overview of the scalable video coding extension of the H. 264/AVC standard[END_REF].

A. Video Coding Layer

In H.264/AVC, each video frame to be encoded will be partitioned into smaller coding units called macroblocks [START_REF] Schwarz | Overview of the scalable video coding extension of the H. 264/AVC standard[END_REF]. A macro-block will cover a rectangular picture area of luminance samples. Not all macro-blocks are fully encoded, most of them can be spatially or temporally pre-dicted before being fed into the VCL encoder. Outputs of the VCL are slices: a bit string that contains the macroblock data of an integer number of macro-blocks (making a full frame) which are normally organized into slices according to the frame scanning order; and the slice header (containing the spatial address of the first macro-block in the slice, the initial quantization parameter, and similar information) [START_REF] Wenger | RTP payload format for H. 264/SVC scalable video coding[END_REF]. In both H.264/AVC and SVC, there are three main types of slices:

I slice: intra-picture coding using intra-spatial prediction from neighboring regions. This type of slice is self-contained and can be decoded without the reference to any other slice. P slice: intra-picture predictive coding and inter-picture predictive coding with one prediction signal for each predicted region. This type of slice can only be decoded with reference information from previous I or P frame. B slice: inter-picture bi-predictive coding with two prediction signals that are combined with a weighted average to form the region prediction. This type of slice can only be decoded with reference information from the previous and successive I or P frame.

B. Network Abstraction Layer

If the VCL is the interface between the encoder and the actual video frames, the Network Abstraction Layer (NAL) is the interface between that encoder and the actual network protocol, which will be used to transmit the encoded bit-stream. The NAL encoder encapsulates the slice output of the VCL encoder into Network Abstraction Layer Units (NALU), which are suitable for transmission over packet networks or used in packet oriented multiplex environments [START_REF] Wenger | RTP payload format for SVC video[END_REF]. In order to generate proper NAL units, we must pre-define the network protocol that we want to use to transmit the video bit-stream. H.264/AVC and SVC support encapsulating VCL slices into a number of network protocol (H.320, MPEG-2, and RTP...) [START_REF] Wiegand | Overview of the H. 264/AVC video coding standard[END_REF] in which RTP is mostly used because of its popularity. SVC extended the H.264/AVC standard by providing scalability. There are three main kinds of scalability that SVC can support:

Temporal scalability: A bit-stream provides temporal scalability when the set of access units (a set of NAL units that always contains exactly one primary coded picture) can be partitioned into a temporal base layer and one or more temporal enhancement layer(s). A strictly requirement for a bit-stream to be called temporal scalable is that, when we remove all access units of all temporal enhancement layers with a temporal layer identifier higher than k (1 < k < maxlayer), then the remaining layers still form a valid bit-stream for a SVC decoder (when k=1, then we have a baselayer bit-stream which must be compatible with conventional H.264/AVC decoders). Due to its nonreference property, B slices are often used to form temporal enhancement layers. Spatial scalability: A bit-stream contains of multiple layers, in which each layer corresponds to a supported spatial resolution and can be referred to by a spatial layer with a dependency identifier. In each spatial layer, motion-compensated prediction and intraprediction are employed as in single-layer video coding. However, among layers, an inter-layer prediction mechanisms are applied to improve the coding efficiency and rate-distortion efficiency by using as much lower layer's information as possible. Lower layer pictures do not need to be present in all access units making it possible to combine spatial and temporal scalability. Quality (SNR) scalability: This scalability can be considered as a special case of spatial scalability with identical picture sizes of base and enhancement layers. Quality scalability comprises of coarse-grain quality scalable (CGS) coding, medium-grain quality scalable (MGS) coding and fine-grain quality scalable (FGS) coding. In CGS, inter-layer prediction is also used. A higher quantization step size will be provided by the enhancement layers to provide a better quality for the lower layers. However, this multi-layer concept for quality scalable coding only supports a few selected bit rates in a scalable bit stream. In general, the number of supported rate points is identical to the number of layers. Switching between different CGS layers can only be done at defined points in the bit stream. Furthermore, the multi-layer concept for quality scalable coding becomes less efficient, when the relative rate difference between successive CGS layers gets smaller. MGS provides a better coding efficiency for bit-streams that have to provide a variety of bit-rates. With MGS, any enhancement layer NAL unit can be discarded from a quality scalable bit stream and thus packet-based quality scalable coding is provided. Fine-grain quality scalable (FGS) provides a coding prediction structure mechanism that completely omits drift (the motion-compensated prediction loops at encoders and decoders are not synchronized because quality refinement packets are discarded from a bit-stream). Combined scalability: In some cases, quality, spatial, and temporal scalability can be combined.

IV. EvalSVC

Our work manages to develop a video transmission evaluation framework supporting SVC's NALU extension types. The most difficult problem is that those extending types haven't been fully defined and standardized by IETF. However, it should be noticed that, the basic NALU extension types (e.g., types 14, 15, 20) have been spared for SVC extensions from AVC NALU types. So we are going to support only those NALU extensions in our EvalSVC framework since they have already reflected the main concepts of SVC. Other NALU types, such as Payload Content Scalability Information (PACSI), Empty NAL unit and the Non-Interleaved Multi-time Aggregation Packet (NI-MTAP), which are being drafted in [START_REF] Wenger | RTP payload format for SVC video[END_REF], are out of our

scope.

A NAL unit comprises of a header and a payload. In AVC, the NALU's header is 1 byte length [START_REF] Wenger | H. 264/avc over ip[END_REF]. Meanwhile, a SVC's NAL header can be 1, 2, or 3 octet length [START_REF] Wenger | RTP payload format for H. 264/SVC scalable video coding[END_REF]. The first octet of SVC's NAL header is identical with AVC (Fig. 4). It contains 3 fields of which 2 first fields (F, NRI) are spared for signaling wire-line/wireless gateway, and the importance of that NALU. The last field in the first octet of the SVC's NAL header is NALU Type specifying the NAL unit payload type. NAL unit type 14 is used for prefix NAL unit, NAL unit type 15 is used for subset sequence parameter set, and NAL unit type 20 is used for coded slice in scalable extension. NAL unit types 14 and 20 indicate the presence of three additional octets in the NAL unit header. NALU types 15 contents header information which is not necessary to be repeatedly transmitted for each sequence of of picture [START_REF] Wang | System and transport interface of SVC[END_REF]. This sub-sequence parameter set can be transmitted on an "out-of-band" transmission for error resilience. We will need this information about the NALU types when we reconstruct the possibly corrupted SVC bit-stream at the receiver side. PRID (priority ID) specifies a priority identifier for the NALU. A lower PRID indicates a higher priority. DID (dependence ID) indicates the inter-layer coding level of a layer representation. QID (quality ID) indicates the quality level of an MGS layer representation. TID (temporal ID) indicates the temporal level of a layer representation. Fig. 3 illustrates basic components of our EvalSVC platform. Some external tools are also integrated into EvalSVC to support the data-flow of the entire framework.

Raw video in : This is the input video. Normally the YUV or CIF formats are used as they are acceptable by SVC encoders as well as common video capturing devices. SVC encoder/decoder : We use JSVM [START_REF] Reichel | Joint scalable video model JSVM-8[END_REF] as our main SVC codec. Hinter : This component is derived from the mp4box tool of the GPAC library [START_REF] Feuvre | GPAC: open source multimedia framework[END_REF]. The main role of this component is to packetize SVC's NALU into RTP packets and add a hint track to the SVC bit-stream.

We can consider the hint track as an in-band signal-ing for the SVC bit-stream. Another option is to distribute the hint track in the format of a SDP file via a separate channel as out-band signaling. Mp4trace : This component acts as a video sender. Its main part is to send the hinted SVC bit-stream out to the network using the packetization information it has from the Hinter. It also logs the sequence numbers, types, and sizes of the video frames, and the number of UDP packets used to transmit each frame (since the frame size may exceed the UDP/RTP maximum payload sizes), and its sending timescale. Mp4trace can work in streaming mode or camera mode. Networks : 2 kinds of networks can be used in EvalSVC, real and simulated networks. Real network's conditions can be obtained by using real IP connections over the Internet. Tcpdump can be used to trace the real network traffic at both ends and to form the sender's and receiver's dumping files. We can also use NS-2 simulated network to form the sender's and receiver's dumping files. Using a NS-2 based simulation network, one can test a new SVC video transmission algorithm, or evaluate the performance of SVC video transmission over a conventional network model (supported by NS-2). A simulated network can comprise of many relaying nodes. Since the SVC bit-stream comprises of multiple layers, enhancement layers can be discarded at the relaying nodes according to the simulation scripts. SVC Re-builder : Being the heart of EvalSVC, the Rebuilder will collect all data from sender's, receiver's dumpings and video trace files, take both the SVC encoded bit-stream and the hinted file at the sender into account and reconstruct a possibly-corrupted output SVC bit-stream at the receiver. The SVC re-builder must understand SVC NALU headers in order to properly rebuild the corrupted SVC bit-stream. When encountering a missing packet, or a missing frame, the SVC re-builder has two options. It can truncate the SVC video frame or fill that frame with zero (or a default value). Other QoS measurements of the network such as end-to-end delay, jitter, loss rate, sender's and receiver's bit-rate will also be generated. Error Generator : Normally, an optimal transmission condition can be obtained by using a direct connection between a sender and a receiver. We can use the Error Generator to modify the dump and trace files according to a pre-defined error distribution function. SVC Evaluator : This component will compare the bitstream from the output of the SVC Re-builder with the original bit-stream from the sender. Objective and subjective quality evaluation (PSNR, MOS) of the SVC video transmission will be carried out at this component. Sender/Receiver nodes : Real or simulated nodes on the transmission network. They are the departure and destination of the video transmission.

A sample evaluation session using EvalSVC starts with the raw video taken from a file or real-time captured by a camera. This raw video will then be encoded by the SVC encoder to form a SVC bit-stream. The SVC encoded bit-stream is fed into the Hinter to be packetized into RTP packets. A hint track will also be added to the original bit-stream. Mp4trace will send the hinted file (using streaming or camera mode) from the Sender node to the real/simulated network. A video trace file, a sender and a receiver dumping files will be generated. Using information from all of these files, and the original bitstream, the SVC Re-builder will reconstruct the received bit-stream and feed it to the SVC Evaluator for generating the video transmission results. The reconstructed SVC video can also be delivered to the SVC decoder to get the output video play-out at the receiver side. Fig. 5 shows the PSNR of the extracted, decoded SVC bit-stream. For example, a cif-size raw file with 1065 frames is encoded using SNR SVC. The output bit-stream is sent via a real direct IP connection from a sender to a receiver. We manually generate errors by erasing entries at the sender's and receiver's dumping files. At the receiver, the received bitstream is re-constructed by using the re-builder component of EvalSVC. Since the JSVM decoder cannot decode a corrupted bit-stream, we need to extract the uncorrupted base-layers out of the corrupted bit-stream for it to be decoded by the decoder. Fig. 5 shows the PSNR of all 1065 frames of the sample SNR SVC video. From this PSNR result, we can get the MOS value of the reconstructed SNR SVC at the receiver which is equal to 4.89 (between Good and Excellent). We can also use EvalSVC to evaluate the transmission of different kinds of SVC streams on a simulated network using NS-2. In the first simulation scenario (Fig. 6), we try to find out the best SVC method which can afford the most with the bottleneck condition of the network. To simulate the bottleneck condition, 3 nodes are built using NS-2: node 0 (the sender), node 1 (the relay), and node 2 (the receiver). The first link (link 1), connecting node 0 and node 1, has a bandwidth of 400 kbps, 1 ms delay. The second link (link 2), connecting node 1 and node 2 has a bandwidth of 100 Mbps, 1 ms delay. This network configuration will create a bottleneck on link 1. Firstly, a CIF-size AVC stream is sent from node 0 to node 2 via node 1. In the second and third simulations, a SNR SVC stream and a Spatial SVC stream (both CIF-size) are sent respectively via the same route from node 0 to node 2. We do not use the temporal SVC in our simulation since a temporal SVC stream is identical with an AVC stream. We use EvalSVC to evaluate the Y-PSNR performance of these 3 streams. Fig. 7 shows that, when bottom-neck occurs, SNR SVC has the best and AVC has the worst Y-PSNR performance. MOV grades of AVC, spatial SVC, and SNR SVC streams are 1.02, 4.07, and 5, respectively. We can conclude that, AVC is very sensible to bottleneck, a single bottleneck in the transmission route can easily block the entire communication session. Meanwhile, all SVC streams can afford quite well (MOS > 4) with the bottleneck condition of the network, among those, SNR SVC has the best performance.

V. Conclusion and future work

In this paper, we have introduced EvalSVC, our evaluation platform for Scalable Video Coding video transmission. The main purpose of this work is to fill the gap between the design, evaluation and implementation processes of variable visual services based on Scalable Video Coding. Using our newly developed framework, we found that, SVC can afford better than AVC in bottleneck conditions of the network. Among SVC, through simulation results, we found that, SNR SVC can afford the most against the bottleneck problem of the network. Our future work is to apply this platform to evaluate our innovative multimedia transmission algorithms based on Scalable Video Coding. This tool-set is publicly available at [START_REF] Le | EvalSVC tool-set[END_REF].

Fig. 1 .

 1 Fig. 1. Schematic illustration of the evaluation framework provided by EvalVid [3].

Fig. 2 .

 2 Fig. 2. Interfaces between EvalVid and NS-2[4].

Fig. 3 .

 3 Fig. 3. EvalSVC's diagram.

Fig. 4 .

 4 Fig. 4. SVC NALU's header.

Fig. 5 .Fig. 6 .

 56 Fig. 5. PSNR of the reconstructed SNR SVC bit-stream after being extracted.

Fig. 7 .

 7 Fig. 7. Y-PSNR comparision among AVC, SNR SVC and Spatial SVC streams.


Tien Anh Le
email: tienanh.le@it-sudparis.eu

Hang Nguyen
email: hang.nguyen@it-sudparis.eu

Scalable Video transmission on overlay networks

Keywords: Scalable video coding, video evaluation platform, QoS Metrics and Measurement, overlay simulation

Scalable Video Coding is the multi-layer extension of Advanced Video Coding with the advantage of providing visual services for customers with heterogeneous network conditions and terminals' capabilities. In this research, advanced features of Scalable Video Coding are investigated and compared with Advanced Video Coding. A new video transmission evaluation platform is proposed to support the latest Network Abstract Layer Units of Scalable Video Coding.

A new interface between the scalable video evaluation platform and an overlay simulation platform is developed so that the transmission performance of Scalable Video Coding bit-streams on an overlay network will be evaluated. Both structural similarity index (SSIM) and peak signal-to-noise ratio (PSNR) measurements are applied to evaluate the performance of the video transmission session. New measurement results are also provided so that other SVC-based service designers can select the right video scalability for their service.

I. INTRODUCTION

People are now working and entertaining in a "3-screen" world. These screens are different in their computational capacities, screen resolutions, and communication bandwidths. However, many service providers are providing their multimedia services based on single layer video coding (such as JPEG2000, Advance Video Coding (AVC)...). A fatal limitation of the single layer video coding is that it is not scalable enough for multimedia services. Once a source video stream has been encoded with AVC, that encoded bitstream will remain the same throughout the communication process. Encoding parameters of the encoded bit-stream (such as bit-rate, frame-rate, screen size, SNR...) will be determined at the beginning of the communication session by senders and receivers (mostly by receivers). A much better solution is to use Scalable Video Coding (SVC). SVC has been standardized as an extension of the AVC standard since 2007 [START_REF] Schwarz | Overview of the scalable video coding extension of the H. 264/AVC standard[END_REF]. The main idea of this extension is to apply multilayer coding into the AVC codec. SVC encodes an input video stream into a multi-layer output bit-stream comprising of a base layer and several enhancement layers. Within those layers, the base-layer is encoded with a basic quality to guarantee that it can be consumed by the weakest receiver of the entire communication group. For the purpose of backward compatibility, the base-layer must be recognized by all conventional H.264 decoders. Enhancement layers, when received at the receivers together with the base-layer, can enhance the overall-quality of the bit-stream. Especially, when all enhancement layers are received in-order at the receiver together with the base layer, the bit-stream will achieve its original encoded quality. However, when real conditions (such as bandwidths, delays, or displaying screen sizes) do not allow, upper layers can be discarded along the transmission link or at any middle box (relaying entities) for the bit-stream to be fit-in with those conditions without corrupting the video communication session. Beside scalable video coding, modern multimedia services often rely on Application Layer Multicast (ALM) [START_REF] Hosseini | A survey of application-layer multicast protocols[END_REF] to serve a large group of subscriber with heterogeneous network and terminal capacities (e.g., IPTV, video conferencing services...). The key concept of ALM is the implementation of multicasting functionality as an application service instead of a network service. ALM algorithms can be optimized for a specific application and of course it can adapt to the SVCbased services. Video services using SVC have been launched since the standardization of the SVC codec. In order to evaluate those services, designers and researchers are really in-need of a video transmission evaluation tool which is specially tailored for the evaluation of SVC encoded video transmissions over a real or simulated network and which has the interface to an Application Layer Multicast simulation platform. So far, the research community depends on Evalvid [START_REF] Klaue | Evalvid-a framework for video transmission and quality evaluation[END_REF] for measuring the objective QoS-related parameters of the underlay networks (such as loss-rate, delays, jitters...), as well as evaluating both the subjective (using Mean Opinion Score -MOS) and objective (Peak Signal to Noise Ratio -PSNR) video quality metrics. Evalvid has supported only up to the H.264 video codec. In [START_REF] Ke | An evaluation framework for more realistic simulations of MPEG video transmission[END_REF], the connecting interface of Evalvid was extended to replace its simple error simulation model by a more general network simulator (NS-2) so that researchers and designers can plug-in their own network architectures to evaluate. However, none of the above has taken SVC and its metrics into the evaluation. An SVC evaluation platform was first proposed in [START_REF] Le | EvalSVC -an evaluation platform for scalable video coding transmission[END_REF]. In this research, an interface between EvalSVC and Oversim has been developed as an evaluation bridge between Scalable Video Coding services and Application Layer Multicast algorithms. The rest of the paper is organized as follows. In section II, we will take a look at the new RTP payloads of SVC to see what should be done to support them in the evaluation platform. Section III will introduce the proposed features of the scalable video coding transmission platform EvalSVC. In section IV, the newly developed interface between EvalSVC and Oversim will be described with some demonstrative simulation scenarios and results. Section V will conclude and open some possible future works.

II. EXTENSIONS IN SCALABLE VIDEO CODING

PAYLOADS

Scalable Video Coding was standardized as an extension of H.264/AVC. Deriving from H.264/AVC, it maintains the concepts of using a Video Coding Layer (VCL) and a Network Abstraction Layer (NAL) [START_REF] Schwarz | Overview of the scalable video coding extension of the H. 264/AVC standard[END_REF].

A. Scalable video slices

In H.264/AVC, each video frame to be encoded will be partitioned into smaller coding units called macro-blocks [START_REF] Schwarz | Overview of the scalable video coding extension of the H. 264/AVC standard[END_REF]. A macro-block will cover a rectangular picture area of luminance samples. Outputs of the VCL are slices: a bit string that contains the macro-block data of an integer number of macro-blocks (making a full frame) which are normally organized into slices according to the frame scanning order; and the slice header (containing the spatial address of the first macro-block in the slice, the initial quantization parameter, and similar information) [START_REF] Wenger | RTP payload format for H. 264/SVC scalable video coding[END_REF]. In both H.264/AVC and SVC, there are three main types of slices:

• I slice: intra-picture coding using intra-spatial prediction from neighboring regions. This type of slice is selfcontained and can be decoded without the reference to any other slice.

• P slice: intra-picture predictive coding and inter-picture predictive coding with one prediction signal for each predicted region. This type of slice can only be decoded with reference information from previous I or P frame.

• B slice: inter-picture bi-predictive coding with two prediction signals that are combined with a weighted average to form the region prediction. This type of slice can only be decoded with reference information from the previous and successive I or P frame.

B. Interface to real networks

If the VCL is the interface between the encoder and the actual video frames, the Network Abstraction Layer (NAL) is the interface between that encoder and the actual network protocol, which will be used to transmit the encoded bit-stream. The NAL encoder encapsulates the output slices of the VCL encoder into Network Abstraction Layer Units (NALU), which are suitable for transmission over packet networks or used in packet oriented multiplex environments [START_REF] Wenger | RTP payload format for SVC video[END_REF]. In order to generate proper NAL units, we must pre-define the network protocol that we want to use to transmit the video bit-stream. H.264/AVC and SVC support encapsulating VCL slices into a number of network protocols (H.320, MPEG-2, and RTP...) [START_REF] Wiegand | Overview of the H. 264/AVC video coding standard[END_REF] in which RTP is mostly used because of its popularity. SVC extended the H.264/AVC standard by providing scalability. There are three main kinds of scalability that SVC can support: Temporal, spatial, quality (SNR), and combined scalability.

III. A SCALABLE VIDEO EVALUATION PLATFORM

Our work manages to develop a video transmission evaluation framework supporting SVC's NALU extension types. The most difficult problem is that those extending types haven't been fully defined and standardized by IETF. However, it should be noticed that, the basic NALU extension types (e.g., types 14, 15, 20) have been spared for SVC extensions from AVC NALU types. So we are going to support only those NALU extensions in our EvalSVC framework since they have already reflected the main concepts of SVC. Other NALU types, such as Payload Content Scalability Information (PACSI), Empty NAL unit and the Non-Interleaved Multi-time Aggregation Packet (NI-MTAP), which are being drafted in [START_REF] Wenger | RTP payload format for SVC video[END_REF], are out of our scope. A NAL unit comprises of a header and a payload. In AVC, the NALU's header is 1 byte length [START_REF] Wenger | H. 264/avc over ip[END_REF]. Meanwhile, a SVC's NAL header can be 1, 2, or 3 octet length [START_REF] Wenger | RTP payload format for H. 264/SVC scalable video coding[END_REF]. The first octet of SVC's NAL header is identical with AVC. It contains 3 fields of which 2 first fields (F, NRI) are spared for signaling wire-line/wireless gateway, and the importance of that NALU. The last field in the first octet of the SVC's NAL header is NALU Type specifying the NAL unit payload type. NAL unit type 14 is used for prefix NAL unit, NAL unit type 15 is used for subset sequence parameter set, and NAL unit type 20 is used for coded slice in scalable extension. NAL unit types 14 and 20 indicate the presence of three additional octets in the NAL unit header. NALU types 15 contents header information which is not necessary to be repeatedly transmitted for each sequence of of picture [START_REF] Wang | System and transport interface of SVC[END_REF]. This sub-sequence parameter set can be transmitted on an "out-of-band" transmission for error resilience. We will need this information about the NALU types when we reconstruct the possibly corrupted SVC bit-stream at the receiver side. PRID (priority ID) specifies a priority identifier for the NALU. A lower PRID indicates a higher priority. DID (dependence ID) indicates the inter-layer coding level of a layer representation. QID (quality ID) indicates the quality level of an MGS layer representation. TID (temporal ID) indicates the temporal level of a layer representation. Fig. 1 illustrates main components of our EvalSVC platform. Some external tools are also integrated into EvalSVC to support the data-flow of the entire framework.

• SVC encoder/decoder: We use JSVM [START_REF] Reichel | Joint scalable video model JSVM-8[END_REF] as our main SVC codec.

• Hinter: This component is derived from the mp4box tool of the GPAC library [START_REF] Feuvre | GPAC: open source multimedia framework[END_REF]. The main role of this component is to packetize SVC's NALU into RTP packets and add a hint track to the SVC bit-stream. We can consider the hint track as an in-band signaling for the SVC bit-stream. Another option is to distribute the hint track in the format of a SDP file via a separate channel as out-band signaling.

• Mp4trace: This component acts as a video sender. Its main part is to send the hinted SVC bit-stream out to the network using the packetization information it has from the Hinter. It also logs the sequence numbers, types, and sizes of the video frames, and the number of UDP packets used to transmit each frame (since the frame size may exceed the UDP/RTP maximum payload sizes), and its sending timescale. Mp4trace can work in streaming mode or camera mode.

• Networks: 2 kinds of networks can be used in EvalSVC, real and simulated networks. Real network's conditions can be obtained by using real IP connections over the Internet. Tcpdump can be used to trace the real network traffic at both ends and to form the sender's and receiver's dumping files. We can also use NS-2 simulated network to form the sender's and receiver's dumping files. Using a NS-2 based simulation network, one can test a new SVC video transmission algorithm, or evaluate the performance of SVC video transmission over a conventional network model (supported by NS-2). A simulated network can comprise of many relaying nodes. Since the SVC bit-stream comprises of multiple layers, enhancement layers can be discarded at the relaying nodes according to the simulation scripts.

• SVC Re-builder: Being the heart of EvalSVC, the Rebuilder will collect all data from sender's, receiver's dumpings and video trace files, take both the SVC encoded bit-stream and the hinted file at the sender into account and reconstruct a possibly-corrupted output SVC bit-stream at the receiver. The SVC re-builder must understand SVC NALU headers in order to properly rebuild the corrupted SVC bit-stream. When encountering a missing packet, or a missing frame, the SVC re-builder has two options. It can truncate the SVC video frame or fill that frame with zero (or a default value). Other QoS measurements of the network such as end-to-end delay, jitter, loss rate, sender's and receiver's bit-rate will also be generated.

• SVC Evaluator: This component will compare the bitstream from the output of the SVC Re-builder with the original bit-stream from the sender. Objective and subjective quality evaluation (PSNR, MOS) of the SVC video transmission will be carried out at this component.

We can also use EvalSVC to evaluate the transmission of different kinds of SVC streams on a simulated network using NS-2. We try to find out the best SVC method which can afford the most with the bottleneck condition of the network.

To simulate the bottleneck condition, 3 nodes are built using NS-2: node 0 (the sender), node 1 (the relay), and node 2 (the receiver). The first link (link 1), connecting node 0 and node 1, has a bandwidth of 400 kbps, 1 ms delay. The second link (link 2), connecting node 1 and node 2 has a bandwidth of 100 Mbps, 1 ms delay. This network configuration will create a bottleneck on link 1. Firstly, a CIF-size AVC stream is sent from node 0 to node 2 via node 1. In the second and third simulations, a SNR SVC stream and a Spatial SVC stream (both CIF-size) are sent respectively via the same route from node 0 to node 2. We do not use the temporal SVC in our simulation since a temporal SVC stream is identical with an AVC stream. We use EvalSVC to evaluate the Y-PSNR performance of these 3 streams. Fig. 2 shows the performance comparison of the three bit-streams using the structural similarity (SSIM) index. SSIM is a method for measuring the similarity between two images. It was designed to improve on traditional methods like peak signalto-noise ratio (PSNR) and mean squared error (MSE), which have proved to be inconsistent with human eye perception.

The SSIM measurement on the same bottle-neck simulated conditions gives us the similar result with Y-PSNR when compared SNR, spatial scalability and AVC. However, the SSIM measurement shows that, the AVC bit-stream is not always worse than the SVC bit-streams. Some frames (e.g., 1-100, 500-750) do have a high similarity with the original bit-stream. We cannot see this similarity if we only use the PSNR measurement.

IV. PROPOSED INTERFACE TO OVERSIM

Oversim [START_REF] Baumgart | OverSim: A flexible overlay network simulation framework[END_REF] is an simulation platform for overlay networks. In comparison to NS-2, it can provide better peerto-peer and overlay simulation features. We can easily simulate application layer multicast algorithms (such as NICE, Narada...) with an almost unlimited number of peers within a multicasting group. Nowadays, more and more visual services (IPTV, video conferencing...) are being provided on multicast overlay networks. Our evaluation platform has an interface to the Oversim platform so that a scalable video bit-stream generated from our platform can be multicasted from a source node over the overlay simulated network generated by OverSim. Then, at each receiving peers within that multicast group, a possibly corrupted bit-stream will be reconstructed and compared with the original bit-stream. SSIM and PSNR measurements will be carried out at any peer or all peers of that multicast group when necessary. This feature is favorable for visual service designers and researchers of application layer multicast algorithms to verify and evaluate their proposals. EvalSVC makes use of the trace files of actual SVC bit-streams. Instead of sending the real video which has big sizes and often has copyrighted contents, trace files containing frame sizes and sending timescales will be used. We can make use of the online available scalable video coding trace library [START_REF] Reisslein | H. 264/AVC and SVC Video Trace Library: A Quick Reference Guide[END_REF]. We can also generate a trace file from a specific SVC bit-stream by using the mp4trace block. According to that trace file, an application running on a randomly chosen source peer of the multicast group will generate the SVC traffic and transmit it through the simulated overlay. At the same time, it creates a sender's dumping file and store them at the sender's side. The video packets are then transmitted on the multicast group to other peers. Each peer will generate a receiver dumping file and write an entry to that file whenever it receives a packet from the sender via the multicast group. After the video transmission session ends, receiver's dumping files are collected from all receiving peers. The information from the sender dumping/trace files, the original/hinted bit-streams and the receivers' dumping files at receiving peers, possibly corrupted bit-streams are reconstructed at each receiver. These files can be decoded using a common Scalable Video Decoder and then compared with the original raw video at the sender using common methods such as Y-PSNR and SSIM. Fig. 3 shows the Y-PSNR measurement of SVC and AVC video transmission over the OverSim interface. We can see that, regarding the Y-SNR on an ALM environment, SNR-SVC has the best performance followed by combined-SVC, spatial-SVC, and temporal-SVC (it should be noted that the temporal-SVC bit-stream has the smallest number of frames simply because many B frames have been dropped for scalability). AVC still owns the worst performance. Regarding the SSIM measurement among the same set of video over the ALM environment, Fig. 4 show that SNR-SVC, combined-SVC, and spatial-SVC still outperform temporal-SVC and AVC. Fig. 5 displays a closer look to the result shown in Fig. 5. Here we can find an interesting different result than the one we have from the Y-PSNR measurement in Fig. 3, on the same ALM environment, SSIM measurement shows that the combined-SVC has a better performance than the SNR-SVC. It is interesting because it shows that even though a combined-SVC bit-stream may have a lower SNR, the combined scalability can help it to achieve a better similarity to the original bit-stream than the SNR-SVC bit-stream.

V. CONCLUSION AND FUTURE WORK In this paper, we have introduced EvalSVC, our evaluation platform for Scalable Video Coding video transmission, proposed a new interface between the EvalSVC and Oversim for bridging and evaluating the works between SVC-based services and ALM-based overlay algorithms. New measurement results are also provided in both PSNR and SSIM so that other SVC-based service designers can select the right scalability for their service. The main purpose of this work is to fill the gap between the design, evaluation and implementation processes of variable visual services based on Scalable Video Coding.

Figure 1 .

 1 Figure 1. EvalSVC's diagram[5].

Figure 2 .

 2 Figure 2. Structural similarity index comparison among SNR, spatial SVC and AVC.

Figure 3 .

 3 Figure 3. Y-PSNR comparison among SNR, spatial, combined, temporal SVC and AVC transmission performance over the OverSim interface.

Figure 4 .

 4 Figure 4. SSIM comparison among SNR, spatial, combined, temporal SVC and AVC transmission performance over the OverSim interface.

Figure 5 .

 5 Figure 5. A closer view of the SSIM comparison among SNR, spatial, combined SVC transmission performance over the OverSim interface.