Hierarchical Routing

The basics

• Aggregate routers into regions - Autonomous Systems (AS)
• Routers in same AS run same Intra-AS routing protocol, routers in different AS can run different protocols
• Gateway Router is a direct link to router in another AS

See also What is an Autonomous System | Cloudflare

Forwarding table is configured by both intra- and inter-AS routing algorithm

• Intra-AS sets entries for internal destinations
• Inter-AS and intra-AS sets entries for external destinations

Inter-AS v Intra-AS

Suppose router in AS1 receives datagram for which dest is outside of AS1, router will forward the packet towards one of the gateway routers. AS1 needs

1. To learn which dests are reachable through AS2 and which through AS3
2. To propagates this reachability info to all routers in AS1

These are all done through Inter-AS Routing

Suppose AS1 learns from the inter-AS protocol that subnet x (in AS3) is reachable from AS3 (gateway 1c) but not from AS2

• Inter-AS protocol propagates reachability info to all internal routers
• Router 1d determines from intra-AS routing info that its interface I is on the least cost path to 1c
• Puts in forwarding table entry (x,I)

Suppose AS1 learns form the inter-AS protocol that subnet x is reachable from AS3 and AS2

• To configure forwarding table, router 1d must determine towards which gateway it should forward packets for dest x
• This is also the job on inter-AS routing protocol
• Hot Potato Routing: send packet towards closest of two routers
  (doesn't care about inter-AS traversal, only cares about getting the packet out of my AS as quick as possible, saves traffic in my own AS)

Why different Intra and Inter-AS routing?

1. Policy
   • Inter-AS: admin wants control over how its traffic routed, who routes through its net
   • Intra-AS: single admin, so no policy decisions needed
2. Scale
   • Hierarchical routing saves table size, reduced update traffic
3. Performance
   • Intra-AS: can focus on performance
   • Inter-AS: policy may dominate over performance

Inter-AS Protocols

Routing across different ASs

BGP (Border Gateway Protocol)

BGP provides each AS a mean to

1. Obtain subnet reachability information from neighboring ASs
2. Propagate the reachability information to all routers internal to the AS
   • Tells nodes who the gateway routers are, but not how to get to them (this is intra-as)
3. Determine "good" routes to subnets based on reachability information and policy

Allows a subnet to advertise its existence to rest of the Internet: "I am here"

BGP Basics

• Pairs of routers (BGP Peers) exchange routing info over semi-permanent TCP connections: BGP Sessions
  • Note that BGP sessions do not correspond to physical links
• When AS2 advertises a prefix to AS1, AS2 is promising it will forward any datagrams destined to that prefix towards the prefix
  • AS2 can aggregate prefixes in its advertisement
• Two types
  • eBGP: between gateways of ASs
  • iBGP: between routers inside an AS (responsible for announcing reachability info)

Distributing reachability info

• With eBGP session between 3a and 1c, AS3 sends prefix reachability info to AS1
• 1c can then use iBGP to distribute this new prefix reach info to all routers in AS1
• 1b can then re-advertise the new reach info to AS2 over the 1b-to-2a eBGP session
• When router learns about a new prefix, it creates an entry for the prefix in its forwarding table

Path attributes and BGP routes

• When advertising a prefix, advert includes BGP attributes
  • Prefix + attributes = route
• Two important attributes
  1. AS-PATH: contains the ASs through which the advert for the prefix passed
     (which ASs the packet went through)
  2. NEXT-HOP: indicates the specific internal-AS router to next-hop AS
     (which internal next-hop inside your AS is, there may be multiple)
• When gateway router receives route advert, uses import policy to accept/decline

BGP Route Selection

• Router may learn about more than 1 route to some prefix. Router must select route.
• Elimination rules:
  1. Local preference value attribute: policy decision
  2. Shortest AS-PATH
  3. Closest NEXT-HOP router: hot potato routing
  4. Additional criteria

BGP Messages
BGP messages exchanged using TCP

• OPEN
• UPDATE
• KEEP ALIVE
• NOTIFICATION

BGP Routing Policy
A,B,C are provider networks
X,W,Y are customer (of provider networks)
X is dual-homed: attached to two networks

X does not want to route from B via X to C
so X will not advertise to B a route to C

A advertises to B the path AW
B advertises to X the path BAW
Should B advertise to C the path BAW?

• No. B gets no “revenue” for routing CBAW since neither W nor C are B’s customers
• B wants to force C to route to w via A
• B wants to route only to/from its customers

Intra-AS Protocols

Routing within the same AS
Also known as Interior Gateway Protocols (IGP)

RIP (Routing Information Protocol)

Routing Algorithms#Distance Vector Algorithm (bellman-ford, overall topology unknown)

• Distance metric is number of hops (max = 15 hops)
• Distance vectors: exchanged among neighbors every 30s via Response Message
  • Also called advertisement
  • Each advertisement list of up to 25 destination nets within AS

Example routing table for D

Link failure and recovery

• If no advertisement heard after 180s, neighbor/link declared dead
  • Routes via neighbor invalidated
  • New advertisements sent to neighbors
  • Neighbors in turn send out new advertisements (if tables changed)
  • Link failure info quickly propagates to entire net
  • Poison reverse used to prevent ping-pong loops (infinite distance = 16 hops)

RIP table processing

• RIP routing tables managed by application-level process called route-d (daemon)
• Advertisements sent in UDP packets, periodically repeated

OSPF (Open Shortest Path First)

Routing Algorithms#Link-State Routing Algorithm (dijkstra's, overall topologies known)

• OSPF advertisement carries one entry per neighbor router
• Advertisements disseminated to entire AS (via flooding)
  • Carried in OSPF messages directly over IP (rather than TCP or UDP)

OSPF advanced features that is not in #RIP (Routing Information Protocol)

• Security: messages authenticated

• Multiple same-cost paths allowed

• For each link, multiple cost metrics for different types of services

  Example: satellite link cost, email, set "low", high for real time

• Integrated uni- and multicast support

• Hierarchical OSPF in large domains