1. Introduction

Wavelength division multiplexing (WDM) has emerged to be the most cost-effective way to unleash the enormous bandwidth in optical fibers for long haul and metropolitan networks. In a WDM optical network, it is possible for each wavelength to be routed independently with re-configurable optical cross connects (OXCs) and optical add/drop multiplexers (OADMs), which allows any ingress node to be connected to any egress node by one or more wavelengths. Given a set of connections, the problem of setting up lightpaths by routing and assigning a wavelength to each connection is called the routing and wavelength assignment (RWA) problem. Typically, connection requests may be of three types: static, incremental and dynamic. With static traffic, the entire set of connections is known in advance, and the problem is then to set up lightpaths for these connections while minimizing the required network resources such as the number of wavelengths or the number of fibers in the network, as in [1–4]. Alternatively, if the network resources, such as number of wavelengths and transceivers, are given, the optical network design problem is to set up as many of these connections as possible with the limited resources, as in [5–9]. In this paper, we study the second problem. Previous works [5–9] have solved many variations of this problem under the assumption of perfect physical layer conditions, i.e. to ignore such physical limitations as amplified spontaneous emission (ASE) noise, crosstalk due to signal leakage in optical cross-connects (OXCs), optical fiber nonlinearities, and dispersions, etc. In reality, there is no satisfactory method to overcome these impairments apart from re-amplification, re-shaping and re-timing, which are collectively known as 3R regeneration. At present and in foreseeable future, 3R regeneration can only be carried out cost effectively in the electronic domain. Realistically, a lengthy end-to-end lightpath has to be set up in a multi-hop manner, i.e., the lightpath needs regeneration at some intermediate nodes, dividing the lightpath into two or more fragments such that the length of each fragment is less than the transparent length (‘Reach’) or each fragment satisfies the bit error rate (BER) requirement [10–18]. This type of optical networks, in which each node routes some lightpaths transparently while subject others to go through the 3R regeneration, is known as translucent optical networks [13].

One approach to designing a translucent optical network is to divide a large-scale optical network into several islands of optical transparent domains. Within the same island, a lightpath can transparently reach any node without any intermediate signal regeneration. For communications across islands, regeneration nodes at the island boundaries are used. These regeneration nodes act as 3R regenerators for lightpaths spanning across one or more island boundaries [14]. Another approach is to sparsely place regeneration nodes in the network by a carefully designed algorithm [15–17]. These two approaches assume that the regenerator facilities are only available at certain nodes. Nevertheless, it was pointed out in [18] that the transceivers in the access stations of optical network nodes can be used for regeneration. No special devices need to be installed but the transceivers would be used for either initiating/terminating lightpaths or regeneration. Since in most cases it is unlikely that the lightpaths that are initiated and terminated at a node will use up all the transmitters and the receivers in the access stations, many nodes will have spare transceivers available for regeneration purpose [18]. This is the kind of networks that we look into and our objective is to maximize the NEC given the traffic matrix, the network topology, the fixed set of wavelengths and the number of transceivers in each node under the constraint of transparent length. This problem can be formulated as a mixed-integer linear programming (MILP) formulation. Since the MILP formulation can only be solved for small sized networks, an effective heuristic algorithm is proposed.

The rest of the paper is organized as follows. In Section 2, the network model is presented. In Section 3, the formulation for maximizing the NEC is presented. In Section 4, the heuristic RWA algorithm is proposed. In Section 5, the numerical results for various networks and some discussion are provided, and finally a conclusion is given in Section 6.

2. Network model

An optical network consists of switching nodes interconnected by optical fiber links. Each node consists of an OXC and an access station, as shown in Fig. 1. The OXC consists of multiplexers, optical switches and demultiplexers. The transmitters (Tx) and receivers (Rx) are in the access station. Incoming optical channels at different wavelengths can be switched to the outgoing fibers or be dropped at the access station by configuring the optical switches. The access station not only can drop optical channels but also add optical channels to the network. If a channel is originated from the node, it enters the network through the T_X set. If the channel is terminated at the node, it exits via the R_x set. If the channel traverses the node and needs regeneration, it enters and exits the node via a TxRx pair.

In our node model, each transceiver can only receive and transmit at a fixed wavelength, the received signals can be switched to one of the fixed-tuned transmitters using electronic switches; therefore wavelength conversion can be realized, as shown in Fig. 1.

 

Fig. 1 The node model

Download Full Size | PDF

3. Problem formulation

In [5], the problem of maximizing the NEC in a network without considering the physical constraints for a fixed number of wavelengths and a given set of connection requests is formulated as an integer linear programming (ILP) problem, but the routes can only be selected from a route table. In [6, 9], the RWA problem with limited-range wavelength conversion is formulated as a MILP. In [19], the RWA problem with power considerations is formulated as a mixed integer nonlinear program (MINLP). However, in that formulation the possible routes for a node pair are predefined, therefore the result may not be optimal.

In this paper, we present an exact MILP formulation for the problem of maximizing the NEC given the network topology, the number of wavelengths, the number of transceivers in each node and the traffic matrix under the constraint of transparent length. The routes are not subject to a given route table. The formulation allows choosing any possible path, any possible wavelength, and regenerating the lightpath at any possible intermediate nodes for a connection request.

We use the following notation:

Given:

The objective is to maximize the number of established connections from the given traffic matrix. Objective:

Constraints:

1) Physical topology constraints

The routing variable is constrained by the physical topology. The equation ensures that only there is a physical link that a lightpath can traverse.

2) Wavelength continuity constraints

The equation ensures that only those ${\gamma }_{i\mathit{,}j\mathit{,}m\mathit{,}n}^{q\mathit{,}w}$ could be nonzero for which the corresponding ${\beta }_{i\mathit{,}j}^{q\mathit{,}w}$ variables are nonzero.

There is at most one lightpath traversing wavelength w in the physical link (m, n).

The equation ensures that a wavelength is conserved at every node of the q^th lightpath between (i, j).

3) Flow constraints

The connection requests traversing through (i, j) is constrained by the number of lightpaths established between (i, j).

On each node of the network, except for those lightpaths that originate from or destine to this node, the number of incoming lightpaths must be equal to the number of outgoing lightpaths.

The number of connections established between any node pair (s, d) is at most c^s,d .

4) Length constraints

For any established lightpath, the length of the lightpath should be less than the transparent length L_s .

5) Transceivers constraints

The number of lightpath emerging from or terminating at or regenerated in a node is constrained by the number of transmitters and receivers at that node.

The number of variables grows as O(N⁴WQ), and the number of constraints also grows as O(N⁴WQ). This formulation is NP-complete [7].

4. The heuristic approaches

Clearly, the formulation can only be solved in small networks. Therefore in this section we propose a heuristic algorithm to solve the problem in large networks. Wavelength routing consists of routing and wavelength assignment. Here we present a heuristic algorithm based on the K-least-wavelength-weight-path routing and statistical method.

K-least-wavelength-weight-path (K_WW) routing algorithm: For this algorithm, the number of occupied wavelength in the links is taken as the weight. For each additional channel (or lightpath) transported by a link, the weight of the link increases by 1. The route for a new lightpath can be selected from the K-least-wavelength-weight routes between the source and destination node pair. In other words, this algorithm attempts to even out the utilization of wavelengths in all the network links. The algorithm proceeds in the following steps:

Step 1: Sort the connection requests between all node pairs in terms of shortest hop length according to ascending (As), descending (De) or random (R) order. NEC=0.

Step 2: The node pair (s, d) is considered. If the number of connection requests c^s,d >0, find K-shortest paths for the node pair. The K paths are named as path1, path2, …, pathK. Consider path1 for processing and go to step3.

Step 3: Find the set of wavelengths that are available for the maximum number of hops, say from node 1 to f, along the route, starting from the source node. Within the segment from the source node to node f, let t (≤f) be the node closest to the destination and that the length between the source node and t is smaller than L_s , the lowest-indexed wavelength with the largest number of spare transmitters from the set of candidate wavelengths is assigned to the lightpath from the source node to t. We then set t as the source node, and repeat the process.

If the connection request can be established on this path, set c^s,d =c^s,d -1 and the number of connections established NEC=NEC+1, go to step2. If the connection cannot be established, go to step4.

Step 4: Repeat step3 until all the alternate paths are checked. If the connection request cannot be established, then c^s,d =0, go to step5.

Step 5: Repeat step2 to step4 until all the connection requests in traffic matrix are checked.

By using step1 to step5, one NEC can be obtained. However, this number is dependent on the sequence in which the connection requests are established as determined in step1. If we compute all the possible sequences, the computation time is unacceptable. Here, a statistical method is used. First the connection requests are sequenced and the NEC for this particular sequence is recorded. For the R ordering, we can then simply sequence all the connection requests randomly for a certain number of times to obtain the distribution of the NECs. For the As and De ordering, many connections may have the same shortest hop length and the sequence of them may still affect the NEC. These requests with the same shortest hop length will be sequenced randomly to obtain the NEC. This is repeated for a certain number of times with different sequence, and the distribution of the NECs can be obtained. We then take the largest value of the NECs as the maximum NEC (MNEC).

We use Yen’s algorithm [20] to find the K-shortest paths and assume the number of links in the network is E, the number of connection requests is D, and the algorithm is repeated F times, then the complexity of this algorithm is O(1/2×F×D×W×E×K×N³ ).

5. Numerical results

In this section, three types of networks are used for simulation: 7-node random networks, a 7-node ring network and the NSFNET. The topologies of one of the 7-node random networks and NSFNET are shown in Fig. 2 and Fig. 3. The link lengths in km are labeled on the links in the networks. We assume the 7-node ring network has equal link length and the link length is 1000km. The traffic matrix to be realized for the 7-node random and 7-node ring networks is shown in Table 1 with a total of 55 connection requests. We assume that at most 3 connections are permitted for a source-destination pair and the number of connections is chosen from 0, 1, 2 and 3 with equal probability for a source-destination pair. While for the NSFNET, the traffic matrix is the same as Table 1 in [6] with a total of 268 connection requests.

 

Fig. 2. The topology of 7-node random network

Download Full Size | PDF

 

Fig. 3. The topology of NSFNET

Download Full Size | PDF

Table 1. The traffic matrix for the 7-node random network and the 7-node ring network

View Table | View all tables in this article

A node with a higher connectivity (node-degree) is equipped with more transceivers proportionally, e.g., a node with T links is equipped with MT transceivers if the network transceiver density is dimensioned as M transceivers per link. In order to keep the wavelengths of the transceivers in each node as far apart as possible, we first assign ⌊(MT)/W⌋ transceivers for each wavelength, and then distribute the remaining MT-W×⌊(MT)/W⌋ transceivers uniformly over different wavelengths.

All experiments were conducted on a 2 GHz PC with 256M RAM. The MILP has been solved by using ILOG OPL Studio (version 3.6.1). Table 2 shows the results obtained for the 7-node random network in Fig. 2 with W=4 for different number of transceivers and different transparent length. ‘L_s =∞’ means the transparent length L_s is infinite. Each entry in Columns 2, 4, 6 and 8 shows the MNECs obtained from ILOG OPL Studio with the computation time after the separator “/”. When solving the MILP, the value of Q needs to be determined, which is constrained by Q _max=Max_{(i, j)} (Min (MT(i), MT(j))), where T(i) and T(j) are respectively the number of links terminated at node i and node j, i, j ∈{1, 2, …, N}, and i≠j. However, this constraint is too large for real problem. We can use the following method to determine the value of Q. For given M and L_s , we can start from Q=1, and apply the MILP to get a solution; then set Q=2 and apply the MILP to get another solution. If the two solutions are identical, it means Q=1 is enough, otherwise we set Q=3 and repeat the procedure. In the 7-node random network, we find that Q=4 is large enough for different M and L_s , which is much smaller than Q _max=3×4=12 when M=4, and much less memory and solving time will be needed. It can be seen from Table 2, for the 7-node random network in Fig. 2 the solving time for MILP is less than 1 minute for different conditions when Q=4. Each entry in Columns 3, 5, 7 and 9 shows the MNECs obtained with the heuristic algorithm (K_WW) by using the ascending (As) order of lightpath arrangement. This is because the As order can get better results than descending (De) and random (R) order. We will show this later. When the heuristic algorithm is used, we repeat the algorithm for F=100 times with K=4. The computation time for the algorithm is less than 2 minutes. It can be seen from this table that, in most cases the results obtained by the heuristic algorithm are the same as the optimal results from MILP.

Table 2. The MNCEs obtained in the 7-node random network (W=4)

View Table | View all tables in this article

Table 3 shows the results obtained in the 7-node ring network with W=4 for different number of transceivers and different transparent length. The resolving time for the MILP is less than 5 minutes for different conditions when Q=4. When the heuristic algorithm is used, we repeat the algorithm for F=100 times with K=2, and the computing time is less than 20 seconds. It also can be found from this table that, in most cases the results obtained by the heuristic algorithm are the same as the optimal results.

Table 3. The MNCEs obtained in the 7-node ring network (W=4)

View Table | View all tables in this article

In order to further examine the performance of the proposed heuristic algorithm on different topologies, we randomly generated twenty 7-node networks with different connectivity α, α=2E/(N×(N-1)), the minimum degree of all the nodes is assumed to be 2 for reliability consideration. The length of the links is randomly selected from [500, 2000]. From the simulation, we find that for different conditions (α changes from 0.33 to 1, M changes from 1 to 4, and the L_s changes from 1000km to infinite), 80% of the results obtained from the heuristic algorithm are the same as the optimal results. The average deviation from the optimal results is 0.45, while the maximum deviation is 3. The optimal results can be obtained only through global optimization as in the MILP. In the heuristic, the lightpaths are simply established one after another in a pre-defined sequence and only K routes are tried, thus trading performance off for speed. Though with greatly reduced complexity, the heuristic yields results reasonably close to the optima. The results do not show any regular pattern of performance deviation from the optima, as it should be due to the random nature of the heuristic.

For NSFNET, the network is too large for the MILP to be solved exactly; the LP upper bound of NCEs is obtained by relaxing the integer constraints of the variables. When the heuristic algorithms are used, we repeat the algorithms for F=200 times with K=3. The computation time is less than 20 minutes.

The relationship between NECs and M for different order of lightpath arrangement in NSFNET is shown in Fig. 4, when W=8 and L_s =3000km. For different order of lightpath arrangements, the Max and Min denote the maximum and minimum value of the NECs obtained from 200 independent trials. We can find that the difference between the maximum and minimum NECs can be up to 20. It proves that the statistical method is effective.

It is obvious that the NECs increase with M, since more transceivers can be used for lightpath adding/dropping and regeneration. Comparing with the results obtained without the constraint in the lightpath length, the heuristics yield results relatively close to the LP upper bound when there are very few transceivers. This is because the transceiver resources become the main bottleneck in both cases. As this bottleneck is being removed by adding more transceivers, the NECs increase rapidly but soon the length constraint takes effect. This results in further deviation from the optimum without the length constraint. At certain point, the performance saturates where adding transceivers would not improve the performance further even in the LP upper bound. At this point, using the heuristics, the NECs would continue to increase by having more transceivers to overcome the length constraint to approach the LP upper bound. We can also find that regardless of M, the performance decreases in the following order: ascending (As), random (R) and descending (De) order of lightpath arrangements. The difference between As and De becomes larger with increasing M. This is because the shortest lightpaths are assigned wavelengths first in As strategy, therefore more network resources can be reserved for later connection requests. While in De strategy, the longest lightpaths are assigned wavelengths, more long lightpaths will be established with increasing M, more resources will be consumed and fewer resources can be reserved for other connection requests.

 

Fig. 4. NECs vs. M for As, De and R order of lightpath arrangements. W=8, Ls=3000Km

Download Full Size | PDF

Figure 5 shows the relationship between NECs and L_s for different order of lightpath arrangements, when W=8 and M=4. The NECs first increase quickly with L_s and then level down where the bottleneck in transceiver resources is encountered. Note that the level at which the performance saturates can be raised if more transceivers were allocated. The existence of the saturation point also shows that given a certain number of transceivers, it is not very helpful to increase the transparent length (e.g., by using better optical components to reduce losses or noise) beyond the saturation point. Regardless of L_s , the performance still decreases in the order of As, R and De.

 

Fig. 5. NECs vs. Ls for As, De and R order of lightpath arrangements. W=8, M=4

Download Full Size | PDF

6. Conclusions

The problem of maximizing the number of established connections (NEC) in translucent optical networks given the network topology, the number of wavelength, the number of transceivers in each node and the traffic matrix under the constraint of transparent length is studied. This problem can be formulated as a MILP. This MILP can only be solved for small networks, therefore a heuristic algorithm based on K-least-wavelength-weight-path routing and statistical method is proposed for large networks. From the simulation in small networks: i.e. 7-node random networks and a 7-node ring network, we can find that the heuristic algorithm yields optimal results in most cases. The MNECs realized by the heuristic algorithm vary when the lightpaths are arranged in different orders and the As order has the best results. The ability of the heuristic algorithm to handle large networks makes it suitable for use in a route engine as well as in a network design tool.