Some Background on Router Protocols


Routing Protocols.  A protocol is a formalized system for exchanging a specific type of information in a certain way.  A routing protocol formalizes the continually ongoing exchange of route information between routers.  Messages called routing updates pass information used by routers to determine and calculate paths to destinations.  Determining and calculating these paths is done by routing algorithms which are composed of a system of rules that control a network's behavior so that routers can adapt to changing circumstances in the network's topology.  Two examples of these ongoing changes can be the implementation of some new equipment on the network or temporarily out of service routers on the network.  A routing table is a list of routes available to forward traffic to various destinations.  Each router typically maintains a single routing table, not one for each interface.

Routing protocols are set up to interact in a peer to peer arrangement where each router plays a relatively equal role.  They are definitely not coordinated by some unique central administration across the internet.  The routing algorithms tend to share the following two basic approaches.

  • Routers send one another update messages advising of changes in internetwork topology and conditions.
  • Each router recalculates its own routing table based on the updated information.

Topology Changes.  How do routers sense topology changes?  There are a fairly constant stream of messages sent at different time intervals so that routers can inform their neighbors about their status.  The following bulleted list represents how routers "sense" down links.

  • Each router broadcasts hello messages to its immediate neighbor routers at a fixed interval.
    • A typical interval is once every 90 seconds
  • If no ACK - acknowledgement message is received back within a specified period the route is declared invalid.
    • A typical interval is 3 minutes
  • If no ACK has returned within a longer period, the router and its routes are removed from the sending router's table and a routing update is issued about all routes that incorporated the nonresponding router as a link.

But sensing a topology change is only the first step.  As soon as a change is sensed, routing updates must be passed until all routers can converge on a new topology by incorporating the change.  Sometimes these updates can cause misinformation to be propagated through the network.  Due to propagation delays, not all routers receive updates at the same moments.  The impact of these propagation delays on convergence after topology changes increases as the size of the internetworks increase.

These propagation delays would not likely cause any problems to routing protocols if routers always converged before any new changes occurred.  Unfortunately, this is not always the case.  A routing loop occurs when payload packets can't reach their destinations because of conflicting routing table information.  This happens in large internetworks when subsequent topology changes occur before routers have converged due to previous topology changes.

Routing protocols incorporate a number of sophisticated mechanisms to thwart the onset of routing loops.

  • Hold Downs - Suppression of advertisements about a route that's in question long enough for all appropriate routers to find out about its true status.
  • Split Horizons - The practice of not advertising a route back in the direction of the route itself.
  • Poison Reverse Updates - A routing update message that explicitly states a network or subnet is unreachable (instead of a nearby router merely dropping it from its routing table for lack of use).
  • Triggered Updates - Updates are sent based on particular trigger events.  Thus some information is sent on immediately.  There are no delays in relaying certain types of  information which can cause looping.

Routing Protocols.  A routing metric is a value used by a routing protocol to influence routing decisions.  The mostly widely used metrics follow along with some discussion.

  • Cost - this is not likely to be a financial cost, but a theoretical number used to represent time, difficulty, risk, and other factors involved in a route.
  • Distance - not physical distance in miles or cable feet, but a theoretical distance number.  This is usually associated with the number of router hops in a route.
  • Bandwidth - The bandwidth rating of a network.
  • Traffic Load - A number representing the amount of traffic, such as the number and size of packets, that travel over a link during a specified period of time.
  • Delay - The time between the start of a routing update cycle and when all routers in an internetwork converge on a single topology view.
  • Reliability - A relative number used to indicate the reliability of a link.
  • MTU - The maximum packet size that a particular network interface can handle.

Implementing these there are three basic types of routing protocols along with some of their best known implementations.

  • Distance Vector Routing Protocols - simple algorithms that calculate a cumulative distance value between routers based on some distance metric.
    • Internet Protocol (IP) Routing Information Protocol (RIP)
    • Internet Packet Exchange (IPX) RIP
    • Interior Gateway Routing Protocol (IGRP)
    • Appletalk Routing Table Maintainance Protocol (RTMP)
  • Link State Routing Protocols - Sophisticated algorithms that maintain a complex database of internetwork topology.  These depend on the state of a link between routers.
    • Open Shortest Path First (OSPF)
    • Intermediate System to Intermediate System (IS-IS)
    • NetWare Link Services Protocol (NLSP)
  • Hybrid Routing Protocols - A combination of distance vector and link state methods that tries to incorporate the advantages of both and minimize their disadvantages.
    • Enhanced Interior Gateway Routing Protocol (EIGRP)

Finally, it is always important to distinguish whether a router is inside, outside or on an interactive boundary or at the gateway of a network.