4-Routing Flashcards
ISP, Content Provider, Campus network or any independently operated network
Autonomous Systems (AS) or ASes
Routing within an AS
Intradomain Routing
Routing traffic between ASes
Interdomain Routing
A high-performance backbone network created by the Internet2 community in the late 1990s. In 2007 it was retired and the upgraded network became known as the “Internet2 Network”.
Abeline network (A Single AS research network in US)
There are 2 types of Intradomain routing
1) Distance Vector
2) Link State
Distance Vector Routing
1) Each node sends multiple distance vectors to each of its neighbors (copies of own routing table)
2) Routers compute costs to each destination based on shortest available path
Distance Vector Routing is based on
Bellman-Ford algorithm
dx(y) = minv(c(x1v)+dv(y))
What is the solutiopn to the “Count to infinity problem?”
Poison Reverse
- Circa 1982
- edges have unit cost
- “infinity” = 16
- table refresh: 30 seconds (or when updates occur)
Routing Information Protocol (RIP)
More on RIP
When an entry changes, it sends the copy of that update to all of it’s neighbors except the one that caused the update (also known as the “split Horizon” rule)
Alternative to RIP
Link-State routing
Link-State Routing (scale is an issue though)
- Each node distributes a network map to every other node in the network
- Each node performs a shortest path computation between itself and all other nodes in the network
Shortest path computation
Dijkstra algorithm
D(v) = min(c(v,w)*D(w), D(v))
2 common link-state routing protocols
1) Open Shortest Paths First (OSPF) ->Areas
2) Intermediate System- Intermediate System (IS-IS) -large ISP and most commonly used in large transit networks today ->Levels
Coping with Scale
Hierarchy
ASes advertise reach-ability to some destination by sending announcements or route advertisements. the protocol used to advertise these announcements is called
Border Gateway Protocol (BGP)
Sequence of AS numbers that describe the route to the destination (Sequence of ASes that the route traversed to reach the recipient AS)
AS Path (1 BGP route attributes)
The last AS
The origin AS
Responsible for transmitting routing information between border routers of adjacent ASes about external destinations
external BGP or eBGP
Responsible for disseminating BGP route advertisements about external destinations to routers inside any particular AS
internal BGP or iBGP
Routes inside an AS to internal destinations
Intradomain routing protocol or IGP
BGP Route Selection Process
1) Prefer a route with the higher “local preference” value
2) Shortest AS path length
3) Multi-exit discriminator (MED)
- Lower values
- Only comparable among routes from same AS
4) Shortest IGP path (“hot potato” routing)
5) Tiebreak -> “most stable” or advertised the longest -> lowest router ID typically
Local Preference (Local Pref)
Allows operator to configure the router to assign different preference values to each of the routes that it learns
Local Preference (Local Pref)
Sometimes used to control OUTBOUND traffic
Local Preference (Local Pref)
Extremely useful for configuring Primary and Backup route
Tag on a route
“Community”
Multiple Exit Discriminator (MED)
To override “hot potato” routing behavior - ASes may use MED values (remember NY and SF example)
Interdomain Routing Business Models
3 types and their rankings:
1) Customer, > 2) Peering (settlement free peering) , > 3) Provider
Money is flowing in the direction of the provider
Interdomain Routing Business Models
From Customer: Everyone
Provider: only Customers
Peer: other customers
Interdomain Routing Can Oscillate
BGP corrective property called “Saftey” by Griffin
But regional and paid peering can violate - so BGP is not guaranteed to be stable… due to Oscillation.
