Wojtek Bigos
email: wojtek.bigos@rd.francetelecom.com

Stéphane Gosselin
email: stephane.gosselin@rd.francetelecom.com

Morgane Le Foll
email: morgane.lefoll@rd.francetelecom.com

Hisao Nakajima
email: hisao.nakajima@rd.francetelecom.com

Bernard Cousin
email: bernard.cousin@irisa.fr

Optimized Design of Survivable MPLS over Optical Transport Networks

Keywords: integer linear program, MPLS over OTN, multilayer optimization, survivability design, spare capacity allocation, protection routing

In this paper we study different options for the survivability implementation in MPLS over Optical Transport Networks (OTN) in terms of network resource usage and configuration cost. We investigate two approaches to the survivability deployment: single layer and multilayer survivability and present various methods for spare capacity allocation (SCA) to reroute disrupted traffic.

The comparative analysis shows the influence of the traffic granularity on the survivability cost: for high bandwidth LSPs, close to the optical channel capacity, the multilayer survivability outperforms the single layer one, whereas for low bandwidth LSPs the single layer survivability is more cost-efficient. For the multilayer survivability we demonstrate that by mapping efficiently the spare capacity of the MPLS layer onto the resources of the optical layer one can achieve up to 22% savings in the total configuration cost and up to 37% in the optical layer cost. Further savings (up to 9 %) in the wavelength use can be obtained with the integrated approach to network configuration over the sequential one, however, at the increase in the optimization problem complexity. These results are based on a cost model with actual technology pricing and were obtained for networks targeted to a nationwide coverage.

I. INTRODUCTION

We consider the MPLS over Optical Transport Network (OTN) as a multilayer network architecture, where label switching routers (LSR) making up the MPLS layer are directly attached to optical cross-connects (OXC) belonging to the optical layer. In the optical layer, optical cross-connects are interconnected with point-to-point WDM links in a mesh topology. The interconnection between routers in this architecture is provided by circuit-switched, end-to-end optical channels or lightpaths. A lightpath (LP) represents a sequence of fiber links forming a path from a source to a destination router together with a single wavelength on each of these links. The OXCs can switch wavelengths between fiber links without undergoing optoelectronic conversion. A lightpath must be assigned the same wavelength on each link on its route, unless the OXCs support the wavelength conversion capability. The set of lightpaths established in the network makes up a logical network topology. IP traffic in the form of label switched paths (LSP) is carried in the network over this logical topology using a single or multiple logical hops. Fig. 1 shows an example of the MPLS over OTN. As network survivability plays critical role in the network design, a number of recovery schemes have been proposed in the scope of the MPLS over OTN architecture. They are based on two general concepts: single layer survivability [START_REF] Demeester | Resilience in Multilayer Networks[END_REF][START_REF] Assi | On the merit of MPLS protection/restoration in IP over WDM networks[END_REF], where recovery mechanisms are implemented only in the MPLS layer and multilayer survivability [START_REF] Demeester | Resilience in Multilayer Networks[END_REF][START_REF] Lei | A joint resilience scheme with interlayer backup resource sharing in IP over WDM networks[END_REF][START_REF] Maesschalck | Intelligent optical networking for multilayer survivability[END_REF], where recovery is employed both in the MPLS and the optical layer. The multilayer survivability has the advantage over the single layer approach in faster and simpler recovery from physical link failures but it is considered to consume more optical layer resources [START_REF] Demeester | Resilience in Multilayer Networks[END_REF][START_REF] Maesschalck | Intelligent optical networking for multilayer survivability[END_REF]. This is because with multilayer recovery each network layer reserves some spare resources for rerouting of affected paths, so multiple spare capacity pools are provided, each dedicated to a particular layer. On the other hand, single layer recovery requires more resources from the MPLS layer what may negatively affect the total network configuration cost, as these resources are more expensive than the resources of the optical layer.

In this paper we present the design of a survivable MPLS over Optical Transport Network (OTN) as an integer linear programming (ILP) optimization problem. Our objective is to minimize the amount of network resources used with a given network configuration. There are implemented different methods for spare capacity allocation (SCA) with the single-and multilayer survivability to reroute disrupted traffic. The planning process for SCA is based on two approaches to the MPLS over OTN configuration: the sequential one, where the MPLS layer and the optical layer are planned separately and the integrated one, where the whole network is designed in one step. The aspects of spare capacity planning and sequential/integrated approaches to network configuration are related to the design of multilayer network architectures and contribute to efficient network configuration in terms of resources usage. The objective of this work is to consider both these aspects in the context of a network optimization problem and to investigate their impact on network resource savings. A set of MPLS over OTN configurations is implemented, where a particular SCA method is combined with a particular configuration approach demonstrating their relative importance to the overall network design in terms of network resource consumption and configuration cost.

The rest of this paper is organized as follows: Section II presents different SCA methods for the single-and multilayer survivability implementation. Section III describes two approaches to the MPLS over OTN configuration: sequential and integrated and explains their impact on the network resource usage. We precise the objectives to be realized with respect to these problems and explain how our work extends the previous studies. In Section IV we define a framework for the survivable MPLS over OTN design. We present algorithms for different spare capacity planning options, define a cost model to be included into the optimization procedure and give exact ILP formulations for the considered problems. Section V concludes with the analysis of the obtained results.

II. SPARE CAPACITY PLANNING IN MPLS OVER OTN

One of the aspects related to the survivability design is how to allocate spare capacity in a network, so that the total amount of network resources is minimized. The total amount of network resources used with a given SCA option depends on supported failure scenarios and a recovery technique used. In this study we employ end to end path protection as a recovery technique in individual network layers; it is believed that such a recovery scheme will be always required in a network to protect the integrity of high class services. The considered failure scenarios include physical link failures (e.g. fiber cuts, optical line system failures), transit 1 node failures (both router and OXC) and IP/optical interface failures.

With the single layer survivability (Fig. 2a) protection is implemented at the LSP level and the MPLS layer covers all failure types. Each working LSP (wLSP) has a corresponding protection LSP (pLSP), link-and node-disjoint in both network layers. With the multilayer survivability (Fig. 2b) protection is implemented both at the LSP level (pLSP) and the lightpath level (pLP). The optical layer protects against physical link and OXC failures, whereas the MPLS layer Fig. 2. Two options for the survivability implementation in MPLS over OTN: a) single layer survivability, b) multilayer survivability. 1 Paths originating/terminating at a failed node are considered as lost, since they cannot be restored with path protection mechanisms. protects against router and IP/optical interface failures which cannot be detected by the optical layer 2 . This implies that, with the multilayer survivability, only multi-hop LSPs which are susceptible to router failures have corresponding protection LSPs routed in the MPLS layer (to provide node disjointness against router failures). Single-hop LSPs do not require any extra spare capacity from the MPLS layer as they are subject only to the failures resolved at the lightpath level (e.g. wLSP2 carried on wLP4 is protected by pLP4). To cover the IP/optical interface failures (e.g. optical line cards, intra-office links and tributary OXC ports), the reach of protection lightpaths is extended towards optical line cards in routers.

Another point to consider with the multilayer survivability implementation is how the MPLS spare capacity used to protect working LSPs is supported by the optical layer. With a simple capacity planning without any precautions taken, called double or redundant protection [START_REF] Assi | On the merit of MPLS protection/restoration in IP over WDM networks[END_REF], spare capacity in the MPLS layer is protected again in the optical layer. The working LSPs are thus twice protected: once in the MPLS layer and once in the optical layer. This results in inefficient use of network resources with very little increase in service reliability. An improvement in the optical spare capacity utilization can be achieved by supporting working and protection LSPs on different lightpaths and treating them differently in the optical layer: lightpaths carrying working LSPs are protected while lightpaths supporting protection LSPs are left unprotected (e.g. wLP3 in Fig. 1b carrying protection LSP pLSP1). This option, called LSP 'spare' unprotected [START_REF] Assi | On the merit of MPLS protection/restoration in IP over WDM networks[END_REF] requires less resources than double protection; it is however still inefficient in a way that the optical layer still dedicates some resources to support the MPLS spare capacity. Further improvement in spare capacity planning consists in sharing spare resources between the MPLS and the optical layer. With this option, called interlayer backup resources sharing (interlayer BRS) [START_REF] Lei | A joint resilience scheme with interlayer backup resource sharing in IP over WDM networks[END_REF] or common pool survivability [START_REF] Demeester | Resilience in Multilayer Networks[END_REF], [START_REF] Maesschalck | Intelligent optical networking for multilayer survivability[END_REF] the MPLS spare capacity is considered as extra traffic in the optical layer (i.e., carried on unprotected, pre-emptible lightpaths, such as wLP3 in Fig. 1b). As a consequence, there exists only one spare capacity pool (in the optical layer, for lightpath protection) which can be reused by MPLS recovery schemes when needed (e.g. in Fig. 2b protection lightpaths pLP1 and pLP2 share the wavelengths with the lightpath wLP3 carrying protection LSP pLSP1). Little or no additional resources in the optical layer are required to support the MPLS spare capacity.

The analysis of the survivability implementation in the MPLS over OTN in terms of resources usage and configuration cost has been already provided in the literature. The analysis provided in [START_REF] Phillips | Network Studies in IP/Optical Layer Restoration[END_REF] shows that the single layer recovery is by 10% more cost-effective than the multilayer recovery when lightpaths are not fully utilized with the working traffic, whereas for the high lightpath utilization it is the opposite. The authors however consider only physical link failures as a possible failure scenario (assuming dual-router architecture to protect against router failures) and the results taking into account more failure scenarios may be different. Various SCA options for the multilayer survivability has been investigated in [START_REF] Lei | A joint resilience scheme with interlayer backup resource sharing in IP over WDM networks[END_REF] showing 15% and 20% cost improvements achieved respectively with the "LSP spare unprotected" and the "interlayer BRS" methods over the "double protection". The planning process used in [START_REF] Maesschalck | Intelligent optical networking for multilayer survivability[END_REF] does not guarantee the recovery from the OXC failures when using the interlayer BRS option. This work extends the previous studies by adding more failure scenarios, including physical link failures, node failures (both router and OXC) and IP/optical interface failures. The exact planning processes are given for different SCA options and a cost model is defined which allows the network configuration cost to be modified according to the price evolution of network components. Finally, we present the integrated approach to the network design where the MPLS and optical layer are optimized jointly, leading to extra savings in network resources.

III. SEQUENTIAL VS. INTEGRATED APPROACH TO THE MPLS OVER OTN CONFIGURATION

In the MPLS over OTN both network layers can be combined using either the overlay or the peer interconnection model [START_REF] Rajagopalan | IP over optical networks: architectural aspects[END_REF]. In the overlay model, the MPLS and the optical layer are controlled separately and each layer has its own instance of the control plane. There are two separate routing processes in the network: the MPLS layer routes LSPs in the logical topology using either existing lightpaths or requesting a new lightpath directly connecting LSP endpoints from the optical layer; then the optical layer routes the lightpaths in the physical topology. In the peer model, a single control plane controls both the MPLS and the optical layer. There is one routing process which runs across both layers and logical and physical links are considered jointly in route selection.

Most previous studies on the routing implementation either with the overlay [START_REF] Assi | On the merit of MPLS protection/restoration in IP over WDM networks[END_REF] or the peer interconnection model [START_REF] Zheng | An efficient dynamic protection scheme in integrated IP/WDM networks[END_REF]- [START_REF] Commellas | Integrated IP/WDM Routing in GMPLS-based optical networks[END_REF] concentrate exclusively on analyzing the blocking probability of a given routing approach under dynamic traffic conditions. There are however no analyses showing their performance in terms of network resources consumption. Our objective is to implement the concepts of sequential and integrated routing as network optimization problems and to compare the use of network resources achieved with both methods. The considered network resources include:

-In the MPLS layer:

• amount of packet processing in routers which is proportional to the volume of transit traffic at each router (i.e. neither originating nor terminating in a router); by minimizing it we improve the router throughput and minimize the Legend: traffic matrix -set of K LSPs; each LSP has associated (s)ource, (d)estination point and (b)andwidth; G PH (N,E) -graph representing the physical network topology of N vertices (nodes) and E edges (physical links); G L (N,I) -graph representing the logical topology of N nodes and I logical links; w i,j -capacity per node pair in the MPLS layer, measured in the number of lightpaths installed between the node pair i-j; Δ i -transit traffic processed by the node i; w e -capacity per link in the optical layer, measured in the number of wavelengths used on the physical link e to carry lightpaths; c LPthe lightpath cost; c λ -the wavelength cost; c TT -the transit traffic cost. Fig. 3. Sequential vs. integrated approach to the MPLS over OTN configuration packet queuing delay.

• number of IP/optical interfaces in routers which constitute a significant part of the configuration cost; -In the optical layer:

• number of wavelengths and wavelength-switching equipment used to route a given set of lightpaths in the physical topology.

With the sequential approach to network configuration, as presented in Fig 3a, the optimization problem consists of two sub-problems. First sub-problem takes as an input a traffic matrix in terms of the LSPs to be routed in the network and returns as a result the set of lightpaths to be established in the optical layer (i.e. the logical topology) and the routing of the LSPs over the logical topology. Thus, only a part of the MPLS over OTN configuration is solved by the first subproblem and the optimization function takes as an objective minimizing only the IP/MPLS layer resources, i.e. the total number of lightpaths between all node pairs ∑ ) , ( ) , ( j i j i w and the total transit traffic ∑ Δ i i processed by routers. Second sub-problem takes the set of lightpaths to be established on physical links and the physical network topology as input parameters and returns the routing of lightpaths in the physical topology optimizing only resources of the optical layer, i.e. the total number of wavelengths ∑ e e w used to route the lightpaths in the physical topology. The lightpath cost c LP , the wavelength link cost c λ and the transit traffic cost c TT are included into the optimization procedure to account for the total configuration cost of the network. Note, however, that such decomposition is approximate or inexact. Solving the sub-problems in sequence and combining the solutions may not result in the optimal solution for the fully integrated problem. On the other hand, with the integrated approach, as depicted in Fig. 3b, there is only one optimization problem implemented which provides a full MPLS over OTN design in one step. The optimization function used to control the configuration process explicitly accounts for the resource usage both in the MPLS and the optical layer. The global optimization of network resources is thus possible with the integrated approach. Nevertheless, achieving an absolutely optimal solution of such a problem may be hard as the computational complexity of the algorithm solving the network configuration problem in a combined fashion is high.

IV. PROBLEM FORMULATION

We consider the following network design problem. Given the offered traffic matrix (in terms of static LSP connections), the physical network topology and a set of constraints on logical and physical link capacities, we search for an MPLS over OTN configuration which (i) provides 100% restorability against the considered failure scenarios and (ii) minimizes the total resource usage in both network layers. A cost model is included into the optimization procedure which represents the monetary cost of various network components. Thereby, by minimizing the amount of network resources the cost of a given network configuration is also optimized. We use integer linear programming (ILP) as an optimization technique and formulate the problem using linear models. The problem solution provides a complete specification to the logical topology design and routing of working and protection paths both in the MPLS and the optical layer together with the resource usage at the minimal cost.

We make the following assumptions in our study: 1) The traffic matrix is symmetric and the lightpaths are bidirectional. Two lightpaths from a pair are routed over the same physical route but in the opposite directions.

2) The optical layer has an opaque configuration with photonic OXCs (i.e. which switch wavelengths optically) surrounded by WDM transponders performing OEO conversion. Transponders perform signal regeneration and adaptation functions including wavelength conversion. 3) As the optical layer supports wavelength conversion, the wavelength continuity constraint is not considered (under which a lightpath is assigned the same wavelength on all links on its route). This assumption reduces the problem in terms of ILP variables and constraints and makes it more computationally tractable.

A. Survivability Implementation

Algorithms for the MPLS over OTN design using the sequential configuration approach combined with various options for the survivability implementation are presented in Fig. 4 a-d. Each algorithm consists of four planning processes (steps): two for the network design with working paths, respectively in the MPLS and the optical layer (steps I and III), and two others for the network configuration with protection paths (steps II and IV). Each part is implemented as a separate optimization problem using a distinct ILP formulation.

The planning process for the computation of working LSPs and lightpaths (i.e. steps I and III in each algorithm) is analogous to the one presented in Fig. 3a. Next, the routing of protection paths is determined for the set of precomputed working paths and spare capacity is allocated. With the single layer survivability (see Fig. 4a), the spare capacity planning is done only in the MPLS layer (in step II). The planning process takes as the inputs the considered failure scenarios and the working LSP routing computed in step I. Then, the routing of protection LSPs is performed analogously to the working LSPs routing, but respecting the constraints for protection routing in the MPLS layer (see below). The optimization function aims at minimizing the total transit traffic ∑ Δ i i and the spare capacity

∑ ) , ( ) , ( j i j i s
consisting of the lightpaths carrying protection LSPs. With the multilayer survivability implementation (see Fig. 4b-d), the spare capacity planning is done both in the MPLS and the optical layer with the objective to minimize the resources of each layer. Contrary to the single layer survivability, only multi-hop LSPs are subject to the protection LSP routing in step II; single hop LSPs are protected at the lightpath level. With the "double protection" method (Fig. 4b), both the lightpaths carrying working and protection LSPs are protected in the optical layer. With the "LSP spare unprotected" option (Fig. 4c), working and protection LSPs are routed over two disjoint sets of lightpaths (sets G L1 and G L2 ) and only the lightpaths carrying working LSPs (from G L1 ) have protection lightpaths; the lightpaths carrying protection LSPs (from G L2 ) are not protected. With the "interlayer BRS" (Fig. 4d), not only the lightpaths carrying protection LSPs are unprotected but they also share the wavelengths with the protection lightpaths to optimize further the wavelength use (i.e. spare capacity s e is shared with the working capacity w e2 supporting the lightpaths which carry protection LSPs). Next, the planning process was repeated but using the integrated configuration approach where the routing of working LSPs and the corresponding lightpaths (i.e. steps I, III) was implemented as a single optimization problem according to the scheme presented in Fig 3b . The same methodology was then used for protection LSPs and the lightpaths carrying protection LSPs (steps II and III). Note, however, that to combine the routing of working and protection LSPs and lightpaths (i.e. steps I -II and III -IV) we use the sequential approach only, i.e. routing of protection paths is determined for the set of pre-computed working paths. The results from computing working and protection paths jointly are reported in [START_REF] Groove | Mesh-Based Survivable Networks. Option and Strategies for Optical, MPLS, SONET and ATM Networking[END_REF] showing 8 % -12 % savings in spare capacity than if the paths are computed separately, however, at the increase in the optimization problem complexity.

The following rules are defined for the protection routing, i.e., how to route protection paths, so that all the considered failure scenarios are supported: I. For the single layer survivability: Legend: s i,j -spare capacity per node pair in the MPLS layer, measured in the number of lightpaths carrying protection LSPs (pLSP) between the node pair i-j; s e -spare capacity in the optical layer, measured in the number of wavelengths used on the physical link e to carry protection lightpaths (pLP); The other symbols have the meaning as specified in Fig. 2 Fig. 4. Algorithms for the MPLS over OTN design using the sequential approach with various options for the survivability implementation. 2. With the "double protection" method each lightpath has a protection lightpath, with the "LSP spare unprotected" and "interlayer BRS" method only the lightpaths carrying working LSPs have corresponding protection lightpaths.

Respective working and protection lightpaths are link-and node-disjoint in the physical topology.

Additional requirement for the "LSP spare unprotected" and "interlayer BRS" methods:

3. Corresponding working and protection LSPs are node disjoint in the physical topology; this prevents a working LSP and its protection LSP from failing simultaneously in case of an OXC failure. And for the "interlayer BRS": 4. Lightpaths transiting an OXC and LSPs transiting the co-located router are protected on different physical links;

this prevents the failed entities from competing for the same spare resources in case of an OXC failure.

B. Cost Model

By including the cost of various network elements into the optimization procedure we optimize the network configuration cost which depends on the number and type of established communication channels. In this study we do not deal with the investments for the initial network deployment which include the cost of lying/leasing fibers and the cost of WDM line systems (without transponders), i.e. WDM (de)multiplexers and optical amplifiers. As it has been stated in the problem formulation, the initial network topology determining these costs is given to the problem as an input parameter.

The following cost components are included into the optimization procedure: the cost of IP/optical interface cards c P_IP , the cost of OXC ports c P_OXC and the cost of optical transponders c TR . The costs of the router and OXC equipment are incorporated, respectively, into the IP/optical interface cost c P_IP and the OXC port cost c P_OXC . Additional cost c TT is associated with the amount of transit traffic processed by the routers as a penalty for diminishing the packet processing capability of a router which could be otherwise used by the originating/terminating traffic. The cost c TT is specified by the c P_IP cost per traffic unit:

C c c IP P TT _ = × t r a n s i t t r a f f i c ( 1 )
where C denotes the IP/optical interface card rate. We take as a reference cost the cost of one transponder. The other elements' costs are referenced to this cost as follows:

c P_IP : c P_OXC : c TR = 8 : 0.5 : 1

(2)

This ratio represents the current prices of the elements (year 2005) for 10 Gbps IP/optical interfaces and transponders, 256×256 port photonic OXCs and 200 Gbps routers. The total cost of a network configuration is a sum of the transit traffic cost and the cost of individual circuits: lightpaths and wavelength links, as depicted in Fig. 5. It is assumed that each wavelength link requires 2 transponders and 2 OXC ports (i.e. 1 transponder and 1 OXC port for each termination point) and each lightpath (protection and working) requires 2 IP/optical interface cards and 2 OXC ports. Thus, the cost components c LP and c λ presented in schemes 4 a-d are as follows:

c LP = 2(c P_IP + c P_OXC ), c λ = 2(c P_OXC + c TR ).

C. ILP formulation

The ILPs are defined using the node-arc formulation, where network nodes are indexed by subscripts and edges are specified by an (x,y) node-name pair: • i and j denote originating and terminating nodes in a lightpath, • q denotes a q-th lightpath between the (i,j) pair, • m and n denote endpoints of a physical link.

Inputs:

N set of nodes; each element represents a generic network node being a combination of a router and the colocated OXC. LSP set of K LSPs to be routed in the network; each element lsp k represents an indivisible traffic flow to be routed on a single LSP and has associated a triple: {s(lsp k ), d(lsp k ), b (lsp k )} denoting respectively its source, destination node and bandwidth. LP set of lightpaths determining the logical topology; each element lp has associated a triple: {i(lp), j(lp), q(lp)} denoting respectively its originating, terminating node and the multiple. p_LSP set of LSPs to be protected; a subset of LSP. p_LP set of lightpaths to be protected; a subset of LP. N_ex [lsp] for each lsp in p_LSP, the set of nodes to be excluded from the route of its protection LSP to respect the protection routing constraints. N_ex [lp] for each lightpath in LP, the set of nodes to be excluded from its route to respect the protection routing constraints. Note, that in general not only protection but also working ligthtpaths are subject to the protection routing, e.g. to provide disjointness between (corresponding) working and protection LSPs in the physical topology with the single layer survivability. P NxN physical topology matrix, where the element p (m,n) = p (n,m) = 1 if there exist a physical link between nodes m and n; otherwise p (m,n) = p (n,m) = 0, (i.e. physical links are bidirectional). It is assumed that there are no multiple links between node pairs. C lightpath capacity. T max. number of IP/optical interfaces in a router. W max. number of wavelengths on a physical link.

Variables:

1) Logical topology variables wβ q j i ), , ( , pβ q j i ), , ( = 1 if there exist a q-th lightpath from node i to node j carrying, respectively, working and protection LSPs; 0 otherwise. 2) LSP routing variables wδ lsp q j i ), , ( , pδ lsp q j i ), , ( = 1 if, respectively, the working / protection LSP lsp is routed on the q-th lightpath from node i to node j; 0 otherwise. ), , ( ) , ( if a q-th working lightpath from node i to node j is routed on the physical link (m,n); 0 otherwise. Note, that as protection lightpaths are routed using the sequential method only, no protection routing variable is defined here.

Optimization function:

The objective is to limit the total network resource usage by minimizing costs of the transit traffic and capacity allocation (working + spare) in both network layers:

where: Constraints:

( ) ∑ ∑∑ + ⋅ = Δ lsp i q lsp q n i lsp q n i n p w lsp req b ), , ( ), , ( ) ( _ δ δ - ∑ = n p) lsp : d(ls lsp req b ) ( _ ( 4
) ∑ ∑ + = + q q q j i q j i j i j i p w s w ), , (
1) Constraints for the logical topology design:

T p w i j j q q j i q j i ≤ + ∑∑ ≠ : ), , ( ), , ( β β , N ∈ ∀ i ( 7 ) T p w j i i q q j i q j i ≤ + ∑∑ ≠ : ), , ( ), , ( β β , N ∈ ∀ j (8)
2) Constraints for the LSP routing:

∑ ∑ ∑ ∑ ≠ ≠ - i j j q lsp i j j q lsp w w : q i), (j, : q j), (i, δ δ ⎪ ⎩ ⎪ ⎨ ⎧ = - = = otherwise 0, ) ( d i if 1, ) ( s i if 1, lsp lsp N LSP, ∈ ∈ ∀ i lsp (9) ∑∑ ∑ ∑ - ∉ ≠ j q lsp lsp ex N j i j j q lsp p p q i), (j, ] [ _ , : q j), (i, δ δ ⎪ ⎩ ⎪ ⎨ ⎧ = - = = otherwise 0, ) ( d i if 1, ) ( s i if 1, lsp lsp ] N_ex[ p_LSP, lsp i lsp ∉ ∈ ∀ (10) 1
), , ( ), , (

≤ + lsp q j i lsp q j i p w δ δ q j i lsp , N ) , ( p_LSP, 2 ∈ ∈ ∀ (11) C ) ( b_req ), , ( , ⋅ ≤ ⋅ ∑ q j i lsp lsp q (i,j) w w lsp β δ q j i , N ) , ( 2 ∈ ∀ ( 1 2 ) C ) ( b_req ), , ( , ⋅ ≤ ⋅ ∑ q j i lsp lsp q (i,j) p p lsp β δ q j i , N ) , ( 2 ∈ ∀ ( 1 3 )
3) Constraints for the lightpath routing:

-With the sequential configuration approach:

∑ ∑ - ∉ ≠ m ] [ lp (m,n) lp N_ex m n, m : m lp (n,m) wλ wλ = ⎪ ⎩ ⎪ ⎨ ⎧ = - = otherwise 0, ) ( j if 1, ) ( i if 1, lp n lp n ] N_ex[ LP; lp n lp ∉ ∈ ∀ (14a) ∑ ∑ - ∉ ≠ m ] [ lp (m,n) lp N_ex m n, m : m lp (n,m) pλ pλ = ⎪ ⎩ ⎪ ⎨ ⎧ = - = otherwise 0, ) ( j if 1, ) ( i if 1, lp n lp n ] N_ex[ p_LP; lp n lp ∉ ∈ ∀ (15) 1 , , ≤ + lp n) (m lp n) (m p w λ λ 2 N ) ( p_LP; lp ∈ ∈ ∀ m, n ( 1 6 a ) W p w lp lp n) (m lp n) (m ≤ + ∑ , , λ λ 2 N ) ( ∈ ∀ m, n (17a)
-With the integrated configuration approach:

∑ ∑ - ∉ ≠ m ), , ( ] [ ), , ( q j i (m,n) lp N_ex m n, m : m q j i (n,m) wλ wλ = ⎪ ⎩ ⎪ ⎨ ⎧ = - = otherwise 0, if , if , ), , ( ), , ( j n w i n w q j i q j i β β ], N_ex[ , N ) , ( 2 q lp n j i ∉ ∈ ∀ (14b) 1 , ), , ( , ≤ + lp n) (m q j i n) (m p w λ λ : p_LP , , 2 N ) ( ), ( q j, q(lp) i, j(lp) i(lp) lp q m,n i,j = = = ∈ ∈ ∀ (16b) W p w lp lp n m j i q q j i n) (m ≤ + ∑ ∑∑ ) , ( ) , ( ), , ( , λ λ N ) n , ( 2 ∈ ∀ m ( 1 7 b ) 4) Binary constraints: , , pλ , wλ , pδ , wδ , pβ wβ lp (m,n) lp (m,n) lsp (i,j),q lsp (i,j),q (i,j),q (i,j),q { } 1 0 , , wλ q (i,j) (m,n) ∈ (18)
Eq. ( 4) specifies the transit traffic at node i as a difference between the total incoming traffic and the traffic terminated at i. Eq. ( 7), ( 8) make the number of lightpaths originating and terminating at node i does not exceed T. For each LSP (working + protection), Eq. ( 9), ( 10) specify the flow conservation constraint at every node on its route. Some nodes are excluded from the routing of protection LSPs (Eq. ( 10)) to meet the protection routing constraints. Eq. ( 11) provides logical link disjointness between corresponding working and protection LSPs. Eq. ( 12) and (13) make the total traffic carried by all LSPs on the lightpath (i,j), q not to exceed the lightpath capacity. For each OXC and lightpath (working + protection), Eq. (14 a,b) and (15) specify the flow conservation constraint at the lightpath level. It states that the number of lightpaths incoming to and outgoing from a node is equal. With the integrated approach the logical topology and lightpath routing are determined jointly (Eq. (14 b)), whereas with the sequential approach lightpath routing is determined for the set of pre-computed lightpaths (Eq. 14a)). Eq. (16 a,b) provide link-disjointness between corresponding working and protection lightpaths. Eq. (17 a,b) make the number of lightpaths routed on the physical link (m,n) not to exceed the total number of wavelengths. Binary constraint (18) ensures that the variables take only 0/1 values.

As the traffic matrix is symmetric and lightpaths bi-directional, for the problem simplification we assume that the lightpath set LP is computed only for the half of LSPs, i.e. LSP =

( ) { } d s b d s lsp k < : , ,
. It is assumed that the other half of LSPs: LSP' =

( ) { } d s b d s p ls k > ′ : , ,
is routed over the corresponding complementary lightpaths. (i.e., for bi-directional lightpaths, if there exist the lightpath lp (i,j),q there exist also the lightpath lp (j,i),q , so if the LSP

lsp k(s,d,b) is routed onto lp (i,j),q than the lsp' k(d,s,b) is routed onto lp (j,i),q ).
In a network of N nodes, E links and max. q lightpaths per node pair supporting a traffic matrix composed of K LSPs, the size of the problem solved with the sequential approach is

2 / 2 K N q ⋅ ⋅ ≈
in terms of variables whereas the same problem solved with the integrated approach is

) 2 / ( 2 E K N q + ⋅ ⋅ ≈ .

V. NUMERICAL RESULTS

The problems specified above were implemented and solved using the CPLEX 9.0 optimization package. All experiments were carried out on a HP Alpha workstation with a 1 GHz CPU and 2 GB RAM running Tru64 UNIX OS. The system parameters were set as follows: C = 10 Gbps, W = 32, q = 2, T = )

1 ( 2 - ⋅ N q
. The number of wavelengths per link W, IP/optical interface cards per node T, the router throughput and the OXC size were overprovisioned in a way that no resources shortage constraints were affecting the configuration process, but only the optimization function used.

A. Computational efficiency

The logical topology design problem belongs to the class of NP-hard problems for which no efficient (i.e. polynomial time) algorithms are known. It is therefore essential to verify the computational limits of the proposed ILP-based solution method. The problem complexity measure was the execution time of the algorithms as a function of the problem size (in terms of the number of nodes and traffic demands). Solution times of the network configuration based on the sequential and integrated approaches were compared for different problem sizes and for the computation of working vs. protection paths. The solver was set to stop any optimization within a maximum time limit of 5 hours and a 3% solution optimality gap was assumed. If in any case the solver stopped without full termination, the solution quality achieved so far has been reported in terms of the optimality gap. The results are summarized in Table 1.

Table 1. Running times of the ILP algorithms for different problem sizes (values in brackets denote achieved optimality gaps).

The obtained results show that by setting reasonable optimality gaps and run-time limits on ILP algorithms quite good solutions to the specified problems can be obtained even without a full termination, at least for moderate size networks (up to 15 nodes with fully meshed traffic matrices). Thereby, the proposed ILP-based solution method can be used as a practical design tool, for example, for nationwide backbone networks (which typically consist of 10-15 nodes in European countries) without resorting to heuristics. The solution times of the optimization based on the integrated approach is about one order of magnitude longer than when using the sequential approach and the difference in solution times for the two methods increases as the problem size grows. This was expected as in a network of N nodes, E links and max q lightpaths per node pair the complexity of the integrated approach increases by ~ 2 N E q ⋅ ⋅ faster in terms of variables and constraints compared to the sequential approach. As a consequence, for the biggest solved problems the solution could only be obtained using the sequential approach.

Solution times for the computation of protection paths were longer due to additional constraints for protection routing: (11) and (15).

B. Analysis of results

For the survivability implementation we used a test network targeted to a nationwide coverage, presented in Fig. 6. The network has a bi-connected mesh topology consisting of 12 nodes and 24 physical links. There are 10 nodes distributing the nationwide traffic (1-10) and 2 gateways providing the Internet access (11,12). The traffic matrix is population-weighted and consists of 56 bidirectional, symmetric traffic demands or 126 LSPs (as some demands consist of more than 1 LSP). To check for different values of the LSP bandwidth and the total offered traffic, three groups of tests were carried out: for the average LSP bandwidth equal to 2.5, 5.0 and 7.5 Gbps. The results obtained with the sequential configuration method are summarized in Tables 2 a-c and Fig. 7.

1) Single layer vs. multilayer survivability analysis.

The main difference between the single layer (SL) and the multilayer (ML) survivability is due to the fact that with the ML survivability only multihop LSPs are subject to protection routing and hence consume the MPLS spare capacity, whereas with the SL survivability both single-and multi-hop LSPs require spare resources of the MPLS layer. This results in higher number of lightpaths carrying protection LSPs (see values in brackets in Tab. 2a-c) and higher transit traffic obtained with the SL survivability. However, with the ML survivability protection lightpaths are added, so the total number of lightpaths is higher in this scenario. This in turn affects the total configuration cost as lightpaths are the most expensive network resources.

For low bandwidth LSPs, the SL survivability is the cheapest option, as depicted in Tab. 2a and Fig. 7. Low bandwidth LSPs tend to be routed in multiple logical hops as they are groomed in intermediate routers to better fill the lightpath capacity. As a result, there exist relatively many multi-hop LSPs wich are subject to protection routing with the ML survivability and more lightpaths are added after the protection LSP routing (21), despite a small total number of lightpaths. This makes the ML survivability the most expensive option for low bandwidth LSPs.

This relation changes for high-bandwidth LSPs, close to the lightpath capacity (Tab. 2c). High bandwidth LSPs tend to be routed in single logical hops, i.e. on direct lightpaths, to minimize the transit traffic (note the small amount of the transit traffic, as compared with the other traffic scenarios). Therefore, there exist relatively few multi-hop LSPs which are subject to the protection routing with the ML survivability. As a result, much fewer lightpaths are added after the protection LSP routing [START_REF] Groove | Mesh-Based Survivable Networks. Option and Strategies for Optical, MPLS, SONET and ATM Networking[END_REF], as compared with the SL survivability (105). This tendency and further savings in the wavelength use brought by the ML survivability (respectively 15%, 18% and 20% with different SCA methods) make this option the cheapest in this traffic scenario. The difference in the wavelength usage is due to the fact that with the SL survivability working and protection LSPs have disjoint routes in both network layers, whereas with the ML survivability working and protection lightpaths are disjoint only in the optical layer. As a result, lightpaths take longer routes with the SL survivability.

We found the ML survivability with the "double protection" the most expensive option for the low-and medium-size LSPs (see tab. 2a, b)

2) Multilayer survivability -analysis of different SCA methods

Decreasing cost trends from "double protection" to "LSP spare unprotected" to "interlayer BRS" was expected as the spare resources of the MPLS layer are supported more and more efficiently by the optical layer. Lower total number of lightpaths achieved with the "LSP spare unprotected" method over the "double protection" is due to the fact that the lightpaths carrying protection LSPs (respectively 21, 20 and 10 with different traffic scenarios) are not protected. Savings in the wavelength usage are because fewer lightpaths in total are routed in the physical topology (respectively 66 vs. 82, 148 vs. 160 and 216 vs. 226 for different traffic scenarios). Further savings are brought by the "interlayer BRS" method due to wavelength sharing among lightpaths carrying protection LSPs and protection lightpaths. One can see that most of the wavelengths used by the protection lightpaths are reused by the lightpaths carrying protection LSPs. Only, respectively, 4, 7, and 0 extra wavelengths are needed to accommodate protection LSPs within the optical layer for different traffic scenarios. This gives the reuse factor equal respectively to 84%, 80% and 100%. 3) Sequential vs. integrated configuration method.

As a next step we tested the impact of the sequential vs. integrated configuration method on network resource usage and configuration cost. The results produced by the two methods for different survivability options and the traffic matrix consisting of medium-size LSPs are summarized in Table 3 and Fig. 8. In all cases we observed a gain in the wavelength usage brought by the integrated method over the sequential one, while the MPLS layer resources (i.e. no. of established lightpaths and the transit traffic) were exactly the same. The difference is due to the fact that with the sequential approach the logical topology design and the lightpath routing are separated and the lightpaths are configured without the knowledge of the physical layer resources. As a consequence, the resulting logical topology is sub-optimal with respect to the wavelength usage and some lightpaths require longer physical routes. This effect is avoided with the integrated method where the both processes are configured jointly. This allows the lightpaths to be optimally designed also in terms of the wavelength use (in fact, about 40% of lightpaths had different termination points when configured with the integrated method as compared to the sequential one). The gain from using the integrated approach is higher for the configuration with working paths only (i.e. without survivability), as with the survivability implementation the wavelength routing is subject additionally to the protection routing constraints which tighten the solution space and leave less room for optimization. Table 3. Sequential vs. integrated configuration method for different survivability options with the average LSP bandwidth equal to 50% of C (as in Tab. 2a). As the number of lightpaths remains the same for both approaches which constitute about 70% of the total configuration cost (comp. Fig. 8), the contribution of the integrated approach to the total cost savings is only 1.4% -3%.

VI. CONCLUSIONS

This study explored some design principles of MPLS over OTN architectures employing wavelength switching and targeted to a nationwide coverage. We used the ILP optimization combined with a cost model to dimension the network with the minimal resource usage and configuration cost. We have presented two approaches to the MPLS over OTN design and investigated various options for the survivability implementation.

The comparative analysis between the single-and multilayer survivability shows the impact of the LSP bandwidth on network resources usage and configuration cost. For high bandwidth LSPs, close to the lightpath capacity, the multilayer survivability is up to 5% more cost-effective in terms of the total cost and up to 20% in terms of the optical layer cost. Contrary, for the low bandwidth LSPs this is the single layer survivability which brings up to 26% of total cost savings. For the multilayer survivability we have demonstrated that by mapping efficiently the spare capacity of the MPLS layer onto the resources of the optical layer one can achieve up to 22% savings in the total configuration cost and up to 37% in the optical layer cost. We have found the integrated configuration method up to 9 % more cost-efficient in terms of the wavelength use as compared with the sequential one, however, at the increase in the optimization problem complexity. The obtained results are based on a cost model with actual technology pricing and representative traffic matrices.

Finally, we show that by setting reasonable optimality gaps and run-time limits on the ILP algorithms quite good solutions to the specified problems can obtained even without a full termination. Thereby, the proposed ILP-based solution method can serve as a practical design tool, at least for moderate size networks, without resorting to heuristics.

Fig. 1 .

 1 Fig. 1. Architecture of the MPLS over OTN.

  , c LP, c λ Min: cttΣ∆ i + clpΣwij + cλΣwe optimize a) Sequential configuration method (the overlay model) b) Integrated configuration method (the peer model)

1 .

 1 Each working LSP (wLSP) has a protection LSP (pLSP); corresponding working and protection LSPs are nodeand link disjoint both in the in the logical and physical topology. II. For the multilayer survivability b) Multilayer survivability with double protection survivability with the "LSP spare unprotected" option d) Multilayer survivability with the interlayer BRS a) Single layer survivability 1. Each multihop working LSP has a protection LSP; corresponding working and protection LSPs are link-and nodedisjoint in the logical topology.

Fig. 5 .

 5 Fig. 5. An example of the MPLS over OTN configuration combined with the network elements' cost.

•

  s and d denote source and destination nodes of an LSP,

3 )

 3 Lightpath routing variables: a) With the sequential configuration method: , respectively, the working / protection lightpath lp is routed on the physical link (m,n); 0 otherwise. b) With the integrated configuration method: wλ q j i n m

  c TT , c LP and c λ are associated as specified in the cost model (see Sec. IV B)

Fig. 6 .

 6 Fig. 6. The 12-node test network.

  with the double protection -multilayer survivability with the LSP spare unprotected -multilayer survivability with the interlayer BRS

Fig. 8 .

 8 Fig. 8. Cost comparison of the sequential (Seq.) vs. integrated (Int.) configuration method.

Table 2 .

 2 Network resource usage and the configuration cost for different survivability options. The number of lightpaths in brackets (row 2) denotes the lightpaths carrying protection LSPs. The number of wavelengths in brackets (row 3) denotes extra wavelengths needed to accommodate protection LSPs with the "interlayer BRS". The cost percentage denotes the cost savings with respect to the most expensive method.

		Computation of working paths			Computation of protection paths
	Config.		Problem size (N)		Config.			Problem size (N)
	Approach	8	10	12	14	15	Approach	8	10	12	14	15
	Sequential	12.4 s (0.77%)	70 s (0.72%)	951 s (0.5%)	1403 s (0.41%)	3632 s (0.83%)	Sequential	(optimal) 70 s	(0.44%) 1011 s	(0.66%) 2542 s	(0.32%) 17093 s	unsolved
	Integrated	101 s (1.62 %)	542 s (1.66%)	1211 s (1.18%)	18000 s (2.8%)	unsolved	Integrated	550 s (0.34%)	8856 s (1.12%)	18000 s (1.76%)	unsolved	-----

The MPLS layer also protects against OXC failures with respect to the LSPs transit in co-located routers.


Bruno Cessac
email: bruno.cessac@inria.fr

The retina: a fascinating object of study for a physicist

I briefly present joint research works where ideas and methods from theoretical physics can be applied to better understand the behaviour of the retina in normal, developmental and pharmacologically controlled conditions.

Introduction

Our visual system has astonishing capacities, from the rapid extraction of the main features of a visual scene, to higher level tasks like reading or face recognition. Our vision starts from the retina. This tiny membrane of a few hundreds of microns thickness covering 75% of the internal ocular globe performs fundamental, yet complex, tasks. Although its prior function is to convert the photons from the outer world into sequences of action potentials (spike trains), encoding the visual scene and conveyed to the visual cortex where they will be "decoded", the retina is not a mere camera. In recent years, researchers has indeed discovered that the retina "is smarter than scientists believed" [1].

In this paper, I would like to share with the reader the fascination for the retina of a physicist, working since years in the field of dynamical systems the-ory and statistical physics applied to "complex systems" -especially neuronal models. Working with biologists specialists of the retina I have discovered a beautiful object of studies both from the applied and theoretical physics point of view. The retina machinery (neurons, synapses, ions transport, light conversion from photoreceptors...) is governed by physics. Yet the extrapolation of physical methods from theoretical physics (mean-field methods, transport equations, Gibbs distributions, . . .) raises several interesting questions I have been confronted with during my research, and that I want to briefly present in this paper.

The retina structure

In all this paper, I will use a "computer-oriented" language to deal with the retina: "information, circuits, code, decode, computation," . . .. This is a contemporary view, largely influenced by our computer-based society. Although this analogy is useful -it eases explanations and provides fruitful paradigmsit has its limitations stressed throughout this paper.

The retina, as the rest of our body, especially the brain, has an evident problem: it can't afford large variations of temperature. Especially, the Joule effect has to be strongly limited. As a consequence, neurons, which are cells producing electric currents, do not use electrons, they use ions transfer (sodium, potassium, calcium, chloride, . . .). The currents produced this way are small (of order 1 -100 pA), as well as voltage variations (∼ 100 mV) thus with an electric power of order pW. Even if there are many neurons of different types in the retina (of order 10 8 , including photo-receptors), the total heat production is quite small, compared to a computer that would perform the same tasks. However, ions are quite slow, and the corollary is that the retina has to use massive parallel computations to perform complex tasks in a short time. This computation is achieved via neurons, but also by synapses: the synaptic organization of the retina plays a central role in its abilities (see eg. http://webvision.med.utah.edu/book/part-i-foundations/simple-anatomy-of-theretina/).

The retina converts photons into variations of electric potential (phototransduction) via photoreceptor cells: rods (about 130 million) ensure eyesight in poor illumination; cones (about 7 million) ensure central vision and colour perception. Phototransduction is a very efficient mechanism as a single photon can produce a visual effect. This is due to a complex cascade of molecular mechanisms with a huge multiplicative effect. At the other side of the retina one finds retinal ganglion cells (RGCs), the final stage of retina encoding, as these are the ones that emit action potential (spikes) via their axons (which constitute the optic nerve), to the visual cortex, via the thalamus. There are about 1.2 to 1.5 million RGCs in the human retina. On average each RGC receives inputs from about 100 rods and cones. These numbers vary greatly among individuals and as a function of retinal location. In between, one finds 3 cells types: horizontal, bipolar and amacrine cells. Unlike most neurons, these cells communicate via graded potentials, rather than action potentials. Horizontal cells are laterally interconnecting neurons, helping integrate and regulate the input from multiple photoreceptors. Bipolar cells transmit the signals from the photoreceptors or the horizontal cells, and pass it on to the ganglion cells directly or indirectly (via amacrine cells).

The retina has therefore both a feedforward structure (from photoreceptors to ganglion cells) and a lateral structure (due to horizontal and amacrine cells). This generates different types of neural circuits enabling the RGCs to efficiently process local visual information such as dim light small responses to single photon absorption, segregating moving objects, filtering the movement of body, head, or eye, motion extrapolation, detection of approaching motion, surprise at the missing element in the sequence. Many of these computations match to the evident challenge of animals: to detect moving objects and locate them correctly; the struggles with a constantly moving image sensor; and the need to predict the future and adapt to changing conditions [1]. Thus, the thalamus and visual cortex receive not a computer-like pixel representation of the image, but a set of features processed via nonlinear mechanisms that researchers try to identify [1].

The optic nerve is therefore like an optical fiber with several millions of channels -the axon of each RGCs -conveying a local spatio-temporal information encoded by sequences of spikes, decoded by the brain. However, in contrast to computers, the code has variability and, nevertheless, robustness. First, several presentations of the same visual stimulus do not trigger the same sequence of spikes although some statistical regularity is observed (typically, a given RGC type fires more intensively when a specific stimulus is presented). Second, there is not a unique coding strategy. RGCs convey part of the information independently from each other through their firing rates, or spikes timing. But they share information because the spatial region they scan have overlaps (a photoreceptor contributes the activity of several RGCs) inducing stimuli-induced correlations in their response. In addition, the lateral connections from horizontal and amacrine cells induces indirect interactions between RGCs. Therefore, also RGCs presumably encode information at a population level. This "population coding" presents several advantages: redundancy, reduction of uncertainty, simultaneous coding of different stimulus attributes, fast response, . . .. It is however a contemporay challenge to understand it.

Population coding and statistical physics

Current acquisition technologies (Multi-Electrodes Array, MEA) allow to record simultaneously several thousands of RGCs in response to a visual scene, providing a contemporay challenge: try and decipher the visual scene from the RGCs spikes, and thereby infer coding strategies of the visual system. Part of this information can be recovered by assuming that cells encode information independently. This allows to design "decoders" based on firing rate, spike latency, rank order, . . .. Yet, the decoders built this way have many fitting parameters and their efficiency may vary with the visual stimulus. In addition, it has been shown [2] that a part of the information is carried by the (weak) correlations between RGCs suggesting that population coding takes place.

For a modeller, it seems clear that a population of connected neurons submitted to an external stimulus will produce a correlated response at the population levels. We have made a mathematical analysis of this aspect in [3,4], using Integrate and Fire models. We have shown that the population statistics is described by a variable length Markov chain where transition probabilities can be explicitely written: they depend on neurons connectivity, on the stimulus and on spikes history in a similar fashion as the so-called Generalized Linear Models [5].

Such Markov chains are closely related to what physicists call "Gibbs distributions", initially introduced by Boltzmann and Gibbs to establish a link between microscopic dynamics of particles and thermodynamics. Gibbs distributions are probabilities of exponential form where the term in the exponential is, in physics, proportional to the energy; the form of the energy is constrained by the forces involved in the problem and defines a statistical model or an "ensemble". More generally, in the correspondance with Markov chain, the term in the exponential has not the interpretation of a physical energy, but we will call it "energy" as well, for simplicity. When dynamics is time-translation invariant ("stationarity") Gibbs distributions are obtained by maximizing the statistical entropy under the constraint that the average of the observables defining the energy is fixed (Maximum Entropy Principle, MEP), but their definition via the equivalence with variable length Markov chains allows to handle non stationary situations.

Using Gibbs distributions to analyze retina data and population coding has known a great success within the last decade. In particular, several important results have been obtained by using the MEP for an energy having the form of an Ising model, i.e. taking into account instantaneous pairwise interactions between neurons [2]. Extensions to more general energy forms have been considered too (triplets interactions [6], time delayed interactions [7]). Especially, we have developed efficient algorithms and a software, PRANAS, [8] allowing to fit the parameters of a Gibbs distribution (whose energy form is given) from MEA data.

This "Gibbs" approach is appealing for a physicist. It would allow to apply the powerful techniques and concepts from statistical physics to the analysis of the neural code. In addition, exhibiting a canonical form of energy well fitting retina data could be a step towards a "thermodynamics" of the retina: to explain the dynamics of a large population of RGCs by a combination of a few canonical observables. This approach raises however several deep questions.

• Which energy form ? In contrast to statistical physics/ thermodynamics the energy form for the retina cannot be inferred from first principles, so researchers are reduced to guess the form. Unfortunately, a mathematical analysis based on the mapping between Markov chains describing the neuronal dynamics and Gibbs distribution shows that the corresponding energy has generically a plethora of highly redundant observables [4]. We have proposed a method to eliminate these redundant terms from data analysis using information geometry, and we have shown experimentally that the degree of redundancy depends on the visual stimulus correlations [START_REF] Herzog | networks[END_REF]. • Non stationarity. Most Gibbs approaches, based on MEP, use the assumption of stationarity. On the opposite, the retina mainly responds to changes in a visual scene, that is transient, non stationary stimuli. The MEP does not extend to this case. We have developed an approach, based on linear response theory, where a time-dependent stimulus is viewed as a perturbation of a stationary state (spontaneous activity) that can be characterized, from data, using MEP. In this case, the response to the stimulus can be writ-ten in terms of correlations of the stationary case (this an extension of the fluctuation-dissipation theorem of physics) [10]. • Decoding. Assume we are able to characterize the population statistics of RGC with a Gibbs distribution, how can we use it to decode the visual stimulus from it ? Although some promising approaches have been proposed this question seems far from being solved.

Retinal waves, retinal development and non linear dynamics

Right after birth the visual system of vertebrates is not yet effective. A complex, transient sequence of dynamical processes takes place starting a few days before birth, progressively enabling "the eyes to see" and stopping when vision is functional. A large part of this processing is due to waves of electric activity ("retinal waves") spreading through the retina with a characteristic periodicity. This macroscopic phenomenon (i.e. occurring at the scale of the whole retina) originates from microscopic processes starting at the molecular level (ionic channels), inducing bursts of activity of specific cells, spreading through the retina thanks to cells connectivity. Retinal waves are classified into 3 consecutive stages each having a specific role in visual system development. The transition between stages results from morphological changes genetically programmed. However, a part of this spatio-temporal activity and its transformation during development can be explained by generic mechanisms in nonlinear dynamics, as we sketch here, focusing on stage II. This section is a summary of D. Karvouniari thesis [11,[START_REF] Karvouniari | Retinal waves: theory, numerics, experiments[END_REF], work done in collaboration with Institut de la Vision and InPhyNi (L. Gil).

Stage II retinal waves are due to spontaneous and periodic bursts of activity of specific retinal cells, the starburst amacrine cells (SACs) coupled via the excitatory neurotransmitter acetylcholine (Ach). When a SAC is active (bursting) it releases acetylcholine; this can trigger the activation of post-synaptic cells. The membrane potential V of SAC i can be modeled as:

C dV i dt = I ion (V i , •) + I sAHP (V i , R i ) + I Ach (V i , A j ), ( 1
)
where C is the membrane capacitance. The term I ion (V, •) represents the sum of ionic currents involved in SACs bursting (mainly calcium and potassium), and depending on additional dynamical variables represented, for simplicity by the symbol • (see [11] for detail); I sAHP (V i , R i ) is a slow hyperpolarization potassium current, depending on a refractory variable R i controlled by a cascade of kinetic processes; finally, I Ach (V, A j ) is the sum of excitatory acetylcholine currents due to active pre-synaptic cells j connected to i.

A bifurcation analysis of the model (1) shows that a SACs can switch, by a saddle-node bifurcation, from a rest state to fast oscillations of order millisecond (bursting). This arises when the current I tot = I sAHP + I Ach crosses from below a threshold value I SN depending on biophysical parameters (conductances, reversal potentials, ... ). Reciprocally, when the cell is bursting it can go back to a rest state, by a homoclinic bifurcation, if I tot crosses from above a threshold value I H c . In general, I H c < I SN but they differ from a few pA, so, for simplicity, we identify them from now. Thus, in short:

if I tot = I sAHP + I Ach , < θ , SAC is at rest, > θ , SAC is active. (2)
The transition from rest to active is due to excitation from pre-synaptic active cells, via the excitatory current I Ach (V, A j ). The transition from active to rest is due to the slow hyperpolarization current I sAHP (V i , R i ) (having a negative sign). Indeed, when the cell is active a complex mechanism, involving calcium takes place, I sAHP (V i , R i ) becomes more and more negative, leading the cell, after a few seconds and via a bifurcation, to an hyperpolarized rest state where it can not be excited during a long period (of order one minute), independently of the excitatory current I Ach provided by the other cells.

Thus, waves propagation is due to a transition from rest to active state of SACs transmitted via Ach interactions. Waves are stopped by hyperpolarized regions corresponding to cells which have burst in a former wave. Therefore, each wave has to propagate into a landscape, imprinted by previous waves, with refractory regions and excitable regions. This lanscape evolves slowly in time, on time scales which are longer than the refractory period of a SACs. This generates a spatial anisotropy where some cells are more active ("leaders") and some others more refractory. In this way, the mere dynamics generate a huge spatio-temporal variability, even if the cells are initially identical. This (biologically observed) variability is purely dynamical and does need to add extra mechanisms to be explained.

A nonlinear wave propagation equation can be obtained, upon several approximation, considering SACs are located on a d-dimensional regular lattice, with spacing a, and nearest-neighbours interactions. The Ach conductance, Γ , considered now as a field in a d-dimensional continuum, obeys:

∂Γ ∂t = -µ Γ + 2dΩ H [Γ -Γ c (R) ] + a 2 Ω ∆ H [Γ -Γ c (R) ] , (3)
where µ is the Ach degradation rate, Ω the Ach production rate; ∆ is the Laplacian operator; H is the Heaviside function, mimicking the threshold effect (2), and Γ c (R) is the critical threshold, derived from the bifurcation condition (2) in a refractory landscape characterized by the variable (field) and depending upon the network history. This is a singular equation because one applies a Laplacian to a Heaviside function. It is however possible to smooth the Heaviside function to get rid of this singularity. This equation can be solved for simple refractory landscapes, but the general situation, where R is a random landscape imprinted by waves history is still under investigation. The process of wave generation and propagation bares some analogy with forest fires introduced in the context of Self-Organized Criticality (SOC). SOC systems have the property to self-organize into a state where characteristic events (avalanches) have power law distributions. This has lead some researchers to hypothetize that the retinal waves distribution (size or duration) could follow a power law [START_REF] Hennig | [END_REF]. Experimental evidences are not convincing though and would deserve a more elaborate analysis. Interestingly, eq. (3) corresponds to a continuum limit of a SOC model (a sandpile) if the term -µΓ + 2dΩ H [Γ -Γ c (R) ] = 0. This is very specific and non generic situation. As a consequence, in our model, waves distribution are exponentials, except at a specific curve in the parameters space, given by this specific relation and related to the bifurcation condition (2); there the distribution is a power law. This suggests that SACs do not organize in a critical state unless some additional mechanisms is added (like homeostasy), driving them towards the critical curve. This model provides an example where one can construct the path from molecular scales to neurons scale, to macroscopic scale. The mathematical analysis allows us to explain bursting of SACs and wave propagation with simple mechanisms in nonlinear dynamics. In addition it allows us to compute explicitely several important quantities such as the wave speed.

But the main interest is the closeness to experiments. The model does not only reproduce experimental facts, it also lead us to experimental predictions, some of them on the way to be experimentally confirmed (see [11,[START_REF] Karvouniari | Retinal waves: theory, numerics, experiments[END_REF] on the role of kV3 channels on bursting of SACs during stage II). Especially, we are able to characterize how retinal waves structure is evolving during development, when synaptic connections are modified. Likewise, the model is accurate enough to explain pharmacological manipulations (e.g. channels or synaptic terminal blocking).

Conclusion and perspectives

In this paper, I have given examples of research where concepts and methods from theoretical physics are used to understand the retina dynamics and how it encodes information. I would like new to briefly present further ongoing developments.

Amacrine cells and motion processing. When an object moves accross the visual field our visual system is able to interpolate its trajectory and to filter many spurious information: eyes-head-body movements, motion of the background. Especially, anticipation is absolutely essential to compensate the time lag of 30 -100 ms between the reception of photons in the retina and the visual cortex response. Part of the anticipation process starts in the retina and is explained by the non linear response (gain control mechanism) of bipolar and ganglion cells [14]. This does not take into account the lateral connectivity of amacrine cells, which play an important role in motion processing (differential motion, approaching motion, . . .). We want to understand the possible role of amacrine cells lateral connectivity in the retina in processing complex motion. Especially, we are seeking a specific transient signature in RGCs correlations, in response to a moving object. We believe that correlated response could provide a more efficient processing of the object motion, especially trajectory anticipation and interpolation. We want to validate this hypothesis at the modelling level (PhD thesis of Selma Souihel) and experimental level, in collaboration with Institut de la Vision and Institut des Neurosciences de la Timone, in the context of the ANR Trajectory.

Effect of switching pharmacologically a population of RGCs. At present, over 30 RGC sub-types have been identified, typically on the basis of common anatomical features or basic functions (e.g. sensitivity to motion, orientation, motion direction etc.). In collaboration with the University of Newcastle, in the context of E. Kartsaki thesis, we want to investigate how different groups of RGCs contribute to the encoding of visual scenes. The project is using a pharmacogenetics approach (combined with MEA physiology, anatomy, computational modelling and behaviour) to reversibly silence subgroups of RGCs sharing gene expression through specific drugs (DREADD) activation. Removing an entire functional RGC group from the population response will shed light about the role these same cells play in population encoding of complex visual scenes and which information is lost, locally and globally.


Hamza Drid
email: hdrid@irisa.fr

Bernard Cousin
email: bcousin@irisa.fr

Miklos Molnar
email: molnar@irisa.fr

A Heuristic Solution to Protect Communications in WDM Optical Networks using P-cycles

Optical WDM mesh networks are able to transport huge amount of information. The use of such technology however poses the problem of protection against failures such as fibre cuts. One of the principal methods for link protection used in optical WDM networks is pre-configured protection cycle (p-cycle). The major problem of this method of protection resides in finding the optimal set of p-cycles which protect the network for a given distribution of working capacity. Existing heuristics generate a large set of p-cycle candidates which are entirely independent of the network state, and from then the good sub-set of p-cycles which will protect the network is selected. In this paper, we propose a new algorithm of generation of p-cycles based on the incremental aggregation of the shortest cycles. Our generation of p-cycles depends on the state of the network. This enables us to choose an efficient set of pcycles which will protect the network. The set of p-cycles that we generate is the final set which will protect the network, in other words our heuristic does not go through the additional step of p-cycle selection.

I. Introduction

Survivability becomes an important issue and well studied topic in wavelength division multiplexing (WDM) optical mesh networks. The WDM technology allows the transmission of huge amounts of data over the same fibre. Currently an optical fibre of 140 wavelengths is able of transmitting up to 14 Tbit/s over a distance of about 160 kilometres [11]. Consequently, any cut of such a fibre may lead to huge data loss and a lot of traffic being blocked. For this reason, methods and mechanisms of protection should be implemented to minimize the data loss when the failure occurs. Several methods for network protection have been proposed. One of the principal protection methods used in optical WDM networks is pre-configured protection cycles (p-cycle). The concept of p-cycle was introduced by Grover and Stamatelakis [START_REF] Schupke | Optimal configuration of p-cycles in WDM networks[END_REF]. The basic idea of p-cycle protection has been inspired from the ring 1 protection. The main difference between p-cycle and ring protection is that, p-cycle protection not only protects the cycle links but protect all links whose end nodes belong to the p-cycle. In other words, p-cycle protects the cycle links and the straddling links in the cycle. A straddling link is a link which does not belong to the p-cycle but whose end-nodes are both on the p-cycle. Each p-cycle can offer two restoration paths to the failed straddling links without requiring any additional spare capacity. This propriety reduces effectively the required protection capacities. The major problem of this method of protection resides in finding the optimal set of p-cycles which protects the network for a given working capacity distribution. The p-cycle design can be formulated as a non-joint or joint optimization problem. In the first approach, after the working paths are routed (e.g. using shortest paths) the optimal set of p-cycles is calculated using available capacity [START_REF] Grover | Cycle-Oriented Distributed Preconfiguration: Ring-like Speed with Meshlike Capacity for Self-planning Network Restoration[END_REF][2][3] [START_REF] Schupke | An ILP for Optimal p-Cycle Selection without Cycle Enumeration[END_REF]. In the second approach, the routing of the working paths (for the demands) and their p-cycles are computed simultaneously minimizing the total capacity [START_REF] Grover | Advances in Optical Network Design with p-Cycles: Joint optimization and pre-selection of candidate P-cycles[END_REF][6] [START_REF] Nguyen | Joint optimization in capacity design of networks with p-cycle using the fundamental cycle se[END_REF].

Several solutions have been proposed in the literature to solve this optimization problem. These solutions can be classified into two categories: exact solution and heuristic solution. The first category uses generally the Integer Linear Programming (ILP) to find the optimal solution. However, ILP becomes unsuitable as the size of the network increases. Because the number of p-cycles possible in a graph grows exponentially as the size of the network grows (number of nodes and edges). The second category of solution is heuristic which is itself divided into two sub-classes: a heuristic approach based on an ILP formulation and a pure heuristic approach. In the first sub-class of solution, the limit set of p-cycle candidates is generated, and then the good sub-set of p-cycles which protects the network is selected using ILP formulation. The second sub-class (pure heuristic) tries to find a good solution without using ILP formulation. The objective of this solution is to reduce the time required to compute the good set of p-cycles that protects the network.

In this paper, we focus on the heuristic algorithms, which first generate a set of p-cycle candidates, and then a good sub-set of p-cycles that protects the network is selected. As we will describe in the next section, most of the solutions proposed in the literature consider that the p-cycles which have more straddling link as the most efficient p-cycles. Consequently, their generation of p-cycles is based only on the topology of the network and it is completely independent of the state of the network (working capacity distribution). An others drawbacks of these solutions are that they generate a big number of candidate p-cycles and the number of p-cycles selected for protection is very big. That makes configuration of network very complex. In this paper we propose a new heuristic for p-cycles generation that takes into account the state of network and that generates a small number of p-cycle which leads to good performance.

The rest of the paper is organized as follows. In section 2, we review some existing solutions and outline the limitations of each algorithm. In section 3, we describe our proposed algorithm of p-cycles generation based on the incremental aggregation. We evaluate our solution and we compare it with other algorithm in section 4. A conclusion is given in section 5.

II. State of the Arts

In [START_REF] Zhang | Finding protection cycles in DWDM networks[END_REF] Zhang and have proposed Straddling Link Algorithm (SLA). The main idea of this algorithm resides in the method of generation of the set of p-cycle candidates. The p-cycles generated by SLA contain potentially one straddling link. In order to construct this type of p-cycle, SLA looks for two shortest node-disjoint paths between the two end nodes of a link. If these paths exist, SLA combines these two paths to construct a p-cycle. SLA is very fast but the set of candidates cycles generated are generally inefficient because they have only one straddling link. Doucette et .al [START_REF] Doucette | Algorithmic Approaches for Efficient Enumeration of Cadidate p-Cycles and Capacitated p-Cycle Network Design[END_REF] have proposed Capacitated Iterative Design Algorithm (CIDA) which is independent of ILP. This algorithm has two steps. In the first step, a set of candidate p-cycles is generated. In CIDA the generation of p-cycles is based on the transformation of the set of cycles provided by SLA into more efficient p-cycles. Three algorithms of transformations were proposed. The main principle of these algorithms consists of replacing the on-cycle2 link of SLA p-cycle by a path between the end nodes of this link. After this transformation the oncycle link becomes a straddling link of the new p-cycle obtained. In the second step, the efficient p-cycles are selected one by one iteratively from the set of candidate p-cycles. In each iteration step, the working capacity protected by a selected cycle is removed. The second step ends when all working capacities are protected. Efficient p-cycles are the cycles that have a high value of actual efficiency (AE).

∑ = ∈ ∑ ∈ ∀ × = 1 , / , ) ( i p X E i i C E i i p X i w p AE
The actual efficiency is defined as:

Where w i is the amount of unprotected working capacity on link i, X p,i the number of protection paths provide by cycle p after failure of link j. C j is the cost of link j.

Another algorithm has been proposed by [START_REF] Liu | Finding good candidate cycles for efficient p-cycle network design[END_REF], called Weighted DFS-based Cycle Search (WDCS). The goal of the algorithm is to compute a small set of candidate p-cycles that can lead to good performance when used by ILP or the heuristic algorithm. WDCS generates two types of cycle, high efficiency cycles and the shortest cycles. A high efficiency cycle is generated using DFS (Depth First Search). The main idea of WDCS is to construct a cycle which starts from a node x and finish at the same node by traversing the DFS path. WDCS assigns weights to the directed edges in the graph to control the behaviour of DFS and to find a p-cycle which includes more straddling links. To extend the searching path, DFS in this algorithm selects a neighbour node w of node v such that (v, w) has the highest weight among all outgoing links incident to v. In the basic DFS, when extending the search path from a node v, the neighbours of v are selected in arbitrary order. The number of cycles produced by WDCS is controlled by an input parameter k.

The second type of cycle is shortest cycle. This algorithm computes two shortest cycles for each link e in the graph. One of the cycles has e as a straddling link (generated with an algorithm similar to SLA) while the other has the link e as an on-cycle link. To create the second cycle, the algorithm finds the shortest path between the end-nodes of e in the graph and combines it with e. As in CIDA, the drawback of the WDCS algorithm is that the generation of candidate cycles is based only on the network topology without considering the state of the network (working capacity distribution).

As describe earlier, most of the solutions proposed in the literature consider the p-cycles which have more straddling link as the most efficient p-cycles. Consequently, their generation of p-cycles is based only on the topology of the network and it is completely independent of the state of the network (working capacity distribution). But in practice, however, the optimal solution can contain different sizes (number of straddling links) of p-cycle as shown in Fig. 1.

Figure .1 (a) shows a WDM network with 8 optical switch, where each link has an integer value that indicates the working capacity of the link. Figure. 1 (b) shows the set of optimal p-cycles that protect the network with a given working capacity. We see well that the optimal solution contains different kinds of p-cycles. This means that the p-cycles which have more number of straddling links are not always the best p-cycles. The table shown in Fig. 5 (c) contains the final set of p-cycles which protect network where n i presents a capacity of p-cycle.

The solution that we propose in this paper generates p-cycles by taking into account the state of the network. This enables us to choose an efficiency set of p-cycles which will protect the network. Our solution is based on the incremental aggregation of the cycles. This consists of choosing the cycle with maximal protection capability among all shortest cycles in the network. Then we aggregate it iteratively with other shortest cycles (according to rules which take into account the state of the network) in order to obtain an efficient p-cycle. With our algorithm we can obtain p-cycles with a maximal number of straddling links. But for the reasons mentioned above our solution find p-cycles of different number of straddling links according to the state of network.

III. Proposed Heuristic Approach

We model the WDM optical network as an undirected graph G =(V, E) where each node in V represents an optical switch and each edge in E represents a network link. Each link has w j working wavelength channels. A pcycle i of a capacity n i can protect n i wavelengths on any on-cycle link of the p-cycle and 2×n i wavelengths on any straddling link of the p-cycle.

Algorithm of P-cycle generation

Our algorithm of generation of p-cycles has two steps. In the first step, the set of shortest cycles is generated. In the second step, we generate high efficiency p-cycles will be directly used to protect the network. Our generation of high efficiency p-cycles is based on incremental aggregation of shortest cycles.

Step 1:

The first step consists of generating all shortest cycles in the graph. A shortest cycle is an elementary cycle without a straddling link. The basic rule to generate such cycles is as follows: for each link X, we find the shortest path between the end nodes of X in G that is different than X. Then we combine the path found with X to create a shortest cycle. When this step finish we delete all redundant shortest cycles. Fig. 3: Shortest cycles After having found the set of shortest cycles, we try to simplify the graph with deleting the parts of graph which contain shortest cycles which cannot be improved. In other words, we delete the shortest cycles that will not have the straddling links. To perform this operation, we delete the shortest cycles that do not share any link with other cycles in the graph. The deleted shortest cycles will be put in the final set of p-cycles that protects network. Step 2:

At the end of the first step, we obtain a simplified graph including only shortest cycles which could be improved. The second step starts in order to generate a set of high efficiency p-cycles. Our solution is based on the incremental aggregation of the shortest cycles, which consists in choosing a shortest cycle and by according rules described below we aggregate it with another cycle in order to obtain an efficient p-cycle.

At the beginning of our algorithm, we choose a cycle that has a link with a minimal working capacity w j among all shortest cycles in the network such that w j is greater than 0. We call the chosen cycle Cyc. Then, we try to aggregate Cyc with another shortest cycle Cyc i . The aggregation is possible if Cyc i shares one and only one link with Cyc and no nodes are shared between them except the end nodes of the shared link. The third condition is the value of redundancy 3 after aggregation of Cyc and Cyc i should be less than the redundancy before aggregation. After the aggregation we obtain one cycle that has one additional straddling link, and which can detours n i wavelengths along the cycle at the same time (n i take a value of link with a minimal working capacity w j ). The cycle obtained becomes the new Cyc that will be used in the next iteration. The process of aggregation continues until, one of the last conditions is violated. When the construction of efficient p-cycle is completed, the working capacities protected by this efficient p-cycle are removed.

The process of construction of p-cycles is repeated until all working capacity is protected or there are no more wavelengths in the network to construct p-cycle. Fig. 4 Graph simplificat 3 The redundancy can be defined as total spare capacity divided by total working capacity ion 4. Remove the working capacity protected by Cyc (we remove n i wavelengths on any on-cycle link of the p-cycle and 2×n i wavelengths on any straddling link of the p-cycle).

5. If there are working capacities unprotected then go to 2.

6. End.

IV. Simulation Results and Analysis

In this section we evaluate our proposed algorithm in terms of redundancy and in terms of the size of final set of p-cycles that protect network. The network topology that we used to evaluate the performance of our solution is 28-node, 45-link USA long haul network taken from [START_REF] Liu | Finding good candidate cycles for efficient p-cycle network design[END_REF]. The working capacity in each link of network is obtained by routing the demand matrix over the shortest path. We assume each node in the network has full wavelength conversion capability. The test network is shown in Fig. 6.

Fig. 6 Test network

We first test the performance of resources utilization (redundancy) for CIDA and for our algorithm in the above network. The redundancy can be defined as the total spare capacity divided by the total working capacity. Smaller value of redundancy means better performance of resource utilization. We can see that the value of redundancy in our solution is always less than 100%. The reason for this is that our solution generates p-cycles by taking into account the state of the network. This enables us to construct only pcycles that have small value of redundancy.

Since the number of p-cycles in the final set that protect network is an important performance for a configuration of WDM network. We also test the number of p-cycles used to protect the network. Smaller number of p-cycles in the final set of p-cycles means better performance Simulation results of the number of p-cycles in the final set that protect network are summarized in Fig. 8. We can see that our solution protects network with a small number of p-cycles. The reason for this is that in our algorithm the p-cycles generated can detour n i wavelengths along the cycle at the same time. But in CIDA all pcycles detour one and only one wavelength along the cycle at the same time.

V. Conclusion

In this paper, we have addressed the protection in WDM optical networks using p-cycles. We have treated the problem of finding an optimal set of p-cycles that protect the optical network for a given working capacity. We have proposed a heuristic solution based an incremental aggregation of shortest cycle. Our generation of p-cycles takes into account the state of the network. This enables us to have a good value of redundancy and a very small number of p-cycles that protect network. The simulation has shown that the redundancy obtained by our heuristic algorithm is always less than 100%, and the number of p-cycles generated by our algorithm is very small than the number of p-cycles generated by CIDA.

  Fig. 1 : p-cycles example

Figure. 4

 4 Figure.4 (b) shows the simplified graph obtained after removing the shortest cycles that are not improvable.

Figure. 5 (Algorithm 1 . 3 .

 513 Figure.5 (a) shows an optical network state after protecting some links. Figure.5 (b), (c), (d) shows the different phases of high efficiency p-cycle construction process. We can see in Fig.5(d) that the aggregation is not possible because the third condition is not verified (the value of redundancy after aggregation should be less than the redundancy before aggregation). The p-cycle generated in phase (c) can detour 2 wavelengths along the cycle at the same time. The table shown in Fig.5(g) contains some p-cycles which protect some links of network.

Fig. 5

 5 Fig. 5 High efficiency p-cycle construction process

Fig. 7

 7 Fig. 7 Simulation comparing CIDA and our algorithm

Fig. 8

 8 Fig. 8 Number of p-cycles selected to protect network

In the ring protection, the traffic on the failed link is rerouted around the ring on the protection fibers between the nodes adjacent to the failure.

On-cycle is a link that belong to the cycle