Shortest-Path Routing Reading: Sections 4.2 and 4.3.4Goals of Today’s LectureWhat is Routing?Forwarding vs. RoutingWhy Does Routing Matter?Shortest-Path RoutingShortest-Path ProblemDijkstra’s Shortest-Path AlgorithmDijsktra’s AlgorithmDijkstra’s Algorithm ExampleSlide 11Shortest-Path TreeLink-State RoutingDetecting Topology ChangesBroadcasting the Link StateSlide 16When to Initiate FloodingConvergenceTransient DisruptionsSlide 20Convergence DelayReducing Convergence DelayScaling Link-State RoutingBellman-Ford AlgorithmDistance Vector AlgorithmDistance Vector AlgorithmDistance Vector Example: Step 0Distance Vector Example: Step 2Distance Vector Example: Step 3Distance Vector: Link Cost ChangesSlide 31Distance Vector: Poison ReverseRouting Information Protocol (RIP)Comparison of LS and DV algorithmsConclusionsSlide 361Shortest-Path RoutingReading: Sections 4.2 and 4.3.4COS 461: Computer NetworksSpring 2007 (MW 1:30-2:50 in Friend 004)Jennifer RexfordTeaching Assistant: Ioannis Avramopouloshttp://www.cs.princeton.edu/courses/archive/spring07/cos461/2Goals of Today’s Lecture•Path selection–Minimum-hop and shortest-path routing–Dijkstra and Bellman-Ford algorithms•Topology change–Using beacons to detect topology changes–Propagating topology or path information•Routing protocols–Link state: Open Shortest Path First–Distance vector: Routing Information Protocol3What is Routing?•A famous quotation from RFC 791 “A name indicates what we seek.An address indicates where it is.A route indicates how we get there.” -- Jon Postel4Forwarding vs. Routing•Forwarding: data plane–Directing a data packet to an outgoing link–Individual router using a forwarding table•Routing: control plane–Computing paths the packets will follow–Routers talking amongst themselves–Individual router creating a forwarding table5Why Does Routing Matter?•End-to-end performance–Quality of the path affects user performance–Propagation delay, throughput, and packet loss•Use of network resources–Balance of the traffic over the routers and links–Avoiding congestion by directing traffic to lightly-loaded links•Transient disruptions during changes–Failures, maintenance, and load balancing–Limiting packet loss and delay during changes6Shortest-Path Routing•Path-selection model–Destination-based–Load-insensitive (e.g., static link weights)–Minimum hop count or sum of link weights 32211414537Shortest-Path Problem •Given: network topology with link costs–c(x,y): link cost from node x to node y–Infinity if x and y are not direct neighbors•Compute: least-cost paths to all nodes–From a given source u to all other nodes–p(v): predecessor node along path from source to v3221141453uvp(v)8Dijkstra’s Shortest-Path Algorithm•Iterative algorithm–After k iterations, know least-cost path to k nodes•S: nodes whose least-cost path definitively known–Initially, S = {u} where u is the source node–Add one node to S in each iteration•D(v): current cost of path from source to node v–Initially, D(v) = c(u,v) for all nodes v adjacent to u–… and D(v) = ∞ for all other nodes v–Continually update D(v) as shorter paths are learned9Dijsktra’s Algorithm1 Initialization: 2 S = {u} 3 for all nodes v 4 if v adjacent to u {5 D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in S with the smallest D(w)10 add w to S 11 update D(v) for all v adjacent to w and not in S: 12 D(v) = min{D(v), D(w) + c(w,v)} 13 until all nodes in S10Dijkstra’s Algorithm Example322114145332211414533221141453322114145311Dijkstra’s Algorithm Example322114145332211414533221141453322114145312Shortest-Path Tree•Shortest-path tree from u•Forwarding table at u3221141453uvwxyzstv (u,v)w (u,w)x(u,w)y (u,v)z(u,v)links (u,w)t(u,w)13Link-State Routing•Each router keeps track of its incident links–Whether the link is up or down–The cost on the link•Each router broadcasts the link state–To give every router a complete view of the graph•Each router runs Dijkstra’s algorithm–To compute the shortest paths–… and construct the forwarding table•Example protocols–Open Shortest Path First (OSPF)–Intermediate System – Intermediate System (IS-IS)14Detecting Topology Changes•Beaconing–Periodic “hello” messages in both directions–Detect a failure after a few missed “hellos”•Performance trade-offs–Detection speed–Overhead on link bandwidth and CPU–Likelihood of false detection“hello”15Broadcasting the Link State•Flooding–Node sends link-state information out its links–And then the next node sends out all of its links–… except the one where the information arrivedX AC B D(a)X AC B D(b)X AC B D(c)X AC B D(d)16Broadcasting the Link State•Reliable flooding–Ensure all nodes receive link-state information–… and that they use the latest version•Challenges–Packet loss–Out-of-order arrival•Solutions–Acknowledgments and retransmissions–Sequence numbers–Time-to-live for each packet17When to Initiate Flooding•Topology change–Link or node failure–Link or node recovery•Configuration change–Link cost change•Periodically–Refresh the link-state information–Typically (say) 30 minutes–Corrects for possible corruption of the data18Convergence•Getting consistent routing information to all nodes–E.g., all nodes having the same link-state database•Consistent forwarding after convergence–All nodes have the same link-state database–All nodes forward packets on shortest paths–The next router on the path forwards to the next hop322114145319Transient Disruptions•Detection delay–A node does not detect a failed link immediately–… and forwards data packets into a “blackhole”–Depends on timeout for detecting lost hellos322114145320Transient Disruptions•Inconsistent link-state database–Some routers know about failure before others–The shortest paths are no longer consistent–Can cause transient forwarding loops232114145332211414321Convergence Delay•Sources of convergence delay–Detection latency–Flooding of link-state information–Shortest-path computation–Creating the forwarding table•Performance during convergence period–Lost packets due to blackholes and TTL expiry–Looping packets consuming resources–Out-of-order packets reaching the destination•Very bad for VoIP, online gaming, and video22Reducing Convergence
View Full Document
Unlocking...