Koster A., Munoz X. Graphs and Algorithms in Communication Networks

Подождите немного. Документ загружается.

168 M. Klinkowski et al.

=v (1-E)(1- )

ijlm

E (1-E)(1-E )

link e

(a) Reduced CS

=v (1-E)(1- )

link e

(b) Reduced OBS

=v +...+v

...

link e

Fig. 6.1 Link load models

CS and OBS networks (see [9] and [21], respectively). Although the ﬁxed point is

unique in CS networks, its uniqueness has not been proved in OBS networks.

Although the trafﬁc offered to a route is Poisson, it may still be thinned by

blocking at consecutive links and thus no longer remain Poisson. Since there is

no straightforward solution to this problem, we make a simpliﬁcation that the burst

arrival process to each link is Poisson.

Non-reduced load (NRL). Formulation (6.2) may bring some computational difﬁ-

culty, especially with regard to the calculation of partial derivatives for optimization

purposes. Therefore, we also consider a simpliﬁed non-reduced load model, where

the trafﬁc offered to link e is calculated as a sum of the trafﬁc offered to all paths

that cross this link:

∑

p∈P

, e ∈E. (6.4)

The rationale behind this assumption is that under low link losses E

, f ∈ E, ob-

served in a properly dimensioned network, model (6.2) can be approximated by

(6.4).

Figure 6.1 presents illustrative examples of the reduced load calculation for both

CS and OBS networks, as well as of the non-reduced load calculation.

6.3.2 Network Loss Calculation

Overall network loss (NL). The calculation of overall burst loss or blocking prob-

ability in an OBS network is presented in [21], and it uses the same formulation

as was proposed for CS networks [9]. In further discussion we name this model an

overall network loss (NL) model.

The main modeling steps include the calculation of

6 Routing Optimization in OBS Networks 169

1. burst loss probabilities E

on links, given by (6.1),

2. loss probabilities L

of bursts offered to paths

= 1 −

∏

e∈p

(1−E

), p ∈ P,and (6.5)

3. the overall burst loss probability B

∑

p∈P

∑

p∈P

−1

. (6.6)

In order to calculate the path loss probability L

, p ∈ P,wemakeanassumption

that burst blocking events occur independently at the network links. Then formula

(6.5) accounts for blocking probabilities in all links e that belong to path p.

The overall burst loss probability B

is calculated simply as the volume of burst

trafﬁc lost in the network normalized to the volume of burst trafﬁc offered to the

network.

Overall link loss (LL). Another method for calculation of burst losses in the entire

network is based on an overall link loss (LL) model [6]. In this method we sum up

the volumes of trafﬁc lost on individual network links.

The main modeling steps include the calculation of

1. burst loss probabilities E

on links, given by (6.1), and

2. B

, a sum of the burst trafﬁc lost on individual links relative to the overall trafﬁc

offered to the network

∑

e∈E

∑

p∈P

−1

. (6.7)

LL overestimates actual burst losses given by (6.6) in NL because it counts twice

the intersection of blocking events that occur on distinct links. In fact, B

may be

higher than 1, and thus it cannot be considered as the probability metric. Neverthe-

less, for E

→0, e ∈E, the blocking events that occur simultaneously vanish rapidly,

and model (6.7) converges to model (6.6).

6.3.3 Multi-path Source Routing

We assume that the network applies source-based routing, so that the source node

determines the path of a burst that enters the network (see Figure 6.2). Moreover, the

network uses multi-path routing where each subset P

comprises a (small) number

of paths, and a burst can follow one of them. We assume that the selection of a route

from set P

is random for each burst and is performed according to a given trafﬁc

splitting factor x

, such that

170 M. Klinkowski et al.

AA1

burst

path 1

path 2

Fig. 6.2 An example of OBS network with source-based routing; x

and x

are the trafﬁc splitting

factors and x

+ x

= 1

0 ≤ x

≤ 1 p ∈ P, (6.8a)

∑

p∈P

= 1 s,t ∈V, s = t. (6.8b)

Thus trafﬁc

offered to path p ∈P

can be calculated as

= x

, (6.9)

where

is the total trafﬁc offered between s and t.

Here vector x =(x

,...,x

|P|

) determines the distribution of trafﬁc over the net-

work; this vector should be optimized to reduce congestion and to improve overall

performance.

6.4 Resolution Methods and Numerical Examples

6.4.1 Formulation of the Optimization Problem

Taking into account different methods of the link load and the network loss cal-

culation presented in Section 6.3, several network loss models with corresponding

objective functions can be deﬁned.

1. NL-RL. The link load is calculated according to the RL model given by (6.2),

and the network loss is calculated according to the NL model given by (6.6), with

the objective function given by

NL−RL

(x)=

∑

p∈P

. (6.10)

2. NL-NRL. The link load is calculated according to the NRL model given by (6.4),

and the network loss is calculated according to the NL model given by (6.6), with

the objective function given by

6 Routing Optimization in OBS Networks 171

NL−NRL

(x)=

∑

p∈P

. (6.11)

3. LL-NRL. The link load is calculated according to the NRL model given by (6.4),

and the network loss is calculated according to the LL model given by (6.7), with

the objective function given by

LL−NRL

(x)=

∑

e∈E

∑

e∈E



∑

p∈P



. (6.12)

The last possible combination of the link load and the network loss calculation is

LL-RL. Because such a model does not bring much gain with respect to the NL-

RL model, as it does not avoid the complexity of ﬁxed-point calculation, we do not

study it.

In each case the normalization factor

∑

p∈P

−1

has been omitted because we

assume it to be a constant value.

The optimization problem is the same for each method, and is formulated as

follows:

min

B(x) (6.13)

subject to the multi-path routing constraints given by (6.8a) and (6.8b).

Since in each case B(x) is a nonlinear function of vector x, the optimization prob-

lem is nonlinear. Taking into account the form of both constraints (6.2) and (6.4),

a particularly convenient optimization method is the Frank-Wolfe reduced gradient

method (algorithm 5.10 in [19]); this algorithm was used for a similar problem in

circuit-switched (CS) networks [7].

6.4.2 Calculation of Partial Derivatives

In general, gradient methods are iterative methods used in the optimization of con-

vex functions. Gradient methods need to employ the calculation of partial deriva-

tives of the cost function to ﬁnd the direction for its improvement. Below, we pro-

vide adequate formulas for the partial derivatives for each of the models.

NL-RL model. The partial derivative of B

NL−RL

with respect to x

, q ∈ P, can be

derived directly by a standard method involving the solution of a system of linear

equations. It follows from (6.2) and (6.1) that

∂ρ

(x)

∂

∑

p∈P

∑

f ∈r

(1−E

)

−1

∂

(x)

∂

, e ∈E,q ∈ P,

(6.14)

172 M. Klinkowski et al.

where

= 1ife ∈ q, and

= 0 otherwise, and

∂

(x)

∂

= E

(

−

)

∂ρ

(x)

∂

, e ∈E,q ∈ P. (6.15)

In order to solve the system of equations (6.14)–(6.15), a ﬁxed-point calculation

procedure, i.e., repeated substitution of (6.14) in (6.15), has to be applied.

From (6.5) we have

∂

(x)

∂

=(1−L

)

∑

e∈p

(1−E

)

−1

∂

(x)

∂

, p,q ∈ P, (6.16)

and ﬁnally from (6.10),

∂

BNL −RL(x)=

∑

p∈P

∂

(x)

∂

, q ∈P. (6.17)

The calculation of partial derivatives (6.14)–(6.17) in NL-NRL model is extremely

time consuming since it involves an iterative ﬁxed-point approximation procedure.

NL-NRL model. The partial derivative of B

NL−NRL

with respect to x

, q ∈P, could

be derived directly from formulas (6.1) and (6.4)–(6.6) by a standard method involv-

ing resolution of a system of linear equations, similarly to (6.14)–(6.17). Although

there is no need for a ﬁxed-point calculation in NL-NRL model, still such a compu-

tation would be time consuming.

Therefore, we propose instead a straightforward exact calculation based on the

approach for CS networks by Kelly [10]; a detailed derivation of formulas is pre-

sented in [11]. In particular, for each path q ∈ P we have

∂

NL−NRL

(x)=

∑

e∈q

, (6.18)

where c

is calculated for each link e ∈E as

∑

p∈P

(1−L

), (6.19)

and

= E(

−1) −E(

), e ∈E. (6.20)

Due to assumption (6.4) we have managed to simplify the model (6.2) and make

the calculation of partial derivatives deﬁned by (6.18) and (6.19) straightforward,

not involving any iterations. Indeed, once

of unknowns (c

) are pre-calculated

they can be used in (6.18) to obtain the partial derivatives. Calculating the gradient

in this method, therefore, is not longer an issue.

6 Routing Optimization in OBS Networks 173

1,E-06

1,E-05

1,E-04

1,E-03

1,E-02

1,E-01

0,4 0,5 0,6 0,7 0,8

Erlangs

Burst loss probability

SPR (sim)

MR, NL-NRL (sim)

MR, NL-RL (an)

MR, NL-NRL (an)

MR, LL-NRL (an)

-2

-4

-3

-5

-1

-6

Offered load, Erlangs

Burst loss probability

19,2 25,616 22,412.8

Fig. 6.3 Validation of optimization models

LL-NRL model. The partial derivative of B

LL−NRL

with respect to x

, q ∈ P, can

be derived directly from formulas (6.1), (6.4), and (6.12),

∂

LL−NRL

(x)=

∑

e∈q

(1−E

))

, (6.21)

where

is given by equation (6.20).

6.4.3 Numerical Results

We evaluated the performance of our multi-path source routing scheme in an event-

driven simulator. In order to ﬁnd a splitting vector x specifying near-optimal rout-

ingweusedasolverfmincon for constrained nonlinear multivariable functions

available in the M

ATLAB optimization toolbox. Then we applied this vector in the

simulator.

The evaluation was performed for NSFNET, an American backbone network

topology of 15 nodes and 23 links [17]; each link had C = 32 wavelengths and the

transmission bitrate in each wavelength channel was 10 Gbit/s. Besides the results

of optimized multi-path routing (MR) we provide, for comparison, the results of

two other routing strategies: simple shortest path routing (SPR) and pure alternative

routing (AR). We considered two shortest paths per source-destination pair of nodes

in MR; they were not necessarily disjoint. In SPR only one path was available, while

in the case of AR we considered two different scenarios: with two and six paths

available. Uniform trafﬁc matrix and exponential burst inter-arrivals and durations

were considered. All the simulation results had 99% level of conﬁdence.

In Figure 6.3 we show the overall burst loss probability results of the MR strategy,

which was optimized with the assistance of NL-NRL, NL-RL, and LL-NRL models,

174 M. Klinkowski et al.

1,E-06

1,E-05

1,E-04

1,E-03

1,E-02

1,E-01

1,E+00

0,4 0,6 0,8 1 1,2

Erlangs

Burst loss probability

SPR, 1 path

AR, 2 paths

AR, 6 paths

MR, 2 paths

-2

-4

-3

-5

-1

-6

Offered load, Erlangs

Burst loss probability

25,6 38,419,2 3212.8

Fig. 6.4 Performance comparison of routing strategies (simulation results)

successively. The characteristics are obtained in the function of offered trafﬁc load,

which is normalized to the wavelength bitrate and expressed in Erlangs (e.g., 12.8

Erlangs means that each node generates 128 Gbit/s). As a reference, we provide the

results of SPR.

In the studied scenario, we can see that the burst loss probability results of opti-

mized MR evaluated in the M

ATLAB environment are (almost) the same regardless

of the network loss model used. Moreover, the analytical results obtained for NL-

NRL model agree very well with simulation results (’(sim)’ in Figure 6.3).

In Figure 6.4 we compare simulation results obtained for different routing sce-

narios. We see that the optimized multi-path routing outperforms the shortest path

routing in the whole range of trafﬁc loads. Also, it offers at least as good results as

the alternative routing if the same number of routing paths is available.

6.5 Discussion

In this section we investigate the accuracy of network loss models and the charac-

teristics of the objective function. We also discuss the computational effort of the

optimization procedure.

6.5.1 Accuracy of Loss Models

We study the accurary of both NR-NRL and LL-NRL network loss approximations

relative to the NL-RL network loss model. To do that we deﬁne the approximation

error as

6 Routing Optimization in OBS Networks 175

Approximation errors relative to NL-RL model

-2,E-01

0,E+00

2,E-01

4,E-01

6,E-01

8,E-01

1,E+00

1,00E-04 1,00E-03 1,00E-02 1,00E-01 1,00E+00

Blocking Probability, B_NL-RL

Relative error

NL-NRL, C=8

LL-NRL, C=8

NL-NRL, C=32

LL-NRL, C=32

-4

0.2

-0.2

0.4

0.6

0.8

1.0

-3

-2

-1

Blocking Probability,B

NL-RL

Relative error,(B-

B )/B

NL-RL NL-RL

Fig. 6.5 Approximation errors relative to NL-RL model vs. blocking probability; NSFNET, short-

est path routing, eight and 32 wavelengths



−B

NL−RL

, (6.22)

where X refers to either NL −NRL or LL −NRL;soB

means the result of the

objective function for model X.

In Figure 6.5 we present the results of Er

obtained in NSFNET network, with

a different number of wavelengths per link considered and the shortest path routing

used. We can see that the accuracy of both network loss approximate models is very

strict for the blocking probability in the network B

NL−RL

below 10

−2

6.5.2 Properties of the Objective Function

NL-RL model. In [10], Kelly demonstrated that the reduced load loss model of a

CS network is in general not convex. Taking into account an analogy of the reduced-

load calculation in both CS and OBS networks, we can expect that function (6.10)

is not convex as well. Therefore, a solution of optimization problem (6.13) may not

be unique.

NL-NRL model. As in the case of the RL-NL model, it can be shown numerically

that the objective function (6.11) is not necessarily convex; in particular, under high

trafﬁc load conditions, two feasible vectors x

can be found such that

NL−NRL

(

+(1 −

) >

NL−NRL

)+(1 −

NL−NRL

), (6.23)

where 0 ≤

≤ 1.

176 M. Klinkowski et al.

Table 6.1 Comparison of computation times

NL-RL NL-NRL LL-NRL

Network Paths Tol. BLP OF SOLV OF SOLV OF SOLV

SIMPLE 2 10

−6

2.4·10

−3

64sec 1.5sec 0.1sec 1.4sec 0.1sec 1.5sec

SIMPLE 4 10

−6

2.4·10

−3

243sec 3sec 0.1sec 3.4sec 0.1sec 3.1sec

NSFNET 2 10

−6

4.6·10

−2

> 5h 0.38sec 22.3sec 0.37sec 24.3sec

NSFNET 4 10

−6

3.1·10

−2

> 5h 1.6sec 937sec 1.5sec 952sec

EON 2 10

−6

1.76·10

−2

> 5h 5.5sec 803sec 5.3sec 837sec

EON 2 10

−3

1.77·10

−2

> 5h 1.1sec 260sec 1.0sec 263sec

LL-NRL model. An advantageous property of the LL-NRL model is the convexity

of its objective function (6.12); a detailed proof can be found in [13]. For this reason,

a corresponding optimization problem has a unique solution.

6.5.3 Computational Effort

In Table 6.1 we compare the computation times of both the objective function (with

the partial derivatives calculation included) and the fmincon solver function of

the M

ATLAB environment; in the table they are denoted as OF and SOLV, respec-

tively. The evaluation is performed on a Pentium D, 3 GHz computer. The results

are obtained for SIMPLE (six nodes, eight links, and 60 paths), NSFNET (15 nodes,

23 links, and 420 paths), and EON (28 nodes, 39 links, and 1,512 paths) network

topologies; the number of wavelengths per link is 32, each source-destination pair

of nodes has two or four shortest paths available, the trafﬁc load is equal to 25.6 Er-

langs and 19.2 Erlangs, respectively, for SIMPLE/NSFNET and EON scenarios. In

case the iterative procedure of the Erlang ﬁxed-point approximation is used, it ends

if the maximal discrepancy between two consecutive link loss calculations is smaller

then 10

−6

. The starting trafﬁc splitting vector is x = 0.5·(1,...,1), meaning that the

trafﬁc is equally distributed on the paths for each demand.

We can see that the calculation of the objective function (and of partial deriva-

tives) is highly time consuming in the NL-RL model even in a small network sce-

nario. In contrast, such a calculation is not an issue if either the NL-NRL or the

LL-NRL model is used. It is worth noting that by decreasing the value of a termi-

nation tolerance parameter (’Tol.’ in the table), which decides on the termination

of the solver function, we signiﬁcantly accelerate the optimization procedure (more

than three times) without substantial decrease of routing performance (compare BLP

value in both EON scenarios). Moreover, we can see that by increasing the number

of paths the computation time of the solver function increases considerably in a

larger (NSFNET) network scenario.

6 Routing Optimization in OBS Networks 177

6.6 Conclusions

In this chapter we have studied a nonlinear optimization method for the multi-path

source routing problem in OBS networks. In this method we calculate a trafﬁc split-

ting vector that determines a near-optimal distribution of trafﬁc over routing paths.

Since a conventional network loss model of an OBS network is complex, we have in-

troduced some simpliﬁcations. The proposed models are computationally effective

and are still highly accurate compared to the basic model. The obtained formulas

for partial derivatives are straightforward and very fast to compute. It makes the

proposed nonlinear optimization method a viable alternative to linear programming

formulations based on piecewise linear approximations of the cost function.

The simulation results demonstrate that our method effectively distributes the

trafﬁc over the network and the overall burst loss probability can be signiﬁcantly

reduced compared with the shortest path routing.

Acknowledgements Part of the results have been achieved during a Short Term Scientiﬁc Mission

of EU COST action 293 – Graphs and Algorithms in Communication Networks (GRAAL) – and

EU COST action 291 – Towards Digital Optical Networks. The work was supported by the Spanish

Ministry of Education and Science under the CATARO project (Ref. TEC2005-08051-C03-01).

References

1. Cameron, C., Zalesky, A., Zukerman, M.: Prioritized deﬂection routing in optical burst switch-

ing networks. IEICE Trans. on Comm. E88-B(5), 1861–1867 (2005)

2. Coutelen, T., Elbiaze, H., Jaumard, B.: An efﬁcient adaptive offset mechanism to reduce burst

losses in OBS networks. In: Proceedings of Proceedings of IEEE Global Communications

Conference (GLOBECOM 2005). St. Louis, MO (USA) (2005)

3. Du, Y., Pu, T., Zhang, H., Quo, Y.: Adaptive load balancing routing algorithm for optical

burst-switching networks. In: Proceedings of Optical Fiber Communication Conference (OFC

2006). Anaheim, CL (USA) (2006)

4. Eramo, V., Listanti, M., Paciﬁci, P.: A comparison study on the number of wavelength con-

verters needed in synchronous and asynchronous all-optical switching architectures. Journal

of Lightwave Technology 21(2), 340–355 (2003)

5. Gao, D., Zhang, H.: Information sharing based optimal routing for optical burst switching

(OBS) network. In: Proceedings of Optical Fiber Communication Conference (OFC 2006).

Anaheim, CL (USA) (2006)

6. Girard, A., Sanso, B.: Multicommodity ﬂow models failure propagation, and reliable loss

network design. IEEE/ACM Trans. on Net. 6(1), 82–93 (1998)

7. Harris, R.: The modiﬁed reduced gradient method for optimally dimensioning telephone net-

works. Australian Telecom. Research 10(1), 30–35 (1976)

8. Hsu, C., Liu, T., Huang, N.: Performance analysis of deﬂection routing in optical burst-

switched networks. In: Proceedings of the 21st Joint Conference of IEEE Computer and

Communications Societies (INFOCOM 2002). New York, NY (USA) (2002)

9. Kelly, F. P.: Blocking probabilities in large circuit-switched networks. Advanced Applied

Probability 18, 473–505 (1986)

10. Kelly, F. P.: Routing in circuit-switched networks: Optimization, shadow prices and decentral-

ization. Advanced Applied Probability 20, 112–144 (1988)