This preview shows page 1-2-3-4-5-6-7-51-52-53-54-55-56-57-58-102-103-104-105-106-107-108 out of 108 pages.
Routing Protocol ReviewInternet RoutingSlide 3Intra-domain Routing ProtocolsLink State Routing (OSPF): FloodingFlooding DetailsLink State Flooding ExampleSlide 8Slide 9Slide 10A Link State Routing AlgorithmDijsktra’s Algorithm (A “Greedy” Algorithm)Example: Dijkstra’s AlgorithmSlide 14Slide 15Slide 16Slide 17Slide 18Distance Vector Routing (RIP)Distance 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 ReverseSlide 32Slide 33Internet StructureIntra-DomainInter-DomainBGP: Path Vector ProtocolBGP Operations (Simplified)Four Types of BGP MessagesAttributes are Used to Select Best RoutesExample: Multiple AS PathsSlide 42Example Uses of MulticastThis approach does not scale…Use routers in distribution treeMulticast Service ModelSupporting Multicast on the InternetIP MulticastFailure of IP MulticastEnd System MulticastPotential Benefits Over IP MulticastConcerns with End System MulticastMulticast: Take-awaySlide 54Routing on a GraphLink State vs. Distance VectorRouting between ISPsNontransit vs. Transit ASesSelective TransitCustomers and ProvidersCustomers Don’t Always Need BGPCustomer-Provider HierarchyThe Peering RelationshipPeering Provides ShortcutsImplementing Customer/Provider and Peer/Peer relationshipsImport RoutesExport RoutesHow Can Routes be Colored? BGP Communities!IPv4 MulticastMulticast Implementation IssuesIP Multicast RoutingDistance Vector Multicast Routing Protocol (DVRMP)Reverse Path Flooding (RPF)ExampleReverse Path Broadcasting (RPB)Don’t Really Want to Flood!Truncated Reverse Path Broadcasting (TRPB)Distance Vector Multicast ScalingCore Based Trees (CBT)ExampleDisadvantagesWhy Need the Concept of AS or Domain?RIPSplit HorizonSplit Horizon with Poisoned ReverseCounting to InfinityPurpose of E-BGPPart II: I-BGP, Carrying Info within an ASI-BGPJoin I-BGP with IGP to Create Forwarding TableMultiple Routing Processes on a Single RouterSlide 92Inter-Domain RoutingBorder Gateway Protocol Part I: E-BGPExample AS GraphBGP IssuesMore IssuesAutonomous Systems (AS)AS Numbers (ASNs)ImplicationsShorter Doesn’t Always Mean ShorterMulticast Routing ApproachesSource Specific TreesSlide 104Shared TreeTerminologiesHow to Send to Multiple Receivers?Example: Internet Radio1Routing Protocol Review(some slides borrowed from Eugene Ng @ Rice Univ.)2Internet RoutingAS 73AS 9AS 5050AS 4554AS 101AS 3999Internet3Routing Protocol ReviewPart 1: Intra-domain routing4Intra-domain Routing Protocols•Two intra-domain routing protocols•Both try to achieve the “shortest path” forwarding•Quite commonly used•OSPF: Based on Link-State routing algorithm•RIP: Based on Distance-Vector routing algorithm•In Project 2, you implemented and played around with OSPF!5Link State Routing (OSPF): Flooding•Each node knows its connectivity and cost to a direct neighbor•Every node tells every other node this local connectivity/cost information–Via flooding•In the end, every node learns the complete topology of the network•E.g. A floods messageAEDCBF2213112535A connected to B cost 2A connected to D cost 1A connected to C cost 56Flooding Details•Each node periodically generates Link State Packet (LSP) contains–ID of node created LSP–List of direct neighbors and costs–Sequence number (64 bit, assume to never wrap around)–Time to live•Flood is reliable–Use acknowledgement and retransmission•Sequence number used to identify *newer* LSP–An older LSP is discarded–What if a router crash and sequence number reset to 0?•Receiving node flood LSP to all its neighbors except the neighbor where the LSP came from•LSP is also generated when a link’s state changes (failed or restored)7Link State Flooding Example67854312121013118Link State Flooding Example67854312121013119Link State Flooding Example678543121210131110Link State Flooding Example678543121210131111A 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•Repeat for all sourcesNotations•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 node 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 known12Dijsktra’s Algorithm (A “Greedy” 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; 13Example: 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) = ;…14Example: 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;15Example: 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;16Example: 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
View Full Document
Unlocking...