BGP and OSPF: Enabling Autonomous Systems Communication

Topics Covered: Autonomous Systems, OSPF, BGP

What is an Autonomous System (AS)?

The Global Internet is comprised of many Autonomous Systems, which we will refer to as ASes from now on. Each AS gets its own ASN (AS Number). Stub AS refers to an end user AS, like a campus network, and Transit AS refers to an AS part of the backbone, like one belonging to an ISP. Routing occurs at two levels, within the AS (Intra-AS), and between ASes (Inter-AS). We will focus on OSPF for intra and BGP for inter. Both OSPF and BGP work to fill in individual routers' forwarding tables. Note: an AS can be comprised of multiple subnets. These aren't the same thing. A single organization can also have multiple ASes.

OSPF

OSPF (Open Shortest Path First) uses the link-state algorithm. Each node is aware of its neighbors and costs to access them, by periodically sending Hello messages directly on IP packet to them. This makes sure our neighbors are still up and we get to measure the costs. Routers also broadcast link-state packets to the entire network.

What happens if we don't get a Hello in the last 10 seconds? Then that node is down. So we need to broadcast our new link-state packet immediately. Otherwise, broadcast every 30 minutes. How do we identify that we have obtained a new link-state packet with the most up-to-date information? LSP needs to contain a sequence number, and we need to ACK those we receive while forwarding.

In summary, the goal of OSPF is to be able to route packets within an AS from any one router to another.

BGP

BGP (Border Gateway Protocol) uses the path-vector algorithm, which is similiar to distance-vector (see last notes). BGP allows ASes to advertise their IP prefixes to the rest of the Internet, and propagate the reachability of the rest of the Internet to all routers within the AS. BGP is over TCP.

When router 3a from AS3 sends a BGP message with the prefix 12.3.6/24 to router 1c in AS1, AS3 tells AS1 that 3a will forward packets toward that prefix. Advertising is not always something an AS wants to do, as you'll see in discussion with BGP policy.

In addition to the IP prefix, BGP messages include attributes.

• AS-PATH is the list of ASes which that advertisement has passed through. In the above example, AS2, AS1, AS3 is the AS-PATH. It's implemented a bit like a stack. Why is it needed? Let's say we have a connection from AS2 to AS3. If AS2 gets AS-PATH AS1, AS3 from AS1, then we know we should not advertise to AS3, otherwise we will have a loop.
• NEXT-HOP is the router which links one AS to another. For the case of AS2 to get to 12.3.6/24, our next hop is to router 1b.
• Local-Preference just states our priority in choosing a path. This takes priority over others. BGP is policy-driven, not necessarily performance-driven ($$$). After local preference, generally speaking shorter AS-PATH is chosen.

eBGP vs iBGP

eBGP is a BGP session between two different ASes. In the above example, 1b advertising to 2a would be eBGP. iBGP is a BGP session between two routers in the same AS, such as 2a to 2c. That's all.

Hot Potato Routing

Let's say we are in AS1, specifically at router 1d in the above image, and all links are the same cost except 1c–1d which is broken (cost

$\mathrm{\infty }$). Let's say both AS3 and AS2 have paths to get to our destination prefix x, and AS3 advertises AS-PATH: AS3, AS4, x while AS2 advertises AS2, AS5, AS6, AS8, x. Hot Potato routing says that we want to get out of our AS as fast as possible, ignoring the AS-PATH. So we would pick AS2, because we only need to hop one link to get to the gateway router 1b. This mainly helps with load-balancing (why?).

Next Week's Topics: Link Layer, ALOHA, CSMA/CD, Ethernet Switching