Routing Flashcards
Global routing algorithm
all routers have complete
topology, link cost info
• “link state” algorithms
Decentralized router algorithm
-router knows physically-connected
neighbors, and link costs
to the neighbors
-• iterative process of
computation, exchange of info
with neighbors
• “distance vector” algorithms
static routing algorithm
routes change slowly over time
dynamic routing algorithm
routes change more quickly over time
-periodic update
entry (Y, p, c) in the vector of router X means:
‘X’ can reach ‘Y’ via (source) port ‘p’ with cost ‘c’
‘A -1 0’ means ‘A can reach itself at cost 0’
distance vector routing (4)
each router maintains a vector of distances to other routers.
initially, it only knows itself
Periodically sends its distance vector to neighboring routers
-distributed implementation of a shortest-path computation algorithm (Bellman-Ford algorithm)
problems with Distance vector Routing
- slow convergence
- after a change in network topology (ie failures of links), it takes a while for routing tables to stabilize
-transient (not permenant) routing loops
link state routing (6)
-using a special purpose broadcast algorithm, every router periodically broadcasts to all other routers a list of its local links
(LSA) - link state advertisement
- every router has complete map of whole network
- uses shortest path algo to find shortest path to other routers
- when detecting failure/ recovery/addition of its local links, a router broadcasts a new LSA
- and all routers re-compute shortest paths
-all LSA forwarding steps are reliable, using stop-and-wait
disadvantages of link state routing (4)
limitations in scale b/c of maintaining entire network map at each router,
periodic broadcasts from each router,
shortest path computations at each router
-higher complexity than RIP
advantage of link state routing
fast convergence after network changes
Path Vector routing
- each router maintains a vector of complete paths to all other routers
- used by Border Gateway Protocol (BGP) of Internet
advantage of path vector routing
prevents routing loops (by inspecting paths)
enables policy routin
policy routing
selection of paths based on non-technical issues (like routers belonging to rival ISPs)
-by scanning a path before accepting it
Autonomous systems (AS)
-Internet is divided into these
Each AS comprises the routers and networks governed by a single administrator (like BU, or Time warner cable)
routing occurs at 2 levels:
Intra-AS routing (internal gateway routing – aka Interior Gateway Protocols (IGP)) (i.e. RIP, OSPF and IGRP) - destination is inside source AS
Inter-AS routing (external gateway routing) (.e. BGP)
inside each AS, ____ - AS routing is used
Intra-AS routing
Border Gateway Protocol (BGP)
-standard for Inter-AS routing
Path Vector protocol
-routes to networks (ASs), not individual hosts
Routing Information Bases (RIB)
-BGP messages exchanged using TCP
When router notices the failure of port p, it changes in its vector all the entries (Y, p, c) to
(Y, p, infinity)
RIP (routing information protocol) (4)
- UDP
- distance vectors (advertisement) exchanged b/t neighbors every 30 secs - each one lists 25 dest networks within Autonomous System (AS) (in UDP packets)
- no ad after 180 secs –> dead , new ads sent (good for spreading news of link failure)
- tables managed by daemons (application-level process)
Why different Intra- and Inter-AS routing?
Inter-AS: admin wants to control who it routes through (no competitors)
Intra-AS: single admin, dont need to worry about that. Can focus on performance
