Network Layer Protocols

In the previous page, we learned that IP forwards packets by consulting a routing table—examining the destination address and determining the next hop. But this raises a critical question: how does the routing table get populated?

For small, static networks, an administrator might manually configure routes. But the global Internet comprises over 70,000 autonomous systems with millions of routers. Manual configuration at this scale is impossible—routes change constantly as links fail, new networks appear, and traffic patterns shift. The answer lies in routing protocols: specialized protocols that automatically discover network topology and compute optimal paths.

Routing protocols are algorithms that enable routers to share information about network topology and compute paths to destinations. They operate in the control plane—the part of networking that determines how packets should be forwarded—as opposed to the data plane where actual forwarding occurs.

To understand routing protocols, we must first distinguish them from routed protocols:

• Routed protocols (like IP): Carry user data across the network
• Routing protocols (like OSPF, BGP): Determine the paths that routed protocols will use

Routing protocols don't carry user traffic—they carry routing information: which networks exist, how to reach them, and what the costs are. This information is exchanged between routers, which then independently compute their routing tables.

Why Dynamic Routing?

Manual (static) routing works for simple, stable networks—but fails in complex environments:

1. Scale: With millions of routes, manual management is impossible
2. Dynamism: Network topology changes frequently (failures, additions)
3. Convergence: After changes, all routers must agree on new paths
4. Load distribution: Traffic may need to be balanced across multiple paths
5. Optimization: Routes should use the best (fastest, cheapest) paths

Routing protocols solve these challenges by:

• Automatically discovering neighboring routers
• Learning about remote networks through information exchange
• Computing optimal paths using algorithms
• Adapting to topology changes without human intervention
• Converging to consistent routing decisions across all routers

The Internet is organized into Autonomous Systems (AS)—networks under a single administrative authority. Your ISP is an AS. Google is an AS. A university might be an AS. Each AS has its own internal structure and policies.

This organization creates a fundamental distinction in routing:

Why This Distinction Matters:

Within an AS, all routers are under common administration. They can trust each other, share detailed topology information, and optimize purely for performance. The goal is finding the fastest path.

Between ASes, the relationship is different. ASes may be competitors or have business agreements that affect routing. An AS might refuse to carry traffic for certain other ASes, or prefer expensive paths for business reasons. The goal isn't just speed—it's enforcing routing policy.

Example Scenario:

Consider an AS that is a customer of two ISPs. For incoming traffic, it might prefer ISP-A (cheaper). For outgoing traffic to certain destinations, it might prefer ISP-B (faster). These policies can't be expressed with simple metrics—they require explicit policy control.

This is why BGP, the inter-AS protocol, is fundamentally different: it's a path-vector protocol with rich policy capabilities, whereas IGPs are typically link-state or distance-vector focused on efficiency.

Distance Vector routing is one of the oldest approaches to dynamic routing, based on the Bellman-Ford algorithm. The core idea is simple: each router maintains a vector (list) of distances to all known destinations, and periodically shares this vector with its neighbors.

How Distance Vector Works:

1. Each router knows the cost to reach its directly connected networks
2. Periodically, each router sends its entire routing table to all neighbors
3. When a router receives a neighbor's table, it considers: "If I go through this neighbor, what would be my total cost to each destination?"
4. If this new cost is lower than the current known cost, update the routing table
5. Repeat until no more updates occur (convergence)

RIP: Routing Information Protocol

RIP is the classic distance vector protocol, still used in small networks:

• Metric: Hop count (number of routers traversed)
• Maximum: 15 hops (16 = unreachable)
• Updates: Every 30 seconds (full routing table)
• Versions: RIPv1 (classful), RIPv2 (classless, supports VLSM)
• Simplicity: Easy to configure and understand

Distance Vector Limitations:

While elegant, distance vector protocols have significant issues:

Mitigations:

Several techniques reduce these problems:

• Split Horizon: Don't advertise a route back to the neighbor you learned it from
• Poison Reverse: Explicitly advertise failed routes with infinite cost
• Triggered Updates: Send updates immediately when topology changes, don't wait for timer
• Hold-Down Timers: After hearing a route failed, ignore new routes to that destination for a period

Despite these improvements, distance vector protocols are largely replaced by link-state protocols for medium to large networks. However, RIP remains in use for small networks due to its simplicity.

Link State routing takes a fundamentally different approach from distance vector. Instead of sharing distances to destinations, routers share information about their directly connected links. Every router then independently builds a complete map of the network and computes shortest paths using Dijkstra's algorithm.

How Link State Works:

1. Neighbor Discovery: Routers discover neighbors using Hello packets
2. Link State Advertisements (LSAs): Each router creates an LSA describing its links and their costs
3. Flooding: LSAs are flooded throughout the network—every router receives every LSA
4. Database Synchronization: All routers build an identical Link State Database (LSDB) containing all LSAs
5. SPF Calculation: Each router runs Dijkstra's Shortest Path First algorithm on the LSDB
6. Routing Table: SPF produces a shortest-path tree; routing table entries are derived from this tree

OSPF: Open Shortest Path First

OSPF is the dominant link state IGP, standardized by IETF (RFC 2328 for OSPFv2):

• Metric: Cost (typically inversely proportional to bandwidth)
• Areas: Large networks divided into areas for scalability
• Area 0: Backbone area; all other areas must connect to it
• LSA Types: Different LSA types for different purposes (router, network, summary, etc.)
• Designated Router: Multi-access networks elect a DR to reduce adjacency count
• Fast Convergence: Sub-second failure detection with BFD integration
• Authentication: Supports MD5 and cryptographic authentication

Why Link State is Superior for Large Networks:

1. Faster Convergence: Changes flood immediately; all routers compute simultaneously
2. Loop-Free by Design: Complete topology means consistent, loop-free paths
3. Better Metrics: Cost can reflect bandwidth, not just hop count
4. Efficient Updates: Only changed LSAs are flooded, not entire tables
5. Hierarchical Design: Areas reduce LSDB size and computation in large networks

Path Vector routing is used exclusively for inter-domain (inter-AS) routing. The sole path vector protocol in use today is BGP (Border Gateway Protocol)—the protocol that literally holds the Internet together.

BGP's Unique Requirements:

Unlike IGPs, BGP must:

1. Scale to the entire Internet: ~1 million routes, ~70,000+ ASes
2. Support Routing Policy: Business relationships determine acceptable paths
3. Provide Loop Detection: Paths can traverse many ASes—loops must be prevented
4. Enable Autonomous Operation: Each AS makes independent decisions
5. Work Between Competitors: Trust is limited; internal topology is hidden

How Path Vector Works:

Path vector is similar to distance vector, but instead of advertising just distances, routers advertise the complete path (sequence of ASes) to each destination:

Loop Detection:

The AS_PATH attribute provides elegant loop detection: if a router sees its own AS number in the path, the route is rejected. This is simpler and more reliable than distance vector's hop-counting approaches.

Policy Implementation:

BGP's true power lies in its policy capabilities. AS_PATH, LOCAL_PREF, MED, and communities allow sophisticated routing decisions:

• LOCAL_PREF: Prefer one exit point over another (internal decision)
• MED (Multi-Exit Discriminator): Suggest preferred entry point to neighbors
• AS_PATH Prepending: Artificially lengthen path to make it less preferred
• Communities: Tag routes for special handling (e.g., "don't export to competitors")

In practice, network architects must choose appropriate routing protocols based on network requirements. No single protocol is best for all scenarios.

Decision Factors:

Common Deployment Patterns:

1. Small Office: Static routes or RIPv2—minimal complexity, easy troubleshooting

2. Enterprise Campus: OSPF—scalable, fast convergence, widespread support, hierarchical design with areas

3. Data Center: eBGP between pods/fabrics or OSPF within—scale and policy requirements vary

4. Service Provider Core: IS-IS or OSPF for internal routing + iBGP for route distribution + eBGP for peering

5. Multi-Site Enterprise: eBGP with private ASNs or OSPF + BGP redistribution

Route Redistribution:

Large networks often use multiple routing protocols. For example, a campus might run OSPF internally but connect to the Internet via BGP. Route redistribution allows routes learned from one protocol to be shared with another—but this must be done carefully to avoid routing loops and suboptimal paths.

Filtering is essential: Never blindly redistribute all routes. Use prefix lists and route maps to control what is shared.

Routing protocols are the intelligence that makes dynamic, adaptive networking possible. Without them, the Internet would require impossible amounts of manual configuration and couldn't recover from failures.