Rigorous Progress on Algorithms Based Routing and Wavelength Assignment in Trans-Egypt Network (TEGYNET)Management

Published Online February 2013 in MECS                                  and Computer Science

Optical Networks employing WDM are believed to be the next generation networks that can meet the everincreasing demand for bandwidth of the end users [1]. To support applications that require high bandwidth, low delay and low error rate, networks must be employed that can meet the requirements. While the optical fiber provides us with links that have the required properties, network bandwidth is limited by the processing speed of the nodes. The reason is that the processing at the nodes must be done electronically. This means that the optical signal on the fiber must be converted into an electronic signal, processed at low electronic speeds and then converted back to optical signals for transmission over and optical fiber. Apart from slowing the network down, the electro-optic conversion needed to facilitate electronic processing is also expensive. The obvious solution to this problem is to build networks in which the signals are processed in the optical domain. Such networks are called all optical networks [2]. WDM has significantly expanded the capacity of optical networks by allowing different wavelengths to be combined and transmitted simultaneously over the same optical fiber [3]. Synchronous optical network (SONET) is a successful standard for communicating digital information over optical fiber and it forms the basis of current high-speed backbone networks [4]. The increasing bandwidth demands are placing a heavier load on the current network infrastructure. Deploying additional hardware equipment and laying extra optical fibers are expensive. Therefore, improving upon current technologies is a more feasible solution. Wavelength routing in optical WDM networks allows network nodes to communicate with each other via all-optical lightpaths. A typical wavelength routed optical WDM network where optical routing nodes are interconnected by fiber links. When a message is sent from the source node to the destination node using a lightpath, optical-electronic-optical conversion and buffering at the intermediate nodes are not required. Thus, a lightpath between two nodes is an all-optical communication path [5].

Optical Transport Networks based on WDM appear as a potential solution to cope with the increasingly growth of Internet traffic demands. In such systems all-optical WDM channels are used to allow the end to end users communication [6]. These WDM channels are referred as lightpaths, and must be selected in a proper manner in order to optimize the network resources. It is in this point where the routing becomes an important factor in the global network performance. Unlike traditional IP routing where only a physical route was selected, two processes are required to establish a lightpath in a WDM network, i.e. selecting the physical route and selecting the wavelength that will be used to transport the traffic flow.

This problem is known as routing and wavelength assignment problem (RWA) and different heuristics exists to cope with it. The RWA problem is differently addressed depending on the availability of wavelength conversion capabilities. Wavelength routed networks without wavelength conversion are known as wavelength selective (WS) networks [7]. In the present study, WDM technology offers a large bandwidth for optical fibers to carry both today’s Internet traffic and that of the future. Lightpath networks, where all optical wavelength channels (called lightpaths) convey the traffic, have been considered to effectively utilize this WDM technology. The model has been investigated to enhance the performance characteristics of TEGYNET design parameters such as blocking probability, link utilization, routing lengths and average setup time with the presence and absence of wavelength conversion.

II. Mathematical Model Analysis

A connection (lightpath) request sees a network in which a wavelength's usage on a fiber link is statistically independent of other fiber links and other wavelengths. However, this model generally tends to overestimate the blocking probability because it ignores the correlation of usage of wavelength in successive links, especially for a multi link lightpath. Let there be W wavelengths per fiber link, and let ρ be the probability that a wavelength is used on any fiber link. (Since ρW is the expected number of busy wavelengths on any fiber link, ρ is also the "fiber utilization" of any fiber.) We will consider an H link path for a connection from node one to any node that needs to be set up [8-10]. First, let us consider a network with wavelength converters. The probability P B(wc) that the connection request from node one to any node will be blocked equals the probability that, along this H link path, there exists a fiber link with all of its W wavelengths in use, so that [11]:

PB ( wc ) = ^{1 -( 1} - ^pW Y , (1)

Defining p to be the achievable utilization for a given blocking probability in a network without wavelength conversion, that can be expressed as:

P = ¹

1 ^H

^PB ( nwc )

f    1

1 _H

~ ln \    P B ( nwc )

Where the approximation holds for large values of H, and for ¹ H  not too close to unity. Observe that the

^PB ( nwc )

achievable utilization is inversely proportional to the length of the lightpath connection H, as expected. Define G=q/p to be a measure of the benefit of wavelength conversion, which is the increase in (fiber or wavelength) utilization for the same blocking probability. From Eqs. (2) and (4), after setting P B(wc) =P B(nwc) , yields:

1 -1

G « H I ^W J

1 P^H B ( nwc )

(       1

In 1 - P ^H .

B (nwc )

Where the approximation holds for small P B(nwc) , large H, and moderate W so that ¹ H is not too close to

^{,                                    P}B ( nwc )

unity. Observe that, if H=1 (one light path), W= 1 (one wavelength), then G=1, i.e., there is no difference between networks with and without wavelength converters in these cases. Based on MATLAB curve fitting program, the fitting traffic load (TL) in Erlangs, as a function of blocking probability in the absence of wavelength conversion, PB(nwc) for both single path (SP) and multi path (MP) routing can be given [13]:

Рви wc) + 0.0456

TL = B ⁽ nwc) ---------, (sp)

0.02196

TL =

Pb ( nwc ) + 0.55 x 10 ^{- 2}

0.002265

, (MP)

Defining q to be the achievable utilization for a given blocking probability in a wavelength convertible network, that yields:

Also in the same way, based on MATLAB curve fitting program, the fitting traffic load in Erlangs, as a function of blocking probability in the presence of wavelength conversion, P B(wc) for both SP and MP routing can be [14]:

P g ( wc ) + 0.77 x 10

Where the approximation holds for small values of P B(wc) /H, when the correlation of successive link utilizations are small. Next, let us consider a network without wavelength converters. The probability P B(nwc) that the connection request from node one to any node will be blocked equals the probability that, along this H link path, each wavelength is used on at least one of the H links, so that [12]:

0.0035707

, -2

, (SP)

TL =

P g ( wc ) + 0.372 x 10 ^{- 6}

0.0003742

, (MP)

P B ( nwc ) =^{[ 1 -( 1 - p} ) H ^]   ,                        ⁽³⁾

The root mean square errors for the previous fitting equations are 0.00546%, 0.00765%, 0.00843%, and 0.00324% respectively. As well as based on MATLAB curve fitting program, the fitting average setup time (T S ) in μs as a function of traffic load, TL in Erlangs, for both SP and MP routing can be given by [15, 16]:

T S = 565 + 2.6524 TL - 0.0120483 TL ², (SP)      (10)

T S = 1201.5 + 5.5578 TL - 0.024889 TL ² , (MP)     (11)

Also the root mean square errors for the previous fitting equations are 0.0.000987%, and 0.00065432% respectively. Moreover based on MATLAB curve fitting program, the fitting average link utilization (U L ) percentage as a function of traffic load, TL in Erlangs, for both SP and MP routing can be expressed as [17-19]:

U L (%) = 28.5 + 0.63219 TL + 0.59353 x 10 ^{- 3} TL ² , (SP) (12)

U_L (%) = 43.44 + 0.0201384 TL + 0.6035 x 10 ³ TL ² , (MP)(13)

In addition to the root mean square errors for the previous fitting equations are 0.0.000437%, and 0.0006987% respectively. The TEGYNET network is with the 6 nodes and 7 links as shown in Fig. 1. the versions of network capacity and connection arrival rate network dimensioning are used as shown in Table 1

each which has a uniform load between source/destination pair and uniform link capacity.

Fig. 1. The 6 nodes TEGYNET network topology.

Table 1: Network uniform capacity and connection arrival rate for TEGYNET network.

	Network uniform capacity						Connection arrival rate
Node	1	2	3	4	5	6	1	2	3	4	5	6
1	0	75	0	75	0	0	0	10	10	10	10	10
2	75	0	0	75	75	75	10	0	10	10	10	10
3	0	0	0	0	75	75	10	10	0	10	10	10
4	75	75	0	0	0	0	10	10	10	0	10	10
5	0	75	75	0	0	0	10	10	10	10	0	10
6	0	75	75	0	0	0	10	10	10	10	10	0

• III.    Simulation Results and Performance Analysis

We have established the research progress on algorithms based routing and wavelength assignment in optical trans-Egypt network management, these algorithms such as first fit (FF), random, least used (LU), and most used (MU) can be applied in our network topology under study over wide range of simulation parameters listed in Table 2. Based on Simulator in Ref. [21], the blocking probabilities of the four algorithms based wavelength assignment and routing for TEGYNET network in the presence and absence of wavelength conversion are listed in Table 2.

Table 2: Simulation parameters used in TEGYNET network topology [14, 15, 20].

Simulation parameters		Values
Network topology		TEGYNET
Wavelengths per links, W		25-75
Link path, H		6
Fiber utilization, ρ		90%
Link bandwidth		OC-24 (1.24416 Gb/s)
Number of nodes		6
Number of links		7
FF	P B(wc)	0.010052-0.055845
	P B(nwc)	0.009948-0.064371
Random	P B(wc)	0.010244-0.053837
	P B(nwc)	0.008380-0.056008
LU	P B(wc)	0.010429-0.054995
	P B(nwc)	0.007834-0.056042
MU	P B(wc)	0.010429-0.054995
	P B(nwc)	0.009105-0.057071

Based on the model equations analysis, the series of the operating parameters that are listed in Table 2, and the series of Figs. (2-33), the following features are assured:

• i)    Figs. (2-5) have indicated that blocking probability with and without wavelength conversion decreases with increasing wavelengths per link for different both light paths and routing algorithms under considerations.

• ii)    As shown in Figs. (6-9) have assured that link utilization with wavelength conversion increases with increasing wavelengths per link for different both light paths and routing algorithms under study. While in the case of link utilization without wavelength conversion decreases with increasing wavelengths per link for different both light paths and routing algorithms under study.

• iii)    Figs. (10-17) have demonstrated that traffic load on the network increases with  wavelength

conversion compared to without  wavelength conversion for different both single and multi light paths and routing algorithms under considerations.

• iv)    Figs. (18-25) have demonstrated that average set up time on the network increases with wavelength conversion compared to without wavelength conversion for different both single and multi light paths and routing algorithms under study.

• v)    As shown in Figs. (26-33) have indicated that average link utilization on the network increases with wavelength conversion compared to without wavelength conversion for different both single and multi light paths and routing algorithms under considerations.

  

  Fig. 2. Blocking probability with and without wavelength conversion in relation to wavelengths per link at the assumed set of the operating parameters.

  
  
  

  Fig. 3. Blocking probability with and without wavelength conversion in relation to wavelengths per link at the assumed set of the operating parameters.

  
  
  

  Fig. 4. Blocking probability with and without wavelength conversion in relation to wavelengths per link at the assumed set of the operating parameters.

  
  
  
  
  

Fig. 5. Blocking probability with and without wavelength conversion in relation to wavelengths per link at the assumed set of the operating parameters.

Wavelengths per link, W

Fig. 6. Link utilization with and without wavelength conversion in relation to wavelengths per link at the assumed set of the operating parameters.

Wavelengths per link, W

Fig. 7. Link utilization with and without wavelength conversion in relation to wavelengths per link at the assumed set of the operating parameters.

Wavelengths per link, W

Fig. 8. Link utilization with and without wavelength conversion in relation to wavelengths per link at the assumed set of the operating parameters.

Link utilization without wavelength                       Link utilization without wavelength conversion, p                                             conversion, p

Wavelengths per link, W

Fig. 9. Link utilization with and without wavelength conversion in relation to wavelengths per link at the assumed set of the operating parameters.

Blocking probability with wavelength conversion, P _B(_wc)

• Fig. 10.    Traffic load in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

  
  
  
  
  
  

  Single path ■ M ulti path

  
  

  FF Algorithm

  
  

  S

  
  
  
  
0.009948  0.014895  0.019842  0.024789 0.029736 0.034683  0.03963  0.044577 0.049524  0.054471  0.059418  0.064365

га о

га

Blocking probability without wavelength conversion, P _B(_nwc)

• Fig. 11.    Traffic load in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

  
  
  

Blocking probability with wavelength conversion, P _B(_wc)

• Fig. 12.    Traffic load in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

  
  
  

Blocking probability without wavelength conversion, P _B(_nwc)

• Fig. 13.    Traffic load in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

  
  
  

Blocking probability with wavelength conversion, P _B(_wc)

Fig. 14. Traffic load in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

Single path

■ ■ ■ ■ M ulti path

LU Algorithm

0.007834  0.012216  0.016598  0.02098  0.025362 0.029744  0.034126  0.038508  0.04289  0.047272  0.051654  0.056036

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 15. Traffic load in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

Blocking probability with wavelength conversion, P _B(_wc)

Fig. 16. Traffic load in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 17. Traffic load in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

Single path M ulti path

FF Algorithm

0.010052  0.014215  0.018378  0.022541 0.026704 0.030867  0.03503  0.039193  0.043356 0.047519  0.051682 0.055845

Blocking probability with wavelength conversion, P _B(_wc)

Fig. 18. Average set up time in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

FF Algorithm

Single path

■ ■ ■ ■ M ulti path

0.010052  0.014215  0.018378  0.022541 0.026704 0.030867  0.03503  0.039193  0.043356 0.047519  0.051682 0.055845

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 19. Average set up time in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

Average set up time, TS, μsec

Single path ■ M ulti path

Random Algorithm

0.010429  0.01448  0.018531  0.022582 0.026633 0.030684 0.034735 0.038786 0.042837 0.046888 0.050939  0.05499

Fig

Blocking probability with wavelength conversion, P _B(_wc)

. 20. Average set up time in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

550 0.010429   0.01448   0.018531  0.022582  0.026633  0.030684  0.034735  0.038786  0.042837 0.046888  0.050939   0.05499

Random Algorithm

Single path ■ M ulti path

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 21. Average set up time in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

Single path

■ ■ ■ ■ M ulti path

LU Algorithm

0.010429  0.01448   0.018531 0.022582 0.026633 0.030684 0.034735 0.038786 0.042837 0.046888 0.050939  0.05499

Blocking probability with wavelength conversion, P _B(_wc)

Fig. 22. Average set up time in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

LU Algorithm

Single path

■ ■ ■ ■ M ulti path

0.010429  0.01448  0.018531  0.022582 0.026633 0.030684 0.034735 0.038786 0.042837 0.046888 0.050939  0.05499

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 23. Average set up time in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

Single path M ulti path

MU Algorithm

0.010429  0.01448   0.018531 0.022582 0.026633 0.030684 0.034735 0.038786 0.042837 0.046888 0.050939  0.05499

Blocking probability with wavelength conversion, P _B(_wc)

Fig. 24. Average set up time in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

MU Algorithm

Single path

■ ■ ■ ■ M ulti path

0.010429  0.01448   0.018531 0.022582 0.026633 0.030684 0.034735 0.038786 0.042837 0.046888 0.050939  0.05499

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 25. Average set up time in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

Blocking probability with wavelength conversion, P _B(_wc)

Fig. 26. Average link utilization in relation to blocking probability with wavelength conversion at the assumed set of the operating

parameters.

47.5

й о

42.5

FF Algorithm

Single path

M ulti path

37.5

ы)

га

32.5

0.010052  0.014215  0.018378  0.022541 0.026704 0.030867  0.03503  0.039193 0.043356  0.047519  0.051682  0.055845

Blocking probability without wavelength conversion, P _B(_nwc)

• Fig. 27.    Average link utilization in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

  
  
  

Blocking probability with wavelength conversion, P _B(_wc)

• Fig. 28.    Average link utilization in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

  

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 29. Average link utilization in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

Blocking probability with wavelength conversion, P _B(_wc)

Fig. 30. Average link utilization in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 31. Average link utilization in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

Blocking probability with wavelength conversion, P _B(_wc)

Fig. 32. Average link utilization in relation to blocking probability with wavelength conversion at the assumed set of the operating parameters.

Blocking probability without wavelength conversion, P _B(_nwc)

Fig. 33. Average link utilization in relation to blocking probability without wavelength conversion at the assumed set of the operating parameters.

• IV. Conclusions

This paper has examined the various facets of the wavelength conversion: from its incorporation in a wavelength-routed trans-Egypt network design to its effect on efficient routing and management algorithms to a measurement of its potential benefits under various network conditions. Some of the important results that were highlighted by our simulation based case study of wavelength conversion as a network needs a mixing of traffic for wavelength converters to be beneficial (i.e., single rings benefit little from wavelength converters, while graphs with higher connectivity benefit more). A network with wavelength conversion can achieve almost the same benefit as a network that has "full" conversion capabilities and traffic load can influence the benefit of wavelength conversion. It is theoretically found that the increased wavelengths per link, resulting in the decreased blocking probability and the increased link utilization, traffic load, average set up time, and average link utilization with wavelength conversion compared to without wavelength conversion for different both single and multi light paths and routing algorithms under study at the same operating conditions.