Olivier Beaumont
email: olivier.beaumont@labri.fr

Nicolas Bonichon
email: nicolas.bonichon@labri.fr

Philippe Duchon
email: philippe.duchon@labri.fr

Hubert Larchevêque
email: hubert.larcheveque@labri.fr

Use of Internet Embedding Tools for Heterogeneous Resources Aggregation

Keywords:

In this paper we are interested in large scale distributed platforms like BOINC, consisting of heterogeneous resources and using Internet as underlying communication network. In this context, we study a resource clustering problem, where the goal is to build clusters having at least a given capacity and such that any two participants to the same cluster are not too far from each other. In this context, the distance between two participants corresponds to the latency of a communication between them. Our goal is to provide algorithms with provable approximation ratios. In such large scale networks, it is not realistic to assume that the whole latency matrix (that gives the latency between any two participants) is known, and we need to rely on embedding tools such as Vivaldi or Sequoia. These tools enable to work on compact descriptions and well described metric spaces in which the distance between two points can be obtained directly from a small amount of information available at each node. We present the Bin Covering under Distance Constraint problem (BCDC for short), and propose dedicated algorithms for this problem for each metric space induced by each of the embedding tools. Then, we propose a comparison of these algorithms based on actual latency measures, that enables to decide which algorithm/embedding tool pair offers in practice for realistic datasets the best balancing between distance prediction and approximation ratios for the resource clustering problem.

I. INTRODUCTION

In this paper, we study the use of two embedding tools for Internet resource clustering in large scale distributed platforms. Internet embedding tools are used to map distributed resources connected through Internet into a simple (usually metric) space. Among the most widely encountered embedding tools in the literature are Vivaldi [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] and Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], [START_REF] Abraham | Reconstructing approximate tree metrics[END_REF]. These tools assign to each resource a position in a simple space, such that the distance (the latency) between any two nodes can be approximated by their distance in the simple space. Of course, another possibility would consist in computing and using the latency matrix L, where L i,j denotes the measured latency between resources i and j. Nevertheless, this approach has two main drawbacks. First, in the context of large scale distributed networks, it is unrealistic to assume that all L i,j values can be determined accurately due to the cost to perform all measures. Second, when using the latency matrix as input, we work in the most general space without any specific topological property. Designing efficient (with good approximation ratios) algorithms in this context turns out to be extremely difficult. On the other hand, embedding tools induce a (small) distortion of latencies, but they enable to work in simpler spaces and therefore to design efficient approximation algorithms. In the context of a given application, such as resource clustering, only the performance of the pair embedding/clustering algorithm is meaningful. In this paper, we consider 3 embeddings : no embedding (direct use of the latency matrix), Vivaldi [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] and Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], [START_REF] Abraham | Reconstructing approximate tree metrics[END_REF]. For each embedding, we design a specific clustering algorithm using the structural properties of the resulting space, and we compare the performance of the embedding/algorithm pair using datasets based on PlanetLab (http://www.planet-lab.org/) latency measurements.

Since Internet latencies space contains a lot of triangular inequality violations [START_REF] Lumezanu | Triangle inequality variations in the internet[END_REF], it can be described as a semimetric space (a space where the distance function does not satisfy the triangular inequality). Thus, it cannot be embedded in a metric space without encountering a loss of accuracy. In fact, Internet latencies space seems to be close to an infra-metric [START_REF] Lebhar | The inframetric model for the internet[END_REF], a space in which the triangular inequality is relaxed in the following way : d(u, v) ≤ ρ. max(d(u, w), d(v, w)) for any triple of nodes (u, v, w). Results presented in [START_REF] Lebhar | The inframetric model for the internet[END_REF] show that most triples satisfy above inequality with ρ = 2, and almost every triples satisfy it with ρ = 10. In this paper, we will consider semi-metric spaces in which most of triples satisfy this inequality for a small value of ρ and approximation results will be given as a function of ρ.

Bin covering [START_REF] Assmann | On a dual version of the one-dimensional bin packing problem[END_REF] is a classical problem that has been studied under many variants. In this paper, we study the case where we are given a set of weighted (heterogeneous) elements (resources) S with distances (latencies) between each pair of elements. In this paper, we consider the generalization where a distance constraint is added. More specifically, we consider that the distance between any two elements belonging to the same bin (cluster) is lower than a given threshold d max . Theoretically, in this generalization, elements belong to a metric space, to an infra-metric space, or even to a space in which distances between nodes are given by a latency matrix (and therefore not necessarily satisfying any kind of triangular inequality). In BCDC, the goal is to build a maximum of bins of diameter no more than d max , weighting at least W , a given threshold.

The motivation for studying BCDC can be found in details in [START_REF] Beaumont | Distributed approximation algorithm for resource clustering[END_REF], [START_REF] Beaumont | Distributed approximation algorithm for resource clustering[END_REF], where this problem was first studied. It is related to highly distributed platforms, such as BOINC [START_REF] Anderson | Boinc: A system for public-resource computing and storage[END_REF] or Folding@home 1 . Until now, all the applications running on these platforms consist of a huge number of independent tasks, and all data necessary to process a task must be stored locally at the processing node. We consider the case where the data set needed to perform a task is possibly too large to be stored in a single node. Then, both processing and storage must be distributed on a small set of nodes that will collaborate to perform the task. The nodes involved in a given cluster should have an aggregate capacity (memory, processing power...) higher than a given threshold, and they should be close enough (the latencies between any two nodes belonging to the same cluster should be small enough) in order to avoid high communication latencies. Building such clusters is equivalent to solving BCDC, where the distance between two nodes corresponds to the latency between these nodes.

In this paper we present approximation algorithms based on resource augmentation techniques [START_REF] Csirik | Resource augmentation for online bounded space bin packing[END_REF], [START_REF] Epstein | Online bin packing with resource augmentation[END_REF]. We compare the number of bins built by a polynomial time algorithm allowed to build bins of diameter at most βd max , for β > 1, to the optimal number of bins of diameter at most d max .

More precisely, we will say that A is an (α, β)approximation algorithm if it runs in polynomial time, builds bins of diameter at most βd max , and if the number of built bins is at least αOP T * , where OP T * is the optimal number of bins with the distance constraint set to d max .

In the context of large scale distributed platforms, resource augmentation is both efficient and realistic. Indeed, the aggregated power (or memory) of a cluster really needs to be larger than a given threshold in order to be able to process a task, whereas the threshold on the maximal latency between two nodes belonging to the same cluster is somehow weaker, since a cluster would still be able to work if it is violated (it would then simply work slowly).

In this context, if β = (2 -), BCDC is hard to approximate in the general case, within any constant approximation ratio (even any function in the number of elements), by a reduction to the MAXIMUM CLIQUE problem. On the other hand, a ( 1 3 , 4)-approximation algorithm has been presented in [START_REF] Beaumont | Distributed approximation algorithm for resource clustering[END_REF] for BCDC in R D .

In this paper we present in Section II-B a ( 2 5 , ρ 2 )approximation algorithm for BCDC in a ρ-inframetric. We also present, in Section II-C a

( 2 5 , 2 + 3 √ 3
2 )-approximation algorithm for BCDC in a space generated by Vivaldi. In Section II-D, we present a ( 1 3 , 2)-approximation algorithm for BCDC in tree metric spaces, that can be used in a space generated by Sequoia. Then in Section III we present our simulations and the way to compare the different embedding tools in the context of resource clustering.

II. DEFINITION AND APPROXIMATION ALGORITHMS

A. Notations and definitions

An instance I of BCDC can be described as a 5-tuple I = (S, d, w, W, d max ) where S is a set S = {e 1 , . . . e n } of elements, (S, d) is a semi-metric space, w is a weight function, W is a weight threshold and d max is the distance threshold.

Throughout this paper, for the sake of simplicity, we set W = 1 and we normalize the weights of the elements accordingly (i.e. divide them by W ). Remember that in our context of Internet resource clustering, the weight of the elements correspond to the heterogeneous capacity (that may represent either processing, memory or storage) of participating resources. Therefore, this normalization corresponds to express all capacities as a percentage of the overall target capacity of the cluster. Moreover, we do not deal with elements whose weight is larger than 1. Indeed, such elements can form bins (clusters) by themselves and can be removed from I. Thus, an instance of BCDC can be described by a 4-tuple I = (S, d, w, d max ), where w : S → [0; 1[, hence the following definition.

Definition 2.1 (BCDC): Given an instance I = (S, d, w, d max ), find a collection of pairwise disjoint subsets S 1 , . . . S K of S of maximal cardinality K such that ∀i ≤ K, e∈Si w(e) ≥ 1, ∀(e u , e v ) ∈ S i , d(e u , e v ) ≤ d max .

To work on graphs, we need the following tool to build a graph from a set of points.

Definition 2.2 (Compatibility Graph): The compatibility graph Comp(I, d) associated to an instance I is the graph G = (S; E) such that ∀(e i , e j ) ∈ S 2 , (e i , e j ) ∈ E ⇔ d(e i , e j ) ≤ d. Observe that (e i , e j ) ∈ E and (e j , e k ) ∈ E ⇒ d(e i , e k ) ≤ ρd in a ρ-inframetric space (ρ ≤ 2 in a metric space). Note that if S are points in a Euclidean space, and L 2 norm is used to define distances, Comp(I, 1) is the unit-disk graph [START_REF] Clark | Unit disk graphs[END_REF].

B. A Greedy ( 2 5 , ρ 2 )-approximation algorithm in a ρinframetric

In [START_REF] Beaumont | Distributed approximation algorithm for resource clustering[END_REF], a polynomial time ( 1 3 , 4)-approximation algorithm for BCDC has been proposed. This algorithm is quite simple to implement in a distributed way, and works in two phases. In this section, we present Algorithm 1, which is an improvement of the previous algorithm. Concerning the number of built bins, this algorithm ensures an approximation ratio of 2 5 in any semi-metric space. When this semi-metric space is a ρ-inframetric, Algorithm 1 is a ( 2 5 , ρ 2 )-approximation algorithm for BCDC. When the space is metric, it is a ( 2 5 , 4)approximation algorithm for BCDC. Otherwise, nothing is guaranteed on the diameter of the bins (on the other hand, as already noted, the values of ρ that are observed in practice are reasonably small).

To build bins, the algorithm is based on a classical strategy for Bin Covering, namely Next-Fit-Decreasing: it consists in sorting the elements in the non-increasing order of their weight. Then elements are considered in this order and put in the current bin, until the weight of this bin overtakes 1. When a weight larger than 1 is reached, the current bin is closed and a new one is opened. Without the distance constraint, this algorithm provides a remove elements corresponding to each bin built from U . 5: end for Phase 2:

1: apply Phase 1 on G = Comp(I, ρd max ).

Theorem 2.1: Algorithm 1 is a ( 2 5 , ρ 2 )-approximation al- gorithm for BCDC when d is a ρ-inframetric.
Proof of Theorem 2.1: Clearly, all bins returned by Algorithm 1 have diameter at most ρ 2 d max , hence the resource augmentation ratio ρ 2 . Indeed, all the elements belonging to a bin built during Phase 1 are at distance at most d max from the central node considered when this bin has been built, and thus two elements of such a bin are at distance at most ρd max . Then, similarly, all the elements belonging to a bin built during Phase 2 are at distance at most ρd max from the central node, and thus two elements of such a bin are at distance at most ρ 2 d max .

Let OPT be an optimal and thrifty solution, i.e. one for which in each bin of weight 1 + w, elements have weight larger than w. Such a solution always exists since we can modify any optimal solution to enforce this property by iteratively removing elements whose weight is smaller than w. Let us denote by B (k) , k = 1, 2 the set of bins built during Phase k and let b k = |B (k) | and let us define the extended area of a bin B ∈ B (1) as the set of elements e ∈ S such that d(e; B) ≤ d max , where d(e; B) = min u∈B d(e; u).

First, let us prove that any bin B OPT of OPT intersects at least one bin of B (1) . Indeed, Phase 1 ends when no bin of diameter lower than d max can be build, what means that at least one element of B OPT has been added to a bin B of B (1) . Therefore, we can notice that B OPT is included in the extended area of B since all its elements are at distance at most d max from B.

Let us partition the bins B

(1) 1) into two subsets K 1 and M 1 , depending on the number of elements

i , 1 ≤ i ≤ b 1 of B (
|B (1) i | they contain:            K 1 = {B (1) i ∈ B (1) , |B (1)
i | = 2}, k 1 = |K 1 | and let OPT K denote the set of bins of OPT that intersect bins in K 1 , M 1 = B (1) \ K 1 , m 1 = b 1 -k 1 and let OPT M denote the set of bins of OPT \ OPT K that intersect bins in M 1 .
Recall that no bin can contain only one element since we do not consider elements whose weight is larger than 1 (see Section II-A). Since all bins of OPT intersect a bin built during Phase 1, then

|OPT| ≤ |OPT K | + |OPT M |.
Since each bin in K 1 consists of exactly 2 elements, and since bins created by OPT are disjoint, then each bin of K 1 intersects at most 2 bins of OPT K . Hence,

|OPT K | ≤ 2k 1 .
In order to bound the cardinality of OPT M , let us introduce w lost , the overall weight of elements that do not belong to any bin returned by Algorithm 1, but that belong to OPT M .

Lemma 2.2: w lost < m 1 Proof: In the extended area of any bin belonging to M 1 , the overall weight of elements that do not belong to a bin returned by Algorithm 1 is strictly less than 1. Indeed, if it was not the case, another bin would have been built during Phase 2. Therefore, w lost < m 1 .

Furthermore,

|OPT M | ≤ w(OPT M ) ≤ w(M)+w(B (2) )+ w lost Lemma 2.3: If B ∈ M 1 , then w(B) < 1 + 1 |B|-1 Proof: Let w(B) = 1 + w.
In Algorithm 1, the Next Fit Decreasing strategy is used to build bins, and as soon as the weight of B is larger than 1, B is closed and no more element is added to it. Hence the last element added to B is weighting more than w. Since elements are added in the decreasing order of their weight, any element of B weights at least w. Then, w(B) > w ×|B| and thus 1+w > w ×|B|. Therefore, w < 1 |B|-1 . Thus, since every bin B of M 1 contains at least 3 elements, then w(B) ≤ 3 2 . Consequently, w(M 1 ) < 3 2 m 1 . Since each bin of B 2 has weight at most 2, then

|OPT m | < 3 2 m 1 + 2b 2 + m 1 = 5 2 m 1 + 2b 2 |OPT| < 5 2 m 1 + 2b 2 + 2k 1 < 5 2 (b 1 + b 2 ),
which concludes the proof of Theorem 2.1.

C. ( 2 5 , 2 + 3 √ 3
2 )-approximation algorithm for BCDC in a space generated by Vivaldi We present Algorithm 2, that is an adaptation of Algorithm 1 (designed for the general case of semi-metric spaces) to the case when elements are placed in a metric space generated by Vivaldi [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF]. Algorithm 2 builds bins of diameter

√ 3+1
2 d max in a first step, and

√ 3+1 2 (2 + √ 3+1 2 ) = 2 + 3 √ 3 2
then (instead of 2d max and 4d max in the general case, in any metric space),

Vivaldi is one of the embedding tools we study in this paper. In Section III, it will be compared through experimental evaluation to different embedding tools. It associates to each node of a network two coordinates in the Euclidean plane, plus a height. In such a space we call Vivaldi space, the distance between two nodes having coordinates

(a x , a y , a h ) ∈ R 2 × R + and (b x , b y , b h ) ∈ R 2 × R + is given by d(a, b) = (a x -b x ) 2 + (a y -b y ) 2 + a h + b h .
This embedding allows good prediction of the latencies between each pair of nodes, as evaluated in [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF].

To describe Algorithm 2, we define the lens of two elements as follows.

Definition 2.3 (Lens of e i and e j ): Let e i and e j be two points. The (symmetric) lens of e i and e j , denoted by Le(e i , e j ) is the set of points e k such that d(e i , e k ) ≤ d(e i , e j ) and d(e j , e k ) ≤ d(e i , e j ). d(e i , e j ) is the diameter of the lens.

We also use a value apply Next-Fit-Decreasing on such a clique 3:

remove elements corresponding to each bin built from U . 4: end while Phase 2:

1: G = Comp(I, β (β + 2)d max ). 2: d ← (β + 2)d max 3: apply Phase 1.
Since each clique of diameter d max is included in a lens of diameter at most d max , building cliques of diameter d max and weight larger than 1 simply consists in examining all such lenses (a lens is associated to a pair elements of S and therefore, there is a polynomial number of lenses) , and identifying in each such lens valid bins to build.

Given two elements e i , e j ∈ S 2 , in the lens Le(e i , e j ) of diameter at most d max we define the graph G ei,ej = Comp(I, β d max ) ∩ Le(e i , e j ). We prove in what follows, using Lemma 2.4, that G ei,ej is a bipartite graph, for β =

√ 3+1 2 .
Therefore, identifying a valid bin in Le(e i , e j ) corresponds to finding a weighted independent set of weight larger than 1 in G ei,ej . Finding a maximum weighted independent set in a bipartite graph can be done by adapting to a weighted version the classical solution for maximum independent set in bipartite graphs that, using Konig's Theorem [START_REF] Lovász | Matching theory[END_REF], can be solved as a matching problem using Hall's Theorem. Therefore, if its weight is larger than 1, since it is a maximum weighted clique in Comp(I,

√ 3+1 2 d max )
, a bin can be built.

Lemma 2.4: Given two points i, j in a Vivaldi space, such that i = (-a, 0, h i ) and j = (a, 0, h j ) for some a ≥ 0, and given two points u = (x u , y u , h u )

and v = (x v , y v , h v ) in Le(i, j), then if y u y v ≥ 0, d(u, v) ≤ √ 3+1
2 . Note that the restriction y i = y j = 0 implies no restriction on the points considered, but is just used to describe the lemma in a simple way.

Lemma 2.4 directly implies that G ei,ej is bipartite when

β = √ 3+1 2 .

Proof of Lemma 2.4:

In what follows, each element e has three coordinates, denoted (x e , y e , h e ). Given e = (x e , y e , h e ), we denote by E its mapping on the Euclidean plane, with coordinates (x e , y e ).

Note that every lens Le(i, j) related to a pair i = (-a, 0, h i ) and j = (a, 0, h j ) with a ≥ 0, h i ≤ 1 and h j ≤ 1 is included in the lens Le(i , j ) with i = (-(a + h i ), 0, 0) and j = (a + h j , 0, 0).

Thus without loss of generality we study the lens Le(k, l), with k = (-1/2, 0, 0) and l = (1/2, 0, 0) (see Figure 1). We also use the point s = (0, √ 3 2 , 0) at the intersection of the two circles centered respectively in k and l and of radius d(k, l) = 1, the point t = (0, 0, 1/2), and the point c = (0, √ 3-1 4 , 0), at the same distance of s as of t. In the rest of the proof, we study the "right upper side" of the lens, i.e. the part of the lens containing points p such that x p ≥ 0 and y p ≥ 0. We show that this right upper side of the lens is included in B(c, d(s,t)

2 ). Using a symmetry argument proves the lemma for the upper side of the lens. Using another symmetry argument ends the proof for the other side of the lens.

Let us first consider the point q = (1/2, and

d(Q, K) -d(Q, C) = 7 4 -4+ √ 3 8 ≥ 3- √ 3
4 . Thus these two points are on the same side of the hyperbola. Since both this side of the hyperbola and the rectangle ST QL are convex, then all the points M in the rectangle ST QL satisfy

d(M, K) -d(M, C) ≥ 3- √ 3 4 . Since d(k, m) = d(K, M ) + h m = 1, we have: d(m, c) = d(M, C) + h m d(m, c) ≤ d(M, K) -3- √ 3 4 + h m d(m, c) ≤ 1 -3- √ 3 4 d(m, c) ≤ √ 3-1
4 , which concludes the proof of Lemma 2.4.

The weight analysis concerning Algorithm 2 is exactly the same as for Theorem 2.1. The required resource augmentation corresponds to the largest diameter a bin can have, hence 2 + 3

√ 3 2 d max in this case. Theorem 2.5: Algorithm 2 is a ( 2 5 , 2 + 3 √ 3
2 )approximation algorithm for BCDC in a Vivaldi space.

In fact, the above algorithm works in any metric space where the existence of a clique of sufficient weight can be detected in polynomial time. In a Vivaldi space, this detection requires the use of a resource augmentation of

β = √ 3+1
2 . However, in the Euclidean plane for instance, no resource augmentation is required to detect such cliques (whatever the underlying norm), i.e. β = 1. Hence the following corollary (one can find its proof in [START_REF] Larchevêque | Agrégation de ressources avec contrainte de distance : applications aux plateformes de grande échelle(in french)[END_REF]):

Corollary 2.6: Algorithm 2 is a ( 2 5 , 3)-approximation algorithm for BCDC in the plane, whatever the underlying norm.

D. ( 13 , 2)-approximation algorithm for BCDC in a treemetric space

In this section, we present Algorithm 3, which is a version of Algorithm 1 dedicated to tree-metric spaces, such as those produced by the Internet embedding tool Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], [START_REF] Abraham | Reconstructing approximate tree metrics[END_REF]. A tree-metric space is a metric space, where the points can be mapped as the leaves of a weighted tree and where the distance between two nodes corresponds to the length of the weighted path between those two nodes in the tree. In the context of tree-metric spaces, Algorithm 3 is a ( 1 3 , 2)approximation algorithm for BCDC.

To build bins, Algorithm 3 is based on a variant of Next-Fit-Decreasing that we call Next-Fit-Distance-Decreasing: given a node in the tree, this strategy consists in sorting the elements in the non-increasing order of their distance to this node. Then, elements are considered one by one in this order and placed in the current bin, until the weight of this bin overtakes 1. When a weight larger than 1 is reached, the bin is closed and a new one is opened.

Given a node x in the tree, we denote by parent(x) its parent, and by children(x) the set of its children. The root of T will be denoted by r.

To ease the description of Algorithm 3, we will use the following definition.

Definition 2.4: Given a tree T and a node e ∈ T , SUBTREE dmax (e) is the subtree of T rooted in e such that ∀e ∈ SUBTREE dmax (e), d(e, e ) ≤ d max .

Algorithm 3 ( 1 3 , 2)-approximation algorithm for BCDC in a tree-metric 1: U ← S // Elements that do not belong to any bin 2: BUILDINSUBTREE(r) Procedure BUILDINSUBTREE(x): Implementing this algorithm in an efficient way just requires to perform an ascent of the tree. During this ascent, each node build a list of the nodes available in its subtree, at distance less than d max from itself, and orders this list in the decreasing order of the distances from each node to itself. Then it can applies Next-Fit-Distance-Decreasing on such a list, to build bins. Eventually it sends the remaining elements of its list to its parent, after having got rid of the nodes too far from its parent to be used. This implementation is working O(n log n), and can also be efficiently distributed.

Theorem 2.7: Algorithm 3 is a ( 1 3 , 2)-approximation algorithm for BCDC when d is a tree-metric space.

Proof of Theorem 2.7: Given an instance I = (S, d, w, d max ) of BCDC in which elements are embedded into a tree T having root r, we choose an optimal solution, denoted by OPT BCDC . Let us denote by B the set of bins built by Algorithm 3 on instance I.

First, observe that each bin built has diameter at most 2d max , hence the resource augmentation used. Indeed, two elements are put in a same bin if both are at distance less than d max from a given node and, thus, they are at distance at most 2d max from each other.

Consider a bin B in a solution of BCDC. Let us denote by r(B) the smallest common ancestor of the nodes in B, called its root. Every element of B is at distance at most d max from r(B).

Note that if two bins from two different solutions use the same element, then the root of one of the two bins is the ancestor of the root of the other bin.

We assign to each bin O of OPT BCDC to the bin B of B intersecting it, whose root is the furthest from the root of the tree T . If the maximal distance from the root of one of the bins of B intersecting O to the root of tree T is the same for more than one bin, we choose the first bin built by Algorithm 3 among them. At least one bin B of B intersects each bin O, since if no other bin has been built before, whereas at node r(O), Algorithm 3 would have built a bin.

Let us first note that r(O) is an ancestor of r(B) (or r(B) itself) if O has been assigned to B. In fact, suppose it is not the case, then r(B) is a strict ancestor of r(O), since they contain a common element. Algorithm 3 would have built a bin, when executed at node r(O), since bin O itself could have been built before reaching node r(B) to build bin B. In fact, from the way O has been assigned to B, no element from O has yet been put into a bin of B when Algorithm 3 reaches r(O) (r(B) is the "first" element to use elements from O to build a bin).

In what follows, we estimate the total weight available for OPT BCDC to build bins. For this purpose, let us denote by w lost the total weight of elements of OPT BCDC not used in bins of B. Each element whose weight is taken into account in w lost belongs to an optimal bin. Thus, we can associate each of these elements to the bin of B to which is assigned the optimal bin it belongs to. Then, given a bin B ∈ B, we can define the lost weight associated to this bin, w lost (B), to be the total weight of elements belonging to optimal bins assigned to B but not used in any bin of B. Lemma 2.8: For each bin B ∈ B, w lost (B) < 1.

Proof: Let e d be an element belonging to both B and a bin O of OPT BCDC and such that r(O) is the closest possible from the root of T . Let d be the distance from r(B) to e d . Let e d be an element of one of the optimal bins assigned to B, not belonging to B, not used in a bin of B, and being the furthest from r(B). Let d be the distance from r(B) to e d (see Figure 2).

We have d ≥ d . In fact, when B is built at node r(B), it uses elements by taking them in the non-increasing order of their distance to itself. Thus, it begins by using elements that are the furthest from itself. Since it uses e d and not e d , then d(r(B), e d ) ≥ d(r(B), e d ). Each ancestor of an optimal bin assigned to B is an ancestor of r(B) (or r(B) itself). There exists at least one among them that is the ancestor of all the others. If it is the case for more than one, just arbitrarily choose one among them. This node, a, is at distance at most d max -d from r(B), using the definition of d. Thus, it is at distance at most d max -d + d from every element taken into account into w lost (B), from the definition of d . Since d ≥ d , it is at distance at most d max from this set of elements.

r(O 1 ) r(O 2 ) B r(B) d max -d d max -d d d O 2 O 1
Thus, all the elements taken into account in w lost (B) are at distance at most d max from a. Thus w lost (B) < 1, otherwise Algorithm 3 would have built a bin when at node a or before.

The weight of each bin of B is strictly smaller than 2. We can upper bound the cardinality of an optimal solution by

|OPT BCDC | ≤ w(OPT BCDC ) ≤ 2|B|+ B∈B w lost (B) ≤ 3|B|,
hence the claimed approximation ratio.

III. EXPERIMENTAL EVALUATION

In this section, we propose a comparison of the most widely encountered embedding tools in the literature, namely Vivaldi [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] and Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], [START_REF] Abraham | Reconstructing approximate tree metrics[END_REF].

As presented in Section II-C, Vivaldi associates to each node of a network two coordinates in the Euclidean plane plus a height. In such a space, the distance between two nodes having coordinates

(a x , a y , a h ) ∈ R 2 × R + and (b x , b y , b h ) ∈ R 2 × R + is : d(a, b) = (a x -b x ) 2 + (a y -b y ) 2 + a h + b h .
This embedding allows good prediction of the latencies between each pair of nodes [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF].

Sequoia embeds Internet nodes into one or several weighted trees in which each node is either a leaf or the root, and in which internal nodes are virtual nodes. The distance between two points in the original network is estimated to be well approximated by the distance in the embedding tree (or as the median of these distances in the case of multiple trees). In [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], it is claimed that the accuracy of the prediction is higher using Sequoia as soon as a few trees are used.

The main originality of the approach we propose is that it is done in the context of a specific application, heterogeneous resources clustering. Indeed, the accuracy of embedding tools have already been compared in [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], but the goal was only to estimate the closeness between latency predictions returned by the embeddings and the actual measurements.

In practice, when considering an actual application, the chain is more complicated and the performance of the whole chain has to be evaluated. Indeed, as we prove in this paper in the context of resource clustering (BCDC), the simplicity of the metric space where original data are embedded plays an important role in the design of the algorithms, and leads to different approximation ratios and inapproximability results. Therefore, to compare the respective performance of embedding tools, we will compare the results obtained using

• no embedding (direct use of the latency matrix) and Algorithm 1 • Vivaldi embedding and Algorithm 2 • 1-tree Sequoia embedding and Algorithm 3. In this context, it is worth noting that the obtained classification strongly depends on the target application, since Vivaldi or Sequoia spaces may be very well suited to a particular application and not to another.

A. Experimental Protocol

In order to perform realistic simulations, we need to estimate the distance (the latencies) between any pair of re-sources and we need to estimate the heterogeneous capacity of the resources.

In order to estimate latencies, we ran simulations on a real dataset taken from the Meridian project2 containing allpairs latency measurements between 2500 nodes arbitrarily chosen from PlanetLab 3 . In this matrix, latency measures are symmetric.

This matrix contains a lot of triangular inequality violations. The study in [START_REF] Lumezanu | Triangle inequality variations in the internet[END_REF] makes a difference between triangular inequality violations due to the structure of Internet itself or due to the traffic on the Internet, and violations due to measurements' inaccuracy. Considering the study by Lebhar et al. in [START_REF] Lebhar | The inframetric model for the internet[END_REF], for each triple we consider that if the value ρ associated to this triple is larger than 10, then it might be due to the inaccuracy of the measurement. Thus, in a first time, we compute for each latency measure between two points the number of times it appears in a triangle in which the ρ value is larger than 10. Figure 3 depicts the repartition function of this number: a point (x, y) means that y% of the latency values appear in less than x triangles having a ρ value larger than 10. Using Figure 3, we choose to modify a latency value as soon as it appears in more than 50 triangles in which the value of ρ is larger than 10, since only around 1% of latency values appear in more than 50 such triangles.

To modify each of these latency values, we examine all triangles it appears in, whatever its ρ value, compute in each triangle the sum of the two other sides, and affect to the latency value to be modified the minimum of these sum values. To obtain this "fixed matrix", we modified around 1% of the latency values in the original latency matrix. In what follows, we run simulations using both the original latency matrix, and this "fixed matrix".

In order to estimate the heterogeneous capacities of the resources, we rely on the XtremLab project 4 dataset. XtremLab consists in a list of the characteristics of nodes running BOINC [START_REF] Anderson | Boinc: A system for public-resource computing and storage[END_REF] applications. We extract from it the data corresponding to the computing power made available by each node to the platform (their value in FLOPS). We get rid of values smaller than 500 KFlops and larger than 10 GFlops (getting rid of less than 0.1% of the values). We choose uniformly at random (so that the resulting distribution is the same as the original one) 2500 values among this set, and work with a total weight of 3632GF lops.

For each simulation, we rely on the following protocol

• We embed the latency matrix, using either Vivaldi or Sequoia algorithm (using a unique tree in the case of Sequoia). • We apply to this embedding the corresponding algorithm for BCDC, all with the same set of weighted elements and for different values of d max , from the minimal distance previously identified to a value of 200ms (since beyond this value, no evolution is observed).

Algorithm 2 and Algorithm 3 dedicated to specific metric spaces (respectively Vivaldi and Sequoia-based) exhibit better theoretical approximation ratios than Algorithm 1, designed for the general case. Nevertheless, we keep Algorithm 1 for the sake of comparison, since a benefit of a better approximation ratio may be canceled by the lack of accuracy of the embedding tool. On the other hand, as mentioned in the introduction, it is unrealistic in practice to assume that the whole latency matrix is known. Indeed, in the context of large scale dynamic platforms, the time taken to estimate all latencies is too high with respect to the dynamics of the system. It is worth noting that the implementation of Vivaldi does not require a centralized knowledge of the matrix, which is not the case for Sequoia to the best of our knowledge. The last simulation we run is also based on Vivaldi. From this embedding, we re-compute the latency matrix (where the distance between any pair of nodes is their distance in Vivaldi space) and we run Algorithm 1, designed for general semi-metric spaces, but which offers better theoretical guarantee than Algorithm 2 dedicated to Vivaldi (since it uses a resource augmentation of 4 instead of 2 + 3 √ 3+1 2

4.6). For each built cluster, we estimate its diameter as the maximal distance between any two nodes in the cluster, where distances are actual ones, i.e. those of the latency matrix, whatever the intermediate distance estimated by the embedding tool is. For each simulation and for each value of d max , we plot the average diameter of built bins, and the number of "valid" bins, i.e. bins whose diameter in the latency matrix is lower than βd max , the maximum diameter allowed by the corresponding algorithm.

We simulate the execution of the different algorithms presented in the previous sections, dedicated to different metric spaces

• Algorithm 1 (( 25 , 4)-approximation algorithm presented in Section II-B, directly using a latency matrix to obtain distances),

• Algorithm 2 (( 2 5 , 2 + 3 √ 3+1 2
)-approximation algorithm presented in Section II-C, dedicated to a Vivaldi space),

• Algorithm 3 (( 13 , 2)-approximation algorithm presented in Section II-D),

• Algorithm 1 using a latency matrix based on an embedding using Vivaldi. We ran simulations for different values of W , and choose W 11GF lops as the more meaningful and representative value (thus, each bin will require about 0.3% of the total weight). For smaller values of W , solutions tend to put fewer and fewer elements in each bin, since element weights get closer to the threshold. Thus, the number of built bins tends towards a steady value for a smaller value of d max . For larger values of W , the weight constraint becomes the most important and the problem is close to classical Bin Covering, since the distance constraint is less and less sensitive: even with large values of d max , bins can still be hard to build due to the lack of weight. Using such a weight threshold, bins contain on average approximately 7 elements.

B. Simulation results

Figures 4 and 5 respectively depict, using each of the embedding/dedicated algorithm combinations, the number of valid built bins and the mean diameter of the built bins, for several values of d max , using the original latency matrix. Figures 6 and7 respectively depict, using each of the embedding/dedicated algorithm combinations, the number of valid built bins and the mean diameter of the built bins, for several values of d max , using the fixed latency matrix.

In all cases, Algorithm 1 run on the original matrix performs better than both Algorithm 2 and Algorithm 1 using the latency matrix built from Vivaldi embedding. All of these outperform Algorithm 3.

Algorithm 2 and Algorithm 1 using the latency matrix built from Vivaldi embedding perform very similarly. It is worth noting that although Algorithm 2 requires a resource augmentation of β 4.6, the mean diameter of the bins it builds tends to be around the same values as the mean diameter of Algorithm 1, that only requires a resource augmentation of β = 4.

Vivaldi performs almost as efficiently as the general case, despite the loss of accuracy in the distance prediction induced by the embedding. The loss of accuracy due to the use of an embedding tool is therefore compensated by the design of an efficient algorithm in a simpler space. Moreover, this proves that using an embedding tool and a dedicated algorithm provides as good results as when using a complete latency matrix, whereas obtaining such a latency matrix is impossible in practice. 8 shows the percentage of bins built during the second phase for each simulation involving one of these algorithms, using the original matrix. This shows that in each case, the second phase is crucial to the algorithms' performance. Now we examine Figures 6 and7. In these two Figures, Sequoia performs far better than on the original latency matrix, and the results of Algorithm 3 become similar to those of the other algorithms. This shows that our dedicated algorithm for BCDC on Sequoia (with one tree) is not robust, since a modification of only 1% of the latency values drastically changes its performances.

By contrast we observe only minor differences in the results of Algorithm 1 and Algorithm 2 between the original and the "fixed" matrix. This suggests that these algorithms are much more robust.

2 :C

 2 = U ∩ {e ∪ N (e)} 3: apply Next-Fit-Decreasing algorithm on C 4:

√ 3 2Figure 1 . 3 4 3 4

 3133 Figure 1. Illustration of notations used in the proof of Lemma 2.4

1 :

 1 for each node y ∈ children(x) do -Distance-Decreasing on U ∩ SUBTREE dmax (x) 5: remove elements corresponding to each bin built from U .

Figure 2 .

 2 Figure 2. Example of a bin B of B and two optimal bins O 1 and O 2 whose ancestors r(O 1 ) and r(O 2 ) respectively belong to bin O 1 and O 2 . r(O 2 ) is at distance at most dmax from all the elements taken into account in w lost (B). Those elements are located between B and r(O 2 ).

Figure 3 .

 3 Figure 3. Repartition function of the number of triangles having a value of ρ larger than 10 in which appear each latency value.

Figure 4 .Figure 5 .

 45 Figure 4. Number of bins built for BCDC, for different values of dmax, using different embeddings, using the original latency matrix.

Figure 6 .Figure 7 . 1 Figure 8 .

 6718 Figure 6. Number of bins built for BCDC, for different values of dmax, using different embeddings, using the fixed latency matrix.

http://folding.stanford.edu

http://www.cs.cornell.edu/People/egs/meridian/data.php

http://www.planet-lab.org/

http://xw01.lri.fr:4320/


Olivier Beaumont
email: olivier.beaumont@labri.fr

Lionel Eyraud-Dubois
email: lionel.eyraud-dubois@labri.fr

Young J Won
email: young.won@labri.fr

Using the Last-mile Model as a Distributed Scheme for Available Bandwidth Prediction

Keywords: Network Coordinate System, Last-Mile, Network Measurement, Available Bandwidth Prediction, Labeling Scheme

Several Network Coordinate Systems have been proposed to predict unknown network distances between a large number of Internet nodes by using only a small number of measurements. These systems focus on predicting latency, and they are not adapted to the prediction of available bandwidth. But end-to-end path available bandwidth is an important metric for the performance optimisation in many high throughput distributed applications, such as video streaming and file sharing networks. In this paper, we propose to perform available bandwidth prediction with the last-mile model, in which each node is characterised by its incoming and outgoing capacities. This model has been used in several theoretical works for distributed applications. We design decentralised heuristics to compute the capacities of each node so as to minimise the prediction error. We show that our algorithms can achieve a competitive accuracy even with asymmetric and erroneous end-to-end measurement datasets. A comparison with existing models (Vivaldi, Sequoia, PathGuru, DMF) is provided. Simulation results also show that our heuristics can provide good quality predictions even when using a very small number of measurements.

Introduction

Predicting network performance (latency or available bandwidth) is important for many Internet applications. For video on demand [START_REF] Suh | Push-to-peer video-on-demand system: Design and evaluation[END_REF] and peer-assisted streaming [START_REF] Liu | Performance bounds for peer-assisted live streaming[END_REF] for example, estimations of available bandwidth allow the construction of an efficient overlay topology.

A number of measurement tools have been developed [START_REF] Goldoni | End-to-end available bandwidth estimation tools, an experimental comparison[END_REF] which measure the available bandwidth on the path between two given Internet nodes. However, in a large scale system, performing measurements between all pairs of nodes would incur too large of an overhead. Thus, there is a need for the possibility to infer (in this paper we also use the term predict1 ) the unmeasured bandwidth values from a limited number of actual available measurements.

For latency estimation, several solutions have been successfully proposed, under the global terminology of Network Coordinate Systems. Most of these solutions embed network nodes into a metric space (not necessarily Euclidean) and approximate the latency between nodes by the distance between their embeddings, which can easily be computed from their coordinates. GNP [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF] is an example of such a system, in which each node is positioned in an Euclidean space with respect to a number of landmarks whose positions are already established. Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] is a decentralised extension of GNP, which avoids the need for landmark nodes. However, the efficient counterparts of these coordinate systems for available bandwidth prediction are still to be proposed.

Recent literature about overlay design for peer-to-peer data dissemination [START_REF] Bonald | Epidemic live streaming: optimal performance trade-offs[END_REF] has generalised the use of a "last-mile" approximation, in which the rates of simultaneous communications are only limited by the upload and download capacities of each node. This simplifying assumption is quite natural in the context of the Internet, and allows to derive provably efficient overlay designs. In this paper, we analyse the validity of this approximation, and how it can be used to develop a technique for predicting available bandwidth from a limited number of measurements.

More precisely, we propose a decentralised heuristic to compute the capacities of each node from a relatively small number of measurements. We analyse this heuristic by using a dataset of available bandwidth measurements performed on PlanetLab [START_REF] Chun | Planetlab: an overlay testbed for broad-coverage services[END_REF]. The accuracy of the predicted values with our solution compares favourably with existing solutions, while requiring significantly fewer measurements.

The organisation of the paper is as follows. We first describe the related works in Section 2. Section 3 presents the rationale behind the last-mile model and our proposed heuristic to compute the capacities of the nodes. In Section 4, we present the evaluation of our solution and compare it to other existing solutions. Concluding remarks and future works are given in Section 5.

Related works

Latency estimation

In the context of latency estimation, a number of network coordinate systems have been proposed, based on the following idea: embedding the nodes of the network into a multi-dimensional space and using the distance between two points in this space as an estimation of the latency between the corresponding nodes. We can make a distinction [START_REF] Ledlie | Network coordinates in the wild[END_REF] between landmark-based and decentralised approaches. In the landmark-based approach (e.g. GNP [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF], PIC, etc.), a fixed number of landmark nodes are selected and positioned in the space. Non-landmark nodes measure their latency to these landmark nodes and compute their coordinates so as to minimise the resulting prediction error. On the other hand, in the decentralised approach (e.g. Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF], Big Bang Simulation, etc.), all participating nodes have the same role, and the coordinates of the nodes are computed in a decentralised way by direct measurements between participating hosts.

Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] is one of the most well-known decentralised coordinate system. It relies on the simulation of a system of springs, in which the interaction between two nodes is modeled by a spring whose force represents the estimation error. This simulation procedure allows to adapt the computed coordinates to changing network conditions.

Recent works have also studied embedding into a hyperbolic structure [START_REF] Dinitz | Online, dynamic, and distributed embeddings of approximate ultrametrics[END_REF]. An example of such a system is the Sequoia algorithm [START_REF] Venugopalan Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], which embeds the nodes as the leaves of a weighted tree, and approximates the distance between two nodes by the length of the path between their respective positions in the tree. The Sequoia algorithm comes with a theoretically proven performance guarantee, and can be applied to both latency and bandwidth estimation. However, the algorithm is quite sensitive to violations of the triangular inequalities, and there is for the moment no decentralised version of Sequoia: computing the embedding requires the measurements between all pairs of nodes.

An important problem with metric-based embeddings comes from the violations of triangle inequalities, which are often observed in Internet measurements. Several studies have thus considered non-metric embeddings. IDES [START_REF] Mao | Ides: An internet distance estimation service for large networks[END_REF] is based on matrix factorisation, which consists in approximating a large matrix by the product of two smaller matrices. Each node is thus assigned two vectors (an incoming and outgoing vector), which correspond respectively to one row and one column of the two smaller matrices. The distance between two nodes A and B is computed as the scalar product of the outgoing vector of A and the incoming vector of B. The IDES system is based on a set of landmark nodes, and recently a decentralised version has been proposed, called DMF [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF] for decentralised matrix factorisation. DMF is an iterative procedure in which each node locally minimizes the prediction error by solving a least square problem.

Bandwidth estimation

There is a relatively small number of studies focusing on bandwidth estimation. The authors of Sequoia [START_REF] Venugopalan Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF] studied the applicability of their algorithm to available bandwidth, and the works based on matrix factorisation [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF] can be applied to bandwidth estimation as well. PathGuru [START_REF] Xing | Predicting available bandwidth of internet path with ultra metric space-based approaches[END_REF] is a landmark-based system specifically designed for available bandwidth estimation, which relies on the observation that, in certain circumstances, Internet available bandwidth forms an ultra metric space. In PathGuru, each node measures the available bandwidth to and from every landmark, and the estimation of bandwidth between two given nodes A and B is performed using the pair of landmarks which most closely forms an ultra metric space with A and B.

BRoute [START_REF] Hu | Exploiting internet route sharing for large scale available bandwidth estimation[END_REF] is another system for available bandwidth estimation, which is based on the observations that most bottleneck links are on the path edges, and that relatively few routes exist near the source and destination. Unlike the previous solutions which only require end-to-end measurements, BRoute uses landmarks and network management tools (such as traceroute and BGP routing information) to identify the bottleneck links near each source and destination, and to infer which links are used by packets between A and B.

A number of works in the literature of communication optimization in large scale systems assume that each participating node is characterised by its upload and/or download bandwidth. This applies to a variety of topics, such as video-on-demand [START_REF] Suh | Push-to-peer video-on-demand system: Design and evaluation[END_REF][START_REF] Boufkhad | An upload bandwidth threshold for peer-to-peer video-on-demand scalability[END_REF], peer-assisted streaming [START_REF] Liu | Performance bounds for peer-assisted live streaming[END_REF][START_REF] Bonald | Epidemic live streaming: optimal performance trade-offs[END_REF][START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF] or multi-port divisible load scheduling [START_REF] Beaumont | Scheduling divisibleworkloads on heterogeneous platforms under bounded multi-port model[END_REF]. Thanks to its simplicity, this rather natural assumption allows to derive provably efficient algorithms. In this paper, we analyse how well this model can approximate the actual available bandwidth in a large scale distributed platform.

3 Last-mile Bandwidth Prediction Model

Last-mile model

Throughout the paper, we denote by M A,B the measured available bandwidth from node A to node B, and by P A,B the corresponding predicted value.

The previous research on the properties of the Internet indicate that the bandwidth at the edge of the network, the so called last-mile (end-host) bandwidth, reflects the overall performance of the complete end-to-end path. Hu et al. [START_REF] Hu | A measurement study of internet bottlenecks[END_REF] show that 60% of wide-area Internet paths between end-hosts have their bottleneck in the first or second hop. A recent study also shows a similar property in broadband access networks [START_REF] Dischinger | Characterizing residential broadband networks[END_REF]. As an insight, we have observed the dataset obtained from measurements on the PlanetLab platform [START_REF] Chun | Planetlab: an overlay testbed for broad-coverage services[END_REF] which is described more precisely in Section 4 where it is used to evaluate our heuristics.

Figure 1 is the plot of the outgoing bandwidth measurements from host planetlab3.hiit.fi and planet-lab7.millenium.berkeley.edu, which will be denoted hiit and berkeley in what follows, to all the other hosts in the platform. The bandwidth values are sorted for increased readability. The plot for berkeley (Figure 1(b)) shows what can be expected for a host with a low outgoing capacity: the bandwidth to the first 50 hosts is limited by their respective ingoing capacity, and then the bandwidth to the rest of the nodes is limited by the outgoing capacity of berkeley, and thus the plot remains quite flat. On the other hand, the plot for hiit (Figure 1(a)) shows the result for a host with a large outgoing capacity: the bandwidth increases quite smoothly. In both cases however, a small number of larger bandwidth measurements can be noticed by a sharp increase around node 300, which can be interpreted as bogus measurements and will be discussed later. This observation has led to propose a last-mile modelisation of available bandwidth [START_REF] Liu | Performance bounds for peer-assisted live streaming[END_REF]. In this model, each participating node x is represented by two different bandwidth capacities, one for upload (β out

x ), and one for download (β in x ). Based on these values, and assuming that they are the only limiting factors for the end-to-end performance, the predicted bandwidth P LM

x,y between two nodes x and y is given by min(β out

x , β in y ). In this paper, in order to analyse the validity of this model, we propose heuristics to compute values for β out x and β in x so as to minimise the prediction error. We first propose a simple way to compute reasonable initial values, and then describe an iteration procedure following the one of [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF].

Initial values

The initial observation may identify that the upload capacity of a node β out x has to be at least as large as the measured value between node x and any other node y (otherwise it would have been impossible to measure such a high value for this particular node y). However, setting β out x = max y M x,y is potentially dangerous: only one bogus measurement is enough to obtain wrong predictions for x. Furthermore, the last-mile assumption is not always satisfied in practice, and it may happen that some nodes share a bottleneck link. A typical example is the case of two nodes A and B on a common local area network, which is connected to the Internet through a DSL connection. The bandwidth from A to any other node X on the Internet is then limited by this DSL connection, while the bandwidth from A to B is not. Hence, setting β out A = max y M A,y = M A,B would result in largely over-estimated predictions for bandwidth from A to any X on the Internet, since it would ignore the limiting DSL connection.

This situation can be observed on our dataset. For instance, on Figure 1(a), most values lie below 2.10 5 kbps, except for a couple of outliers with very high measured bandwidth, which can be either erroneous measurements or hosts with a local, direct high-capacity connection to hiit.

This observation motivates the removal of a few outliers hosts before computing β in and β out values. The solution we propose in this paper is to define β out A as a given percentile 1α of all measured values M A,y . It is a generalisation of the previous straightforward answer of taking the maximum value, which corresponds to α = 0; larger choices of α ignore more and more measurement values. This solution yields a very simple way of computing β out and β in values, and is very resilient to missing and erroneous measurements and "too high" bandwidths due to nodes in the same local network, since corresponding measurements are ignored.

Algorithm 1 Computing initial values for the last-mile

Input: M,: measurement matrix k: number of neighbours for each node α: percentile parameter Output: β out and β in for all node A do select a random set S of k neighbours sort up = (MA,y)y∈S and down = (My,A)y∈S

β out A = (1 -α) -percentile of up β in A = (1 -α) -percentile of down end for
With this procedure, each host can compute its own β out and β in values independently, assuming that it has access to the measurements of all pairs it is involved in. Furthermore, a standard technique to reduce the measurement overhead (at the cost of accuracy) is the random sampling of the hosts, in which each host selects a random subset of neighbours and performs available bandwidth measurements to and from this subset. By computing the (1α)-th percentile of these measurements to use as β out and β in , the result is expected to be a reasonable approximation of the real β out and β in values obtained if all measurements were available. The resulting algorithm is given in algorithm 1.

Methodology

The experimental results described in this paper are based on a dataset from the Scube project [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF]. This project aims at monitoring the large scale distributed platform PlanetLab [START_REF] Chun | Planetlab: an overlay testbed for broad-coverage services[END_REF]. Available bandwidth is measured between almost all pairs of nodes of PlanetLab, and results are made available as regular snapshots of the platform. For space reasons, we only present here results obtained from the snapshot of April 20th, 2010; however other snapshots yield the same conclusions. This snapshot contains 426 hosts, with some missing measurements, and we extracted a set of 308 hosts for which the complete measurement matrix is available 2 .

The quality of the prediction algorithms is given by the precision of the predictions compared to the original values. In this paper, we use the modified relative error as defined in [START_REF] Mao | Ides: An internet distance estimation service for large networks[END_REF]:

e x,y = |M x,y -P x,y | min(M x,y , P x,y )
where the min-operation serves to increase the penalty for underestimated values. Most plots in this paper depict the cumulative distribution function (CDF) of the modified relative error for all pairs of hosts. Therefore, if algorithm A provides better estimations than algorithm B, then the plot corresponding to A will be above the plot corresponding to B in the graph.

Sometimes it is more convenient to represent the fitness of the embedding with a single value. In that case we will consider the 80-th percentile of the modified error ratios, i.e. the error e such that 80% of the node pairs have their available bandwidth estimated with error at most e. We also measure the stress, to represent the global error of the prediction, defined by: stress =

x,y (M x,y -P x,y ) 2

x,y M 2

x,y

Parameter tuning

We first analyse the effect of the parameter α on the accuracy of the predictions, both for the initial values obtained with algorithm 1 and for the result of the iterative procedure after 20 iterations. The number of neighbours k is fixed to k = 16, and we also compare to the special case in which there is no random neighbour selection (all measurements are used), which we denote as k = 0. The resulting stress values are depicted in Figure 2(a). For the cases which involve random selection, we report average, minimum and maximum values over 10 runs. The first observation is that using a non zero value of α is very important when considering all measurements, which is expected as discussed in section 3: a small number of invalid measurements have a very bad impact on the accuracy of the predictions. With random selection (k = 16), the effect of the parameter α is not as big, and it is even lower for the iterative procedure, which effectively improves the fitness of the embedding and gives a result which does not depend on this parameter. This hints that the result of the iterative procedure is independent of the initial values. In the rest of the evaluation, we will use the value α = 0.1.

The effect of the parameter k (number of neighbours for each node) is studied in details in the next section, together with the comparison with other prediction heuristics.

We also study the convergence of the iterative procedure by measuring the stress of the fitness obtained after each iteration. The result is shown on Figure 2(b) and shows that the total stress remains stable across the iterations, and that the convergence is fast. We can also see that the initial values computed by algorithm 1 are actually quite precise.

Comparison methods

We compare our results with several other solutions from the literature:

-The Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] algorithm provides a basis for comparison even though it was originally designed for latency estimation. -The Sequoia [START_REF] Venugopalan Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF] algorithm, based on tree embeddings, is advertised as being usable for both latency and bandwidth estimation. -PathGuru [START_REF] Xing | Predicting available bandwidth of internet path with ultra metric space-based approaches[END_REF] is a landmark-based solution explicitly designed for bandwidth estimation.

-DMF [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF] is an algorithm which was proposed in the context of latency estimation, but it can be used for bandwidth estimation as well since it does not make any assumption on the structure of the input measurement matrix.

Public implementations of Vivaldi3 and DMF4 are available and have been used for this evaluation. However, no implementation seems to be available for PathGuru and Sequoia, so we implemented them based on their description in the corresponding paper.

This dataset is used as input to different prediction algorithms. However, Sequoia and Vivaldi are originally designed for latency prediction, for which smaller values mean that nodes are closer. Hence, these algorithms are fed with the inverse of the available bandwidth measurements5 , and their resulting distance predictions are inversed as well before comparing to the original measurements.

For all algorithms, we used the default values of the parameters as they are described in the corresponding paper (15 prediction trees for Sequoia and l = 10 dimensions for DMF). However, we changed the number of neighbours in DMF and landmarks in PathGuru to explore the compromise between accuracy and number of measurements used.

Evaluation results

We first analyse the variability of the results with respects to the random choices involved: choice of the levers for Sequoia, of the landmarks for PathGuru, and of the neighbours of each node for DMF and last-mile. We provide in Table 1 the average and standard deviation of the stress and of the 80-th percentile of the modified error ratio for 30 runs for each heuristic. For visual comparison, the CDFs of modified relative error for a selection of parameters are given on Figure 3. For a given heuristic and parameter value, the CDFs corresponding to the 30 runs are depicted together on the plot to visualise the variability.

In addition, Figure 4 provides a direct comparison of the most relevant heuristics. On this figure the CDFs of one run for each heuristic are plotted together. The low variability exhibited by table 1 ensures that these particular plots are relevant enough.

The results for Vivaldi show as expected that this algorithm is not appropriate for bandwidth estimation. We can also see that the prediction of last-mile and DMF (for large enough values of k) are much more accurate and stable than the predictions of PathGuru and Sequoia. PathGuru in particular is very sensitive to the choice of the landmarks, and its performance does not really increase with the number of landmarks (however it gets more stable). The predictions of Sequoia are better than those of PathGuru, but remember that Sequoia needs to access the measurements between all pairs of nodes. Sequoia is also (together with Vivaldi) the only heuristic which produces symmetric estimations, and this is a big disadvantage because available bandwidth between two nodes is often asymmetric.

We can also see that while DMF is able to make a better use of a larger number of measurements, last-mile achieves a reasonably good accuracy even for low values of k. Actually, increasing k does not increase much the accuracy of the predictions of lastmile, but it makes them more stable. In particular, last-mile with 16 neighbours per node is about as accurate as DMF with 32 neighbours per node, which is the default value proposed in [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF] for latency estimation. It is worth pointing out that measuring available bandwidth incurs a larger overhead than measuring latency; hence, being able to use a smaller number of measurements is an attractive feature.

These results show that the last-mile model is able to explain a large part of the structure of the available bandwidth on the Internet, with a very low number of parameters (each node is characterised by only 2 values, to be compared with 20 for DMF

Fig. 1 .

 1 Fig. 1. Outgoing bandwidth distributions for two PlanetLab hosts; the values are sorted in increasing order: (a) planetlab3.hiit.fi; (b) planetlab7.millennium.berkeley.edu

Fig. 2 .

 2 Fig. 2. (a) Stress of the last mile embeddings for different values of α; (b) Stress of the last mile embeddings after each iteration

The design of techniques for efficient and reliable available bandwidth measurements is an interesting research question, but it is not in the scope of this paper. Instead, we assume in this work that a (limited) number of measurements are available, and our goal is to use these measurements to provide estimations for the unmeasured bandwidth values.

The code and dataset used to obtain the results of this section will be made publicly available upon acceptance of the paper.

http://www.eecs.harvard.edu/ ~syrah/nc/

http://www.run.montefiore.ulg.ac.be/ ~liao/DMF

This choice is different from the one made in the evaluation of Sequoia in[START_REF] Venugopalan Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], in which the authors subtract the bandwidth values from a large constant. Using the inverse as we are doing actually yields better results for Sequoia.

In practice, many overlay networks provide the ability of choosing a random node, either by construction (e.g. Distributed Hash Tables) or using gossiping algorithms, so that random sampling can easily be implemented in a distributed way.

Iterative procedure

In order to improve on this initial calculation, following Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] and DMF [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF], we propose a procedure in which nodes iteratively update their β in and β out values. To update its β out value, each node A obtains the values of β in from its neighbours, and sets β out A to the value x that minimises the prediction error:

The value of β out A which minimises this quantity can be easily computed, since each y such that β in y ≤ β out A contributes a constant factor to the error. Hence for x between two consecutive values β in y1 and β in y2 , the error can be rewritten as:

And this expression is minimised for x equal to the average of the M A,y values for β in y > β in y1 . Of course, if this value is above or below the prescribed interval, x is set to the corresponding bound of the interval. By sorting the β in y values and testing all the k possible intervals, it is possible to compute the value of x that minimises equation [START_REF] Beaumont | Scheduling divisibleworkloads on heterogeneous platforms under bounded multi-port model[END_REF]. The resulting iterative procedure is described in algorithm 2.

Algorithm 2 Iterative procedure. with 10 dimensions) and accessing a small number of measurements. The last-mile model is thus a promising approach for the prediction of available bandwidth on the Internet.

Concluding Remarks

Estimating the available bandwidth between nodes in a large scale distributed platform is a crucial issue in many distributed applications. On the other hand, it is impossible to rely on complete measurement sets, because of the intrinsic cost of these measurements, and because many measures may be inaccurate due to varying external conditions. Therefore, as it has been done successfully for latency estimations, several labeling schemes have been proposed, such as Sequoia and PathGuru, that enable to predict at low cost the bandwidth between any pair of hosts.

In this paper, we propose simple decentralised heuristics to use the last-mile model as a prediction mechanism for available bandwidth, by characterising each node by an incoming and an outgoing capacity. Based on real-world PlanetLab bandwidth measurements, we show that this model, although simple, achieves better prediction accuracy than the current available solutions, in particular when the number of available measurements is low. The prediction results of PathGuru depend heavily on the choice of landmarks, and Sequoia suffers from its inability to provide asymmetric predictions. When more measurements are available, decentralised matrix factorisation provides more precise predictions than our last-mile heuristic, probably because each node is described with a larger number of parameters.

In the future work, we are planning to investigate the possibility to increase the number of parameters in the last-mile model for a better accuracy, and also to make a combined use of latency and available bandwidth measurements in order to improve the predictions of the model.


Zdenek Zelinger

Agnès Perrin
email: agnes.perrin@lisa.univ-paris12.fr

First analysis of the high resolution FTIR spectrum of the ν ν ν ν 2 band of the FCO 2 radical at 970.2 cm -1

Keywords: fluoroformyloxyl radical, high resolution IR spectrum, spin-rotation, rotational analysis, Fermi resonances fluoroformyloxyl radical, high resolution IR spectrum, rotational analysis, spin-rotation interactions, Fermi resonances

The infrared spectrum of the fluorocarboxyl radical, FCO 2 , was recorded at high resolution (0.0035 cm -1 ) in the 600-1400 cm -1 region on a Bruker IFS 120 HR Fourier transform spectrometer of the University of Wuppertal. The analysis of the A-type ν 2 band of FCO 2 (CF stretching mode) centred at 970.208 cm -1 was performed taking use of the ground state parameters achieved by Kolesniková et al. [

I Introduction

Recent interest on the fluorocarboxyl radical, FCO 2 , is motivated because it is assumed to participate in atmospheric processes such as the degradation of hydrofluorocarbons that have been considered as chlorofluorocarbon substitutes [1][2][3][4]. On the other side, FCO 2 is isoelectronic to NO 3 and the spectroscopic and thermodynamic properties of these free radicals are expected to be governed by vibronic interactions to low lying electronic excited states [5][6][7]. Actually, the Born-Oppenheimer approximation breaks down for NO 3 [6,7], while there still exists rather little information on the spectroscopic properties of the FCO 2 radical.

Several results were achieved through ab initio calculations, like for example, the equilibrium structure of the FCO 2 radical which possesses C 2v symmetry in its ground state (X 2 B 2 ) and in the next highest states [5,[START_REF] Francisco | Structures of low-lying electronic states of the fluoroformyloxyl radical[END_REF]9]. Also the standard enthalpy of formation of FCO 2 was calculated [9]. The highly structured absorption in the visible originating at 13150 cm -1 was assigned, by comparison with ab initio calculations, to the B 2 A 1 ← X 2 B 2 electronic transition by Maricq et al. [5,10], and from the observed progressions of hot bands, the ν 3 vibrational mode of FCO 2 in the X 2 B 2 ground state was measured at 520 cm -1 . From the study of photodetachment of the -2 FCO ion, the ν 1 , ν 2 and ν 3 mode of FCO 2 in X 2 B 2 are measured at 1465, 950 and 500 cm -1 , respectively [11]. In addition, the visible spectrum and the IR spectrum of natural FCO 2 , FC 18 O 2 and F 13 CO 2 isolated in noble gas matrices was reported [12]. In this study the free FCO 2 radical was prepared by vacuum flash pyrolysis of bis(fluoroformy1) peroxide, FC(O)OOC(O)F, diluted in N 2 , Ar, or Ne and, the six fundamental vibrational states for FCO 2 in the ground X 2 B 2 electronic state were assigned.

For FCO 2 isolated in Ne the ν 1 , ν 2 and ν 3 modes are at 1475, 960, and 519 cm -1 (A 1 symmetry), ν 4 and ν 5 at 1098 and 474 cm -1 (B 1 symmetry), and ν 6 at 735 cm -1 (B 2 symmetry).

Table 1 and 2 give the symmetry properties of the FCO 2 radical and a short description of the vibrational modes in the ground state X 2 B 2 , respectively. In Ref. [13] the first gas-phase detection of the FCO 2 radical by millimeter wave and high resolution infrared spectroscopy was performed guided by ab initio calculations. In this way the observed infrared bands ν 1 (1478 cm -1 ), ν 2 (970 cm -1 ) and ν 4 (1094 cm -1 ) were identified. In this paper a detailed analysis of the FCO 2 radical was performed by microwave techniques, leading to a first set of ground state parameters including rotational, quartic centrifugal distortion, fine and hyperfine constants. Indeed FCO species, the coupling of the electron spin, with the rotation splits the rotational levels into two sublevels, and each of them is further split into a doublet by the hyperfine interaction due to the fluorine nuclear spin. The analysis of the millimeter wave measurements [13] was performed in the coupling scheme J=N+S and F=J+I F between the rotational N, electron spin S, and 19 F nuclear spin I F angular momenta. These ground state parameters were later improved by a subsequent millimeter wave analyses [14,15]. Finally, the electron paramagnetic resonance spectra of the fluoroformyloxyl radical FCO 2 isolated in noble gas matrices have been investigated leading to the determination of principal g values and 19 F hyperfine coupling constants of FCO 2 [16].

Little information exists on gas phase infrared band analysis of FCO 2 . To our knowledge, there is only one ongoing infrared study, which concerns the ν 4 band (antisymmetric CO stretching) centered at 1094.1492 cm -1 [START_REF] Bailleux | Poster J28 presented at the 20st International Conference on High Resolution Molecular Spectroscopy[END_REF]. One surprising result of the analysis of this rather unperturbed B-type band are the significant differences between the spin rotational constants of the 4 room temperature according to the literature procedures [12].

The IR spectra of FCO 2 were recorded on a Bruker HR 120 spectrometer at an apodized resolution (1/maximum optical path difference) of 0.003 cm -1 in the order of the Doppler width, and in the region 600 and 1400 cm -1 using a KBr beam splitter, an MCT600 detector, and an cut-off filter (>1400). Altogether 60 scans were co-added to obtain the final spectrum.

The signal to noise ratio of the spectrum was ca. 20:1. Calibration was done by comparison with CO 2 lines [START_REF] Guelachvilli | Handbook of Infrared Standards[END_REF].

III Analysis

The fluorocarboxyl radical, FCO 2 , is a planar oblate asymmetric rotor molecule of C 2V symmetry. Its symmetry axis is the a inertial axis, and the ν 2 mode is of A 1 symmetry type (see Table 1). The total wavefunction (involving the electronic, vibrational, rotational and nuclear spin contributions) remains unchanged under symmetry operations equivalent to the permutation of the two oxygens (with a zero nuclear spin I( 16 O) = 0), Due to the symmetry

(X 2 B 2 )
of the ground electronic state, the existing vibration-rotation energy levels

(v 1 v 2 …v 6 )[N K a K c ] in the ground electronic state are K a =odd if (v 4 + v 5 +v 6 )= even (resp. K a =
even for (v 4 + v 5 +v 6 )= odd). Therefore for the ground and the 2 1 vibrational states, only rotational levels with odd values of K a are allowed [12,15]. As expected from symmetry considerations (see Table 1), the ν 2 band is an A -type band (see Fig. 1), and, as usual for planar oblate molecules, the P and R lines are grouped in clusters of lines keeping a constant value of (2N-K c ), the spacing between two successive clusters being of about 2C. Examples of such clusters are given for a portion of the R branch on Fig. 2.

Within these P and R clusters the strongest transitions which are those involving the low K a values (starting from 1 " a = K

) are overlapping, and the assignments within these clusters are often difficult: this is evidenced on Figs. 2 and 3. In the Q branch, which is congested, the strongest transitions involve K a = J and very low K c values. Series of N N 1,0 ← N N 0,1 (K c″ = 0 and 1) transitions are easily observed on Fig. 4, from which A′ < A″ can be inferred.

For the FCO 2 radical, each [N K a K c ] energy levels are split by the electron spinrotation interactions into two subcomponents corresponding to J = N ± 1/2. However, the spin-rotation parameters in the 2 1 vibrational excited state differ only marginally from those of the ground state. As we are dealing with an A-type band, the spin-rotation splittings have similar values in the upper and lower levels for transitions involving energy levels in the symmetric top limit either for high

K a (K a ~ N, K c << N) or for high K c (K a << N, K c ~ N)
values. For this reason, the spin rotation splittings are not observable in the spectrum for strong lines of the P and R branches, or in the Q branch, since these transitions involve very low K a (P and R branches) and very high K a values (Q branch), respectively. This is clearly evidenced on Figs. Finally, lets us mentioned that the hyperfine structure (of few megahertz, only) could not be observed during this infrared study. It is presumed that this hyperfine structure contributes to the apparent line width observed for the ν 2 transitions. Some low and medium N and K a transitions in the ν 2 band were first assigned. Then, using the ground state parameters of Ref. [15], the lower state spin -rotational energy levels were calculated and added to the newly observed line positions to get a list of experimental upper state energy levels. The upper state spin-rotational energy levels were inserted in a Fermi type resonances are accounted for by the energy levels calculation. This iterative process was carried out until the ν 2 band was satisfactorily assigned. Table 3 gives an overview of the results of the present analysis. However, as the resonances coupling the 2 1 and 5 2 energy levels occur for rather high N values, the perturbed ν 2 lines are already weak and it was not possible to assign the resonating transitions belonging to the dark 2ν 5 band.

Some remaining lines could not be assigned in the spectrum: it is presumed that these lines belong to hot bands: indeed since the ν 5 and ν 3 vibrational states are located near 474 and 519 cm -1 , respectively, the ν 2 +ν 5 -ν 5 and ν 2 +ν 3 -ν 3 are assumed to contribute for about 10 % and 8 %, respectively, to the total band intensity. However, the precise band head of these Q branch hot bands could not be located unambiguously.

IV Energy levels calculations.

In order to explain the perturbations which were observed during the analysis of the ν 2 band starting from N~40, one has to identify the dark states located in the vicinity of the 2 1 bright state. Indeed, the 5 2 , 3 1 5 1 and 3 2 states of A 1 , B 1 and A 1 symmetry type are crudely estimated near 948, 993 and 1038 cm -1 , respectively, by extrapolating from the values of the ν 3 and ν 5 vibrational frequencies issued from the Ne matrix measurements [12] (see Table 2).

We tried several types of energy levels calculations depending on the symmetry type of the dark states which are assumed to be responsible of the observed resonances. Indeed, C-type Coriolis involving the 3 1 The final calculation was performed considering in the v-diagonal part of the Hamiltonian both spin-rotation operators [START_REF] Brown | [END_REF] and Watson 's type rotational operators written in I R representation with an A-type reduction [START_REF] Watson | Aspects of quartic and sextic centrifugal effects on rotational energy levels[END_REF]. This choice of reduction and type of representation for the FCO 2 oblate asymmetric top is justified because it allows a straightforward comparison with the ground state parameters achieved in Refs. [13][14][15]. In addition this Hamiltonian involves Fermi type operators in the 5 2 2 1 off diagonal blocks.

The theoretical details are given in Ref. [START_REF] Perrin | [END_REF], and the final form of the Hamiltonian matrix is given in Table 4.

The experimental 2 1 spin-rotational energy levels obtained in this work were introduced in a least squares fit using this Hamiltonian model. Table 5 lists the Hamiltonian parameters (band centers, rotational, spin-rotation and coupling constants) resulting from the fit, together with their associated statistical uncertainties. Some constants were maintained at their ground state values [15], like for example the spin -rotation constants of the 5 2 dark state. For the 5 2 dark state we estimated the accuracy of the vibrational energy to be about 2 cm -1 , and the achieved rotational constants are rather effective ones: indeed, the resonances coupling the 5 2 and 2 1 energy levels begin to be significant only for N> 40, and it is difficult, at this stage, to predict accurately the position of the 5 2 resonating levels. In addition, it is not possible to estimate the rotational constants of 5 2 from those of 5 1 since no high resolution study exists so far for the ν 5 fundamental band.

Finally, as it can be seen in Table 5 the spin-rotation parameters in the 2 1 differ marginally from those of the ground state. To the contrary, an ongoing study of the ν 4 band [START_REF] Bailleux | Poster J28 presented at the 20st International Conference on High Resolution Molecular Spectroscopy[END_REF] revealed a large vibrational dependence of the spin-rotation parameters, which probably can be traced back to a vibronic coupling to a nearby B 2 A 1 electronic state via the ν 4 vibrational mode.

As far as the 5 2 2 1 Fermi interaction constants are concerned, it was not possible to determine the zero order constants 0 F 55,2 h which was maintained at zero during the calculations.

The results of the energy levels calculations proved to be rather satisfactory, as can be seen from the standard deviation and statistical analysis given in the lower part of Table 3. Finally, Figures 1 to 5 give detailed comparisons between the observed and calculated spectra in various spectral regions. For these comparisons, the relative line intensities of the spin-rotational sub-components were computed, using the tensorial method which is described in Ref. [22] to account for the spin-rotation interaction.

Conclusion

The first high resolution analysis of the ν 2 band of the fluorocarboxyl radical, FCO 2 , centred at 970.208 cm -1 was performed using spectra recorded at high resolution at Wuppertal.

Because the spin-rotation parameters in the 2 Overview of the 940-999 cm -1 spectral region with the ν 2 band of fluorocarboxyl radical, FCO 2 .

Caption:

The lower trace corresponds to the experimental spectrum (T = 296 K). The upper trace is the line by line calculation for the ν 2 band of FCO 2 . sub-branches, with J = K a (∆J=∆K a =0). In this case, the spin splittings are not observable. List of Tables Table 1 Symmetry properties of FCO 2 in the X 2 B 2 ground electronic state. Vibration-rotational levels (v 1 v 2 …v 6 )[N K a K c ] exist only are for K a odd if v 4 +v 5 +v 6 = even (resp. K a even for v 4 +v 5 +v 6 = odd).

Table 2 List of the vibrational modes for FCO 2 in the X 2 B 2 ground electronic state.

Table 3 Range of the observed energy levels and the statistical analysis of the results of the energy level calculation.

Table 4 Hamiltonian matrix for the for the {2 1 ,5 2 } interacting vibrational states of FCO 2 Table 5 Vibrational energies, rotational, and spin-rotation constants, as well as coupling constants for the {2 1 ,5 2 } interacting vibrational states of FCO 2

Note: The results are in cm -1 and the quoted errors are one standard deviation. Constants marked with an # were fixed to the ground state values [15] during the least squares fit. Vibration a Fundamental vibration wavenumber (in cm -1 ), Ref. [12] b Band centers in cm -1 .

A 1 1 1 1 1 T z ν 1 , ν 2 , ν 3 A 2 1 1 -1 -1 R z B 1 1 -1 1 -1 T x R y ν 4 , ν 5 B 2 1 -1 -1 1 T y R x X 2 B
c Ref. [12] d Ref. [START_REF] Bailleux | Poster J28 presented at the 20st International Conference on High Resolution Molecular Spectroscopy[END_REF] e This work

N N

Electron spin -rotation interaction in A-type reduction, I r representation:

+ ε + ε + ε = c c cc b b bb a a aa N S N S N S V v v v SR vv ( ) { } ( ) ( ) ( ) ( ) ( ) { } 2 2 z z z z 2 2 vS K 2 2 vS N z 3 z vS K vS KN 2 z z z z 2 vS NK 2 vS N N N S N S N N N 2 1 S . N N N S N S . N N N S S N N 2 1 S . N N - + - + - + + + + δ + + δ + ∆ + ∆ + + ∆ + ∆

  (2)(3)(4)(5). On the other hand, for weaker lines in the P and R branches involving medium K a and K c values (1 <<K a << N, and 0<< K c << N, respectively) the line doublings are clearly observable in the spectrum, since in this case the spin splittings in the upper and lower states differs significantly. Examples of these splittings are given on Figs 2, 3, and 5.

  to get an improved set of upper states parameters allowing better predictions and hence more assignments to be made. This process was repeated iteratively until it appeared that several series were significantly perturbed for N≥ 40 values because of resonances involving the energy levels belonging to the 5 2 dark state located near 965 cm -1 . A model accounting for these resonances together with the spin-rotation interactions was then set up, which allowed more accurate predictions. To illustrate this point, Fig.5gives a portion of the R branch at 986.2 cm -1 : for the (2N-K c )=40 stack, the line by line calculation is significantly improved when the 52 2 1

Figure 2 .

 2 Figure 2. Part of R branch of the ν 2 band of FCO 2 near 976.3 cm -1 .

Figure 3 .

 3 Figure 3. Part of P branch of the ν 2 band of FCO 2 near 955.4 cm -1 .

Figure 4 .

 4 Figure 4.Q branch of the ν 2 band of FCO 2 in the 970.2 cm -1 spectral region.Caption:

Figure 5 . 1

 51 Figure 5. Part of R branch of the ν 2 band of FCO 2 near 986.3 cm -1 .

  Overview of the 940-999 cm-1 spectral region with the nu2 band of fluorocarboxyl radical, FCO2. 279x215mm (150 x 150 DPI) Part of R branch of the nu2 band of FCO2 near 976.3 cm-1. 279x215mm (150 x 150 DPI) Part of P branch of the ν2 band of FCO2 near 955.4 cm-1. 279x215mm (150 x 150 DPI) the nu2 band of FCO2 in the 970.2 cm-1 spectral region. 279x215mm (150 x 150 DPI) Part of R branch of the nu2 band of FCO2 near 986.3 cm-1. 279x215mm (150 x 150 DPI) Page 26 of 26 URL: http://mc.manuscriptcentral.com/tandf/tmph Molecular Physics

  2 is an open -shell molecular

	19 th of November	4
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

  Fermi resonances, and this in agreement with the conclusions of the infrared investigation of the vibrational structure of FCO 2 in noble gas matrices performed by Argüello et al.[12].

	19 th of November	8
	2 1
		F o r
		P
		e
			e r
			R
			e
			v i e
			w
			O n l
			y
		5 1	2 1 resonating levels, Fermi resonances coupling either the 5 2
	2 1 or the 3 2	2 1 resonating energy levels were considered for these test calculations. It
	appeared that the resonances are satisfactorily accounted for when considering only the 5 2

  1 upper state are similar to the ground state values, spin-rotation doublings for this A-type band are observable only for the weaker transitions involving medium K a or K c values in the P and R branches. The ν 2 fundamental band is weakly perturbed by a Fermi -type resonance coupling the 2 1 and 5 2 energy levels.

		List of figures
	Figure 1.
	The final energy level calculation was performed accounting both for the spin-rotation resonances within the 2 1 and 5 2 vibrational states, together with the 2 1 5 2 Fermi-type F o r F o r F o r
	interactions.	P P P
		e e e
		e r e r e r
		R R R
		e e e
		v i e v i e v i e
		w w w
		O n l O n l O n l
		y y y

Table 1

 1

	I	C 2z	σ xz	σ yz	Polar	Axial	Ground
					vector	vector	electronic
							state:

Table 2

 2

	2	ν 6

URL: http://mc.manuscriptcentral.com/tandf/tmph

Table 3

 3

						ν ν ν ν 2 band
						2377 lines,
						1141 levels
					N ≤ 55, K a ≤ 39
	Statistical analysis of the results
	Number of 2 1 spin-rotation levels:	1141
	0	≤	δ	<	001 . 0	cm	1 -	60.9 %
	001 . 0	≤	δ	<	002 . 0	cm	1 -	22.1 %
	002 . 0	≤	δ	<	004 . 0	cm	1 -	12.7 %
	004 . 0	≤	δ	<	008 . 0	cm	1 -	4.3 %
	Standard deviation: 1.7×10 -3 cm -1
					δ	=	obs E -	E	calc

Page 18 of 26 URL: http://mc.manuscriptcentral.com/tandf/tmph

								Molecular Physics
	F o r
	P
			e
				e r
								R
										e
	+	h	v K	N	4 z	,	N	2 xy	+	h	v i e N , N 2 xy 2 z KJ v 2	+	2	h	v J	N	2 x	y	2	2	+
											w
											O n l
																	y

Table 5 Band centers and rotational constants

 5

	Fermi type interactions:
	H	F vv'	=	h	F ' vv 0	+	h	F vv 1	'	N	2	+	h	F vv' 2	N	2 xy	+	...
	with: c.c.: complex conjugate, {A,B}=AB+BA and 2 xy N	=	2 x N N -	2 y

th of November

URL: http://mc.manuscriptcentral.com/tandf/tmph Molecular Physics

Acknowledgments A.P. is grateful to the INSU (Institut national des sciences de l'Univers) of the CNRS for financial support. M.S. is grateful to the three months post-doc position of the "European Science Foundation" through the "Interdisciplinary Tropospheric Research: from the Laboratory to Global Change" (INTROP) Project. We appreciate support from the Deutsche Akademische Austauschdienst (DAAD, PPP-Tschechien, D22-CZ 12/09-10) for the German-Czech collaboration, for support from MEYS of the Czech Republic provided via Research program LC06071 and a grant OC09050 (action COST ES0604) and H.B. and H.W. acknowledge financial support from the Deutsche Forschungsgemeinschaft (DFG).

Table 4

Hamiltonian matrix J 2 1 5 2