IP Routing Mechanics & Exterior Gateway (BGP)

The global Internet is fundamentally an interconnected federation of independently administered autonomous networks bound together by standard routing protocols and forwarding hardware. At the core of this planetary distributed system are two distinct yet deeply coupled operational paradigms: the Data Plane (Forwarding), which evaluates incoming packet headers in silicon at sub-microsecond line rate, and the Control Plane (Routing), which dynamically computes network topology, exchanges policy constraints, and resolves reachability graphs across global administrative domains.

Mastering enterprise and carrier-grade IP routing requires an exhaustive exploration of algorithmic prefix matching, hardware forwarding engines (TCAMs and pipeline ASICs), the separation of the Routing Information Base (RIB) and Forwarding Information Base (FIB), and the complete operational lifecycle of the Border Gateway Protocol (BGP-4, RFC 4271). This guide presents an authoritative, mathematically rigorous analysis of IP routing mechanics, path-vector convergence dynamics, and carrier-scale BGP policy design.

1. Algorithmic Forwarding: Longest Prefix Match (LPM) & Hardware Architecture#

When an IPv4 or IPv6 datagram arrives at an ingress router interface, the router must determine the egress interface and next-hop Layer 2 MAC address. Unlike conventional key-value datastores that perform exact-match lookups (O(1) hash tables), IP routing operates under the Longest Prefix Match (LPM) paradigm.

+---------------------------------------------------------------------------------------+
|                         Longest Prefix Match (LPM) Trie Tree                          |
|                                                                                       |
|                                       (Root)                                          |
|                                      /      \                                         |
|                                   0 /        \ 1                                      |
|                                  [0]          [1]                                     |
|                                 /   \        /   \                                    |
|                                0     1      0     1                                   |
|                              [00]   [01]  [10]   [11] -> /2 Prefix Node               |
|                                              \                                        |
|                                               1                                       |
|                                              [101]                                    |
|                                                \                                      |
|                                                 0                                     |
|                                               [1010] -> /4 Match (Next Hop: eth2)     |
+---------------------------------------------------------------------------------------+

The Longest Prefix Match Invariant#

Given a destination IP address D and a forwarding table containing routes R_i = (P_i, L_i, NextHop_i), where P_i is the base network prefix and L_i is the prefix length in bits (the subnet mask length):

A route R_i matches destination D if and only if the most significant L_i bits of D are identical to the prefix P_i:

(D ≫ (W - L_i)) = (P_i ≫ (W - L_i))

where W is the bit width of the address family (W = 32 for IPv4, W = 128 for IPv6).

If multiple routes R_a, R_b, ..., R_k match destination D, the router must forward the packet according to the route possessing the strictly maximal prefix length:

R_{selected} = arg max_{R_i ∈ Matches(D)} L_i

Architectural Principle: More specific prefixes take absolute precedence over less specific prefixes, regardless of route metrics, administrative distances, or protocol origins. A /28 static route will unconditionally override a /16 BGP route covering the same address block.

Algorithmic Solutions: From Radix Tries to Level-Compressed Tries#

Software-based forwarding engines implement tree-based data structures to execute LPM efficiently:

1. Unibit Radix Trie:

- A binary tree where each node represents a bit position. Traversing left represents a 0 bit; traversing right represents a 1 bit.

- Nodes corresponding to valid prefix endpoints store forwarding pointers.

- Time Complexity: O(W). For IPv4, worst-case lookup requires 32 memory references; for IPv6, 128 memory references. On modern memory architectures with 60 ns DRAM latency, 32 sequential memory stalls equate to ~1.9 microseconds per lookup, capping software throughput at a meager 500,000 packets per second.

1. Multibit & Patricia Tries (Practical Algorithm to Retrieve Information Coded in Alphanumeric):

- Patricia tries compress one-way branching nodes (paths containing no intermediate prefix endpoints), storing a skip-count index.

- Multibit tries evaluate k bits simultaneously (stride k), reducing trie depth by a factor of k at the expense of memory expansion (2^k pointers per node).

1. Level-Compressed Tries (LC-Tries):

- Dynamically adjusts branching factors based on subtree density: completely populated subtrees of depth d are replaced by single array nodes with 2^d child pointers.

- Reduces average lookup depth for the full global routing table to fewer than 4 to 6 memory access cycles.

Hardware Forwarding: TCAMs & Pipeline ASICs#

In carrier-grade routers (e.g., Cisco Silicon One, Juniper Trio, Arista Jericho), software trie lookups cannot meet line-rate forwarding demands (e.g., 800 Gbps requires processing 1.2 billion packets per second). Hardware implementations utilize Ternary Content Addressable Memory (TCAM).

Standard RAM:   Address Input --------> Data Output
CAM:            Data Input -----------> Exact Address Output (0 or 1 matching)
TCAM:           Data Input + Mask ----> Matching Entry with "Don't Care" (X) bits

TCAM Operational Mechanics:

• Each TCAM storage cell supports three states: 0, 1, and X ("Don't Care" / Wildcard).
• A routing prefix such as 192.168.0.0/16 is stored in TCAM cells as:

11000000 10101000 XXXXXXXX XXXXXXXX

• When an incoming destination IP address is broadcast across the TCAM array, the hardware performs a parallel comparison against all stored entries simultaneously in a single clock cycle (sub-nanosecond latency).
• Priority Encoders: If multiple TCAM entries match (e.g., both a /16 and a /24 prefix match), a hardware priority encoder outputs the lowest physical memory address. Router microcode guarantees LPM correctness by sorting prefixes during FIB compilation such that longer prefix lengths physically occupy lower TCAM array indices.

Hardware Trade-offs: TCAM cells require 16 transistors per cell (compared to 6 for standard SRAM) and dissipate massive electrical power (generating high heat). Global Internet routing table growth places immense strain on line-card TCAM budgets.

2. Control Plane vs. Data Plane: RIB, FIB, & Hardware Offload#

A fundamental axiom of modern networking is the strict bifurcation between the Control Plane and the Data Plane (Forwarding Plane).

+---------------------------------------------------------------------------------------+
|                               Router Architecture                                     |
|                                                                                       |
|  [ CONTROL PLANE (General Purpose CPU) ]                                              |
|      +----------+   +----------+   +--------+                                         |
|      | BGP-4    |   | OSPFv3   |   | Static |                                         |
|      +----+-----+   +----+-----+   +---+----+                                         |
|           \              |            /                                               |
|            v             v           v                                                |
|      +-----------------------------------------+                                      |
|      | Routing Information Base (RIB)          |  <-- Policy evaluation, path metrics,|
|      | Master Topology Table                   |      administrative distance.        |
|      +--------------------+--------------------+                                      |
|                           |                                                           |
|                           v FIB Compilation / Kernel Netlink                          |
|                                                                                       |
|  .........................|.......................................................... |
|                           v IPC / PCIe Bus Transfer                                   |
|  [ DATA PLANE (ASIC / Network Processor Silicon) ]                                    |
|      +-----------------------------------------+                                      |
|      | Forwarding Information Base (FIB)       |  <-- Resolved next-hop MAC addresses,|
|      | Compiled TCAM / Pipeline SRAM Table     |      egress port indices, fast LPM.  |
|      +--------------------+--------------------+                                      |
|                           ^                                                           |
|                           | Line-rate packet processing                               |
|                     Ingress Packets                                                   |
+---------------------------------------------------------------------------------------+

The Routing Information Base (RIB)#

The RIB resides exclusively within the control plane operating system memory (e.g., Linux kernel or vendor OS such as Cisco IOS-XR / Junos).

• Aggregates route advertisements from all active routing daemons: BGP, OSPF, IS-IS, RIP, static configuration, and directly connected subnets.
• Maintains multiple candidate paths to identical destination prefixes, including inactive backup routes and sub-optimal metrics.
• Applies Administrative Distance (AD) (or Route Preference) to adjudicate between disparate routing protocols claiming reachability to the exact same prefix:

The Forwarding Information Base (FIB)#

The FIB is a strictly compiled, distilled, optimized projection of the RIB programmed directly into data plane memory (TCAM and high-speed SRAM).

• FIB Resolution: The FIB contains only the single winning next-hop interface for each active prefix (or multiple next-hops in Equal-Cost Multi-Path, ECMP).
• Recursive Next-Hop Resolution: In the RIB, a BGP route might list a next-hop IP of 198.51.100.1. The router cannot directly emit an Ethernet frame to 198.51.100.1 unless it resolves how to reach that IP. The control plane recursively queries the IGP (OSPF) to find the outgoing physical interface and issues an ARP/NDP lookup to resolve the destination Layer 2 MAC address. The FIB stores the final resolved physical output port and pre-computed Layer 2 rewrite header, allowing the data plane ASIC to forward frames without control plane intervention.

3. Autonomous Systems & Exterior Gateway Protocols#

The Internet is divided into thousands of administrative entities designated as Autonomous Systems (AS). An Autonomous System is a collection of IP networks and routers under the control of a single technical administration that presents a common, unified routing policy to the global Internet (RFC 1930).

• Autonomous System Numbers (ASNs):

- 16-bit ASNs (Legacy): Range 1 to 65,535 (Private ASNs: 64,512 to 65,534).

- 32-bit ASNs (RFC 4893 / 6793): Range 1 to 4,294,967,295. Introduced to avert global ASN pool exhaustion.

• Interior Gateway Protocols (IGP) vs. Exterior Gateway Protocols (EGP):

- IGPs (OSPF, IS-IS): Optimize for shortest path within a single AS. Routers share complete link-state metrics (bandwidth, delay) and compute shortest path trees using Dijkstra's algorithm. IGPs do not scale to millions of routes and cannot enforce inter-organizational business policies.

- EGPs (BGP-4): Optimize for business policies, commercial transit agreements, peering settlements, and regulatory jurisdictions across disparate Autonomous Systems. BGP does not use shortest physical path; it uses Path-Vector routing.

4. BGP-4 Protocol Architecture & Finite State Machine (FSM)#

BGP-4 (RFC 4271) is a stateful, reliable path-vector routing protocol. Unlike IGPs that flood raw IP packets or multicast frames, BGP operates entirely on top of TCP on destination port 179. This architectural decision offloads reliable delivery, packet retransmission, fragmentation, and sequence ordering directly to the kernel TCP stack.

+---------------------------------------------------------------------------------------+
|                             BGP Finite State Machine (FSM)                            |
|                                                                                       |
|     +--------+                                                                        |
|     |  IDLE  | <---------------------+                                                |
|     +---+----+                       |                                                |
|         | Manual Start / Event       | Error / Notification                           |
|         v                            |                                                |
|     +--------+                       |                                                |
|     |CONNECT | ----------------------+ (TCP Fail -> ACTIVE)                           |
|     +---+----+                       |                                                |
|         | TCP Established            |                                                |
|         v                            |                                                |
|     +--------+                       |                                                |
|     | OPENSENT                       |                                                |
|     +---+----+                       |                                                |
|         | Receive Valid OPEN Message |                                                |
|         v                            |                                                |
|     +------------+                   |                                                |
|     | OPENCONFIRM|                   |                                                |
|     +---+--------+                   |                                                |
|         | Receive KEEPALIVE          |                                                |
|         v                            |                                                |
|     +------------+                   |                                                |
|     |ESTABLISHED | ------------------+                                                |
|     +------------+                                                                    |
|           ^                                                                           |
|           |-- Exchanges UPDATE & KEEPALIVE messages continuously                      |
+---------------------------------------------------------------------------------------+

The Six BGP States#

1. Idle:

- The initial state. The BGP process allocates memory, listens for incoming connections, and initializes state variables.

- Upon a start event (administrative configuration or interface activation), BGP clears the ConnectRetry timer, initiates a TCP handshake to the configured peer, and transitions to Connect.

1. Connect:

- BGP waits for the TCP 3-way handshake to complete on port 179.

- If TCP completes successfully: BGP sends an OPEN message to the peer and transitions to OpenSent.

- If the ConnectRetry timer expires prior to TCP establishment: BGP resets the timer, begins listening for incoming peer SYN packets, and transitions to Active.

1. Active:

- In this state, BGP actively attempts to establish a TCP connection with the remote peer by re-initiating the SYN handshake.

- If TCP succeeds: Sends OPEN message and transitions to OpenSent.

- If the ConnectRetry timer expires while in Active: BGP reverts to Connect and restarts the timer.

- Production Symptom: A BGP neighbor toggling continuously between Active and Connect indicates a Layer 3 connectivity failure, mismatched IP addressing, an intervening firewall blocking TCP port 179, or an absent route to the neighbor.

1. OpenSent:

- BGP has transmitted its OPEN message and awaits the peer's corresponding OPEN message.

- When the peer's OPEN arrives, BGP validates all parameters: BGP version (must be 4), peer ASN, BGP Identifier (Router ID), and Hold Time.

- If parameters are valid: BGP transmits a KEEPALIVE message and transitions to OpenConfirm.

- If a mismatch occurs: BGP sends a NOTIFICATION message with the appropriate error code and reverts to Idle.

1. OpenConfirm:

- BGP waits for a KEEPALIVE message from the peer confirming receipt and acceptance of its OPEN parameters.

- Upon receipt of the KEEPALIVE: BGP transitions to Established.

1. Established:

- The BGP peering session is fully operational.

- Peers continuously exchange UPDATE messages (advertising new prefixes or withdrawing unreachable prefixes) and periodic KEEPALIVE messages (to reset the Hold Timer, typically default 90 seconds, sent every 30 seconds).

- If the Hold Timer expires without receiving any communication, or if an invalid update is parsed, BGP emits a NOTIFICATION message and immediately resets the connection to Idle.

BGP Message Formats#

All BGP messages share a mandatory 19-octet header:

• Marker (16 octets): Set to all ones (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) for backward compatibility and synchronization.
• Length (2 octets): Total message size in octets (spanning 19 to 4,096 octets; extended to 65,535 octets under Extended Message Support RFC 8654).
• Type (1 octet):

- 1: OPEN (Negotiates BGP version, Local ASN, Hold Time, BGP Router ID, and Optional Capabilities such as Multiprotocol BGP, 4-byte ASN, Route Refresh).

- 2: UPDATE (Advertises feasible routes with path attributes, or withdraws unfeasible routes).

- 3: NOTIFICATION (Closes the peering session upon encountering an error condition, providing Error Code, Error Subcode, and diagnostic data).

- 4: KEEPALIVE (Header-only message exchanged to ensure peers remain alive in the absence of UPDATE traffic).

- 5: ROUTE-REFRESH (RFC 2918: Dynamically requests a peer to re-advertise its outbound routing table without resetting the TCP connection).

5. BGP Path Attributes & The 13-Step Best Path Algorithm#

Unlike distance-vector protocols that measure path cost in simple hop counts, BGP associates every advertised prefix with an extensible list of Path Attributes. BGP path attributes are categorized across a strict taxonomy:

+---------------------------------------------------------------------------------------+
|                               BGP Path Attribute Taxonomy                             |
|                                                                                       |
|  [ Well-Known Attributes ]                                                            |
|      |                                                                                |
|      +--> Mandatory: Must be included in every UPDATE advertising feasible routes.    |
|      |               (ORIGIN, AS_PATH, NEXT_HOP)                                      |
|      |                                                                                |
|      +--> Discretionary: Recognized by all BGP implementations, but optional.         |
|                          (LOCAL_PREF, ATOMIC_AGGREGATE)                               |
|                                                                                       |
|  [ Optional Attributes ]                                                              |
|      |                                                                                |
|      +--> Transitive: Unrecognized attributes are preserved and passed to downstream  |
|      |                peers. (COMMUNITY, AGGREGATOR)                                  |
|      |                                                                                |
|      +--> Non-Transitive: Unrecognized attributes are silently discarded.             |
|                           (MULTI_EXIT_DISC / MED, ORIGINATOR_ID, CLUSTER_LIST)        |
+---------------------------------------------------------------------------------------+

Detailed Path Attributes#

1. AS_PATH (Type Code 2, Well-Known Mandatory):

- A sequential list of Autonomous System numbers traversed by the route advertisement.

- When an eBGP router advertises a prefix to an external peer, it prepends its own ASN to the head of the AS_PATH vector.

- Loop Prevention Invariant: When a router receives an UPDATE from an eBGP peer, it scans the AS_PATH. If its own local ASN appears anywhere within the sequence, the route is immediately discarded. This guarantees loop-free inter-domain routing across arbitrary network topologies.

1. NEXT_HOP (Type Code 3, Well-Known Mandatory):

- Defines the IP address of the router that should be used as the next hop to the destinations listed in the UPDATE.

- Rule in eBGP: The NEXT_HOP is updated to the IP address of the interface emitting the advertisement.

- Rule in iBGP: By default, iBGP does not alter the NEXT_HOP attribute when reflecting external routes internally. Interior routers must configure next-hop-self to force the edge router to rewrite the NEXT_HOP to its own loopback address.

1. LOCAL_PREF (Type Code 5, Well-Known Discretionary):

- Used exclusively within an Autonomous System (shared between iBGP peers; never advertised across eBGP boundaries).

- Conveys local administrative preference for outbound traffic exits. Higher values indicate higher preference (default is typically 100).

1. MULTI_EXIT_DISC (MED / Metric - Type Code 4, Optional Non-Transitive):

- Conveyed across eBGP links to inform external neighbors of the preferred ingress point into the advertising AS.

- Lower values indicate higher preference (opposite of Local Preference).

- By default, routers only compare MED values between paths originating from the exact same neighboring Autonomous System.

1. COMMUNITY (Type Code 8, Optional Transitive - RFC 1997):

- A 32-bit tag formatted as ASN:Value (e.g., 65001:100).

- Well-known communities include:

- NO_EXPORT (0xFFFFFF01): Do not advertise this route to external eBGP peers.

- NO_ADVERTISE (0xFFFFFF02): Do not advertise this route to any peer (internal or external).

- BLACKHOLE (RFC 7999, 65535:666): Directs upstream transit providers to discard traffic destined to this prefix at line rate in silicon (DDoS mitigation).

The Canonical 13-Step BGP Best Path Selection Algorithm#

When a BGP router receives multiple paths to the exact same prefix, it evaluates them sequentially through a deterministic elimination tournament. The first path to break a tie wins, and evaluation immediately terminates:

1. Next-Hop Reachability: Verify that the NEXT_HOP IP address is resolvable in the local routing table (via IGP or static route). Unresolvable paths are eliminated immediately.
2. Weight (Vendor Specific - Cisco): Prefer the path with the highest Weight (internal to the local router, range 0 to 65,535; default 0, 32,768 for locally originated routes).
3. Local Preference: Prefer the path with the highest LOCAL_PREF across the Autonomous System.
4. Locally Originated: Prefer the path that was originated locally on the router (via network command, redistribution, or aggregation) over paths learned from peers.
5. AS_PATH Length: Prefer the path with the shortest AS_PATH sequence (evaluating total ASN count; AS_SET counts as 1).
6. Origin Code: Prefer the lowest origin code: IGP (0) < EGP (1) < INCOMPLETE (2).
7. Multi-Exit Discriminator (MED): Prefer the path with the lowest MED (compared only between paths originating from the same neighbor AS, unless bgp always-compare-med is enabled).
8. Neighbor Type: Prefer eBGP paths over iBGP paths (External over Internal).
9. IGP Metric to Next-Hop: Prefer the path with the lowest internal IGP cost to reach the BGP NEXT_HOP address (Hot-Potato Routing: eject traffic from the local AS as rapidly as possible).
10. Multipath: If BGP Multipath (ECMP) is configured, install multiple equal-cost paths into the FIB. Otherwise proceed to tie-breakers.
11. Oldest Route (eBGP): Prefer the path that was received first (minimizes route flap disruption).
12. Lowest BGP Router ID: Prefer the path advertised by the peer with the lowest BGP Identifier (evaluated as an IPv4 address).
13. Lowest Peer IP Address: Prefer the path learned from the lowest neighbor IP address.

6. Programmatic BGP State Machine & Path Selector in Python#

The following production-grade implementation models BGP path attributes, validates the 13-step best path selection tournament, and computes winning routes deterministically:

# Programmatic BGP Best Path Selection Engine
from typing import List, Optional
from dataclasses import dataclass, field

@dataclass
class BGPPath:
    neighbor_ip: str
    router_id: str
    is_ebgp: bool
    next_hop: str
    next_hop_reachable: bool
    weight: int = 0                  # Local router weight (Cisco)
    local_pref: int = 100            # Default Local Preference
    locally_originated: bool = False
    as_path: List[int] = field(default_factory=list)
    origin: str = "IGP"              # "IGP", "EGP", or "INCOMPLETE"
    med: int = 0                     # Multi-Exit Discriminator (lower is better)
    igp_cost_to_next_hop: int = 10   # Internal metric to reach next_hop
    route_age_seconds: int = 100     # Time route has been active

class BGPDecisionEngine:
    ORIGIN_HIERARCHY = {"IGP": 0, "EGP": 1, "INCOMPLETE": 2}

    @classmethod
    def select_best_path(cls, candidate_paths: List[BGPPath]) -> BGPPath:
        if not candidate_paths:
            raise ValueError("No candidate paths provided.")

        # Step 1: Filter out unresolvable next-hops
        viable = [p for p in candidate_paths if p.next_hop_reachable]
        if not viable:
            raise ValueError("All candidate paths have unresolvable next-hops.")

        if len(viable) == 1:
            return viable[0]

        # Step 2: Highest Weight
        max_weight = max(p.weight for p in viable)
        viable = [p for p in viable if p.weight == max_weight]
        if len(viable) == 1: return viable[0]

        # Step 3: Highest Local Preference
        max_lp = max(p.local_pref for p in viable)
        viable = [p for p in viable if p.local_pref == max_lp]
        if len(viable) == 1: return viable[0]

        # Step 4: Locally Originated
        local_orig = [p for p in viable if p.locally_originated]
        if local_orig and len(local_orig) < len(viable):
            viable = local_orig
            if len(viable) == 1: return viable[0]

        # Step 5: Shortest AS_PATH
        min_as_len = min(len(p.as_path) for p in viable)
        viable = [p for p in viable if len(p.as_path) == min_as_len]
        if len(viable) == 1: return viable[0]

        # Step 6: Lowest Origin Code (IGP < EGP < INCOMPLETE)
        min_origin = min(cls.ORIGIN_HIERARCHY.get(p.origin, 2) for p in viable)
        viable = [p for p in viable if cls.ORIGIN_HIERARCHY.get(p.origin, 2) == min_origin]
        if len(viable) == 1: return viable[0]

        # Step 7: Lowest MED (assuming identical neighboring AS)
        min_med = min(p.med for p in viable)
        viable = [p for p in viable if p.med == min_med]
        if len(viable) == 1: return viable[0]

        # Step 8: eBGP over iBGP
        ebgp_paths = [p for p in viable if p.is_ebgp]
        if ebgp_paths and len(ebgp_paths) < len(viable):
            viable = ebgp_paths
            if len(viable) == 1: return viable[0]

        # Step 9: Lowest IGP Metric to Next-Hop (Hot-Potato)
        min_igp = min(p.igp_cost_to_next_hop for p in viable)
        viable = [p for p in viable if p.igp_cost_to_next_hop == min_igp]
        if len(viable) == 1: return viable[0]

        # Step 11: Oldest Route (for eBGP paths)
        if any(p.is_ebgp for p in viable):
            max_age = max(p.route_age_seconds for p in viable)
            viable = [p for p in viable if p.route_age_seconds == max_age]
            if len(viable) == 1: return viable[0]

        # Step 12: Lowest BGP Router ID (lexicographical IP comparison)
        import ipaddress
        viable.sort(key=lambda p: int(ipaddress.IPv4Address(p.router_id)))
        min_rid = viable[0].router_id
        viable = [p for p in viable if p.router_id == min_rid]
        if len(viable) == 1: return viable[0]

        # Step 13: Lowest Neighbor IP Address
        viable.sort(key=lambda p: int(ipaddress.IPv4Address(p.neighbor_ip)))
        return viable[0]

7. Checkpoint Practice Problems & Applied Walkthroughs#

Deepen your mastery of routing logic and BGP convergence dynamics through four applied, multi-step calculation problems.

Problem 1: CIDR Longest Prefix Match Routing Table Lookup#

An enterprise core layer-3 switch maintains the following simplified Forwarding Information Base (FIB):

A stream of three distinct packets arrives at the switch carrying the following destination IP addresses:

• Packet A: 10.130.42.155
• Packet B: 10.130.43.10
• Packet C: 10.200.15.1

Questions to Solve:

1. For each packet, determine all matching routes from the FIB.
2. Determine which route wins under the Longest Prefix Match (LPM) rule, specifying the winning egress interface and next-hop gateway.
3. Show binary expansion of the critical boundary octet for Packet B.

Step-by-Step Solution:

Analysis for Packet A (`10.130.42.155`):

• Route 6 (0.0.0.0/0): Matches (covers all addresses). Length: 0.
• Route 1 (10.0.0.0/8): First octet is 10. Matches. Length: 8.
• Route 2 (10.128.0.0/10):

Second octet 130 in binary: 10000010.

Prefix 128 in binary: 10000000.

First 2 bits of second octet are 10. Matches! Length: 10.

• Route 3 (10.130.0.0/16): First two octets are 10.130. Matches! Length: 16.
• Route 4 (10.130.40.0/22):

First 16 bits match 10.130.

Let us inspect third octet (bits 17 to 24):

Mask /22 means 16 + 6 bits = 22 bits. We evaluate top 6 bits of third octet.

Prefix third octet is 40: 00101000. Top 6 bits: 001010.

Destination third octet is 42: 00101010. Top 6 bits: 001010.

They are identical! Matches! Length: 22.

• Route 5 (10.130.42.128/25):

First three octets match 10.130.42.

Mask /25 means top 1 bit of fourth octet.

Prefix fourth octet is 128: 10000000. Top bit is 1.

Destination fourth octet is 155: 10011011. Top bit is 1.

Matches! Length: 25.

Winning Route for Packet A:

Matching routes: Routes 6, 1, 2, 3, 4, 5.

Maximum prefix length is /25 (Route 5).

Packet A is forwarded via interface `eth4` to next-hop `172.16.4.1`.

Analysis for Packet B (`10.130.43.10`):

• Route 6 (0.0.0.0/0): Matches. Length: 0.
• Route 1 (10.0.0.0/8): Matches. Length: 8.
• Route 2 (10.128.0.0/10): Matches (top 2 bits of 130 are 10). Length: 10.
• Route 3 (10.130.0.0/16): Matches (10.130). Length: 16.
• Route 4 (10.130.40.0/22):

Let us examine binary expansion of the third octet:

Prefix 40: 00101000

Destination 43: 00101011

Comparing top 6 bits:

Prefix bits: 0 0 1 0 1 0

Dest bits: 0 0 1 0 1 0

The top 6 bits match completely!

Therefore, Route 4 matches! Length: 22.

• Route 5 (10.130.42.128/25):

Destination third octet is 43. Prefix third octet requires 42.

Bits do not match. Does not match Route 5.

Winning Route for Packet B:

Matching routes: Routes 6, 1, 2, 3, 4.

Maximum prefix length is /22 (Route 4).

Packet B is forwarded via interface `eth3` to next-hop `172.16.3.1`.

Analysis for Packet C (`10.200.15.1`):

• Route 6 (0.0.0.0/0): Matches. Length: 0.
• Route 1 (10.0.0.0/8): Matches (10.x.x.x). Length: 8.
• Route 2 (10.128.0.0/10):

Second octet is 200: in binary 11001000.

Top 2 bits are 11.

Prefix 128 top 2 bits are 10.

Mismatch! Does not match Route 2.

• Routes 3, 4, 5: All require second octet 130. Mismatch!

Winning Route for Packet C:

Matching routes: Routes 6, 1.

Maximum prefix length is /8 (Route 1).

Packet C is forwarded via interface `eth0` to next-hop `172.16.0.1`.

Problem 2: BGP 13-Stage Best Path Elimination Tournament#

A core edge router (AS 65000, Router ID 10.0.0.1) receives four competing BGP UPDATE path advertisements for the destination prefix 203.0.113.0/24. The path attributes are summarized below:

Execute the 13-stage BGP Decision Algorithm step-by-step. Document every eliminated path at each stage and determine the winning path installed into the routing table.

Step-by-Step Solution:

Stage 1: Next-Hop Reachability

• Path Alpha: 198.51.100.1 is resolvable. (Retained)
• Path Beta: 198.51.100.2 is resolvable. (Retained)
• Path Gamma: 198.51.100.3 is NOT resolvable (next-hop-reachable: False).

Elimination: Path Gamma is immediately disqualified. Despite having Weight 32768 and Local Pref 200, an unresolvable next-hop renders a path physically unforwardable.

• Path Delta: 198.51.100.4 is resolvable. (Retained)
• Remaining Paths: Alpha, Beta, Delta.

Stage 2: Highest Weight

• Path Alpha: Weight = 0
• Path Beta: Weight = 0
• Path Delta: Weight = 0
• All remaining paths tie at 0. (No eliminations).
• Remaining Paths: Alpha, Beta, Delta.

Stage 3: Highest Local Preference

• Path Alpha: Local_Pref = 100
• Path Beta: Local_Pref = 150
• Path Delta: Local_Pref = 150
• Highest Local_Pref is 150.

Elimination: Path Alpha is eliminated (100 < 150).

• Remaining Paths: Beta, Delta.

Stage 4: Locally Originated

• Path Beta: Locally Originated = No
• Path Delta: Locally Originated = No
• Tie.
• Remaining Paths: Beta, Delta.

Stage 5: Shortest AS_PATH Length

• Path Beta: AS_PATH = [65300, 65400, 65500] -> Length = 3 ASNs.
• Path Delta: AS_PATH = [65300, 65500] -> Length = 2 ASNs.
• Minimum length is 2 ASNs.

Elimination: Path Beta is eliminated (Length 3 > Length 2).

Decision:

Evaluation terminates at Stage 5.

Winning Path: Path Delta is selected as the BGP Best Path and programmed into the FIB.

Notice that we did not even need to evaluate Origin code (where Delta was inferior with INCOMPLETE), MED, or Router ID, because Stage 5 resolved the tie decisively in Delta's favor.

Problem 3: TCAM Sizing & FIB Exhaustion in Carrier Core Routers#

A tier-1 telecommunications provider prepares a multi-chassis core routing platform for a 5-year hardware lifecycle.

• Current Global Routing Table Size:

- IPv4 Prefixes: N_{v4} = 950,000 routes

- IPv6 Prefixes: N_{v6} = 210,000 routes

• Projected Annual Growth Rates:

- IPv4 compound annual growth rate: g_{v4} = 6.5% per year

- IPv6 compound annual growth rate: g_{v6} = 18.0% per year

• TCAM Hardware Constraints:

- The line-card forwarder utilizes 72-bit TCAM blocks.

- An IPv4 entry (32-bit IP + 32-bit mask + 8 bits metadata) occupies exactly one 72-bit TCAM block.

- An IPv6 entry (128-bit IP + 128-bit mask + 16 bits metadata = 272 bits) requires four contiguous 72-bit TCAM blocks (288 bits allocated).

- The line-card features a total hardware TCAM capacity of 3,500,000 blocks of 72 bits.

• Calculations Required:

1. Calculate the total number of 72-bit TCAM blocks consumed by the current routing table.

2. Project the total IPv4 and IPv6 route counts after t = 5 years.

3. Calculate the projected TCAM block consumption at year 5 and determine whether hardware exhaustion (TCAM overflow) will occur.

Step-by-Step Solution:

Step 1: Calculate current TCAM block consumption.

• IPv4 routes occupy 1 block each:

B_{v4, 0} = 950,000 × 1 = 950,000 blocks

• IPv6 routes occupy 4 blocks each:

B_{v6, 0} = 210,000 × 4 = 840,000 blocks

• Total Current TCAM Usage:

B_{total, 0} = 950,000 + 840,000 = 1,790,000 blocks

• Current Utilization Percentage:

U_0 = (1,790,000 / 3,500,000) × 100 ≈ 51.14%

Step 2: Project route counts at Year 5 using compound growth.

Formula for compound growth: N_t = N_0 × (1 + g)^t

For IPv4 after 5 years at g = 6.5% (1.065):

N_{v4, 5} = 950,000 × (1.065)^5

(1.065)^5 ≈ 1.3700867

N_{v4, 5} = 950,000 × 1.3700867 ≈ 1,301,582 IPv4 routes

For IPv6 after 5 years at g = 18.0% (1.180):

N_{v6, 5} = 210,000 × (1.180)^5

(1.180)^5 ≈ 2.2877578

N_{v6, 5} = 210,000 × 2.2877578 ≈ 480,429 IPv6 routes

Step 3: Calculate projected Year 5 TCAM block consumption.

• IPv4 TCAM blocks required:

B_{v4, 5} = 1,301,582 × 1 = 1,301,582 blocks

• IPv6 TCAM blocks required:

B_{v6, 5} = 480,429 × 4 = 1,921,716 blocks

• Total Projected TCAM Blocks:

B_{total, 5} = 1,301,582 + 1,921,716 = 3,223,298 blocks

• Year 5 Utilization Percentage:

U_5 = (3,223,298 / 3,500,000) × 100 ≈ 92.09%

Exhaustion Analysis:

Total capacity is 3,500,000 blocks. At year 5, consumption reaches 3,223,298 blocks (92.09%).

The hardware will survive the 5-year lifecycle without catastrophic exhaustion.

However, remaining margin is only 276,702 blocks (7.91%). By Year 6:

Projected Year 6 total blocks:

1,301,582 × 1.065 + (480,429 × 1.180 × 4) = 1,386,185 + 2,267,625 = 3,653,810 blocks.

Since 3,653,810 > 3,500,000, the line card will experience complete TCAM exhaustion in Year 6, precipitating route drops or silent fallback to software slow-path forwarding.

Problem 4: RPKI Route Origin Validation (ROV) Cryptographic Evaluation#

To prevent malicious BGP hijacking and unintentional route leaks, an autonomous system deploys Resource Public Key Infrastructure (RPKI) Route Origin Validation (ROV).

The network administrator registers a signed Route Origin Authorization (ROA) object in the regional RPKI trust anchor containing:

• Authorized ASN: AS 64496
• Prefix: 198.51.100.0/22
• MaxLength: /24

The edge BGP router subsequently receives four external BGP route advertisements across various internet exchange peering points:

• Route A: Prefix 198.51.100.0/22, Origin AS in AS_PATH = 64496
• Route B: Prefix 198.51.100.0/24, Origin AS in AS_PATH = 64496
• Route C: Prefix 198.51.100.0/25, Origin AS in AS_PATH = 64496
• Route D: Prefix 198.51.100.0/24, Origin AS in AS_PATH = 64500

Questions to Solve:

1. State the three standardized RPKI validation states defined in RFC 6811.
2. Evaluate and classify each of the four routes (Route A through Route D) under RFC 6811 validation rules.
3. If the router implements standard RPKI invalid-drop policy, which routes will be permitted into the BGP decision engine, and what attack vector is thwarted?

Step-by-Step Solution:

Step 1: Standard RFC 6811 RPKI Validation States:

• Valid: At least one ROA matches the prefix, the prefix length does not exceed MaxLength, and the advertising origin ASN matches the ROA authorized ASN.
• Invalid: A ROA covers the prefix, but either:

1. The origin ASN does not match the authorized ASN in the covering ROA, OR

2. The prefix length is strictly greater than the authorized MaxLength.

• NotFound (Unknown): No covering ROA exists in the RPKI cache for the specified prefix.

Step 2: Evaluation of Candidate Routes:

• Route A (`198.51.100.0/22`, Origin AS 64496):

- Covering ROA exists for 198.51.100.0/22.

- Origin AS 64496 matches authorized ASN.

- Length (/22) ≤ MaxLength (/24).

- Classification: Valid.

• Route B (`198.51.100.0/24`, Origin AS 64496):

- Covering ROA exists for 198.51.100.0/22.

- Origin AS 64496 matches authorized ASN.

- Prefix length is /24. Since /24 ≤ MaxLength (/24), this deaggregated subnet is explicitly authorized by the ROA.

- Classification: Valid.

• Route C (`198.51.100.0/25`, Origin AS 64496):

- Covering ROA exists (198.51.100.0/22).

- Origin AS matches (64496).

- Prefix length is /25.

- Condition: /25 > MaxLength (/24).

- Even though the origin ASN is legitimate, the prefix length violates the authorized MaxLength.

- Classification: Invalid.

• Route D (`198.51.100.0/24`, Origin AS 64500):

- Covering ROA exists (198.51.100.0/22).

- Prefix length /24 ≤ MaxLength (/24).

- Origin ASN in advertisement is 64500. Authorized ASN in ROA is 64496.

- ASN mismatch!

- Classification: Invalid.

Step 3: Security Policy Outcome:

• Under standard ROV policy (discard-invalid):

- Permitted Routes: Route A and Route B are accepted into the BGP table.

- Dropped Routes: Route C and Route D are discarded at the ingress filter.

• Attack Vector Thwarted:

- Route D represents a classic BGP Subprefix Hijack. An adversarial autonomous system (AS 64500) attempted to hijack traffic by announcing a specific /24. Because /24 is a longer prefix than the benign /22, without RPKI, global Internet routers would have favored AS 64500 due to the Longest Prefix Match rule, redirecting all user traffic into the adversary's network. RPKI ROV flagged the unauthorized origin ASN and dropped the announcement in the control plane, neutralizing the hijack.