S Bessy
email: bessy@lirmm.fr

C Lepelletier

Optical index of fault tolerant routings in WDM networks

Keywords: optical networks, forwarding and optical indices, routing, fault tolerance

introduced the problem of designing f -tolerant routings in optical networks, i.e., routings which still satisfy the given requests even if f failures occur in the network. In this paper, we provide f -tolerant routings in complete and complete balanced bipartite optical networks, optimal according to two parameters: the arc-forwarding index and the optical index. These constructions use tools from design theory and graph theory and improve previous results of Dinitz, Ling and Stinson [4] for the complete network, and Gupta, Maňuch and Stacho [5] for the complete balanced bipartite network.

Introduction

In this paper, we are interested in a problem arising in the design of optical networks. Using models of graph theory and design theory, this topic has been of considerable interest over the last decade (see [START_REF] Beauquier | Graph problems arising from wavelength-routing in all-optical networks[END_REF], [START_REF] Beauquier | Optimal wavelength-routed multicasting[END_REF] or [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF] for instance). Readers may refer to [START_REF] Beauquier | Graph problems arising from wavelength-routing in all-optical networks[END_REF] for a background review of optical networks. The model studied in this article is valid for the so-called wavelength division multiplexing (or WDM) optical network. Such a network is modeled by a symmetric directed graph with arcs representing the fiber-optic links. A request in the network is an ordered pair of graph nodes, representing a possible communication in the network. A set of different requests is an instance in the network. For each request of the instance, we have to select a routing directed path to satisfy it, and the set of all selected paths forms a routing set according to the instance. To make the communications possible, a wavelength is allocated to each routing path, such that two paths sharing an arc do not carry the same wavelength; otherwise the corresponding communications could be perturbed. Given a routing set related to the wavelength assignment, we can define two classical invariants. The arc-forwarding index of the routing set is the maximum number of paths sharing the same arc. In the network, there is a general bound on the number of wavelengths which can transit at the same time in a fiber-optic link, corresponding to the admissible maximal arc-forwarding index. The other invariant, called the optical index of the routing set, is the minimum number of wavelengths to assign to the routing paths in order to ensure that there is no interference in the network.

The main challenge here is to provide, for a given instance, a routing set which minimizes the arc-forwarding index or the optical index, or both if possible.

Our work is a contribution to a variant of this problem, introduced by Maňuch and Stacho [START_REF] Maňuch | On f -wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes[END_REF], in which we focus on possible breakdowns of nodes in the network. Precisely, for a given fixed integer f , we have to provide, for every request, not just one directed path to satisfy it, but rather a set of f +1 directed paths with the same beginning and end nodes (corresponding to the request) and which are internally disjoint. In this routing, if f nodes break down, every request between the remaining nodes could still be satisfied by a previously selected routing path which contains no failed component. Such a routing set of directed paths is called an f -fault tolerant routing or an f -tolerant routing.

In this paper, we focus on the very special cases of complete symmetric directed graphs and complete balanced bipartite symmetric directed graphs. Moreover, we only study the case of all-to-all communication, i.e., where the instance of the problem is the set of all ordered pairs of nodes of the network. Some results on these problems were presented by Gupta, Maňuch and Stacho [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF] and Dinitz, Ling and Stinson [START_REF] Dinitz | Fault tolerant routings with minimum optical index[END_REF]. We improve these results: for complete symmetric directed graphs, we show that optimal routings for the arc-forwarding index given in [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF] are also optimal for the optical index. And for complete balanced bipartite symmetric directed graphs, we provide routings that are optimal for both parameters.

Preliminaries

In this section, we specify the previous definitions and formalize the problem. For the purpose of the paper, we only describe the case of all-to-all communication, but the notions can be extended to any kind of instances. We mainly use the notations proposed in [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF].

We model an all-optical network as a symmetric directed graph D = (V (D), A(D)), where V (D) is the vertex set of D and A(D) is the arc set with the additional property that if (u, v) ∈ A(D) then (v, u) ∈ A(D). If no confusion is possible, we simply write V and A instead of V (D) and A(D), respectively. All paths and circuits are considered as oriented.

A directed graph D is strongly connected if, for every two vertices x and y of D, there is a path from x to y in D. In a symmetric directed graph, strong connectivity is equivalent to connectivity of the underlying non-oriented graph. So, for an integer k ≥ 1, a symmetric directed

graph D is k-connected if, for every set {x 1 , . . . , x k-1 } of vertices of D, D \ {x 1 , . . . , x k-1 } is strongly connected.
For a fixed positive integer f , an f -tolerant routing in D is a set of paths:

R = {P i (u, v) : u, v ∈ V, u = v, i = 0, . . . , f }
where, for each pair of distinct vertices u, v ∈ V , the paths P 0 (u, v), . . . , P f (u, v) are internally vertex disjoint. Note that such a set of paths exists if and only if the connectivity of the directed graph is large enough (at least f + 1), which will be the case in complete and complete bipartite networks for suitable f . The basic parameters for WDM optical networks, the arc-forwarding index and the optical index, are generalized in f -tolerant routings. The load of an arc in R is the number of directed paths of R containing it. By extension, the maximum load over all the arcs of D is the load of the routing, which is also called the arc-forwarding index of R and is denoted by π(R). Each path of R receives a wavelength in the network to enable the communication and, to avoid interference, two paths sharing an arc do not receive the same wavelength. Like graph coloring, we speak about wavelengths as colors to assign to the paths of R. Finally, the optical index of R, denoted w(R), is the minimum number of wavelengths to assign to paths of R so that no two paths sharing an arc receive the same wavelength. In other words, w(R) is exactly the chromatic number of the graph with vertex set R and where two paths of R are linked if they share the same arc of D (known as the path graph of R).

The goal is to minimize π(R) and w(R). So the f -tolerant arc-forwarding index of D and the f -tolerant optical index of D are respectively defined by:

π f (D) = min R π(R) w f (D) = min R w(R)
where the minima span all the possible routing sets R. A routing set achieving one of the bounds is said to be optimal for the arc-forwarding index or optimal for the optical index, respectively.

For a routing set R, all paths sharing the same arc must receive different wavelengths in the computation of w(R). In particular, we have π(R) ≤ w(R). By considering a routing set which is optimal for the optical index, we obtain π f (D) ≤ w f (D). The equality was conjectured by Maňuch and Stacho [START_REF] Maňuch | On f -wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes[END_REF].

Conjecture 1 (J. Maňuch, L. Stacho, 2003, [7]) Let D be a symmetric directed k-connected

graph. For any f , 0 ≤ f < k, we have π f (D) = w f (D).
For f = 0 (without tolerating any faults), the conjecture was previously raised by Beauquier et al. [START_REF] Beauquier | Graph problems arising from wavelength-routing in all-optical networks[END_REF].

Let K ⋆ n denote the complete symmetric directed graph with vertex set {x 1 , . . . , x n } and arc set {x i x j : i = j}. The complete balanced bipartite symmetric digraph K ⋆ n,n is the directed graph on vertex set X∪Y with X = {x 1 , . . . , x n } and Y = {y 1 , . . . , y n } and arc set {xy, yx : x ∈ X, y ∈ Y }.

The arc-forwarding indices of K ⋆ n and K ⋆ n,n were computed by Gupta, Maňuch and Stacho in [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF].

Moreover, they give w f (K ⋆ n ) and w f (K ⋆ n,n ) up to a multiplicative factor. In [START_REF] Dinitz | Fault tolerant routings with minimum optical index[END_REF], Dinitz, Ling and Stinson compute, among other things, w f (K ⋆ n ) up to an additive constant in some cases. In the next two sections, we provide exact values for w f (K ⋆ n ) and w f (K ⋆ n,n ) and hence prove Conjecture 1 for the complete symmetric directed graph and the complete balanced bipartite symmetric directed graph.

Complete optical network

It is easy to provide a lower bound for the arc-forwarding index of K ⋆ n . Indeed, any two vertices x and y of K ⋆ n have to be linked in an f -tolerant routing by f + 1 internally disjoint paths. If one of these paths has length one (the direct arc xy), all the others have length at least two, and at least 2f + 1 arcs are needed to ensure f -tolerant communication from x to y. So, by an average argument, one arc of K ⋆ n must have load at least 2f + 1, providing w f (K ⋆ n ) ≥ 2f + 1. In the case of K ⋆ n , Gupta, Maňuch and Stacho prove that this lower bound gives exactly the value of the arc-forwarding index. Indeed, they construct f -tolerant routings through families of independent idempotent Latin squares in [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF], which are optimal for the arc-forwarding index.

Theorem 2 (A. Gupta, J. Maňuch, L.Stacho, 2005, [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF]) For every f with 0 ≤ f ≤ n -2,

we have π f (K ⋆ n ) = 2f + 1.
They also partially bound the optical index of their f -tolerant routings, proving that w f (K ⋆ n ) ≤ 3f + 1 for some f . This result was improved by Dinitz, Ling and Stinson [START_REF] Dinitz | Fault tolerant routings with minimum optical index[END_REF], who gave a better multiplicative factor for some infinite sets of values of n and the optimal index up to an additive constant for another infinite set of values of n. We improve these results by showing that every f -tolerant routing set of K ⋆ n which is optimal for the arc-forwarding index is also optimal for the optical index.

Theorem 3 For every f , 0 ≤ f ≤ n -2, and every f -tolerant routing set R of K ⋆ n with π(R) = π f (K ⋆ n ) = 2f + 1, we have w(R) = 2f + 1.
In particular, we have

w f (K ⋆ n ) = π f (K ⋆ n ) = 2f + 1.
Proof. Let f be fixed with 0 ≤ f ≤ n -2 and consider an f -tolerant routing R of K ⋆ n which is optimal for the arc-forwarding index, i.e., of value 2f + 1. By the tightness of the lower bound, for any two vertices x and y of K ⋆ n there is exactly one path xy of length 1 and f paths of length 2 from x to y in R (otherwise, summing up the total load gives π(R) ≥ 2f + 2). Hence, every arc of K ⋆ n has a load of exactly 2f + 1 and appears in one path of length 1 and 2f paths of length two in R. Now, define the graph H with vertex set being the set of the arcs of K ⋆ n and link two arcs of K ⋆ n if they belong to the same path of R of length 2. Thus, we have a one-to-one correspondence between the edge set of H and the paths of length 2 of R. Since each arc of K ⋆ n belongs to exactly 2f paths of R of length 2, H is regular with degree 2f . By Vizing's Theorem (see [START_REF] Diestel | Graph theory[END_REF] or [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF]), the edges of H can be colored with 2f + 1 distinct colors such that any two adjacent edges receive distinct colors. This provides a coloring of the paths of length 2 of R with 2f + 1 colors. To conclude, a path of length 1 of R intersects exactly 2f paths of length 2 and we can color this path with the remaining color.

Moreover, the edge-coloring provided by Vizing's Theorem can be computed in polynomial time (polynomial in the size of the input graph, H here). So, given an optimal routing for the arc-forwarding index, this proof gives a polynomial algorithm (polynomial in n and f ) to obtain a wavelength assignment for a routing which is optimal for the optical index.

Complete balanced bipartite optical network

In this section, we compute the exact optical index of K ⋆ n,n and thus prove Conjecture 1 for this family of graphs. This improves the result in [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF], where the upper bound given on the optical index of K ⋆ n,n is 20% higher than the conjectured optimal value.

Theorem 4 For any n ≥ 1 and any

f with 0 ≤ f ≤ n -1, we have w f (K ⋆ n,n ) = π f (K ⋆ n,n ).
To prove Theorem 4, we provide a routing set for K ⋆ n,n which is optimal both for the arcforwarding index and the optical index. The construction depends on the values of n and f .

Recall that X ∪ Y denotes the canonical partition of K ⋆ n,n , with X = {x 1 , . . . , x n } and Y = {y 1 , . . . , y n }. For convenience, indices of the vertices of X and Y are computed modulo n.

Routing set and arc-forwarding index

We use the paths of minimum length to route in K ⋆ n,n . Indeed, for two vertices x and y, we use paths of length 2 when x and y belong to the same partite set of K ⋆ n,n and one path of length 1 and other paths of length 3 (if f > 0) when x and y do not belong to the same partite set. The main challenge here is to pack the paths of length 3 in order to provide the right optical index.

This will be achieved by using the following decomposition result.

Theorem 5 (Tillson, 1980, [8]) The arcs of K ⋆ n can be partitioned into Hamiltonian circuits if and only if n = 4 and n = 6.

For n = 4 and n = 6, {C 1 , . . . , C n-1 } denotes a set of n -1 Hamiltonian circuits which partition the arcs of K ⋆ n . Let {1, . . . , n} denote the vertex set of

K ⋆ n . Moreover, for a vertex i of K ⋆ n and a circuit C k , the out-neighbor of i in C k is denoted C k (i). We use C k as a functional notation: for p ≥ 1, C p k (i) = C k (C p-1 k (i))
. Moreover, we compute the powers of C k modulo n,

in particular C 0 k (i) = i and C -1 k (i) is the in-neighbor of i in C k .
The previous Hamiltonian decomposition is used to route paths of length 3 in K ⋆ n,n . For paths of length 2, we use a Latin square A of order n, i.e., a n × n matrix in which each row and each column is a permutation of the set {1, . . . , n}. Moreover, we require A to be idempotent: for every i, 1 ≤ i ≤ n, we have A(i, i) = i. An idempotent Latin square exists for each value of n, except for n = 2 (see [START_REF] Lindner | Design theory[END_REF], Chapter 2, for an explicit construction). For 0 ≤ k ≤ n -1, M k = {x i y i+k , y i+k x i : 1 ≤ i ≤ n}, denotes the symmetric orientations of n disjoint matchings which partition the arcs of K ⋆ n,n (see Figure 1). The indices of M k are computed modulo n. In our figures, we represent two symmetric arcs by a (non-oriented) edge.

x x 2 1 x x x n-1 n 3 x x 2 1 x x x n-1 n 3 x x 2 1 x x x n-1 n 3 y y 2 1 y y y n-1 n 3 y y 2 1 y y y n-1 n 3 y y 2 1 y y y n-1 n 3 M M M 1 2 0 Figure 1: Some matchings M k .
Now, for n = 2, n = 4 and n = 6, we describe three kinds of paths to construct the routing set:

-Paths of length 1 between vertices which belong to different partite sets of K ⋆ n,n :

D 0 [X, Y ] = {x i y j : 1 ≤ i ≤ n, 1 ≤ j ≤ n} D 0 [Y, X] = {y i x j : 1 ≤ i ≤ n, 1 ≤ j ≤ n} D 0 = D 0 [X, Y ] ∪ D 0 [Y, X]
-Paths of length 3 between vertices which belong to different partite sets of

K ⋆ n,n , for 1 ≤ k ≤ n -1: D k [X, Y ] = {x i y C -1 k (j) x C k (i) y j : 1 ≤ i ≤ n, 1 ≤ j ≤ n} D k [Y, X] = {y i x C -1 k (j) y C k (i) x j : 1 ≤ i ≤ n, 1 ≤ j ≤ n} D k = D k [X, Y ] ∪ D k [Y, X]
-Paths of length 2 between vertices which belong to the same partite set of

K ⋆ n,n , for 0 ≤ k ≤ n -1: S k [X, X] = {x i y A(i,j)+k x j : 1 ≤ i ≤ n, 1 ≤ j ≤ n, i = j} S k [Y, Y ] = {y i x A(i,j)+k+⌈n/2⌉ y j : 1 ≤ i ≤ n, 1 ≤ j ≤ n, i = j} S k = S k [X, X] ∪ S k [Y, Y ]
And for a fixed f , 0 ≤ f ≤ n -1, we define the routing set R f by

R f = f k=0 (S k ∪ D k )
Note that, by construction, for distinct vertices x and y of K ⋆ n,n , R f contains exactly f + 1 internally disjoint paths from x to y. So, R f is an f -tolerant routing for an all-to-all instance in K ⋆ n,n . Moreover, note that every arc of K ⋆ n,n appears exactly once in D 0 and three times in Using these remarks, we can give the arc-forwarding index of R f . The computation of π f (K ⋆ n,n ) was obtained in [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF].

D k for 1 ≤ k ≤ n -1 (for instance the arc x i y j appears in D k in paths from x i to y C k (j) , from x C -1 k (i) to y j and from y C -1 k (j) to x C k (i) ). For 0 ≤ k ≤ n,
Lemma 6 (A. Gupta, J. Maňuch, L. Stacho, 06, [START_REF] Gupta | Fault tolerant forwarding and optical indexes: a design theory approach[END_REF]) The arc-forwarding of K ⋆ n,n is:

π f (K ⋆ n,n ) =          5f + 3 for 0 ≤ f ≤ ⌈n/2⌉ -2 5f + 2 for ⌈n/2⌉ -1 ≤ f ≤ n -2 5f + 1 for f = n -1
In fact, we prove that R f is optimal for the arc-forwarding index.

Lemma 7 For every f , 0 ≤ f ≤ n -1, the routing set R f satisfies π(R f ) = π f (K ⋆ n,n ).
Proof. For 0 ≤ f ≤ ⌈n/2⌉ -2, every arc of K ⋆ n,n appears at least 5 times in

S k ∪ D k for 1 ≤ k ≤ f and 3 times in S 0 ∪ D 0 , so the computation of π(R f ) is clear. For f ≥ ⌈n/2⌉ -1, every arc of K ⋆ n,n is in a matching M k or M k+⌈n/2⌉ for some k, 0 ≤ k ≤ f and thus is not in a path of one of the S k [X, X] or S k [Y, Y ]. We then save 1 in the computation of π(R f ) in these cases. Finally, if f = n -1, every arc of K ⋆ n,n is in a matching M k and in a matching M k ′ +⌊n/2⌋
for some suitable k and k ′ in {0, . . . , n -1}. So, every arc of K ⋆ n,n is not in any path of S k [X, X] and not in any path of S k ′ [Y, Y ], and we save two in the computation of π(K ⋆ n,n ).

We then have a lower bound for the optical index of K ⋆ n,n , and now we prove that the routing set R f achieves this bound.

Packing the paths of R f

A color class of paths of R f is set of paths which are pairwise arc-disjoint. To construct the different color classes, we need the following notations and definitions. To indicate a path or a set of paths of R f , we always specify the subset

D k or S k it belongs to. For instance, S 0 [X, X]{x 1 y A(1,2) x 2 } is the path x 1 y A(1,2) x 2 of S 0 [X, X] and D 0 {M 1 } is the set of paths in M 1 of D 0 .
We use the notation ⋆ as a 'joker' instead of all the possible path names. For instance, S 0 [X, X]{⋆ y 1 ⋆} stands for all paths of S 0 [X, X] whose intermediate vertex is y 1 . We specially focus on two particular subsets of paths. For k ≥ 1 and x i , a

vertex of K ⋆ n,n , D k [X, Y ]{x i ⋆ x C k (i) ⋆} contains the n paths of D k which start at x i and whose third vertex is x C k (i) . As (C k (1), C k (2), . . . , C k (n)) is a permutation of (1, 2, . . . , n),
note that these paths are pairwise arc-disjoint and that they cover exactly all arcs beginning at x i , all arcs beginning at x C k (i) and all arcs ending at x C k (i) . Moreover, we have

n-1 l=0 D k [X, Y ]{x C l k (1) ⋆ x C l+1 k (1) ⋆} = D k [X, Y ]. The set D k [X, Y ]{x i ⋆ x C k (i)
⋆} and its representation on X, which shows the saturated in and out-neighborhood, are depicted in Fig- ure 2. Similarly, we will use the sets

D k [X, Y ]{⋆ y i ⋆ y C k (i) }, D k [Y, X]{⋆ x i ⋆ x C k (i) } and D k [Y, X]{y i ⋆ y C k (i) ⋆}. 2 1 3 n-1 n i k x x x x x x x C (i) 2 1 3 n-1 n i k x x x x x x x C (i) y y 2 1 3 y y y n-1 n + + [X,Y] D k _ Figure 2: The set of paths D k [X, Y ]{x i ⋆ x C k (i)
⋆} and its representation on X.

In addition, for 0

≤ k ≤ n -1 and 1 ≤ i ≤ n, S k [Y, Y ]{⋆ x i ⋆} denotes the set of paths S k [Y, Y ]{⋆ x i ⋆}∪D 0 {x i y i+k+⌈n/2⌉ , y i+k+⌈n/2⌉ x i }. As S k [Y, Y ] and M k+⌈n/2⌉ are disjoint, S k [Y, Y ]{⋆ x i ⋆}
disjoint from D 0 {M k }. + - 2 1 3 x x x i x n-1 n x x 2 1 3 x x x i x n-1 n x x y y 2 1 3 y yi+k+ n/2 y y n-1 n y y 2 1 3 y yi+k+ n/2 y y n-1 n 2 1 3 x x x i x n-1 n x x S [Y,Y] k Figure 3: The sets S k [Y, Y ]{⋆ x i ⋆}, S k [Y, Y ]{⋆ x i ⋆} and the representation of S k [Y, Y ]{⋆ x i ⋆} on X.
Now we can define the colors classes. They are constructed differently according to the value of f : we distinguish three main cases following the residue of n modulo 3. However, some particular cases occur: n = 2 due to the non-existence of an idempotent Latin square of order 2, n = 4 and n = 6 which are exceptions to Tillson's Theorem, and n = 1 and n = 5 for which the techniques used in general cases n ≡ 1 (mod 3) and n ≡ 2 (mod 3) cannot be applied.

Moreover, for any value of n, the case f = 0 is different from the other cases.

Routings without fault

The case f = 0 is simpler than other cases in the sense that the paths of length 1 form a proper color class, whereas for f > 0 these paths are used to complete other color classes. More precisely, R 0 = D 0 ∪ S 0 and to obtain the optical index, we assign one different color to each of these sets of paths:

D 0 , S 0 [X, X] and S 0 [Y, Y ]. So, for every n ≥ 1, we have w 0 (K ⋆ n,n ) = π 0 (K ⋆ n,n ) = 3.

Optical index in case n ≡ 0 (mod 3)

This is the simplest case, so paths of length 2 and 3 can be packed separately. For any k,

1 ≤ k ≤ n -1,
to color paths of length 3, we define:

c 3 k = n/3-1 t=0 D k [Y, X]{⋆ x C 3t k (1) ⋆ x C 3t+1 k (1) } ∪ D k [X, Y ]{x C 3t+1 k (1) ⋆ x C 3t+2 k (1) ⋆} c 4 k = n/3-1 t=0 D k [Y, X]{⋆ x C 3t+1 k (1) ⋆ x C 3t+2 k (1) } ∪ D k [X, Y ]{x C 3t+2 k (1) ⋆ x C 3t+3 k (1) ⋆} c 5 k = n/3-1 t=0 D k [Y, X]{⋆ x C 3t+2 k (1) ⋆ x C 3t+3 k (1) } ∪ D k [X, Y ]{x C 3t+3 k (1) ⋆ x C 3t+4 k (
• If 1 ≤ f ≤ ⌈n/2⌉ -2, for 0 ≤ k ≤ f , we fix: c 2 k = S k [X, X] + - - + + - x C (1) k 2 x C (1) k 4 x C (1) k 3 x C (1) k 5 + - - + + - x C (1) k n-2 x C (1) k n-1 x C (1) k n-3 x k C (1) D [X,Y] x 1 + - - + + - [Y,X] D [X,Y] D [Y,X] D [X,Y] D [Y,X] D k k k k k k
∪ c 2 0 ∪ f k=1 {c 1 k , c 2 k , c 3 k , c 4 k , c 5 k } (sole D 0 {M ⌈n/2⌉ }, D 0 {M 1+⌈n/2⌉ }, . . . , D 0 {M f +⌈n/2⌉ } are used)
. So, we put the remaining paths of D 0 in a class c 3 0 , and we obtain, in this case,

w f (K ⋆ n,n ) = 5f + 3. • If ⌈n/2⌉ -1 ≤ f ≤ n -2,
we have enough space to pack the paths of length one in the other classes. Indeed,

c 1 0 ∪ c 2 0 ∪ f k=1 {c 1 k , c 3 k , c 4 k , c 5 k } does not contain the direct paths D 0 {M f +1+⌈n/2⌉ }, D 0 {M f +2+⌈n/2⌉ }, . . . , D 0 {M ⌈n/2⌉-1 }, with n ≤ f +1+⌈n/2⌉ ≤ n+⌈n/2⌉- 1 (note that indices of M i are computed modulo n). So, for 0 ≤ k ≤ f , we set: c 2 k = S k [X, X] if f + 1 + ⌈n/2⌉ -n ≤ k ≤ ⌈n/2⌉ -1 c 2 k = S k [X, X] else
So, all paths of D 0 are used, and we obtain w f (K ⋆ n,n ) = 5f + 2.

• If f = n -1, we should save another color. This time, all paths of length 1 are packed in n-1 k=0 c 2 k and the second saved color is obtained by optimally packing the set of paths {S k [X, X] : 0 ≤ k ≤ n -1} using only n -1 colors. First, we complete the color class c 2 1 . We start by covering all the arcs beginning at x 1 and all the arcs ending at x 2 , which can be done by placing in c 2 1 all the paths from

x 1 to x 2 : n-1 i=0 S i [X, X]{x 1 y A(1,2)+i x 2 } (corresponding to the paths of n-1 i=0 S i [X, X] which use the value A(1,
2) in the matrix A). Then, we focus on the arcs beginning at x 2 and the arcs ending at x 3 using the paths:

n-1 i=0 S i [X, X]{x 2 y A(2,
3)+i x 3 } (paths using A(2, 3)). Subsequently, we cover the arcs beginning at x p and the arcs ending at x p+1 for p = 1, 2, . . . , n (corresponding to all paths using values A(p, p + 1) in A). So, c 2 1 forms a color class which covers exactly once all arcs of K ⋆ n,n . Once c 2 1 is complete, we proceed in the same way to obtain c 2 2 , using, this time, for p = 1, 2, . . . , n, the paths of n-1 i=0 S i [X, X] obtained through the values A(p, p+2)

to cover the arcs from x p and those to x p+2 .

In general way, 1 ≤ k ≤ n -1, c 2 k is constructed using the paths obtained through the values A(p, p + k), for p = 1, 2, . . . , n. More precisely, we define:

c 2 k = n j=1 n-1 i=0 S i [X, X]{x j ⋆ x j+k }
Finally, we obtain the color classes

{c 1 0 } ∪ n-1 k=1 {c 1 k , c 2 k , c 3 k , c 4 k , c 5
k } which give the optimal value for the optical index:

w f (K ⋆ n,n ) = 5f + 1.

Optical index in case n ≡ 1 (mod 3)

This time a color class cannot be composed with only paths of length 3. For 1 ≤ k ≤ n -1, we pack together a maximum number of paths of length 3 (i.e., from D k ) in classes c 3 k , c 4 k and c 5 k , which we supplement with paths of length 2 from c 1 k (i.e., from S k ). Consequently, c 1 k contains the main part of paths of length 2 and the remaining paths of length 3, which is possible as soon as n ≥ 3. Precisely, for n ≥ 3, we construct c 1 0 = S 0 [Y, Y ], and, for 1 ≤ k ≤ n -1, we set:

c 3 k = (n-1)/3-1 t=0 D k [Y, X]{⋆ x C 3t+1 k (1) ⋆ x C 3t+2 k (1) } ∪ D k [X, Y ]{x C 3t+2 k (1) ⋆ x C 3t+3 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x 1 ⋆} c 4 k = (n-1)/3-1 t=0 D k [Y, X]{⋆ x C 3t+2 k (1) ⋆ x C 3t+3 k (1) } ∪ D k [X, Y ]{x C 3t+3 k (1) ⋆ x C 3t+4 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C k (1) ⋆} c 5 k = (n-1)/3-1 t=0 D k [Y, X]{⋆ x C 3t+3 k (1) ⋆ x C 3t+4 k (1) } ∪ D k [X, Y ]{x C 3t+4 k (1) ⋆ x C 3t+5 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 2 k (1) ⋆} c 1 k = S k [Y, Y ] \ S k [Y, Y ]{⋆ x 1 ⋆} ∪ S k [Y, Y ]{⋆ x C k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 2 k (1) ⋆} ∪ D k [Y, X]{⋆ x 1 ⋆ x C k (1) } ∪ D k [X, Y ]{x C k (1) ⋆ x C 2 k (1) ⋆}
As previously, Figure 5 shows the representation on X of c 3 k , where the vertices of X are sorted along C k . A shift of one vertex on the right (modulo n) of the sets of paths gives the representation of c 4 k for the same k. And a shift of two vertices gives the representation of c 5 k .

+ x C (1) k 2 x C (1) k 4 x C (1) k 3 x C (1) k 5 x C (1) k n-2 x C (1) k n-1 x C (1) k n-3 x k C (1)
x 1 Figure 6 gives the representation on X of the color classes

+ - - + + - + + - + - - + - + - - [Y,Y] S k D [X,Y] [Y,X] D [Y,X] D D [X,Y] [Y,X] D k k k k k
c 1 k . Note that c 1 k is well defined only if n ≥ 3. + - + - x C (1) k 4 x C (1) k 3 x 1 x C (1) k 2 x C (1) k n-3 x C (1) k n-2 x C (1) k n-1 + + - k [Y,Y] S k [Y,Y] S k [Y,Y] S k [Y,Y] S k [Y,Y] S + - + - + - + - - x k C (1) [Y,X] D [X,Y] D k k Figure 6:
The representation on X of the color class c 1 k , where the vertices of X are sorted along C k . Now, the exact optical index will be obtained by packing the remaining paths of length 1 and 2, as done previously: the classes c 2 k for 0 ≤ k ≤ f are defined exactly as in the case n ≡ 0 (mod 3). Indeed, even if the definitions of classes c 1 k , c 3 k , c 4 k and c 5 k have changed, the use of the paths D 0 {M i } is still the same: for every k, 0 ≤ k ≤ f , we have

D 0 {M k } ⊂ c 1 k ∪ c 3 k ∪ c 4 k ∪ c 5 k .
Finally, we obtain:

• If 1 ≤ f ≤ ⌈n/2⌉ -2, w f (K ⋆ n,n ) = 5f + 3. • If ⌈n/2⌉ -1 ≤ f ≤ n -2, w f (K ⋆ n,n ) = 5f + 2. • And, if f = n -1, w f (K ⋆ n,n ) = 5f + 1.
4.6 Optical index in case n ≡ 2 (mod 3)

We proceed as in case n ≡ 1 (mod 3), except that this time we supplement each class of paths of - Figure 8 gives the representation on X of the color classes c 1 k . Note that c 1 k is well defined only if n ≥ 6.

c 3 k = (n-2)/3-1 t=0 D k [Y, X]{⋆ x C 3t+2 k (1) ⋆ x C 3t+3 k (1) } ∪ D k [X, Y ]{x C 3t+3 k (1) ⋆ x C 3t+4 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x 1 ⋆} ∪ S k [Y, Y ]{⋆ x C k (1) ⋆} c 4 k = (n-2)/3-1 t=0 D k [Y, X]{⋆ x C 3t+4 k (1) ⋆ x C 3t+5 k (1) } ∪ D k [X, Y ]{x C 3t+5 k (1) ⋆ x C 3t+6 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 2 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 3 k (1) ⋆} c 5 k = (n-2)/3-1 t=0 D k [Y, X]{⋆ x C 3t+6 k (1) ⋆ x C 3t+7 k (1) } ∪ D k [X, Y ]{x C 3t+7 k (1) ⋆ x C 3t+8 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 4 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 5 k (1) ⋆} c 1 k = S k [Y, Y ] \ S k [Y, Y ]{⋆ x 1 ⋆} ∪ S k [Y, Y ]{⋆ x C k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 2 k (1) ⋆}∪ S k [Y, Y ]{⋆ x C 3 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 4 k (1) ⋆} ∪ S k [Y, Y ]{⋆ x C 5 k (1) ⋆} ∪ D k [Y, X]{⋆ x 1 ⋆ x C k (1) } ∪ D k [X, Y ]{x C k (1) ⋆ x C 2 k (1) ⋆}∪ D k [Y, X]{⋆ x C 3 k (1) ⋆ x C 4 k (1) } ∪ D k [X, Y ]{x C 4 k (1) ⋆ x C 5 k (
+ + - x C (1) k 2 x C (1) k 4 x C (1) k 3 x C (1) k 5 x C (1) k n-2 x C (1) k n-1 x C (1) k n-3 x k C (1) x 1 [Y,Y] S k [Y,Y] S k + - - + + - D [X,Y] [Y,X] D [Y,X] D k k k + - - + + - D [X,Y] [Y,X] D k k + -
+ + - - - + + - + - + - + + - - - + x C (1) k 4 x C (1) k 3 x 1 x C (1) k 2 x C (1) k n-1 x C (1) k n-2 x C (1) k 5 x C (1) k 6 [Y,X] D [X,Y] D k k [Y,X] D [X,Y] D k k k [Y,Y] S k [Y,Y] S k [Y,Y] S x k C (1)
Figure 8: The representation on X of the color class c 1 k , where the vertices of X are sorted along C k .

To conclude, the classes c 2 k for 0 ≤ k ≤ f are defined exactly as in the cases n ≡ 0 (mod 3) and n ≡ 1 (mod 3). Once again, the paths D 0 {M k } are used as previously, and we obtain:

• If 1 ≤ f ≤ ⌈n/2⌉ -2, w f (K ⋆ n,n ) = 5f + 3. • If ⌈n/2⌉ -1 ≤ f ≤ n -2, w f (K ⋆ n,n ) = 5f + 2. • And, if f = n -1, w f (K ⋆ n,n ) = 5f + 1.

Remaining particular cases

As previously noted, five cases were not treated in the previous study: n = 2 because of the non-existence of a Latin square of order 2, n = 4 and n = 6 due to the exception to Tillson's Theorem and n = 1 and n = 5, where the general techniques for n = 1 mod 3 and n = 2 mod 3 fail. For all of these cases, we provide routings that give, for every f , 0

≤ f ≤ n -1, w f (K ⋆ n,n ) = π f (K ⋆ n,n
). These cases illustrate the above-mentioned general method and are studied in an appendix, available at: http://www.lirmm.fr/~bessy/publis.html. More precisely, the first circuit provides the following classes:

C 1 C 1 C 3 C 3 C 1 2 3 4 1 C 1 C 2 C 3 C 2 C 2 C 3 2 3
c 1 = D 1 [Y, X]{⋆ x 1 ⋆ x 2 } ∪ D 1 [X, Y ]{x 2 ⋆ x 3 ⋆} ∪ S 1 [Y, Y ]{⋆ x 4 ⋆} c 2 = D 1 [Y, X]{⋆ x 2 ⋆ x 3 } ∪ D 3 [X, Y ]{x 3 ⋆ x 1 ⋆} ∪ S 2 [Y, Y ]{⋆ x 4 ⋆} c 3 = D 3 [Y, X]{⋆ x 3 ⋆ x 1 } ∪ D 1 [X, Y ]{x 1 ⋆ x 2 ⋆} ∪ S 3 [Y, Y ]{⋆ x 4 ⋆}
From the second circuit, we obtain:

c 4 = D 3 [Y, X]{⋆ x 1 ⋆ x 3 } ∪ D 1 [X, Y ]{x 3 ⋆ x 4 ⋆} ∪ S 1 [Y, Y ]{⋆ x 2 ⋆} c 5 = D 1 [Y, X]{⋆ x 3 ⋆ x 4 } ∪ D 1 [X, Y ]{x 4 ⋆ x 1 ⋆} ∪ S 2 [Y, Y ]{⋆ x 2 ⋆} c 6 = D 1 [Y, X]{⋆ x 4 ⋆ x 1 } ∪ D 3 [X, Y ]{x 1 ⋆ x 3 ⋆} ∪ S 3 [Y, Y ]{⋆ x 2 ⋆}
From the third circuit, we obtain:

c 7 = D 2 [Y, X]{⋆ x 1 ⋆ x 4 } ∪ D 3 [X, Y ]{x 4 ⋆ x 2 ⋆} ∪ S 1 [Y, Y ]{⋆ x 3 ⋆} c 8 = D 3 [Y, X]{⋆ x 4 ⋆ x 2 } ∪ D 2 [X, Y ]{x 2 ⋆ x 1 ⋆} ∪ S 2 [Y, Y ]{⋆ x 3 ⋆} c 9 = D 2 [Y, X]{⋆ x 2 ⋆ x 1 } ∪ D 2 [X, Y ]{x 1 ⋆ x 4 ⋆} ∪ S 3 [Y, Y ]{⋆ x 3 ⋆}
Finally, we obtain from the fourth circuit:

c 10 = D 3 [Y, X]{⋆ x 2 ⋆ x 4 } ∪ D 2 [X, Y ]{x 4 ⋆ x 3 ⋆} ∪ S 1 [Y, Y ]{⋆ x 1 ⋆} c 11 = D 2 [Y, X]{⋆ x 4 ⋆ x 3 } ∪ D 2 [X, Y ]{x 3 ⋆ x 2 ⋆} ∪ S 2 [Y, Y ]{⋆ x 1 ⋆} c 12 = D 2 [Y, X]{⋆ x 3 ⋆ x 2 } ∪ D 3 [X, Y ]{x 2 ⋆ x 4 ⋆} ∪ S 3 [Y, Y ]{⋆ x 1 ⋆}
The next class uses S 0 [Y, Y ] and the last matching of D 0 :

c 13 = S 0 [Y, Y ]
To conclude, as previously in the case n ≡ 0 (mod 3), we pack the paths of 3 k=0 S k [X, X] in three color classes:

c 14 = 4 j=1 3 i=0 S i [X, X]{x j ⋆ x j+1 } c 15 = 4 j=1 3 i=0 S i [X, X]{x j ⋆ x j+2 } c 16 = 4 j=1 3 i=0 S i [X, X]{x j ⋆ x j+3 }
Finally, we obtain w 3 (K ⋆ 4,4 ) = π 3 (K ⋆ 4,4 ) = 16.

D Routing in K ⋆

5,5

We are in the case n ≡ 2 (mod 3), but the general decomposition is only valid for n ≥ 6. Indeed, To simplify the notation, we fix, in Figure 11, a decomposition of the arcs of K ⋆ 5 . Using this decomposition we define the routing sets as previously, in Section 4.1. Now, we detail how to pack the paths for all values of f . The case n = 6 is the second exception to Tillson's Theorem of decomposition, so we define in Figure 12 the partition of the arcs of K ⋆ 6 . Then, for the different values of f , the routings are defined as previously, in Section 4.1. As all the circuits involved in this decomposition have length 3 or 6, the computation of w f works exactly as in general case n ≡ 0 (mod 3). Finally, we obtain, for all f = 0, . . . , 5,

for
w f (K ⋆ 6,6 ) = π f (K ⋆ 6,6
), which completes the proof of Theorem 4.

  the routing S k behaves slightly differently: S k [X, X] contains only pairwise arc-disjoint paths and the same holds for S k [Y, Y ]. Moreover, S k [X, X] and M k are disjoint and every arc not in M k appears exactly once in S k [X, X]; on the other hand, S k [Y, Y ] and M k+⌈n/2⌉ are disjoint and every arc not in M k+⌈n/2⌉ appears exactly once in S k [X, X].

  contains only arc-disjoint paths. Moreover, it contains exactly all arcs beginning and ending at x i , and we have n i=1 S k [Y, Y ]{⋆ x i ⋆} = S k [Y, Y ]∪D 0 {M k+⌈n/2⌉ }. This set and the representation of S k [Y, Y ]{⋆ x i ⋆} on X are shown in Figure 3. Similarly, we will use the sets S k [X, X]{⋆ y i ⋆},

  1) ⋆} In Figure 4, we give the representation on X of c 3 k , where the vertices of X are sorted along C k . A shift of one vertex on the right side (modulo n) of the sets of paths gives the representation of c 4 k , for the same k. And a shift of two vertices gives the representation of c 5 k . Then, note that every path of D k [X, X] belongs to one of the class c 3 k , c 4 k or c 5 k . For k ∈ {0, . . . , n -1}, we also define c 1 k = S k [Y, Y ]. Now, we pack the remaining paths of length 1 and 2 in classes c 2 k according to the value of f .

Figure 4 :

 4 Figure 4: The representation on X of the color class c 3 k , where the vertices of X are sorted along C k .

Figure 5 :

 5 Figure 5: The representation on X of the color class c 3 k , where the vertices of X are sorted along C k .

length 3

 3 with two sets of paths from S k [Y, Y ]. Conversely, the classes c 1 k contain the remaining paths of S k [Y, Y ] and 4 sets of paths of length 3 from D k , provided that n ≥ 6. Precisely, for n ≥ 6, we construct c 1 0 = S 0 [Y, Y ], and for 1 ≤ k ≤ n -1, we set:

  1) ⋆} Once again, we give in Figure 7 the representation on X of c 3 k , assuming that vertices of X are sorted along C k . A shift of two vertices on the right side (modulo n) of the sets of paths gives the representation of c 4 k , for the same k. And a shift of four vertices gives the representation of c 5 k .

Figure 7 :

 7 Figure 7: The representation on X of the color class c 3 k , where the vertices of X are sorted along C k .

3 Figure 9 :

 39 Figure 9: The chosen decomposition of the arcs of K ⋆ 4 .

4 1 C 2 Figure 10 :

 1210 Figure 10: New decomposition of the arcs of K ⋆ 4 in case f = 3.

  every k, we need six sets of S k [Y, Y ] centered on six different vertices to complete the three color classes constructed from the paths of D k . In the case n = 5, we need to use paths from different sets S k [Y, Y ] to complete the color classes constructed from a single set D k .

1 Figure 11 : 5 .•

 1115 Figure 11: An explicit decomposition of the arcs of K ⋆ 5 .

4 Figure 12 :

 412 Figure 12: The chosen decomposition of the arcs of K ⋆ 6 .

Acknowledgment

We thank Jean-Claude Bermond for introducing the problem to us and for motivating our research.

We are in the case n ≡ 1 (mod 3), but the general decomposition is valid for n ≥ 3. However, here, there is just one value of f to study: f = 0 and the direct routing immediately gives

For n = 2, there is no idempotent Latin square of order 2, so we provide precisely the routing.

• For f = 0, D 0 forms a color class, and we choose the set of pairwise arc-disjoint paths of length 2 given by S 0 = {x 1 y 1 x 2 , x 2 y 2 x 1 , y 1 x 1 y 2 , y 2 x 2 y 1 } to form the second color class. So,

• For f = 1, we define S 1 = {x 1 y 2 x 2 , x 2 y 1 x 1 , y 1 x 2 y 2 , y 2 x 1 y 1 }, which contains pairwise arcdisjoint paths, and D 1 = {x i y j+1 x i+1 y j , y i x j+1 y i+1 x j : 1 ≤ i ≤ 2, 1 ≤ j ≤ 2} (which corresponds to usual definition of D 1 ). The color classes are defined by: c 1 = S 0 , c 2 = S 1 and c (i,j) = D 0 {x i y j , y j x i } ∪ D 1 {x i y j+1 x i+1 y j , y j x i+1 y j+1 x i } for 1 ≤ i ≤ 2 and 1 ≤ j ≤ 2.

Finally, we obtain w

The case n = 4 is the first exception to Tillson's Theorem of decomposition, so we define in Figure 9 the partition of the arcs of K ⋆ 4 . Then, for the different values of f , the routings are defined as previously, in Section 4.1.

• For f = 0, f = 1, and f = 2, since C 1 and C 2 are disjoint Hamiltonian circuits of K ⋆ 4 , the routings are defined exactly as in the general case n ≡ 1 (mod 3). So, in these cases, we

• For f = 3, we need to pack the paths of R 3 . We differently organize the arcs of K ⋆ 4 in order to obtain a suitable decomposition of the paths. The scheme of the routing is given Figure 10. The arcs are labeled with the name of the circuit C i they belong to. k = 1, . . . , 5, we define:

The remaining paths form the two color classes S 2 [X, X] and S 3 [X, X] So, we obtain

• Finally, for f = 4, we have to change color classes. Indeed, this time, paths from D i are packed with sets of type

) which saturate exactly the in and out-neighborhood of the vertices x l and x m . Precisely, we define, for k = 1, . . . , 5: The remaining paths are exactly the direct paths, D 0 . So, we obtain w 4 (K ⋆ 5,5 ) = π 4 (K ⋆ 5,5 ) = 21.


Olivier Lopez

Amale Kanj

Paul-Eric Pottie

Daniele Rovera

Joseph Achkar

Christian Chardonnet

Anne Amy-Klein

Giorgio Santarelli
email: giorgio.santarelli@institutoptique.fr

Simultaneous remote transfer of accurate timing and optical frequency over a public fiber network

In this work we demonstrate for the first time that it is possible to transfer simultaneously an ultra-stable optical frequency and precise and accurate timing over 540 km using a public telecommunication optical fiber network with Internet data. The optical phase is used to carry both the frequency information and the timestamps by modulating a very narrow optical carrier at 1.55 µm with spread spectrum signals using two-way satellite time transfer modems. The results in term of absolute time accuracy (250 ps) and long-term timing stability (20 ps) well outperform the conventional Global Navigation Satellite System or geostationary transfer methods.

Introduction

In the last five years ultra-stable optical fiber links have been successfully developed enabling precise and accurate frequency transfer with fractional frequency stability in the range of 10 -18 after only 3 hours of measurement and frequency accuracy of a few 10 -19 . Recently ground-breaking frequency transfer has been demonstrated on a record distance of 920 km on dedicated fiber [1]. We extended this technique to public fiber networks with simultaneous data traffic, providing a scalable technique for extension to the continental level [2,3]. This approach is much more stable and accurate than satellite-based frequency comparisons using the Global Navigation Satellite System (GNSS), or other satellite-based techniques. This opens the way to accurate remote clock comparisons, for modern atomic clocks having already demonstrated accuracy in the range 10 -16 -10 -17 [4][5][6][7][8]. This is a key-point in advanced time-frequency metrology and for advanced tests of fundamental physics [9]. Accurate frequency plays also a key role for geodesy, high resolution radio-astronomy, modern particle physics, and for the underpinning of the accuracy of almost every type of precision measurement. For all these applications, accurate timing is also important and gives the capability to precisely synchronize distant experiments. A salient case is the neutrinos speed measurement from CERN to Gran Sasso. Fiber-optical two-way time transfer methods have been demonstrated on dedicated links with an accuracy of the order of one hundred of ps or better [10,11]. Long distance accurate time dissemination is usually based on GNSS signals, or geostationary telecommunication satellites, with timing accuracy of the order of 1 ns in the best case [12,13]. In this work we present a novel method to simultaneously disseminate an ultra-stable optical frequency and accurate timing over a public telecommunication network on a 540 km optical link simultaneously carrying Internet data traffic, using a dedicated "dark" channel.

Experimental set -up description.

This method exploits an ultra-stable laser at 1.55 µm to carry both the frequency information as shown in Ref [3] and the timing signal through optical phase modulation. Figure 1 shows the scheme of the experiment. The 540 km-long optical link (LPL-Reims-LPL) depicted in Fig. 1 (i) is identical to the one reported in [3] Figure 1 (ii) shows the hybrid time comparison and ultra-stable optical frequency distribution system. The detailed description of the ultra-stable optical frequency dissemination is given in [3].

Here we briefly recall the operation of the optical ultra-stable frequency transfer: the frequency signal consists of the frequency of an ultra-stable cavity-stabilised laser (in block A, Fig. 1(ii)), which feeds the optical fiber. The fiber propagation noise is detected and compensated by comparison of the input optical phase with the signal phase after a roundtrip, thanks to an optical interferometer. Corrections are applied using an Acousto-Optical Modulator (AOM) operating around 40 MHz. For the sake of simplicity we gather all error signal processing functions into a symbolic box called Optical Phase Stabilization Unit (OPSU). At the far end of the link the optical signal is regenerated by a narrow linewidth laser We implement an approach similar to the one used in coherent optical telecommunication to encode the time signal on the optical carrier. At each link end the laser is phase-modulated by a fiber pigtailed electro-optical modulator (EOM) with frequency shifted replicas of the time signal at 400 MHz and 700 MHz respectively. These frequency shifts are chosen to

3.

Results and discussion.

The frequency transfer stability and the timing stability/jitter were simultaneously measured and are plotted in Fig. 2. The frequency stability of the link reaches a resolution of 2x10 -18 at 30 000 s averaging time, which is almost identical to the one reported in [3]. The accuracy of the frequency transfer is about 2x10 -18 .

The time stability shows a noise of less than 20 ps over the whole measurement time period. Delay calibration is a prerequisite of accurate dissemination of timing signals. Since the fiber optical length is unknown and fluctuates over time, a rigorous calibration test is needed to guarantee the independence of the system from the fiber length. This calibration procedure is a standard method in time&frequency metrology [START_REF] Bauch | Rapport BIPM2011/01[END_REF]. We change the propagation length by "shortcuts" in the accessible places along the long-haul optical link. We vary the link length from 10 m to 94 km, 400 km and the total length of 540 km. The overall link attenuation is maintained nearly constant within ±2 dB by inserting a variable optical attenuator into the common fiber path. This minimizes the impact of the received power dependent delay variations in the modems. We measure that the differential time delay variation versus distance is at most 50 ps. In addition we checked the system sensitivity by changing the power of the signals from the optical detection up to the modem input. As long as the modems operate in optimal conditions (i.e. low input power level), the system shows a coefficient below 15ps/dB. We also performed several tests of disconnection/connection, power shutdown and restart without measuring appreciable time delay variation. Tests on fiber spools of 25 km, 50 km, 75 km and 100 km are consistent with the above reported results. This method is strongly immune In addition, we varied the input polarization state using Lefevre's three-loop rotating wave plate and did not observe any significant variation within a measurement resolution of 50 ps. It is worth noting that both time measurements are collocated in this experiment so that the set-up is not sensitive to the Sagnac effect. The preliminary conservative accuracy budget of 250 ps is mainly dominated by phase jumps of about 50-80 ps. The Figure 3 shows typical data over a period of more than 2 weeks (missing data are due to technical issues). The origin of such jumps seems related to the propagation in the long-haul Internet fiber link. Additional tests performed by replacing the long-haul link with fiber spools did not reveal any phase jumps over several days of measurements. The cause of such behavior is not yet well understood. Its analysis is difficult as these scarce phase jumps happen randomly. Nevertheless the system is quite robust, in addition to the results presented in We believe that in the case of slightly lower fiber losses and better distribution of the optical amplification such a link can be extended over more than a thousand kilometres. This method of accurate time transfer can be extended to segmented optical links by the use of intermediate optical regeneration stations [2,3] which include RF signal processing techniques and station delay calibration procedures. This method can be improved for example by developing new modems with wider pseudorandom codes. The scheme proposed here can be drastically simplified if one focuses only on time transfer as no ultra-stable laser is then needed. It is important to point out that the use of heterodyne detection allows operation with very large optical losses, for which classical Intensity Modulation (IM) techniques are ineffective. This method has been proven to be applicable to non-dedicated fiber and installed long-haul fiber links carrying Internet data. This opens the way to frequency and time dissemination on a continental scale since NRENs together with transnational fiber networks such as GEANT in Europe could be used for that purpose.

Figure 1

 1 Figure 1 (i) layout of the long distance optical fiber link, OADM (Optical Add-Drop Module), DWDM (Dense Wavelength Division Multiplexing), DCF (Data Center facility) (ii) Sketch of the experimental set-up; FM : Faraday mirror, PD : photodiode, AOM : acoustooptic modulator, EOM : electro-optic modulator, OPSU : Optical Phase Stabilization Unit, PLL : Phase-Locked Loop.

( 3

 3 kHz) (in block B, Fig. 1(ii)), phase-locked on the incoming light, and frequency-offset by 79 MHz. The optical frequency transfer stability is obtained by measuring the optical beat-note between the ultra-stable laser from A and the phase locked laser in part B. Concerning time transfer, signals are provided by a pair of two-way satellite time transfer modems [15]. These signals are generated by relating the phase of a pseudorandom noise modulation (20 Mchip/s) on a radio frequency carrier signal (50-80 MHz) to the one-pulse-per-second (1 pps) and 5 MHz reference signals from a common clock. Orthogonal specific pseudo-random codes are allocated to each modem device. This equipment correlates the received signal with a local replica of the signal expected from the transmitting site and measures the time of arrival of the received signal with respect to the local clock. A computer collects the time of arrival of both modems and computes the differential time delays.

  avoid interference between optical signals and allow efficient filtering of the time comparison signals. The low modulation depth (~1%) and the spread spectrum nature of the modulating time signals lead to a very pure optical spectrum, allowing the optical frequency carrier transfer to operate without degradation. The time signals are recovered by an optical heterodyne beat-note of the local laser with the incoming signal at each link end. After successive frequency mixing and filtering the spread spectrum time signals are processed by the modems. This step is not trivial considering the frequency width of the pseudo-random codes (~20 MHz) and the large dynamic range of the signals in the detection system, where parasitic signals due to stray reflections are 40 dB larger than the useful signal.

Figure 2

 2 Figure 2 fractional optical frequency stability (black circles, left scale) and timing stability in picoseconds (red squares, right scale) for the 540-km fiber link.

  against fiber chromatic dispersion due to the very low frequency/wavelength difference between the two counter-propagating time signals (about 0.3 GHz/2.4 pm). The overall effect for the 540 km link is below 25 ps. The timing fluctuations due to Polarisation Mode Dispersion (PMD) penalty is also well below 20 ps, derived from previous telecommunication fiber network characterization.

Figure 3 :

 3 Figure 3: One-way time delay (blue plot, right axis) and differential delay (black plot, left axis) (each data point is the average of 120 one second delay measurements) versus time for the 540-km fiber link (constant calibration time offset removed on both plots).

Figure 3 ,

 3 Figure 3, we have several runs of about one week for which the peak-to-peak time fluctuations are below 200 ps while oneway fluctuations are in excess of 10 ns. The results in terms of timing stability and accuracy clearly outperform the satellite techniques [12].

Acknowledgments

This work would not have been possible without the support of the GIP RENATER. We acknowledge the funding support from the Agence Nationale de la Recherche (ANR BLANC 2011-BS04-009-01).