Side_1_360

where x= (x^1 , ..., xA) is subject to the constraints

xr> 0

for all routes r, and for all links l

In words, the constraints require that each LSP
has a strictly positive bandwidth and that the
bandwidths of the LSPs passing through link lin
total use the entire bandwidth of link l.

The necessary condition for xto be a local opti-
mum for F(x) is that for any route rin the LSP
set Ra

(3)

In words, equation (3) says that the change in
revenue obtained by moving an infinitesimal
amount of bandwidth to route rof aggregate ais
equal to the revenue lost in acquiring this band-
width from aggregates whose LSP sets include
direct LSPs over the links of r,and vice versa.

4.2 XFG: An LSP Optimisation

Algorithm

We wish to design an MPLS network were each
aggregate is supported by one or more LSPs. If a
flow is routed over more than one LSP, packets
belonging to the same flow may arrive out of
order at the destination. This can be avoided by
a systematic sub-classification of packets such
that any flow in an aggregate will always use the
same LSP. For example, if two LSPs with equal
bandwidth support an aggregate, packets may be
split between the LSPs according to the parity of
the full destination address.

4.2.1 A Bandwidth Market
The XFG algorithm is based on the concept of
bandwidth cost. Each aggregate computes the
price that it is willing to pay in order to buy
more bandwidth, and the price at which it is
willing to sell off bandwidth. An under-capaci-
tated aggregate will buy more bandwidth on an
existing LSP or establish a new LSP according
to where the largest revenue increase can be
made at the smallest bandwidth cost. An over-
capacitated aggregate will sell off bandwidth on
the LSP where the largest bandwidth cost can be
obtained for the smallest revenue decrease.

Bandwidth is traded in units the size of which is
typically determined by scheduling mechanism
constraints in the LSRs and quality of service
requirements from users. For example, LSRs

that schedule complete IP packets with a maxi-

mum size of 1540 bytes over links the band-

width of which is 2.048 Mbps will be able to

serve at most 2.048 × 106 / (1540 ×8) = 170

packets per second. If the quality of service

requires that a reserved bandwidth is to be

realised on a 100 ms time scale a link will corre-

spond to 0.1 ×170 = 17 units. Alternatively, if

the LSRs schedule ATM cells, at most 2.048 ×

106 / (53 ×8) = 4830 cells per second can be

served, hence a link corresponds to 483 units

under the same resolution requirements.

4.2.2 Link and LSP Prices

The gain Qa(c) obtained by allocating uaddi-

tional units of bandwidth to an LSP supporting

aggregate ais given by the increase in revenue

when the bandwidth of the LSP is increased

from cto c+ u. Thus

Qa(c) = F(a,c+ u) – F(a,c) (4)

where the link revenue function F(a,c) is given

in equation (2).

When the bandwidth of the aggregate aLSP

from node oto node dis increased from cto

c+u, the additional uunits of bandwidth are

obtained from aggregates with direct LSPs on

all links lon the route. The cost qa'(l)(c) of

acquiring uunits of bandwidth from an aggre-

gate a'(l),a'l∈Ra', is given by

qa'(c) = F(a',c) – F(a',c– u) (5)

where for each link l, class s(a'(l)) is the cheapest

provider of bandwidth on link land cis the class

s(a'(l)) bandwidth of link l.

Equations (4) and (5) approximate the deriva-

tives of equation (3). A cubic spline is fitted to

the values computed for equations (4) and (5) to

ensure that the values of left- and right deriva-

tives are identical.

The total cost qr(x) of acquiring a unit of band-

width from each link along the route r= (l 1 , ...,

lJ) is

4.2.3 The Algorithm

The XFG algorithm uses the model of a band-

width market to solve the LSP design problem

by allocating capacity to LSPs in a series of

transactions. The algorithm executes in a loop

and each iteration of the loop implements one

transaction. A transaction can either be a multi-

link LSP buying one unit of bandwidth from a

set of single link LSPs or a set of single link

LSPs buying one unit of bandwidth from a

multi-link LSP. The transaction chosen is the

F(xopt)=maxx F(x)=maxx

∑A

a=1

F(a, xa)

∑

r∈A 1

xr=B

∂

∂xr

F(a, xr)=

∑

∈r

∂

∂x


F(·,x
).

qr(x)=

∑J

j=1

qa′(
j)(c)