EECS 122 Introduction to Computer Networks Link State and Distance Vector Routing Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Today s Lecture 7 2 17 18 19 6 10 11 Application Transport 14 15 16 7 8 9 21 22 23 25 Network IP Link Physical Katz Stoica F04 2 IP Header Vers IP versions HL Header length in 32bits Type Type of service Length size of datagram header data in bytes Identification fragment ID Fragment offset offset of current fragment x 8 bytes TTL number of network hops Protocol protocol type e g TCP UDP Source IP addresses Destination IP address Katz Stoica F04 3 What is Routing Routing is the core function of a network It ensures that information accepted for transfer at a source node is delivered to the correct set of destination nodes at reasonable levels of performance Katz Stoica F04 4 Internet Routing Internet organized as a two level hierarchy First level autonomous systems AS s AS region of network under a single administrative domain AS s run an intra domain routing protocols Distance Vector e g Routing Information Protocol RIP Link State e g Open Shortest Path First OSPF Between AS s runs inter domain routing protocols e g Border Gateway Routing BGP De facto standard today BGP 4 Katz Stoica F04 5 Example Interior router BGP router AS 1 AS 3 AS 2 Katz Stoica F04 6 Intra domain Routing Protocols Based on unreliable datagram delivery Distance vector Routing Information Protocol RIP based on Bellman Ford Each neighbor periodically exchange reachability information to its neighbors Minimal communication overhead but it takes long to converge i e in proportion to the maximum path length Link state Open Shortest Path First OSPF based on Dijkstra Each network periodically floods immediate reachability information to other routers Fast convergence but high communication and computation overhead Katz Stoica F04 7 Routing Goal determine a good path through the network from source to destination Good means usually the shortest path Network modeled as a graph A Routers nodes 1 Link edges Edge cost delay congestion level 2 5 B 2 D 3 C 3 1 5 F 1 E Katz Stoica F04 2 8 Outline Link State Distance Vector Katz Stoica F04 9 A Link State Routing Algorithm Dijkstra s algorithm Net topology link costs known to all nodes Accomplished via link state flooding All nodes have same info Compute least cost paths from one node source to all other nodes Iterative after k iterations know least cost paths to k closest destinations Notations c i j link cost from node i to j cost infinite if not direct neighbors D v current value of cost of path from source to destination v p v predecessor node along path from source to v that is next to v S set of nodes whose least cost path definitively known Katz Stoica F04 10 Link State Flooding Example 5 4 7 8 6 11 2 1 10 3 13 12 Katz Stoica F04 11 Link State Flooding Example 5 4 7 8 6 11 2 1 10 3 13 12 Katz Stoica F04 12 Link State Flooding Example 5 4 7 8 6 11 2 1 10 3 13 12 Katz Stoica F04 13 Link State Flooding Example 5 4 7 8 6 11 2 1 10 3 13 12 Katz Stoica F04 14 Dijsktra s Algorithm 1 Initialization 2 S A 3 for all nodes v 4 if v adjacent to A 5 then D v c A v 6 else D v 7 8 Loop 9 find w not in S such that D w is a minimum 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 new cost to v is either old cost to v or known shortest path cost to w plus cost from w to v 13 until all nodes in S Katz Stoica F04 15 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 start S A D B p B D C p C D D p D D E p E D F p F 2 A 1 A 5 A 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 1 Initialization 2 S A 3 for all nodes v 4 if v adjacent to A 5 then D v c A v 6 else D v Katz Stoica F04 16 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D D E p E D F p F 2 A 1 A 5 A 4 D 2 D start S A AD 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 8 Loop 9 find w not in S s t D w is a minimum 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 S Katz Stoica F04 17 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D D E p E D F p F 1 A 2 A 5 A 4 D 2 D 3 E 4 E start S A AD ADE 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 8 Loop 9 find w not in S s t D w is a minimum 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 S Katz Stoica F04 18 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D D E p E D F p F 2 A 1 A 5 A 4 D 2 D 3 E 4 E start S A AD ADE ADEB 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 8 Loop 9 find w not in S s t D w is a minimum 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 S Katz Stoica F04 19 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D D E p E D F p F 2 A 1 A 5 A 4 D 2 D 3 E 4 E start S A AD ADE ADEB ADEBC 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 …
View Full Document
Unlocking...