Introduction

Transport technologies such as Synchronous Digital Hierarchy (SDH/SONET) and Asynchronous Transfer Mode (ATM) becames increasingly speed-limited and can no longer respond to the demand for high bandwidth services (HDTV, video conferencing, electronic banking, multimedia applications, etc). They, through employing optical fiber, do not realize the full potential of the optical medium. The speed of these technologies are limited to few tens of Gbps du to the peak electronic speed of the network components, wheres a single mode fiber can carry data at very highest speeds. In order to increase the bandwidth of optical fiber, Wavelength division multiplexing (WDM) technology is evolved. It is a promising technology to effectively utilize the enormous bandwidth of optical fiber.

In wavelength division multiplexing technology the transmission spectrum of a fiber link can be divided into many protocol transparent channels. Multiple channels can be operated in a single fiber simultaneously at different wavelengths, providing for each channel the bandwidth that is compatible with current electronic processing speeds. These channels can be independently modulated to accommodate dissimilar data formats at various bit rates if necessary. By utilizing WDM in optical networks, we can achieve link capacities on the order of Tbps.

WDM networks are rapidely evolved as a powerfull class of networks for use in wide area networks. These networks consist of optical switches that route a signal based on the identity of the input port (i.e. related overlying service) and the wavelength of the incoming signal. A WDM network is called also wavelength routed network [START_REF] Ramaswami | Multiwavelength lightwave networks for computer communication[END_REF] [START_REF] Ramaswami | Optical networks: a practical perspective[END_REF] since it employs wavelength routing technique. Access switches and end switches provide the electronic-to-optical conversion and vice versa to interface the optical network with electronic stations. Wavelength routing provides the network with the ability to identify and localize the traffic flow, thereby allowing the same wavelength to be reused in spatially disjoint segments of the network. In order to carry data from one access node to another, a connection needs to be set up at the optical layer similar to the case in a circuit-switched networks. This operation is performed by determining a path in the network connecting the source node to the destination node and by allocating a single free wavelength on all of the fiber links in the path. Such an all-optical path is referred as lightpath [START_REF] Chlamtac | Lightpath communications: An approach to high bandwidth optical wan's[END_REF] [START_REF] Ramaswami | Optical networks: a practical perspective[END_REF], each lightpath can carry data at peak electronic speed. However, practical limitations on the transmission technology and optical devices restrict the number of available wavelengths per fiber link, it is unlikely that a lightpath can be established between every pair of access nodes. The intermediate nodes in the path route the lightpath in the optical domain using wavelength-sensitive switches. A fundamental constraint in a wavelength-routed optical network is that two or more lightpaths traversing the same fiber link must be on different wavelengths so that they do not interfere with one another. A wavelength-routed network, which carries data from one access station to another without any intermediate opticalto-electrical conversion is referred as an all-optical wavelength-routed network. All-optical wavelength-routed networks will be the subject of our work. These networks have several benifits like the potential to accommodate the rapidly increasing bandwidth, improved network reliability, simpler network management, and are independent from modulation format and bit rate [START_REF] Cochrane | The hidden benefits of optical transparency[END_REF] [START_REF] Ramaswami | Optical networks: a practical perspective[END_REF].

Since the lightpaths are the basic switched entities of a wavelength-routed WDM network, their effective establishment and usage are crucial. Thus, it is important to propose efficient algorithms to select the routes for the requested connections and to assign wavelengths on each of the links along these routes. This is known as the routing and wavelength assignment problem. The routing and wavelength assignment problem (RWA) in optical networks considers a network where requests (i.e. lightpaths) can be transported on different optical wavelengths through the network. Each accepted request is allocated a path from its source to its sink, as well as a specic wavelength. Lightpaths routed over the same link must be allocated to different wavelengths, while lightpaths whose paths are link disjoint may use the same wavelength. Lightpaths that cannot be established due to constraint on wavelengths availability are said to be blocked.

Litterature Survey

Several works have studied the RWA problem in all-optical WDM networks and various contributions have been made through interesting algorithms. The problem consider a directed network G = (V, E) where V is the set of nodes representing the switches of the physical network and E is the set of edges representing the fiber links of the physical network. Given a set of requests for all-optical connections or lightpaths between nodepairs and a set of available wavelengths, the problem is to find routes from the source nodes to their respective destination nodes and assign wavelengths to these routes.

The RWA problem in WDM networks can be categorized into two types based on traffic arrivals.

(1) Static Lightpath Establishment (SLE) : The traffic is static and the set of connection requests is known in advance. This kind of problem pertains to the planning phase of the WDM network. The algorithms proposed for solving the static RWA problem are referred to as Offline algorithms. Static RWA is known to be an NP-hard optimization problem [START_REF] Chlamtac | Lightpath communications: An approach to high bandwidth optical wan's[END_REF] since it is considered as a special case of the integer multicommodity flow (MCF) problem [START_REF] Leighton | Fast approximation algorithms for multicommodity flow problems[END_REF] [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF] with additional specific constraints and can be formulated as an integer linear program (ILP).

(2) Dynamic Lightpath Establishment (DLE) in the case of dynamic traffic : The traffic is dynamic and the connection requests arrive sequentially, one by one, at random times over an infinite time horizon. The DLE problem is posed in the operational phase where each network resource must be managed efficiently. The algorithms proposed for solving the dynamic RWA problem are referred to as Online algorithms. A review on dynamic RWA algorithms can be found in [START_REF] Zang | Dynamic lightpath establishment in wavelength routed wdm networks[END_REF].

In our study we will focus on the static RWA problem and the offline algorithms that proposed in litterature to solve this kind of problem. Offline RWA is more difficult than online RWA since it aims at jointly optimizing the lightpaths used by the connections in the same way that the multicommodity flow problem is more difficult than the shortest-path problem in general networks. We classify the previous works in three classes. For each class we discuss the already proposed algorithms and the adopted approaches.

2.1. Joint RWA ILP-based algorithms. Many ILP-based formulations have been proposed in litterature for routing and wavelength assignment problems jointly. [START_REF] Jaumard | Ilp formulations for the routing and wavelength assignment problem: Symmetric systems[END_REF] provides different ILP formulations (path-based, edge-based and arc-based formulations). The authors proposed a synthesis of the mathematical models for symmetrical systems where bandwidth requirements are similar on the downstream and upstream directions. Several objectives have been considered: (a) minimizing the blocking rate or maximizing the number of accepted requests given a fixed number of available wavelengths, (b) minimizing the number of used wavelengths assuming that all connection requests can be accepted, (c) minimizing the congestion that is expressed through the minimization of the maximum number of wavelengths on a given fiber link, (d) minimizing the network load defined as the ratio of used wavelengths over the overall potential number of wavelengths. A continuous relaxations have been also proposed. The authors of [START_REF] Cavendish | Routing and wavelength assignment in wdm mesh networks[END_REF] developed an ILP model for RWA problem using other optimization criteria like minimizing the number of wavelength conversions or minimizing the hop count. [START_REF] Simonis | Solving the static design routing and wavelength assignment problem[END_REF] proposed two direct RWA ILP formulations : basic formulation in which the aim is to minimize the maximum number of wavelengths per fiber link, and extended formulataion that try to minimize the overall number of used wavelengths. A source aggregation is considered to reduce the number of constraints and improve the two mathematical models. In [START_REF] Jaekel | New techniques for efficient traffic grooming in wdm mesh networks[END_REF], the authors proposed a new formulation that addresses the complete trafc grooming problem, including topology design as well as routing and wavelength assignment (RWA) of lightpaths. In Other works, the authors used some efficient techniques in order to scale their RWA ILP formulations to problem instances encountered in practice. A link selection techniques were considered in [START_REF] Liu | Link selection algorithms for link-based ilps and applications to rwa in mesh networks[END_REF] to reduce the size of the link-based formulation in terms of both the number of variables and the number of constraints. Column Generation technique was also used in [START_REF] Jaumard | On column generation formulations for the rwa problem[END_REF] [START_REF] Lee | An optimization approach to routing and wavelength assignment in wdm all-optical mesh networks without wavelength conversion[END_REF] to improve the RWA formulation. In [START_REF] Liu | A fast path-based ilp formulation for offline rwa in mesh optical networks[END_REF], the authors demonstrated that their new path-based formulation achieves a decrease of up to two orders of magnitude in running time compared to existing formulations. Since the majority of proposed ILP were very hard to solve, a corresponding relaxed linear programs have been used to get bounds on the optimal value that can be achieved. As an example, The LP-relaxation formulation proposed in [START_REF] Ozdaglar | Routing and wavelength assignment in optical networks[END_REF], and also considered in [START_REF] Christodoulopoulos | Comparison of routing and wavelength assignment algorithms in wdm networks[END_REF], is able to produce exact RWA solutions in many cases, despite the absence of integrality constraints. In [START_REF] Christodoulopoulos | Offline routing and wavelength assignment in transparent wdm networks[END_REF], the authors presented an algorithm for solving the static RWA problem based on a LP-relaxation formulation that provides integer optimal solutions despite the absence of integrality constraints for a large subset of RWA input instances. The RWA formulation was then extended in order to take into consideration the physical layer impairments and account for the interference among lightpaths. Iterative fixing and Rounding techniques have been also used to provide an integer solution for the relaxed problem.

2.2.

RWA decomposition-based algorithms. Another known approach in litterature is to break the RWA problem in the two constituent subproblems and solves them individually and sequentially. This approach consists on two steps, by first finding routes for all requested connections and secondly searching for appropriate wavelength assignment [START_REF] Zang | A review of routing and wavelength assignment approaches for wavelength-routed optical wdm networks[END_REF] [START_REF] Stern | Multiwavelength optical networks: A layered approach addison-wesley[END_REF]. Note that both subproblems are NP-hard: The routing subproblem for a set of connections corresponds to a multicommodity flow problem, while wavelength assignment corresponds to a graph coloring problem. Several works have been adopted a decomposition-based algorithms. In [START_REF] Simonis | Solving the static design routing and wavelength assignment problem[END_REF] [2] [START_REF] Christodoulopoulos | Comparison of routing and wavelength assignment algorithms in wdm networks[END_REF], the authors choose a decomposition technique which handles the first step with a ILP program which assigns paths to the demands while minimizing the maximal number of demands routed over a link. The second step is expressed as a graph coloring problem where the nodes are demands and disequality constraints (links) are imposed between any two demands which are routed over the same link. The final solution is an approximate solution of the original complete RWA problem taht can be not optimal. Works [START_REF] Banerjee | A practical approach for routing and wavelength assignment in large wavelength-routed optical networks. Selected Areas in Communications[END_REF] [9], formulated the routing sub-problem as a continuous multicommodity flow problem and applied a randomized rounding technique to provide an integer solution in which the objective function takes on a value close to the optimum of the rational relaxation. A performance comparison between a RWA ILP-based algorithm and a decomposition-based algorithm was made in [START_REF] Christodoulopoulos | Comparison of routing and wavelength assignment algorithms in wdm networks[END_REF]. However, [START_REF] Zang | A review of routing and wavelength assignment approaches for wavelength-routed optical wdm networks[END_REF] synthesized a lot of known approaches for resolving the routing sub-problem. Fixed routing, fixed-alternate routing and adaptative routing were described. Ten dynamic wavelength assignment heuristics were also discussed. the authors said that these heuristics may also be applied to the static wavelength assignment problem by ordering the lightpaths and then sequentially assigning wavelengths to the ordered lightpaths. Note that all the proposed decomposition techniques, previously cited, suffer from two major drawbacks: [START_REF] Ahuja | Network Flows[END_REF] The approximate solution, obtained as a result of the problem decomposition, is often not optimal (2) The optimal solution of the joint RWA might not be included in the solutions provided by the algorithms used for the two subproblems.

2.3. RWA heuristics. For static lightpath establishment (SLE), several heuristic algorithms have been proposed for establshing a maximum number of lightpaths from a given set of request [START_REF] Ganz | Efficient algorithm for virtual topology design in multihop lightwave networks[END_REF] [26] [START_REF] Zhang | A heuristic wavelength assignment algorithm for multihop wdm networks with wavelength routing and wavelength re-use[END_REF]. However, most of these old algorithms are based on traditional circuit-switched networks where routing and wavelength assignment steps are decoupled. Several recent studies have been focused on solving the joint RWA problem by sophisticated heuristics. In [START_REF] Siregar | Efficient routing and wavelength assignment in wavelength-routed optical networks[END_REF][START_REF] Kumar | Static lightpath establishment in wdm networksnew ilp formulations and heuristic algorithms[END_REF][START_REF] Chen | On hierarchical traffic grooming in wdm networks[END_REF][START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF], a lot of proposed heuristics were presented and evaluated. In the following, we summarize and describe the most known heuristics used for solving the joint RWA problem.

• Shortest First Fixed Path (SFFP) [START_REF] Kumar | Static lightpath establishment in wdm networksnew ilp formulations and heuristic algorithms[END_REF]: M. shiva Kumar used wavelength-graph or layered-graph to find routes and wavelengths for the given lightpath set. In the layered graph model the physical network G = (V, E) is replicated |W| times, each sub graph G = (V λ , E λ ), λ ∈ W corresponding to the given physical network on a particular wavelength. The objective here was to maximize the network throughtput. The heuristic algorithm finds the shortest path for all the given node-pairs by using Dijkstra's algorithm in the given physical network topology. Then the requested connections are arranged in non-decreasing order of their path lengths. Now heuristic algorithm routes lightpaths sequentially on the wavelength-graph in a single layer with the shortest path. If a route is found with finite cost, then the lightpath is established, and the wavelength-graph is updated by assigning infinite cost to the edges along which the request is routed. If a route with minimum cost is not found for a node pair then the request is skipped, and the next request from the sorted list is considered. In the second phase the algorithm finds the shortest available path on the residual wavelength-graph for the lightpath requests that were skipped in the first phase. Thus by assigning a wavelength to the shortest path first maximizes the number of lightpaths established, which is equivalent to maximizing the network throughput.

• Longest First Fixed Path (LFFP) or Longest-path First [7] [35]: In this heuristic, wavelengths are assigned to the longest lightpath first. A comparison with SFFP was made in [START_REF] Kumar | Static lightpath establishment in wdm networksnew ilp formulations and heuristic algorithms[END_REF] based on the number of established lightpaths. The results showed that The number of lightpaths established by SFFP is more after a certain size of the lightpath request set. However, the average fiber utilization obtained by LFFP is more when compared to SFFP. This is because, by establishing long lightpaths first, would result better wavelength reuse.

• Minimum Number of Hops (MNH) [START_REF] Baroni | On the number of wavelengths in arbitrarily-connected wavelength-routed optical networks[END_REF] [35]: Baroni and Bayvel proposed an MNH algorithm for minimizing the maximum load per link in arbitrarily connected networks. In MNH, each node-pair of the given set of connection requests is firstly assigned one of its shortest paths. Then, alternate shortest paths are examined for a possible better path and the previously assigned path will be replaced by the alternate path if the load of the most congested link is reduced. This process is repeated for all the node-pairs and stops when no subtitutions are possible. Results in [START_REF] Siregar | Efficient routing and wavelength assignment in wavelength-routed optical networks[END_REF] showed that the MNH provided a more efficient routing with a minimum number of used wavelengths than LFFP.

• Longest First Alternate Path (LFAP) [6] [35]: In LFAP, the RWA problem is formulated as a knapsack problem. Wavelengths are treated as knapsacks, each of which can hold more than one lightpath. Lightpaths are treated as items and more than one lightpath can share the same wavelength on condition that no two lightpaths pass through the same link. The LFAP algorithm assigns a wavelength to a longer lightpath with higher priority and attempts to maximize the number of lightpaths per wavelength. More precisely, wavelengths are added one by one until all the lightpaths for the given set of requests are established. For each newly added wavelength, the longest lightpath among those of the given requests is established. Then, the shorter lightpaths will be checked one by one. If no lightpath can be established, alternate paths are searched. If no lightpath can be established any more, a new wavelength will be added and the searching process is repeated. After establishing each lightpath, the network topology is modified by removing the links used by the newly established lightpath. The results in [START_REF] Siregar | Efficient routing and wavelength assignment in wavelength-routed optical networks[END_REF] showed that the performance (i.e. number of wavelengths required) of LFAP is much better than LFFP and MNH. However, LFAP spends more time than LFFP in order to provide solution.

• Heaviest Path Load Deviation (HPLD) [START_REF] Siregar | Efficient routing and wavelength assignment in wavelength-routed optical networks[END_REF]: In HPLD, the RWA problem is formulated as a routing problem where the link cost is determined based on the load (utilization) of each link. The HPLD algorithm attempts to re-route some lightpaths that pass through the heaviest link in order to minimize the number of wavelengths. More precisely, HPLD algorithm search to deviate the load of the most loaded link to other less loaded path so that the maximum number of wavelengths used in the network is reduced. That is, the HPLD algorithm tries to re-route some lightpaths that pass through the heaviest link. The HPLD algorithm employs the shortest path routing technique to solve this problem based on the network graph.

The weight function of a link (link cost) is determined by the link load. The results in [START_REF] Siregar | Efficient routing and wavelength assignment in wavelength-routed optical networks[END_REF] showed that HPLD is a bit more efficient than LFAP in term of the number of used wavelengths. However, it needs more time than LFAP to find a feasible solution.

Note that the four first following heuristics were developed by applying classical bin packing algorithms [START_REF] Karmarkar | An efficient approximation scheme for the one-dimensional bin-packing problem[END_REF]. Lightpath requests represented items, while copies of graph G represented bins. Each copy of G, referred to as bin G i , i = 1, . . . , |W |, corresponds to one wavelength. The authors in [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF] showed that their heuristics were tested on a series of large random networks and compared with an efficient previous algorithm for the same problem. Results indicated that the proposed algorithms yield solutions signicantly superior in quality, not only with respect to the number of wavelength used, but also with respect to the physical length of the established lightpaths.

• First Fit (FF-RWA) [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF], called also Greedy-EDP-RWA in [START_REF] Manohar | Routing and wavelength assignment in optical networks from edge disjoint path algorithms[END_REF] based on the boundedlength greedy algorithm for Edge-Dijoint Paths problem: First, only one copy of G, bin G 1 , is created. Higher indexed bins are created as needed. Lightpath requests (s j , d j ) are selected at random and routed on the lowest indexed copy of G in which there is place (i.e. room). Bin G i is considered to have room for lightpath (s j , d j ) if the length of the shortest path from s j to d j in G i , denoted as P i j , is less than H. If a lightpath is routed in bin Gi, the lightpath is assigned wavelength i and the edges along path P i j are deleted from G i . If all the edges from bin G i are deleted, the bin no longer needs to be considered. If no existing bin can accommodate lightpath request (s j , d j ), a new bin is created.

• Best Fit (BF-RWA) [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF]: BF-RWA routed lightpaths in the bin into which they t "best". The algorithm considered the best bin to be the one in which the lightpath can be routed on the shortest path. In other words, if at some point in running the algorithm, there are B bins created, bin G i ,1 ≤ i ≤ B , is considered to be the best bin for lightpath (s j , d j ) if l(P i j ) ≤ l(P k j ), for all k = 1, . . . , B, and k = i. This is not necessarily the overall shortest path, SP j , since it is possible that none of the existing bins have this path available. If there is no satisfactory path available in any of the B bins (i.e. l(P i j ) > H, for i = 1, . . . , B), a new bin is created. The motivation for the "best fit" approach described above, is not only to use less wavelengths, but also to minimize the physical length of the established lightpaths

• First Fit Decreasing (FFD-RWA) [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF]: FFD-RWA algorithm sorts the lightpath requests in non-increasing order of the lengths of their shortest paths, SP j , in G.

Lightpaths with shortest paths of the same length are placed in random order. The algorithm then proceeds as FF-RWA. The motivation for such an approach is as follows. If the connection request with the longest shortest path is considered rst, it will be routed in "empty" bin G 1 . This means the lightpath will not only successfully be routed in G 1 , but will be routed on its overall shortest path. After deleting the corresponding edges from bin G 1 , the remaining edges can be used to route "shorter" lightpath requests which are easier to route on alternative routes that are satisfactory (i.e. shorter than H). In other words, the FFD-RWA algorithm rst routes "longer" lightpaths which are harder to route, and then lls up the remaining space in each bin with "shorter" lightpaths. This may lead to fewer wavelengths used.

• Best Fit Decreasing (BFD-RWA) [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF]: BFD-RWA algorithm sorts the lightpath requests in non-increasing order of the lengths of their shortest paths SP j in G, and then proceeds as BF-RWA. The obtained results in [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF] showed that BFD-RWA provided more better solution (i.e. number of required wavelengths) than the three other algorithms.

• A weight based Edge Dijoint Path (WEDP) algorithm has been also proposed in [START_REF] Shekhawat | Weight based edge disjoint path routing and wavelength assignment (wedp-rwa) algorithm for wdm networks[END_REF] to solve the RWA problem. The authors showed that WEDP performed better than a greedy MEDP algorithm used for solving the same problem. M RCL

The Table 1 summarizes all the previous described works. Note that we illustrate only static/offline RWA cases.

Minimization of the number of lighpaths

Given a set of traffic demands, our goal is to minimize the number of new lighpaths to be created in the optical network for supporting these demands. We address this problem by considering only the edge nodes of the Optical Transport Network (OTN). We view a lighpath between nodes u and v as a directed edge between these nodes, with a certain capacity representing the maximum amount of traffic that a lighpath can accomodate. We assume that the number of lighpath between any two nodes is given by some large integer value K. We show that the problem of minimizing the number of lighpaths can then be formulated as that of routing demands in a multigraph with the goal of minimizing the number of used links. We propose a simple heuristic to solve this problem.

3.1. Problem statement. We consider a network represented by a multidigraph G := (V, E, s, t), where • V is a set of vertices or nodes,

• E is a set of edges or lines,

• s : E → V assigns to each edge its source node,

• t : E → V assigns to each edge its target node. The network is such that there are K edges between any two pairs of nodes, that is the cardinality of the set {e ∈ E : s(e) = i, t(e) = j} , is K for all i, j = i in V . An example of such a network is shown in Figure 1. It is assumed that the capacity of each edge e ∈ E is C units of bandwidth. We are given a set D of traffic demands that have to be routed in the network. For each demand d ∈ D, we let λ d be the traffic volume of demand d, s d its source node and t d its destination node. Traffic demand d ships its flow by splitting its demand λ d over a set of paths Π(d). We assume that the set Π(d) contains all simple path between s d and t d . Since the network is symmetric, the number of paths is the same for all demands and it will be denoted by S in the following. Let x d,π denote the amount of trafic sent by demand d over path π. A routing strategy for demand d ∈ D is a vector

x d = (x d,π ) π∈Π(d) in IR S + such that π∈Π(d) x d,π = λ d .
We let X d denote the set of all routing strategies for demand d:

X d =    x d ∈ IR S + : π∈Π(d) x d,π = λ d    .
The vector x = (x d ) d∈D will be called a routing strategy. It belongs to the product strategy space X = d∈D X d . For each edege e ∈ E, we define the function y e : X → IR + by

y e (x) = d∈D π∈Π(d) δ π e x d,π .
where δ π e = 1 if e ∈ π, and 0 otherwise. In other words, y e (x) represents the amount of traffic flowing through link e under strategy x. A routing strategy is feasible if y e (x) ≤ C for all links e. In the following, we say that link e is used under strategy x if and only if y e (x) > 0.

We wish to find a feasible routing strategy which minimizes the number of used links. This amounts to solving the following optimization problem:

minimize v(x) = e∈E 1 {ye(x)>0} (OPT) subject to x ∈ X , y e (x) ≤ C, ∀e ∈ E.
It is immediate to see that problem (OPT) can be formulated as the following integer programming problem: In the following, we shall assume that K is sufficiently large for the above problem to have a feasible solution. More precisely, we shall assume that

K ≥ d λ d C .
We note that problem (OPT-LP) involves binary variables and is thus difficult to solve. We propose in the following section a simple successive approximation heuristic to find an approximate solution.

3.2. Successive approximation heuristic. Before describing the successive approximation algorithm in Section 3.2.2, we first establish in Section 3.2.1 some results regarding the optimal routing strategy of a single demand when the routing strategies of the other demands are given.

3.2.1.

Optimal routing strategy for a single traffic demand. Denote by x -d the vector (x f ) f =d , that is the routing strategy obtained by routing all traffic demands but demand d. It is assumed that this routing strategy is fixed and feasible. It can be viewed as a partial solution to problem (OPT). Define E -as the set of links that are used under strategy x -d , that is

E -= {e ∈ E : y e (x -d ) > 0} ,
and define E + as E + = E \ E -. We do not make explicit the dependance on d in order to simplify notations. Let c e = Cy e (x -d ) be the residual capacity for demand d on link e. The minimum-cost solution that can be obtained from the partial solution x -d is then obtained by solving the following optimization problem:

minimize v d (x d ) = e∈E + 1 {ye(x d )>0} (OPT-d) subject to x d ∈ X d , y e (x d ) ≤ c e , ∀e ∈ E.
As before, we note that the above problem can be formulated as a mixed linear programming problem:

minimize e∈E + β e (OPT-d-LP) subject to z e ≤ C.β e , ∀e ∈ E + , z e ≤ c e , ∀e ∈ E -, z e = π∈Π(d) δ π e x d,π , ∀e ∈ E, π∈Π(d) x d,π = λ d , x d,π ≥ 0, ∀π ∈ Π(d), z e ≥ 0, ∀e ∈ E, β e ∈ {0, 1}, ∀e ∈ E.
In the following, we denote by x * d an optimal solution of problem (OPT-d). Proposition 1 gives an explicit expression for the cost of such an optimal routing strtategy.

Proposition 1. The optimal value of problem (OPT-d) is v d (x * d ) = λ d -λ (E -) C ,
where λ (E -) is the optimal value of the following linear program:

maximize λ (Max-Flow) subject to z e ≤ c e , ∀e ∈ E -, z e = π∈Π(d) δ π e x d,π , ∀e ∈ E -, π∈Π(d),π⊂E - x d,π = λ, λ ≤ λ d , x d,π ≥ 0, ∀π ∈ Π(d), π ⊂ E - z e ≥ 0, ∀e ∈ E -, Proof. Let n = λ d -λ(E -) C
. The proof is in two parts. We first show that for each routing strategy x d ∈ X d such that y e (x d ) ≤ c e , ∀e, we have v d (x d ) ≥ n. We then prove that there exists a routing strategy for demand d whose cost is n. Consider a solution x d ∈ X d such that y e (x d ) ≤ c e , ∀e. Let α = π∈Π(d),π⊂E -x d,π be the amount of traffic routed on paths in the subgraph (V, E -). By definition of λ (E -), we have α ≤ λ (E -). Since ye(x d ) C ≤ 1 for all e ∈ E + , we have

v(x d ) = e∈E + 1 {ye(x d )>0} , = e∈E + y e (x d ) C , ≥     1 C e∈E + y e (x d )     . However e∈E + y e (x d ) = e∈E + π∈Π(d) δ π e x d,π = π∈Π(d)   e∈E + δ π e   x d,π ≥ π∈Π(d),π∩E + =∅ x d,π ≥ λ d -α, from which we obtain v(x d ) ≥ λ d -α C ≥ λ d -λ (E -) C = n.
We thus conclude that any feasible solution to (OPT-d) has a cost greater than or equal to n.

We now turn to the second part of the proof. Let x - d be the optimal solution of problem (Max-Flow). If n = 0, i.e., if λ (E -) = λ d , then the routing strategy x * d defined by

x * d,π = x - d,π if π ⊂ E -, 0 otherwise.
is clearly an optimal solution to (OPT-d). Otherwise, choose arbitrarily n edges e 1 , . . . , e n ∈ E + such that s(e k ) = s d and t(e k ) = t d for k = 1, . . . , n and let π k be the path π k = {e k } for k = 1, . . . , n. Consider the routing strategy x * d ∈ X d defined as follows:

x * d,π =      x - d,π if π ⊂ E -, λ d -λ(E -) n π = π 1 , . . . , π n 0 otherwise.
We clearly have x * d,π ≥ 0 for all paths π ∈ Π(d). Moreover, We note that the second part of the proof of Proposition 1 provides an algorithm to find an optimal solution to problem (OPT-d):

π∈Π(d) x * d,π = π∈Π(d),π⊂E - x * d,π + n k=1 x * d,π k , = λ E -+ λ d -λ E -, = λ
Step 1. Solve Problem (Max-Flow) in order to find the value of λ (E -) and the amount of traffic to be routed on each path π between s d and t d in the subgraph (V, E -). We note that the structure of this problem is that of a standard maximum flow problem, for which very efficient algorithms are known [START_REF] Ahuja | Network Flows[END_REF].

Step 2. Choose arbitrarily

n = λ d -λ(E -) C
edges in E + between s d and t d , and split evenly the traffic λ dλ (E -) among these links.

3.2.2. Successive approximation algorithm. The successive approximation algorithm is described in Figure 2. At each iteration, this algorithms routes optimally a single traffic demand assuming the routing strategies of the other demands are fixed. The algorithm stops when it is no more possible to decrease the number of used links by re-routing a single traffic demand.

Lemma 1. The successive approximation algorithm converges in a finite number of steps.

Proof. Define a round to be a sequence of iterations of the algorithm in which each traffic demand is rerouted exactly once (Steps 4-19 in Figure 2). Once an order is fixed in the first round, it is assumed to be the same in each subsequent round (the order in which the traffic demands are routed in the first-round can be arbitrary). Observe that if the algoritm does not stop at the end of a round, then the number of used links at the end of the round is lower by at least one than the number of used links at the end of the previous round. Hence, the number of used links at the end of each round is a strictly decreasing sequence. Since this number has to be positive, the algorithm converges in a finite number of rounds.

3.3.

Experiments and results. In this section, several experiments on the optimization problem for traffic routing were performed in order to evaluate and validate the effectiness of the proposed solutions. The CPLEX solver, from IBM-ILOG society, is used for solving the integer linear program (OPT-LP). The aim of the experiments here is to analyze the performance and compare the proposed methods. The comparison is performed between the ILP-based algorithm (OPT-LP) and the successive approximation algorithm illustrated in Fig. 2.

In the following sections, the performance comparison between the algorithms is done based on three criteria. The first and second ones are related to the computation time and the memory consumption, respectively. The third one represents the routing strategy cost, which reflects the number of used links for the routing of all demands.

Require: G := (V, E, s, t), C, D

E -← {e ∈ E : y e (x -d ) > 0}, E + ← E \ E - 7
:

c e ← C -y e (x -d ), ∀e ∈ E 8:
x * d ← 0

9:

Compute λ (E -) and x * d,π for all π ⊂ E -by solving (Max-Flow)

10: n = λ d -λ(E -) C 11:
for k = 1 . . . n do 12:

Choose arbitrarily edge ℓ ∈ E + such that s(ℓ) = s d and t(ℓ) = t d 13:

x * d,{ℓ} = (λ dλ (E -))/n

14:

E + ← E + \ {ℓ}, E -← E -∪ {ℓ} 15:
end for 16:

if n < v(x) -v(x -d ) then 17:
Convergence = false 18:

x d ← x * d 19:
end if

20:
end for 21: end while Figure 2. Successive approximation algorithm.

Computation Time.

To evaluate the computation time for both ILP-based algorithm and successive approximation algorithm, several topologies, with different sizes, are considered for simulations. In each simulation, the two algorithms are executed on the same topology and for the same set of demands which are randomly generated. Table 2 illustrates the obtained results for each topology size. For the last three simulations, the execution of the ILP-based algorithm is stopped before its termination because lack of sufficient RAM memory.

From these results, it can be seen clearly that the successive approximation algorithm is much more faster than the ILP-based one. A routing strategy solution can be found in a few seconds for large topology sizes.

Memory Consumption.

For evaluating the memory consumption related to the two algorithms, the same set of simulations as previous section is considered here. For the last three simulations, the execution of the ILP-based algorithm is stopped before its termination because lack of sufficient RAM memory. The results of simulations are illustrated in As mentionned in the Table 3, important memory consumptions are recorded when solving the routing problem by the ILP-based algorithm. However, the successive approximation algorithm gave a solution with a memory consumption of 40M for a 100-node topology.

Routing Strategy Cost.

The routing strategy cost is equal to the number of used links when solving the routing problem. This value is returned by the objective function in the linear program (OPT-LP) and deduced in the successive approximation algorithm after routing all demands. To compare the quality of routing for the two algorithms, it suffices to compare theirs routing strategies costs. For this comparison, a simplistic topology with 10 nodes is considered. Twenty five Simulations have been performed on this network. For each simulation, both ILP-based algorithm and successive approximation algorithm try to route the same set of demands, which are randomly generated. Figure 3 represents 4 illustrates the relative error between the optimal and approximate solutions.

The obtained results shows that the successive approximation algorithm provides a lower quality of routing that the ILP-based algorithm, but globally acceptable. In fact, as this heuristic iterates through the demands sequentially, it attempts to find optimal solution for each demand without taking into account the impact on following ones in later iterations. Therefore, it may not always reach the performance of the ILP-based algorithm which solves the routing problem for all demands altogether. In this example shown in Figure 4, the average gap, along 25 simulations, between the two solutions is around 7, 92%. Average gaps of 7, 85%, 7, 82% and 7, 78% have been recorded, along 100 simulations, for 10-node, 15-node and 20-node topologies respectively. According to the obtained results, the routing quality ensured by the successive approximation algorithm seems satisfactory compared to the optimal ILP solution, especially if we consider the gain in time computation and memory consumption. The average gap is expressed by simulations (

Solapprox-Solopt Solapprox

) nb simulations These results confirms that the successive approximation algorithm converges in a finite number of iterations.

Routing of Lightpaths and Wavelength Assignment

The routing and wavelength assignment (RWA) problem is an optical networking problem. The general objective of the RWA problem is to maximize the number of established connections.

4.1.

Integer Linear Programming Formulation. We consider an optical transport network represented by an directed graph G := (V, E), where V is a set of vertices or nodes corresponding to the switches of the OTN and E is the set of optical fibers between nodes. We denote by W = {1, . . . , W } the set of wavelengths (or colours) that can be assigned to lighpaths. We are given a set K of lightpaths that have to be routed in the network. Each lighpath request must be given a route and a wavelength. The wavelength must be consistent for the entire path (it is assumed that no wavelength converter is used). Two lighpaths can share the same optical link, provided a different wavelength is used. For each lighpath k ∈ K, we let s k be its source node and t k be its destination node.

For each coulour w ∈ W, we define a layer of the network as a graph G w = (V w , E w ), where each node of V w is obtained by duplicating the corresponding node of V , and each edge of E w is obtained by duplicating the corresponding directed edge in E. We thus have as many network layers as there are possible colours. This is illustrated in Figure 6. We view each network layer as a separate network where each link has capacity 1, so that a single lighpath can be routed ont it. Then, the problem can be formulated as that of routing each lighpath in one and only one network layer.

For all lighpaths k ∈ K and all colours w ∈ W, let us define the following binary decision variables:

(1) (2)

y w k = 1 if lighpath k is assigned coulour w, 0 otherwise,
x e k = 1 if lighpath k is routed on link e, 0 otherwise, for all e ∈ E W . Since each lighpath has to be routed in a single network layer, we clearly have

(3) w∈W y w k = 1, ∀k ∈ K.
Obviously, the links of network layer w are not used by lighpath k if this lighpath is not assigned the colour w, so that (4)

x e k ≤ y w k , ∀e ∈ E w , ∀w ∈ W, ∀k ∈ K. On the contrary, if lighpath k is assigned colour w, then it has to be routed in network layer w. Defining, for each node n ∈ V w , E + w (n) (resp. E - w (n)) as the set of directed edges of E w that are incoming (resp. outgoing) at node n, this routing problem can be expressed using a node-link formulation:

(5)

e∈E + w (n) x e k - e∈E - w (n) x e k =      -y w k n = s k y w k n = t k 0 otherwise.
In each network layer, each link can accomodate at most one lighpath, so that we also have the following constraint:

(6) k∈K x e k ≤ 1, ∀e ∈ E w , ∀w ∈ W.
Constraints ( 4)-( 6) define feasible solutions to the RWA problem. The goal is to minimize the number of used wavelengths, or, equivalently, the number of used network layers. For each colour w, define [START_REF] Chlamtac | Lightpath communications: An approach to high bandwidth optical wan's[END_REF] u w = 1 if colour w is used 0 otherwise.

Since colour w is used if at least one lighpath is assigned to it, we clearly have ( 8)

k∈K y w k ≤ K u w , ∀w ∈ W,
where K is the number of lighpaths. The RWA problem can now be formally defined as an integer linear program (ILP), as shown below. It has been shown that the RWA problem is NP-complete in [START_REF] Chlamtac | Lightpath communications: an approach to high bandwidth optical wan's[END_REF]. The proof involves a reduction to the n-graph colorability problem.

In other words, solving the RWA problem is as complex as finding the chromatic number of a general graph.

minimize w max (RWA) subject to w u w ≤ w max , ∀w ∈ W,

k∈K y w k ≤ K u w , ∀w ∈ W, k∈K x e k ≤ 1, ∀e ∈ E w , ∀w ∈ W, e∈E + w (s k ) x e k - e∈E - w (s k ) x e k = -y w k , ∀k ∈ K, ∀w ∈ W, e∈E + w (t k ) x e k - e∈E - w (t k )
x e k = y w k , ∀k ∈ K, ∀w ∈ W,

e∈E + w (n) x e k - e∈E - w (n)
x e k = 0, ∀n = s k , t k , ∀k ∈ K, ∀w ∈ W,

x e k ≤ y w k , ∀e ∈ E w , ∀w ∈ W, ∀k ∈ K, w∈W y w k = 1, ∀k ∈ K, x e k ∈ {0, 1}, ∀e ∈ E w , ∀w ∈ W, ∀k ∈ K, y w k ∈ {0, 1}, ∀w ∈ W, ∀k ∈ K, u w ∈ {0, 1}, ∀w ∈ W, w max ≥ 0.
We note the following property of optimal solutions of the above problem.

Lemma 2. Let (x, y, u, w max ) be an optimal solution of problem (RWA). Then

(9) k∈K y w k ≥ 1, ∀w ≤ w max ,
Proof. Assume on the contrary that there exists q < w max such that k∈K y q k = 0. Then it is easy to see that we can define another feasible solution (x, ŷ, û, q) such that all lighpaths routed in network layer w max are now routed in network layer q (with exactly the same path), while the routes of the other lighpaths are the same in both solutions. The new solution uses w max -1 network layers, which implies that (x, y, u, w max ) is not an optimal solution, i.e., a contradiction. We observe that, given a routing strategy x satisfying ( 5)-( 6), we can easily obtain a feasible solution to the above integer linear program. Indeed, if lighpath k is routed in network layer w, then we can set y w k = 1 and u w = 1. This suggests that the RWA problem can be formulated as a pure routing problem. 4.2. Formulation as an equivalent routing problem. We shall now show that the RWA problem can be equivalently formulated as a pure routing problem. Define the following constants: [START_REF] Christodoulopoulos | Offline routing and wavelength assignment in transparent wdm networks[END_REF] c w = K w-1 , w = 1, . . . , W.

Noting that (K -1)

q w=1 c w = (K -1) q-1 n=0 K n , = q n=1 K n - q-1 n=0 K n , = K q -1,
we see that these coefficients are such that ( 11)

K q w=1 c w < q w=1 c w + c q+1 .
Let us now consider the following optimization problem:

minimize w∈W c w k∈K y w k (EQ-RWA) subject to k∈K x e k ≤ 1, ∀e ∈ E w , ∀w ∈ W, e∈E + w (n) x e k - e∈E - w (n) x e k = h n k (y w k ), ∀n ∈ V w , ∀k ∈ K, ∀w ∈ W, x e k ≤ y w k , ∀e ∈ E w , ∀w ∈ W, ∀k ∈ K, w∈W y w k = 1, ∀k ∈ K,
x e k ∈ {0, 1}, ∀e ∈ E w , ∀w ∈ W, ∀k ∈ K, y w k ∈ {0, 1}, ∀w ∈ W, ∀k ∈ K, where we have used the following notations for k ∈ K and n ∈ V w (12)

h n k (y w k ) =      -y w k n = s k y w k n = t k 0 otherwise.
We have the following result.

Theorem 1. Let (x, y) be any optimal solution of problem (EQ-RWA). Then (x, y, u, w max ) is an optimal solution of problem (RWA), where Proof. It is clear from the definition of problem (EQ-RWA) that the vectors x and y satisfy equations ( 4)-( 6). From ( 13), constraints ( 8) are also satisfied. Moreover, the definition of w max implies that w max ≥ 0 and wu w ≤ w max for all w ∈ W. Hence, (x, y, u, w max ) is a feasible solution of problem (RWA).

Assume that this solution is not an optimal one, that is that there exists a feasible solution (x, ŷ, û, q) of problem (RWA) such that q ≤ w max -1. This clearly implies that the vector ŷ is such that k∈K ŷw k = 0, ∀w > q.

Hence,

w∈W c w k∈K ŷw k = q w=1 c w k∈K ŷw k , ≤ K q w=1 c w , < q w=1 c w + c q+1 ,
where the first inequality follows from k∈K ŷw k ≤ K, ∀w ∈ W, and the second one follows from [START_REF] Cochrane | The hidden benefits of optical transparency[END_REF]. Since q + 1 ≤ w max and since from Lemma 2

k∈K y w k ≥ 1, ∀w ≤ w max , it yields
Require: G = (V, E), K and W 1: w ← 1 2: while K = ∅ do 3:
Solve problem (MAX-FLOW-w) for network layer w.

4:

K ← K \ {k ∈ K : y w k = 1}

5:

w ← w + 1 6: end while We thus conclude that (x, y) is not an optimal solution of problem (EQ-RWA), i.e., a contradiction. Therefore, (x, y, u, w max ) is an optimal solution of problem (RWA).

According to Theorem 1, we can easily obtain an optimal solution of the original problem from an optimal solution of problem (EQ-RWA). Thus, in the following we shall study problem (EQ-RWA) instead of studying problem (RWA).

x e k ≤ 1, ∀e ∈ E w , e∈E + w (n) x e k - e∈E - w (n) x e k = h n k (y w k ), ∀n ∈ V w , ∀k ∈ K, x e k ∈ {0, 1}, ∀e ∈ E w , ∀k ∈ K, y w k ∈ {0, 1}, ∀k ∈ K,
In this section, we propose an heuristic for resolving the (EQ-RWA) problem. The algorithm of the proposed heuristic is described in figure 7.

In this algorithm, we seek to maximize the use of each network layer before proceeding to the next layer. The transistion to the next layer is done once the current layer is saturated. Therefore, it's clear that no demand of the w-layer can be rerouted or replaced in the overlying layers. As against, demands placed in the w-layer can be rerouted over the underlying layers, since these layers may be considered as under-used for some or all of w-layer demands. Let us note K w = {k ∈ K : y w k = 1} the set of demands placed on the w-layer and L R = {λ ∈ W : λ < w} the set of used network layers after solving the optimization problem (EQ-RWA) whith our proposed heuristic.

From this assumption, we proposed an improved algorithm based on successive approximation method. After a first routing with the algorithm proposed in figure 7, we opt to decrease the number of used network layers by trying to reroute all demands of each layer in the others underlying layers. In each w-layer iteration, we seek to find a new routing strategy where w-layer is no longer used. This algorithm try to reroute each demand k ∈ K w over the shortest λ-path where λ ∈ [[w + 1...L R ]]. If there is no available paths for k in all λ-layers, then the w-layer still used in the final routing strategy.

For a given network layer λ, let us define the following optimization problem for the demand k:

minimize e∈E λ z e (SHORTEST λ-PATH-k) subject to e∈E + λ (n) z e - e∈E - λ (n) z e =      -1 if n = s k 1 if n = t k 0 otherwise. , ∀n ∈ V λ , z e ≤ δ e , ∀e ∈ E λ , z e ∈ {0, 1}, ∀e ∈ E λ .
where we have used the following notations for e ∈ E λ ( 14)

δ e = 1 if e is λ-available 0 otherwise.
The enhanced algorithm is described in figure 8 4.4. Experiments and results. In this section, several experiments on the optimization problem for traffic routing were performed in order to evaluate and validate the effectiness of the proposed solutions. The GUROBI solver is used for solving the two integer linear programs: (RWA) and (EQ-RWA). The aim of the experiments here is to analyze the performance of algorithms and compare the proposed methods. The comparison is performed between the different proposed algorithms: ILP-based algorithm (RWA), equivalent ILPbased algorithm (EQ-RWA), basic and enhanced algorithms to solve optimization problem (EQ-RWA) which are illustrated in Fig. 7 and Fig. 8 repectively.

Require: G = (V, E), K and W

1: w ← 1 2: while K = ∅ do 3:
Solve problem (MAX-FLOW-w) for network layer w.

4:

K ← K \ {k ∈ K : y w k = 1} 5: w ← w + 1 6: end while 7: L R ← {λ ∈ W : λ < w} 8: for w ∈ L R do 9: K w ← {k ∈ K : y w k = 1}
for λ = w + 1 . . . |L R | do 19:
Solve problem (SHORTEST λ-PATH-k) for network layer λ. Table 5. Memory Consumption for RWA proposed algorithms

if {e ∈ E λ : z e = 1} = ∅ then 21: K λ-tmp ← K λ-tmp ∪ {k}, K w-tmp ← K w-tmp \ {k}
if cpt = |K w | then 34: L A ← L A ∪ {w} 35: for λ = w . . . |L R | do 36: K λ ← K λ-tmp
Topology Size (RWA) (EQ-RWA) (BA-RWA) (EA-RWA) |V | = 5, |E| = 12, |W | = 20 5M 6M 5M 6M |V | = 8, |E| = 20, |W | = 20 80M 85M 9M 11M |V | = 10, |E| = 26, |W | = 30 280M 295M 14M 16M |V | = 15, |E| = 40, |W | = 40 520M 545M 18M 20M |V | = 20, |E| = 56, |W | = 40 940M 980M 26M 28M |V | = 30, |E| = 86, |W | = 60 1.9G 2G 40M 43M |V | = 40, |E| = 122, |W | = 60 2.8G >3G 75M 79M |V | = 50, |E| = 158, |W | = 80 >3G >3G 200M 206M
The performance comparison between the algorithms is done based on two criteria. The first is related to the execution performance including computation time and memory consumption. The second one concerns the routing strategy cost which represents in this case the number of used wavelengths (i.e. colours) for satisfying all routed lightpaths. 4.4.1. Execution performance. In this part, we summarize the run performance of the proposed algorithms on several topologies, with different sizes. The results related to computation time and memory consumption are illustrated in Tables 4 and5, respectively. For each simulation, the differents algorithms are executed on the same topology and for the same set of demands which are randomly generated. Topology size is defined by three terms |V |, |E| and |W | which represents the number of nodes, the number of fibers and the number of available wavelengths in each fiber, respectively.

From these results, it's clear that the approximate algorithms are much more faster, and consume less memory than the ILP-based ones. A routing strategy solution can be found in a few seconds for large topology sizes. 4.4.2. Routing strategy cost. In RWA problem, the routing strategy cost represents the number of used layers (i.e. wavelengths) when routing the lightpaths matrix. This optimization criterion is the same in all our proposed algorithms. In this part, we compare the quality of routing ensured by the differents solutions. For that, it suffices to compare their routing strategy costs. For this comparison, a simplistic topology with 10 nodes, 26 fibers and 40 available wavelengths is considered. Twenty simulations have been performed on this network. For each simulation, the differents algorithms try to route the same set of demands, which are randomly generated. Table 6 illustrate the obtained results and figure 9 represents the curve of the relative error between the ILP-based algorithm (EQ-RWA) solution (i.e. optimal solution) and the (EA-RWA) one (i.e. approximate solution), along the 20 simulations. The matrix size here represents the total number of lightpath demands.

The obtained results clearly show the efficiency of the proposed enhanced heuristic. Among the twenty simulations, there are only five times where we don't reach the optimal solution. In addition, the (EA-RWA) algorithm provides an improved solution compared to the (BA-RWA) algorithm. In several simulations, we succeeded in enhancing the strategy routing cost returned by the (BA-RWA) thanks to our enhanced algorithm. Since we search to maximize the number of routed lightpaths on the w-layer given that each link (i.e. fiber) can be used only once, the problem is equivalent to a Maximum Multicommodity Problem with edges capacities equal to 1. Commodity pairs represents the set of pairs (s k ,t k ) of lightpaths for k ∈ K.

A multicommodity flow problem is defined on a directed network G = (V, E) with capacities u(e) for e ∈ E and p source-target pairs (s j ,t j ) for 1 ≤ j ≤ p. The problem is to find flows f j from s j to t j that satisfy flow conservation constraints and capacity constraints that ensures that the sum of flows on any edge does not exceed the capacity of the edge. For the maximum multicommodity flow problem, the objective is to maximize the sum of the flows j |f j |.

While there are many different algorithms known for this problem we discuss one which guarantee an (1 + ω)-approximation to the maximum throughtput. The goal of the Garg-Knemann algorithm is to find an ω-approximate solution for any error parameter ω > 0. the ω-approximate solution is a flow that has value at least (1ω) times the maximum Require: network G = (V, E), capacities u(e), commodity pairs (s j , t j ) for 1 ≤ j ≤ p, accuracy ǫ 1: Initialize l(e) = φ ∀e, x = 0 2: while there is a P ∈ P with e⊂P l(e) < 1 do value. In addition, the running time of this type of algorithms is known depending on the approximation value ω, the number of commodity pairs p and the number of edges m.

This generic algorithm for maximum multicommodity flow, that we adopted here, try to find mutually two solutions for the primal and dual programs for the maximum multicommodity flow problem. Let P j denote the set of paths from s j to t j , and P := ∪ j P j .

x(P ) equals the amount of flow sent along path P and represents the decision variable of the primal program. The length of an edge l(e) represents the decision variable of the dual program and reflects the marginal cost of using an additional unit of capacity of the edge. The generic Garg-Knemann algorithm, described in figure 10, stops when the ratio between the primal and the dual solutions is at most 1 + ω. The accuracy ǫ is a fixed constant that choosen appropriately depending on ω. φ represents the inial length of all network edges which depends on ǫ and m.

The Garg-Knemann algorithm solves the maximum multicommodity flow problem with a guarantee of error approximation. The real flow can be deducted by scaling the final flow obtained in the generic algorithm by log 1+ǫ 1+ǫ φ . But the generated flow is generally fractional which is not adapted in our study case where we search to route a set of lightpaths (i.e. flows in the case of maximum multicommodity flow problem). Therefore, the solution must be integer or at least quasi-integer. For this, we have proposed a modification in Garg-Knemann algorithm in order to converge to a quasi-integer solution: Since in each iteration we search the minimum length path and the algorithm augments flow along this path, so we can use different paths in two successive iterations. Our idea consists on keeping the choosen minimum length path and augmenting flow along it until the "real" flow converges to 1. Once this condition is satisfied, the algorithm can switch to another minimum length path and repeat the same treatment. The modified Garg-Knemann algorithm is described in figure 11. The proposed modification allows a primal quasi-integer solution. This solution can be easily rounded to an integer solution.

The Garg-Knemann algorithm try to maximize the flow sent between the source and the taget of each commodity pair. Hence, the calculated flow for a commodity j can exceed the required amount of demand (i.e. number of lightpaths) between s j and t j . This does Require: network G = (V, E), capacities u(e), commodity pairs (s j , t j ) for 1 ≤ j ≤ p, amount of demands t j for 1 ≤ j ≤ p, accuracy ǫ, threshold α (close to 1) 1: Initialize l(e) = φ ∀e, x = 0 2: iter ← 1 3: while there are a commodity j ∈ [[1...p]] and a path P ∈ P j :

e⊂P l(e) < 1 and Q∈P j x(Q) < t j do 4:

if iter = 1 or x(P ) ≥ α or Q∈P j x(Q) ≥ t j then 5:

Select the minimum length path P ∈ P and the commodity j : P ∈ P j and Q∈P j x(Q) < t j 6:

end if 7:

u ← min e⊂P u(e)

8:

x(P ) ← x(P ) + iter ← iter + 1 11: end while 12: Return (x, l). not match with our expectation. Consequently, we have added an additional capacity constraints for commodity pairs. For each commodity j, we have assigned a constant t j which is equal to the required demand between s j and t j . The total flow for commodity j (= Q∈P j x(Q))) must not exceed the value of t j . Adopting this modification, we can guarantee that the maximum flow sent between s j and t j can not exceed the required number of lightpaths for the commodity j.

After applying our updates, we can adopt this modified algorithm for solving the (MAX-FLOW-w) problem.

Experiments and results

. several experiments on the optimization problem (MAX-FLOW-w) were performed in order to evaluate and validate the effectiness of the proposed solutions. The GUROBI solver is used for solving the integer linear program (MAX-FLOW-w). The aim of the experiments here is to analyze the performance of algorithms and compare the proposed methods. The comparison is performed between the ILP-based algorithm and the modified Garg-Knemann algorithm after its adaptation to our optimization case. We compare her the optimal solution generated by the ILP-based algorithm and the approximate solution deducted by the modified Garg-Knemann algorithm. For this comparison, three simplistic topologies are considered. Ten simulations have been performed on each network. For each simulation, the two algorithms try to route the same set of demands (i.e. lightpaths), which are randomly generated. Tables 7, 8 and 9 illustrate the obtained results for the three studied topologies. the fixed ω for the Garg-Knemann algorithm is 0, 05. 4.6. New heuristic as an equivalent to "Maximum Edge-Dijoint Paths" to solve the (MAX-FLOW-w) problem.

4.6.1. Algorithm. As shown in the previous section, we can solve the (MAX-FLOW-w) problem effectively using a modified version of the Maximum Multicommodity Flow Garg-Knemann algorithm. the adopted algorithm try to route the maximum amount of flows over a network w-layer. The obtained solution is generally fractionnal, but we can easily provide a rounded feasible solution. Since a flow unit represents a lightpath and a flow unit path can be used only once because the capacity of every edge in w-layer is 1, the problem can be distinguish as a "Maximum Edge-Dijoint Paths" (MEDP). The goal is to route as many requests as possible along edge-dijoint paths. The input consists of a directed graph G = (V, E) and a set containing k requests K = {(s i , t i )|i = 1 . . . k}, where each request is a pair of vertices in V . The request (s i , t i ) asks for a directed path from s i to t i in G. A feasible solution is given by a subset A and an assignment of edge-disjoint paths to all requests in that subset. More precisely, each (s i , t i ) ∈ A must be assigned a directed path P i from s i to t i in G such that no two paths P i and P j (for i, j ∈ A and i = jhave a directed edge of the graph in common. The requests in A are called the accepted requests. We search to maximize the cardinality of A.

The MEDP problem has been studied in many works and solved by several algorithms. One of these algorithms is the Shortest-Path-First suggested by Kolliopoulos and Stein. The algorithm is illustrated in figure 12 4.7. Comparison between (RWA) solution and approximate solution using the new heuristic. In this section, we compare the performance of the three algorithms : the (RWA) ILP-based algorithm, the (BA-RWA) algorithm and the (EA-RWA) algorithm. For the two last algorithms, illustrated in figure 7 and8, the (MAX-FLOW-w) ILP-based algorithm is remplaced by our new heuristic "Modified Garg-Knemann algorithm" shown if figure 11. We adopt here the same network model (10 nodes, 26 links and 40 available wavelengths) and the same set of simulations we used in the section 4.4.2. We recall that we compare the routing strategy costs for the three algorithms. The routing stategy cost represents the number of used layers (i.e. wavelengths) for routing all lightpath demands. Table 10 represents the results among twenty simulations and figure 13 show the relative error between the optimal solution and the approximate (EA-RWA) solution. Require: network G = (V, E), K = {(s i , t i )|i = 1 . . . k} 1: A ← ∅ 2: while K contains a request that can be routed in G do 3:

Select a request (s i , t i ) in K such that the shortest path from s i to t i in G has minimum length among all requests in K 4:

A ← A ∪ {(s i , t i )}

5:

K ← K \ {(s i , t i )}

6:

P i ← a shortest path from s i to t i in G 7:

Remove all edges of P i from G 8: end while 9: Return A and {P i |(s i , t i ) ∈ A}. Computation time and memory consumption are also compared for the three studied algorithms. we summarize here the run performance of the proposed algorithms on several topologies, with different sizes. The results related to computation time and memory 11 and12, respectively. For each simulation, the differents algorithms are executed on the same topology and for the same set of demands which are randomly generated. Topology size is defined by three terms |V |, |E| and |W | which represents the number of nodes, the number of fibers and the number of available wavelengths in each fiber, respectively.

1 2 3 Figure 1 .

 31 Figure 1. Simple example of network with 3 nodes and 2 directed edges between each pair of nodes.

  minimize e∈E b e (OPT-LP) subject to y e ≤ C.b e , ∀e ∈ E, y e = d∈D π∈Π(d) δ π e x d,π , ∀e ∈ E, π∈Π(d) x d,π = λ d , ∀d ∈ D, x d,π ≥ 0, ∀π ∈ Π(d), ∀d ∈ D, y e ≥ 0, ∀e ∈ E, b e ∈ {0, 1}, ∀e ∈ E.

  d , which proves that x * ∈ X d . Note that by definition of x - d , we have y e (x * d ) = y e (x - d ) ≤ c e for all e ∈ E -. Moreover, since λ d -λ(E -) n ≤ C, we have y e k (x * d ) ≤ C = c e for k = 1, . . . , n. We thus conclude that y e (x * d ) ≤ c e , ∀e ∈ E. Since the routing strategy x * d uses n links in E + , we conclude that v d (x * d ) = n, and thus there exists at least one feasible solution to (OPT-d) whose cost is n.

1 : x ← 0 2 : 4 :

 124 Convergence = false 3: while Convergence = false do

Figure 3 .

 3 Figure 3. Routing Strategy Cost

Figure 4 .

 4 Figure 4. Relative error between optimal and approximate solutions

Figure 5 .

 5 Figure 5. Successive Approximation Algorithm Convergence : Number of iterations

Figure 6 .

 6 Figure 6. The original network and the three layers obtained by duplicating nodes and links in the case of two colours.

= 1 ,

 1 . . . , W, and w max = max w∈W (w u w ).

Figure 7 .

 7 Figure 7. Basic approximate algorithm (BA-RWA) to solve optimization problem (EQ-RWA).

4. 3 .

 3 Solution procedure. For a given network layer w, let us define the following opti-

  if rerouted = f alse then 27: for λ = w . . . |L R | do 28:K λ-tmp ← K λ

Figure 8 .

 8 Figure 8. Enhanced approximate algorithm (EA-RWA) to solve optimization problem (EQ-RWA).

Table 4 .

 4 Computation Time for RWA proposed algorithms Topology Size (RWA) (EQ-RWA) (BA-RWA) (EA-RWA) |V | = 5, |E| = 12, |W | = |V | = 10, |E| = 26, |W | = 30 2m19s 2m43s 4.2s 4.5s |V | = 15, |E| = 40, |W | = 40 6m52s 8m24s 12.2s 12.8s |V | = 20, |E| = 56, |W | = 40 13m12s 17m05s 52.2s 53s |V | = 30, |E| = 86, |W | = 60 38m56s 49m21s 4m12s 4m14s |V | = 40, |E| = 122, |W | = 60 >2h >2h 9m34s 9m38s |V | = 50, |E| = 158, |W | = 80 >3h >3h 27m42s 27m53s

4. 5 .

 5 New heuristic as an equivalent to "Maximum Multicommodity Flow" to solve the (MAX-FLOW-w) problem.

Figure 9 .

 9 Figure 9. Relative error between approximate and optimal solutions

3 :

 3 Select the minimum length path P ∈ P4:u ← min e⊂P u(e) 5:x(P ) ← x(P ) + u 6:∀e ∈ P, l(e) ← l(e)(1 + ǫu u(e) ) 7: end while 8: Return (x, l).

Figure 10 .

 10 Figure 10. Generic Garg-Knemann algorithm.

9 :

 9 ∀e ∈ P, l(e) ← l(e)(1 + ǫu u(e) )10:

Figure 11 .

 11 Figure 11. Modified Garg-Knemann algorithm.

Figure 12 .

 12 Figure 12. Shortest-Path-First algorithm.

Figure 13 .Table 12 .Figure 14 .

 131214 Figure 13. Relative error between optimal and (EA-RWA) approximate (based on Modified Garg-Knemann algorithm) solutions

Table 1 .

 1 Summary of static RWA algorithms

	Problems	Approaches	Comments	References
	Joint RWA	ILP Formulation	NP-complete	[15, 5, 34, 14, 24, 23]
		(including relaxed formulation)		[27, 9, 10]
		SFFP
		LFFP
		MNH	Heuristics	[7, 35, 33, 6, 3]
		LFAP
		HPLD	Objective: Minimizing
		FF-RWA	the number of required
		BF-RWA	wavelengths	[36, 25]
		FFD-RWA
		BFD-RWA
	Routing	ILP Formulation	NP-complete	[31, 34, 2, 9]
		(including relaxed formulation)
		Fixed routing		[39, 22, 28]
		Alternate routing
	Wavelength	Graph coloring	NP-complete	[39, 34, 2, 9]
	Assignment		(routes are known)
		Random
		LU (SPREAD)	Heuristics
		FF	used with
		MP (multi-fiber)	Fixed Routing	[39, 4, 17, 18, 38, 41]
		MU (PACK)	approach
		LL (multi-fiber)

Table 2 .

 2 Computation Time

	Topology Size ILP-Based Algorithm Successive Approximation Algorithm
	5 nodes	0.08s	0.008s
	8 nodes	0.5s	0.01s
	10 nodes	2m19s	0.014s
	12 nodes	6m54s	0.2s
	15 nodes	27m43s	0.3s
	20 nodes	36m21s	0.6s
	25 nodes	52m16s	0.8s
	30 nodes	>1h	0.9s
	50 nodes	>2h	1.2s
	100 nodes	>5h	3.4s

Table 3 .

 3 Memory Consumption

	Topology Size ILP-Based Algorithm Successive Approximation Algorithm
	5 nodes	80M	2M
	8 nodes	170M	4M
	10 nodes	240M	6M
	12 nodes	825M	8M
	15 nodes	1.3G	9M
	20 nodes	1.8G	11M
	25 nodes	3.2G	14M
	30 nodes	>4G	18M
	50 nodes	>4G	26M
	100 nodes	>4G	40M

Table 3 .

 3

Table 6 .

 6 Routing strategy cost

	Matrix size (EQ-RWA) (BA-RWA) (EA-RWA)
	89	13λ	14λ	13λ
	86	14λ	15λ	14λ
	104	16λ	16λ	16λ
	97	14λ	14λ	14λ
	80	13λ	14λ	13λ
	81	14λ	15λ	14λ
	82	16λ	16λ	16λ
	98	15λ	16λ	15λ
	83	14λ	14λ	14λ
	92	13λ	14λ	14λ
	169	25λ	25λ	25λ
	174	28λ	28λ	28λ
	187	27λ	28λ	28λ
	158	22λ	23λ	22λ
	174	26λ	27λ	26λ
	168	27λ	27λ	27λ
	172	27λ	27λ	27λ
	165	23λ	24λ	24λ
	169	28λ	29λ	29λ
	177	26λ	27λ	27λ

Table 7 .

 7 Topology 1 : 6 nodes and 14 links

	Number of Optimal Approximate solution	Approximate solution	Rounded solution
	demands solution	(shortest-path-first)	(Modified Garg-Knemann) (Modified Garg-Knemann)
	40	13	13	12,9247	13
		0.4s	0.009s	0.04s
	42	9	9	8,9894	9
		0.4s	0.008s	0.02s
	48	10	10	9,9893	10
		0.5s	0.007s	0.02s
	41	12	12	11,9707	12
		0.4s	0.008s	0.03s
	39	9	9	8,9986	9
		0.4s	0.007s	0.02s
	49	10	10	9,9985	10
		0.6s	0.009s	0.03s
	34	10	10	9,9618	10
		0.4s	0.007s	0.02s
	55	11	11	10,9892	11
		0.5s	0.008s	0.02s
	47	11	11	10,9617	11
		0.4s	0.007s	0.02s
	42	12	12	11,9707	12
		0.4s	0.008s	0.03s

Table 8 .

 8 Topoogy 2 : 15 nodes and 38 links

	Number of Optimal Approximate solution	Approximate solution	Rounded solution
	demands solution	(shortest-path-first)	(Modified Garg-Knemann) (Modified Garg-Knemann)
	263	27	27	26,9701	27
		1.5s	0.02s	0.1s
	308	31	31	30,9555	31
		1.3s	0.026s	0.2s
	328		31	30,9492	31
		1.3s	0.027s	0.2s
	315	28	27	26,9618	27
		1.3s	0.021s	0.1s
	289	31	31	30,9683	31
		1.4s	0.026s	0.2s
	316	30	29	28,9971	29
		1.3s	0.024s	0.1s
	312	30	30	29,9349	30
		1.3s	0.024s	0.1s
	304	34	34	33,9031	34
		1.3s	0.026s	0.2s
	295	31	31	30,9459	31
		1.5s	0.024s	0.1s
	211	26	26	25,9602	26
		1.3s	0.021s	0.1s

Table 9 .

 9 Topoogy 3 : 34 nodes and 92 links

	Number of Optimal Approximate solution	Approximate solution	Rounded solution
	demands solution	(shortest-path-first)	(Modified Garg-Knemann) (Modified Garg-Knemann)
	1128	76	76	75,8519	76
		5.4s	0.208s	2.3s
	1119	72	72	71,8396	72
		6.2s	0.202s	2.1s
	1091	70	70	69,8849	70
		5.8s	0.193s	1.9s
	1089	71	71	70,8561	71
		6.3s	0.194s	1.9s
	1143	73	72	71,8837	72
		5.6s	0.209s	2.1s
	1103	71	70	69,8503	70
		6.1s	0.196s	1.9s
	1126	70	70	69,8529	70
		5.5s	0.194s	1.9s
	1108	73	73	72,8785	73
		6.4s	0.207s	2.1s
	1116	67	66	65,8944	66
		5.2s	0.186s	1.8s
	1058	65	63	62,8864	63
		5.1s	0.177s	1.5s

Table 10 .

 10 Routing strategy cost : Comparison between optimal solution and approximate ones Number of (RWA) or (EQ-RWA) (BA-RWA) → (EA-RWA) (BA-RWA) → (EA-RWA) lightpaths (based on Modified Garg-Knemann) (based on Shortest-path-first)

	89	13λ	13λ → 13λ	13λ → 13λ
	86	14λ	15λ → 15λ	15λ → 15λ
	104	16λ	17λ → 16λ	17λ → 16λ
	97	14λ	14λ → 14λ	14λ → 14λ
	80	13λ	14λ → 13λ	14λ → 14λ
	81	14λ	15λ → 14λ	15λ → 14λ
	82	16λ	16λ → 16λ	16λ → 16λ
	98	15λ	16λ → 16λ	16λ → 16λ
	83	14λ	15λ → 14λ	15λ → 14λ
	92	13λ	14λ → 14λ	14λ → 14λ
	169	25λ	27λ → 25λ	27λ → 25λ
	174	28λ	30λ → 29λ	30λ → 29λ
	187	27λ	29λ → 29λ	29λ → 29λ
	158	22λ	23λ → 23λ	24λ → 23λ
	174	26λ	29λ → 28λ	29λ → 28λ
	168	27λ	27λ → 27λ	27λ → 27λ
	172	27λ	28λ → 28λ	28λ → 28λ
	165	23λ	25λ → 24λ	25λ → 24λ
	169	28λ	30λ → 30λ	30λ → 30λ
	177	26λ	28λ → 27λ	28λ → 27λ
	consumption are illustrated in Tables