EECS 122: Introduction to Computer Networks Link State and Distance Vector RoutingToday’s Lecture: 7IP HeaderWhat is Routing?Internet RoutingExampleIntra-domain Routing ProtocolsRoutingOutlineA Link State Routing AlgorithmLink State Flooding ExampleSlide 12Slide 13Slide 14Dijsktra’s AlgorithmExample: Dijkstra’s AlgorithmSlide 17Slide 18Slide 19Slide 20Slide 21ComplexityOscillationsSlide 24Distance Vector Routing AlgorithmDistance Vector RoutingDistance Vector Algorithm (cont’d)Example: Distance Vector AlgorithmExample: 1st Iteration (C A)Example: 1st Iteration (BA, CA)Example: End of 1st IterationExample: End of 2nd IterationExample: End of 3rd IterationDistance Vector: Link Cost ChangesDistance Vector: Count to Infinity ProblemDistance Vector: Poisoned ReverseLink State vs. Distance VectorKatz, Stoica F04EECS 122: Introduction to Computer Networks Link State and Distance Vector RoutingComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04Today’s Lecture: 7Network (IP)ApplicationTransportLinkPhysical27, 8, 910, 1117, 18, 1914, 15, 1621, 22, 232563Katz, Stoica F04IP HeaderVers: IP versionsHL: Header length (in 32-bits)Type: Type of serviceLength: size of datagram (header + data; in bytes) Identification: fragment IDFragment offset: offset of current fragment (x 8 bytes)TTL: number of network hopsProtocol: protocol type (e.g., TCP, UDP)Source IP addressesDestination IP address4Katz, Stoica F04What is Routing?Routing is the core function of a networkIt ensures that•information accepted for transfer •at a source node •is delivered to the correct•set of destination nodes, •at reasonable levels of performance.5Katz, Stoica F04Internet RoutingInternet organized as a two level hierarchyFirst level – autonomous systems (AS’s)-AS – region of network under a single administrative domainAS’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-46Katz, Stoica F04ExampleAS-1AS-2AS-3Interior routerBGP router7Katz, Stoica F04Intra-domain Routing ProtocolsBased on unreliable datagram deliveryDistance 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 lengthLink 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 overhead8Katz, Stoica F04RoutingGoal: determine a “good” path through the network from source to destination-Good means usually the shortest pathNetwork modeled as a graph-Routers nodes-Link edges•Edge cost: delay, congestion level,…AEDCBF22131125359Katz, Stoica F04OutlineLink StateDistance Vector10Katz, Stoica F04A Link State Routing Algorithm Dijkstra’s algorithmNet topology, link costs known to all nodes-Accomplished via “link state flooding” -All nodes have same infoCompute least cost paths from one node (‘source”) to all other nodesIterative: after k iterations, know least cost paths to k closest destinationsNotationsc(i,j): link cost from node i to j; cost infinite if not direct neighborsD(v): current value of cost of path from source to destination vp(v): predecessor node along path from source to v, that is next to vS: set of nodes whose least cost path definitively known11Katz, Stoica F04Link State Flooding Example678543121210131112Katz, Stoica F04Link State Flooding Example678543121210131113Katz, Stoica F04Link State Flooding Example678543121210131114Katz, Stoica F04Link State Flooding Example678543121210131115Katz, Stoica F04Dijsktra’s Algorithm1 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; 16Katz, Stoica F04Example: Dijkstra’s AlgorithmStep012345start SAD(B),p(B)2,AD(C),p(C)5,AD(D),p(D)1,AD(E),p(E)D(F),p(F)AEDCBF22131125351 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) = ;…17Katz, Stoica F04Example: Dijkstra’s AlgorithmStep012345start SAADD(B),p(B)2,AD(C),p(C)5,A4,DD(D),p(D)1,AD(E),p(E)2,DD(F),p(F)AEDCBF2213112535…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;18Katz, Stoica F04Example: Dijkstra’s AlgorithmStep012345start SAADADED(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,EAEDCBF2213112535…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;19Katz, Stoica F04Example: Dijkstra’s AlgorithmStep012345start SAADADEADEBD(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,EAEDCBF2213112535…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;20Katz, Stoica F04Example: Dijkstra’s AlgorithmStep012345start SAADADEADEBADEBCD(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,EAEDCBF2213112535…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;21Katz, Stoica F04Example: Dijkstra’s AlgorithmStep012345start SAADADEADEBADEBCADEBCFD(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,EAEDCBF2213112535…8 Loop 9
View Full Document
Unlocking...