1. Introduction

Research is underway currently to develop intelligent control planes for the next-generation optical mesh networks, which can provide customers with automatic, flexible, and real-time provisioning as well as enhanced network survivability and interoperability. Besides, in the large-scale optical networks nowadays, sometimes several carriers providing their bandwidth resources determine an inter-domain lightpath, even another inter-domain backup lightpath, for traffic connection between customers. Since each carrier has its own policy and will not open the specifics of its network for commercial secrecy, an inter-domain routing algorithm is concerned to exchange routing information among the carriers and solves the problem above. International standardization organizations have constituted the standard so as to achieve the communications among each AS, such as Optical Border Gateway Protocol (OBGP) [1] and Domain to Domain Routing Protocol (DDRP) [2].

Routing optimization is to solve the problems of how to improve the performance of the whole networks under multi constraint condition, for instance the aspects of blocking probability of traffic requests and average network congestion degree with an acceptable convergence speed, besides how to determine an optimal path. Inter-domain routing optimization is a more complicated problem, because the establishment of the optimal path is considered according to not only traditional intra-domain but also inter-domain. So the cost connection between inter-domain and intra-domain must be concerned. To routing optimization, another crucial problem is diverse routing calculation for network survivability demands. It emphasizes on how to obtain an optimal pair of working path and backup path.

Inter-domain routing for OBGP based on the Optimal Path Identifier has been proposed in [3]. The traditional approach on inter-domain routing for DDRP utilizes the Modified-Dijkstra algorithm, which is applicable for intra-domain routing originally. This algorithm returns one single optimal routing at a time, so a Maximally Disjoint Path (MDP) algorithm [4] is adopted in intra-domain diverse routing calculation for path protection. In the MDP algorithm, the optimal routing for the working path and the backup path is calculated in sequence, which complicates the routing calculation. Of particular note is that sometimes the backup path cannot exist. For example in Fig. 1, each Domain Controller (DC) speaks for a domain and can be seen as the topology abstract node of the domain. The working path between DC1 and DC7 is given DC1->5->6->7 based on the Modified-Dijikstra algorithm; however the backup path cannot be obtained in the modified graph after the working path done.

 

Fig.1. An example for the comparison of MDP and SATORA

Download Full Size | PDF

The traditional algorithms of Dijkstra and MDP can obtain the optimal path with shortest path first, and only focus on how to achieve the diverse routing calculation with one single constraint with a polynomial time complexity of O(N)². However, the routing optimization in the actual optical networks becomes a NP-complete problem subject to multiple constraints, such as the length and the hop count of the path, the delay and the congestion of the link, and so on. Some heuristic algorithms, for instance Simulated Annealing (SA) algorithm and Genetic Algorithm (GA), can be utilized to solve the problem. The GA-based routing algorithm in optical networks has been given in [5]. Some researches based on the SA algorithm have been carried out to design an excellent static logical topology for optical networks [6-8] or for single-domain network survivability [9]. However all of them are not for the real-time and distributed routing and not for multi-domain optical networks either.

For the routing calculation under multi-constraint condition, the present work proposes a novel routing algorithm based on the SA algorithm, according to which a SA-based Two-steps Optimization Routing Algorithm (SATORA) is advanced to meet the inter-domain routing, and an improved SATORA is presented for multi-domain network survivability. In the SATORA, the calculations of the inter-domain routing and the intra-domain routing in the domains on the inter-domain path are implemented in sequence by invoking the SA-based routing algorithm separately. Since the SATORA can gain multi global optimal solutions synchronously, it can supply an inter-domain optimal diverse routing for dedicated or shared path protection in multi-domain optical networks. In Fig.1, the working path can be calculated as DC1->2->3->6->7 while the dedicated backup path DC1->5->8->9->7 according to the SATORA.

The rest of the paper is organized by five sections as follows. The network model is described in Section two. Section three focuses on the SA-based routing algorithm and the SATORA, including the evaluation function and the content of the routing algorithm. Based on the approach of SATORA, a developed diverse inter-domain routing algorithm is discussed in Section four. Simulation experiments on three kinds of multi-domain network topologies are shown in Section five, and then the numerical results and analyses are reported. Conclusion is given in the last section.

2. Network model

The network is represented by a directed graph G (V, E), where V is the set of nodes and E is the set of links. N and L stand for the number of network nodes and links, respectively, i.e. N=|V| and L=|E|. P={S= v ₀, v ₁ ,…, D=v_n} is a path between the source node S and the destination D. Here, v_i∈V and (v_i, v_{i +1})∈E, and n+1=|P| is the hop count of P. The number of wavelength in each link is all assumed |W|, and a graph G_w is given for each wavelength w. The initial network resources are assumed unoccupied, so ∀i, j(i≠j), G_i=G_j initially.

Two types of graph should be taken into consideration in the multi-domain optical networks. One is the G_Intra for intra-domain graph, in which V and E are composed of veridical nodes and links in a domain. The other is the G_Inter for inter-domain graph, in which v_i∈V is the topology abstract of domain i, such as the DC in Fig. 1, and (v_i,v_j)∈E represents the inter-domain adjacency between domain i and domain j. The number of nodes in the graph G_Intra is denoted N_Intra while N_Inter in G_Inter.

The model has two styles of resource matrixes. The inter-domain two-dimensional matrix M_Inter (i, j) describes the inter-domain connectivity and the utilized wavelength information of each inter-domain link and is shared in all the DCs in the networks. Each row in M_Inter (i, j) consists of Link ID, Local DC ID, Remote DC ID, Local Node ID, Remote Node ID, Reverse Link ID, and Wavelength 1 to |W|. The intra-domain two-dimensional matrixes M_Intra (n,w,i,j),1≤n≤N_Inter,1≤w≤|W| maintains the connectivity in domain n at wavelength w, and the matrix element (i, j) indicates the connection information of a unidirectional link (v_i,v_j), in which 0 means connected and unoccupied, 1 or other positive numbers mean connected and occupied, and -1 means unconnected.

3. Description of SATORA

3.1 Evaluation function

SA algorithm requires an evaluation function on E(P,G)to estimate the cost of a lightpath P under the topology graph G. The function is also abbreviated to E(P), which is estimated by the length, the hop count, the delay in the path P, or the congestion in the network. Thus, the optimization objective is {P| minE(P)}.

In this paper, two major factors are considered to determine the evaluation function E(P), the hop count of the path and the congestion degree of the network with the coefficients of α and β respectively in the multi-criteria constraint. Accordingly the expression of E(P) can be described as

Here, the hop count E ₁(P) is equal to |P|, and the network congestion degree E ₂ (P) is the occupied wavelength number in the busiest link, i.e. the maximum number of occupied wavelength among all the links in the current network.

3.2 Initialization routing algorithm

We assume that the number of the outgoing links in each node v_k is a variable value expressed by link_nums, and the ith outgoing links in node v_k are described as link i. The original path P={S=v ₀} presumes only the source node S included, and the initial hop_count of P is 1. And then the nodes v ₁, v ₂,…, D=v_n are acquired in turn by searching the matrix M, and form the initial path P={S=v ₀, v ₁,…, D=v_n}. The process above is a circle operation. For the operation of the current node v_k, each time of the circle is described in Fig. 2. If the node v_k is accepted at the end of this time of the circle, the next time of the circle is for the node v_{k +1}, otherwise for the node v_{k -1} for the node v_k is rejected. The end of the circle is on the condition that the hop_count is zero when no routing returned, or the next hop is the destination node D=v_n when obtaining a routing.

 

Fig. 2. Flowchart of initialization routing algorithm

Download Full Size | PDF

During the above procedure, we make a circle calculation for the initialization routing more than once, e.g. ten times, and select the path P _min with the minimum evaluation function E(P _min) as the optimal initial solution in order to accelerate the convergence of the following routing algorithm based on SA.

3.3 Routing algorithm based on SA

The SA-based routing algorithm presented in the paper can be expatiated on in Table 1. To avoid losing the optimal solution, we utilize a pair of values, P_opt and E_opt to memorize the current optimal solution. After the initialization course, the current solution P is regulated to P_opt step by step with the temperature t decreasing from t ₁ to t ₁=α ^I-1 t ¹. Here, I is a given value of the iterative times and α is a common value between 0.8 and 0.99.

Table 1. The SA-based routing algorithm

View Table | View all tables in this article

Two approaches are considered to change the path P={S=v ₀, v ₁,…, D=v_n} with another path P′ randomly, as described in the step 2-1 in Table 1. The first is that, randomly create a pair of integers (i, j) between 0 and n, and then compute a new path (v_i,v′ _i+1,…,v_j) from node v_i to node v_j to attain the replacing path P′={S=v ₀, v ₁,…, v_i,v′ _i+1,…,v_j, …, D=v_n}. The second is that, compute the replacing path from node S to v_n, n-v ₁,…, v ₁ in turn, and then attain the replacing path P′ between node S and node D. Both the approaches are on the assumption that unleashing the occupied resource of the original path P to obtain the authentic replacing path P′, and require that the path P′ without loop is distinct from the path P. The approach adopted in our study is the first one.

3-4 SATORA

In the SATORA, the routing optimization has two steps. In the first step, the SA-based routing algorithm is invoked to attain the optimal inter-domain routing between the source DC and the destination DC under the graph G_Inter. In the second step, on receiving the remote request from the source DC, each domain along with the inter-domain path calculates the optimal intra-domain routing between the incoming node (or the source node) and the outgoing node (or the destination node) in the domain by the SA-based routing algorithm again. And then it delivers the optimization solution of intra-domain to the source DC. So the evaluation function E(P,G)can be formalized as

where the first term represents the evaluation of the inter-domain routing while the others evaluate all the intra-domain routings along with the inter-domain path P_Inter. The parameters of Φ and Ψ can be regulated, e.g., the case of Φ=1 and Ψ=0 means the optimization objective is evaluated by the inter-domain routing exclusively.

To adapt for the non-wavelength-conversion networks, the algorithm of SATORA acquires all the optimal routing solutions based on distinct wavelengths, in other words, the wth optimal routing solution P_w utilizes wavelength w under the graphs of G_Inter,w and G_Intra,w. And then compares and selects the optimal wavelength routing among the solutions according to the evaluation function

The SATORA is described as follows.

Table 2. The SATORA

View Table | View all tables in this article

To testify the routing algorithm, a common backward-reservation inter-domain signaling scheme is combined with the SATORA. During the course of reservation phase from the destination to the source, the graphs of G_{Inter,w_opt} and G_{Intra,w_opt} are modified.

4. Improved SATORA for dDiverse inter-domain routing

We have achieved the inter-domain path protection by improving the SATORA with a memorized Pair_opt=(P_wr,P_br), since the failure of a domain or an inter-domain link may result from the admission control among domains or the other common reasons. During the course of routing optimization, the SATORA can obtain more than one global optimal solution, so it can be used for diverse routing, e.g., the best path as the working path and the second best path as the backup path. However, the SATORA cannot ensure that these two paths are link-disjoint, that is to say, the backup path has some links in common with the working path. This induces that the diverse routing between the S-D DC pair is lost. We have improved the SATORA to perform the dedicated-path protection, which is described in Table 3. To solve the above problem of no link-disjoint, when a new better working path P_{wr_new} is found without its compatible backup path P_{br_new}, the current temperature t backfires to the initial t ₁.

Table 3. The improved SA-based routing algorithm for diverse routing

View Table | View all tables in this article

In the SATORA, the above algorithm is used in the first step of the two-steps approach, that is to say, it calculates the optimal inter-domain diverse routing only. The comparison of all the optimal solutions based on distinct wavelengths is just performed by the evaluation function of the working path E(P_wr) in the paper. The following research will consider applying the evaluation functions of both E(P_wr) and E(P_br).

5. Simulation and numerical results

Three multi-domain network topologies are seen in Fig. 3. Between the two adjacent domains, there is only one inter-domain link in the network TOPO1 while more than one in TOPO2. Different from these two topologies, the details of the intra-domain topology is not given out in TOPO3. A domain is regarded as a node in TOPO3, NSFNET. Both two steps of the SATORA are run in TOPO1 and TOPO2. However, only the first step of the SATORA is performed, and the SA-based routing algorithm is invoked once for inter-domain routing calculation in TOPO3, NSFNET. So we can utilize NSFNET to testify the SA-based routing algorithm and the improved one for diverse routing. The simulation experiment is carried out in the networks with 8 wavelengths (|W|=8) in each bidirectional fiber.

 

Fig. 3. Simulation network environment: (a) and (b) N_Inter=9; (c) N_Inter=14.

Download Full Size | PDF

In our simulation experiment, the traffic call requests for bidirectional lightpath are considered to arrive at the multi-domain networks according to an independent Poisson process with arrival rate λ. The s-d node pair (source DC_ID/Node_Number, destination DC_ID/Node_Number) is chosen randomly based on a uniform distribution. The traffic connection duration is negative exponentially distributed with mean $\frac{1}{\mu }$. Thus the network traffic load is $\rho =\frac{\lambda }{\mu }$. Note that a node may engage in multiple calls and several calls may be accommodated simultaneously between an s-d node pair. The simulation ignores the effects of signaling scheme, that is to say, only the impact of routing algorithm for call requests is considered, so it is assumed that the mean interarrival time of call requests $\frac{1}{\lambda }$ is far larger than the mean end-to-end delay of call setups $\frac{1}{\theta }$.

It can be seen from Fig.4 that the blocking probability changes with the network load in the SATORA that operates the inter-domain routing or dedicated-path protection under two kinds of network, TOPO1 and TOPO2. An appropriate set of the parameters α, β in Eq. (1) and Φ, Ψ in Eqs. (2) and (3) is that (α,β,Φ,Ψ)=(2,1,2,1) in Fig. 4. As a result, the blocking probability in TOPO2 is much lower than that in TOPO1. The simulation indicates that adding inter-domain links between two adjacent domains can reduce the blocking probability by one order of magnitude averagely. Besides, the blocking performance is worse for about two orders of magnitude in the case of path protection with the SATORA in both topologies.

 

Fig. 4. Blocking probability vs. network traffic load for SATORA

Download Full Size | PDF

The comparison between the MDP algorithm and the SATORA on the dedicated-path protection is given in Fig. 5 and Fig. 6, as the eight curves shown. The curves are obtained respectively based on different network topologies and different parameters α,β,Ψ and Ψ. According Fig. 5, we can draw a conclusion that the SATORA used to the diverse routing is a little better than the MDP algorithm on the blocking performance when the network traffic load is under 20 erlang in TOPO2. Moreover, the improving extent of the performance is increased with the networks traffic load decreasing, e.g., 2.6% at 20 erlang, 9.8% at 10 erlang, and 48% at 6 erlang. In TOPO3, we also find the same conclusion, 3.0% at 10 erlang, 9.4% at 8 erlang, and 30% at 6 erlang. When the traffic load is reduced more, the blocking probability in the MDP and the SATORA is both verging on zero. However, with the load increasing to almost 25 erlang, the blocking probability reaches almost the same, because some traffic requests blocked by the MDP is made a detour and set up in the SATORA, which expends overfull network resources and influences the following requests. From Fig. 5, the parameters α,β,Φ and Ψ have a little influence on the blocking performance, and the optimal (α,β,Φ,Ψ) is (2,1,2,1) in TOPO2 and is (2,1,1,0) in TOPO3. Considering no intra-domain routing in NSFNET, the simulation sets Ψ=0 in TOPO3.

 

Fig. 5. Comparing SATORA and MDP for path protection in blocking probability

Download Full Size | PDF

 

Fig. 6. Comparing SATORA and MDP for path protection in network congestion degree

Download Full Size | PDF

We randomly choose 100 time sample dots for the duration of simulation and record the network congestion degree of time and the average for 1000 times calculation is illustrated in Fig. 6. In TOPO2 (or TOPO3), the average network inter-domain congestion degree for the dedicated-path protection in the SATORA is lower than that in the MDP algorithm under the network traffic load of 20 erlang (or 15 erlang). And the congestion degree in the MDP altorithm and the SATORA approaches on the whole when the traffic load is more than 25 erlang (or 20 erlang). It is because that the network resource is occupied fully at heavy traffic period. Of particular note is that the parameters α, β, Φ and Ψ have worked on the simulation results. The network congestion performance in the curves with (2,1,2,1) in TOPO2 and (2,1,1,0) in TOPO3 are better than the others in the same topology. The percent of improving extent between the SATORA with (2,1,2,1) and the MDP with (1,0,2,1) in TOPO2 is expressed as $\frac{E_2^{(2,1,2,1)}-E_2^{(1,0,2,1)}}{E_2^{(2,1,2,1)}}$, as described in Table 4. That between the SATORA with (2,1,1,0) and the MDP with (1,0,1,0) in TOPO3 is also in the following table. It is obvious that the improvement is the most when the network traffic load is 8 erlang.

Table 4. Improvement of the network congestion degree between SATORA and MDP

View Table | View all tables in this article

However, the routing calculation of the SATORA is not as fast as that of the MDP, because some circles is adopted to obtain a better network performance of blocking probability of traffic requests and average network congestion degree by the SATORA. To speed the convergence of calculation in the SATORA, we can determine a set of appropriate parameters, including the circle times of the initialization, the annealing times I in both inter-domain and intra-domain, and the circle times of changing both the inter-domain path and the intra-domain path. In our simulation experiment, the operation time of the SATORA is approximately twice on an average as long as that of the MDP in TOPO2, while three times in TOPO3, which is considered to be acceptable. The results also can be seen from Table 5.

Table 5. Operation time in SATORA and MDP

View Table | View all tables in this article

6. Closing remarks

For the first time we achieved real-time and distributed routing optimization based on the simulated annealing routing algorithm in optical networks. An inter-domain routing algorithm, SATORA, invokes the novel SA algorithm twice to achieve inter-domain optical routing calculation. It can also serve for inter-domain dedicated-path protection, and acquire the diverse working and backup routing by one routing calculation, instead of twice in the traditional Dijkstra-based MDP algorithm. Our present works can be applied for routing, especially inter-domain routing, and path protection as well in optical mesh networks. Experiment and analysis have shown that the SATORA can reduce the network congestion degree and enhance the blocking performance of routing calculation for traffic requests, compared with the MDP algorithm.

The present SA-based algorithm, SATORA, separates the inter-domain and intra-domain routing calculations into two steps, instead of integrating them. Considering the problem of global optimization of both inter-domain and intra-domain, integrating the routing of inter-domain and intra-domain may improve the network performances of blocking and congestion further. One method by improving the SATORA is that the inter-domain optimization is combined with the intra-domain optimization in each domain along with the inter-domain path. However the operation efficiency of the method may be much lower than the SATORA, because it is necessary to do a circle of changing the current inter-domain path many times in order to acquire the optimal solutions in the inter-domain optimization, which results in long time in the intra-domain routing calculation. Thus, the future work will focus on how to minimize the total cost of both inter-domain and intra-domain routing and how to decrease the routing operation time.