4 - Routing Flashcards
Examples of an Autonomous System
Internet service provider, content provider, campus network
intra-domain routing
process by which traffic is routed inside any single autonomous system
inter-domain routing
process of routing traffic between autonomous systems
A topology inside of an autonomous system consist of:
nodes and edges.
Points of Presence (PoP)
nodes inside of an autonomous system
PoP is typically located in a dense population center so that:
It can be close to the PoPs of other providers for easier interconnection and also close to other customers for cheaper back haul to customers that may be purchasing connectivity from this particular AS
PoPs are constrained by:
fiber paths
Routing is the process by which:
nodes discover where to forward traffic so that it reaches a certain node.
2 types of intra-domain routing
distance vector and link state
Distance Vector routing
Each node sends multiple distance vectors to each of its neighbors, which amounts to copies of its own routing table.
routers then compute costs to each destination in the topo, based on shortest available path.
based on bellman-ford algorithm.
Routing Information Protocol (RIP)
a distance vector routing protocol.
edges have unit cost
infinite = 16
table refresh: 30 seconds or when updates occur.
Tell all neighbors except for one that caused update (“split horizon”)
Downsides of Routing Information Protocol (RIP)
- slow convergence
2. count to infinity
Link State Routing
used in most networks
distribute network map
each node performs shortest path (SPF) computation
Iniitially adds costs of immediate neighbors, flood costs to neighbors
Dijkstras algorithm
2 common link state routing protocols and which one is more commonly used?
- Open Shortest Paths First (OSPF)
2. Intermediate System - Intermediate System (IS-IS) (used more)
Problem with link state routing
scale
The complexity of a link state routing protocol grows as n cubed where n is the # of nodes in the network
How to cope with scale (related to link state routing)
introduce hierarchy
OSPF: Areas
IS-IS: Levels
Shortest path computed within area or stitching together the shortest path to the area zero backbone router, and the shortest path across area zero, followed by another intra area shortest path
Route Advertisements
Each AS advertises reachability to some destination by sending these (in interdomain routing).
used Border Gateway Protocol (BGP)
Route advertisement contains these 3 things (BGP route attributes)
Destination IP, Next Hop IP, AS path
Last number on AS path is known as the “origin AS”, which originated the announcement
eBGP (external Border Gateway Protocol)
Consisting of route advertisements solely between border routers of adjacent autonomous systems
Responsible for transmitting routing information between border routers of adjacent ASes about external destinations
iBGP (internal border gateway protocol)
The protocol that is used to transmit routes inside an autonomous system for external destinations
Responsible for disseminating BGP route advertisements about external destinations to routers inside any particular AS
IGP (intra-domain routing protocol)
routes inside an AS to internal destinations
iBGP (internal-gateway border protocol)
routes inside an AS to external destinations
BGP Route Selection Process
- Prefer higher “local preference”
- Shortest AS path length
- Multi-exit discriminator (MED) (lower med values preferred and only comparable among routes from the same AS)
- Shortest IGP path (“hot potato” routing)
- Tiebreak -> “most stable”, lowest router ID
