Side_1_360

path, then the packet will be forwarded in this

tunnel;

• “Advertise tunnels into the IGP”: In this
  model implemented by some manufacturers,
  tunnels are advertised in the IGP and used in
  the shortest path calculations as virtual inter-
  faces.

Depending on implementation details and in par-
ticular on the tunnels metric assignment, many
different options are possible in the path selec-
tion process. They give more flexibility to the
current IGP routing protocols: the resulting
routing patterns will not necessarily be shortest
paths, nor satisfy the SO condition, nor even be
destination based.

4 Routing Performance

Criteria for Best Effort

IP Traffic

We consider static routing patterns and best
effort traffic controlled by TCP. The perfor-
mance of routing patterns can be viewed from
the user’s point of view or from the network’s
point of view. This distinction is introduced in
[Awduche_2] where traffic oriented perfor-
manceand resource oriented performance
objectivesare defined:

• Traffic oriented performance: The quality of
  service perceived by end users is mainly
  determined by the (random) duration of a doc-
  ument transfer (Web page, e-mail, FTP file,
  etc.). Since the source traffic rates are reactive
  to the network load (TCP behaviour), the
  quality of service will depend on the link
  loads across the path;


• Resource oriented performance: From the
  operator’s point of view, the objective is to
  minimise resource utilisation (link capacity).
  Another objective can be the robustness of the
  traffic repartition against traffic fluctuations.
  The first objective implies that a routing pat-
  tern must be found such that another routing
  cannot be found with a lower load on each
  link and with a strictly lower load for at least
  one link. Such a routing pattern is said to be
  non dominated. The second objective can be
  partially addressed by looking for a routing
  pattern that minimises the maximum link load:
  such a routing pattern will be able to cope
  with the maximal traffic increase (with the
  assumption of a homogeneous traffic increase
  across all origin-destination demands).

For the sake of computational tractability, a sim-
ple performance criterion is required: it should
only be related to the edge loads and capacities,
but independent of the network topology and of
the effectively used routing paths.

Notations:

We consider a network defined by its set of

edges Land a given static routing pattern. Let Cl

be the capacity of edge land Albe the average

traffic load carried through this edge (this load

effectively depends on the routes within the net-

work). The average load of edge lis defined as

ρl=Al/ Cl. A routing pattern is said to be feasi-

ble if ρl≤1 for every edge.

Criteria based on the edge loads:

It seems natural to try to maximise a concave

decreasing function of the edge loads as for

instance:

, α≥0, α≠1(1)

This function was proposed and studied in

[Mo&Warland] and [Bonald&Massoulié].

When αis close to 1, the function (1) is equiva-

lent to.

Therefore, for α= 1, criterion (1) can be ex-

tended and replaced by.

A routing is said to be optimal if it is able to

carry the whole traffic flow minimising criterion

(1). An interpretation can be proposed for some

values of α:

• α= 0 minimises the average edge load. This is
  a simple criterion but we would not recom-
  mend it because it is unable to differentiate
  two links with respective loads of 0 % and
  100 % and two links 50 % loaded (contrarily
  to the case α> 0, the function is not strictly
  concave);


• α= 1 maximises , equivalently
  the geometric mean of (1 – ρl);


• α= 2 minimises , equivalently
  the harmonic mean of (1 – ρl);


• α= ∞corresponds to a “min-max” criterion.
  One is successively interested in minimising
  first the maximum load, then the second maxi-
  mum load, and so on.

The higher the value of αis, the more attention

is paid to the most heavily loaded edge.

Criteria based on the edge residual

capacities:

It is also possible to replace in (1) the edge load

by the residual capacity Cl(1 – ρl). Objective

∑1/(^1 −ρl)

∑log(^1 −ρl)

∑log(^1 −ρl)

L

1 −α

+

l∈L

∑log 1(−ρl)

1

1 −αl∈L

∑(^1 −ρl)

1 −α