To aid the process of path determination,
routing algorithms initialize and maintain routing tables,
which contain route information. Route information varies
depending on the routing algorithm used. Routing algorithms
fill routing tables with a variety of information. Two examples
destination/next hop associations and path desirability.
- Destination/next hop associations tell a router that
a particular destination is linked to a particular router
representing the “next hop” on the way to the
final destination. When a router receives an incoming
packet, it checks the destination address and attempts to
associate this address with a next hop.
- With path desirability, routers compare metrics to
determine optimal routes. Metrics differ depending
on the routing algorithm used. A metric is a standard of measurement,
such as path length, that is used by routing
algorithms to determine the optimal path to a destination.
Routers communicate with one another and maintain their routing
tables through the transmission of a variety of messages.
- Routing update messages may include all or a portion
of a routing table. By analyzing routing updates
from all other routers, a router can build a detailed picture
of network topology.
- Link-state advertisements inform other routers of
the state of the sender’s link so that routers can
maintain a picture of the network topology and continuously
determine optimal routes to network destinations.
Routing Algorithm Goals
Routing tables contain information used by
software to select the best route. But how, specifically,
are routing tables built? What is the specific nature of the
information they contain? How do routing algorithms determine
that one route is preferable to others?
Routing algorithms often have one or more of the following
Optimality - the
capability of the routing algorithm to select the best route,
depending on metrics and metric weightings
used in the calculation. For example, one algorithm may use
a number of hops and delays, but may weight
delay more heavily in the calculation.
Simplicity and low overhead -
efficient routing algorithm functionality with a minimum of
software and utilization overhead. Particularly
important when routing algorithm software must run on a computer
with limited physical resources.
Robustness and stability
- routing algorithm should perform correctly in the
face of unusual or unforeseen circumstances,
such as hardware failures, high load conditions, and incorrect
implementations. Because of their locations
at network junctions, failures can cause extensive problems.
Rapid convergence -
Convergence is the process of agreement, by all routers, on
optimal routes. When a network event causes
changes in router availability, recalculations are need to
restablish networks. Routing algorithms
that converge slowly can cause routing loops or network outages.
routing algorithm should quickly and accurately adapt to a
variety of network circumstances. Changes
of consequence include router availability, changes in network
bandwidth, queue size, and network delay.
Routing algorithms have used many different
metrics to determine the best route. Sophisticated routing
algorithms can base route selection on multiple metrics, combining
them in a single (hybrid) metric. All the following metrics
have been used:
Path length -
The most common metric. The sum of either an assigned cost
per network link or hop count, a metric
specify the number of passes through network devices between
source and destination.
dependability (bit-error rate) of each network link. Some
network links might go down more often than
others. Also, some links may be easier or faster to repair
after a failure.
Delay - The length
of time required to move a packet from source to destination
through the internetwork. Depends on bandwidth
of intermediate links, port queues at each router, network
congestion, and physical distance. A common
and useful metric.
Bandwidth - available
traffic capacity of a link.
Load - Degree
to which a network resource, such as a router, is busy (uses
CPU utilization or packets processed per
Communication cost -
operating expenses of network links (private versus public
Now let’s talk a little about network