that link flows do not violate link capacity and (4) says

that li nk flo ws are nonne gative . The PRI MAL_I solution

specifies the , and so we have the optimal path with

arbitrary splitting for all sessions that minimize MLU.

Our objective is to find a practical method suited for IP

netwo rks that fo rces the t raffic to go through a set of op-

timal paths. To achieve this goal we should find a set of

new link metrics such that all paths which are specified

by PRIMALI problem can also be obtained by the short-

est path algor ithm in regard t o the new metrics. It means

that if

0

k

ij

X>

, then l ink should be selected by ses-

sion k according to the shortest path algorithm. Here we

assume that the shortest path algorithm is OSPF that

supports Equal-Cost Multi-Path (ECMP).

The load balancing methods introduced in [6,7] are

based on primal optimization problem. In this paper we

consider the dual optimization problem (DUAL_II)

which is obtained with respect to Lagrange Multipliers.

In other word we aim to distribute traffic by deter mining

the links weight. And It will be shown that t he Lagra nge

Multipliers comparable with constraint (3) can be inter-

preted as OSPF link metrics that satisfy the load balanc-

ing objective. Link metric in OSPF protocol must be an

inte ger be tween 1 and 655 35 but we will sho w in secti on

IV tha t the La gr an ge Multip lie rs that are o btains fro m the

solution of DUAL_II problem and comparable with con-

straint (3), do not satisfy this range in general. So the

following definition gives us the choice of an alternative

weight set.

Definition 1: Two weights set

{ }

1

L

ii

Ww

=

=

and

{ }

1

L

ii

Ww

=

′′

=

are equivalent with respect to a given graph

(,)

GNA with

L

links, if and only if the shortest paths

between any arbitrary nodes in

G

are the same consi-

dering any one of these two weight sets.

3. The Dual Problem

Before Before Defining the Lagrange multiplayer

{ }

1

N

ii

p=

comparable with constraint (2) and

{ }

,(,)

ij ij A

w

∈

compara-

ble with constr a int (3), the Lagrange polynomial is:

0

:( ,):(.)

(,)

(,,,)

k

ij

X

kk

i kijji

kK iNj i jAjjiA

k

ijij ij

ij AkK

LXMLUP W

MLUp DXX

w XC

≥

∈∈∈ ∈

∈∈

=+ −+

+−

∑∑∑ ∑

∑∑

(5)

For more details can be referred to chapter 5 of [9].To

achieve the dual problem the following equation should

be satisfied for each feasible X and

MLU

.

(,,, )MLULXMLUP W≥

(6)

To satisfy (6) we must have:

0

ij

w≥

. Now the func-

tion

(,)

gW P is defined as bellow:

,

(, )min(,, ,)

X MLU

gWPLXMLUP W=

(7)

So we have:

,

(, )

(, )

(, )min

()

(1)

kk

ii

X MLU

k

ij jiij

k K ijA

ij ij

ij A

gW PpD

Xp pw

MLUw C

∈∈

∈

=

+ −+

+−

∑∑

∑∑

∑

(8)

Because

ij

w

and k

ij

X are positive values, we have:

(,)

1

(,) 1

kk

iiijijij ij

k Ki N

ijijij ij

ijA

pDppwandC w

gW PppworC w

∈∈

∈

−≤ =

=−∞− ≥≠

∑∑ ∑

∑

(9)

The dual function is defined to maximize

(,)gW P

when all

ij

w

are positive values. Equation (10) shows

the DUAL_I problem that is the dual function of

PRIMAL_I.

max .(10)

k

kk

t

kK

pD

∈

∑

(11)

kk

ijij

ppw−≤

(, )

1 (12)

ij ij

ij A

Cw

∈

=

∑

Maximum Load Balancing with Optimized Link Metrics

Copyright © 2012 SciRes. JSEA

16

0 (13)

k

k

s

p=

0 (14)

ij

w≥

As the primal and dual problems are linear, strong

duality holds and according to complementary slackness

in KKT theorem if

ˆ

k

ij

X

is optimal solution of PRIM-

AL_I and

{

}

ˆˆ ,

k

ij ij

wp

is the optimal solution of DUAL_I

we have:

ˆ

ˆˆˆ

.() 0

kk k

ij ijij

Xp pw

−+ =

(15)

Equation (15) indicates that if session k passes link

(, )ij

then

kk

j iij

ppw−=

. According to theorem 1 in [8]

if

{ }

(,)

ˆ

ij ij A

w

∈

is used as a link metric in a shortest path

algorithm, all non empt y links (

0

k

ij

X>

) will be included

among the selected paths by the shortest path algorithm

procedure.

4. Practical Requirements

{ }

(,)

ij ij A

w

∈

that is calculated from the DUAL_I are equal

to or greater than zero. But as we mentioned before

OSPF link metrics cannot be zero. We show that there

exists a weight set equivalent to

{ }

(,)

ij ij A

w

∈

that can be

obtained using the new optimization problem.

Proposition 1: consider

(,)GNA

with weight set

{ }

(,)

ij ij A

w

∈

and some scalars

{ }

1

N

ii

δ

=

corresponding to

each link and node respectively. If we change the link

weight to

ijijji

ww

δδ

= +−

, then the weight set

{ }

(,)

ij ij A

w

∈

and

{ }

(,)

ij ij A

w

∈

are equivalent weight sets

with respect to

(,)GNA

[8]. To achieve non-zero

weight set we changed the weights of the links according

to algorithm 1.

Algorithm 1:

Step 1: For each session

kK∈

assign the scalar set

{ }

1

N

k

ii

δ

=

as follows:

● If there exists at least one directed path to node i from

source node of session k (k

s), the n

k

i

δ

is equal to th e

length of the longest hop-count non-loopy path from

k

sto i.

● Else

k

i

δ

is equal to zero.

Step 2: Assign the

max

k

i

k

δ

as the final scalar

i

δ

Step 3:

● If the

0

ji

δδ

−≥

then

ijijji

ww

δδ

= +−

● Else

1

ij ij

ww= +

.

So according to Proposition 1 and algorithm 1, there

exists an equivalent weight set to

{ }

(,)

ij ij A

w∈ that all of

them are greater or equal to one. Thus we can assume

.

ij ij

ij

Cw H=

∑

.

Theorem 1: consider two optimization p roblems called

DUAL_I and DUAL_II.

DUAL_I:

(,)

max .

1

0

0

k

k

kk

t

kK

kk

ijij

ij ij

ij A

k

s

ij

pD

ppw

Cw

p

w

∈

∈

−≤

=

=

≥

∑

∑

DUAL_II:

(,)

max .

0

1

k

k

kk

t

kK

kk

ij ij

ij ij

ij A

k

s

ij

pD

ppw

CwH

p

w

∈

∈

′

′′ ′

−≤

′=

′=

′≥

∑

∑

If

{ }

(,)

ˆ

ij ij A

w

∈

is an optimal solution of DUAL_I and

{ }

(,)

ˆ

ij ij A

w

∈

′

is an optimal solution of DUAL_II, the sets

{ }

(,)

ˆ

ij ij A

w

∈

and

{ }

(,)

ˆij ij A

w∈

′ are equivalent weight sets

with respect to

(,)GNA

.

Proof: Consider the optimization problem PRIM-

AL_II.

PRIMAL_II:

(,)

max. .

1

0

0

k

k

kk

t

kK

kk

ijij

ij ij

ij A

k

s

ij

HpD

ppw

Cw

p

w

∈

∈

−≤

=

=

≥

∑

∑

It is clear that the ij

X

s which minimizes the objec-

tive function of the problem PRIMALL_II are the same

as the ones which cause the problem PRIMALL_I to be

optimized.

The dual of PRIMAL_II is the DUAL_TEMP.

DUAL_TEMP:

(, )

max .

0

0

k

k

kk

t

kK

kk

ijij

ij ij

ij A

k

s

ij

pD

ppw

CwH

p

w

∈

∈

′

′′ ′

−≤

′=

′=

′≥

∑

∑

From complementar y slackness theorem

ˆˆˆˆ

.() 0

kk k

ij ijij

Xpp w

′′′

−+ =

(16)

Since the optimal solutions of the PRIMAL_I and

Maximum Load Balancing with Optimized Link Metrics

Copyright © 2012 SciRes. JSEA

17

PRIMAL_II are the same, thus the weight sets

{ }

(,)

ˆ

ij ij A

w

∈

and

{ }

(,)

ˆ

ij ij A

w

∈

′

are equivalent weight sets.

The weight set

{ }

(,)

ij ij A

w∈is the feasible set of the prob-

lem DUAL_TEMP and hold (16). Therefore it is the op-

timal solutio n o f t his problem.

So we in this way, we were able to obtain optimal

weights that do not include any link with weight 0 by

limiting the constraint

0

ij

w≥

to

1

ij

w′≥

. This converts

the problem DUAL_TEMP to DUAL_II. Figure 1 shows

the fl ow c hart of our method.

With ECMP routing a flow arriving at a node is split

evenl y ove r the l ink s on the sho rtest paths fro m this node

to the destination. It should be mentioned that arbitrary

routing is not possible once ECMP in OSPF is used. so in

OSPF environment we can never obtain the optimal

routing but we can get close to it as much as possible.

Objec tive function that is used in [8] is min

. The second term in this ob-

jective function cause to minimizes

(,)

k

ij

ij A

X

∈

∑

in addi-

tion to

MLU

. In this case the weight set resulted from

the dual function is

{ }

ij

wr+

(where

{ }

(,)

ij ij A

w

∈

are

Lagrange multipliers that correspond to the non-equal

constraint). The routing algorithm that we use in this

paper is OSPF. This protocol splits the traffic equally

among the available shortest paths, so we prefer traffic

splitting as much as possible even if it passes through

longer paths. As the constant

r

in the second term pre-

vents the flow to go through long paths we assume that

0r=

.

Figure 1 . Maximum load balancing flow chart.

5. Simulation Results

In this section we simulate the OSPF protocol with its

default link metrics and with the metrics that are calcu-

lated using the optimizatio n problem.

A. Scenario I : In fir st scenario the simula tion plat for m

is shown in Figur e 2.

All links in this network are DS3 with 44.7 Mbps rate.

We suppose FIFO as a queuing policy. The session is a

VOIP with GSM quality and the average bit rate is 40

Mbps. Node 1 is the source node and node 2 is the desti-

nation.

Table 1 show the solution of primal problem ( )

which indicate t he paths that mini mize maximum utiliza-

tion. Solution of DUAL_I problem is shown in Ta ble 2

and Ta b l e 3 show the solution of DUAL_II problem.

Figure 2. Simulation network to pology.

Table 1. O pt imum f lows.

X12

20

X13 20

X23 0

X24 20

X25 0

X35 20

X54 20

Table 2. The Soluti on of DUAL_ I.

w12 0.0056

w13 0.0017

w23 0

w24 0.0056

w25 0

w35 0.0077

w54 0.0017

Table 3. The Solution of DUAL_II.

W12 2 .0177

W13 1 .3567

W23 1 .0000

W24 1 .9823

W25 1 .0000

W35 1 .2843

w54 0.0017

Maximum Load Balancing with Optimized Link Metrics

Copyright © 2012 SciRes. JSEA

18

Table 1 sho w that t he opti mum pat hs are 1->2->4 and

1->3->5. These paths can obtain in a shortest path algo-

rithm regardin g to the weig hts that show in Table 2. Ta-

ble 2 and Table 3 are the equivalent weight s with respect

to the graph that shows in Figure 2. So we use the sub-

optimal weigh set in Table 3 instead of default OSPF

link metrics. Figure 3 show tha t in rec ent me thod p acket

drop decrease signifi cantly.

In fowlloing scenarioes (senario 2-) the simulation

plat for m is s ho wn in Fig ur e 4. We co mpare MLU, BWE

(Band width Efficiency), Nu mber of Over Utilized Links,

IP Traffic Dropped and IP Traffic Received for all scena-

rios

Figure.3. D ropping traffic in scenario1 for default protocol

and new method.

Figure 4. Si mulation Network T opology.

In fowlloing scenarioes (senario 2-) the simulation

plat for m is s ho wn in Fig ur e 4. We co mpare MLU, BWE

(Bandwidth Efficiency), Num ber of Over Utilized Links,

IP Traffic Dropped and IP Traffic Received for all scena-

rios

Scenario 2: In this scenario R1 is the traffic source and

R13 is the tra ffic destinat ion. Table 4 and Table 5 show

the Subo ptimal Link Weights that obt in by DUAL_II .

MLU in new method decreases from 91.3 percent to

36.3 percent and BWE increases from 7.6 percent to 10

percent as shown in Table 6.

Table 4. Solution of DUAL_ II f or Senario2.

W1_2 56.84 W3_6 1.000

W2_1

55.56

W6_3

1.000

W1_3

1.000

W3_7

1.000

W3_1

1.000

W7_3

1.000

W1_4

1.000

W4_9

1.000

W4_1

1.000

W9_4

1.000

W2_5

1.000

W4_8

1.000

W5_2

1.000

W8_4

1.000

W2_11

1.000

W5_12

1.000

W11_2

1.000

W12_5

1.000

W2_3

1.000

W6_11

1.000

W3_2

1.000

W11_6

1.000

W3_4

2.000

W6_10

1.000

W4_3

1.000

W10_6

1.000

Table.5. Solution of D UAL_ II, cont for Senario2.

W6_7 55.84 W10_13 1.000

W7_6

1.000

W13_10

1.000

W7_10

1.000

W10_14

1.000

W10_7

1.000

W14_10

1.000

W7_9

1.283

W11_12

1.000

W9_7

1.000

W12_11

1.000

W8_9

1.000

W11_13

1.000

W9_8

1.000

W13_11

1.000

W9_10

1.000

W12_13

1.000

W10_9

1.000

W13_12

1.000

W9_15

2.000

W13_14

1.000

W15_9

1.000

W14_13

1.000

W10_11

1.000

W14_15

1.000

W11_10

1.000

W15_14

1.000

Table 6. MLU and BWE v alue s for Senar io2.

Default

Algorithm Suboptimal

Algorithm

M LU 91.3 36.3

BWE 7.6 10

Number of Over

Utilized Lin k

0

0

Maximum Load Balancing with Optimized Link Metrics

Copyright © 2012 SciRes. JSEA

19

IP Traffic Dropped and IP traffic Received do not

change in this scenario because there is no congestion

Scenario 3: in this scenario we have three source-des-

tination pairs

11

(, )

sd ,

22

(, )sd

,

33

(, )sd

that are origi-

nated from R1 to R13, R5 to R9 and R4 to R2 respec-

tively. MLU in the new method decreases from 137 per-

cent to 91.3. The Number of over-utilized links also de-

creases from eight links to two links. BWE increases

from 26.6 percent to 31.4 percent, Table 7. F igure 5 and

Figure 6 show the comparison of IP Traffic Dropped and

IP Traffic Received

6. Conclusion

In this paper we show that Optimization Theory can help

Internet protocols work better. We use a duality theor y to

find a weight set that improve the routing protocols effi-

ciencies. As a matter of fact ro uting is the most i mportant

aspect of Internet Traffic Engineering. So we focus on

routing protocols and introduce a practical method that

optimizes Link Metrics. Previous optimization methods

suffer from practical issues but our method could be im-

plemented with Routing Protocols that based on

Table 7. MLU and BWE values for Senario 3.

Default

Algorithm Suboptimal

Algorithm

M LU 137 91.3

BWE 29.6 31.4

Number of Over

Utilized Link 8 2

Figure 5. Ssenario2 IP traffic dro pped.

Figure 6 . Ssenario2’s IP traffic received.

shortest paths. Our simulation results show significant

improvement on network e fficiency.

REFERENCES

[1] Y. Lee et al., “Traffic Engineering in Next-Generation

Optical Networks,” IEEE Commun. Surveys & Tutorials,

vol. 6, n o. 3, 2004, pp. 16 –33.

[2] D. Awduche et al, “Requirements on Traffic Engineering

over. 2. MPLS,” RFC 2702, June 1999.

[3] D. Awduche et al., “MPLS and Traffic Engineering in IP

Networks, IEEE Commun. Mag., vol. 37, no. 12, Dec.

1999, pp . 42–47.

[4] B. Fortz et al., “Internet Traffic Engineering by Optimis-

ing OSPF Weights,” Proc. IEEE INFOCOM, 2000, pp.

519–28.

[5] N. Hu et al., “Locating Internet Bottlenecks: Algorithms,

Measure-ments and Implications,” Proc. ACM SIG-

COMM, 2004, pp. 41–54.

[6] A.Marija et al “Two Phase Load balance Routing using

OSPF,” IEEE JOURNAL ON SELECTED AREAS IN

COMMUNICATIONS, VOL. 28, NO. 1, JANUARY

2010

[7] E. Oki et al” Load-Bal anced IP Routin g Scheme Based on

Shortest Paths in Hose Model” IEEE Transaction on

comminications, Volume : 58, Page(s): 2088 - 2 09 6, 2010

[8] Z. Wang, Y. Wang, and L. Zhang, ”Internet Traffic Engi-

neering without Full Mesh Overlaying,” INFOCOM’2001

[9] S. Boyd and L. Vanderberghe. Convex Optimization.

Cambrid ge U niv. Pres s, 20 04

[10] D. P. Bertsekas. Network Optimization: Continuous and

Discrete M odels Athena Sci entific, 1998