131
today, and the functionalities that are already
implemented there. Also mentioned are new
requirements that cannot be satisfied with
today’s routing protocols.2.1 Routing Basics
2.1.1 Routing Functionalities
Although different networks employ different
routing algorithms, they all share a core of basic
routing functionality [STEE95]. The first of the
core routing functions is collecting network and
user traffic state informationthat is used in gen-
erating and selecting routes, and keeping it up to
date. The state information includes service
requirements and current locations of users, ser-
vices provided by and resources available within
the network, and restrictions on the use of these
services and resources.The second core routing function is generating
and selecting feasible and even optimal routes
based on user and network state information.
Feasible routes are those that satisfy all the user-
and network-imposed service constraints. Opti-
mal routes are feasible routes that are “best”
with respect to a specific performance objective.Forwarding user traffic along the routes
selectedwas defined as another core routing
function. In recent years, however, the term for-
warding is classified as a separate function,
while routing is now used to describe the first
two functions [BLAC00].2.1.2 Routing Protocol Requirements
Routing protocols are the protocols that establish
mutually consistent routing tables in every router
in the network. The manner in which the route is
calculated is based on a routing algorithm, and
the algorithm is a very important part of the
overall routing architecture.Some design goals can be established for routing
algorithms [THOM98]:- Simplicity: Since route management is an
overhead component in a router, it must not
consume too much overhead. As far as possi-
ble, routing algorithms should be simple, and
they should not consume a lot of memory and
CPU capacity. - Robustness: During periods of unusual types
of traffic or large volumes of traffic, they
should not fail. If they fail, it should not mean
a complete loss of routing capacity. The goal
of robustness is one aspect of the goal of accu-
racy. - Convergence: Once a change occurs that
requires a route recalculation, the update mes-
sages and resulting recalculation of the routes
is done quickly, and all nodes reach agreement
(convergence) quickly.- Flexibility: A routing algorithm should acc-
ommodate different metrics; it should support
default routes; it should allow a hierarchy of
routing domains, it should support one or
more than one path to a destination, etc. - Accuracy: It makes little difference if the
route-calculation algorithm is simple, robust,
or whatever, if it does not calculate and select
accurate routes according to the “best” routing
criteria. Of course, the best route depends on
the metrics and the algorithm’s use of the met-
rics.
2.1.3 Choices in Routing Protocol
Design
Designers of routing protocols have many mech-
anisms available to them. In this section, we will
describe some commonly available choices for
routing [MEEL90]. These choices also represent
a rough taxonomy to categorise routing proto-
cols.- Centralised vs. distributed routing:In cen-
tralised routing, a central processor collects
information about the status of each link (up
or down, utilisation, capacity, etc.) and pro-
cesses this information to compute a routing
table for every node. It then distributes these
tables to all the routers. In distributed routing,
routers co-operate using a distributed routing
protocol to create mutually consistent routing
tables. Centralised routing is reasonable when
the network is centrally administrated and the
network is not too large. However, it creates a
single point of failure, and the concentration
of routing traffic to a single point. - Intra-domain routing vs. inter-domain routing:
The nodes are grouped into regions on differ-
ent levels. This implies that the nodes have
full knowledge of the topological structure
within one region, but only a few are responsi-
ble for the routing between the regions. A spe-
cial case here will be the routing between
domains on a general basis, e.g. between
autonomous systems (AS). - Source-based vs. hop-by-hop:A packet header
can carry the entire route (that is, the address
of every router on the path from the source to
the destination), or the packet can carry just
the destination address, and each router along
the path can choose the next hop.These alter-
natives represent extremes in the degree to
which a source can influence the path of a
packet. A source route allows a sender to
specify a packet’s path precisely, but requires
Bjørn Slagsvold (65) is
Research Scientist at Telenor
R&D and a member of the Inter-
net Network Architecture group,
presently working on optical
transmission and routing.
bjorn-johan.slagsvold
@telenor.com
Per Thomas Huth (48) is
Research Scientist at Telenor
R&D, Kjeller, He is working in
the Internet Network Architec-
ture group with special interests
in traffic engineering, IP, service
differentiation, network utilisation
and simulations.
Telektronikk 2/3.2001