Side_1_360

will never be completely up-to-date due to the

non-negligible delay of the information dissemi-

nation process. The larger the network, the more

imprecise the information gets.

To reduce the scalability problem for larger net-

works, information may be aggregated according

to the hierarchical structure of the network,

obtaining an aggregated (partial) global state

view. [CHEN98] has described these matters in

more detail.

3.2.2 The Unicast Routing Problem

The unicast routing problemis defined as fol-

lows: given a source node s, a destination node t,

a set of QoS constraints C, and possibly an opti-

misation goal, find the best feasible path from s

to tthat satisfies C.

QoS requirements on metrics such as residual

bandwidth and buffer space, so-called “bottle-

neck” requirements, are relatively easy to han-

dle. The state of the resulting path is determined

by the state of the bottleneck link. In Figure 3.1,

the bandwidth of path s – i – j – tis 1, which is

the bandwidth of the bottleneck link (i, j). In this

case, two basic routing problems may be de-

fined. One problem is called link-optimisation

routing. For example, bandwidth-optimisation

routing is to find a path that has the largest band-

width on the bottleneck link (the widest path).

The other problem is called link-constrained

routing. For example, bandwidth-constrained

routing is to find a path whose bottleneck link

has a bandwidth above a required value.

QoS requirements on metrics such as delay and

cost, so called “additive” requirements, are more

complex to handle. The state of the path is deter-

mined by the combined state of all links on the

path. In Figure 3.1, the delay of path s – i – j – t

is 10, which is the total delay of all links on the

path. In this case, two basic routing problems

may be defined. One problem is called path-

optimisation routing. For example, least-cost

routing is to find a path whose total cost is min-

imised. The other problem is called path-con-

strained routing. For example, delay-constrained

routing is to find a path whose delay is bounded

by a required value.

A number of composite routing problems can be

derived from the four basic problems cited above.

Some of these composite routing problems are

hard to solve. For details, see [CHEN98].

Proposed traffic engineering extensions to OSPF

[OSPF-TE] and IS-IS [ISIS-TE] currently sup-

port the advertisement of a single routing metric,

in addition to bandwidth and resource class

information. Additional link metrics, e.g. delay-

related metrics, are not supported. Thus, infor-

mation will not be directly available “on-line”

for calculating paths with delay-related QoS

requirements. A solution to get around this

might be to use the resource class information

(link colour) to mark links, so that e.g. satellite

links are avoided for delay-sensitive traffic.

There is work in progress that considers IGP

extensions supporting multiple metrics, see e.g.

[Fedyk].

3.2.3 Path Precomputation versus

Dynamic QoS Routing

QoS routing may primarily be aimed at traffic

engineering, and the operation is characterised

by a long timescale and a coarse granularity of

the traffic flow it handles (traffic aggregates). In

this case, the goal of QoS routing is to maximise

the network performance in the presence of

slowly changing traffic patterns. The different

paths computed by QoS routing are either pre-

established or change only infrequently. Several

proposed QoS routing protocols are based on

precomputing paths for all possible QoS require-

ments, and then assign traffic to the paths

accordingly. An example would be the establish-

ment of MPLS LSPs to accommodate traffic

with varying QoS requirements (e.g. DiffServ

classes). A drawback here is that the use of traf-

fic aggregates and the focus on network wide

traffic optimisation cannot provide explicit QoS

guarantees to individual flows. The precomputa-

tion perspective of QoS routing is described in

detail in [ORDA00].

The other extreme is to compute QoS routes for

each request, where each request explicitly

express its resource requirements (e.g. similar

to IntServ). The QoS routing will in this case

be constrained by satisfying individual QoS

requirements, rather than obtaining a more

global optimisation of network performance

and resource usage.

Figure 3.1 Network state
[CHEN 98]

(2,2,1)

ij

st

kl

(1,6,1)

(2,1,2)

(5,2,3)

(1,2,2.5)

(2,2,3)

(2,1,1)

(1.5,2,6.3)

Link state = (bandwidth, delay, cost)