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 are
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 design goals:
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.
Flexibility – 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.
Reliability – 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 second).
Communication cost – operating expenses of network links (private versus public lines).
Now let’s talk a little about network addressing.