English
Menu

Distance-Vector vs Link-State Routing: RIP vs OSPF, Convergence

A routing protocol lets routers exchange route information and build their routing tables automatically. Protocols used inside an organization (IGPs) follow one of two main approaches. In a distance-vector protocol, each router hears from its neighbors "how far it is to each destination" and picks routes by adding its distance to that neighbor. RIP, the classic example, uses the number of routers passed through (the hop count) as the distance. In a link-state protocol, each router advertises the state of its own links so that all routers share a map of the network (the topology), and each one computes shortest paths with Dijkstra's algorithm. OSPF, the classic example, picks routes by the sum of costs assigned to each link. Distance-vector protocols are simple and easy to configure, but routes settle (converge) slowly after a failure, so they do not suit large networks. Link-state protocols need more computation and memory, but they react to changes quickly and scale to large networks.

AspectDistance-vector (such as RIP)Link-state (such as OSPF)
What each router knowsOnly the distance and next hop for each destination, as heard from its neighbors; it does not know the layout of the whole networkEvery router and link in its area and their costs; all routers in the area hold the same map (the link-state database)
Route calculationAdds the distance to a neighbor to the distance heard from it and picks the smallest (the Bellman-Ford idea)Computes a shortest-path tree rooted at itself from the map, using Dijkstra's algorithm
Metric (value expressing how good a route is)RIP uses hop count, up to 15; 16 means "unreachable"OSPF uses the sum of per-link costs; the cost can be set by the administrator and is commonly derived from bandwidth
How updates are sentRIP sends the contents of its routing table to neighbors at a fixed interval (30 seconds in RFC 2453), and also sends changes right away (triggered updates)When something changes, link-state information (LSAs) is spread through the whole area (flooding); otherwise Hellos check that neighbors are alive and LSAs are only refreshed at a long interval (30 minutes)
Convergence speed and loopsSlow; after a failure, distances can creep upward step by step (count to infinity); split horizon and similar techniques limit thisFast; once a change has spread, each router recomputes right away, and since all routers compute from the same map, loops are unlikely
Network sizeSuited to small networks; RIP cannot handle destinations 16 or more hops awaySuits large networks too; the network is split into areas arranged around the backbone area (area 0)
Resources and configurationLight on CPU and memory; simple to configureNeeds more CPU and memory to hold the map and compute shortest paths; configuration, such as area design, is more complex
ExamplesRIP (RIPv1, RIPv2, and RIPng for IPv6)OSPF (OSPFv2 for IPv4, OSPFv3 for IPv6), IS-IS

Figures are typical orders of magnitude and vary by process generation and product.

When to use which

Distance-vector (such as RIP)
Small networks with few routers and an almost fixed layout, where ease of configuration comes first. Slow convergence and the hop-count limit make it a poor fit for large or redundant networks.
Link-state (such as OSPF)
Networks with many routers and redundant paths, such as in companies and data centers, where routes should switch quickly after a failure. In large networks, splitting into areas keeps the amount of computation and information down.

FAQ

What is count to infinity?

In a distance-vector protocol, when a destination becomes unreachable, neighboring routers can keep teaching each other stale information, so the distance grows by one at a time and the route takes a long time to disappear. Meanwhile, packets for that destination bounce between the routers. RIP caps this by defining 16 as "unreachable". It also makes the problem less likely with split horizon (not advertising a route back to the neighbor it was learned from), poison reverse (advertising it back to that neighbor with distance 16, unreachable) and triggered updates (sending changes right away).

How is the OSPF cost decided?

RFC 2328 treats the cost of each interface as a value set by the administrator. Many devices use a reference bandwidth divided by the link bandwidth as the default cost. If the reference bandwidth is left at 100 Mbps, every link of 100 Mbps or faster gets a cost of 1 and fast links cannot be told apart, so the reference bandwidth is set to a larger value consistently on all routers.

Which type is BGP?

BGP uses an approach called path vector: it attaches the sequence of ASes a route has passed through (AS_PATH) and passes it to neighbors. Choosing routes from what neighbors report resembles distance vector, but because it carries the path itself rather than a distance, it can prevent loops by discarding routes that contain its own AS number. BGP is used between organizations (between ASes), while OSPF and similar protocols are used inside an organization.

If a router learns a route to the same destination from both RIP and OSPF, which one does it use?

Hop count and cost mean different things, so the metrics cannot be compared directly. For routes to the same destination with the same prefix length, the router installs the one with the lower administrative distance, a per-source preference. The values differ between equipment vendors, but on a device that uses 110 for OSPF and 120 for RIP, the OSPF route is chosen.

Check your understanding

Which statement correctly describes a link-state routing protocol?

  1. AEach router builds its routing table only from the destinations and distances (such as hop counts) it receives from neighboring routers
  2. BEach router floods the state of its own links so that all routers share the topology of the whole network, and each router computes shortest paths with Dijkstra's algorithm
  3. CAn administrator configures routes on each router by hand, and routers exchange no routing information
Show answer and explanation

Answer: B. Each router floods the state of its own links so that all routers share the topology of the whole network, and each router computes shortest paths with Dijkstra's algorithm

In a link-state protocol (such as OSPF or IS-IS), each router advertises the state of its links (its neighbors and the costs to them), and all routers in the same area hold the same map. From this map, each router computes a shortest-path tree rooted at itself with Dijkstra's algorithm. A distance-vector protocol (such as RIP) chooses routes by adding its own distance to the "distance to each destination" heard from its neighbors; this is simple, but routers do not know the topology of the whole network and can take time to settle after a failure. Link-state protocols need more computation and memory but react to changes quickly.

In OSPF, router R1 has three paths to a network beyond R4. Path A uses a 10 Gbps link R1–R5 and a 1 Gbps link R5–R4; path B is a direct 100 Mbps link R1–R4; and path C uses 1 Gbps links R1–R2, R2–R3 and R3–R4. The cost of each link is "reference bandwidth 10 Gbps ÷ link bandwidth", and the cost beyond R4 is the same for all paths. Which path does R1 choose?

  1. APath A
  2. BPath B
  3. CPath C
Show answer and explanation

Answer: A. Path A

The costs are 10 ÷ 10 = 1 for a 10 Gbps link, 10 ÷ 1 = 10 for 1 Gbps and 10 ÷ 0.1 = 100 for 100 Mbps. Path A costs 1 + 10 = 11, path B 100 and path C 10 × 3 = 30, so path A, with the lowest total cost, is chosen. If the reference bandwidth is left at 100 Mbps, long the default on much equipment, every link of 100 Mbps or faster costs 1, giving path A 2, path B 1 and path C 3, and the slowest path, B, is chosen. Networks with fast links therefore set the reference bandwidth to a larger value, the same on every router.

A router has learned routes to the same destination, 192.168.50.0/24, from both OSPF and RIP. On this router, the administrative distance, which expresses the preference for each route source (lower is preferred), is 110 for OSPF and 120 for RIP. Which route goes into the routing table?

  1. ABoth routes are installed and used alternately for each packet
  2. BOnly the RIP route is installed
  3. COnly the OSPF route is installed
Show answer and explanation

Answer: C. Only the OSPF route is installed

Routing protocols express route quality (the metric) in different ways, such as OSPF cost and RIP hop count, so their metrics cannot be compared directly. When routes to the same destination with the same prefix length are learned from several sources, the router therefore installs the one with the lower administrative distance, a measure of how much each source is trusted. Here OSPF's 110 is lower than RIP's 120, so the OSPF route goes into the routing table. Directly connected networks commonly get 0 and static routes 1, giving lower values to what people configure, but the name and default values differ between equipment vendors.

  1. On the internet, which protocol exchanges routing information between the networks run by organizations such as ISPs (ASes, autonomous systems) and chooses routes based on attributes such as the sequence of ASes a route has passed through (AS_PATH) and on each organization's policy?
  2. Which correctly describes dynamic routing?

Practice Network Design and Operations questions

Key terms explained

IP routing
Deciding which path packets take to reach their destination on an IP network. Each router holds a routing table, picks the route that matches the destination IP address with the longest prefix (longest-prefix match) and passes the packet to the next router. The table is built by static routing, configured by hand, or by dynamic routing, built automatically with routing protocols such as OSPF, RIP and BGP.
Router
A network-layer (layer 3) device that forwards packets between different networks. It compares the destination IP address of each packet with its routing table, picks the next router (next hop) and the outgoing interface, and sends the packet on. Home routers also bundle NAPT, a DHCP server and a firewall.
OSPF (Open Shortest Path First)
A link-state routing protocol used inside an organization. Each router floods the state of its own links so that all routers share the network topology, and computes the path with the lowest total cost using Dijkstra's algorithm. Costs are generally derived from link bandwidth, and splitting the network into several areas lets it scale to large networks.
BGP (Border Gateway Protocol)
The routing protocol that exchanges routing information between ASes (autonomous systems, the units of network run by organizations such as ISPs) on the internet. It chooses routes based on attributes attached to them, such as the sequence of ASes they have passed through (AS_PATH), and on each organization's policy. Routers connect to each other over TCP port 179 to exchange information.
Dijkstra's algorithm
An algorithm that finds the shortest paths from one starting vertex to every vertex in a graph whose edge weights are 0 or greater. It repeatedly finalizes the nearest vertex whose distance is not yet final and updates the distances of its neighbors. It does not work correctly with negative edge weights.
Administrative distance
A preference value for each route source, used to decide which route to install in the routing table when routes to the same destination with the same prefix length are learned from several sources, such as static routes, OSPF and RIP. Lower values are preferred. It is not used to choose between routes with different prefix lengths; that is decided by longest prefix match. The name and default values differ between equipment vendors.

Related comparisons