Interdomain Routing and the
Border Gateway Protocol (BGP)—
What does it all mean?


Slide 3

Telstra international

WorldCom (UUNet)

Network Interconnections

What about Logical Connectivity?

All Hail the IP Datagram!

Hosts, Networks, and Routers

Actually, IP addresses Identify Interfaces

IP Forwarding Table

IP Forwarding Process

Routing vs. Forwarding

How Are Forwarding Tables Populated to implement Routing?

Routers Talking to Routers
(The “control plane”)

Architecture of Dynamic Routing

"Topology information is flooded within..."

The Gang of Four

Happy Packets: The Internet Does Not Exist Only to Populated Routing Tables

AS Numbers (ASNs)

Autonomous Routing Domains Don’t Always Need BGP or an ASN

U of Minnesota Neighborhood

ASNs Can Be “Shared” (RFC 2270)

Number of Used ASNs

AS Graphs Can Be Fun

AS Graph != Internet Topology

Growth of BGP Routes

Customers and Providers

The Peering Relationship

Peering Provides Shortcuts


BGP Operations (Simplified)

Four Types of BGP Messages

BGP Attributes

Attributes are Used to Select Best Routes

BGP Route Processing

Route Selection Summary

Tweak Tweak Tweak

ASPATH Attribute

Shorter Doesn’t Always Mean Shorter

Shedding Inbound Traffic with ASPATH Padding Hack

Padding May Not Shut Off All Traffic

COMMUNITY Attribute to the Rescue!

Hot Potato Routing: Go for the Closest Egress Point

Getting Burned by the Hot Potato

Cold Potato Routing with MEDs
(Multi-Exit Discriminator Attribute)


Policies Can Interact Strangely
(“Route Pinning” Example)

News at 11:00h

Slide 51

Separate dynamic and static semantics

An instance of the Stable Paths Problem (SPP)

A Solution to a Stable Paths Problem

An SPP may have multiple solutions

Multiple solutions can result in
“Route Triggering”


SURPRISE : Beware of Backup Policies


Distributed algorithms to solve SPP?

SPVP protocol

SPVP wanders around assignment space

Solving an SPP

Use 3-SAT…

Modeling assignment to variable X

SPP Solvability is NP-complete

 A sufficient condition for sanity

Dispute Digraph

Dispute Digraph (cont.)

Dispute Digraph Example


Addressing and ASN RFCs

Selected BGP RFCs

Titles of Some Recent Internet Drafts

Selected Bibliography on Routing

BGP Stability and Convergence

Analysis of Interdomain Routing

Internet Route Registries

Some BGP Theory