Side_1_360

service demands may very well share resources.
A simple strategy may be to begin with com-
pletely separated networks and later, when
enough operational experience is gained, merge
some classes. The resources that are released at
this stage can be used to satisfy a growing
demand.

The conclusion is that separation will, in many
cases, be the preferred option. The evolution of
MPLS and current interest in the concept con-
firm this assumption. A highly relevant question
is then how to design and manage separated net-
works of LSPs on top of a common MPLS
infrastructure.

4 The Design of Optimal

MPLS Networks

We now turn to the problem of how to design a
set of LSPs such that each origin-destination
(O-D) pair is connected by one or more LSPs
per service class. A survey of algorithms which
are more or less suitable for this purpose can be
found in [13].

We present two MPLS models. The first model,
presented in this section, finds and capacitates
optimal LSPs which support connection oriented
aggregates using, e.g., UDP for which the nota-
tion of equivalent bandwidth applies and some
CAC mechanism is in place. The second model,
presented in Section 5, finds and capacitates
optimal LSPs which support connectionless
aggregates using TCP for which equivalent
bandwidth makes no sense and best effort
applies.

4.1 The LSP Design Problem

Consider a network which consists of Nnodes
and Lphysical links. The network supports A
aggregates, each of which is characterised by its
origin ELR, destination ELR and service class.
Each aggregate acorresponds to a unique triple
(o,d,s): let n(a) = (o,d) denote that the origin and
destination nodes of aggregate aare oand d
respectively and let s(a) = sdenote that the ser-
vice class of aggregate ais s.

Let λadenote the Poisson arrival rate of connec-
tion requests in aggregate a. Let 1/μadenote the
mean connection holding time in aggregate a.
The holding time distribution is general. Let ρa
= λa/ μadenote the load offered by aggregate a.
A connection in aggregate agenerates revenue at
a rate θaper time unit.

Let Bldenote the bandwidth of the link lbetween
n(l) = (o,d) such that Bl> 0 denotes the existence
of a physical link from node oto node d.

A route ris a non-cycling sequence of physical

links connecting an origin node to a destination

node. An LSP on a single link route where |r| = 1

is said to follow a directroute and an LSP on a

multi-link route rwhere |r| > 1 is said to follow

atransitroute.

Let Radenote the set of LSPs including the

direct one (if it exists) that is used to carry

aggregate a. Let Aldenote the set of LSPs

including the direct LSP that uses link l.

Let xrdenote the bandwidth assigned to LSP r.

Let xa= (xr)r∈Radenote the bandwidths assigned

to the LSPs in Ra. The capacity C(a,xa) of the

LSP set Raused by aggregate ais given by

(1)

where fs(a)(x) is the equivalent number of ser-

vice class s(a) circuits configured on LSP r

which has bandwidth x. The equivalent number

of circuits is the maximum number of simultane-

ous connections that can be supported. The func-

tion will typically be non-linear unless peak rate

allocation is applied.

Let E(C(a,xa),ρa) denote the blocking probabil-

ity (objective function) experienced by aggregate

aconnections with load ρaon an LSP set of

capacity C(a,xa). The rate F(a,xa) at which

aggregate aconnections generate revenue when

the LSP configuration is xais

F(a,xa) = θaρa(1 – E(C(a,xa), ρa)). (2)

The LSP design problemis specified in terms of

the following constrained non-linear optimisa-

tion problem: Find the LSP configuration xopt

that maximises the revenue earning rate F(x)

Figure 1 Comparison of

sharing and partitioning

of bandwidth on a link

1

Traffic proportions 1:1

Traffic proportions 1:10

Traffic proportions 1:100

10 100 1000

Total offered traffic

Break even cost relationship

0.1

0.01

0.001

0.0001

C(a, xa)=

∑

r∈a

fs(a)(xr)