Modiﬁed distributed relative capacity loss algorithm for ...repositorio.unicamp.br/bitstream/REPOSIP/57661/1/... · The DRCL algorithm is based on the RCL algorithm, but the connection

Modified distributed relative capacity lossalgorithm for WDM optical networks

Reinaldo G. Dante

Laboratório de Tecnologia Fotônica, Departamento de Semicondutores, Instrumentos e Fotônica,Faculdade de Engenharia Elétrica e de Computação, Universidade Estadual de Campinas

(UNICAMP), Campinas, SP, Brazil, and Departamento de Automação,Centro Federal de Educação Tecnológica de São Paulo (CEFET-SP), Sertãozinho, SP, Brazil

[email protected]

Edson Moschim

Laboratório de Tecnologia Fotônica, Departamento de Semicondutores,Instrumentos e Fotônica, Faculdade de Engenharia Elétrica e de Computação,

Universidade Estadual de Campinas (UNICAMP), Campinas, SP, Brazil

[email protected]

Joaquim F. Martins-Filho

Grupo de Fotônica, Departamento de Eletrônica e Sistemas,Universidade Federal de Pernambuco(UFPE), Recife, PE, Brazil

[email protected]

RECEIVED 2 FEBRUARY 2005;REVISED 18 MARCH 2005;ACCEPTED22 APRIL 2005;PUBLISHED 2 MAY 2005

We focus on the routing and wavelength assignment (RWA) problem in intelli-gent and transparent optical networks operating under no wavelength conversionconstraint for end-to-end connections in distributed environments. We proposeand demonstrate what we believe to be a novel wavelength assignment algorithmbased on hop counts and relative capacity loss, called modified distributedrelative capacity loss (MDRCL). It consists of grouping end-to-end routes withthe same number of hops in MDRCL tables. Unlike the distributed relativecapacity loss (DRCL) algorithm, MDRCL offers a new strategy for wavelengthassignment, including the destination node in its analysis and assuming one,more than one, or even all potential routes from source node to destinationnodes combined by the same number of hops in its tables. We present simulationresults of dynamic traffic in a hypothetical meshed network in terms of blockingprobabilities as a function of network load. We show that our MDRCL algorithmoutperforms the traditional wavelength assignment algorithms. © 2005 OpticalSociety of America

OCIS codes:060.2330, 060.4250.

© 2005 Optical Society of AmericaJON 6570 May 2005 / Vol. 4, No. 5 / JOURNAL OF OPTICAL NETWORKING 271

1. Introduction

Dense wavelength division multiplexing, used in conjunction with wavelength routing, isa promising mechanism for information transport in intelligent and transparent optical net-works (ITONs) [1–3]. Recently, automatically switched optical networks (ASONs) [4, 5]seem strong candidates for future transport technology in ITONs. ASONs show some ad-vantages [6], such as (1) on-demand bandwidth provision, (2) a distributed control mecha-nism, (3) dynamic setup of optical connections (i.e., permanent, soft, and switched connec-tions), (4) packet and optical layer interconnection through GMPLS, and (5) a restorationmechanism. Those advantages allow one to conclude that an ASON is a fast, efficient, anddynamic optical network, and it is a feasible solution for such networks, which are meshedand require optical high-level quality of services (optQoS).

In our analysis we assume that the ITON is a circuit-switched network and that it isnecessary only to process and switch the virtual optical channels on each optical cross-connect (OXC), whereas in packet-switched ITONs the processing time of optical packetoverheads would be added.

We also assume that there is no wavelength conversion in that ITON due to the costof wavelength converters (transponders), which is still high and significant for the finan-cial network budget. Those transponders are bit-rate, protocol, and format dependent andtheir costs increase proportionally to these parameters. Furthermore, the estimated Internettraffic volume and enterprise network demands for the next ten years may be supported bythe sets of wavelengths in theC, L, andSbands. Therefore we consider the ITON under awavelength-continuity constraint rather than a wavelength-conversion ITON.

In addition, each ITON network element, or OXC, knows the network topology andthe network state, but the connection request matrix is unknown. Boundary conditions ap-proach reality when the connection request arrivals are random and the ITON can use itsfunctions to discover the topology and network state automatically.

The procedure of connection establishment can be understood as follows: a client net-work, e.g., client A, generates a request for a connection from itself to client B and sendsthe request to the edge source WDM node(s) via a user-network interface (UNI). ITON sig-naling and connection-oriented routing protocols, which are located in the ITON controlplane, find a virtual path among the OXCs via a network–network interface (NNI) to con-nect A to an edge destination node (d) that in turn is connected to client B. That virtual pathconsists of a route and an available wavelength that satisfy the required parameters of theconnection request (e.g., duration of calling, bit rate, QoS, etc.). Once the virtual path is de-fined, the ITON control plane sets up the connection by configuring every OXC along thatvirtual path to establish an end-to-end connection (e.g., a permanent connection). When theITON control plane sets up the connection by configuring only the edge source node as aresult of a management request (e.g., soft or permanent) or a client network request (e.g.,a switched connection), then that edge source node will be able to configure other OXCsrescued by signaling and connection-oriented routing protocols to establish a virtual pathreaching the edge destination node. In all cases mentioned above, once the connection isestablished the available wavelength of the virtual path is assigned to transport the clienttraffic via an optical WDM channel, called a “lightpath.” When the virtual path cannot befound to establish an end-to-end connection because there is no available wavelength, theconnection request is blocked.

Thus, it is important to achieve high performance in the ITON, reducing the callingblocking probabilities and avoiding, if possible, high complexity in implementation. Givena limited set of wavelengths on each optical link and a wavelength-continuity constraint,the RWA problem could be formulated as NP-complete [7]. The solution of that RWAproblem could be found with difficulty. However, that RWA problem could be reduced to


two major subproblems, routing and wavelength assignment (WA), and each subproblemcould be solved separately. In regard to the WA subproblem, the WA heuristic algorithmswould reach some excellent results.

In this paper we propose and demonstrate a novel WA algorithm, called “modified dis-tributed relative capacity loss” (MDRCL), with a new strategy based on hop counts andrelative capacity loss. Unlike the DRCL algorithm, MDRCL may consider all potentialpaths from sources to d, grouping them in the same hop-based MDRCL table. This newstrategy allows us to refine the analysis of relative capacity loss, comparing paths withthe same number of hops. We assume circuit-switched bidirectional connections and thewavelength-continuity constraint in our hypothetical meshed optical networks.

We present simulation results of dynamic traffic in terms of blocking probability asa function of network load. We show that our algorithm outperforms the traditional WAheuristic algorithms. We also show the results of the proposed WA algorithm in terms ofblocking probability as a function of percentage of potential routes and how it could affectnetwork performance.

This paper is organized as follows: Section2 presents a brief description of some tra-ditional WA algorithms, such as first fit (FF), relative capacity loss (RCL), and DRCL;Section3 discusses the MDRCL WA algorithm proposed; Section4 shows the computa-tional complexity analysis of some WA algorithms, including MDRCL; in Section5 wecompare the performance of all the WA algorithms discussed in this paper; and, finally,Section6 concludes the paper.

2. Traditional Wavelength Assignment Algorithm Descriptions

In this section we examine some traditional WA algorithms such as FF, RCL [8], and DRCL[9]. The FF algorithm enumerates all wavelengths from a given set in a list and assigns thefirst available indexed wavelength. This scheme requires no global information. The RCLalgorithm is based on MAX-SUM [10], and it requires global information such as the trafficmatrix and the network state and topology.

Let ψ be a network state that specifies the existing lightpaths (routes and wavelength as-signments) in the network. The link capacity on linkl and wavelengthj in stateψ, r (ψ, l , j),is defined as the number of fibers on which wavelengthj is unused on linkl in Eq. (1), asfollows:

r (ψ, l , j) = Ml −D(ψ)l j , (1)

whereMl is the number of fibers on linkl andD(ψ) is the number of assigned fibers onlink l and wavelengthj in the stateψ.

The path capacityr (ψ, p, j) on wavelengthj is the number of fibers on which wave-length j is available on the most congested link along the path,

r (ψ, p, j) = minl∈π(p)

r (ψ, l , j) . (2)

The path capacity ofp in stateψ, R(ψ, p), is the sum of path capacities on all wavelengths,

R(ψ, p) =W

∑j=1

minl∈π(p)

r (ψ, l , j) . (3)

MAX-SUM [ 10] chooses wavelengthj to minimize the total capacity loss (TCL), whichcan be computed as

∑p∈P

[r (ψ, p, j)− r

(ψ′ ( j) , p, j

)], (4)

whereψ′ ( j) is the next state of the network if wavelengthj is assigned to the connectionandr (ψ′ ( j) , p, j) is the path capacity after wavelengthj is assigned in the stateψ′ ( j).


On the other hand, the RCL algorithm [8] chooses wavelengthj to minimize the relativecapacity loss, which can be computed as

∑p∈P

[r (ψ, p, j)− r (ψ′ ( j) , p, j)

r (ψ, p, j)

]. (5)

The strategy of the RCL algorithm is to determine the total relative capacity loss [i.e., thesum of relative capacity loss (TRCL)] for all connection requests in a single RCL table,for a known traffic matrix, and to minimize TRCL. Having to know the connection requestmatrix makes implementing the RCL algorithm difficult and expensive in a distributed envi-ronment [9]. In this paper the term “distributed” for optical networks means the possibilityof analyzing the effect of an assigned wavelength on the chosen path for that current con-nection request, among the alternative paths for the future connection requests, in order tobalance the load on the network as in Ref. [9]. Therefore knowledge of the network state isrequired.

The DRCL algorithm is based on the RCL algorithm, but the connection request matrixis unknown. The DRCL algorithm depends strongly on a routing table, which is imple-mented by using the Bellman–Ford algorithm. In that table there is a preselected routingfor each possible connection request in an(s,d) node pair. Given a connection request froms to d and a routing table, the DRCL algorithm considers all paths froms to every othernode in the network, excludingd. In summary, the DRCL algorithm does not consider thedestination node of the arriving connection request (d), and the DRCL algorithm computesall possible paths independently of the number of nodes. That computing could be hardwork when there are many nodes in the network [9]. Furthermore, the DRCL algorithmincludes all selected nodes in the same DRCL table in order to find the wavelength thatminimizes TRCL. The DRCL algorithm performs well in distributed environments.

3. Modified Distributed Relative Capacity Loss Algorithm Description

The MDRCL algorithm is based on relative capacity loss and hop counts and is imple-mented for single-fiber networks; however, it can be extended to multifiber networks eas-ily. We assume that each OXC knows the network state and topology but that the trafficmatrix (set of connection requests) is unknown. The block diagram of our proposed WAalgorithm, called modified distributed relative capacity loss (MDRCL), is shown in Fig.1.For a given connection request from source node (s) to destination node (d), consider a setof all potential routes, calledΘ or Θall, and a subset of an amountK of potential routes,calledΛ, such thatΛ ⊂ Θ. In addition, assume that all potential routesM are inΘ andthatK potential routes are chosen to fillΛ, we annotate this subsetΛ asΛ(K/M)%; in otherwords, the index ofΛ represents the percentage of selected potential routes over all routesin the(s,d) node pair. The subsetΛ can be taken through an AR that calculates and selectsK potential routes fromΘ. The AR depends on the network state, and its adaptive routingstrategy is based on the cost metric to determine the route from a source node to a desti-nation node, dynamically, similar to Ref. [9]. A dynamic routing algorithm, called hybridfixed-path least-congestion-k (HFPLC-k), is described in Ref. [11], and it is an exampleof a routing algorithm in whichk shortest-routes from the(s,d) node pair are calculated.It is based on Yen’sk-shortest-paths algorithm [12], and the main idea with the HFPLC-kalgorithm is to use thek most congested links on each candidate route to find the best routewhen a request arrives. Instead of using the firstk links on each route, like FPLC-k [13], us-ing thek most congested links ensures that the most congested route will be avoided. ThoseK potential routes fromΛ could be saved in a dynamic pointer matrix on the adaptive rout-ing program or an rw file at OXC. The MDRCL algorithm could receive either routes fromΛ or even all routes fromΘ for each given(s,d) connection request. In the first case, the


MDRCL algorithm receives the routes fromΛ, by reading that rw file or accessing the con-tent of that dynamic pointer matrix on the adaptive routing program. Alternatively, the ARcould build a routing table as described in Ref. [9] and supply it to the MDRCL algorithm.In the second case, the MDRCL algorithm could obtain all routes through knowledge ofthe network topology, and, consequently, the MDRCL algorithm would need no AR. TheMDRCL algorithm is essentially a WA algorithm; however, we implement a small routinein the MDRCL algorithm to obtain all routes for a given network topology in case there isno underlying the AR. In summary, the MDRCL algorithm is flexible for both cases, andthe network operator could configure it to work in conjunction with an AR or alone (in thiscase, a small routine is set up to create theΘall that supplies the MDRCL), and that net-work operator’s decision would depend on the number of nodes and the network topology.This flexibility of the MDRCL algorithm is very interesting, and simulation results showan improved network performance for the MDRCL algorithm for both cases.

Receives all routes orK potent ial routes from

adapt ive rout ing algorithm

Combine the same hop-based rout ings in M-DRCL Table

Calculate the relat ive and total relat ive capacity losses (i.e., RCL and T-RCL)

RCL ≠ 0 ?

Choose the (rout ing, wavelength) pair from minimum (T-RCL, RCL) M-DRCL Table

BlockedCall

Call Request

Yes

No

Fig. 1. Block diagram of our WA algorithm.

Let the potential routes fromΛ be supplied and combined, by the criteria of the samenumber of hops, in MDRCL tables. Each MDRCL table contains one or more routings withthe same number of hops independently whether there is or is not an available wavelengthto assign for the given connection request. In each hop-based MDRCL table the proposedWA algorithm calculates the RCL and TRCL for each wavelength. If there is no availablewavelength (i.e., if RCL= 0 for each wavelength), the connection request is blocked. Onthe other hand, if there is a set of available wavelengths, the MDRCL algorithm will selectthe wavelength that minimizes the TRCL on each hop-based MDRCL table. Assuming thatthere are two or more routings for that selected wavelength in the hop-based MDRCL table,


the proposed WA algorithm selects the routing that produces the minimum relative capacityloss.

When there is a draw for minimum total relative capacities through calculation of twoor more wavelengths on different hop-based MDRCL tables, the MDRCL algorithm willselect the wavelength from a minimum-hop-number MDRCL table. The MDRCL algo-rithm is implemented in 150 C++ code lines. The blocking probability is obtained from asimulation of a set of bidirectional calling requests (5×105 calls). We use a Poisson dis-tribution for call arrivals and for call holding time. The source–destination node pair foreach call follows a uniform distribution.

For comparison we also determine the performance of some traditional WA heuristicalgorithms such as FF, RCL, and DRCL for some fixed and adaptive routing algorithms.The MDRCL algorithm is easy to implement in realistic networks because it requires thetopology but not the traffic matrix.

The MDRCL and RCL algorithms are different, although both use the common conceptof RCL. In other words, the MDRCL and RCL algorithms determine the RCL and TRCLalong the paths from the source node of an arriving connection request (s) to the destinationnode of the arriving connection request (d). However, for a given(s,d) connection request,MDRCL groups each potential path froms to d with those of an equal number of hopsin the same MDRCL table, whereas RCL considers all connection requests and groups allpaths from those connection requests in the same RCL table. The MDRCL algorithm doesnot know the connection request matrix. The percentage of routes is given from an ARor, depending on the number of nodes in the network, all routes could be considered. Weunderstand that two or more paths can be compared in terms of relative capacity loss whenthey have the same number of hops because (1) routes with a large number of hops cannaturally result in a higher capacity loss than routes with small number of hops, and so theycannot be compared; (2) the minimum TRCL for all paths, independently of the number ofhops, in a single table does not lead to the best choice of wavelength. For example, considerfour nodes and a set of three wavelengths (numberedλ0 throughλ2) per link in a single-fiber network as shown in Fig.2. The diagram of assigned wavelengths on each link is alsoshown in Fig.2.

1

λ0

0

2 3

λ0 , λ1

λ2

λ2

λ1

λ1 λ2

λ2

Fig. 2. Diagram of assigned wavelengths in an example network.

Suppose that a connection request is generated from node 0 to node 3,P(0,3), and weconsider all possible routes to calculate the relative capacity loss. If we consider all theroutes, independently of the number of hops, in a single RCL table, we obtain the resultshown in Table1. The routes are (1)R1 = {0,1,2,3}, (2) R2 = {0,2,3}, (3) R3 = {0,1,3},and (4)R4 = {0,3}.


Table 1. Relative Capacity Loss of All Possible Routes forP(0,3)

λ R1 R2 R3 R4 Sum of RCL (T-RCL) 0 0 0 1 ½ 1.5 1 0 1 0 0 1.0 2 1 0 0 ½ 1.5

Indicates thatλ1 in R2 is the wavelength that minimizes the TRCL. On the otherhand, the MDRCL algorithm chooses either of two wavelengths,λ0 or λ2 in R4,as shown in Table2.

Table 2. Calculation in the MDRCL Algorithm: Routing with (a) 0 Hops (b) 1 Hop,(c) 2 Hops

λ R4 Sum of RCL (T-RCL)

0 ½ 0.5 1 0 0 2 ½ 0.5

(a)

λ R2 R3 Sum of RCL (T-RCL)

0 0 1 1.0 1 1 0 1.0 2 0 0 0

(b)

λ R1 Sum of RCL (T-RCL)

0 0 0

1 0 0 2 1 1.0

(c)

This example illustrates that the MDRCL scheme is neither an average RCL calculationfor all possible routes nor a set of a few possible routes. Instead, the MDRCL algorithmapplies the criteria of hop count to separate all possible routes or a set of few possible routesinto the same hop-based MDRCL tables, and then it selects the better route.

4. Analysis of Computational Complexity

In this section we examine the computational complexity of some heuristic WA algorithms,such as RCL, DRCL, and MDRCL. The RCL computational complexity is analyzed inRef. [9]. Let N andW be the total number of nodes and the total number of wavelengthson the optical networks, respectively. The DRCL algorithm considers all potential pathsfrom the source node of the arriving connection request to every other node in the network,excluding the destination node of the arriving connection request; since each link of thispath is shared by others, the worst-case running time is of the order ofO

(N2

). The worst

case is havingO(WN2

)cells in the DRCL table to calculate the path capacity, and filling

each cell takes at mostO(N), so the overall computation cost will beO(WN3

), similar to

results for MAX-SUM and RCL algorithms [9].


Let Φ be the total percentage of potential routes that compounds the set of all routes,calledΘall, for a given(s,d) connection request. Moreover, letK be a certain percentage ofpotential routes calculated by an AR, whereK < Φ, that compounds the subset of a numberK of potential routes, calledΛK , such thatΛK ⊂ Θ. In the MDRCL algorithm, we find twoworking modes: (1) in the absence of a routing algorithm, so thatΘall is considered, and (2)with an AR working in conjunction with the MDRCL algorithm, so thatΛK is considered.In the first case, the worst-case running time isO(ΦN) once the number of links on a pathis bounded byO(N). To calculate the capacity on each such path, all the links along thatpath have to be examined for the minimal number of available wavelengths. The worst caseis havingO(WΦN) cells in the MDRCL table, and filling each cell takes at mostO(N), sothe overall computation cost will beO

(WΦN2

). The total percentage of potential routes

Φ could depend on the node numbers and network topology, and ifΦ increases then thiscomputational cost will be expensive. In the second case, the worst-case running time isO(KN) once the number of links on a path is bounded byO(N). Similar to the previouscase, the overall computation cost will beO

(WKN2

). This computational cost could be

lower, equal or higher thanO(WN3

), depending onK. The MDRCL algorithm will have a

lower computational cost than the DRCL algorithm whenK < N.

5. Simulation Results and Discussion

This paper presents the simulation results of two hypothetical single-fiber networks: (1)that proposed by Zang in Ref. [9] as shown in Fig.3(a) (here called network 1), and (2)meshed double rings as illustrated in Fig.3(b) (here called network 2).

Fig. 3. Simulated network topologies: (a) proposed in Ref. [9]; (b) meshed double rings.

Figure4 shows the blocking probability as a function of network load for four RWAalgorithms simulated in network 1: from top to bottom, orange downward triangle, fixedrouting algorithm, which generates a static routing table, in conjunction with the DRCLalgorithm; green asterisk, the same fixed routing algorithm in conjunction with the FFalgorithm; red upward triangle, AR (i.e., the weighted link capacity algorithm [14]), whichgenerates a dynamic routing table and updates it before each new connection request, inconjunction with the DRCL algorithm (denoted WLC, DRCL); blue rectangle, without anyAR because all potential routes fromΘ are considered in conjunction with the MDRCLalgorithm (denotedΘall, MDRCL). Because of the topology of network 1, which is small,the blocking probability of the MDRCL is equal to the DRCL algorithm.

Figure5 shows the blocking probability as a function of load for a sequence of RWAalgorithms: from top to bottom, black filled circle, the subsetΛ10%, composed of 10% ofthe better potential routes calculated by AR (i.e., the weighted link capacity algorithm), in


20 30 40 50 60 70 80 90 100 11010 -6

10 -5

10 -4

10 -3

10 -2

10 -1

f ixed routing , DRC L f ixed routing , FF W LC , DRCL Θ all, M -DRCL

Bloc

king

Pro

babi

lity

Load (E rlangs)

Fig. 4. Blocking probability versus load for network 1 [9].

conjunction with the MDRCL algorithm (denotedΛ10%, MDRCL); gray downward trian-gle, the same AR, which generates a dynamic routing table and updates it before each newconnection request, in conjunction with the DRCL algorithm (denoted WLC, DRCL); or-ange rectangle, a subsetΛ90%, composed of 90% of the better potential routes calculated bythe same AR in conjunction with the MDRCL algorithm (denotedΛ90% MDRCL); brownrectangle, a subsetΛ70%, composed of 70% of the better potential routes calculated by thesame AR in conjunction with the MDRCL algorithm (denotedΛ70% MDRCL); red rectan-gle, without any AR because all potential routes fromΘ are considered in conjunction withthe MDRCL algorithm (denotedΘall, MDRCL); olive diamond, a subsetΛ40%, composedof 40% of the better potential routes calculated by the same AR in conjunction with theMDRCL algorithm (denotedΛ70%, MDRCL); green rectangle, a subsetΛ20%, composedof 20% of the better potential routes calculated by the same AR in conjunction with theMDRCL algorithm (denotedΛ20% MDRCL); and, blue upward triangle, a subsetΛ25%,composed of 25% of the better potential routes calculated by the same AR in conjunc-tion with the MDRCL algorithm (denotedΛ25% MDRCL), for a set of 16 wavelengths innetwork 2.

From Fig.5, we observe the performance of all WA heuristic algorithms in decreas-ing sequence, as follows: (1)Λ25%, MDRCL; (2) Λ20%, MDRCL; (3) Λ40%, MDRCL; (4)Θall, MDRCL; (5) Λ70%, MDRCL; (6) Λ90%, MDRCL; (7) WLC, DRCL; and (8)Λ10%,MDRCL. That result shows a highly successful performance of the MDRCL algorithm inconjunction with an AR and even alone, when all potential routes are considered, comparedwith the DRCL algorithm in conjunction with the same AR.

Figures6 and7 illustrate the blocking probability as a function of load for 8 and 16wavelengths in network 2, respectively. For a given connection request, if there are two ormore shortest-distance paths to be selected in network 2, the dynamic Dijkstra’s algorithmwill choose that shortest-distance path with the maximum number of free wavelengths.These figures show that the MDRCL algorithm outperforms the DRCL algorithm signif-icantly. Moreover, for a blocking probability of 1%, the MDRCL algorithm supports ap-proximately 20% more traffic load than does the DRCL algorithm for network 2, as shownin Figs.6 and7.


45 50 55 60 65 70 75 80 85 90 95 100 10510-4

10-3

10-2

10-1

Λ 10%, M-DRCL W LC, DRCL Λ 90%, M-DRCL Λ 70%, M-DRCL Θ all, M-DRCL Λ 40%, M-DRCL Λ 20%, M-DRCL Λ 25%, M-DRCL

Bloc

king

Pro

babi

lity

Load (Erlangs)

Fig. 5. Blocking probability versus load for network 2 with a set of 16 wavelengths perlink.

10 15 20 25 30 35 40 4510-6

10-5

10-4

10-3

10-2

10-1

fixed routing, FF dynamic dijkstra, DRCL W LC, DRCL Θall, M-DRCL Λ25%, M-DRCL

Blo

ckin

g Pr

obab

ility

Load (Erlangs)

Fig. 6. Blocking probability versus load for 8 wavelengths in network 2.


40 45 50 55 60 65 70 75 8010-6

10-5

10-4

10-3

10-2

10-1

fixed routing, FF dynamic dijkstra, RCL dynamic dijkstra, DRCL WLC, DRCL Θall, M-DRCL Λ25%, M-DRCL

Blo

ckin

g Pr

obab

ility

Load (Erlangs)

Fig. 7. Blocking probability versus load for 16 wavelengths in network 2.

Table3 shows the average simulation time of a single call using an AR (i.e., WLC) inconjunction with MDRCL, DRCL, and FF algorithms for networks 1 and 2. The WLC–FFalgorithm pair is the fastest to process 5×105 calls in the simulation. The FF algorithmis implemented in 76 C++ code lines. The WLC–DRCL algorithm pair is the slowest toprocess the calls because the AR needs to update its whole routing table before each newconnection request in order to match the best performance of the DRCL algorithm (theDRCL algorithm requires a routing table). The DRCL algorithm is implemented in 157C++ code lines. The WLC–RCL algorithm pair could process 5×105 calls in a lower sim-ulation time than WLC–DRCL because the RCL strategy is modified to accommodate themain boundary condition: the connection request matrix is unknown for all RWA algo-rithms. The original RCL strategy requires the connection request matrix and is describedin Ref. [8]. However, the RCL strategy, which is implemented in our simulator, is describedas the example in Section2 (see Table1). The RCL strategy is implemented in 150 C++code lines. Although the WLC–MDRCL algorithm pair takes 18.5% more processing timethan the WLC–FF algorithm pair, it achieves the best performance of all of algorithms interms of blocking probabilities. The propagation delay of routing information is neglectedin our simulation. With that observation, we verify that the MDRCL algorithm could savesignificant processing time in routing and WA calculation at each OXC compared withother dynamic WA algorithms (e.g., the DRCL algorithm), and the CPU can process 1 callper 40µs for network 1 or even 1 call per 120µs for network 2 easily. The CPU configu-ration used in our simulations is an Athlon 2 GHz with RAM of 256 Mbytes. According toRef. [15], if we consider the same average propagation delay between two nodes for net-work 1, that is 106.65µs, it will be feasible to implement the MDRCL algorithm in realisticoptical networks.

Figure8 shows the blocking probability of the MDRCL algorithm as a function of thepercentage of possible routes selected from AR or even all possible routes for 16 wave-lengths in network 2. The behavior of the blocking probability versus the percentage ofpossible routes is the same for any load. We observe that the MDRCL algorithm in con-junction with underlying AR works well and results in the lowest blocking probability at


Table 3. Single-Call Average Simulation Time Using WLC Algorithm in Conjunctionwith MDRCL, DRCL, RCL, and FF Algorithms for Networks 1 and 2

M-DRCL DRCL RCL FF Network 1 40µs 1.2ms 40µs 34µs Network 2 120µs 3.6ms 120µs 100µs

Λ25%. That the lowest blocking probability occurs at 25% potential routes is particular forthe given boundary conditions, e.g., a Poissonian traffic distribution and network topol-ogy (i.e., network 2), and cannot be understood as a general result for some other networktopology. However, for both network topologies considered in our simulation, the MDRCLalgorithm in conjunction with AR performed well atΛ25%. This implies that it is enough toselect a set of a few routes to composeΛ, instead of selecting all possible routes fromΘ.If Θall is considered (the 100% case in Fig.8), then the MDRCL algorithm will not dependon any routing algorithm. Consequently, the MDRCL algorithm could work alone, withouta routing algorithm, and even in this situation it results in lower blocking probability thanthe DRCL algorithm, as shown in Figs.5–8.

0 10 20 30 40 50 60 70 80 90 1000,00

0,01

0,02

0,03

0,04

0,05

Load 78 Erlangs Load 70 Erlangs Load 65 Erlangs Load 60 Erlangs

Bloc

king

Pro

babi

lity

Am ount of Routes (% )

Fig. 8. Blocking probability versus amount of possible routes for 16 wavelengths in net-work. The minimum under 20%–30% is particular to our simulation conditions and is nota general trend. An understanding of this behavior will be the subject of future work.

6. Conclusion

In conclusion, we have proposed and demonstrated a novel WA heuristic algorithm for in-telligent and transparent optical networks based on hop counts and relative capacity loss.Assuming all possible routes or a set of a few them, the proposed WA algorithm, calledmodified distributed relative capacity loss (MDRCL), chooses the wavelength that mini-


mizes the total relative capacity loss in the hop-based MDRCL table, where the selectedroute is chosen by minimum relative capacity loss.

The MDRCL algorithm leads to lower or equal blocking probability than does theDRCL algorithm. Another advantage of the MDRCL over the DRCL algorithm is that itcomputes either a set of a few paths or all of the paths, whereas the DRCL algorithm alwayscomputes all of them from a routing table, excluding the destination node. Moreover, theMDRCL algorithm dismisses the routing table, which contains a selected routing from anode to another, to choose a wavelength on the connection request. Since each node knowsthe network state and topology, the MDRCL algorithm can choose the wavelength from theoff-line–on-line calculation of a set of few possible routes. Therefore it is not necessary toupdate the routing tables.

It is easy to implement the MDRCL algorithm because of the single calculation ofrelative capacity loss per route from source to destination node of an arriving connectionrequest.

The MDRCL algorithm analyzes the influence of assigning the wavelength on the cur-rent call among the possible future calls and neighbor nodes in distributed environments.The results in this paper clearly show that considering the number of hops for the calcula-tion of relative capacity loss has a significant effect on the blocking probability of opticalnetworks.

Acknowledgments

J. F. Martins-Filho acknowledges financial support from Siemens Brazil (8° and 12° TA,Conv. 003/01 SIEMENS-UFPE) and the Conselho Nacional de Desenvolvimento Cientí-fico e Tecnológico (CNPq). Edson Moschim acknowledges financial support from ProjectKyatera of the State of São Paulo Research Foundation (FAPESP), and the authors ac-knowledge suggestions from Aleksandra Smiljanic and the interesting comments of AkeboYamakami and the reviewers.

References and Links[1] B. Mukherjee, “WDM optical communication networks: progress and challenges,” IEEE J. Sel.

Areas Commun.18, 1810–1824 (2000).[2] Paul Green, “Progress in optical networking,” IEEE Commun. Mag.39, 54–61 (2001).[3] Z. Zhang, J. Fu, D. Guo, and L. Zhang, “Lightpath routing for intelligent optical networks,”

IEEE Netw.15, 28–35 (2001).[4] ITU-T Recommendation G.8080, “Architecture for the automatically switched optical net-

works” (2001).[5] ITU-T Recommendation G.7715, “Architecture and requirements for routing in the automati-

cally switched optical networks” (2002).[6] A. Manzalini, K. Shimano, C. Cavazzoni, and A. D’Alessandro, “Architecture and functional

requirements of control planes for automatic switched optical networks: experience of the ISTProject LION,” IEEE Commun. Mag.40, 60–65 (2002).

[7] S. Even, A. Itai, and A. Shamir, “On the complexity of timetable and multicommodity flowproblems,” SIAM J. Comput.5, 691–703 (1976).

[8] X. Zhang and C. Qiao, “Wavelength assignment for dynamic traffic in multi-fiber WDM net-works,” in Proceedings of the Seventh International Conference on Computer Communicationsand Networks, Vol. 1 (IEEE, 1998), pp. 479–485.

[9] H. Zang, J. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approachesfor wavelength-routed optical WDM networks,” Opt. Netw. Mag.1, 47–60 (2000).

[10] R. A. Barry and S. Subramaniam, “The MAX-SUM wavelength assignment algorithm forWDM ring networks,” inDigest of Optical Fiber Communications Conference, Vol. 6 of 1997Technical Digest Series (Optical Society of America, 1997), pp. 121–122.


[11] R. Mewanou and S. Pierre, “Dynamic routing algorithms in all-optical networks,” inIEEECanadian Conference on Electrical and Computer Engineering 2003 (CCECE 2003) Proceed-ings, Vol. 2 (IEEE, 2003), pp. 773–776.

[12] E. Q. V. Martins and M. M. B. Pascoal, “A new implementation of Yen’s ranking loopless pathsalgorithm,” Q. J. Belgian, French Ital. Oper. Res. Soc.1(2), 121–133 (2003).

[13] L. Li and A. K. Somani, “Dynamic wavelength routing using congestion and neighborhoodinformation,” IEEE/ACM Trans. Netw.7, 779–786 (1999).

[14] R. Dante, E. Moschim, and J. F. Martins-Filho, “An Adaptive Routing Algorithm for Intelligentand Transparent Optical Networks,” Vol. 3124 of Springer-Verlag Lecture Notes in ComputerScience (Springer-Verlag, 2004), pp. 336–341.

[15] H. Zang, L. Sahasrabudd, J. P. Jue, S. Ramamurthy, and B. Mukherjee, “Connection manage-ment for wavelength-routed WDM networks,” inProceedings of IEEE Global Telecommunica-tions Conference 1999 (GLOBECOM ’99), Vol. 2 (IEEE, 1999), pp. 1428–1432.


Documents

Modiﬁed distributed relative capacity loss algorithm for ...repositorio.unicamp.br/bitstream/REPOSIP/57661/1/... · The DRCL algorithm is based on the RCL algorithm, but the connection