YCG's Oasis🌴

Recent Notes

Hierarchical Routing

5 min read

Why Hierarchical Routing?

Idealizing networks as a flat graph of interconnected, identical routers. In practice, this approach is not feasible for two main reasons:

  • Scalability Issue

    • The Internet has hundreds of millions of destination networks.
    • It’s impossible for any single router to store a routing table entry for every destination.
    • Even if it were possible, exchanging these massive routing tables among all routers would overwhelm the network links.

  • Administrative Autonomy

    • The Internet is a “network of networks.”
    • Each individual network is under a different administrative authority.
    • Each administrator wants to control how traffic is routed within their own network.

Autonomous Systems (AS)

To address these issues, we aggregate routers into groups called regions or Autonomous Systems (AS):

image|w50

  • An Autonomous System (AS) is a collection of routers under a single administrative authority.
  • Each AS is assigned a unique Autonomous System Number (ASN).

    For example, the HKUST network is an AS with ASN AS 3363

Gateway Routers

Routers that sit at the edge of an AS and have a direct connection to a router in another AS are called gateway routers. These routers are crucial for inter-AS communication.

graph TD
    subgraph AS1
        R1[Router 1D] -- Intra-AS --> G1[Gateway 1C];
    end
    subgraph AS2
        G2[Gateway 2B];
    end
    subgraph AS3
        G3[Gateway 3A];
    end

    G1 -- Inter-AS Link --> G2;
    G1 -- Inter-AS Link --> G3;

Intra-AS vs. Inter-AS Routing

The routing process is split into two levels:

  • Intra-AS Routing: Routing within a single AS. Routers inside the same AS run the same Intra-AS routing protocol (e.g., OSPF).

  • Inter-AS Routing: Routing between different ASes. Gateway routers run an Inter-AS routing protocol (e.g., BGP) to learn and share reachability information outside their own AS.

Intra-AS Routing

Usually we use Interior Gateway Protocols (IGP) for Intra-AS routing. There are two main categories of IGPs:

  • Distance-Vector Protocols: Routers share their distance vectors with neighbors (e.g., RIP).

  • Link-State Protocols: Routers share the complete network topology with all routers in the AS (e.g., OSPF).

RIP

Routing Information Protocol (RIP) is one of the earliest distance-vector protocols, which use distance vector algorithms for routing within an AS.

  • Distance Metric: Number of hops (cost of 1 per link).
  • Limitation: Maximum of 15 hops (16 hops is considered infinity).
  • Advertisements: Routers exchange their entire distance vector (up to 25 subnets) with neighbors every 30 seconds via UDP.

If no advertisement is received from a neighbor for 180 seconds, the routes through that neighbor are considered invalid:

  • The router sets the distance to those destinations to infinity (16 hops).
  • The router then propagates this information to its neighbors.

OSPF (Open Shortest Path First)

OSPF is a more advanced and widely used protocol that overcomes many of RIP’s limitations.

  • use link state algorithm to do the routing, all routers have a complete map of the network topology
  • security: all OSPF messages are authenticated.
  • allow multiple same cost path (for load balancing)
  • service-aware routing: Integrates with the IP Type of Service (ToS) field.

    A link can have different costs for different traffic types (e.g., high cost for real-time traffic on a high-latency satellite link).

Hierarchical OSPF

To improve scalability in large networks, OSPF can divide an AS into a backbone and local areas.

  • Link-state advertisements are flooded only within an area.

  • Each router knows the detailed topology of its own area but only knows the direction (summary) to other areas.

  • This creates a two-level hierarchy:

    • Within an area: Link-state routing.
    • Between areas: Distance-vector-like routing.

image|w70

Inter-AS Routing

Border Gateway Protocol (BGP) is the de facto standard for Inter-AS routing. It is the “glue” that holds the Internet together.

image|w85

Important

BGP allows an AS to:

  1. Obtain subnet reachability information from neighboring ASes (via eBGP).
  2. Propagate this reachability information to all routers within its own AS (via iBGP).
  3. Determine “good” routes to other networks based on policies.

BGP Basics

  • Path Vector Protocol: BGP routers (peers) advertise not just a destination, but the entire path (a list of AS numbers) to reach that destination.
  • Sessions: BGP peers establish semi-permanent TCP connections to exchange routing information.
  • Advertisements: An AS advertises a prefix (e.g., 193.14.0.0/16) and promises to forward traffic destined for that prefix. An AS can also aggregate multiple prefixes into a single advertisement.

Important

advertisements are the key to policy control (since BGP is policy driven protocol). If you don’t want to carry traffic for a certain prefix, simply do not advertise it.

Key BGP Attributes

Each advertised prefix comes with attributes. Two of the most important are:

  • AS-PATH: The sequence of ASes the advertisement has passed through. This is crucial for policy.
  • NEXT-HOP: The specific router interface to use to get to the next AS in the path.

Route Selection Criteria

When a router learns multiple routes to the same destination, it selects the best one based on this order:

  1. Local Preference Value: A policy-based attribute set by the administrator.
  2. Shortest AS_PATH: The route with the fewest ASes in its path is preferred.
  3. Hot Potato Routing: If multiple routes are still tied, the router chooses the path with the closest gateway router (i.e., the one with the lowest cost within its own AS).
  4. Additional Criteria: Other BGP attributes can be used as a final tie-breaker.

Summary: Intra-AS vs. Inter-AS Routing

FeatureIntra-AS Routing (IGP)Inter-AS Routing (BGP)
GoalOptimize routing within a single administrative domain.Connect different administrative domains.
PolicyFocuses on performance; little to no policy.Policy dominates. Administrators control who can use their network.
ScaleFocuses on performance within a limited scope.Focuses on scalability by aggregating network information.
PerformanceHigh priority (e.g., finding the absolute shortest path).Secondary to policy. Performance is considered via hot potato routing.

This hierarchical structure allows the Internet to function at a global scale while respecting the administrative boundaries and policies of individual networks.

Graph View