there), or selective flooding (sending on
outgoing links going approximately in the
requested direction).
- Flow-based routing; taking both traffic load
and topology into account when deciding the
routing. In case the routing is static, mean traf-
fic load values could be used (e.g. found from
measurements).
- Distance vector routing; each router maintains
a table (vector) describing the better “dis-
tance” to each destination (or rather set of des-
tinations) and the corresponding outgoing
link. As these tables are updated by informa-
tion exchanged between routers, it can dynam-
ically adapt to the current situation in a net-
work. The “distance” measure can be number
of hops, delay, queuing length, and so forth.
A well-known problem is the count-to-infinity
problem when a node goes down as this infor-
mation may propagate slowly.
- Link state routing; the topology and all delays
are estimated and distributed to every router in
the network. Then, a shortest path algorithm
can be used to find which path to use to reach
each (set of) router. Four steps can be recog-
nised: i) discover neighbour routers and their
addresses (e.g. by Hello packets); ii) measure
delay (or cost) to each of the neighbours (e.g.
by Echo packets); iii) distribute a packet to all
other routers containing the measure; and iv)
compute the shortest path to every (set of)
router.
- Hierarchical routing; routers may be divided
into a number of regions. All routers know
every other router within its region although
without knowing details of other regions.
Information on which router to use in case a
packet is to leave the region has to be known,
though. Several levels may be used in the
hierarchy depending on the number of routers,
as well as other factors, like domains, opera-
tors, etc.
- Broadcast/multicast routing; sending packets
to multiple receivers is commonly seen for
some services, like news and conferences.
One simple way of broadcasting is simply to
distribute an incoming packet on all outgoing
links (flooding), although this would likely
waste transmission capacity. Then, reverse
path forwarding has been proposed where a
router forwards a packet from a sender in case
the packet arrives on a link that is used for
sending packets to the sender (in the opposite
direction). Spanning trees can also be con-
structed when packets are to arrive at a set of
destinations. However, maintaining such trees
may become cumbersome for larger networks.
Therefore a core-based tree algorithm has
been suggested where a smaller core does the
multicasting within the core and then other
multicast techniques can be applied between
the core and the final destination. This may be
seen to have some resemblance with hierarchi-
cal routing.
Link state routing is commonly applied within a
domain, e.g. Open Shortest Path First, OSPF and
Intermediate System – Intermediate System, IS-
IS. Commonly topology information is used
(only able to tell whether links are up or down).
More dynamics can be reached by introducing
other measures. To include a measure based on
delay may only cause oscillations to occur as
traffic tends to be sent towards paths with short
delays. These paths may then become over-
loaded and long delays result of which other
links will be announced as lighter loaded and
then the traffic may be sent towards these, and
so on.
Therefore, other measures and constraints are
also considered, ref. [Feng01]. When several
links are included in a path, the measures of the
links have to be aggregated. Aggregating metrics
depends on the parameter as described in Box C.
Finding an optimal path subject to two or more
additive, multiplicative or root-mean-square is
NP-complete (cannot be solved in polynomial
time). Hence, heuristic algorithms are used with
such measures.
In addition to specifying the next router, looser
routing can be applied. Then a set of routers is
listed, allowing for flexibility to decide which
one to use. Further, this allows a sender to have
imperfect information on the details. The set of
routers may also be referred to as an abstract
router. This is support source specific routing
when the complete path is, more or less, strictly
specified by the sender.
Box C Aggregating Measures
When aggregating measures a number of different approaches may be feasible,
depending on the parameter in question. Assuming independence between the
different parts, three ways are:
- additive basis, i.e. Ptot= P 1 + P 2 + ... Pn
- probabilistic basis, i.e. Ptot= 1 – [(1 – P 1 ) (1 – P 2 ) ... *(1 – Pn)]
- root-mean-square basis, i.e. Ptot= sqrt[P 12 + P 22 + ... Pn^2 ]
- concave basis, i.e. Ptot= min[P 1 , P 2 , ..., Pn]
Delay and hop count are examples of an additive parameter, while packet loss
is an example of probabilistic, and delay variation is an example of root-mean-
square basis. Bandwidth may be an example of a concave basis.
