← Previous Tutorial  |  Table of Contents  |  Unit Home  |  Next Tutorial →

Tutorial 7: Hierarchical Routing and Autonomous Systems Expanded

Table of Contents

  1. Learning Objectives
  2. Overview
  3. Detailed Technical Content
  4. Quiz
  5. Exercises
  6. Homework
  7. Summary

Learning Objectives

Overview

As the Internet grew from a few nodes to billions of devices, it became impossible to run a single routing protocol on all routers. The control plane needed a scalable structure that could accommodate administrative boundaries, policy differences, and the sheer volume of routing information. This led to the adoption of hierarchical routing, where the network is partitioned into Autonomous Systems (ASes). Within an AS, an interior gateway protocol (IGP) like OSPF or RIP handles internal routing; between ASes, an exterior gateway protocol (EGP) – specifically BGP – exchanges reachability information. This two-level hierarchy enables scalability, allows organizations to enforce their own policies, and isolates routing failures. This tutorial provides a deep dive into the theoretical and practical aspects of hierarchical routing, including graph-theoretic models, AS types, route aggregation, economic relationships, and the challenges that arise in inter-domain routing.

Detailed Technical and Theoretical Content

1. The Need for Hierarchy: Scalability and Administrative Autonomy

A flat routing architecture would require every router to know the path to every other router, leading to:

Hierarchy partitions the problem: each AS manages its internal routing independently, and only reachability information (not full topologies) is exchanged between ASes. This reduces the global routing table size from O(V²) to O(number of prefixes) with summarization.

2. Graph-Theoretic Foundations of Hierarchy

Hierarchical routing can be modeled as a two-level graph:

Aggregation is achieved by summarizing internal routes at the AS boundary. For example, all prefixes within an AS can be advertised as a single aggregate prefix if they are contiguous. This reduces the number of entries in the inter-AS routing table.

3. Autonomous Systems (AS): Definition, Types, and ASNs

An Autonomous System (AS) is a collection of IP networks and routers under the control of a single administrative entity that presents a common routing policy to the Internet. Each AS is identified by a unique AS Number (ASN) (16-bit or 32-bit) assigned by IANA/Regional Internet Registries.

AS types:

4. Intra-AS Routing (IGP) and Its Role

Within an AS, an Interior Gateway Protocol (IGP) is used. Common IGPs include OSPF (link-state), IS-IS, and RIP. The IGP provides:

The IGP routes packets to the AS's exit routers (border routers) for destinations outside the AS. The IGP also resolves the NEXT-HOP attribute learned from BGP (i.e., the IGP is used to reach the BGP next-hop router).

5. Inter-AS Routing (EGP) – The Role of BGP

The only EGP used on the Internet is BGP (Border Gateway Protocol). Unlike IGPs, BGP is not concerned with internal topology; it exchanges reachability information (prefixes) and path attributes (AS-PATH, NEXT-HOP, LOCAL-PREF, etc.) between ASes. BGP is policy-based: each AS selects and announces routes according to its own policies (e.g., avoid certain ASes, prefer a cheaper provider).

6. Hierarchical Routing Architecture and Route Propagation

The typical path of a packet from a host in AS1 to a host in AS3 involves:

  1. AS1's IGP forwards the packet to the egress border router that has a BGP route to AS3.
  2. The egress router forwards the packet to the next AS (AS2) via eBGP.
  3. Inside AS2, IGP forwards the packet to the appropriate border router.
  4. AS2 forwards to AS3 via eBGP.
  5. Inside AS3, IGP forwards to the destination.

BGP ensures that each AS learns the path (AS-PATH) to external prefixes. The IGP is used solely for internal delivery.

7. Route Aggregation and Summarization (CIDR)

Classless Inter-Domain Routing (CIDR) allows routes to be aggregated. For example, instead of advertising 192.168.1.0/24, 192.168.2.0/24, and 192.168.3.0/24 separately, an AS can advertise 192.168.0.0/22. Aggregation reduces the size of the global BGP routing table and limits the propagation of specific updates. However, aggregation can also cause black holes if the aggregate includes subnets that are not reachable, or sub-optimal routing if the aggregate forces traffic through a non-optimal AS.

8. Design Principles of Hierarchical Routing

9. AS Relationships: Customer-Provider, Peering, Transit

AS relationships determine how routes are propagated and how traffic flows:

These relationships are enforced by BGP policies: a router will not announce routes learned from a peer to its other peers (valley-free routing).

10. Challenges: Policy Conflicts, Scalability, and Traffic Engineering

Figure 1: AS-level hierarchy and relationships

    +----------------+          +----------------+
    |   Tier-1 AS A  | <---->   |   Tier-1 AS B  |  (peering)
    +----------------+          +----------------+
          |   \                    /   |
          |    \                  /    |
    +-------+     +---------+   /     +-------+
    | Tier-2 |     | Tier-2  | /      | Tier-2|
    | AS 1   |     | AS 2    |        | AS 3  |
    +-------+     +---------+        +-------+
        |             |                  |
    +----------+  +----------+    +----------+
    | Stub AS  |  | Stub AS  |    | Stub AS  |
    +----------+  +----------+    +----------+
    (Customer-Provider: Tier-2 buys from Tier-1; Stub buys from Tier-2)

Quiz

Answer each question; check your understanding by revealing the answer.

Question 1: What is the primary reason for hierarchical routing in the Internet?

Show AnswerScalability: to reduce routing table size and limit update propagation, and to allow administrative autonomy and policy enforcement.

Question 2: What is an Autonomous System (AS)?

Show AnswerAn AS is a collection of networks under a single administrative domain that presents a common routing policy to the Internet.

Question 3: What is an ASN, and who assigns it?

Show AnswerAn ASN (Autonomous System Number) is a unique identifier for an AS, assigned by IANA/Regional Internet Registries.

Question 4: What is the difference between a stub AS and a transit AS?

Show AnswerA stub AS connects to only one other AS and does not carry transit traffic; a transit AS connects to multiple ASes and allows traffic to pass through.

Question 5: Which protocol is used for intra-AS routing? Give two examples.

Show AnswerInterior Gateway Protocols (IGPs) like OSPF and RIP.

Question 6: Which protocol is used for inter-AS routing on the Internet?

Show AnswerBGP (Border Gateway Protocol).

Question 7: What is the role of route aggregation (CIDR) in hierarchical routing?

Show AnswerIt reduces the number of prefixes advertised, shrinking routing tables and limiting update overhead.

Question 8: What is a customer-provider relationship between ASes?

Show AnswerThe customer pays the provider to carry its traffic to the rest of the Internet; the provider announces the customer's routes.

Question 9: What is peering in the context of AS relationships?

Show AnswerPeering is a mutual exchange of traffic between two ASes, often without payment, where each only carries traffic for its own customers.

Question 10: How does hierarchical routing help with failure isolation?

Show AnswerA failure within an AS is contained within that AS; it does not flood the entire Internet with updates, only the AS's reachability may change.

Question 11: What is the main challenge of inter-AS routing in terms of policies?

Show AnswerPolicy conflicts: different ASes have different objectives, leading to suboptimal global routes.

Question 12: Why is BGP convergence slow compared to IGPs?

Show AnswerDue to hold-down timers, policy-based decision making, and the need to propagate updates across multiple ASes.

Question 13: What is a multihomed AS?

Show AnswerAn AS that connects to two or more other ASes but does not allow transit traffic between them.

Question 14: In a two-level hierarchy, what does the upper level (AS-level graph) represent?

Show AnswerIt represents the connections (peering/transit) between ASes, with nodes as ASes.

Question 15: How does route aggregation potentially cause black holes?

Show AnswerIf an aggregate prefix is advertised but some subprefixes within it are not reachable, traffic to those subprefixes will be dropped.

Question 16: What is the valley-free routing principle?

Show AnswerA path should not go from a provider to a customer and then to a provider (i.e., it should not use peering to reach another provider), ensuring no transit through a customer.

Question 17: How does an AS use BGP to influence inbound traffic?

Show AnswerBy manipulating attributes like AS-PATH prepending, MED, or communities to make its routes less or more preferred.

Question 18: What is the difference between peering and transit?

Show AnswerPeering is mutual exchange without payment; transit involves payment to carry traffic to other ASes.

Question 19: How does an IGP help BGP?

Show AnswerThe IGP is used to resolve the NEXT-HOP attribute of BGP routes, providing a path to the border router that advertised the route.

Question 20: What is the main benefit of hiding internal topology from other ASes?

Show AnswerIt reduces the amount of routing information exchanged and allows internal changes without affecting the rest of the Internet.

Question 21: What is the role of the IANA in AS number allocation?

Show AnswerIANA allocates blocks of AS numbers to Regional Internet Registries (RIRs), which then assign them to ISPs and organizations.

Question 22: How does route aggregation reduce the size of the BGP routing table?

Show AnswerBy representing multiple contiguous prefixes with a single prefix, reducing the number of entries.

Question 23: What is a "transit AS" in terms of policy?

Show AnswerAn AS that provides connectivity between other ASes, carrying traffic that neither originates nor terminates in it.

Question 24: Why might an AS choose to de-aggregate its prefixes?

Show AnswerFor traffic engineering: to attract traffic to specific entry points or to load balance.

Question 25: What is the relationship between the IGP and BGP on a border router?

Show AnswerThe border router runs both IGP (to reach internal destinations) and BGP (to exchange external routes). It injects BGP-learned routes into the IGP (or distributes them via iBGP) to make them known internally.

Exercises

Work through these problems; sample solutions are hidden.

Exercise 1: Draw a network of three ASes: AS1 (stub), AS2 (transit), AS3 (stub). AS2 connects to AS1 and AS3. Show the BGP update flow and the path a packet takes from a host in AS1 to a host in AS3.

Show Sample Solution

AS1 and AS3 are stub; AS2 is transit. AS1 advertises its internal prefixes to AS2 via eBGP. AS2 imports them and advertises them to AS3 via eBGP. A packet from AS1 to AS3: inside AS1, IGP forwards to border router; border router forwards to AS2; AS2 forwards via IGP to its border router to AS3; AS3's IGP forwards to destination.

Exercise 2: Explain why a full mesh of iBGP sessions is not required if route reflectors are used. How does a route reflector help scale iBGP?

Show Sample Solution In a full mesh, each iBGP router must peer with every other iBGP router, resulting in O(n²) sessions. A route reflector (RR) allows iBGP routers to peer only with the RR(s). The RR reflects routes to its clients, reducing the number of sessions to O(n).

Exercise 3: An AS has four prefixes: 10.1.0.0/24, 10.1.1.0/24, 10.1.2.0/24, 10.1.3.0/24. Can these be aggregated? If so, what is the aggregate prefix?

Show Sample Solution Yes, they are contiguous in the 10.1.0.0/22 range. The aggregate is 10.1.0.0/22 (covers addresses 10.1.0.0 to 10.1.3.255).

Exercise 4: Suppose AS X has a customer AS Y and a peer AS Z. According to valley-free routing, should AS X advertise routes from Y to Z? Why or why not?

Show Sample Solution No, AS X should not advertise routes from its customer Y to its peer Z, because that would allow Z to use Y's routes without paying for transit, violating the peering agreement (peering is usually between peers for their own customers, not for customers of peers).

Exercise 5: Explain how the AS-PATH attribute in BGP prevents routing loops.

Show Sample Solution When a BGP router receives an update, it checks if its own AS number is already in the AS-PATH. If so, it discards the route because it would create a loop.

Exercise 6: Compare the routing table size in a flat routing scheme (all routers know all paths) versus a hierarchical scheme (with ASes). Use a network with N routers and M ASes (each with N/M routers).

Show Sample Solution Flat scheme: each router has O(N) entries (all destinations). Hierarchical: each router has internal entries (N/M) plus external entries (M prefixes after aggregation). Total entries ≈ N/M + M, which is much smaller than N for large N.

Exercise 7: What is the impact of using a very large number of ASes on the scalability of BGP?

Show Sample Solution More ASes means more AS-PATH lengths and more updates, increasing processing and memory. Also, route aggregation becomes harder, leading to a larger global routing table.

Exercise 8: Describe the process of route selection at an AS border router when it receives multiple BGP routes for the same prefix from different neighbors (e.g., a customer, a peer, a provider).

Show Sample Solution The router applies policies: typically it prefers routes from customers over peers over providers (economic preference). Within each category, it uses BGP attributes (LOCAL-PREF, AS-PATH length, MED, etc.) to select the best.

Exercise 9: Explain how BGP route aggregation can lead to suboptimal routing. Give an example.

Show Sample Solution If AS1 aggregates 192.168.0.0/22, but the best path to 192.168.1.0/24 would be via AS2, and to 192.168.2.0/24 via AS3, the aggregate forces all traffic to go via one AS (the one advertising the aggregate), which may not be optimal.

Exercise 10: In a multi-homed AS, how can the AS influence outbound traffic to choose a specific provider?

Show Sample Solution By setting LOCAL-PREF higher for routes received from the preferred provider.

Homework Assignments

These questions require deeper thought and research. Write comprehensive answers.

Homework 1: Prove that hierarchical routing reduces the average routing table size in a network with N routers partitioned into M ASes, each of size N/M. Assume perfect aggregation of external routes.

Show Answer Outline Calculate the number of entries: internal = (N/M) - 1, external = M (if each AS announces one aggregate). Total ≈ N/M + M. Minimized when M = sqrt(N), giving 2√N entries, which is much less than N for large N.

Homework 2: Compare and contrast the design goals of intra-AS (IGP) and inter-AS (BGP) routing. Why do they have different metrics and convergence requirements?

Show Answer Outline IGP: optimize for performance (min delay, max bandwidth), fast convergence, scalability within hundreds of routers. BGP: optimize for policy, scalability to millions of prefixes, stability over speed, and economic relationships.

Homework 3: Research the concept of "BGP route dampening" and explain how it prevents route flapping from causing instability.

Show Answer Outline Route dampening assigns a penalty to routes that flap (withdraw and readvertise). When the penalty exceeds a threshold, the route is suppressed (not used) for a period. It decays over time, reducing instability.

Homework 4: Design a hierarchical routing architecture for a large enterprise with multiple sites (4 data centers, 20 branch offices). Describe how you would partition into ASes (or use a single AS with areas) and justify your choices.

Show Answer Outline Use a single AS with OSPF areas (or multiple ASes if policy separation is needed). For simplicity, use OSPF with area 0 backbone, and areas for each site. If using multiple ASes, each site as a stub AS connecting to a backbone AS.

Homework 5: Explain the "valley-free" routing property and prove that it holds if all ASes follow the standard peering/transit policies. What happens if an AS violates this property?

Show Answer Outline Valley-free: a path can go through customers (up) and peers (sideways) but not down then up (i.e., you cannot go from provider to customer then to provider). Violation can cause an AS to carry transit traffic for a peer, violating agreements and potentially causing loops.

Homework 6: Discuss the trade-offs between using multiple ASes for an organization versus a single AS with OSPF areas. Consider scalability, policy flexibility, and management complexity.

Show Answer Outline Multiple ASes give policy flexibility and isolation, but increase BGP complexity and require more resources. Single AS with OSPF areas is simpler but may not allow different policies per site.

Homework 7: Investigate the growth of the global BGP routing table. What are the main drivers of growth (e.g., IPv6, de-aggregation, multi-homing)? How do mitigation techniques like aggregation and route reflectors help?

Show Answer Outline Growth driven by IPv6, multi-homing, and de-aggregation for TE. Aggregation reduces entries; route reflectors reduce iBGP mesh, not table size. Need for better aggregation and filtering.

Homework 8: Explain how BGP communities are used to implement routing policies. Provide an example of a community used for traffic engineering.

Show Answer Outline Communities are tags attached to routes (e.g., 100:10). They can be used to influence routing decisions within an AS or between ASes. Example: a community that sets LOCAL-PREF to prefer a route for specific traffic.

Homework 9: Compare the scalability of iBGP full mesh versus route reflection in an AS with 100 routers. Calculate the number of iBGP sessions needed in each case.

Show Answer Outline Full mesh: n*(n-1)/2 = 4950 sessions. With route reflectors (e.g., 2 RRs), each router peers with RRs: 2n = 200 sessions, much smaller.

Homework 10: Explain how an AS can use AS-PATH prepending to influence inbound traffic. Provide a scenario where this is useful.

Show Answer Outline AS-PATH prepending adds extra AS numbers to a route, making it appear longer (less preferred). This is useful to reduce inbound traffic on a congested link.

Homework 11: Research the concept of "BGP route leakage" and explain how it can cause disruption on the Internet. Provide an example.

Show Answer Outline Route leakage occurs when an AS announces routes learned from one peer to another, violating policies. This can cause traffic to be misrouted, e.g., a provider announcing its customer's routes to a peer, causing the peer to send traffic through that provider, potentially overloading it.

Homework 12: Discuss the role of Internet Exchange Points (IXPs) in hierarchical routing. How do they affect peering and route propagation?

Show Answer Outline IXPs are physical locations where multiple ASes peer, reducing latency and transit costs. They create a dense peering mesh at the AS level, allowing more direct paths and reducing reliance on transit providers.

Summary

This tutorial provided a thorough examination of hierarchical routing and Autonomous Systems. We explored the fundamental need for hierarchy, graph-theoretic models, AS types, and the roles of IGPs and BGP. We analyzed route aggregation, design principles, AS relationships, and the challenges of policy conflicts and scalability. Understanding hierarchical routing is essential for comprehending how the Internet scales to billions of devices while accommodating diverse administrative and economic requirements. This knowledge sets the stage for the detailed study of BGP in the next tutorial.

← Previous Tutorial  |  Table of Contents  |  Unit Home  |  Next Tutorial →

End of Tutorial 7 .