The problem of how to upgrade translucent optical networks is studied in this paper. This study is motivated by the cost advantage of not having network nodes fully equipped with transceivers in the beginning of network deployment but adding transceivers as and when it is necessary. A novel heuristic algorithm for the selection of nodes to upgrade (by adding transceivers) based on the transitional weight of the nodes and the length of the links is proposed. Spare transceivers in the nodes can be used to regenerate signals. An algorithm for locating the regeneration nodes in the network is also proposed. The proposed upgrade node selection algorithm is studied with the regeneration node selection algorithm and a wavelength weighted routing algorithm by means of numerical simulations. Simulation results show that upgrading translucent optical network by means of the proposed upgrade node selection algorithm has lower blocking probability and cost advantage compared to other strategies.
© 2003 Optical Society of America
Wavelength division multiplexing (WDM) optical network is likely to be the backbone of future communication network. Although most people are optimistic about the emergence of an all-optical global-scale optical network, they must address the technical difficulties of overcoming the signal degradation introduced by the physical impairments such as amplified spontaneous emission noise, dispersions, optical fiber nonlinearities, etc. In reality, there is no satisfactory method to overcome these impairments without Optical-Electrical-Optical (OEO) conversion. Therefore, selective regeneration may be required if the transmission path length exceeds the available transparency length (‘reach’). These types of optical networks in which each node routes some lightpaths transparently while subject others to go through the regeneration are known as translucent optical networks .
One approach for 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 between different islands, however, regeneration nodes are used at the island boundaries to relay the lightpaths across the island boundaries . Another approach is called sparse placement of regeneration nodes in the network. For this approach, a number of selected nodes within the entire network will be used for regeneration . Although the two approaches contribute to the performance improvement, the hardware cost of the network increases. Also, offline allocation does not utilize the full potential of regeneration resources.
Each optical node consists of an optical cross connect (OXC) and an access station. It is first pointed out in  that regenerators can share resources with access stations. Since in most cases, it is unlikely that channels that are initiated and terminated at a node will use up all the transmitters and receivers in the access stations, many nodes will have spare transceivers available for regeneration purpose. So, it is not necessary to place extra transceivers at selected nodes simply for regeneration. Every node with spare transceivers can become a potential regenerator . This is the kind of network that we are looking into.
To minimize upfront capital investment, most operators would prefer not to fully equip the network nodes with transceivers in the beginning of network deployment. More transceivers can be added to the nodes in an incremental manner as and when traffic demand increases. In this context, the adding of transceivers to a network node will be referred to as upgrading. This in turn raises the problem of choosing the most appropriate nodes to upgrade. To the best of our knowledge, none of the literature considers the upgrading problem of this kind in translucent optical networks. In this paper, an upgrade node selection algorithm is proposed to sequence the nodes for upgrading. A regeneration node selection algorithm is also proposed to select the transceivers in the access stations for regeneration. The two algorithms are studied with a wavelength weighted (WW) routing algorithm.
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 the receivers (Rx) are in the access station. The 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 can not only drop optical channels but also add optical channels to the network. Tx and Rx can be grouped into three sets: TA, RA and TRRR. If a channel is originated from the node, it enters the network through the TA set. If a channel is terminated at the node, it exits via the RA set. If the channel traverses an intermediate node and needs regeneration, it enters and exits the node via a TxRx pair in the TRRR set .
Each node is equipped with a number of fixed-wavelength transceivers with different wavelengths, and we assume that the transceiver λi can only receive and transmit at λi . Wavelength conversion is not considered. Let N be the number of nodes and L be the number of links in the network. Two adjacent nodes are connected with one pair of unidirectional fibers to provide bi-directional connectivity. Let W be the number of wavelengths that can be used in the network and that all links are designed to carry all the W designated wavelengths. Let M be the number of transceivers for each wavelength in each node. Ls is the transparent length (the maximum transmission length in the optical domain). If the length of a lightpath is larger than Ls , then the lightpath has to be regenerated in one or more intermediate nodes such that the distance between two adjacent regeneration points is less than or equal to Ls .
3. Upgrade node selection algorithm
Given that a network has N nodes and we need to select K nodes for upgrading, there are possible combinations to evaluate. This number will escalate quickly when the network size increases, e.g. there are over a million possible combinations if we want to upgrade 5 nodes of a 45-node network. Hence, a carefully thought-out heuristic algorithm is necessary. A lot of prior works consider the placing of electrical regeneration nodes or wavelength conversion nodes within a lightpath-routed network [3, 5]. After careful examination of these approaches, we propose a heuristic algorithm that will consider not only how ‘central’ a node is in the network but also the influence of the link spans (lengths) since transceivers will also need to be used for regeneration.
It is logical to think that the most promising candidate for upgrading is the node most ‘central’ in the network [3, 6]. The term ‘central’ means that the node has the largest number of lightpaths passing through it. Here, we measure how central a node is by means of a parameter called transitional weight (TW). Let be a parameter that assumes the value of one if the route between node pair s and d transits through node k; otherwise, it takes the value of zero. Also, is defined to be zero for k=s or d. TW of an arbitrary node k is defined as:
When we calculate the transitional weight of each node, the WW routing algorithm is used. For each additional channel (or lightpath) transported by a link, the weight of the link increases by 1. The route for a new lightpath is the route between the source-destination node pair that has the least weight. Here we assume that the transparent length is infinite and regeneration is not considered. Certain number of connection requests is used for transitional weight computation. The connection requests are uniformly distributed in the network. After the computation, a group of Ck can be obtained, and a node with a larger TW has a higher priority to be upgraded.
Since the transceivers in the access stations of network nodes will also be used for regeneration, the longer the length of a link, the transceivers in the nodes at both ends of the link will have a higher probability to be used for regeneration. Therefore, link lengths should also be considered in the upgrade node selection.
First, we sort all the N nodes in descending order of Ck . We define Pk as the index (order) of node k in the TW sequence. Second, we sort all N nodes in descending order of the lengths of the links they terminate. Since a node may have several links of different lengths, there are multiple entries for each node in the sequence. For the multiple entries for a node k, we define Qk as the entry that has the smallest index in the length sequence. Note that the two nodes at both ends of a link may have the same value.
We define a new weight factor Fk for node k:
where α is a parameter which can be assigned a value in the space of [0, 1]. If α=1, the upgrade node selection is determined solely by TW. If α=0, the upgrade node selection is determined solely by length. If α is assigned a value between 0 and 1, we can sort all N nodes in ascending order of Fk , and define this sequence as a TL sequence. An arbitrary node k that has a smaller value of Fk has a higher priority to be selected for upgrading.
We use the NSFNET model shown in Fig. 2 as an example for illustration and experimentation. The length of each link in km is labeled beside the link.
In order to calculate the TW of the nodes, 10,000 connection requests are uniformly generated for the network. The normalized TW of each node is shown in Fig. 3 by using the WW routing algorithm. Then the sequence obtained by sorting the nodes in descending order of Ck is shown in Row 2 of Table 1. It can be seen from Fig. 3 that a node with more ports has a larger value of Ck , e.g. node 6 and 11 have 4 ports and also have the largest Ck , while node 7 and 14 have 2 ports and have the smallest Ck . Therefore, nodes 6 and 11 have higher priority to be upgraded in the TW strategy.
While in the strategy in which only link length is considered, the sequence in descending order of the link length is given in Table 2. Recall that Qk is the smallest index of node k in the length sequence. For exemplification, let us consider node 9. There are three links terminated at node 9 and these links are ranked 1st, 7th, and 16th in Table 2. Since the lowest index among 1, 7 and 16 is 1, Q9 =1. Similarly, Q4 =1, Q2 =Q8 =2 and Q6 =Q13 =3, etc.
If the value of α is given, Fk for each node k can be obtained. Table 1 shows the sequence for TW and TL (α=0.5). For example, the index of node 11 is 2 in the TW sequence (Table 1) and 4 in the length sequence (Table 2), P11 =2 and Q11 =4, when α is 0.5, F11 =0.5×2+0.5×4=3. Similarly, P4 =4 and Q4 =1 and F4 =0.5×4+0.5×1=2.5 for node 4. Therefore, in the TW sequence, node 11 has a higher priority than node 4 to be selected for upgrading, but in the TL sequence, node 4 has a higher priority to be selected.
4. Routing and wavelength assignment algorithm
Wavelength routing consists of routing and wavelength assignment. Here the WW routing algorithm is chosen for connection request establishment. The first-fit (FF) wavelength assignment algorithm is used. From λ1 to λw , if λi (1≤i≤W) is available along the selected route and if the total length is shorter than Ls , λi is assigned to the call and the connection is established. If the length of the route is larger than Ls , then the lightpath should be regenerated in some intermediate nodes. We use the following regeneration node selection algorithm.
Assume that the nodes in the route are numbered as S, 1, 2, …, k, …, T, where S and T are the source node and destination node respectively. The number of free transmitters and receivers for λi from the intermediate node 1 to node k can be obtained. Define cost1m ≡min(nTx (m), nRx (m)) and cost2m =max(nTx (m), nRx (m)), where m:1≤ m≤k and nTx (m) and nRx (m) are the number of free transmitters and receivers respectively. From node 1 to the intermediate node j, where the length from S to j is smaller than Ls and the length from S to j+1 is larger than Ls , the node that has the largest cost1 is selected as regeneration node. If multiple nodes have the same cost1, the node that has the largest cost2 is selected. If more than one node have the same cost1 and cost2, the node that is farthest away from S is selected. Then, the regeneration node is set as the source node and the procedure is repeated until the length between the regeneration node and the destination node T is smaller than Ls . If none of the intermediate nodes has free λi transceivers, then the search procedure is terminated and the next wavelength λi+1 is checked. If all the wavelengths are checked but none is available, then the lightpath connection request is rejected.
The computational complexity of the routing and wavelength assignment algorithm is O(N2×W×L).
5. Numerical results
The NSFNET is used for the simulation studies, and we have made the following assumptions:
- Uniform distribution of lightpath connection set-up requests throughout the network.
- The generation of connection requests for the whole network is governed by a Poisson process. Once established, a lightpath is held for a negative exponentially distributed time with a mean of unity.
- First 10,000 connection requests are used for network warm-up, and then blocking probabilities are estimated for subsequent 100,000 connection requests.
The value of α is determined by the network topology and the transparent length. In NSFNET, when the transparent length is 3,000km, we find that α=0.5 gives the lowest blocking probability for different number of upgrade nodes. Figure 4 shows the relationship between the blocking probability and the offered network load for the two upgrade node selection algorithms, when the network is upgraded from M=1 to M=2. It can be seen from Fig. 4, for different number of nodes selected for upgrading (2, 3, 5, 7, 10), the TL algorithm always yields better results than those of the TW algorithm. When the number of upgrade nodes is 2 or 3, the difference between the two strategies is small but when the number of upgrade nodes is 5, the difference becomes larger. The difference in node selection between the two strategies is that node 5 is selected for upgrade in the TW strategy while node 9 is selected in the TL strategy. Though node 5 has a higher transitional weight than node 9, node 9 is attached to the longest link in the network and the links connecting node 5 are all short. The transceivers in node 9 have a much higher probability to be used for regeneration; therefore, the blocking probability obtained in the TL strategy is smaller than that in the TW strategy. When the number of upgrade nodes is 10, the difference between the two strategies becomes small again. This is because residual nodes are less important due to their smaller TW or due to the shorter links attached to them; hence, their selections have less effect on the blocking probability.
Figure 5 shows the relationship between the blocking probability and the offered network load for the two upgrade node selection algorithms for different number of upgrade nodes, when the network is upgraded from M=2 to M=3. It can be seen from Fig. 5 that the TL strategy still yields better results but the difference between the two strategies is much smaller than that for the case of upgrading from M=1 to M=2 (Fig. 4).
In order to test the TL strategy further, we consider the case in which the same number of upgrade nodes are selected randomly. We first randomly select a group of nodes, which are to be upgraded from M=1 to M=2 or from M=2 to M=3 (node 7 and node 14 are not included, since the largest M of these two nodes is 2.). Then we run the simulation for the network to find the blocking probability. Following this, we randomly select another group again and repeat the same process. The results of the random selection strategy for ten five-node random selection cases, labeled as R1 to R10, are shown in Fig. 6 and Fig. 7 for upgrading from M=1 to M=2 and M=2 to M=3 respectively. It can be seen that the TL strategy performs significantly better than the random selection strategy (Av.R1-R10 is the average result of R1 to R10). These results provide further evidence that the TL strategy is indeed an efficient solution to the problem of selecting appropriate nodes for upgrading.
Another performance index used to compare the algorithms is to compare the increased traffic load that can be carried by a network after an upgrade for a given blocking probability constraint. Fig. 8 shows the difference between the increased traffic load after upgrading using the TL and TM algorithms when the blocking probability constraint is 0.01 and the network is upgraded from M=1 to M=2. It can be found that for different number of upgrade nodes, the increased traffic load by the TL algorithm is larger than that by the TM algorithm. That means more traffic load can be supported when the network is upgraded by the TL algorithm, and more revenue can be obtained.
Figure 9 compares the increased traffic loads after upgrading using the TL algorithm and the random selection strategy, when the blocking probability constraint is 0.01 and the network is upgraded from M=1 to M=2. The results for the random selection strategy are averaged over ten samples. It can be found that the increased traffic load by the TL algorithm increases much more quickly than that by the random selection strategy. The TL algorithm can therefore achieve the same level of performance with less upgraded nodes. For instance, the increased traffic load by upgrading 4 nodes in the TL algorithm is larger than those by upgrading 5 or 6 nodes in the random selection strategy. This clearly shows the significance of having a carefully designed upgrade node selection algorithm so that fewer transceivers will be needed to achieve the same performance, and thus cost can be saved.
Figure 10 shows the relationship between the blocking probability and the number of wavelengths for the two upgrade node selection algorithms, when the network is upgraded from M=1 to M=2. It is obvious that the blocking probability decreases with the increase of the number of wavelengths. It can be seen from Fig. 10 that, for different number of wavelengths, the TL algorithm always yields better results than those of the TW algorithm for the same number of upgrade nodes. Also, we can find that with the increase of the number of wavelengths, the difference between the TL and TW algorithms is also larger; this suggests that the performance of the TL algorithm improves with more wavelengths in the network. The same results can be obtained when the network is upgraded from M=2 to M=3.
In Fig. 11, we study the impact of the transparent length on the performance of the TL algorithm. The relationship between the blocking probability and the transparent length (Ls ) for the two upgrade node selection algorithms is shown in Fig. 11, while the network is upgraded from M=1 to M=2. Since the value of α is affected by the transparent length, we should therefore vary the value of α to optimally select the nodes for upgrade for different transparent lengths. It is obvious that the blocking probability decreases with the increase of the transparent length. It can be seen from Fig. 11 that when Ls is larger than 2500km, the TL algorithm has better performance than the TW algorithm, but when Ls is smaller than 2500km, the TL algorithm has little performance improvement over the TW algorithm. This may be due to the network topology that we study. We believe that TL algorithm is still effective for other transparent lengths in other networks. The same results can be obtained when the network is upgraded from M=2 to M=3.
In the above analysis, we do not consider wavelength conversion in the network. In the following, we test the TL algorithm taking wavelength conversion into account. To realize wavelength conversion, one method is to equip the nodes with wavelength converters; another method is to use tunable transmitters. In the latter case, the received signal can be retransmitted at other wavelength by tuning the lasers so that, wavelength conversion and regeneration can be realized simultaneously. Figure 12 shows the relationship between the blocking probability and the offered network load for the two upgrade node selection algorithms, when the nodes in the network are fully equipped with wavelength converters and the network is upgraded from M=1 to M=2. We can see that the TL algorithm still yields better results than those of the TW algorithm for different number of upgraded nodes. Compared with Fig. 4, the blocking probability in this case is much lower than that without wavelength conversion in the network. Similar results are obtained when the network is upgraded from M=2 to M=3.
Figure 13 shows the relationship between the blocking probability and the offered traffic load for the two upgrade node selection algorithms, when tunable transmitters are used and the network is upgraded from M=1 to M=2. We can find that the TL algorithm still yields better results than those of the TW algorithm. Compared with Fig. 4 and Fig. 12, the blocking probability in this case is lower than that without wavelength conversion (Fig. 4) in the network but higher than that when wavelength converters are fully equipped (Fig. 12) in the network. Similar results are obtained when the network is upgraded from M=2 to M=3.
In this paper, we study the approaches to upgrade translucent optical networks. We propose an upgrade node selection algorithm, which considers not only the transitional weight of the nodes but also the impact of the link lengths. The upgrade node selection algorithm is studied with a regeneration node selection algorithm and a wavelength weighted routing algorithm. Through simulation, we demonstrate that upgrading translucent optical network by means of the proposed upgrade node selection algorithm has lower blocking probability and cost advantage compared to other strategies.
This work can be extended in several directions. One is to study the effectiveness of the upgrade node selection algorithm for other kinds of traffic distribution, other than the uniform traffic distribution studied in our work. Another direction is to develop more sophisticated routing algorithms, which consider not only the wavelength usage of the links but also the usage of the transceivers in the nodes. Also, some kind of regeneration node selection algorithm can be proposed and compared with the algorithm proposed in this paper.
The authors would like to thank Dr. Teck Yoong Chai for the helpful discussion, Mr. Varghese Paulose for proofreading and editing this paper and the reviewers for their comments on improving this paper.
References and links
1. B. Ramamurthy, D. Datta, H. Feng, J. P. Heritage, and B. Mukherjee, “Transparent vs. opaque vs. translucent wavelength-routed optical network,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Washington, D.C., 1999), pp. 59–61
2. A. A. M. Saleh, “Transparent optical networking in backbone networks,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Washington, D.C., 2000), pp. 62–64
3. G. Shen, W. D. Grover, T. H. Cheng, and Sanjay K. Bose, “Sparse placement of electronic switching nodes for low-blocking in translucent optical networks,” OSA J. Optical Networking1, 424–441, 2002.
4. X. Yang and B. Ramamurthy, “Dynamic routing in translucent WDM optical networks,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp. 2796–2802
5. S. Thiagarajan and A. K. Somani, “An efficient algorithm for optimal wavelength converter placement on wavelength-routed networks with arbitrary topologies,” in Proceedings of IEEE International Conference on Computer Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 1999), pp. 916–923
6. B. Ramamurthy, S. Yaragorla, and X. Yang, “Translucent optical WDM networks for the next-generation backbone networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, San Antonio, TX, 2001), pp. 60–64