Side_1_360

Telektronikk 2/3.2001

Routing pattern: For a given network topology,

we define a routing pattern as a set of (possibly

multiple) directedroutes between pairs of nodes

in the network. If there is at least one route in

each direction between each pair of nodes, the

routing pattern is fully meshed.

Various static routing patterns are introduced

here with their possible realisation in an IP intra-

domain network. We also focus on some specific

IP routing strategies based on the modification

of the IGP routing with ER-LSP (Explicit

Routed Label Switched Path) created with

MPLS.

In the sequel the terms ER-LSP, tunnel, and

MPLS tunnel are indifferently used.

3.1 Single-path Routing Patterns

In a single-path routing pattern there is at most

one route between each pair of nodes. We can

distinguish symmetric single-path routing pat-

terns if the paths between Aand Band Band A

use the same edges for all pairs of nodes (A,B).

Single-path routing patterns may be divided into

the following interesting sub-classes:

• Shortest path routings patterns: If there
  exists a metric (a set of pairs of values, one for
  each direction, on the edges of the network)
  such that all paths of the routing pattern are a
  shortest path between the end-points accord-
  ing to that metric. A special case is when all
  shortest paths are also unique (unique shortest
  path).
  
  
  • Classical intra-domain routing protocols
    (OSPF, IS-IS) are based on such shortest
    path calculations. Administrative metric
    values are related to the system interfaces:
    between two routers a different metric value
    can be related to each interface of a same
    link. Resulting routing patterns can thus be
    symmetric or not.
  
  
  
  


• Routing patterns satisfying a sub-optimal-
  ity (SO) property: Two given paths having
  two points in common satisfy the sub-optimal-
  ity condition if they share the same sub-path

between these two points (Figure 1). Note that

this sub-optimality condition excludes traffic

load balancing and load distribution which

aim to divide at an intermediate node the traf-

fic toward the same destination on several dis-

tinct paths. Note also that routing patterns sat-

isfying the SO condition are necessarily sym-

metric. Routing patterns based on unique

shortest paths satisfy the sub-optimality condi-

tion when the metric values are the same on

the two interfaces of a link. The contrary is

false [Ben-Ameur&Gourdin_1].

• Destination-based single-path routing: Any
  packet is forwarded through the network using
  the destination address. Obviously, shortest
  path routing and sub-optimal routing are also
  based on destination. However, this class of
  routing patterns is larger. In fact, this is equiv-
  alent to establishing a spanning tree for each
  destination. The destination trees can be com-
  pletely independent.


• General single-path routing patterns with-
  out constraints: The whole traffic demand
  between an origin-destination pair is routed
  through a single path without any additional
  constraint.
  
  
  • In an IP network running a classical IGP
    routing protocol, only shortest path routing
    patterns can be realised. Other single-path
    routing patterns can be realised with the
    explicit routing functionality enabled by
    MPLS (strict ER-LSP). As an ER-LSP is
    always unidirectional, symmetric or direc-
    tional routing patterns can be realised.
    When the routing pattern is fully meshed,
    the total number of ER-LSP to create is
    equal to n* (n– 1) where nis the number
    of nodes.
  
  
  
  

In the sequel, for the sake of simplicity of the

study, we focus our attention on symmetric sin-

gle-path routing patterns only.Note that for

operational reasons this property is often re-

quired by network operators. One reason is to

limit the complexity of management of the net-

work. Another reason is to prevent having a

Eric Gourdin (38) obtained his
PhD in 1994 from the Ecole
Polytechnique de Montréal, doing
most of his PhD research at the
Groupe d’Étude et de Recherche
en Analyse des Décisions on
global optimization problems.
He worked on a grant from 1996
to 1998 at Université Libre de
Bruxelles on traffic management
problems. Since 1998 he has
been working with France Tele-
com R&D on various network
opitmization problems, espe-
cially the ones arising in the
context of new Internet routing
protocols. As of this year he is in
charge of a project aimed at
developing new models and
methods for network optimiza-
tion problems.

[email protected]

Bernard Liau (45) graduated
from the Ecole Nationale Supér-
ieure des Télécommunications,
Paris, France in 1979 and joined
France Telecom R&D in 1985.
His main research interests
have included traffic and net-
work modelling, optimisation of
telecom networks and cost ori-
ented pricing. He currently
leads the group of France Tele-
com R&D in charge of multi-
media network architecture
and optimisation.

[email protected]

Routing pattern satisfying

the sub-optimality condition

Routing pattern not satisfying

the sub-optimality condition

Figure 1 The sub-optimality condition

146