Dynamic Routing and OSPF

Why dynamic routing

Static routes (see Routing Basics) work well for a handful of networks. They stop working well when a network grows: with 50 routers, every new subnet means a change on dozens of devices, and every typo is an outage. Worse, a static route does not notice when a path fails, so traffic keeps being sent into a broken link until someone changes it.

A routing protocol solves both problems. Routers running the same protocol discover each other, exchange information about the networks they can reach, and put the best routes in their routing tables automatically. When a link fails, they tell each other and switch to another path — usually before anyone opens a ticket. This is dynamic routing. The price is some bandwidth and central processing unit (CPU) time for the protocol, and a protocol that you must understand to troubleshoot.

Interior and exterior gateway protocols

Routing protocols are split by where they are used. An autonomous system (AS) is a network under one administration, such as a company, a university or an Internet provider.

• An interior gateway protocol (IGP) routes inside one autonomous system. Examples: Open Shortest Path First (OSPF), Enhanced Interior Gateway Routing Protocol (EIGRP), Intermediate System to Intermediate System (IS-IS) and Routing Information Protocol (RIP). Goal: find the fastest path, and converge quickly.
• An exterior gateway protocol (EGP) routes between autonomous systems. Today there is only one in use: Border Gateway Protocol (BGP). Goal: follow each organization's policy about which traffic it carries, at the scale of the whole Internet.

Distance vector and link state

Interior protocols come in two families that differ in what routers tell each other.

Distance vector

In a distance vector protocol, each router sends its neighbors its list of known networks with a distance (how far) and a direction (via me). A router adds its own cost, keeps the best route per network, and passes that on. No router sees the whole network; each only trusts what its neighbors tell it, which is why this is nicknamed routing by rumor.

RIP is the classic example. Its metric is the hop count, the number of routers on the way, regardless of link speed. A route of 16 hops counts as unreachable, so RIP networks cannot be more than 15 hops wide. RIP version 2 sends its whole table every 30 seconds, and because bad news travels one neighbor at a time, it can take minutes to converge; mechanisms such as split horizon and hold-down timers exist to prevent routing loops in the meantime. RIP is rare in production today but still appears in exam questions and old networks. Cisco's EIGRP is an advanced distance vector protocol: it sends only changes, keeps backup routes ready, and uses a metric based on bandwidth and delay.

Link state

In a link state protocol, every router describes its own links — which neighbors and networks it has and what each link costs — in a link state advertisement (LSA). These advertisements are flooded unchanged to every router in the area, so all routers build the same link state database: a complete map. Each router then runs the shortest path first (SPF) algorithm, invented by Edsger Dijkstra, with itself as the root, and puts the results in its routing table.

Because every router has the full map, a change is flooded immediately and everyone recalculates: link state protocols converge fast and do not rely on rumors. They cost more memory and CPU, which is one reason networks are divided into areas. OSPF and IS-IS are link state protocols.

Shortest path first in Python

You never run SPF yourself, but seeing it once makes OSPF's behavior less mysterious. This sketch of Dijkstra's algorithm computes R1's best path to every router in the diagram. It keeps a queue of candidate paths, always extends the cheapest one first, and remembers the best total per router:

import heapq

# Link costs between four routers (the same in both directions)
links = {
    ("R1", "R2"): 1,
    ("R1", "R3"): 10,
    ("R2", "R3"): 1,
    ("R2", "R4"): 10,
    ("R3", "R4"): 1,
}
graph = {}
for (a, b), cost in links.items():
    graph.setdefault(a, []).append((b, cost))
    graph.setdefault(b, []).append((a, cost))


def shortest_paths(source):
    best = {source: (0, [source])}
    queue = [(0, source, [source])]
    while queue:
        total, router, path = heapq.heappop(queue)
        if total > best[router][0]:
            continue  # an older, longer entry for this router
        for neighbor, cost in graph[router]:
            new_total = total + cost
            if neighbor not in best or new_total < best[neighbor][0]:
                best[neighbor] = (new_total, path + [neighbor])
                heapq.heappush(queue, (new_total, neighbor, path + [neighbor]))
    return best


for router, (total, path) in sorted(shortest_paths("R1").items()):
    print(f"{router}: cost {total:>2}  path {' -> '.join(path)}")

R1: cost  0  path R1
R2: cost  1  path R1 -> R2
R3: cost  2  path R1 -> R2 -> R3
R4: cost  3  path R1 -> R2 -> R3 -> R4

A hop-count protocol such as RIP would see R1 → R3 → R4 and R1 → R2 → R4 as equally good (two hops each) and never choose the three-hop path, even though each of those routes includes a link that is ten times more expensive. A cost-based protocol prefers three fast links. For the Python used here, see Dictionaries and Sets.

Path vector: BGP and Internet routing

BGP (Border Gateway Protocol) is the routing protocol of the Internet: it exchanges reachability information between autonomous systems. Every provider, and most organizations that connect to more than one provider, have a public autonomous system number (ASN) and runs BGP at its edge. The numbers 64496–64511 are reserved for documentation, so an example could show AS 64500 announcing 198.51.100.0/24 to its providers.

BGP is a path vector protocol. Each route carries the list of autonomous systems it has passed through, the AS path. A router that sees its own AS number in the path rejects the route, which prevents loops between organizations. Path selection is not about speed but about policy: administrators use attributes such as local preference to choose which provider carries which traffic. BGP runs over Transmission Control Protocol (TCP) port 179, between neighbors that are configured by hand. Between autonomous systems it is called external BGP (eBGP); between routers inside one AS, internal BGP (iBGP).

For a starter in network operations (NetOps), BGP mostly shows up as "the provider's BGP session went down" or "a prefix is not being announced". The details are beyond CCNA level; knowing what BGP is for, that it is an EGP, and its administrative distances is enough to start with.

Administrative distance and metric

A router may run more than one routing protocol, and have static routes too. Two numbers decide which route ends up in the routing table, and they answer different questions.

Administrative distance

Administrative distance (AD) is how much a router trusts the source of a route: when two sources offer the same prefix, the route with the lowest administrative distance is installed. The values are Cisco defaults and can be changed per route or per protocol.

In show ip route the administrative distance is the first number in brackets: [110/2] is an OSPF route with metric 2. A floating static route (see Routing Basics) uses exactly this mechanism, with a distance set higher than the protocol it backs up.

Metric

A metric is the value a routing protocol uses to compare paths to the same destination that it learned itself; the lowest metric wins. Each protocol measures differently, which is why metrics cannot be compared across protocols and administrative distance is needed at all:

• RIP: hop count.
• OSPF: cost, the sum of the interface costs along the path.
• EIGRP: a composite metric, by default from bandwidth and delay.
• BGP: no single metric, but a list of path attributes.

If a protocol finds several paths with the same lowest metric, it can install all of them and share traffic across them: equal-cost multi-path (ECMP) load balancing. OSPF does this by default for up to four paths on most Cisco routers.

OSPF basics

OSPF (Open Shortest Path First) is an open-standard link state IGP, supported by every router vendor. OSPF version 2 (Request for Comments (RFC) 2328) carries Internet Protocol (IP) version 4, IPv4; OSPFv3 carries IPv6. It is the most common interior routing protocol in enterprise networks and the one the CCNA focuses on. OSPF runs directly on top of IP (protocol number 89) and sends most of its packets to the multicast address 224.0.0.5, which every OSPF router listens to.

Router ID

Every OSPF router is identified by a router ID: a 32-bit number written like an IPv4 address, such as 1.1.1.1. It must be unique in the OSPF domain. A router picks it in this order:

1. the value set with the router-id command;
2. otherwise, the highest IPv4 address on a loopback interface that is up;
3. otherwise, the highest IPv4 address on any other interface that is up.

Setting it by hand is best practice: an ID that depends on interface addresses can change after a reboot and make troubleshooting confusing. A new router ID takes effect after the OSPF process restarts (clear ip ospf process).

Neighbors and adjacencies

OSPF routers find each other with hello packets, sent on every OSPF interface. On Ethernet the hello timer is 10 seconds and the dead timer 40 seconds: if no hello arrives from a neighbor for 40 seconds, the neighbor is declared down and its routes are recalculated. Two routers become neighbors only when these parameters match in their hellos:

• the same area ID;
• the same subnet and subnet mask on the shared link;
• the same hello and dead timers;
• matching authentication, if configured;
• and different router IDs.

After that, the routers exchange their databases and become fully adjacent. The neighbor goes through the states Down, Init, 2-Way, ExStart, Exchange, Loading and finally Full. A neighbor stuck in ExStart or Exchange often points to a maximum transmission unit (MTU) mismatch between the two interfaces.

Areas and area 0

An OSPF area is a group of routers and links that share one link state database. Flooding and SPF calculations stay inside an area; between areas only summary information is exchanged. This keeps databases small and contains the effect of a flapping link. Every OSPF network has a backbone, area 0, and every other area must connect to it. A router with interfaces in area 0 and another area is an area border router (ABR).

The CCNA covers single-area OSPF: all routers and links in area 0. That is also a sensible design for a small or medium network.

Cost and reference bandwidth

OSPF's metric is cost. Each interface has a cost, and the cost of a route is the sum of the outgoing interface costs along the path. By default, Cisco calculates the interface cost from its bandwidth:

cost = reference bandwidth ÷ interface bandwidth, rounded down, with a minimum of 1.

The default reference bandwidth is 100 Mbps, chosen when 100 Mbps was fast. The result is a problem you can see right away:

def ospf_cost(reference_mbps, interface_mbps):
    # OSPF drops the fraction and never goes below 1
    return max(1, int(reference_mbps / interface_mbps))


links = [("T1 serial", 1.544), ("Ethernet", 10), ("FastEthernet", 100),
         ("GigabitEthernet", 1_000), ("10 Gigabit", 10_000), ("100 Gigabit", 100_000)]

print(f"{'Interface':<16} {'Mbps':>7}  ref 100  ref 100000")
for name, mbps in links:
    print(f"{name:<16} {mbps:>7}  {ospf_cost(100, mbps):>7}  {ospf_cost(100_000, mbps):>10}")

Interface           Mbps  ref 100  ref 100000
T1 serial          1.544       64       64766
Ethernet              10       10       10000
FastEthernet         100        1        1000
GigabitEthernet     1000        1         100
10 Gigabit         10000        1          10
100 Gigabit       100000        1           1

With the default reference, every link of 100 Mbps or faster gets cost 1: OSPF cannot tell a 100 Mbps link from a 100 Gbps link and may prefer a slow path with fewer hops. The fix is to raise the reference bandwidth, in Mbps, with auto-cost reference-bandwidth 100000 under router ospf. Do it on every router in the domain; otherwise routers calculate costs on different scales and paths become inconsistent. You can also set a cost directly on an interface with ip ospf cost.

DR and BDR

On a multi-access segment such as Ethernet, full adjacencies between every pair of routers would multiply the flooding. OSPF therefore elects a designated router (DR) and a backup designated router (BDR). All other routers (DROTHERs) become fully adjacent with only the DR and BDR, and stay in the 2-Way state with each other. The highest interface priority wins the election (default 1; priority 0 means never), then the highest router ID. The election is not pre-emptive: a better router that joins later does not take over until the DR fails. On a link with only two routers, ip ospf network point-to-point skips the election altogether.

Configuring single-area OSPF

Using the two-router network from Routing Basics: R1 has its local area network (LAN) 192.168.1.0/24 on GigabitEthernet0/0 and the link to R2, 10.0.12.0/30, on GigabitEthernet0/1. R1 keeps its static default route toward 203.0.113.1, but the static route to 192.168.2.0/24 is removed: with administrative distance 1 it would beat the OSPF route (110) to the same prefix, and OSPF should carry R2's networks now.

R1(config)# router ospf 1
R1(config-router)# router-id 1.1.1.1
R1(config-router)# network 10.0.12.0 0.0.0.3 area 0
R1(config-router)# network 192.168.1.0 0.0.0.255 area 0
R1(config-router)# passive-interface GigabitEthernet0/0

• router ospf 1 starts OSPF process 1. The process ID is local to the router; it does not have to match on neighbors.
• router-id 1.1.1.1 sets the router ID by hand.
• network 10.0.12.0 0.0.0.3 area 0 enables OSPF on every interface whose address falls in this range, and places it in area 0. The second value is a wildcard mask, the inverse of the subnet mask: 0 bits must match, 1 bits are ignored. For a /30 that is 0.0.0.3, for a /24 0.0.0.255. The connected network of each matching interface is then advertised.
• passive-interface GigabitEthernet0/0 stops OSPF from sending hellos on the LAN, where no routers are expected. The network is still advertised. This saves resources and stops anyone on the LAN from forming an OSPF neighborship with your router.

Instead of network statements, you can enable OSPF per interface, which many engineers find clearer because the configuration sits where it applies:

R1(config)# interface GigabitEthernet0/1
R1(config-if)# ip ospf 1 area 0

Verifying OSPF

Two commands answer the first two questions in any OSPF ticket: do I have neighbors, and did I learn routes?

R1# show ip ospf neighbor

Neighbor ID     Pri   State           Dead Time   Address         Interface
2.2.2.2           1   FULL/DR         00:00:36    10.0.12.2       GigabitEthernet0/1

R1# show ip route ospf
Codes: L - local, C - connected, S - static, R - RIP, M - mobile, B - BGP
       … (remaining code lines trimmed)

Gateway of last resort is 203.0.113.1 to network 0.0.0.0

      172.16.0.0/24 is subnetted, 1 subnets
O        172.16.30.0 [110/2] via 10.0.12.2, 00:05:12, GigabitEthernet0/1
O     192.168.2.0/24 [110/2] via 10.0.12.2, 00:05:12, GigabitEthernet0/1

• Neighbor ID is R2's router ID; Pri its priority on this link.
• FULL/DR: the adjacency is complete, and R2 is the designated router on this Ethernet link (both have priority 1; R2 won with the higher router ID because both came up at the same time). FULL/ - would appear on a point-to-point link, which has no DR.
• Dead Time counts down from 40 and resets with each hello; if it reaches zero, the neighbor is lost.
• Both routes to R2's networks have distance 110 and cost 2: cost 1 for R1's GigabitEthernet0/1 plus cost 1 for R2's interface on that network (GigabitEthernet0/0 for 192.168.2.0/24, GigabitEthernet0/2 for 172.16.30.0/24).

Convergence

Convergence is the state in which all routers have the same, correct view of the network after a change; convergence time is how long it takes to get there. Until the network has converged, packets can be dropped or loop between routers.

Convergence has two parts: noticing the change and recalculating. If a link physically goes down, the router notices immediately; if a neighbor silently stops responding, OSPF waits for the dead timer (40 seconds by default). After that, OSPF floods the change and every router reruns SPF within seconds. RIP, which spreads news one neighbor per update interval and uses hold-down timers, can take minutes. Fast convergence is one of the main reasons link state protocols replaced RIP in most networks.