Intradomain Routing EECS 122: Lecture 10What is Routing?Datagram v/s Virtual CircuitMany Kinds of RoutingA Graph ModelWalksPathsRoutesRoutingRouting affects Flow ControlWhat is going on?The internet has many Administrative DomainsBorder RoutersHierarchical RoutingRouting Sub-FunctionsSlide 16Three types of Routing ProtocolsLink State ProtocolsFlooding Link State InformationExample NetworkSlide 21Slide 22Slide 23Real story…Some IssuesRoute Computation: DijkstraDijkstra: Shortest PathSlide 28Dijkstra: Forwarding TableDistance Vector ProtocolsSlide 31Slide 32Why does this compute shortest paths?Counting to InfinityBad News Travels Slowly…Slide 36Asynchronous Bellman FordOscillationsLink State vs. Distance Vector No clear winnerIntradomain RoutingEECS 122: Lecture 10Department of Electrical Engineering and Computer SciencesUniversity of CaliforniaBerkeleyFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 102What is Routing?Routing is the core function of a networkIt ensures thatinformation accepted for transfer at a source node is delivered to the correctset of destination nodes, at reasonable levels of performance.February 20, 2003Abhay Parekh: EECS 122 Lecture 103Datagram v/s Virtual CircuitDatagram routingEach packet to be forwarded independentlyVirtual CircuitEach packet from same o-d uses same routeMore state (pick the “right” granularity)QoS sensitive networks use VC’s and signalingFind a route that has the resources available for the connection. “Reserve” the resources before sending data packetsFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 104Many Kinds of RoutingDriven by…Destination setIP point-to-pointMulticastPhysical CharacteristicsOpticalmobile wirelessDiffusion (sensor networks)Interconnection network routingGeographic (wireless)Network FunctionP2PContent Distribution NetworksFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 105A Graph Model6785431212101311Nodes are Routers/HostsEdges are undirectedFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 106Walks6785431212101311A Walk from 1 to 11Cycle 4-8-7-5-4February 20, 2003Abhay Parekh: EECS 122 Lecture 107Paths6785431212101311Routes are PathsA Path is a Walk with no cyclesThere are 24 paths from1 to 11February 20, 2003Abhay Parekh: EECS 122 Lecture 108Routes678543121210131112232128111512212122722Routes are PathsA Path is a Walk with no cyclesThere are 24 paths from1 to 11Edges have weightsFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 109Routing678543121210131112232128111512212122722Routes are PathsA Path is a Walk with no cyclesThere are 24 paths from1 to 11Edges have weightsSelect the shortest path routeMany ways to do thisFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1010Routing affects Flow ControlAny function that “paces” the flow of bits into or within the network is flow controlExample: All links have capacity 1ADB1CADB1C1Nothing admittedFEFEFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1011What is going on?Routing and flow intimately relatedLink congestion metrics for routing depends on flow controlFlow control feedback delay depends on routingOptimizing them jointly is nice in theory but intractable in practice. Separating flow control and routing makes both extremely difficult to implement with high performanceFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1012The internet has many Administrative DomainsABC3121210131167854February 20, 2003Abhay Parekh: EECS 122 Lecture 1013Border Routers643213ABC2436137851121011OSPFRIPIGRPBGPFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1014Hierarchical RoutingABC6785431212101311643213B243613OSPFRIPIGRPBGPInterDomainInterDomainIntraDomainIntraDomainIntraDomainFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1015Routing Sub-FunctionsTopology Update: Characterize and maintain connectivityDiscover neighborsMeasure “distance” (one or more metric)DisseminateRoute Computation:Kind of path: Multicast, UnicastCentralized or Distributed AlgorithmPolicyHierarchySwitching: Forward the packets at each nodeFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1016Routing Sub-FunctionsTopology Update: Characterize and maintain connectivityDiscover neighborsMeasure “distance” (one or more metric)Disseminate Route Computation:Kind of path: Multicast, UnicastCentralized or Distributed AlgorithmPolicyHierarchySwitching: Forward the packets at each nodeFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1017Three types of Routing ProtocolsTopology changes can be detected by nearby nodesThese changes must be reflected in the routesMechanisms for disseminating informationLink State: Communicate the names and costs of neighbors. Each node maintains the entire topology. E.g. used in OSPFDistance Vector: Communicate current distance estimates of node to every other node. E.g. used in RIPPath Vector: Communicate current estimates of preferred paths from node to every other node. E.g. used in BGPFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1018Link State Protocols1. Every node learns the topology of the networkFlooding of Link State Packets (LSP)2. An efficient shortest path algorithm computes routes to every other node3. Node updates Forwarding TableFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1019Flooding Link State InformationEvery router sends Link State Packets (LSPs) to all of its neighborsLSPs arrive and wait in buffers to be “accepted”If node j receives a LSP from node k it compares the sequence numbers. If this is the most recent one from k, send to N(j)-{k}.This way each router can send its LSP to all other routersAge starts out at 7. At any router, value is decremented every 8 seconds. At 0 discard.As long as sequence don’t wrap this worksOtherwise things can get uglySourceSequence NumberAgeList of NeighborsFebruary 20, 2003Abhay Parekh: EECS 122 Lecture 1020Example Network6785431212101311February 20, 2003Abhay Parekh: EECS 122 Lecture 1021Example Network6785431212101311February 20, 2003Abhay Parekh: EECS 122 Lecture 1022Example Network6785431212101311February 20, 2003Abhay Parekh: EECS 122 Lecture 1023Example Network6785431212101311October 9, 2002Abhay K. Parekh: Topics in Routing24Real story…Sequence numbers from some router, s, wrapped aroundA < B < C < ARouter, t, has a buffer with LSPs from s of all three values in order: A, B, CStore and
View Full Document