Jean-Louis Loday

Nikolay M Nikolov

Operadic construction of the renormalization group

First, we give a functorial construction of a group associated to a symmetric operad. Applied to the endomorphism operad it gives the group of formal diffeomorphisms. Second, we associate a symmetric operad to any family of decorated graphs stable by contraction. In the case of Quantum Field Theory models it gives the renormalization group. As an example we get an operadic interpretation of the group of "diffeographisms" attached to the Connes-Kreimer Hopf algebra.

Introduction

The combinatorics underlying the renormalization of Quantum Field Theory (QFT) is encoded into the Feynman diagrams. The diagram technique is a powerful tool in perturbative QFT. It was discovered by Connes and Kreimer that the combinatorics in renormalization can be described by a Hopf algebra structure on the space of Feynman diagrams since the attached group is the renormalization group. In this paper our aim is to systematize this procedure by means of symmetric operads. First we show that a family of decorated graphs which is stable for the contraction of the internal edges determines a symmetric operad. Second, we show that to any symmetric operad is attached a (formal) group which takes care of the symmetric group action. Combining the two constructions we get the construction of a group attached to families of diagrams. In the case of QFT we get the renormalization group.

For the notation and terminology on operads we follow [5] for which we refer for details.

2 Operadic construction of the group of formal diffeomorphisms Let V ≡ R N be a vector space and → x = (x 1 , . . . , x N ), → y , → z ∈ V . Consider the formal power series

→ y = → f → x = ∞ ∑ n = 1 1 n! N ∑ µ 1 ,...,µ n = 1 → f µ 1 ,...,µ n x µ 1 • • • x µ n , (1)
→ z = → g → y = ∞ ∑ n = 1 1 n! N ∑ µ 1 ,...,µ n = 1 → g µ 1 ,...,µ n x µ 1 • • • x µ n ,
where → f µ 1 ,...,µ n = ( f ν;µ 1 ,...,µ n ) N ν = 1 and → g µ 1 ,...,µ n = (g ν;µ 1 ,...,µ n ) N ν = 1 are the series coefficients. Since these series do not have constant terms (i.e., terms with n = 0) it is well known that their composition

→ z = → g → f → x = ∞ ∑ n = 1 1 n! N ∑ µ 1 ,...,µ n = 1 → h µ 1 ,...,µ n x µ 1 • • • x µ n , (2)
can be determined completely algebraically. A less popular fact is the formula for the coefficients → h µ 1 ,...,µ n = (h ν;µ 1 ,...,µ n ) N ν = 1 of the composition series: g ν;ρ 1 ,...,ρ k f ρ 1 ;µ i 1,1 ,...,µ i 1, j 1

• • • f ρ k ;µ i k,1 ,...,µ i k, j k , (3)
which, in the case N = 1, is known as the Faà di Bruno formula. Here are the notations used in Eq. ( 3):

• the sum is over all partitions P = i 1,1 , . . . , i 1, j 1 , . . . , i k,1 , . . . , i k, j k

of the set {1, . . . , n}; • in particular, k is the cardinality |P| of the partition P and j 1 , . . . , j k are the cardinalities of its pieces; • the partitions P are unordered, but we shall introduce a "canonical order" such that inside each group the elements are in increasing order and the groups are ordered according to the order of their minimal elements

i ,1 < • • • < i , j , i 1,1 < i 2,2 < • • • < i k, j k . (5)
Note that all the coefficients → f µ 1 ,...,µ n , → g µ 1 ,...,µ n and → h µ 1 ,...,µ n are symmetric in their indices µ 1 , . . . , µ n and hence, our convention in Eq. (3) about the order on P is not essential. However, we shall see that dropping the symmetry condition on the coefficients still defines an associative product.

Let us try to simplify a little bit Eq. ( 3) by absorbing some summations: the coefficients → f µ 1 ,...,µ n define a multi-linear map

f n = → f µ 1 ,...,µ n : V ⊗n → V (6)
and vice versa, every multi-linear map f n : V ×n → V defines a system of coefficients → f µ 1 ,...,µ n by its matrix elements. Furthermore, the coefficients → f µ 1 ,...,µ n are symmetric in µ 1 , . . . , µ n iff the map f n is symmetric. Similarly, we set

g n = → g µ 1 ,...,µ n : V ⊗n → V , h n = → h µ 1 ,...,µ n : V ⊗n → V (n = 1, 2, . . . ). Then Eq. (3) reads h n = ∑ P ∈ Part{1,...,n} g k • f j 1 ⊗ • • • ⊗ f j k • σ P , (7)
where the numbers k, j 1 , . . . , j k are defined by conventions ( 4) and (5) together with the permutation σ P ∈ S n , which is

σ P := i 1,1 , . . . , i 1, j 1 , . . . , i k,1 , . . . , i k, j k .
Thus, the formal power series 1) is encoded by a sequence

→ y = → f → x of formula (
f = f 1 , f 2 , . . . , f n , . . . ∈ ∞ ∏ n = 1 Hom V ⊗n ,V S n (Hom V ⊗n ,V S n being the subspace of S n -invariant maps in Hom V ⊗n ,V ). The multiplication in ∞ ∏ n = 1 Hom V ⊗n ,V S n , h = g • f := h n ∞ n = 1 ,
that is defined by Eq. ( 7) is associative. It has a unit, the composition unit:

1 = (id V , 0, . . . ) Furthermore, if we assume that f 1 = id V (the identity map of V ), then f has a com- position inverse f -1 = 1, ( f -1 ) 2 , . . . since for n > 1 we have 0 = 1 n = f -1 • f n = ( f -1 ) n + f n + low order terms , which inductively fixes ( f -1 ) n .
The so described group of formal diffeomorphisms is denoted by

FDiff(V ) ∼ = {id V } × ∞ ∏ n = 2 Hom V ⊗n ,V S n . (8)
Note that the vector space V can be even arbitrary linear vector space: N then will be the cardinality (possibly, infinite) of the linear basis of V and the series (1) would be neither more nor less formal. We note also that f ν;µ 1 ,...,µ n for fixed µ 1 , . . . , µ n are nonzero only for no more than a finite number of indices ν since they are coordinates of the vector

→ f µ 1 ,...,µ n . Hence, the correspondence → f →
x ↔ f defined by ( 6) remains valid and the composition (2) is again well defined algebraically.

Group associated to a symmetric operad

We now observe that the multiplication (7) has a straightforward generalization in a symmetric operad (see Eq. (9) below). Indeed, it uses two basic structures which are axiomatized in the operad theory. These are the composition of multilinear maps and the right action of (or, composition with) permutations.

Theorem 1. ([4]

) There is a functor together with a subfunctor:

Category of Symmetric operads

→ Category of Groups

P = {P(n)} ∞ n = 1 → G(P) = {id} × ∞ ∏ n = 2 P(n) P = {P(n)} ∞ n = 1 → G(P) = {id} × ∞ ∏ n = 2 P(n) S n ,
where P(n) S n stands for the subspace of S n -invariant elements. The multiplication law is given by

(β • α) n = ∑ P ∈ Part{1,...,n} γ β k ; α j 1 , . . . , α j k σ P (9) for α = (α n ) ∞ n = 1 and β = (β n ) ∞ n = 1
and the notations of Eq. [START_REF] Stora | Causalité et Groupes de Renormalisation Perturbatifs[END_REF]. On operadic morphisms ϑ :

P → P (= {ϑ n : P(n) → P (n)} ∞ n = 1 ) the functor gives G(ϑ ) := ∞ ∏ n = 1 ϑ n .
In the case of End V we have a natural isomorphism

G End V ∼ = FDiff(V ) . (10)
The most nontrivial part of the above statement is the associativity of the operation • (9). It can be proven by straightforward inspection. The existence of a unit and inverse elements follows exactly by the same arguments as for the group of formal diffeomorphisms.

Remark 1. There is a natural group associated with a non-symmetric operad P = P n n 1 (see [5, Sect. 5.8.15]). However when this construction is applied to a symmetric operad considered as a non-symmetric it gives a different group.

We will give below some facts about the structure of of the groups related to symmetric operads.

Proposition 1. ([4]) Let us set for m > 0 G m (P) = α = (α n ) ∞ n = 1 ∈ G(P) α 2 = • • • = α m = 0 (for m = 1, G 1 (P) := G(P)). Then G m (P) is a normal subgroup of G(P).
Note that

G(P) = lim ←- G(P) G m (P)
and in the case when the operadic spaces P(n) are finite dimensional the quotient groups are (finite dimensional) Lie groups. Hence, in the latter case the group G(P) is a pro-Lie group. We use this fact to derive the Lie algebra corresponding to the group G(P) together with the exponential map.

Theorem 2. ([4])

The Lie algebra corresponding to the group G(P) is

g(P) = {0} × ∞ ∏ n = 2 P(n)
The Lie bracket on g(P) is built from a pre-Lie bracket

[µ, ν] = µ * ν -ν * µ (µ, ν ∈ g(P)), where 1 (µ * ν) n = ∑ / 0 = J ⊆ {1,...,n} ν k • min J µ j σ P J ≡ ∑ / 0 = J ⊆ {1,...,n} γ ν k ; id, . . . , id, µ j ↑ min J
, id, . . . , id σ P J (11) 1 • i is the ith operadic partial composition where j = |J| and the partition P J is the partition {i} i ∈ {1, . . . , n}\J ∪ {J}. (Note that the sum in (11) is the subsum in (9) corresponding to partitions P of a form P J .)

The Lie algebra g(P) is again an inverse limit of finite dimensional Lie algebras

g(P) = lim ←- g(P) g m (P)
where g m (P) is the ideal

g m (P) = µ = (µ n ) ∞ n = 1 ∈ g(P) µ 2 = • • • = µ m = 0 .
Note that the quotient group G(P) G m (P) and Lie algebra g(P) g m (P) are isomorphic as sets to the set

Feynman diagrams and their combinatorics

Feynman diagrams are a powerful tool in perturbation theory. They indicate the terms of perturbative expansions. Furthermore, many manipulation on the corresponding formal perturbation series have a combinatorial description by operations on diagrams.

a) Basic definitions

A Feynman diagram is a finite graph with various decorations. A graph Γ is a set of points, called vertices, with attached flags (or half-edges) to them. Some pairs of these flags are further joined to become edges connecting the corresponding vertices. All these structures are contained in the following data: two finite sets, the set of vertices vert(Γ ) and the set of flags flag(Γ ), and two maps

s : flag(Γ ) → vert(Γ ) , σ : flag(Γ ) → flag(Γ ) (12)
such that σ 2 = id. Thus, the map s represents the process of attaching flags to vertices, i.e., the flag f is attached to the vertex s( f ). The map σ represents the process of joining flags, i.e., the flag f is joined with the flag σ ( f ). In the latter case if f = σ ( f ) then we call this flag an external line; such a line is attached to one only vertex. If f = σ ( f ) then the unordered pair { f , σ ( f )} form an edge, or an internal line of the graph, which is attached to the vertices s( f ) and s(σ

( f )). When s( f ) = s(σ ( f )) but f = σ ( f )
we have an internal line attached to one and the same vertex. Such an internal line is called a tadpole and it is usually excluded to exist.

To every graph we assign a topological space: its geometric realization. To this end we assign to each edge a copy of the closed interval [0, 1] (without the orienta-tion) and to each vertex a point. Then we glue all of these spaces according to the incidence between the edges and the vertices.

A decorated graph is a graph with some extra data. Forgetting these extra structure we obtain just a graph that is called the body of the decorated graph. We shall consider graphs with the following decorations: a) Colors for the vertices and for the flags. They form two sets -a set of colors for the vertices: Colv -a set of colors for the flags: Colf Then we have maps assigning colors:

c v : vert(Γ ) → Colv , c f : flag(Γ ) → Colf . (13)
b) The second type of decoration we shall consider is an enumeration

ν : vert(Γ ) ∼ = {1, . . . , n} (14)
of the set of vertices.

b) Examples

These are the notion of graph and decorated graph, or also diagram. Here are some examples to illustrate them.

Example 1. An example of a graph is: vert(Γ ) = {0, 1}, flag(Γ ) = {a, b, c, d, e, f }, s(a) = s(b) = s(c) = 0, s(d) = s(e) = s( f ) = 1, σ (a) = a, σ (b) = e, σ (c) = d, σ ( f ) = f .
c v (0) = c v (1) = •, c f (a) = , c f (b) = , c f (e) = , c f ( f ) = , c f (c) = = c f (d).
The result can be drawn as So, we indicated the colors in this example by shapes, which is common in physics. Also if the colors of two joined flags coincide we indicate this as a color of the corresponding edge. In the above example we also meet situation of edges of the form and in this case it is also convenient to think of such an edge as an oriented edge

. Then we can draw the diagram of this example as

c) Types of graphs and diagrams

A graph is called connected if its geometric realization is a connected space. Another important type of graphs are the so-called one particle irreducible (1PI) graphs. A graph Γ is called one particle irreducible if it is connected and after cutting any of its inner edges it remains connected. Here cutting of an inner edge determined by a pair of flags f = σ ( f ) means to change the second structure map σ to a new map σ such that σ ( f

) := σ ( f ) if f = f and f = σ ( f ), and σ ( f ) := f if f = f or f = σ ( f ).
We shall impose in addition the requirement that 1PI graphs have no tadpoles and have at least two vertices (or equivalently, at least one inner edge).

If the body of a decorated graph is connected, then the graph is also called connected. Similarly a decorated graph is called 1PI if its body is 1PI.

e) Operations on graphs and diagrams

A subgraph of a graph Γ is a subset J ⊆ vert(Γ ). It determines a graph Γ J as follows: the set of vertices of Γ J is vert(Γ J ) := J ⊆ vert(Γ ). The set of flags of Γ J is flag(Γ J ) := s -1 (J) ≡ s -1 vert(Γ J ) and we set the map s J : flag(Γ J ) → vert(Γ J ) to be the restriction of the map s. The map σ J : flag(Γ J ) → flag(Γ J ) coincides with σ whenever f and σ ( f ) belong to flag(Γ J ): such pairs { f , σ ( f )} of different flags are the inner edges of the subgraph. For the remaining f ∈ flag(Γ J ) we set σ J ( f ) = f and they are the outer edges of the subgraph. Note that the outer edges of the graph Γ J are either outer edges of Γ attached to a vertex in J or they are inner edges of Γ with only one end belonging to J.

If the graph Γ is colored then the graph Γ J determined by a subgraph J has an induced coloring defined just by the restrictions of the coloring maps c v and c f to vert(Γ J ) and flag(Γ J ), respectively.

If the graph Γ is enumerated, then the graph Γ J has an induced enumeration provided by the unique monotonically increasing isomorphism ν(J) ∼ = {1, . . . , |J|}.

Another important operation on graphs is the contraction of a subgraph. For every graph Γ and its subgraph J ⊆ vert(Γ ) we define the contracted graph Γ /J as follows. We introduce a new vertex v J , which for the sake of definiteness can be identified with the set J. Then we set

vert(Γ /J) := vert(Γ )\J ∪ {v J } , flag(Γ /J) := f ∈ flag(Γ ) if s( f ) and s(σ ( f )) ∈ J then f = σ ( f ) ≡ flag(Γ ) f ∈ flag(Γ ) s( f ), s(σ ( f )) ∈ J and f = σ ( f ) ,
in other words, flag(Γ /J) contains all the flags of flag(Γ ) except those ones that form the inner edges of the graph Γ J . The structure maps s Γ /J and σ Γ /J are defined as follows:

s Γ /J ( f ) := s( f ) if s( f ) / ∈ J and s Γ /J ( f ) := v J if s( f ) ∈ J , σ Γ /J := σ vert(Γ /J) ,
where the second identity is provided by the fact that flag(Γ /J) is defined as a σ -invariant subset. To summarize, the graph Γ /J is obtained by shrinking all the vertices in J to a single vertex v J and removing all the internal lines of Γ J . Note that if the graph Γ is connected or 1PI, respectively, then so is Γ /J. If the graph Γ is colored, then for every pair (J, L) consisting of a subset J ⊆ vert(Γ ) and an element L ∈ Colv we can define a colored contracted graph Γ /(J, L) constructed as the graph Γ /J endowed with the following coloring maps c v and c f :

c v vert(Γ )\J := c v vert(Γ )\J , c v (v J ) := L , c f := c f flag(Γ /J) .
Finally, if we have an enumerated graph Γ , then the contracted graph Γ /J will be endowed with the enumeration provided by the unique monotonically increasing isomorphism

ν(vert(Γ )\J) ∪ {min ν(J)} ∼ = {1, . . . , n -|J| + 1} .
Note that if the graph Γ has no tadpoles, then the graphs Γ J and Γ /J have no tadpoles for every subgraph J of Γ .

f) Isomorphic diagrams

Let us introduce the notion of an isomorphism of two enumerated diagrams Γ and Γ . We shall treat two such diagrams as identical. An isomorphism of graphs Γ ∼ = Γ consists of a pair of bijections j v : vert(Γ ) ∼ = vert(Γ ) and j f : flag(Γ ) ∼ = flag(Γ ), which commute with the structure maps s, s and σ , σ , respectively. In other words, j v • s = s • j f and j f • σ = σ • j v . An isomorphism of colored graphs is an isomorphism of graphs, which in addition satisfies c v = c v • j v and c f = c f • j f (compatibility with the coloring maps). Finally, an isomorphism of enumerated colored graphs is an isomorphism of colored graphs which preserves the enumeration. Let Dgm(n) := set of all equivalence classes of isomorphic enumerated colored graphs with n vertices.

(15)

g) Combinatorial Feynman rules, or, representation of diagrams in a monoid

There is a convenient one-to-one correspondence between the equivalence classes of isomorphic enumerated colored graphs and the elements (monomials) of a commutative monoid. This construction follows on an abstract algebraic (or combinatorial) level the so called "Feynman rules" that assign in QFT to every Feynman diagram an analytic expression. Let M(n) := the free commutative monoid with a set of generators

{1, . . . , n} × Colv ∪ {1, . . . , n} × Colf ∪ {1, . . . , n} × Colf ×2 . ( 16
)
Let us introduce "physical" names and notation for the elements in the above three disjoint sets. We call the elements of Colf the basic "fields" and denote them by φ , ψ, etc. Then the element (i, φ ) ∈ {1, . . . , n} × Colf will be denoted by φ (i) and called a "field at the point i". Next, the elements (i, φ ; j, ψ) ∈ {1, . . . , n} × Colf ×2 will be denoted by C φ ,ψ (i, j) and will be called "propagators". Finally, the elements L ∈ Colv will be called "interactions" and a pair (i, L) ∈ {1, . . . , n} × Colv will be called an interaction at the point i and will be denoted by L(i).

Thus, in the above notations the set of generators (16) for the monoid M(n) reads:

L(i) L ∈ Colv, i = 1, . . . , n ∪ φ (i) φ ∈ Colf, i = 1, . . . , n ∪ C φ ,ψ (i, j) φ , ψ ∈ Colf, i, j = 1 . . . , n . (17)
Now, to each enumerated colored graph Γ we assign a monomial in M(n) in the following way. To the vertex ν -1 (i) (i.e., to the vertex with number i) we assign L(i) if its color is L ∈ Colv. To each outer edge attached to the vertex ν -1 (i) we assign φ (i) if the color of the corresponding flag is φ ∈ Colf. To each inner edge connecting the vertices ν -1 (i) and ν -1 ( j) we assign C φ ,ψ (i, j) if the colors of the flags attached to ν -1 (i) and ν -1 ( j) are φ and ψ, respectively. Finally, we multiply all the above obtained generators in M(n). The resulting monomial in M(n) is denoted by M Γ .

Example 3. In the case of Example 2 with vertex enumeration ν(0

) = 1, ν(1) = 2 we have M Γ = ψ(1) ψ(2) L(1) L(2)C A,A (1, 2)C ψ,ψ (1, 2) ,
where we denoted now the colors by letters: L := • ∈ Colv and A := := , ψ := .

Proposition 2. The correspondence Γ → M Γ is a bijection Dgm(n) ∼ = M(n), i.e., it is a one-to-one correspondence between the equivalence classes of isomorphic enumerated colored graphs with n vertices and the elements of the monoid M(n).

Proof. It is clear that Γ → M Γ maps injectively the equivalence classes of diagrams to elements of M(n). To see that this map is surjective one constructs for every element of M(n) a diagram that reproduces this monomial.

The universal contraction operad

Recall that Dgm(n) is the set of all equivalence classes of isomorphic enumerated colored graphs with n vertices. Let us define

R(n) := Hom K K (Dgm(n)) , K (Colv) ∼ = K Dgm(n)×Colv , (18)
where K (I) stands for the vector space over the ground field (ring) K spanned by a basis indexed by I and the existence of the second canonical isomorphism follows in the case when Colv is a finite set, which we shall assume further. This canonical isomorphism is provided by the decomposition

Q(Γ ) = ∑ L ∈ Colv q(Γ , L) L , (19)
where Q ∈ R(n). We shall treat the isomorphism at the second equality in (18) as an identification, R(n) = K Dgm(n)×Colv . We call the elements of R(n) contraction maps. This is motivated by the fact that they can be thought of as prescriptions for contracting subgraphs as we shall describe below.

Note that the action of the permutation group S n on Dgm(n) induces an action on R(n). We shall endow now the so-defined S-module R = {R(n)} n 1 with a structure of a symmetric operad.

To this end we shall define the partial composition maps:

• i : R(n) ⊗ R( j) → R(n -1 + j) , (20)
i = 1, . . . , n, j = 1, 2, . . . . Let us introduce for every enumerated diagram Γ the subsets of vertices J := J(i, j) ⊆ vert(Γ ):

J ( ≡ J(i, j)) := ν -1 ( ) = i + 1, . . . , i + j . (21)
We define for Q ∈ R(n), Q ∈ R( j) and Γ that is a representative of an isomorphism class in Dgm(n -1 + j):

(Q • i Q )(Γ ) = ∑ L ∈ Colv q (Γ J , L) Q Γ /(J, L) , (22)
where

Q (Γ J ) =: ∑ L ∈ Colv q (Γ J , L) L . ( 23
)
Note that if we set

Q (Γ ) = ∑ L ∈ Colv q (Γ , L) L , Q(Γ ) = (Q • i Q )(Γ ) = ∑ L ∈ Colv q(Γ , L) L, (24)
then Eq. ( 22) reads

q(Γ , K) = ∑ L ∈ Colv q (Γ J , L) q Γ /(J, L), K . ( 25
) Proposition 3. ([4]) R = {R(n)} n 1 is a symmetric operad.
The proof is straightforward checking and we omit it.

6 Suboperads in R and concrete combinatorial models of Quantum Field Theory

In the previous section we have defined a universal operad R on decorated graphs, which can include, at the combinatorial level, any concrete model of Quantum Field Theory (QFT) provided that we have sufficiently many colors in Colv and Colf. So, the QFT models can be considered as particular suboperads of R. Describing these suboperads can be quite cumbersome in general and we shall do this in several steps. At each step we shall impose certain restrictions on the contraction maps Q ∈ R(n). These restrictions include, in particular, requirements that Q should vanish on certain classes of diagrams that are "not admissible for contraction". For instance, excluding tadpoles was a first example of such a restriction on diagrams. It was "stable with respect to contractions and subdiagrams" and hence, it defined a suboperad in R. More precisely, the statement is that the subspaces in R(n) for every n = 1, 2, . . . , which consist of those contraction maps that vanish on diagrams with tadpoles, form a suboperad.

Let us formulate the argument in a more general principle:

Proposition 4. ([4]) Let Φ = {Φ(n)} n 1 be a system of subsets Φ(n) ⊆ Dgm(n) × Colv for n = 1, 2, . . . and let us define R Φ (n) = K Φ(n) ⊆ K Dgm(n)×Colv ≡ R(n) , R Φ (n) ≡ Q = ∑ q L ∈ R(n) q (Dgm(n)×Colv)\Φ(n) = 0 , (26)
where we use the expansion (19) and embeddings of type Then the following conditions are equivalent:

K A → K B for A ⊆ B,
(i) The system R Φ = {R Φ (n)} n 1 is a suboperad of R.
(ii) Each subset Φ(n) is S n -invariant and the system {Φ(n)} n 1 has the property

(Γ J , L) ∈ Φ(|J|) and (Γ /(J, L), K) ∈ Φ(n -|J| + 1) ⇒ (Γ , K) ∈ Φ(n) (27)
for every Γ ∈ Dgm(n), J ⊆ vert(Γ ) and K, L ∈ Colv.

Corollary 1. The following systems form a suboperad in R:

R 1PI (n) := Q ∈ R(n) Q(Γ ) = 0 if Γ is not 1PI .
Let us give another example for a restriction on diagrams that induces a suboperad. Let us consider a non-empty subset

E ⊂ Colf ×2 and call it a set of admissible connections. A colored graph Γ is called E -admissible if for all flags f ∈ flag(Γ ) such that f = σ ( f ) we have (c f ( f ), c f (σ ( f ))) ∈ E .
Or in other words, if the pairs of colors of the flags corresponding to the inner edges are contained in E . As an application of Proposition 4 we get: Corollary 2. Let E be any symmetric subset in Colf ×2 and let R E (n) be the space that consists of all contraction maps Q ∈ R(n), which vanish on all diagrams that either are not E -admissible, or have tadpoles. Then R E (n) n 1 is a suboperad of R.

Note that in Corollaries 1 and 2 the sets Φ(n) are of the form

Φ(n) = Dgm (n) × Colv
for some subsets Dgm (n) ⊆ Dgm(n). In this case condition (27) reads

Γ J ∈ Dgm (|J|) and Γ /J ∈ Dgm (n -|J| + 1) ⇒ Γ ∈ Dgm (n) . and R Φ is R Φ (n) = Q ∈ R(n) Q Dgm(n)\Dgm (n) = 0 ≡ Hom K K (Dgm (n)) , K Colv = K Dgm (n)×Colv .
Example 4. Let us introduce an example of the set E for the case of Quantum Electrodynamics (QED). In this case we use three colors for flags Colf = set of admissible connections is:

E = , , .
The diagram of Example 2 was thus E -admissible for QED and as there we can use for edges single colors, one with no orientation and one with orientation. The nonoriented lines are called "photon lines" and the oriented lines are called "electron lines".

Our next "selection rule" for contraction maps is by the type of vertices. A vertex is a colored graph with one vertex and no tadpoles. So, it contains only outer edges which are called corolla of the vertex. The number of the external edges of the vertex is called its valency.

Let V ⊆ Dgm(1) be a set of vertices. We call the set V types of vertices in the theory. Let us define then the system

Φ V = {Φ V (n)} n 1 Φ V (n) = (Γ , L) ∈ Dgm(n) × Colv ∀J ⊆ Γ if |J| = 1 then Γ J ∈ V and Γ /(vert(Γ ), L) ∈ V .
It follows that Φ V satisfies condition (ii) of Proposition 4 and hence,

R V := R Φ V , is a suboperad of R.
Thus, a physical theory can be defined as intersection of the operads

R E ,V := R 1PI ∩ R E ∩ R V . (28)
In the next section we shall consider the main examples of physical theories.

Remark 2. If {Φ i } i∈I is a collection of systems Φ i = {Φ i (n)} n 1 each satisfying condition (ii) of Proposition 4 then i∈I R Φ i = R Φ where Φ = {Φ(n)} n 1 with Φ(n) = i∈I Φ i (n) ,
and Φ also satisfies condition (ii) of Proposition 4.

7 The group related to the contraction operad and its representation in the group of formal diffeomorphisms on the space of interactions

Having defined a symmetric operad R for each particular QFT model we have automatically a group G(R) associated to it. This group is precisely the operadic construction of the renormalization group.

Notions of renormalization group

There are several widespread notions of renormalization group in physics and they do not lead to equal objects although they are closely related to each other. We shall review below some of them. For recent related works we refer the reader to [START_REF] Stora | Causalité et Groupes de Renormalisation Perturbatifs[END_REF], [1].

In renormalization theory a physical quantity U (an observable for instance, or a correlation function in QFT) is derived as a function U = U(κ 1 , . . . , κ N ; ε) (≡ U( → κ ; ε)) of various parameters including:

• physical constants κ 1 , . . . , κ N . In QFT these are called coupling constants.

• An additional subsidiary parameter ε > 0 called a regularization parameter. It makes meaningful the value of U(κ 1 , . . . , κ N ; ε) that is usually ill-defined for ε → 0. The latter limit corresponds exactly to the actual physical value of U and the purpose of the renormalization is to understand how to do it. • There might be further variables but we consider them as a "part" of U (so that U is then valued in some vector or function space).

Furthermore, in perturbation theory, one has defined U only as a formal power series in the coupling constants

U( → κ ; ε) = ∞ ∑ n = 0 1 n! N ∑ i 1 ,...,i n = 1 U i 1 ,...,i n (ε) κ i 1 • • • κ i n , (29)
with coefficients U i 1 ,...,i n (ε) that are functions in ε > 0. The renormalization issue now is to find such a change of the physical parameters:

→ κ = → K ( → κ ; ε) , κ i = ∞ ∑ n = 1 1 n! N ∑ i 1 ,...,i n = 1 K i;i 1 ,...,i n (ε) κ i 1 • • • κ i n , (30)
again as a formal power series, so that after the substitution 2

U ren ( → κ ; ε) := U → K ( → κ ; ε); ε = ∞ ∑ n = 0 1 n! N ∑ i 1 ,...,i n = 1 U ren i 1 ,...,i n (ε) κ i 1 • • • κ i n , (31)
the resulting coefficients U ren i 1 ,...,i n (ε) would have a finite limit for ε → 0. We set the final renormalized physical quantity U ren to be

U ren ( → κ ) := lim ε→0 U ren ( → κ ; ε) . (32)
The existence of such a formal diffeomorphism

→ κ = → K ( → κ ; ε) (30)
for a given in advance series U( → κ ; ε) (29) so that the limit (32) exists is far from being a trivial statement. This phenomena is called renormalizability of U. The physical interpretation of this procedure is that we pass by the change (30) to a new set of coupling constants called "renormalized couplings" so that the initial "bare couplings" become infinite (meaningless) for ε → 0.

Still, the above renormalization procedure has a built in ambiguity. Namely, if

we have one solution

→ K ( → κ ; ε) (30) of this problem then any composition → K 1 ( → κ ; ε) = → K → X ( → κ ); ε with a formal diffeomorphism → X ( → κ )
will also be a solution. Thus, the group of formal diffeomorphisms of the couplings → κ appears naturally as acting on the renormalization schemes. This is the first notion of a renormalization group. It is simply the group of formal diffeomorphism.

We see that the above concept of renormalization is rather general. It leads also to the most primary concept of a renormalization group and so, it should be related to any other such notion. More precisely, any other notion of a renormalization 2 in terms of formal power series; note that the series → K ( → κ ; ε) starts from n = 1 but for U( → κ ; ε) we do not have such a restriction group should have a representation (a homomorphism) in the group of formal diffeomorphisms of the coupling constants. In this case we speak about "renormalization group action", i.e., it is an action of the corresponding group by formal diffeomorphisms of the couplings.

We pass now to a second notion of the renormalization group that is specific for QFT and it is finer than the above one. In QFT there are additional technical features of the renormlization procedure. Namely, each of the terms U i 1 ,...,i n (ε) in series ( 29) is additionally expanded in a finite sum labeled by a Feynman graph with n vertices. The renormalization adds to every diagram contribution a counter-term together with recursively determined counter-terms for subdiagrams. Without going more into the details we will only mention that the ambiguity in the renormalization in QFT is described exactly by contraction maps introduced in Sect. 5. So, we obtain now a finer notion of renormalization group that is formed by sequences of contraction maps. One further shows that the composition in this group is exactly given by the rule following from the operadic structure on contraction maps. The latter is shown in [START_REF] Nikolov | [END_REF]Sect. 2.6] in a more general context of renormalization than the graph-combinatorial one.

Thus, from this second perspective the renormalization group appears exactly as a group related to the contraction operad on Feynman diagrams. Then, as explained above, there should be related a "renormalization group action", i.e., a homomorphism from this group to the group of formal diffeomorphisms of the couplings. The existence and the derivation of this homomorphism follow also from the general renormalization theory and are not a part of the present work. However, our result is that the resulting homomorphism corresponds to an operadic morphism via the functor established in Theorem 1. Let us summarize all this:

There is an operadic morphism, Ξ : R E ,V → End R V , from the contraction operad to the operad End R V over the vector space spanned by the set of type of vertices V . The latter set indexes the set of coupling constants in the QFT model that is determined by the combinatorial data (E , V ). The induced map between the related groups

G(Ξ ) : G R E ,V → G End R V ∼ = FDiff R V (33)
coincides with the renormalization group action determined from the renormalization theory.

In the subsequent subsections we will construct the morphism Ξ : R E ,V → End R V . We shall continue our considerations on a general ground field (ring) K but the above application uses the case K = R.

Bosons and fermions

We introduce a subdivision of the set of fields, i.e. the set Colf of flags' colors, into two disjoint subsets called bosons and fermions. According to this we assign (Z/2Z)-parities to the set of generators (17) of the monoid M(n). For a bosonic φ the element φ (i) is even and for fermionic φ , φ (i) is odd. The parity of the propagator C φ ,ψ (i, j) is the sum of the parities of the coupled fields φ and ψ. Usually bosons are coupled only to bosons and fermions -to fermions, so that the propagators are then always even. Finally, the interactions L(i) are even as well.

Recall that we introduced in Sect. 4 g a canonical isomorphism Dgm(n) ∼ = M(n) between the set Dgm(n) of all classes of isomorphic enumerated colored diagrams with n vertices and the elements in the free monoid M(n) generated by the set (17). Let us introduce the linear envelope of the monoid M(n):

M (n) := K (M(n)) ∼ = K (Dgm(n)) , (34)
which is thus an algebra. 3 In the more general case of presence of fermions we redefine the algebra structure on M (n) (34) and set M (n) := the graded commutative algebra generated by the set (17).

Note that in all the constructions up to now the division of the fields (i.e., the set Colf) into bosons and fermions is inessential.

The Wick generating operator of diagrams

Let us assume first that we have a theory only with bosons so that the algebras M (n) are commutative.

Let us have n vertices I 1 , . . . , I n ∈ V and consider them as one enumerated colored graph that is completely disconnected (i.e., it has no inner lines). The monomial in M(n) corresponding to this diagram is thus

I 1 (1) • • • I n (n) ≡ I 1 ⊗ • • • ⊗ I n ,
where the number in bracket "( j)" indicates the number assigned to the corresponding vertex. Denote Wick E n (I 1 , . . . , I n ) := ∑ all possible ways of connecting the vertices

I 1 (1), . . . , I n (n) into E -admissible enumerated colored graphs with no tadpoles = I 1 (1) • • • I n (n) + • • • , (36)
where E ⊆ Colf ×2 is a set of admissible connections as defined in Sect. 6. This defines us a multilinear map

Wick E n : K V ×n → M (n) . Proposition 5. ([4]) Under the isomorphism Dgm(n) ∼ = M(n) (Proposition 2) the following equation holds Wick E n (I 1 , . . . , I n ) = ∏ 1 i < j n exp ∑ (φ ,ψ)∈E C φ ,ψ (i, j) ∂ 2 ∂ φ (i)∂ ψ( j) I 1 (1) • • • I n (n) . (37)
In the presence of fermions Eq. (37) continues to generate the terms in the right hand side of Eq. (36) but with some signs that depend on the order of writing of the remaining generators of M (n). The derivatives ∂ ∂ φ (i) are understood as left Grassman derivatives for odd φ (i).

Construction of operadic morphism

Ξ : R E ,V → End K V
The operadic morphism Ξ : R E ,V → End K V consists of a sequence of linear maps

Ξ n : R E ,V (n) → End K V (n) ≡ Hom K V ⊗n , K V . (38)
The ansatz for Ξ n is

Ξ n (Q)(I 1 ⊗ • • • ⊗ I n ) = Q Wick E n (I 1 , . . . , I n ) ∈ K V , (39)
where Q ∈ R E ,V (n) ⊆ R(n) is generally given by Eq. ( 19) and Q is then set to be

Q(Γ ) = ∑ L ∈ Colv q(Γ , L) Γ (vert(Γ ), L) , Q : K (Dgm(n)) → K Dgm(1) , (40)
i.e., Q(Γ ) contracts the diagram Γ to a sum of single vertices according to the color prescription of Q : K (Dgm(n)) → K (Colv) . Let us explain by words the meaning of Eq. ( 38). The value of Ξ n (Q)(I 1 ⊗ • • • ⊗ I n ) is a sum of single vertices obtained by making first a sum over all possible ways of connecting the vertices I 1 (1), . . . , I n (n) into enumerated diagrams; then we contract each of the terms in the latter sum to a sum of single vertices via Q. Shortly speaking, Ξ n (Q)(I 1 ⊗ • • • ⊗ I n ) is the Q-contraction of all possible connections of I 1 , . . . , I n into diagrams.

Outlook

We make here a connection with the Connes-Kreimer Hopf algebra of "formal diffeographisms" ( [2]), which in details will appear in a forthcoming work.

The first step towards the comparison with the Connes-Kreimer approach is to study the dual (commutative) Hopf algebra to the Lie algebra associated with a symmetric operad. In fact, it can be associated directly to a symmetric co-operad. When this construction is applied to the contraction operads on diagrams we obtain a Hopf algebra that is very close to the Connes-Kreimer Hopf algebra. However, there is an important difference. On a technical level, in our approach a subdiagram is always contracted to a vertex, while in the Connes-Kreimer theory some subdiagrams that have two external lines can be contracted also to an edge with no intermediate vertex.

The origin for this difference comes from physics. The Connes-Kreimer Hopf algebra incorporates an additional step in the renormalization called a "field renormalization". Let us briefly explain this. Our set of vertices V corresponds to all the monomials in the Lagrangian of a given QFT model. Some of these vertices of valence two correspond to quadratic terms in the Lagrangian, which are called "kinetic terms" since they basically determine the propagators. For this reason in physics there are no physical parameters related to these terms: we always normalize them with some standard normalization coefficients like

1 2 (∂ φ ) • (∂ φ ) , ψ(γ • ∂ )ψ ,
for a scalar and a spinor field, respectively (γ • ∂ being the Dirac operator). On the other hand, as a result of the renormalization the coefficients in front of these kinetic terms are changed (renormalized). Then we absorb this change by a redefinition of the field strengths. For instance, in the above examples we pass to new fields φ = Z φ φ , ψ = Z ψ ψ and ψ = Z ψ ψ so that the kinetic terms are changed by Z 2 φ and Z ψ Z ψ , respectively, in such a way that compensate the renormalization change.

h ν;µ 1

 1 ,...,µ n = ∑ P ∈ Part{1,...,n} N ∑ ρ 1 ,...,ρ k = 1

2 P

 2 (n) and the group and pre-Lie products on this set are just • (9) and * (11) truncated up to order m.

  The geometric realization is: Example 2. A decoration for the graph in Example 1 is provided by Colv = {•}, Colf =, and coloring maps:

  which are defined by (x a ) a ∈ A → (y b ) b ∈ B such that y a = x a for a ∈ A and y b = 0 for b ∈ B\A.

Proposition 6 .

 6 ([4]) Equation (40) determines an operadic morphism.

However, we remark that the algebra structure induced by the monoid structure of M(n) is quite different from the algebra structure on the space of diagrams that is usually used in the Connes-Kreimer approach.

Acknowledgements We thank Dorothea Bahns, Kurusch Ebrahimi-Fard, Alessandra Frabetti, Klaus Fredenhagen and Raymond Stora for fruitful discussions. The work was partially supported by the French-Bulgarian Project Rila under the contract Egide-Rila N112. N.N. thanks the Courant Research Center "Higher order structures in mathematics" (Göttingen) and the II. Institute for Theoretical Physics at the University of Hamburg for support and hospitality.


Claudio Freire
email: claudio-daniel.freire@inria.fr

Alina Quereilhac
email: alina.quereilhac@inria.fr

Thierry Turletti
email: thierry.turletti@inria.fr

Walid Dabbous
email: walid.dabbous@inria.fr

Automated deployment and customization of routing overlays on PlanetLab

Keywords: networking, overlays, PlanetLab, NEPI

PlanetLab testbed is widely used to evaluate protocols and applications under realistic Internet conditions, but this realism comes at the cost of uncontrolled topology and traffic behavior. The use of overlay networks on PlanetLab can solve this problem by giving more control to the experimenter. However, manually creating such overlays is far from simple, and existing solutions are either not available for all PlanetLab nodes, or lack support for low level overlays. Deployment and customization of overlay architectures are also poorly supported. In this paper we present a flexible solution to support overlay networks on Plan-etLab, providing deployment automation, tunneling, routing, and traffic shaping capabilities. By building our solution into NEPI, a general framework for network experimentation, which automates design, deployment, and management of experiments, we simplify the complexity of building overlays on PlanetLab, and foster reusability and extensibility though NEPI's modular structure.

Introduction

PlanetLab [START_REF] Chun | PlanetLab: an overlay testbed for broad-coverage services[END_REF] is a globally distributed testbed composed of many nodes connected to the Internet. It provides support for the development of new network technologies, enabling researchers to evaluate new protocols and applications under realistic Internet conditions. It is difficult, or even impossible, to achieve the same level of realism using alternative experimentation environments, such as simulators [START_REF] Floyd | Difficulties in simulating the internet[END_REF], and this is what makes PlanetLab so valuable. However, this realism comes at the cost of a lack of control over the many factors that influence the outcome of an experiment, such as links, nodes, and external traffic conditions, since the researchers have no control over the Internet itself.

The use of overlay topologies on top of the Internet can mitigate this problem by giving more control to the experimenters. Overlays can be used to force specific routing topologies [START_REF] Jannotti | Overcast: Reliable Multicasting with an Overlay Network[END_REF], or to analyze real traffic conditions [START_REF] Subramanian | OverQoS: An Overlay based Architecture for Enhancing Internet QoS[END_REF][START_REF] Andersen | Resilient overlay networks[END_REF] with a degree of fault isolation.

Still, creating overlays on top of PlanetLab is a non-trivial task because of the constraints imposed by the type of network virtualization [START_REF]Linux-VServer[END_REF][START_REF] Mark | VNET: PlanetLab Virtualized Network Access[END_REF] used to allow multiple experiments to run independently in the same nodes. Setting up routes, tunnels, or IP filters, cannot be achieved by simply invoking appropriate system calls as in classical (non-virtualized or fully virtualized) environments, but requires instead the use of PlanetLab-specific tools.

Previous efforts have been made to enable the creation of overlay networks on PlanetLab, which were mainly focused on the tunneling and routing aspects. Existing solutions like PL-VINI [START_REF] Bavier | In VINI veritas: realistic and controlled network experimentation[END_REF] are limited because they depend on extensions or infrastructure that is not available for all nodes, and thus they do not currently work on the whole PlanetLab network. Other alternatives like Splay [START_REF] Leonini | SPLAY: distributed systems evaluation made simple (or how to turn ideas into live systems in a breeze[END_REF], do not suffer from this limitation, but can only be used with application-level overlays. While these solutions do provide enabling technology to build overlays on top of PlanetLab, they do not solve the heavy load of manual work involved in the customization and deployment of concrete overlay experiment scenarios. In general, they do not provide enough tools to easily customize overlays, and only perform a subset of the tasks needed to run and manage experiments on top of them.

In this paper we present a solution for automatic creation and customization of overlay experiment scenarios on PlanetLab, based on NEPI [START_REF] Lacage | NEPI: using independent simulators, emulators, and testbeds for easy experimentation[END_REF][START_REF] Quereilhac | NEPI: An Integration Framework for Network Experimentation[END_REF], the Network Experimentation Programming Interface. Similar to other tools, our work enables the creation of virtual links over the Internet, allowing both, layer-2 switching and layer 3-routing, between PlanetLab nodes. Nevertheless, by building our solution into NEPI, we provide support for the different steps involved in the construction of overlay experiment scenarios, integrating the design, configuration, and automatic deployment on top of PlanetLab in one single tool. We refer to this aspect of experimental overlay construction as deployment automation. Moreover, our solution provides all the necessary mechanisms for overlay customization, including custom queues and transmission mechanisms, and the functionalities required to run applications in the overlay, like IP routing.

Efficient and flexible tunneling between arbitrary PlanetLab nodes is accomplished by providing several tunneling alternatives. Like RiaS [START_REF] Lischka | RiaS: overlay topology creation on a PlanetLab infrastructure[END_REF] and Trellis [START_REF] Bhatia | Trellis: a platform for building flexible, fast virtual networks on commodity hardware[END_REF], we support layer-2 and layer-3 tunnels with options for UDP, TCP and GRE encapsulation. However, in contrast with previous work, our solution does not require specially tailored nodes, and can be deployed in any node in the PlanetLab network.

Routing table manipulation was not possible before due to the lack of an appropriate system interface. We enhanced routing capabilities in PlanetLab by extending the vsys [START_REF] Bhatia | Vsys: A Programmable sudo[END_REF] interface to allow scalable, secure, and cooperative manipulation of nodes' routing tables, a capability on top of which our solution builds application-transparent overlay networks.

Our solution was designed to enable the use of experimental queuing and aggregation methods with low implementation overhead. It allows the researcher to easily perform traffic shaping within experimental overlays.

Using these tools, researchers can experiment with routing overlays on Plan-etLab with minimal effort, and through NEPI they can perform the experiments repeatedly and automatically in a controlled way.

The focus of this paper will be set on the techniques used to support deployment automation, tunneling, routing, and traffic shaping capabilities for the construction of routing overlays on PlanetLab using NEPI, which we consider the be the core contributions of this work.

The rest of the paper is organized as follows: we begin by discussing the challenges involved in the development of our solution, then we cover the implementation details of NEPI overlay construction and customization support for PlanetLab. We finally evaluate the solution with a concrete use case showing how the tools we develop can benefit to the evaluation of networking protocols with increased accuracy.

Related Work

Two of the most complete previous solutions for low-level overlay deployment in PlanetLab are PL-VINI [START_REF] Bavier | In VINI veritas: realistic and controlled network experimentation[END_REF] and RiaS [START_REF] Lischka | RiaS: overlay topology creation on a PlanetLab infrastructure[END_REF]. Both have serious drawbacks that limit their usability.

PL-VINI is an implementation of a virtual network infrastructure on Plan-etLab, that uses User Mode Linux virtual machines [START_REF]User-mode Linux[END_REF] to provide full network virtualization for independent experiments running in the same node. Contrary to the Linux-VServer [START_REF]Linux-VServer[END_REF] container-based virtualization approach used natively in PlanetLab, in PL-VINI, virtual machines in the same node have direct access to the kernel network stack, making it possible to trivially manipulate routing tables and create tunnels without interfering each other.

PL-VINI has a good performance and enables to easily create layer-2 overlay topologies, but only around 40 nodes out of the many (1040) nodes in PlanetLab support it. It depends on a set of extensions to PlanetLab that have not been deployed on all nodes, and access to dedicated infrastructure that is also not globally available, making it not suitable for big scale deployments in PlanetLab.

While PL-VINI allows the implementation of custom routing and queuing algorithms, this can only be done through the Click modular router [START_REF] Bavier | In VINI veritas: realistic and controlled network experimentation[END_REF][START_REF] Kohler | The click modular router[END_REF], which precludes the possibility to reuse prototype code. In contrast, our solution was crafted upon the idea of easy re-usability and it does not relinquish overlay customization to a single application, thus it makes the researcher's task of testing prototype algorithms in realistic conditions easier. Furthermore, we provide methods to run the experimental code in any PlanetLab node, expanding available resources beyond what PL-VINI provides.

Trellis [START_REF] Bhatia | Trellis: a platform for building flexible, fast virtual networks on commodity hardware[END_REF], is another platform for network virtualization which implements container based virtual machines by using Linux network namespaces [START_REF]Linux network namespaces[END_REF]. Although being the most performant alternative out there, by constructing its tunnel implementation using GRE and kernel-mode switches, it suffers from scalability issues. It creates one bridge and four taps (at least) per tunnel, all connected via virtual (software) switches, stateful and expensive to maintain objects. If every experiment running in a PlanetLab node created such tunnels, the kernel would be overwhelmed very easily. Trellis also does not respect the administrative and fair share bandwidth limits that are imposed per node (and critical) to PlanetLab. Although it does provide bandwidth management, it is not integrated with PlanetLab's mechanism, so large-scale deployment of the technique would be impractical. Like PL-VINI, it also would require heavy changes in the PlanetLab system to enable its wide deployment, and thus it remains an unavailable solution on most PlanetLab nodes.

RiaS [START_REF] Lischka | RiaS: overlay topology creation on a PlanetLab infrastructure[END_REF], on the other hand, is supported by all the nodes in PlanetLab. It is built upon an architecture of user-mode packet forwarders that create a network of point-to-point links with layer-2 tunnels. By operating in user-mode, it scales significantly more graciously than previous approaches under pressure, since it is subject to PlanetLab's fair-share scheduler. However, its support for layer-3 tunneling is limited because nodes with more than one interface (routers) in the overlay topology are required to be PL-VINI nodes, thus for layer-3 tunneling RiaS shares PL-VINI and Trellis limitations.

RiaS is heavily focused on layer-2 experiments, and because of this its architecture is ill-suited for layer-3 overlays. It only implements layer-2 routing techniques, to circumventing PlanetLab nodes' inability to set IP routes at the kernel level for one, and to support experimentation with arbitrary layer-2 protocols. It works more like a switch than a router. This imposes limitations on the experiments, since RiaS by itself provides no layer-3 routing, and nodes cannot reach other networks. Since RiaS does it all in user mode, it incurs heavy CPU overhead, resulting in artificial bandwidth and scalability limits, and packet loss well above that experienced in the underlying network. Rias does provide some support for overlay deployment automation, in the form of a Resource Allocator and Virtual Network Mapper tools. Although these tools consider the topology level of an experiment, they do not cover the application level.

Other solutions like Splay [START_REF] Leonini | SPLAY: distributed systems evaluation made simple (or how to turn ideas into live systems in a breeze[END_REF] and Plush [START_REF] Albrecht | PlanetLab application management using plush[END_REF], do not even support low level overlays (i.e. at layer 2 or 3), but rather they build application-level overlays. Splay [START_REF] Leonini | SPLAY: distributed systems evaluation made simple (or how to turn ideas into live systems in a breeze[END_REF] is a good example, as it automates deployment both at topology and application levels, has good performance, and is easy enough to use. However, it only handles packets at the application level. Even its packet loss models apply at the application level, which is an inaccurate rendition of link packet loss in most cases. It is also not able to handle all applications, since they must be written in Ruby using splay-specific support libraries.

PlanetLab support in NEPI was built to address the need to easily create and customize overlays, both at topology and application levels, a problem which current solutions do not fully address.

Challenges

PlanetLab [START_REF] Chun | PlanetLab: an overlay testbed for broad-coverage services[END_REF] uses container-based virtualization to allow multiple experiments to run independently on the same node while sharing its resources. The implementation of network virtualization [START_REF] Mark | VNET: PlanetLab Virtualized Network Access[END_REF], however, has a cost: some tasks are made more complex than in a classical (non-virtualized or fully virtualized) environment. Slivers (isolation units for experiments running in PlanetLab) do not have full root privileges, so system calls to set up routes, tunnels, or IP filters, among others, are forbidden, requiring the use of PlanetLab-specific tools to perform these tasks. These limitations make many of the existing tools for overlay creation unusable within PlanetLab [START_REF] Muir | Privileged operations in the PlanetLab virtualised environment[END_REF].

In order to build overlays on PlanetLab, the first challenge that needs to be addressed is tunneling. Packets have to be captured, encapsulated, and transmitted over the Internet to their destination in a way that is transparent for applications, and neutral for the intervening networks. Since PlanetLab nodes host many slivers, 300 in average, which are container-based virtual machines that share the same network stack, lower layer tunnels have to be implemented to respect network isolation, in an environment of high concurrency.

User mode tunnels have their own challenges too. Since only the kernel knows when a link is congested, and it will happily discard outgoing packets in this case. To avoid packet loss at the kernel's queue, which is undesirable when applying customized queuing, it is necessary to limit packet egress rate to match available bandwidth. But bandwidth can only be guessed, so user mode queues become delicate to use.

Routing packets is another key challenge. Kernel routing table virtualization is not able to handle as many slivers as are normally present in a node, so a technique that shares resources safely is key to achieve routing successfully.

Per-sliver routing, a technique designed for UMTS/3G-connected nodes in PlanetLab in [START_REF] Botta | Providing UMTS connectivity to PlanetLab nodes[END_REF] and embodied as a PlanetLab vsys script, allows slivers to create their own private routing tables. This technique has scalability issues since it only supports 150 concurrent slivers on each node, whereas the average on PlanetLab is around 300.

Another problem that requires special attention is the testbed's unstable and unreliable nature. Nodes can be brought up and down without any warning, or be overloaded and unresponsive, and their state is not always faithfully mirrored in the PLC API which we use for resource discovery. Our automation procedures had to be made resilient on these situations, otherwise deployment of big experiments resulted in unacceptably high failure rates.

PlanetLab Overlays in NEPI

NEPI [START_REF] Lacage | NEPI: using independent simulators, emulators, and testbeds for easy experimentation[END_REF][START_REF] Quereilhac | NEPI: An Integration Framework for Network Experimentation[END_REF] is a framework for network experimentation that automates experiment design, deployment, and control, providing a uniform way of interacting with different testbeds. NEPI provides an experiment description (ED) language that allows researchers to design experiments, both at topology and application levels, by adding and connecting testbed-specific component abstractions, such as nodes and links. New abstractions can be implemented to support other testbeds or to add new functionality.

An experiment controller (EC) entity is in charge of orchestrating the experiment from the given experiment description. The EC is responsible for allocating resources, configuring components, running applications, and retrieving experiment results. It also handles the coordination of the (possibly several) testbeds involved in the experiment. The EC is independent from any specific testbed, providing a large body of pre-existing automation functionality.

Because of these characteristics NEPI was an ideal choice to support automated deployment and overlay customization on PlanetLab. Our work was focused, then, on adding the PlanetLab specific functionality to allow NEPI to deploy experiments on PlanetLab. This not only included implementing the necessary abstractions on NEPI, but also modifying the available interface in PlanetLab to add the required routing and tunnel-enabling functionality.

In this section we will describe how overlays are created and customized on PlanetLab using NEPI. We will also explain the mechanisms developed to support network-level routing overlays in PlanetLab, that is, overlays that route IP or Ethernet packets. Other kinds of overlays are application-specific, and thus require application-specific abstractions that are beyond the scope of our work. The new mechanisms we contributed to PlanetLab to enable routing and tunneling, can be invoked by any user and application through the vsys interface. With them, any PlanetLab user can now easily set up GRE links, and manipulate routing tables. In order to automate deployment of experiments involving overlays, an experiment must first be described in a machine-understandable way. NEPI provides an experiment description language based on interconnecting experiment component abstractions, called boxes. These boxes can be grouped into two categories: topology, and application.

Deployment Automation

To describe the topology-level of a PlanetLab experiment, we added boxes to represent PlanetLab nodes, interfaces, and internet access. Picking nodes is a critical design step. Since experiments can be affected by the presence of overloaded nodes, we allow researchers to specify constraints on various node metrics that will be resolved at deployment time. An experiment could accept any node, or it might require nodes with some amount of CPU or bandwidth unused. Or, the other way around, we might need overloaded nodes, perhaps, if they were trying to evaluate what happens when a node in the network is congested. All those criteria can be useful for reproducing previous experiments.

To describe the application level, we added application and applicationdependency boxes, which can be connected to a node box, and represent an instruction to deploy the application or dependency, and run it on the specified node. Application boxes allow the specification of all the dependencies needed for deployment: packages they depend on, to be automatically installed in the nodes, and user programs to be launched, built and installed if necessary.

NEPI supports the concept of application traces, which capture the output of applications or even network traffic. NEPI can automatically gather all the traces at any point during execution, for inspection or analysis.

In contrast with Splay [START_REF] Leonini | SPLAY: distributed systems evaluation made simple (or how to turn ideas into live systems in a breeze[END_REF] and Plush [START_REF] Albrecht | PlanetLab application management using plush[END_REF], during experiment execution, NEPI acts as a PlanetLab controller which can manage PlanetLab slices (groups of slivers) and execute commands within nodes, rather than an agent that runs directly in PlanetLab. NEPI only gives instructions to PlanetLab nodes the way regular users would, using SSH. In this sense, our solution can be regarded as a big, specialized scripting engine. The main benefits of this approach arise from its flexibility: researchers can easily add functionality to it, and they do not require any modifications made to PlanetLab itself, making it very easy to build a range of reusable experimentation modules for deploying common topologies or utilities in PlanetLab slices. Also, experiments descriptions remain valid and usable for experiment reproduction, since NEPI and PlanetLab are decoupled and changes to one do not usually affect the other Once given access to the slice, NEPI uses the PLC API to perform resource discovery, based on the criteria specified by the researcher in the experiment description, and provision the nodes adding them to the slice.

To map overlay nodes into PlanetLab nodes, we implemented an algorithm that constructs a set of viable hosts for each node, based on explicit and implicit constraints. Implicit constraints include the number of real interfaces as specified in the experiment description, and capabilities as required by the presence or absence of virtual interfaces and custom routing tables. After such a set is built for all nodes in the experiment, a simple backtracking procedure constructs a subset of all viable assignments. Not one solution, but a whole class of solutions are represented in a way that lets NEPI pick the best one in terms of qualitative health metrics, such as node load and reliability. NEPI obatins these node qualitative health metrics, tracked by the CoMon [15] tool, through the PLC API. If apparently healthy nodes turn out not to be so, NEPI adds those "seemingly live" nodes to a blacklist. With these precautions, allocation on nodes with unstable communication is minimized, and thus deployment success rates improve, which is a real problem when deploying large experiments consisting of a great many nodes.

In order to achieve a certain level of reproducibility, we had to take into account the constantly changing landscape of PlanetLab. The controller will record effective running parameters, like node load at the moment of deployment, physical locations, available bandwidth. When those parameters are not constrained by experiment design, effective execution values will provide all the information needed for posterior experiment reproduction, even when resource availability has changed. Later runs can use this information to constrain node selection in a way that resembles prior executions, or that ensures sufficient resource availability.

Once the nodes are successfully added to the slice and become responsive, NEPI coordinates the process of deploying applications and dependencies. Application resources, such as source code, are copied over to a few select nodes, called the build masters. These build masters take care of building applications, and downloading required rpm packages. In this way we avoid inefficient use of PlanetLab's resources -binaries only need to be built once per architecture, and bandwidth can be better utilized by sharing required downloads in a peer-topeer fashion, preferring fast connections over slow ones. The rest of the nodes, the build slaves, wait for their master to be done to copy the resulting binaries and rpms from them.

When everything is ready, the controller launches the applications. The researcher can further interact with the experiment in realtime, modify certain configurations, start and stop applications, and retrieve results though the controller's API.

Tunneling

NEPI supports tunneling both at layer 2 and layer 3, and provides encapsulation over TCP, UDP, and GRE. Encapsulation over GRE is highly efficient since it is supported at the kernel level. UDP and TCP encapsulation, in contrast, requires user-mode packet forwarding, which adds processing overhead. However, it is better suited for overlay customization, since the user-mode packet forwarding daemon used by NEPI has been coded to support easily pluggable user-specified behavior.

The creation of tunnels has two aspects. The first one is the creation and configuration of the virtual interfaces, which is done through PlanetLab's vsys interface. We extended the existing interface to support creation of GRE links, which was previously only possible through Trellis [START_REF] Bhatia | Trellis: a platform for building flexible, fast virtual networks on commodity hardware[END_REF], with all the scalability issues mentioned in Section 2. We also addressed potential conflicts related to concurrent use of GRE tunnels by many slivers, a problem present in Trellis, by marking all GRE packets between any two endpoints as belonging to the slice, and in this way allowing the kernel to de-multiplex traffic belonging to each slice both efficiently and securely, and allowing widespread adoption of GRE tunneling without interference.

We enhanced point-to-point links configuration in PlanetLab by allowing passing the remote endpoint to the kernel when appropriate, and automatically setting point-to-point routes, which is essential in the correct operation of many applications. The system as a whole, though, still needs network-level routes, so a mechanism for routing table manipulation is still necessary and will be discussed in 4.3.

The second aspect of tunnel creation, is the actual forwarding of packets. NEPI deploys a special purpose application for this, tun connect. It creates UDP, TCP or GRE tunnels between two virtual interfaces, a basic building block of more complex topologies. GRE tunnels require no user-mode packet processing, so they perform best. But, when GRE links are inappropriate, such as when custom queues or stream filters are applied, user-space packet forwarding is performed. NEPI only performs packet encapsulation, routing and packet forwarding is done in the kernel, avoiding any kind of heavyweight packet processing that was a limiting factor in previous approaches.

Routing

Connecting network segments requires the presence of routing-capable nodes. That is, nodes that can forward packets to the intended destination IP, for which they need knowledge of the network's topology. There are two main ways to do this: static and dynamic routing.

In static routing, routes are predefined, either manually or automatically, but they do not change. This is the most common case, where routing tables are populated with fixed rules.

In dynamic routing, routing tables are present just as in static routing, but routers communicate with router-specific protocols to dynamically maintain optimum paths. There are many algorithms to do this, so the routing algorithms usually work in user space and are highly customizable, sending routing table updates to the kernel which does the actual forwarding. This mechanism is a compromise between flexibility and performance, with highly customizable routing daemons in user space, and packet forwarding taking place in the kernel, to avoid unnecessary copying and thus achieving higher performance.

In order to support both static and dynamic routing, a mechanism to manipulate the kernel's forwarding information base (FIB) is required. To this end we developed a new PlanetLab-specific interface, the vroute vsys script, that implements the standard IP routing manipulation system calls in a straightforward fashion while enforcing certain rules aimed at maintaining proper separation between slivers. vroute adds entries to the main routing table after validating that the routes will not interfere with other slivers. This is done by checking the private network address space assigned to the slice through the vsys vnet tag. This tag can only be assigned by administrators, who are responsible of making sure that the assigned segments are non-overlapping.

Prior to our work, PlanetLab only provided the sliceip interface to create routing tables for slivers, which only supports 150 concurrent slivers per node, an insufficient amount for the average number of slivers in a node (see Section 2). By using both, the sliceip per-sliver routing, and the new vroute per-node routing methods, we solve the scalability problem and afford every sliver necessary control over the routing tables.

Using the main routing table has the benefit of being limited by the number of rules per node, rather than the number of slivers in a node. In fact, NEPI will pick the vroute method if it does not need many rules, and sliceip if the table is big enough to warrant a separate table, or the routes do not belong to the slice's private address space. With this we hope to make the system scale better to high number of users sharing resources on the same nodes.

In combination with per-sliver routing [START_REF] Botta | Providing UMTS connectivity to PlanetLab nodes[END_REF], our solution creates a scalable and secure way of configuring IP-routing at the kernel-level, that can be widely adopted without disrupting PlanetLab. This means userland routing daemons like olsrd are easily adaptable.

In this way, bandwidths up to 300Mbps have been achieved, enabling highbandwidth, low-overhead, and highly-customized overlays, which were previously only possible in PL-VINI (using the handful PL-VINI-enabled nodes).

Traffic Shaping

In order to support overlay customization, including new queuing policies, userland packet forwarding and routing, like Xorp and Click, and even new tunnelling protocols like OverQoS [START_REF] Subramanian | OverQoS: An Overlay based Architecture for Enhancing Internet QoS[END_REF], we introduced several hooks into the framework in order to let experiments process network packets without having to implement all the low-level details. 3. Customizing overlay packet handling. Interprocess communication is used to send all packets through a user process. Custom queuing, filtering and aggregation algorithms can in this way be applied to the packet stream, both before encapsulation and transmission, and after reception and de-encapsulation. When this is used in combination with the built-in rate limiting options, arbitrary loss models, among other things, can be applied to the overlay.

Stream filters can be arbitrary applications that process the packets flowing through the overlays. They can be used to implement custom queues, packet filters or transformations, tunnelling protocols. These modules can be provided to the tun connect userland packet forwarder, to route all packets through userspecified code. The mechanism only works when userland forwarding is taking place, so it cannot be used with GRE tunnels.

The mechanism was designed so that even previous code not designed to work with NEPI could be used. It takes either Python or C code, and provides several ways in which experiments can process packets. Packets can be rejected by implementing a filtering predicate, or a customized queuing class can be provided that will be used instead of the primitive default FIFO. For more complex processing, a connection to an external process that filters packets can be made, covering most customization scenarios.

External filters can include piping all packets through a shell command, or forwarding them to separate daemons, as would be the case if we wanted to use Click. This is accomplished by writing a small module that returns two file descriptors (i.e. a socketpair) through which all packets are piped. Thus, no matter how a researcher decides to implement the prototype, the same code could be reused for testing within PlanetLab. All this provides a level of flexibility no other framework does.

The tun connect module also performs user-land queuing. PlanetLab does not allow slivers to control virtual interface's queuing parameters, so queuing can be accomplished in user-land by specifying custom queuing sizes or classes. This allows researchers to very easily experiment with new queuing disciplines, as we will demonstrate in 5.1.

Implementing OverQoS in PlanetLab would be trivial with this framework, once the prototype has been written, significantly lowering the cost of experimentation. The only foreseeable drawback of this technique is performance, as the usage of stream filters incurs significant performance overhead.

Evaluation

In order to evaluate the solution in terms of ease of use, effectiveness and practicality, we present an experiment case conducted on PlanetLab using NEPI. We evaluate the practicality of our framework for real research cases by reproducing an experiment from a published paper: POPI [START_REF] Lu | POPI: a user-level tool for inferring router packet forwarding priority[END_REF], a tool for packet forwarding priority inference. It was originally validated in PlanetLab in a costly and laborious way, by probing routes between nodes and then manually requesting information from intermediate providers by contacting their administrators.

We re-validated POPI using NEPI in a controlled PlanetLab overlay, a possibility that was not available at the time the paper by Guohan et al [START_REF] Lu | POPI: a user-level tool for inferring router packet forwarding priority[END_REF] was published: by controlling routing behavior and comparing known overlay characteristics against POPI's inferred ones, we managed to achieve verifiable results, in an automated and effortless fashion.

POPI

POPI [START_REF] Lu | POPI: a user-level tool for inferring router packet forwarding priority[END_REF], which stands for Packet fOrwarding Priority Inference, is a tool that attempts to infer packet priorities in the intervening routers between two endpoints. In the paper by Guohan Lu et al, the tool is evaluated by simulation as a first step, and in PlanetLab as a second step. During the PlanetLab run, however, researchers had to ask ISPs about their routing policies, because they could not otherwise verify that the priorities reported by the tool corresponded to actual prioritization policies. Even then, their success was limited, because not every provider answered, and because the information so gathered was very rough.

We re-evaluated POPI, with the intention to evaluate NEPI's adequacy in creating controlled routing overlays for protocols and application validation. NEPI provides here the ability to create an overlay spanning lossy and congested links, while at the same time granting controllable packet prioritization at selected routing points by the use of customized queuing. Designing the experiment was straightforward. NEPI already provided a reference queue class with TOS support1 , out of which a classifier queue based on IP protocol was rather trivial to derive. We exploited our ability to control routing to introduce a mediating node between two arbitrary PlanetLab nodes. All traffic between the endpoints is routed through this mediating node, which applies a controlled class of queuing, and which should result in the application of recognizable statistical bias to the packet stream. Figure 4 shows the experiment design, which includes deployment of POPI, unmodified, in PlanetLab.

We ran the experiment with numerous queue configurations, with the help of a small script that leverages NEPI's programmatic API. The experiment was run in PlanetLab Europe (PLE) as well as a private PlanetLab-like cluster, allowing us to experiment with different environments with little effort. The experiment took 179 hours to run, but required no supervision. Of 325 runs, only 11 failed to be deployed, because of connectivity issues (the controller was operating from a domestic network), but were automatically retried or flagged as bad runs so they could be skipped when analyzing results.

Since any PlanetLab node would be able to run the experiment, we could have cut experiment run time significantly by running several configurations in parallel, using more nodes instead, and illustrating the convenience of not being limited to using only PL-VINI nodes for routing, as RiaS is. However, this would have undermined our ability to compare against our small, private cluster.

Table 1 shows execution details. We induced multiple connectivity glitches by connecting and disconnecting from the network, and joining and leaving VPNs to stress NEPI's failure recovery capabilities. Within the remaining runs, 32 failed because of problems with POPI's tool itself and produced no results. A vastly lower failure rate can be observed in our dedicated cluster, evidencing that the strain on PLE nodes does have an effect on experiment success. Our experiment was conducted at a particularly busy time of the year, yet failure rates are acceptable, due to NEPI's automated recovery procedures.

runs/sets

Good Bad Fail PlanetLab Europe 142/30 8/0 16/0 Dedicated cluster 172/35 3/0 16/1 Table 1. POPI experiment runs. Good runs are those where NEPI returned a successful code. Bad runs when it did otherwise. Failed runs are good runs that produced no output, in every case, because POPI could not establish the control connection due to connectivity glitches.

POPI could successfully infer queue prioritization in clear channels as long as the different classes had different rate limits, but in instances where protocols were assigned separate classes with equal bandwidth (fair share queuing), POPI could not tell the difference from a plain FIFO queue. There was a certain amount of overpartitioning (cases where POPI inferred more classes than in reality) and underpartioning (cases where POPI failed to infer a class), as expected, although somewhat more frequent than expected according to the original research paper. Table 2 summarizes our results. 2. POPI results, based on PLE runs only. Columns specify the bandwidth at the node with the classifier queue, while rows specify the classifier queue configuration. Marks show sets that contain cases (1) where the correct classification was detected (2) where there was underpartitioning (3) where there was overpartitioning. Marks are ordered according to predominance within the set. "4x TCP" represents a queue with 4 times as much bandwidth allocated to TCP traffic than other kinds.

In our experiment, 256k and 384k cases should not result in any classification, because other nodes were uniformly limited to 256k. Any partitioning there is considered overpartitioning, except when it detects the exact queue configuration. It is interesting to note that TCP priority detection is consistently less precise than with other protocols, as shown by the results of "4x TCP" and "4x U+T 16x I" at 128k. In the former, there was a tendency to overpartitioning, while in the latter TCP was consistently detected as having less priority than UDP. This, after checking the resulting packet captures, could most probably be due to reactive traffic generated by target nodes responding to POPI's synthetic TCP packets. This can interfere with the measurements, by exerting more pressure than expected on the bottleneck queue. This effect is even more prominent in our private cluster, where POPI is generally more precise due to the absence of background traffic. This only highlights the bias experienced in TCP measures, that is less evident when running in PLE.

All the required sources and scripts to reproduce the experiment have been made available on-line. With our tools, researchers can easily (assuming they do have access to PlanetLab) reproduce the experiment, and even build other experiments on top of it. NEPI's experiment description XML contains not only topology information, but also deployment instructions: where to get POPI sources, how to build it, how to patch it if it were required. NEPI's execution XMLs contain valuable details about the resources used to run the experiment. All this results in very strong reproducibility guarantees.

More details, and instructions on how to reproduce this experiment, can be found at: http://www.nepihome.org/wiki/nepi/popiExperiment

Conclusions

In this paper we have presented a framework that increases control over experiments conducted using PlanetLab, allowing researchers to go beyond what previously available tools permitted.

Our solution is based on building flexible routing overlays on top of Planet-Lab. We provide the ability to automate deployment of whole overlay experiment scenarios, and improve the flexibility and scalability of the tunnelling and routing techniques compared to previous approaches used in PlanetLab. Additionally, our solution supports custom traffic shaping and different traffic encapsulation and transmission methods, enabling easy customization of the overlays.

As part of this work, we extended PlanetLab's vsys interface to include scalable and secure mechanisms for routing table manipulation, and creation of GRE links. With these tools, we have shown how to implement low-overhead yet highly customizable routing overlays.

In our use case "POPI", we demonstrated the relevance of our contribution by showing how it enables the researcher to gather experimental information that was previously unavailable to him or her. By choosing to reproduce a previously published experiment case, we proved that our solution is relevant to real research cases, while providing additional value.

A comprehensive technical evaluation of our solution is needed to further validate the extent and limitations of our work. In future work, we will focus on evaluating metrics related to scalability, resource usage, and performance. To this end, we will consider node specific metrics, such as per node maximum bandwidth and resource consumption, as well as global performance and scalability metrics, such as maximum number of concurrent overlays and maximum number of nodes per overlay.

Fig. 1 .

 1 Fig. 1. NEPI-managed PlanetLab overlays. (1) The user creates the Experiment Description (ED) and passes it to the Experiment Controller (EC). (2) The EC uses the instructions in the ED to discover and provision available resources. (3) The EC instructs the allocated PlanetLab nodes to perform compilation and installation of applications. (4) Build masters prepare application data which is then distributed Peerto-Peer among all nodes prior to experiment execution. (5) Results are relayed back to the researcher automatically upon completion.

  Fig.3. Customizing overlay packet handling. Interprocess communication is used to send all packets through a user process. Custom queuing, filtering and aggregation algorithms can in this way be applied to the packet stream, both before encapsulation and transmission, and after reception and de-encapsulation. When this is used in combination with the built-in rate limiting options, arbitrary loss models, among other things, can be applied to the overlay.

Fig. 4 .

 4 Fig. 4. POPI experiment concept. Three PlanetLab nodes connected physically by the Internet, on top of which a routing overlay provides a controllable environment in which to test POPI.

  n/a (1,3) (1) indep. U,T,I (2) (2) n/a (1) n/a Table

  Fig.2. Resource allocation strategy. Available nodes are partitioned into categories defined by the constraints derived from the experiment description. Each node will require assignment from one or more categories. A backtracking algorithm computes a set of solutions represented as an assignment node-to-category. Since each category contains more than one node, the final solution is built using only the healthiest nodes of the category (i.e. taking into account the node reliability).

	Sample Topology			Health Optimization phase
	A min load	B >80% load	C min load		A 10% load Best nodes C 20% load for class	B 100% load 90% rel Best node for class
	10% load 20% load	50% load 70% load	100% load 90% rel 100% load 10% rel	Backtracking	A, C Lightly loaded	B Overloaded
	Lightly loaded 4 nodes	Overloaded 2 nodes

NEPI provides a base queue implementation, which can be attached to network devices in PlanetLab, and defines queuing policies by inspecting the Type Of Service (TOS) field in the IPv4 header.