Making routing scalable
Here are some concepts to note:
scale: billions of destinations:
- can't store all destinations in routing tables.
- routing table exchange would swamp links.
administrative autonomy:
- Internet: a network of networks
- each network admin may want to control routing in its own network
Approach to scalable routing
We always aggregate routers into regions known as "autonomous systems" (a.k.a "domains").
And intra-AS (intra-domain) is such routing among routers within same AS(network).
- all routers in AS must run same intra-domain protocol.
- routers in different AS can run different intra-domain protocols.
- gateway router: at edge of its own AS, has link(s) to router(s) in other AS'es
inter-AS routing among AS'es is the gateways perform inter-domain routing
Both of them determine entries for destination of routers, while former is within AS and latter is for external destinations. Most common intra-AS routing protocols:
- RIP (Routing Information Protocol), which is no longer widely used.
- OSPF (Open Shortest Path First), which includes classic link-state routing.
- EIGRP: (Enhanced Interior Gateway Routing Protocol), which is DV based/
OSPF
OSPF is an intra-domain routing protocol.
open: publicly available
classic link-state:
- each router floods OSPF link-state advertisements (directly over IP) to all other routers in entire AS.
- multiple link costs metrics possible: bandwidth, delay.
- global (has full topology)
There is two-level hierarchy: local area and backbone.
- Local routers only know/compute detailed topology within its local area, and forwad information to area border routers.
- And area border routers are responsible for summarizing distances to destinations in own area, and advertising in backbone.
BGP
BGP is an inter-domain routing protocol ("glue that holds the Internet together").
BGP provides each AS a means to:
- obtain destination network reachability information from neighboring ASes (eBGP).
- determine roues to other networks based on reachability information and policy.
- propagate reachability information to all AS-internal routers (iBGP).
- advertise destination reachability information.
BGP Basics
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
BGP protocol messages [RFC 4371]:
- Open: opens TCP connection to peer and authenticates sending BGP peer
- Update: advertises new path (or withdraws old)
- Keepalive: keeps connection alive in absence of UPDATES; also ACKS OPEN request
- Notification: reports erros in previous msg; also used to close connection
BGP: path advertisement
BGP advertised path: prefix + attributes
- path prefix: destination being advertised
- two important attributes:
- AS-PATH: list of ASes through which prefix advertisement has passed
- NEXT-HOP: indicates specific internal-AS router to next-hop AS
BGP policy
ISP only wants to route traffic to/from its customer networks (does not want to carry transit traffic between other ISPs – a typical “real world” policy)
BGP: populating forwading tables
Just popluate from boundary to internal and choose local gateway that has least intra-domain cost. Omit details here.
Benefits
Intra/Inter-AS routing scale the network, creating hierarchical routing, reducing forwarding table size. And seperate them can make:
- intra-AS focus on performance.
- inter-AS has policy dominates over performaance.