|
An algorithm is a detailed solution to a
problem. In the case of routing packets, different routing protocols
use different algorithms to decide which port an incoming packet
should be sent to. Routing algorithms depend on metrics to make these
decisions.
Routing protocols often have one or
more of the following design goals:
- Optimization – Optimization describes
the capability of the routing algorithm to select the best route.
The route will depend on the metrics and metric weightings used in
the calculation. For example, one algorithm may use both hop count
and delay metrics, but may consider delay metrics as more important
in the calculation.
- Simplicity and low overhead – The
simpler the algorithm, the more efficiently it will be processed by
the CPU and memory in the router. This is important so that the
network can scale to large proportions, such as the Internet.
- Robustness and stability – A routing
algorithm should perform correctly when confronted by unusual or
unforeseen circumstances, such as hardware failures, high load
conditions, and implementation errors.
- Flexibility – A routing algorithm
should quickly adapt to a variety of network changes. These changes
include router availability, router memory, changes in bandwidth,
and network delay.
- Rapid convergence – Convergence is
the process of agreement by all routers on available routes. When a
network event causes changes in router availability, updates are
needed to reestablish network connectivity. Routing algorithms that
converge slowly can cause data to be undeliverable.
Routing algorithms use different
metrics to determine the best route.
 Each
routing algorithm interprets what is best in its own way. The routing
algorithm generates a number, called the metric value, for each path
through the network. Sophisticated routing algorithms base route
selection on multiple metrics, combining them in a single composite
metric value. Typically, smaller metric values indicate preferred
paths.
Metrics can be based on a single
characteristic of a path, or can be calculated based on several
characteristics. The following are the metrics that are most commonly
used by routing protocols:
- Bandwidth – The data capacity of a
link. Normally, a 10-Mbps Ethernet link is preferable to a 64-kbps
leased line.
- Delay – The length of time required
to move a packet along each link from source to destination. Delay
depends on the bandwidth of intermediate links, the amount of data
that can be temporarily stored at each router, network congestion,
and physical distance.
- Load – The amount of activity on a
network resource such as a router or a link.
- Reliability – Usually a reference to
the error rate of each network link.
- Hop count – The number of routers
that a packet must travel through before reaching its destination.
Each router the data must pass through is equal to one hop. A path
that has a hop count of four indicates that data traveling along
that path would have to pass through four routers before reaching
its final destination. If multiple paths are available to a
destination, the path with the least number of hops is preferred.
- Ticks – The delay on a data link
using IBM PC clock ticks. One tick is approximately 1/18 second.
- Cost – An arbitrary value, usually
based on bandwidth, monetary expense, or other measurement, that is
assigned by a network administrator.
|
Web Links