## Novel algorithm for upgrading of translucent optical networks

Optics Express, Vol. 11, Issue 23, pp. 3022-3033 (2003)

http://dx.doi.org/10.1364/OE.11.003022

Acrobat PDF (182 KB)

### Abstract

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

## 1. Introduction

*WW*) routing algorithm.

## 2. Network model

_{A}, R

_{A}and T

_{R}R

_{R}. If a channel is originated from the node, it enters the network through the T

_{A}set. If a channel is terminated at the node, it exits via the R

_{A}set. If the channel traverses an intermediate node and needs regeneration, it enters and exits the node via a TxRx pair in the T

_{R}R

_{R}set [4].

*λ*

_{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.

*L*

_{s}is the transparent length (the maximum transmission length in the optical domain). If the length of a lightpath is larger than

*L*

_{s}, 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

*L*

_{s}.

## 3. Upgrade node selection algorithm

*N*nodes and we need to select

*K*nodes for upgrading, there are

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

*TW*). Let

*s*and

*d*transits through node

*k*; otherwise, it takes the value of zero. Also,

*k=s*or

*d*.

*TW*of an arbitrary node

*k*is defined as:

*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

*C*

_{k}can be obtained, and a node with a larger

*TW*has a higher priority to be upgraded.

*N*nodes in descending order of

*C*

_{k}. We define

*P*

_{k}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

*Q*

_{k}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.

*F*

_{k}for node

*k*:

*α*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

*F*

_{k}, and define this sequence as a

*TL*sequence. An arbitrary node

*k*that has a smaller value of

*F*

_{k}has a higher priority to be selected for upgrading.

*km*is labeled beside the link.

*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

*C*

_{k}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

*C*

_{k}, e.g. node 6 and 11 have 4 ports and also have the largest

*C*

_{k}, while node 7 and 14 have 2 ports and have the smallest

*C*

_{k}. Therefore, nodes 6 and 11 have higher priority to be upgraded in the

*TW*strategy.

*Q*

_{k}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,

*Q*

_{9}=1. Similarly,

*Q*

_{4}=1,

*Q*

_{2}=

*Q*

_{8}=2 and

*Q*

_{6}=

*Q*

_{13}=3, etc.

*α*is given,

*F*

_{k}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),

*P*

_{11}=2 and

*Q*

_{11}=4, when

*α*is 0.5,

*F*

_{11}=0.5×2+0.5×4=3. Similarly,

*P*

_{4}=4 and

*Q*

_{4}=1 and

*F*

_{4}=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

*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

*L*

_{s},

*λ*

_{i}is assigned to the call and the connection is established. If the length of the route is larger than

*L*

_{s}, then the lightpath should be regenerated in some intermediate nodes. We use the following regeneration node selection algorithm.

*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

*cost1*

_{m}≡min(

*n*

_{Tx}(

*m*),

*n*

_{Rx}(

*m*)) and

*cost2*

_{m}=max(

*n*

_{Tx}(

*m*),

*n*

_{Rx}(

*m*)), where

*m*:1≤

*m*≤

*k*and

*n*

_{Tx}(

*m*) and

*n*

_{Rx}(

*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

*L*

_{s}and the length from

*S*to

*j*+1 is larger than

*L*

_{s}, 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

*L*

_{s}. 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.

*O*(

*N*

^{2}

*×W×L*).

## 5. Numerical results

- 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.

*α*is determined by the network topology and the transparent length. In NSFNET, when the transparent length is 3,000

*km*, 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.

*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).

*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.

*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.

*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.

*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.

*TL*algorithm. The relationship between the blocking probability and the transparent length (

*L*

_{s}) 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

*L*

_{s}is larger than 2500

*km*, the

*TL*algorithm has better performance than the

*TW*algorithm, but when

*L*

_{s}is smaller than 2500

*km*, 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.

*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.

*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.

## 6. Conclusion

## Acknowledgments

## 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 |

2. | A. A. M. Saleh, “Transparent optical networking in backbone networks,” in |

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,” |

4. | X. Yang and B. Ramamurthy, “Dynamic routing in translucent WDM optical networks,” in |

5. | S. Thiagarajan and A. K. Somani, “An efficient algorithm for optimal wavelength converter placement on wavelength-routed networks with arbitrary topologies,” in |

6. | B. Ramamurthy, S. Yaragorla, and X. Yang, “Translucent optical WDM networks for the next-generation backbone networks,” in |

**OCIS Codes**

(060.4250) Fiber optics and optical communications : Networks

(060.4510) Fiber optics and optical communications : Optical communications

**ToC Category:**

Research Papers

**History**

Original Manuscript: September 4, 2003

Revised Manuscript: October 27, 2003

Published: November 17, 2003

**Citation**

Yabin Ye, Tee Cheng, and Chao Lu, "Novel algorithm for upgrading of translucent optical networks," Opt. Express **11**, 3022-3033 (2003)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-11-23-3022

Sort: Journal | Reset

### References

- 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
- 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
- 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 Networking 1, 424-441, 2002.
- 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
- 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
- B. Ramamurthy, S. Yaragorla, 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

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

### Figures

Fig. 1. |
Fig. 2. |
Fig. 3. |

Fig. 4 |
Fig. 5. |
Fig. 6. |

Fig. 7. |
Fig. 8 |
Fig. 9. |

Fig. 10. |
Fig. 11. |
Fig. 12. |

Fig. 13. |
||

« Previous Article | Next Article »

OSA is a member of CrossRef.