Network Layer: Intra-AS and Inter-AS Routing Protocols

Foundations and Limitations of Flat Routing Architectures

Idealized Routing Assumptions:
- Theoretical routing models typically assume that all network routers are completely identical in function, capacity, and role.
- Theoretical models treat the network topology as a flat, uniform graph structure with no regional partitioning or administrative boundaries.
- These models assume that all routers cooperate unconditionally to calculate globally optimal paths and forward datagrams efficiently along the shortest possible paths.
- In operational production networks, none of these idealized assumptions hold true.
Flat Network Graph Representation:
- In an idealized flat topology, routers are modeled as simple nodes connected by weighted undirected links (such as nodes $u, v, w, x, y, z$ with link costs $(u, v) = 2$ , $(u, x) = 1$ , $(u, w) = 5$ , $(v, w) = 3$ , $(v, x) = 2$ , $(w, x) = 3$ , $(w, y) = 1$ , $(w, z) = 5$ , $(x, y) = 1$ , and $(y, z) = 2$ ).

Idealized flat network graph with weighted links between routers

Real-World Operational Challenges:
- Administrative Autonomy:
  - The Internet is an interconnected aggregation of independent, commercial, governmental, and academic organizations.
  - End-user experience is predominantly determined by the performance, bandwidth, and latency of edge and last-hop networks.
  - Every network administrator insists on retaining complete authority to design, configure, manage, and optimize the internal routing architecture within their own domain without external interference.
- Scale of the Global Internet:
  - The global Internet comprises on the order of hundreds of millions of routers ( $O(\text{hundreds of millions})$ ).
  - At this scale, broadcasting link-state updates globally or running periodic distance-vector exchanges across all routers is computationally intractable and would overwhelm link bandwidth.
  - Even if global algorithm synchronization were possible, hardware routers cannot maintain or program forwarding tables containing billions of individual destination addresses.

Hierarchical Routing: Autonomous Systems and Gateway Routers

The Autonomous System (AS) Model:
- To overcome scalability limits and preserve administrative independence, the Internet aggregates routers into distinct operational domains known as Autonomous Systems (AS).
- An Autonomous System represents a collection of routers under the control of a single technical administration (such as an ISP, a corporate enterprise, or an educational institution).
Intra-AS (Intra-Domain) Routing:
- Refers to the routing protocols and algorithms executing strictly within the boundaries of a single Autonomous System.
- Each organization possesses complete freedom to select whichever intra-AS routing protocol aligns with its internal performance metrics.
- Once a protocol is selected by an administrator, all internal routers within that specific AS must run the identical protocol.
Inter-AS (Inter-Domain) Routing:
- Refers to the routing protocols and algorithms executing across boundaries to interconnect distinct Autonomous Systems.
- While individual ASes are free to execute any intra-AS protocol internally, every Autonomous System across the global Internet must run the identical inter-AS protocol to establish end-to-end reachability.
Gateway Routers:
- A gateway router is a designated router positioned at the perimeter or edge of an Autonomous System that possesses physical links terminating at routers in external Autonomous Systems.
- Gateway routers execute both intra-domain and inter-domain routing protocols simultaneously, bridging internal reachability with external routing announcements.
Forwarding Table Configuration:
- A router's forwarding table is programmed through the joint interaction of both intra-AS and inter-AS routing processes.
- Local Destinations: Determined exclusively by intra-AS routing protocols, which map internal destination subnets to the appropriate local outgoing interface.
- External Destinations: Determined jointly by inter-AS and intra-AS routing algorithms; inter-AS routing identifies the egress gateway router, and intra-AS routing determines the internal path and local interface required to reach that gateway.

Intra-AS Routing Protocols: Standards and Taxonomy

Routing Information Protocol (RIP):
- Standardized under RFC 1723.
- Built upon the classic Distance-Vector algorithm.
- Calculates paths based purely on hop count (maximum metric capped at 15 hops to prevent count-to-infinity).
- Considered legacy technology and is not widely used in modern production networks.
Open Shortest Path First (OSPF):
- Standardized under RFC 2328.
- Built upon the Link-State algorithm using Dijkstra’s shortest path formulation.
- Represents the most commonly deployed intra-AS routing protocol in modern enterprise and service-provider networks.
Enhanced Interior Gateway Routing Protocol (EIGRP):
- Standardized under RFC 7868.
- Built upon an advanced Distance-Vector algorithm (utilizing the Diffusing Update Algorithm, or DUAL).
- Originally developed as a proprietary Cisco protocol; Cisco opened the protocol specification in 2013.

Open Shortest Path First (OSPF) Protocol Architecture

Specification and Standards History:
- Formally specified as OSPF Version 2 in RFC 2328 (Standards Track, STD 54; obsoletes RFC 2178), authored by J. Moy (Ascend Communications, Inc.) under the Network Working Group of the Internet Society in April 1998.
- Engineered strictly as a link-state routing protocol designed to operate internal to a single Autonomous System.
- Identical Topology Database: Every participating OSPF router within an area maintains an identical Link-State Database (LSDB) that completely describes the internal network topology.
- Shortest-Path Tree Calculation: Each router independently executes Dijkstra’s shortest-path algorithm using its local LSDB to construct a shortest-path tree rooted at itself, deriving its local forwarding table entries.
The Five OSPF Message Types:
- Hello (Type 1): Discovers, builds, and maintains neighbor relationships and adjacencies between directly connected routers; periodically verifies neighbor reachability.
- Database Description (DBD / DD, Type 2): Transmits an abbreviated summary of the router's local link-state database (specifically LSA headers) to adjacent peers during initial synchronization.
- Link-State Request (LSR, Type 3): Requests specific, detailed Link-State Advertisements from an adjacent router when the local router identifies outdated or missing entries following a DBD exchange.
- Link-State Update (LSU / Link-State Response, Type 4): Transmits full, detailed Link-State Advertisements (LSAs) containing the current state and metrics of specific links.
- Link-State Acknowledgment (LSAck, Type 5): Provides explicit, reliable transport acknowledgment for received Link-State Update packets, guaranteeing database synchronization.

OSPF Adjacency Formation and State Machine:
- Down State: The initial state where no Hello packets have been received from the neighboring router.
- Init State: Router R1 sends a Hello packet announcing its Router ID (RID 1.1.1.1) with the seen list empty (Seen [null]).
- 2-way State: Router R2 receives R1's Hello and responds with a Hello acknowledging R1 (Seen [1.1.1.1], RID 2.2.2.2). R1 receives this and confirms R2 (Seen [2.2.2.2]), establishing bidirectional communication.
- Designated Router (DR) Election: On broadcast multi-access segments, routers evaluate priorities and RIDs to elect a Designated Router (DR=x.x.x.x) and Backup Designated Router (BDR) to limit full mesh adjacencies.
- ExStart State: Routers initiate database synchronization by establishing a master/slave relationship and choosing an initial sequence number using DBD packets containing LSA headers.
- Exchange State: Routers exchange DBD packets containing LSA headers to compare link-state database contents.
- Loading State: Routers issue Link-State Requests (LSR) for missing or more recent records, receiving the full LSAs inside Link-State Updates (LSU), and confirming them via Link-State Acknowledgments (LSAck).
- Full State: Neighboring routers achieve identical link-state databases, achieving full operational adjacency.

OSPF adjacency formation and message exchange state machine

Operational Characteristics and Engineering Features:
- Security Mechanisms: All OSPF messages can be authenticated to prevent unauthorized routers or malicious intruders from corrupting routing tables. OSPF supports cryptographic MD5 authentication.
- Transport Layer Independence: Although OSPF operates as a control-plane protocol, it does not use transport-layer protocols such as TCP or UDP. OSPF packets are encapsulated directly into IP datagrams (using IP protocol number 89), implementing its own internal Reliable Data Transfer (RDT) mechanisms via explicit timeouts and LSAck packets.
- Hierarchical OSPF Deployment:
  - Large enterprise networks can be segmented into multiple distinct OSPF areas to constrain memory consumption and CPU churn.
  - All areas must connect directly to a central Backbone Area (Area 0).
  - Each area runs an isolated link-state calculation internally.
  - Area Border Routers (ABRs) summarize internal routes belonging to their local areas before announcing them into the backbone network.
- Equal-Cost Multi-Path (ECMP): When multiple paths to a destination exhibit identical cost metrics, OSPF supports splitting traffic across all available paths, facilitating advanced traffic engineering and load balancing.
- Link Metric Assignment and Traffic Engineering:
  - There is an intrinsic two-way relationship between assigned link weights and calculated routing paths.
  - Setting all link weights to $1$ ( $\text{weight} = 1$ ) results in pure minimum-hop routing.
  - Setting link weights inversely proportional to link capacity ( $\text{weight} = \frac{1}{\text{link-capacity}}$ ) discourages routing through narrow links, steering high-volume traffic toward high-bandwidth links.

Border Gateway Protocol (BGP): Architecture and Operation

Protocol Overview and Internet Role:
- The Border Gateway Protocol (BGP) is the de-facto standard inter-domain routing protocol of the global Internet, serving as the foundational mechanism that interconnects all Autonomous Systems.
- Core Objective: Enables independent Autonomous Systems to advertise their existence, broadcast the destination IP prefixes they can reach, and establish loop-free paths across the wide-area Internet.
Four Primary Functional Capabilities of BGP:
- External Reachability Advertisement: Allows an AS to announce its reachable IP prefixes to directly adjacent neighboring Autonomous Systems via external BGP (eBGP). This advertisement includes the path.
- External Reachability Ingestion: Allows an AS to learn destination prefix reachability information from neighboring Autonomous Systems via eBGP. The Ingestion just shows its endpoints its capable of reaching and not the pathways.
- Route Selection and Policy Enforcement: Enables an AS to select the best path toward any external destination prefix based on received reachability data and internal policy rules.
- Internal Reachability Propagation: Distributes externally acquired reachability information to all internal routers within the local AS boundary via internal BGP (iBGP).
eBGP versus iBGP Connectivity:
- External BGP (eBGP): Operates over direct physical links connecting gateway border routers located in different Autonomous Systems .
- Internal BGP (iBGP): Operates over logical peering connections between routers located inside the same Autonomous System
- Gateway Router Integration: Border gateway routers execute both eBGP and iBGP protocols simultaneously, translating external reachability data into internal network announcements.

BGP architecture illustrating physical eBGP links between gateway routers and logical iBGP mesh within autonomous systems

BGP Sessions and Path Vector Mechanics:
- BGP Session: Two peering BGP routers exchange control messages over a persistent Transmission Control Protocol (TCP) connection on port 179.
- Distance-Vector Extension (Path Vector): BGP is a path-vector protocol. BGP advertisements convey the target destination IP prefix accompanied by a complete Path Vector (the ordered list of Autonomous System Numbers through which the advertisement has traveled).
- Loop Prevention: If a router receives a BGP advertisement containing its own Autonomous System Number inside the AS-PATH attribute, it immediately discards the route to prevent routing loops.
- Forwarding Commitment: An advertised BGP route constitutes an administrative commitment that the advertising AS is prepared and capable of forwarding traffic toward the specified IP prefix.

BGP Policy Routing, Path Propagation, and Forwarding

Policy-Based Routing Principles:
- Unlike intra-AS protocols where shortest paths are calculated mathematically based on link costs, BGP routing choices are dominated by economic, commercial, and geopolitical policies.
- Import Policy (Inbound): When a gateway router receives an external route advertisement for destination prefix $X$ , it applies local policy rules to accept or reject the path (e.g., establishing a rule to never route traffic through a commercial rival AS $W$ or through country $Y$ ).
- Export Policy (Outbound): A gateway router evaluates local policy to decide whether to advertise a known path to neighboring AS $Z$ (e.g., deciding whether to carry transit traffic originating from $Z$ that is destined for external network $X$ ).
Step-by-Step BGP Path Advertisement Walkthrough:
- Consider a multi-AS topology comprising AS1, AS2, and AS3, where network prefix $X$ is physically attached to AS3:
  1. Gateway router 3a in AS3 transmits an eBGP advertisement for prefix $X$ with the path vector AS3, X to gateway router 2c in AS2.
  2. Based on AS2's local import policy, router 2c accepts the route AS3, X and propagates it internally to all AS2 routers (2a, 2b, 2d) via iBGP.
  3. Based on AS2's export policy, gateway router 2a prepends its own AS identity and announces the path AS2, AS3, X across the eBGP connection to gateway router 1c in AS1.

BGP path advertisement flow across interconnected autonomous systems AS3, AS2, and AS1

Handling Multiple Path Announcements:
- Gateway router 1c in AS1 may receive two distinct paths to reach destination $X$ : an indirect path AS2, AS3, X via router 2a, and a direct path AS3, X via router 3a.
- Based on local selection policy (such as shortest AS-PATH, local preference, or peering economics), router 1c selects AS3, X as its active route and advertises this choice across AS1 to routers 1a, 1b, and 1d using iBGP.
Populating Local Forwarding Tables:
- Routers combine iBGP reachability data with internal OSPF path calculations to install forwarding entries:
  - Inside AS1, routers 1a, 1b, and 1d learn via iBGP from border gateway 1c: To reach destination $X$ , send traffic to gateway 1c.
  - At router 1d, intra-domain OSPF routing calculates that the shortest internal path to reach gateway 1c exits via local interface 1. Router 1d populates its forwarding table mapping destination $X$ to interface 1.
  - At router 1a, intra-domain OSPF routing calculates that the shortest internal path to reach gateway 1c exits via local interface 2. Router 1a populates its forwarding table mapping destination $X$ to interface 2.

Commercial Economics and Policy Engineering in BGP

Customer-Provider Peering Relationships:
- Internet transit agreements are strictly governed by financial relationships: customer networks pay provider networks for global transit, whereas peering networks exchange customer traffic symmetrically without settling fees.
- Fundamental Provider Policy: An Internet Service Provider (ISP) routes traffic to and from its paying customers, but will strictly refuse to carry transit traffic between other competing ISPs.
Selective Path Advertisement Scenario:
- Consider a topology where customer network $A$ hosts destination prefix $w$ and connects to two upstream providers, $B$ and $C$ :
  - Customer network $A$ advertises its route A, w to both provider $B$ and provider $C$ .
  - Provider $B$ chooses not to advertise path B, A, w to provider $C$ .
  - Economic Justification: Neither $C$ , $A$ , nor $w$ pays provider $B$ to transit traffic between $C$ and $A$ . Carrying traffic along path C -> B -> A -> w would consume $B$ 's backbone bandwidth without generating any revenue.
  - Result: Provider $C$ never learns the route C, B, A, w and is compelled to forward packets destined for $w$ directly across its own customer link C, A, w.
Multi-Homed Customer Routing Policy:
- Consider customer network $x$ that is multi-homed (attached concurrently to two upstream providers, $B$ and $C$ ):
  - Customer $x$ purchases redundant connections for reliability and resilience.
  - Policy Objective: Customer $x$ wants to prevent provider $B$ from using $x$ as a transit conduit to send traffic to provider $C$ , which would consume customer $x$ 's paid access bandwidth.
  - Implementation: Customer router $x$ does not advertise routes learned from provider $B$ to provider $C$ , and does not advertise routes learned from provider $C$ to provider $B$ .
  - Result: Providers $B$ and $C$ can only use links to $x$ for traffic whose ultimate source or destination terminates within customer network $x$ .

Architectural Comparison: Intra-AS vs. Inter-AS Routing

Policy versus Performance Drivers:
- Inter-AS Routing: Driven primarily by policy, business economics, and administrative control. Network operators must have absolute authority over how external traffic transits their infrastructure, which paths are selected, and who routes through their network. Optimal algorithmic performance is secondary to policy compliance.
- Intra-AS Routing: Driven entirely by performance optimization. Because the entire Autonomous System is controlled by a single administrative organization, trust and policy are not concerns. Protocols focus exclusively on path metrics, load balancing, and minimizing internal network latency.
Scale and State Complexity Drivers:
- Inter-AS Routing: Must scale across hundreds of thousands of independent networks and manage forwarding state for hundreds of thousands of global IP prefixes. Protocol data structures, message passing, and update mechanisms are engineered to minimize memory overhead and suppress route flapping globally.
- Intra-AS Routing: Scalability is bounded by the perimeter of a single organization. Even when an enterprise network or ISP scales to tens of thousands of routers, scalability bottlenecks are resolved by partitioning the domain into hierarchical OSPF areas connected via an Area 0 backbone.