Lesson 7: Understanding Routing

What Is Routing? | Network Addressing | Routing Protocols

Routing Tables

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 Metrics

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.

<<Back [1] [2] [3] [4] [5] [6] Next>>