Mohamed Lamine Lamali
email: mohamed_lamine.lamali@alcatel-lucent.com

Hélia Pouyllau
email: helia.pouyllau@alcatel-lucent.com

Dominique Barth
email: dominique.barth@prism.uvsq.fr

Path Computation in Multi-Layer Multi-Domain Networks: A Language Theoretic Approach

Keywords: Multi-layer networks, Pseudo-Wire, Push-Down Automata

Multi-layer networks are networks in which several protocols may coexist at different layers. The Pseudo-Wire architecture provides encapsulation and decapsulation functions of protocols over Packet-Switched Networks. In a multidomain context, computing a path to support end-to-end services requires the consideration of encapsulation and decapsulation capabilities. It appears that graph models are not expressive enough to tackle this problem. In this paper, we propose a new model of heterogeneous networks using Automata Theory. A network is modeled as a Push-Down Automaton (PDA) which is able to capture the encapsulation and decapsulation capabilities, the PDA stack corresponding to the stack of encapsulated protocols. We provide polynomial algorithms that compute the shortest path either in hops or in the number of encapsulations and decapsulations along the inter-domain path, the latter reducing manual configurations and possible loops in the path.

Introduction

Most carrier-grade networks comprise multiple layers of technologies (e.g. Ethernet, IP, etc.). These layers are administrated by different control and/or management plane instances. The Pseudo-Wire (PWE3) architecture [START_REF] Bryant | RFC3985 -Pseudo Wire Emulation Edge-to-Edge[END_REF] unifies control plane functions in heterogeneous networks to allow multi-layer services (e.g. Layer 2 VPN). To this end, it defines encapsulation (a protocol is encapsulated into another) and decapsulation (a protocol is unwrapped from another) functions, called adaptation functions further in this paper. These functions allow the emulation of services (e.g. Frame Relay, SDH, Ethernet, etc.) over Packet-Switched Networks (PSN, e.g. IP or MPLS).

Prior to a service deployment in a multi-layer network, the resources must be identified during the path computation process. The path computation must take into account the adaptation function capabilities in order to explore all resources and to ensure the end-to-end service deployment. The authors of [START_REF] Bocci | RFC5659 -An Architecture for Multi-Segment Pseudowire Emulation Edge-to-Edge[END_REF] defined the multi-segment Pseudo-Wire architecture for multi-domain networks. In [START_REF] Cho | Stitching dynamically and statically provisioned segments to construct end-toend multi-segment pseudowires[END_REF], the authors mention the problem of path determination over such an architecture, stressing the importance of having path computation solutions.

In such an architecture, the path computation should comply with protocol compatibility constraint: if a protocol is encapsulated in a node, it must be decapsulated in another node; the different encapsulation processes should be transparent to the source and target nodes. Thus, some nodes may be physically connected but, due to protocol incompatibility, no feasible path (i.e., which comply with protocol compatibility) can be found between them. This constraint leads to non trivial characteristics of a shortest path [START_REF] Dijkstra | A path finding implementation for multi-layer networks[END_REF]: i) it may involve loops (involving the same link several times but with different protocols); ii) its subpaths may not be feasible. Computing such a path is challenging and cannot be performed by classical shortest path algorithms.

Currently, the configuration of these functions is manually achieved within each network domain: when an encapsulation function is used, the corresponding decapsulation function is applied within the domain boundaries. In largescale carrier-grade networks or in multi-domain networks, restricting the location of the adaptation functions to the domain boundaries might lead to ignore feasible end-to-end paths leading to a signaling failure. Hence, in the path computation process, it must be possible to nest several encapsulations (e.g. Ethernet over MPLS over SDH). A decapsulation should not be restricted to the same domain as its corresponding encapsulation. This allows the exploration of more possible paths and new resources in the path computation.

The problem we address is to compute the shortest feasible path either in the number of nodes or in the number of involved (and possibly nested) adaptation functions. The latter is motivated by two goals: i) as such functions are manually configured on router interfaces, minimizing their number would simplify the signaling phase when provisioning the path; ii) as our algorithms do not allow loops without adaptation functions (loops without encapsulations or decapsulations are useless and can be deleted), reducing the number of adaptation functions leads to reducing the number of loops. Reducing the number of loops is important because if there are several loops involving the same link, the available bandwidth on this link may be exceeded.

The authors of [START_REF] Kuipers | Path selection in multi-layer networks[END_REF][START_REF] Dijkstra | A multi-layer network model based on ITU-T G.805[END_REF] focused on the problem of computing a path in a multilayer network under bandwidth constraints. In [START_REF] Lamali | End-to-End Quality of Service in Pseudo-Wire Networks[END_REF], we demonstrated that the problem under multiple Quality of Service constraints is NP-Complete. In this paper we demonstrate that the problem without QoS constraints is polynomial, and we provide algorithms to compute the shortest path. These algorithms use a new model of multi-layer networks based on Push-Down Automata (PDAs). The encapsulation and decapsulation functions are designed as pushes and pops in a PDA respectively, the PDA stack allowing to memorize the nested protocols. If the goal is to minimize the number of adaptation functions, the PDA is transformed in order to bypass sub-paths without adaptation functions. The PDA or transformed PDA is then converted into a Context-Free Grammar (CFG) using a method of [START_REF] Hopcroft | From PDA's to Grammars[END_REF]. A shortest word, either corresponding to the shortest path in nodes or in adaptation functions, is generated from this CFG.

This paper extends the work published in [START_REF] Lamali | Path computation in Multi-Layer multi-domain networks[END_REF], providing the detailed proofs of the correctness of the algorithms and including new algorithms (transforming the PDA, converting the PDA to a CFG, generating the shortest word). Furthermore, the complexity analyses are refined and the total worst case complexity of the path computation is significantly reduced.

This paper is organized as follows: Section 2 recalls the context of multilayer multi-domain networks and the related work on path computation in such networks and presents the proposed approach; Section 3 provides a model of multi-layer multi-domain networks and a formal definition of the problem; Section 4 explains how a network is converted into a PDA and provides the complexity of this transformation; finally, Section 5 gives the different methods that compute the shortest path in nodes or in encapsulations/decapsulation.

In order to ease the paper reading, a table summarizing the used notations is provided in Appendix A.

Path computation in Pseudo-Wire networks

Some standards define the emulation of lower layer protocols over a PSN (e.g. Ethernet over MPLS, [START_REF] Martini | RFC4448 -Encapsulation Methods for Transport of Ethernet over MPLS Networks[END_REF], Time-Division Multiplexing (TDM) over IP, [START_REF] Stein | RFC5087 -Time Division Multiplexing over IP (TDMoIP)[END_REF]). For instance, one node in the network encapsulates the layer 2 frames in layer 3 packets and another node unwraps them. This allow to cross a part of the network by emulating a lower layer protocol, and thus to overcome protocol incompatibilities.

The PWE3 architecture [START_REF] Bryant | RFC3985 -Pseudo Wire Emulation Edge-to-Edge[END_REF], as well as the multi-layer networking description of [START_REF] Shiomoto | RFC5212 -Requirements for GMPLS-based multi-region and multilayer networks[END_REF], assumes an exhaustive knowledge of the network states. This assumption is not valid at the multi-domain scale. Thus, the authors of [START_REF] Bocci | RFC5659 -An Architecture for Multi-Segment Pseudowire Emulation Edge-to-Edge[END_REF] defines an architecture for extending the Pseudo-Wire emulation across multiple PSNs segments. The authors of [START_REF] Cho | Stitching dynamically and statically provisioned segments to construct end-toend multi-segment pseudowires[END_REF] stress the importance of path determination in such a context and suggest it to be an off-line management task. They also suggest to use the Path Computation Element architecture (PCE) [START_REF] Farrel | RFC4655 -A Path Computation Element (PCE)-Based Architecture[END_REF], which is adapted to the multi-domain context. It could be a control plane container for solution detailed in this paper. It would require protocol and data structure extensions in order to add encapsulation/decapsulation capabilities in the PCE data model.

Related work on path computation in multi-layer networks

The problem of path computation in heterogeneous networks raised first at the optical layer. Due to technology incompatibilities (different wavelengths, different encodings, etc.), it soon became clear that classical graph models cannot capture these incompatibilities thus forbidding classical routing algorithms to tackle this problem. The authors of [START_REF] Chlamtac | Lightpath (Wavelength) Routing in Large WDM Networks[END_REF] propose a Wavelength Graph Model instead of the classical network graph models to resolve the problem of wavelength continuity. The authors of [START_REF] Zhu | A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks[END_REF] propose an Auxiliary Graph Model to resolve the problems of traffic grooming and wavelength continuity in heterogeneous WDM mesh networks, this model is later simplified in [START_REF] Yao | A Link Bundled Auxiliary Graph Model for Constrained Dynamic Traffic Grooming in WDM Mesh Networks[END_REF]. The common feature of these works is that they model each physical device as several nodes, each node being indexed by a technology. The existence of an edge depends on the existence of a physical link, but also on the technology compatibility. In [START_REF] Gong | Optimal and Efficient End-to-End Path Computation in Multi-Layer Networks[END_REF], the authors take into account the compatibility constraints on several layers: wavelength continuity, label continuity, etc. They propose a Channel Graph Model to resolve the multi-layer path computation problem. The proposed models and algorithms take into account protocol and technology but ignore the encapsulation/decapsulation (adaptation) capabilities. As they do not have a stack to store the encapsulated protocols, they cannot model the PWE3 architecture.

In the PWE3 architecture, the compatibility between two technologies on a layer depends also on the encapsulated protocols on the lower layer. In [START_REF] Dijkstra | A multi-layer network model based on ITU-T G.805[END_REF], the authors addressed the problem of computing the shortest path in the context of the ITU-T G.805 recommendations on adaptation functions. They stress the lack of solutions on path selection and the limitations of graph theory to handle this problem. The authors of [START_REF] Dijkstra | A path finding implementation for multi-layer networks[END_REF] present the specificities of a multi-layer path computation taking into account the encapsulation/decapsulation (adaptation) capabilities: the shortest path can contain loops and its sub-paths may not satisfy the compatibility constraints. They provide an example of topology where classical routing algorithms cannot find the shortest path because it contains a loop. In [START_REF] Kuipers | Path selection in multi-layer networks[END_REF], the authors addressed the same problem in a multi-layer network qualifying it as an NP-Complete problem. The NP-Completeness comes from the problem definition as they consider that the loops in the path can exceed the available bandwidth, because if the path involves the same link several times it may overload this link. They aim to select the shortest path in nodes and provide new graph models allowing to express the adaptation capabilities. They propose a Breadth-First Search algorithm which stores all possible paths and selects the shortest one. This algorithm has an exponential time complexity.

In the problem we consider, we exclude bandwidth constraints and propose a solution for minimizing the number of encapsulations and decapsulations. Our algorithm does not allow loops without adaptation functions, the only loops that may exist involve encapsulations or decapsulations. Thus, minimizing the number of adaptation functions in the path also leads to minimizing the number of loops -and avoiding them if a loop-free feasible path with less encapsulations exists.

Proposed approach

In this work, we propose a new multi-domain multi-layer network model wich takes into account encapsulation and decapsulation capabilities. To the best of our knowledge no previous work has considered this problem at the multi-domain scale. It induces to go beyond the domain boundaries allowing multi-domain compatibility to determine a feasible inter-domain path: when an encapsulation for a given protocol is realized in one domain its corresponding decapsulation must be done in another. It appears that PDAs are naturally adapted to model the encapsulation and decapsulation capabilities, as push and pop operations easily model encapsulations and decapsulations, and the PDA stack can model the stack of encapsulated protocols. By using powerful tools of Automata and Language Theory, we propose polynomial algorithms that generate the shortest sequence of protocols of a feasible path. This sequence allows to find the shortest feasible path.

Furthermore, we consider two kind of objectives: either the well-known objective of minimizing the number of hops or the objective of minimizing the number of adaptation functions. The latter is motivated by the fact that it is equivalent to minimize the number of configuration operations, which are often done manually and can be quite complex. It is also motivated by reducing the number of possible loops (as the number of adaptation functions involved in a path is correlated with the number of loops), and thus avoiding to use the same link several times and to exhaust the available bandwidth on it.

Figure 1 summarizes our proposed approach. It presents the different models leading to the shortest path and the algorithms computing them. Compared to the preliminary version of this work [START_REF] Lamali | Path computation in Multi-Layer multi-domain networks[END_REF], we detail the proofs of correctness and refine the complexity of our algorithms. We also provide the detailed algorithm which converts the PDA to a CFG, and we propose a new method to generate the shortest word which is linear in the length of the shortest word.

Appendix A summarizes the notations used in this paper.

Multi-layer multi-domain network model

A multi-domain network having routers with encapsulation/decapsulation capabilities can be defined as a 3-tuple: a directed graph G = (V, E) modeling the routers of a multi-domain network, we consider a pair of vertices (S, D) in G corresponding to the source and the destination of the path we focus on; a finite alphabet A = {a, b, c, . . . } in which each letter is a protocol; an encapsulation or a decapsulation function is a pair of different letters in the alphabet A:

• Figure 2

-if x i = a ∈ A and x i+1 = b ∈ A or x i+1 = b ∈ A then β i = (a, b) -if x i = b ∈ A and x i+1 = a ∈ A\{b} or x i+1 = a ∈ A\{b} then β i = (a, b)
Note that the pair (a, a), a ∈ A can appear in a transition sequence, as it represents a passive function. However, according the definition above, a pair (a, a), a ∈ A cannot appear, as it is forbidden to encapsulate (and thus to decapsulate) a protocol a in itself.

• Let denotes the empty word, "•" indicates the concatenation operation, and H C denotes the transition sequence obtained from a path C as explained above. The following definitions give a formal characterization of the feasible paths.

Definition 1. A sequence M C from H C is valid if and only if M C ∈ L,
where L is the formal language recursively defined by:

L = ∪   (x,y)∈A 2 (x, y) • L • (x, y)   • L Definition 2. A path C is a feasible path in N from S to D if: • S, U 1 , . . . , U n-1 , D is a path in G = (V, E),
• The well-parenthesized sequence M C from C is valid,

• For each i ∈ {1, . . . , n}:

-if x i = a and x i+1 = b or b then (a, b) ∈ P (U i ) -if x i = a and x i+1 = b or b then (a, b) ∈ P (U i ) -if x i = a and x i+1 = a or a then a ∈ T (U i )
The language L of valid sequences is known as the generalized Dyck language [START_REF] Liebehenschel | Lexicographical Generation of a Generalized Dyck Language[END_REF]. It is well-known that this language is context free but not regular. Thus, push-down automata are naturally adapted to model this problem.

Example. The multi-domain network illustrated by Fig. 3 Problem definition. As explained above, our goal is to find a feasible multidomain path. Furthermore, we set as an objective function either the size of the sequence of adaptation functions or the size of the path in number of nodes. Hence, the problem we aim to solve can be defined as follows:

min C |H C | or |M C | s.t. C is a feasible path

From the network model to a PDA

In this section, we address the conversion from a network to a PDA. Algorithm 1 takes as input a network N = (G = (V, E), A, P ) and converts it to a PDA A N = (Q, Σ, Γ, δ, S A , Z 0 , {D A }), where Q is the set of states of the PDA, Σ the input alphabet, Γ the stack alphabet, δ the transition relation, S A the start state, Z 0 the initial stack symbol and D A the accepting state, is the empty string. The automaton A N from N is obtained as follows:

• Create a state U x of the automaton for each U ∈ V and each x ∈ In(U ), except for the source node S for which a single state S A is created,

• The top of the stack is the last encapsulated protocol,

• If the current state is U x then the current protocol is x,

• The adaptation functions will be converted into transitions in the PDA. A transition t ∈ δ is denoted (U x , x, α, β , V y ) where U x ∈ Q is the state of the PDA before the transition, x ∈ Σ is the input character, α ∈ Γ is the top of the stack before the transition (it is popped by the transition), β ∈ Γ * is the sequence of symbols pushed to the stack, and V y is the state of the PDA after the transition. Thus if β = α then t is a passive transition, if β = xα then t is a push of x, and if β = ∅ then t is a pop,

• A passive transition of a protocol x across a node U is modeled as a transition without push or pop between the state U x and the following state

V x . It is denoted (U x , x, α, α , V x ),
• An encapsulation of a protocol x in a protocol y by a node U is modeled as a push of the character x in the stack between the state U x and the following state

V y . It is denoted (U x , x, α, xα , V y ) 2 ,
• A decapsulation of y from x by a node U is modeled as a pop of the protocol y from the stack. It is denoted (U x , x, y, ∅ , V y ).

Algorithm 1 Convert a network to a PDA Input: a network N = (G = (V, E), A, P ), a source S and a destination D Output: push-down automaton Proof. Let a feasible path C = Sx 1 U 1 x 2 . . . x i U i x i+1 . . . U n-1 x n D in a network N and its trace T C = x 1 . . . x i x i+1 . . . x n leading to a valid sequence M C . We aim to demonstrate that: i) T C is recognized by A N and ii) U 1 , . . . , U n-1 is a path in N and iii) There exists a feasible path corresponding to T C in N if T C is recognized by the PDA A N . It is sufficient to show that C = S, x 1 , U 1 , x 2 , . . . , U n-1 , x n , D is a feasible path in N if and only if T C is recognized by A N (i.e the final state is reached and the stack is empty).

A N = (Q, Σ, Γ, δ, S A , Z 0 , {D A }) (1) Σ ← A ∪ A ; Γ ← A ∪ {Z 0 } (
From C we deduce the following path in A N defined as a sequence of transitions. This path begins with transitions: (S A , , Z 0 , Z 0 , (U i ) x 1 ) for each U i s.t. x 1 ∈ In(U i ). Hence, transition (S A , , Z 0 , Z 0 , (U 1 ) x 1 ) belongs to this set. Then, the path in A N follows the order induced by T C , for each element in x 1 , . . . , x n , we consider one or two transitions in A N as follows:

• if x i = a then -if x i+1 = a or x i+1 = a consider the transition ((U i ) a , a, α, α , (U i+1 ) a )
where α ∈ Γ\{a}, if x i+1 = b or x i+1 = b consider the transition ((U i ) a , a, α, aα , (U i+1 ) b ), where α ∈ Γ\{a}

• else (i.e., if

x i = a) then consider the transition ((U i ) a , a, b, ∅ , (U i+1 ) b ). Note that, if i = n then U i+1 = D.
It is clear that this sequence of transitions is a path in A N recognizing the trace T C . Since M C is a well parenthesized word, if x i = a then the head of the stack when reaching state (U i ) x i contains aZ 0 and when reaching state (U i+1 ) x i+1 , the head of the stack is reduced to Z 0 . Then, when reaching state D A , the stack is empty.

Conversely, we can show with a similar construction that any well recognized word on a path in A N induces one unique trace T C of feasible paths in G from S to D. 2

Example.

The shortest feasible path

In section 4, we provided a method to build a PDA allowing to determine the feasible paths. The next step is to minimize either the number of nodes or the number of adaptation functions. The method to minimize the number of nodes uses directly the PDA as described in section 5.1. But to minimize the number of adaptation functions, the PDA is transformed in order to bypass the sub-paths without any adaptation function, as detailed in section 5.2. Then, a CFG derived from the PDA (or the transformed PDA) generates words whose length is equivalent to the number of nodes (or to the number of adaptations). An algorithm browses the CFG to determine the shortest word. Finally, another algorithm identifies the multi-domain path corresponding to this shortest word.

Minimizing the number of nodes

The number of characters in a word accepted by the automaton A N is the number of links in the corresponding feasible path (each character is a protocol used on a link). Thus the step of automaton transformation (section 5.2) should be skipped. The automaton A N is directly transformed into a CFG, then the shortest word is generated as described in section 5.3.2. The corresponding feasible path is computed by algorithm 6 described in section 5.3.3.

Minimizing the number of adaptation functions

To enumerate only encapsulations and decapsulations in the length of each word (and thus minimize adaptation functions by finding the shortest word accepted), a transformed automaton A N in which all sequences involving passive transitions are bypassed must be determined. The length of the shortest word accepted by A N is the number of adaptation functions plus a fixed constant.

Let us define Q a (a ∈ A) as Q a = {V x ∈ Q|x = a}, and let A a N be the subautomaton induced by Q a . By analogy with an induced subgraph, an induced sub-automaton is a multigraph with labeled edges such that the set of vertices is Q a and the set of edges is the set of transitions between elements of Q a . Since there are only passive transitions between two states in Q a , all paths in the subautomaton are passive. Let define P (U x , V x ) as the shortest path length between U x and V x . This length can be computed between all pairs of nodes in Q a using the Floyd-Warshall algorithm. Let Succ(V x ) be the set of successors of V x in the original automaton A N , i.e., Succ(V x ) = {W y ∈ Q|∃(V x , x, α, β , W y ) ∈ δ}. Let L(A N ) be the set of words accepted by A N , and let L(A N ) be the set of words accepted by A N . Let f : Σ → Σ * be a function s.t.:

• if x i = a i ∈ A then f (x i ) = aa . . . aa i occurrences • if x i = a i ∈ A then f (x i ) = aa . . . aa i occurrences
The domain of f is extended to (Σ ) * :

f : (Σ ) * → Σ * w = x 1 i x 2 j . . . x n k → f (w ) = f (x 1 i )f (x 2 j ) . . . f (x n k )
For simplicity, we consider that x and x 1 are the same character. f (L(A N )) denotes the set of words accepted by A N transformed by

f (i.e. f (L(A N )) = {f (w ) s.t. w ∈ L(A N )}).
It is clear that f is not a bijection (f (x i x j ) = f (x i+j )). So to operate the transformation between L(A N ) and L(A N ), we define g : Σ * → (Σ ) * s. In other words, w = g(w) is the shortest word in (Σ ) * s.t. f (w ) = w.

The following lemmas and proposition show that the set of words accepted by the transformed automaton is 'equivalent' to the set of words accepted by the original automaton. Equivalent in the meaning that, using f , each word accepted by the transformed automaton can be associated to a word accepted by the original one. In addition, the transformed automaton has a new propriety: there is a linear relation between the length of an accepted word and the minimum number of pushes (and pops) involved to accept it. This propriety allows to find the word requiring the minimum number of pushes accepted by the original automaton. This is done by finding the shortest word accepted by the transformed automaton. Lemma 1. f (L(A N )), the set of words accepted by A N and transformed by f , is equal to L(A N ), the set of words accepted by A N .

Proof. We prove this by double inclusion:

1. L(A N ) ⊆ f (L(A N )) : ∀w ∈ L(A N ), f (w) = w (remind that we consider that x = x 1 ). So f (L(A N )) = L(A N ) (1)
. On the other hand, the construction of A N by algorithm 2 does not delete any character, transition, state or set of final states from

A N . So L(A N ) ⊆ L(A N ). And thus f (L(A N )) ⊆ f (L(A N )) (2)
By ( 1) and ( 2),

L(A N ) ⊆ f (L(A N )). 2. L(A N ) ⊇ f (L(A N )) : Let w = x 1 i x 2 j .
. . x n l be a word in L(A N ) and let t 1 t 2 . . . t n+1 be a sequence of transitions accepting w . For each transition

t m = (U x m-1 , x m-1 k , α, β , W x m ) (1 < m < n) in this sequence, s.t. t m ∈ δ \δ,
there is a sequence of k -1 passive transitions in A N (because the creation of t m in A N requires the existence of such a sequence in A N ). This sequence begins from the state U x m-1 and is followed by a transition (V x m-1 , x m-1 , α, β , W x m ). Thus, this sequence in A N matches with f (x m-1 k ) And for each t m in A N , either t m ∈ δ so t m matches with x m+1 k (if k = 1), or t m ∈ δ \δ and there is a sequence of transitions in

A N which matches with f (x m+1 k ) (if k > 1). And since, by definition, f (w ) = f (x 1 i )f (x 2 j ) . . . f (x n l ), f (w ) ∈ L(A N ). Thus f (L(A N )) ⊆ L(A N ). 2
Let w be the shortest word accepted by A N , let N b

A N push (w ) be the minimum number of pushes in a sequence of transitions accepting w in A N , and let N b A N pop (w ) be the minimum number of pops in a sequence of transitions accepting w in A N .

Lemma 2. The length of the shortest path (sequence of transitions) accepting

w in A N is 1 + N b A N push (w ) + N b A N pop (w ) and N b A N pop (w ) = N b A N push (w ) + 1.
Proof. First we prove that w cannot be in the form of . . . x m i x m+1 j . . . with x m = x m+1 . Let U x m be the state in which A N is before reading the character x m i . Let V x m+1 be the state in which A N is after reading x m i and before reading x m+1 j . And let W y be the state in which A N is after reading x m+1 j . If x m = x m+1 , then, by construction, there is a transition (U x m , x m i+j , α, β , W y ) (where α, β is a pop of y or a push of x m if x m = y). So, if x m i x m+1 j is replaced by x m i+j in w , the word obtained is shorter then w and is also accepted by A N . Thus, the shortest word accepted by

A N is w = x 1 i x 2 j . . . x n k where x m = x m+1 for (1 ≤ m < n).
By construction of A N , for each character x m i in w , there is a push transition

(U x m , x m i , α, x m α , W y ) if x m i ∈ A or a transition (U x m , x m i , y, ∅ , W y ) if x m i ∈ A . So
all transitions in the shortest sequence that accepts w are pops or pushes, except the first transition from the initial state (S A , , Z 0 , Z 0 , U x 1 ) and the final pop (V x n , x n k , Z 0 , ∅ , D A ). The number of other pops is equal to word -even if the stack is not empty). Algorithm 3 takes as input an automaton which accepts words by empty stack. A N and A N accept words by empty stack and by final state, because the only transitions that empty the stack are those that reach the final state (the transitions in the form (D x , x, Z 0 , ∅ , D A ), x ∈ In(D)). Thus, Algorithm 3 performs correctly with A N or A N as input.

The shortest word generated by a CFG.

To find the shortest word generated by G N , a function associates each nonterminal to the length of the shortest word that it generates.

More formally, :

{N ∪ Σ ∪ { }} * or {N ∪ Σ ∪ { }} * → N ∪ {∞} s.t.:
• if w = then (w) = 0,

• if w ∈ Σ or Σ then (w) = 1, Proof. We prove that at each iteration (except the last one), there is a least one nonterminal [X] s.t. ([X]) is updated with the length of the shortest word that [X] produces.Thus, the update of all ([X]) with their correct values is done at worst in |N | iterations. We proceed by induction on the number of iterations:

• if w = α 1 . . . α n (with α i ∈ {N ∪ Σ ∪ { }} or {N ∪ Σ ∪ { }}) then (w) = n i=1 (α i ). Algorithm 4 computes the value of ([X]) for each [X] ∈ N .
Basis: There is no -production in G N , and there is at least one production in the form [X] → x where [X] ∈ N and x ∈ Σ (resp. Σ ) (see algorithm 3 for the construction of G N ). -Either each γ i contains a nonterminal which generates no word. Thus, [Y ] generates no word and the value of ([Y ]) = ∞ is correct.

-Or all nonterminals in each γ i generate a word. However, in the derivation of the shortest word generated by any nonterminal, no nonterminal is used twice or more (otherwise a shorter word can be generated by using this nonterminal once). Thus, among all nonterminals with a wrong -value, there is one which does not use others to generate its shortest word. So its -value is already correct or it will be updated to the correct value at the following iteration. 2

Complexity. As there is at worst |N | iteration of the while loop, the complexity

of algorithm 4 is in O(|N | × |P|) which is O(|A| 8 × |V | 4 × |E|) (resp. O(|A| 8 × |V | 7
)) in the network model There are several algorithms which allow the generation of a uniform random word of some length from a CFG [START_REF] Hickey | Uniform random generation of strings in a contextfree language[END_REF][START_REF] Ph | A calculus for the random generation of labelled combinatorial structures[END_REF][START_REF] Mairson | Generating Words in a Context-Free Language Uniformly at Random[END_REF], or, more recently, a non-uniform random generation of a word according to some targeted distribution [START_REF] Denise | Controlled non-uniform random generation of decomposable structures[END_REF][START_REF] Gardy | Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models[END_REF]. For instance, the boustrophedonic and the sequential algorithms described in [START_REF] Ph | A calculus for the random generation of labelled combinatorial structures[END_REF] generate a random labeled combinatorial object of some length from any decomposable structure (including CFGs). The boustrophedonic algorithm is in O(n log n) (where n is the length of the object) and the sequential algorithm is in O(n 2 ) but may have a better average complexity. Both algorithms use a precomputed table of linear size. This table can be computed in O(n 2 ). These algorithms require an unambiguous CFG, and the CFG computed by algorithm 3 can be inherently ambiguous depending on the input network (as several feasible paths can use the same sequence of protocols and thus have the same trace T C ). However, the unambiguity requirement is only for the randomness of the generation. Recall that our goal is to generate the trace of the shortest feasible path. Thus, we do not take into consideration the randomness and the distribution over the set of shortest traces. In order to generate the shortest word in L(G N ), the boustrophedonic algorithm can take G N and ([S G ]) as input (recall that ([S G ]) is the length of the shortest word generated by G N ). Thus, the generation of the shortest word w (resp. w ) would have been in O(|w| 2 ) (resp. O(|w | 2 )), where |w| denotes the length (number of characters) of w. This complexity includes the precomputation of the table. However, this complexity hides factors depending of the size of the CFG, the construction of the precomputed table requires at least one pass over all the production rules. Example. From the shortest trace abba, algorithm 6 computes the only feasible path in the network on Fig. 3(a), which is S, a, U, b, V, b, W, a, D.

; i ← 1 (2) While D is not reached do (2.1) for each U ∈ N odes[i] and each V ∈ V s.t. (U, V ) ∈ E do (2.1.1) If x i ∈ A, x i ∈ Out(U ), x i ∈ In(V ) and (x i-1 , x i ) ∈ P (U ) (2.1.1.1) Add (U, V ) to Links[i] and V to N odes[i + 1] (2.1.2) If x i ∈ A, x i ∈ Out(U ), x i ∈ In(V ) and (x i , x i-1 ) ∈ P (U ) ( 2

Conclusion

The problem of path computation in a multi-layer network has been studied in the field of intra-domain path computation but is less addressed in the interdomain field with consideration of the Pseudo-Wire architecture. There was no polynomial solution to this problem and the models used were not expressive enough to capture the encapsulation/decapsulation capabilities described in the Pseudo-Wire architecture.

In this paper, we provide algorithms that compute the shortest path in a multi-layer multi-domain network, minimizing the number of hops or the number of encapsulations and decapsulations. The presented algorithms involve Automata and Language Theory methods. A Push-Down Automaton models the multi-layer multi-domain network. It is then transformed in order to bypass passive transitions and converted into a Context-Free Grammar. The grammar generates the shortest protocol sequence, which allows to compute the path matching this sequence.

The different algorithms of our methodology have polynomial upper-bound complexity as summarized by Table 1. Compared to the preliminary version of this work, the proofs of correctness of the algorithms are detailed and the complexity analysis is significantly refined (the highest algorithm complexity is in O(|A| 8 × |V| 7 ) instead of O(|A| 11 × |V| 7 × |E| 2 )).

In order to figure out the whole problem of end-to-end service delivery, we plan to extend our solution to support end-to-end Quality of Service constraints and model all technology constraints on the different layers (conversion or "mapping" of protocols). As a future work, we also plan to investigate which part of our algorithms can be distributed (e.g., Can the domains publish their encapsulation/decapsulation capabilities without disclosing their internal topology?) and how such a solution can be established on today's architectures.

I

  . Convert a multi-domain Pseudo-Wire network into a PDA, i. If the goal is to minimize the number of adaptation functions, transform the PDA to bypass the "passive" functions (i.e. no protocol adaptation), ii. Else let the PDA as is, II. Derive a CFG from the PDA or the transformed PDA, III. Determine the "shortest" word generated by the CFG, IV. Identify the shortest path from the shortest word.

Figure 1 :

 1 Figure 1: Proposed approach to compute the shortest feasible path.

  (a) illustrates the encapsulation of the protocol x by the node U in the protocol y; • Figure 2(b) illustrates that the protocol x is unwrapped by the node U from the protocol y; • Figure 2(c) illustrates that the protocol x transparently crosses the node U (no encapsulation or decapsulation function is applied). Such pairs are referred as passive further in this paper. We denote by ED and by ED the set of all possible encapsulation functions and decapsulation functions respectively, (i.e., ED ⊂ A 2 ). A subset P (U ) of ED∪ED indicates the set of encapsulation, passive and decapsulation functions supported by vertex U ∈ V. We define In(U ) = {a ∈ A s.t. ∃b ∈ A s.t. (a, b) or (b, a) ∈ P (U )} and Out(U ) = {b ∈ A s.t. ∃a ∈ A s.t. (a, b) or (b, a) ∈ P (U )}. The set T (U ) = {a ∈ A s.t. (a, a) ∈ P (U )} is the set of protocols that can passively cross the node U .

Figure 2 :

 2 Figure 2: Different transitions when a protocol crosses a node U

  The well-parenthesized sequence of C, denoted M C = β 1 , . . . , β m , is obtained from H C by deleting each passive transition β i s.t. β i = (a, a) and a ∈ A Example. Consider the path C = S, a, U, b, V, b, W, a, D in the network illustrated by Fig. 3(a). The transition sequence corresponding to C is H C = (a, b), (b, b), (a, b) and its trace is T C = abba. The well-parenthesized sequence from C is M C = (a, b), (a, b).

  (a) has 6 routers and two protocols labeled a and b. Adaptation function capabilities are indicated below each node. For example, the node U can encapsulate the protocol a in the protocol b (function denoted by (a, b)) or can passively transmit the protocol a (function denoted by (a, a)). In this multi-domain network, the only feasible path between S and D is S, a, U, b, V, b, W, a, D and involves the encapsulation of the protocol a in the protocol b by the node U , the passive transmission of the protocol b by the node V and the decapsulation of the protocol a from b by the node W . (functions (a, b), (b, b) and (a, b) respectively).

2 )( 6 )Proposition 1 .

 261 Create a single state S A for the node S (3) For each node U = S and each protocol x ∈ In(U ), create a state U x (4) For each state U x s.t. (S, U ) ∈ E and x ∈ Out(S) Create a transition (S A , , Z 0 , Z 0 , U x ) (5) For each link (U, V ) ∈ E s.t. U = S and for each (x, y) ∈ P (U ) and each α∈Γ\{x} (5.1) If x ∈ T (U ) ∩ In(V ) Create a transition (U x , x, α, α , V x ){passive trans.} (5.2) If x = y and y ∈ In(V ) Create a transition (U x , x, α, xα , V y ){encap.} For each link (U, V ) ∈ E s.t. U = S and for each (y, x) ∈ P (U ) (6.1) If x ∈ In(V ) Create a transition (U x , x, y, ∅ , V y ){decap.} (7) Create a fictitious final state D A . (8) For each x ∈ In(D) and each α ∈ Γ\{x} Create a transition (D x , x, Z 0 , ∅ , D A ) Complexity. Each node U from the graph generates |In(U )| states, except the source node S. A fictitious final state is added. Thus, the number of states is at worst 2 + (|V| -1) × |A| so in O(|V| × |A|). The worst case complexity of algorithm 1 is in O(max((|V| × |A|), (|E| × ((|A| × |ED|) + |ED|))))). We assume that the network is connected, so |E| ≥ |V| -1. Since ED is a subset of A 2 , then |ED| < |A| 2 and |ED| < |A| 2 . Thus, the upper bound complexity is in O(|A| 3 × |E|), which is also an upper bound for the number of transitions. Considering a network N = (G = (V, E), A, P ), a source S ∈ V and a destination D ∈ V, the language recognized by A N is the set of traces of the feasible paths from S to D in N .

Figure 3 (

 3 b) is an example of output of algorithm 1. The algorithm transforms the network illustrated by Fig. 3(a) into a PDA of Fig 3(b). For instance, the link (U, V ) is transformed into the transitions (U a , a, Z 0 , aZ 0 , V b ) and (U a , a, b, ab , V b ) (pushes) because the node U should encapsulate the protocol a in the protocol b using the adaptation function (a, b) before transmitting to the node V . The link (W, D) is transformed into the transitions (W b , b, Z 0 , bZ 0 , D a ) and (W a , b, a, ba , D a ) (pushes) according to the adaptation function (a, b). It is also transformed into the transition (W b , b, a, ∅ , D a ) (pop) because the node W can decapsulate the protocol a from b using the adaptation function (a, b) before transmitting to the node D. The link (V, W ) is transformed into the transitions (V b , b, Z 0 , Z 0 , W b ) and (V b , b, a, a , W b ) (passive transitions) according the capability of the node V (adaptation function (b, b)).

O

  x∈A |δ| + |Q| + |Q x | 3 + (|Q x | 2 × |Q| × |A|) . And ∀x ∈ A, |Q x | ≤ |A| (see algorithm 1 for the construction of the set of states Q). Thus, the complexity of algorithm 2 is in O max |A| × (|δ| + |Q|), |A| × |V| 3 , |A| 2 × |V| 2 × |Q| , which corresponds to O max(|A| 4 × |E|, |A| 3 × |V| 3 ) in the network model. The number of transitions in δ is bounded by |δ|+O x∈A (|Q x | 2 × |Q| × |A|) , which corresponds to O(|A| 3 × |V| 3 ) in the network model. Example. Algorithm 2 transforms the PDA in Fig. 3(b) into the PDA in Fig. 3(c). For the protocol b, the algorithm computes the sub-automaton induced by the states V b , W b and K b . The distance P (V b , W b ) = 1 is then computed. Thus, to bypass the sequence of transitions (V b , b, a, a , W b ) (W b , b, a, ∅ , D a ), the transition (V b , b 2 , a, ∅ , D a ) is added.

  t. : for each w = xx . . . x i occurrences yy . . . y j occurrences . . . zz . . . z k occurrences ∈ Σ * , g(w) = x i y j . . . z k .

Algorithm 4 Proposition 3 .

 43 Compute the values ([X]) for each nonterminal[X] ∈ N Input: G N = (N , Σ, [S G ], P) or (N , Σ , [S G ], P) Output: ([X]) for each nonterminal [X] (1) Initialize each ([X]) to ∞ (2)While there is at least one ([X]) updated at the previous iteration do (2.1) For each production rule [X] → α 1 . . . α n in P (2.1.1) ([X]) ← min{ ([X]), n i=1 (α i )} Algorithm 4 terminates at worst after |N | iterations, and each ([X]) ([X] ∈ N ) obtained is the length (number of characters) of the shortest word produced by [X].

Algorithm 6

 6 Find the shortest path Input: Network N and T C Output: Shortest path C (1) N odes[1] ← S

  Figure 3: Example

  Either there is a nonterminal [Y ] s.t. ([Y ]) has not already the correct value (i.e., it can already be updated), but for all productions [Y ] → γ 1 | . . . |γ m (each [Y ] → γ i is a production) all nonterminals in γ 1 , . . . , γ m have their correct -values. And thus, ([Y ]) will be updated with the correct value at the end of the following iteration. • Or, for each nonterminal [Y ] with a wrong -value, there is at least a nonterminal in each of its productions [Y ] → γ 1 | . . . |γ m which has not its correct -value yet.

	•
	For each [X] ∈ N s.t. {[X] → x} ∈ P, ([X]) = 1. And
	algorithm 4 assigns these values to each ([X]) at the first iteration.
	Induction: Suppose that at iteration n, there are at least n (n ≤ n < |N |)
	nonterminals [X] s.t. the algorithm has assigned the correct value to ([X]). So
	there are |N | -n nonterminals which have not the correct -value yet.

Table 1 :

 1 .1.2.1) Add (U, V ) to Links[i] and V to N odes[i + 1] (2.2) i + + (3) Backtrack from D to S by adding each covered link in the backtracking to C. Algorithms and their complexities Complexity. The while loop stops exactly after T C steps, because it is sure that there is a feasible path of length |T C | if T C is accepted by the automaton A N . At each step, all links and nodes are checked in the worst case. Thus, algorithm 6 is in O(|T C | × |V| × |E|) in the worst case.

	Algorithm	Upper-Bound Complexity Minimizing hops Minimizing enc./dec.
	Algo. 1: Network to PDA		O(|A| 3 × |E|)
	Algo. 2: Transform PDA	/	O(max(|A| 4 × |E|, |A| 3 × |V| 3 )
	Algo. 3: PDA to CFG	O(|A| 5 × |V| 2 × |E|)	O(|A| 5 × |V| 5 )
	Algo. 4: Shortest word length	O(|A| 8 × |V| 4 × |E|)	O(|A| 8 × |V| 7 )
	Algo. 5: Shortest word	O(|A| 3 × |V| 2 × |w|)	O(|A| 3 × |V| 2 × |w |)
	Algo. 6: Shortest path	O(|T C | × |V| × |E|)

Table A .

 A 2: List of symbols used in the paper.

Note that, even if x = a ∈ A, the transition has the form (Ua, a, α, aα , Vy). Characters in A are only used as input characters. Characters indexing states and pushed characters in the stack are their equivalent in A.

Acknowledgment

The first author would like to thank Kaveh Ghasemloo for his help about Algorithm 4. This work is partially supported by the ETICS-project, funded by the European Commission. Grant agreement no.: FP7-248567 Contract Number: INFSO-ICT-248567.

Algorithm 2 takes as input A N and computes the transformed automaton A N = (Q , Σ , Γ , δ , S A , Z 0 , {D A }). A N is initialized with the values of A N . Then, the algorithm computes the sub-automaton for each character x ∈ A (step [START_REF] Bocci | RFC5659 -An Architecture for Multi-Segment Pseudowire Emulation Edge-to-Edge[END_REF]) and the length values P (U x , V x ) for each pair of states in the subautomaton (step [START_REF] Bryant | RFC3985 -Pseudo Wire Emulation Edge-to-Edge[END_REF]). Each path between a pair of states is a sequence of passive transitions. If such a path exists (step (3.1)), the algorithm adds transitions to δ from U x to each state in Succ(V x ) (steps (3.1.2) and (3.1.3)). These added transitions are the same that those which connect V x to its successors W y , but with an input character indexed by the number of passive transitions between U x and V x , (i.e., P (U x , V x )) plus one (indicating that there is a transition sequence which matches with a sequence of protocols xx . . . x of length P (U x , V x ) + 1). The indexed character is added to the input alphabet Σ (step (3.1.1)).

Algorithm 2 Transform automaton A N

Input: push-down automaton ). If x=y, there are at worst |A| -1 transitions between V x and W y in Q (transitions in the form (U x , x, α, α , W x ) for all possible values of α except x -as the construction of the automaton forbids the encapsulation of a protocol x in x, and thus it is impossible to have x as current protocol and at the top of the stack in the same time). If x = y, there are at worst |A| transitions between V x and W y in Q (the pop (V x , x, y, ∅ , W y ) and the pushes (V x , x, α, xα , W y ) for all possible values of α except x). And as |Succ(V x )| < |Q|, the steps (3.1.2) and (3.1.3) are bounded by O(|Q| × |A|). However, a state belongs to only one sub-automaton, the complexity of algorithm 2 is therefore bounded by the number of pushes (in order to have Z 0 at the top of the stack before the final transition).

2

Now let w be a word accepted by A N , let N b A N push (w) be the minimum number of pushes in a sequence of transitions accepting w in A N , and let N b A N pop (w) be the minimum number of pops in a sequence of transitions accepting w in A N . Lemma 3. For each w ∈ L(A N ):

Proof. Let t 1 t 2 . . . t n be the sequence of transitions accepting w in A N with minimum number of pushes and pops. For each sequence t i t i+1 . . . t j of passive transitions, followed by a push or a pop transition, there is a transition with the same push or pop and the same input character indexed by

Let t 1 t 2 . . . t n be the sequence of transitions with minimum pushes and pops accepting g(w) in A N . It is clear that f (g(w)) = w. So if there is a sequence t 1 t 2 . . . t n that accepts g(w) with less pops and pushes than t 1 t 2 . . . t n , then each t i ∈ δ \δ can be replaced by a sequence of passive transitions followed by a pop or a push in A N . And theses sequences accept f (g(w)) (which is w) with less pops and pushes than in the sequence t 1 t 2 . . . t n , which contradicts the fact that it minimizes the number of pops and pushes to accept w. 2

Proposition 2. The word accepted by A N which minimizes the number of pushes is f (w ), where w is the shortest word (i.e., with minimum number of characters) accepted by A N .

Proof. By lemma 2, the shortest word accepted by A N minimizes the number of pushes in A N (since the number of pushes grows linearly as a function of the length of the word). Let w be this word. Suppose that there is a word w accepted by

Ad absurdum, f (w ) is the word which minimizes the number of pushes in A N . 2

The shortest path as a shortest word

In order to find the shortest word accepted by A N (resp. A N ), the CFG G N such that L(G N ) = L(A N ) (resp. L(A N )) is computed. The shortest word in L(G N ) is then generated.

From the PDA to the CFG.

The transformation of a PDA into a CFG is well-known. We adapted a general method described in [START_REF] Hopcroft | From PDA's to Grammars[END_REF] to transform A N (resp. A N ) into a CFG. The output of algorithm 3 is a CFG

where N is the set of nonterminals (variables), Σ (resp. Σ ) is the input alphabet, [S G ] is the initial symbol (initial nonterminal) and P is the set of production rules. Except [S G ], nonterminals are in the form [U XV ] where U, V ∈ Q and X ∈ Γ (resp. Q and Γ ). The demonstration of the correctness of this transformation is also in [START_REF] Hopcroft | From PDA's to Grammars[END_REF].

Complexity. Example. This method transforms the PDA in Fig. 3(c) into a CFG.

Remark. There are two mechanisms of acceptance defined for PDAs: an input word can be accepted either by empty stack (i.e., if the stack is empty after reading the word) or by final state (i.e., if a final state is reached after reading the Actually, as the -values are already computed, the generation can simply be done in linear time in the length of the shortest word. The standard algorithm 5 takes as input the CFG and the -values. Each nonterminal is replaced by the left part with minimal -value among its productions. Example. Algorithm 4 gives ([S G ]) = 3. Algorithm 5 computes the shortest word using the production rules in Fig. 3(d). The derivation is:

[

ab 2 a Thus, the shortest word accepted by the transformed PDA is ab 2 a. And the shortest trace of a feasible path is f (ab 2 a) = abba.

5.3.3.

From the shortest word to the path. If the goal is to minimize the number of nodes in the path, algorithm 6 takes as input the shortest word w accepted by A N . Otherwise, as w is the shortest word accepted by A N and generated by G N , according to proposition 2, f (w ) is the word which minimizes the number of pops and pushes in A N . In such a case it is the trace T C of the shortest feasible path C in the network N . It is possible that several paths match with the trace T C = w (resp. f (w )). In such a case, a load-balancing policy can choose a path.

Algorithm 6 is a dynamic programming algorithm that computes C. It starts at the node S and takes at each step all the links in E which match with the current character in T C . Let T C = x 1 x 2 . . . x n (x i ∈ A ∪ A). At each step i, the algorithm starts from each node U in N odes[i] and adds to Links[i] all links (U, V ) which match with x i . It also adds each V in N odes[i+1]. When reaching D, it backtracks to S and selects the links from D to S.

Appendix A. List of notations

In order to facilitate the paper reading, Table A.2 summarizes the symbols used in the paper.