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)
