OSA's Digital Library

Optics Express

Optics Express

  • Editor: Michael Duncan
  • Vol. 11, Iss. 23 — Nov. 17, 2003
  • pp: 3022–3033
« Show journal navigation

Novel algorithm for upgrading of translucent optical networks

Yabin Ye, Tee Hiang Cheng, and Chao Lu  »View Author Affiliations


Optics Express, Vol. 11, Issue 23, pp. 3022-3033 (2003)
http://dx.doi.org/10.1364/OE.11.003022


View Full Text Article

Acrobat PDF (182 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

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 [1

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

].

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 [2

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

]. 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 [3

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.

]. 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 [4

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

] 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 [4

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

]. 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 [4

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

].

Fig. 1. The node model.

3. Upgrade node selection algorithm

It is logical to think that the most promising candidate for upgrading is the node most ‘central’ in the network [3

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.

, 6

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

]. 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 Tksd 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, Tksd is defined to be zero for k=s or d. TW of an arbitrary node k is defined as:

Ck=s,d,(sd)Tksd,k(1,2,,N)
(1)

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:

Fk=α·Pk+(1α)·Qk
(2)

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.

Fig. 2. The topology of NSFNET.

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.

Fig. 3. The transitional weight of nodes.

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.

Table 1. Sequence of Nodes Selected for Upgrading

table-icon
View This Table
| View All Tables

Table 2. Links Ordered in Descending Order of Link Lengths

table-icon
View This Table
| View All Tables

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 (1iW) 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.

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.

Fig. 4 Comparison between the two node selection strategies, when the network is upgraded from M=1 to M=2, W=8, Ls =3000km

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

Fig. 5. Comparison between the two node selection strategies, when the network is upgraded from M=2 to M=3, W=8, Ls =3000km

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.

Fig. 6. Comparison between the TL strategy and the random selection strategy, when the network is upgraded from M=1 to M=2, W=8, Ls =3000km.
Fig. 7. Comparison between the TL strategy and the random selection strategy, when the network is upgraded from M=2 to M=3, W=8, Ls =3000km.

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.

Fig. 8 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, W=8, Ls =3000km.

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.

Fig. 9. The increased traffic load 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, W=8, Ls =3000km.

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.

Fig. 10. The relationship between the blocking probability and the number of wavelengths for the TL and TW algorithms, when the network is upgraded from M=1 to M=2, Ls =3000km, 40Erlangs.

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.

Fig. 11. The relationship between the blocking probability and the transparent length for the TL and TW algorithms, when the network is upgraded from M=1 to M=2, W=8, 40Erlangs.

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.

Fig. 12. Comparison between the two node selection strategies, when wavelength conversion is considered and the network is upgraded from M=1 to M=2, Ls =3000km, W=8.

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.

Fig. 13. Comparison between the two node selection strategies, when tunable lasers are used and the network is upgraded from M=1 to M=2, Ls =3000km, W=8.

6. Conclusion

Acknowledgments

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

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

  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 Networking 1, 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, 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.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited