1. Introduction

In a wavelength-routed optical network (WRON) with limited number of wavelength, strategically placing converters at selected nodes can effectively increase the utilization of wavelengths and hence reduce the blocking probabilities of each channel. The converter placement problem aims to equip selected network nodes with converters based on the given traffic demand and number of converter such that the overall blocking probability of the network is minimized. The proliferation of wavelength-routing network and prohibitively expensive cost of wavelength converter have motivated numerous attempts to solve the NP-hard converter placement optimization problem. In [1], Gao et al. surveyed the significant researches related to this problem and presented an optimization model of the converter placement problem as minimization of a polynomial function of 0–1 variables under a linear constraint. Based on the model, Teo et al. introduced a PSO-based solver [2] to find the optimal solution of converter placement, which requires much lesser computation resources as compared to the search algorithm proposed in [1]. The major advantage of the PSO-based algorithm is that it is not necessary to build a search tree in finding the optimal solution, and that only a relatively small number of particle is needed to explore the huge solution space. Hence in terms of solution simplicity, BPSO outperforms all the previously proposed heuristics that in general require time-consuming organized search through the solution space.

Both of the optimization algorithms presented in [1] and [2] only consider the fixed single shortest-path routing, which is known to perform poorly for network resource provision. Single shortest-path routing, though computational less intensive, tends to route traffic along the already congested shortest paths between node pairs while leaving other longer uncongested paths under-utilized. To overcome the inefficiency of shortest-path routing, Foo et al. proposed the application of equal-cost multipath (ECMP) routing and traffic-engineering(TE)-aware shortest-path routing in converter placement problem [3]. These routing schemes guarantee higher level of network-wide load balance and resource utilization efficiency. Computed results in [3] showed that an optimization framework consists of TE-aware shortest-path routing and binary PSO (BPSO)-based algorithm is highly effective and efficient in reducing the blocking probability in sparse wavelength conversion networks.

Inspired by the NP-hard nature of the optimal routes-set selection, a strategic search heuristic is developed to further explore the effects of having different routing schemes on converter placement optimization. Simulations are carried out based on the 14-node NSFNET to verify the performance and effectiveness of the proposed heuristic.

2. Problem formulation

The system model is based on the network and traffic models described in [1]. The network is modeled as a directed graph G=(V, E), which consists of a set of nodes, V, and a set of directed links, E. The state vector (x₁ , x₂ ,…, x_n ) indicates the placement of converters on a network with n nodes. The binary variable x_i is set to be 1 if node i is equipped with a converter; 0 if otherwise. The blocking probability on a link l_ij connecting node i and j is defined as the probability that a specific wavelength on this link is occupied. The blocking probability ρ_ij can be computed by:

where F is the number of wavelengths on each link; ${\lambda }_{\mathit{\text{st}}}^{\mathit{\text{ij}}}$ is the end-to-end traffic load from node s to node t, which also represents the arrival probability of a call from s to t.

The overall success probability of this model can be represented by the geometric average which is defined as:

where P_st is the path between node s and node t on which λ_st (the traffic load from s to t) is routed. S(P_st ) is the end-to-end success probability of a call on path P_st . The segment of the path, d, is the set of links between two consecutive converter nodes; or between an end node and its nearest converter node in the path. Given traffic matrix T and k converters, the optimization objective is to determine the values in (x₁ , x₂ ,…, x_n ), so that the overall blocking probability of the network is minimized, or conversely, the overall success probably of the network is maximized.

3. Converter placement optimization

3.1 ECMP and TE-aware shortest-path routing

Single shortest-path routing is known to be a poor network resource provisioning scheme as it inevitably causes the traffic congestion on the few shortest paths. A popular approach used in internet routing protocols, equal-cost multipath (ECMP) routing, attempts to overcome this problem by selectively forward traffic onto alternate paths with the same cost. However, ECMP routing does not always minimize the maximum link load if multiple paths are not chosen carefully for the global traffic demand. An alternative approach would be to examine all the possible routes between every source and destination pair, compute the loads on each link for the chosen route, and select the set of routes that best maintains the network-wide load balance. Obviously this approach is infeasible as the number of candidate routes between any source-destination pair will grow exponentially with network size, resulting in another NP-hard problem. TE-aware shortest-path routing addresses these design constraints by selecting a single shortest path from all possible shortest paths for each node pair such that the maximum link load is significantly reduced. Experimental results in [4] confirm that even though TE-aware shortest-path routing uses a single path, it is capable of achieving near-optimal solution in a mesh network topology with a typical traffic demand matrix. It has also been shown by experiments that, even in the case of a small number of equal-cost multiple paths, TE-aware shortest paths are effective in reducing the maximum link load.

A two-step integer linear programming (ILP) formulation of the TE-aware shortest-path routing problem is presented in [4]: the first step calculates the weight of the shortest paths by minimizing the sum of the integer link weight, and the second step minimizes the maximum link load among the possible sets of shortest paths that satisfy the minimum weight of the shortest paths found in the first step. A simple heuristic algorithm [4] is then applied to solve large instances of this problem based on the information of all the available equal-cost multiple shortest paths. The steps included in the heuristic are:

• [Step 1] Calculate ECMPs for all node pairs.

• [Step 2] Initialize a random set of single shortest paths that satisfy the destination based forwarding rule.

• [Step 3] Find the set of flows, {F_i }, over the most congested link l_c , with the maximum link load, L_max .

• [Step 4] For each candidate flow, F_i , select an alternate path, and determine “induced flows” that also have to change their paths to meet the destination-based forwarding rule.

• [Step 5] If by swapping paths of F_i and induced flows determined in [Step 4] can reduce L_max , exchange the current shortest path with the alternate path.

• [Step 6] Mark F_i as examined.

• [Step 7] If the new congested link is different from l_c , go to [Step 3].

• [Step 8] If the flows to be examined remain in {F_i }, go to [Step 4]; otherwise, terminate.

3.2 Particle swarm optimization (PSO) algorithm

After the network connectivity topologies have been derived, BPSO is used to solve the NP-hard converter placement problem. The original PSO algorithm is a parallel evolutionary computation technique developed by Kennedy and Eberhart [5] based on the social behavior metaphor. Unlike other evolutionary optimization methods, such as Genetic Algorithm (GA), PSO requires relatively small amount of computation resources since it does not rely on crossover and mutation processes. The algorithm is initialized with a population of random candidate solutions, conceptualized as particles. Each particle is assigned a randomized velocity and is iteratively moved through the problem space. It is attracted towards the location of the best fitness achieved so far by the particle itself and by location of the best fitness achieved so far across the entire population.

In the system model of our study, a node will either be equipped with 1 converter or none. Using the binary codification, the string ‘10010’ indicates the presence of converters at first and fourth node of a 5-node network. Hence the converter placement problem can be formulated as a binary programming problem and be solved by BPSO. The pseudocodes of the BPSO algorithm incorporated in the optimization process are shown in Table 1.

Table 1. Algorithm for BPSO-based converter placement problem solver

View Table | View all tables in this article

4. Strategic search heuristic

ECMP and TE-aware shortest-path routing schemes are both designed based on the likelihood that the set of routes which best minimizes the maximum link load can be derived among a set of k-shortest candidate routes. With this insight, we propose a search method that will further explore the possible routing configurations based on the given traffic demand matrix and multiple equal-cost shortest paths (ECSP) between source-destination pairs. The heuristic starts by identifying all the ECSP between each node pairs and arranges these paths using either ECMP or TE-aware shortest-path algorithms. When ECMP is applied, the ECSP are sorted according to the sequence for which these paths are identified. For TE-aware sorted multiple paths, the first path in each ECSP sets will produce the minimum link load according to [4]. The maximum number of sorted ECSP to be included in the search is set according to the network size. For the case of NSFNET, the maximum number of sorted ECSP is chosen to be 3. Each path between node s and node t is labeled as A_st , B_st , and C_st respectively. Different sets of network connectivity topology are derived using all the possible combinations of these paths as shown in Table 2.

Table 2. Search heuristic for single shortest-path connectivity topology

View Table | View all tables in this article

From Table 2, it can be seen that a total of 3!=6 connectivity topologies can be derived using the ECSP in this case. The heuristic exploits the simple fact that there always exists different number of shortest-paths between node-pairs. By systematically choosing and combining these shortest-paths, a single shortest-path routed topology is produced. The search algorithm aims to provide connectivity topologies which might lead to a network with lower blocking probability after wavelength converters are placed by the BPSO-based solver. The proposed heuristic will also be evaluated based on the efficiency η, which is defined as:

where N is the total number of network nodes, k is the number of wavelength converters, $C_k^N$ is the binomial coefficient; and α is the number of attempts needed to find the optimal placement of the wavelength converter in order to obtain the minimum blocking probability.

5. Results and discussions

Simulation experiments are conducted by applying the ECMP, TE-aware shortest-path routing, as well as the proposed search heuristic to the 14-node NSFNET with the same traffic demand matrix used in [1] and [2]. The traffic loads are converted into the probabilities of call arrivals accordingly based on Eq. (1). Each call requires a full wavelength on each link that it traverses. For all experiments, it is assumed that there are 5 wavelengths on each of the 21 physical links of NSFNET. Traffic load on each link is nonuniform due to the varying traffic demand and selected route between all node-pairs. Hop-based calculation is employed to determine the shortest path for every route. All analyses are based on the assumption that random wavelength assignment and fixed routing are being simulated in the experimental network. After the connectivity topology is determined, BPSO is used to strategically equip the selected nodes with the available converters. Computations are performed off-line since the converter placement problem considered in this study is a static configuration problem.

 

Fig. 1. Blocking probability vs. number of wavelength converters, k

Download Full Size | PDF

Figure 1 shows the comparison between the blocking probability of each network generated by the selected topologies. In Fig. 1, ECMP0 and TE0 represents the topology obtained originally using ECMP and TE-aware shortest-path routing, respectively. Based on the relatively high blocking probability of ECMP0, it is obvious that the standard ECMP is not the best method in deriving network connectivity topology on which the optimal placement of converters will be determined by BPSO. The proposed search heuristic is then applied to both the original set of paths generated by ECMP and TE-aware shortest-path algorithms. Different connectivity topologies are produced based on the path selection pattern as described in Table 2. For example, TE1 is derived by applying the path selection criteria set1 in Table 2 to the set of TE-aware sorted multiple paths. As evident from Fig. 1, few newly generated topologies TE1, ECMP4, and ECMP5 result in lower blocking probability after the BPSO is employed to equip the network with fixed number of wavelength converters. Comparing the results obtained by TE0 and TE1, the TE1 exhibits more strength especially when the given number of converters is less than half of the network size. Both ECMP4 and ECMP5 outperform the standard TE0 regardless of the number of converters assigned.

 

Fig. 2. Efficiency η vs. number of wavelength converters

Download Full Size | PDF

To further compare the performance of the strategic search heuristic, Eq. (3) is used to calculate the efficiency of the optimization process that has been performed on each of the selected connectivity topologies. A plot of efficiency versus the number of converters for the different topologies is shown in Fig. 2. It can be seen from Fig. 2, that on average the highest efficiency is achieved when placing converters optimally on TE1. In general, the efficiency of the BPSO-based technique is low for small $C_k^N$ since all possible combinations of the converter placement patterns are likely to be attempted during the search, regardless of the topology used. It can be observed from Fig. 2, that in the range of 4≤k≤9, all the topologies included in the experiment have the chance of yielding optimization process with efficiency exceeding 90%. Computed results shown in Fig. 1 and Fig. 2 imply that the proposed search heuristic is effective and efficient in producing network connectivity topology that will result in the further reduction of blocking probability in sparse wavelength conversion network. Since the proposed solution is based on off-line computation, new results can be obtained by repeating the simulation when given arbitrary physical network topologies and the corresponding traffic demand matrices.

6. Conclusion

We presented a highly effective search method in deriving network connectivity topologies that stand higher chance to produce a sparse wavelength conversion networks with lower blocking probability. Experimental results indicate that our search method, when combined with the optimization framework proposed in [3], outperforms both the standard ECMP and TE-aware shortest-path based approaches. The results provide interesting insights to key issues that have direct impact on the performance of wavelength-routed optical networks. Possible extensions of this work include improving the model and technique used to solve the converter placement problem by taking into account the effects of applying different load-balancing heuristics into the optimization framework.