Scalability Problem of Routing
In 04-Control Plane Routing Protocols, we assumed:
- Aligned objectives
- All routers aim to deliver packets to the destination as efficiently as possible
- Willingness to cooperate
- Routers are willing to share routing information, and sometimes even full topology information
- A common metric
- Shortest path, least cost, or lowest delay
- A single administrative domain
- The network is managed by one organization, or at least follows one common set of rules
- Basic mutual trust among node
- All routers aim to deliver packets to the destination as efficiently as possible
- Manageable scale
This works inside small managed network, however the Internet breaks those assumptions.
Internet approach to scalable routing
Internet aggregate routers into regions known as “autonomous systems” (AS) (aka domains).
- Intra-AS
- Scope: within one AS
- Goal: efficiency + shortest path
- Example protocols: OSPF, RIP, EIGRP
- Inter-AS
- Scope: across ASes
- Goal: policy + cost + agreements
- Example protocol: BGP
Intra-AS routing
Most common intra-AS routing protocols
- RIP (Routing Information Protocol)
- classic DV
- no longer widely used
- EIGRP (Enchanced Interiror Gateway Routing Protocol)
- DV based
- formerly Cisco-proprietary for decades
- OSPF (Open Shortest Path First)
- link-state routing
- IS-IS protocol (ISO standard) essentially same as OSPF
Hierarchical OSPF: handles what if AS itself becomes large?
Two-level hierarchy exists - local area and backbone area:
- area border routers
- summarize distances to the routers in its area
- advertise them to backbone router
- local routers
- flood link-state across routers in its area
- compute routing within its area
- forward packets to outside via area border router
- boundary router (Gateway router)
- connects to other ASes
- backbone routers
- runs OSPF limited to backbone routers
Inter-AS routing: BGP (Border Gateway Procotol)
- BGP: the de facto inter-domain routing protocol
- “glue that holds the internet together”
- allows subnet to advertise its existence, and the destinations it can reach to the rest of Internet.
A Tempting Abstraction: AS as Node
- No AS has a complete view of the whole Internet.
- Routing information is exchanged neighbor by neighbor.
- Reachability is propagated incrementally.
- In that sense, BGP still feels “vector-like”.
Inter-AS Routing Is Not Just About Efficiency
- Limited trust: they may not trust each other fully
- Hide internal topology: they may not want to reveal internal topology
- Business relationships: competitors
- Policy over shortest path: they may prefer one route for policy reasons, not for shortest distance
Once we move across AS boundaries, routing is no longer just a technical optimization problem.
It becomes a problem involving economics, policy, and autonomy.
Path Vector: Advertize the Path
BGP session: two BGP routers exchange BGP messages over semi-permanent TCP connection:
- Advertising paths to different destination network prefixes (BGP is a “path vector” protocol)
- Distance vector: “I can reach this destination with this cost”
- Path Vector: “I can reach this destination through this AS path”
Why path vector is necessary: loop prevention
- For pure distance vector, loop is hard to detect: “count-to-infinity” problem.
- In BGP, loop detection becomes much more explicit since a route carries the ASes it has terversed.
- AS rejects a path if itself appears in the path.
Why path vector is necessary: policy-based routing
- AS1 gateway router 1c learns:
- path AS2, AS3, X from 2a.
- path AS3, X from 3a.
- Based on policy, AS1 gateway router 1c chooses path AS3, X and advertises path within AS1 via iBGP.
iBGP + eBGP + Intra-AS routing
