# 50.012 Lecture 15
Textbook Section 5.3, 5.4

## Making Routing Scalable
Routing is so far idealized:
* All routers are identical
* Networks are "flat"

In real life, there are hierarchies in networks, which will actually help routing to be more scalable.

Routers are aggregated into regions known as "autonomous systems" (AS) (a.k.a. "domains"). This is so that not all internal routers need to communicate with those from other AS.

**Intra-AS routing**
* Routing among hosts, routers in same AS ("network")
* All routers in AS must run the same intra-domain protocol
* Routers in different AS can run different intra-domain routing protocol
* Gateway router: at "edge" of its own AS, has link(s) to router(s) in other AS'es.

**Inter-AS routing**
* Routing among AS'es.
* Gateways perform inter-domain routing (as well as intra-domain routing).

### Interconnected AS-es

### Inter-AS Tasks

Suppose router in AS1 receives a datagram destined outside of AS1, the router should forward the packet to gateway router.

AS1 is supposed to learn which destinations are reachable through AS2 and AS3.
Then, it will propagate this information to all routers in AS1.

### Intra-AS Routing
It's also knwon as interior gateway protocol (IGP).
Most common intra-AS routing protocols:
* RIP: Routing Information Protocol
* OSPF: Open Shortest Path First (essentially the same as IS-IS protocol)
* IGRP: Interior Gateway Routing Protocol, which used to be proprietary to Cisco.

### OSPF
"open" means publicly available.

It uses link-state algorithm. This is because we can limit the size of the graph (and hence scalability is not an issue).

For bigger AS-es, there can still be a hierarchy within the AS. (see textbook)

Route computation in OSPF is done using Dijkstra's algorithm.

Router will need to flood OSPF link-state advertisements to all other routers in entire AS. Hence, OSPF messages can be sent directly over IP (rather than TCP or UDP).

### Inter-AS Routing: BGP
Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol.

BGP has 2 "sub-protocols":
* eBGP: to obtain subnet reachability information from neighboring AS-es.
* iBGP: to propagate reachability information to all AS-internal routers.

BGP uses a variant of distance vector algorithm.
1c, 2a, 2c, 3a are known as gateway routers.

### BGP Basics

BGP session: 2 BGP routers, "peers", exchange BGP messages over semi-permanent TCP connection. The message is to advertise paths to different destination network prefixes.
This protocol is known as a "path vector" protocol.
Note that instead of broadcasting just the distance, this protocol has to announce the path.


When AS3 gateway router 3a advertises path AS3,X to AS2 gateway router 2c, AS3 promises to AS2 it will forward datagrams towards X.

### BGP Route Selection
BGP sequentially invokes the following rules to select a route:
1. Local preference value attribute: policy decision
2. Shortest AS-PATH
3. Closest NEXT-HOP router: hot potato routing
4. Additional Criteria

Since BGP is an inter-domain protocol, route-finding is not as simple as the conventional shortest path problem. (e.g. sometimes there are countries that are not friendly and we can't route via those countries).
There are policies that BGP must abide by.

### Achieving Policy via Advertisements

Since W is a customer of A, it is A's duty as providers to connect W to the rest of the Internet, and vice versa.
W will be assigned a block of IP Address by A.
A will then help to advertise the path Aw to B and C.
When B receives this advertisement, B can choose whether to accept it (import policy) and whether to advertise it (export policy).

In this context, import policy happens at the gateway/border router that is closer to A, while export policy takes place at the gateway router that is closer to C.

If B announces the path BAw to C, it promises C that it will forward the packet from C to W via that path.
Since B and C are just peering relationship, if C sends packets via B, B does not get any revenue for routing CBAw. This is because none of C,A,w are B's customers. Hence, B may choose to not advertise BAw.

In this figure, X is dual-homed (X is attached to two networks).
B and C have the duty and interest to announce the routes to X, and X's existence to the rest of the Internet.

However, in this case, consider if X does not want to be
The policy to enforce is that X does not want to route from B to C via X. So X will not advertise to B a route to C.
As a customer network, it does not make sense for X to forward traffic from B to C.

### Intra vs Inter AS Routing
#### Policy
* Inter-AS: Admin wants control over how its traffic is routed, who routes through its net.
* Intra-AS: Single admin, so no policy decisions needed.

#### Scale:
* Scalability is critical for inter-AS routing
* Intra-AS: less an issue, can always use hierarchical routing to reduce scale.

#### Performance
* Inter-AS: policy may dominate over performance.
* Intra-AS: Can focus on performance