Intradomain Routing EECS 122 Lecture 10 Department of Electrical Engineering and Computer Sciences University of California Berkeley 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 February 20 2003 Abhay Parekh EECS 122 Lecture 10 2 Datagram v s Virtual Circuit Datagram routing Virtual Circuit Each packet to be forwarded independently Each packet from same o d uses same route More state pick the right granularity QoS sensitive networks use VC s and signaling Find a route that has the resources available for the connection Reserve the resources before sending data packets February 20 2003 Abhay Parekh EECS 122 Lecture 10 3 Many Kinds of Routing Driven by Destination set Physical Characteristics IP point to point Multicast Optical mobile wireless Diffusion sensor networks Interconnection network routing Geographic wireless Network Function P2P Content Distribution Networks February 20 2003 Abhay Parekh EECS 122 Lecture 10 4 A Graph Model 5 7 4 8 Nodes are Routers Hosts Edges are undirected 6 11 2 1 10 3 February 20 2003 13 Abhay Parekh EECS 122 Lecture 10 12 5 Walks A Walk from 1 to 11 5 4 7 Cycle 4 8 7 5 4 8 6 11 2 1 10 3 February 20 2003 13 Abhay Parekh EECS 122 Lecture 10 12 6 Paths A Path is a Walk with no cycles Routes are Paths 5 There are 24 paths from 1 to 11 4 7 8 6 11 2 1 10 3 February 20 2003 13 Abhay Parekh EECS 122 Lecture 10 12 7 Routes A Path is a Walk with no cycles Routes are Paths 8 4 There are 24 paths from 1 to 11 15 2 3 1 2 7 8 Edges have weights 2 6 2 2 12 7 11 1 13 12 February 20 2003 11 10 2 3 2 5 1 12 2 12 2 Abhay Parekh EECS 122 Lecture 10 8 Routing A Path is a Walk with no cycles Routes are Paths 8 4 There are 24 paths from 1 to 11 15 2 3 1 2 7 8 Edges have weights 2 Select the shortest path route Many ways to do this 6 2 2 12 7 11 1 13 12 February 20 2003 11 10 2 3 2 5 1 12 2 12 2 Abhay Parekh EECS 122 Lecture 10 9 Routing affects Flow Control Any function that paces the flow of bits into or within the network is flow control Example All links have capacity 1 1 A B E C F D February 20 2003 1 1 A B E Nothing admitted C F D Abhay Parekh EECS 122 Lecture 10 10 What is going on Routing and flow intimately related Link congestion metrics for routing depends on flow control Flow control feedback delay depends on routing Optimizing them jointly is nice in theory but intractable in practice Separating flow control and routing makes both extremely difficult to implement with high performance February 20 2003 Abhay Parekh EECS 122 Lecture 10 11 The internet has many Administrative Domains B 5 4 7 8 6 11 2 10 3 1 13 C A February 20 2003 12 Abhay Parekh EECS 122 Lecture 10 12 Border Routers B 5 44 7 8 RIP 66 11 2 2 10 OSPF BGP 1 33 13 13 C IGRP A February 20 2003 12 Abhay Parekh EECS 122 Lecture 10 13 Hierarchical Routing 44 BGP B 66 B 5 22 IntraDomain 4 InterDomain InterDomain 3 3 7 8 6 RIP 13 13 11 2 10 OSPF IntraDomain 3 1 IntraDomain 13 IGRP C A February 20 2003 12 Abhay Parekh EECS 122 Lecture 10 14 Routing Sub Functions Topology Update Characterize and maintain connectivity Route Computation Discover neighbors Measure distance one or more metric Disseminate Kind of path Multicast Unicast Centralized or Distributed Algorithm Policy Hierarchy Switching Forward the packets at each node February 20 2003 Abhay Parekh EECS 122 Lecture 10 15 Routing Sub Functions Topology Update Characterize and maintain connectivity Route Computation Discover neighbors Measure distance one or more metric Disseminate Kind of path Multicast Unicast Centralized or Distributed Algorithm Policy Hierarchy Switching Forward the packets at each node February 20 2003 Abhay Parekh EECS 122 Lecture 10 16 Three types of Routing Protocols Topology changes can be detected by nearby nodes These changes must be reflected in the routes Mechanisms for disseminating information Link State Communicate the names and costs of neighbors Each node maintains the entire topology E g used in OSPF Distance Vector Communicate current distance estimates of node to every other node E g used in RIP Path Vector Communicate current estimates of preferred paths from node to every other node E g used in BGP February 20 2003 Abhay Parekh EECS 122 Lecture 10 17 Link State Protocols Every node learns the topology of the network 1 2 3 Flooding of Link State Packets LSP An efficient shortest path algorithm computes routes to every other node Node updates Forwarding Table February 20 2003 Abhay Parekh EECS 122 Lecture 10 18 Flooding Link State Information Source Sequence Number Age List of Neighbors Every router sends Link State Packets LSPs to all of its neighbors LSPs 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 routers Age starts out at 7 At any router value is decremented every 8 seconds At 0 discard As long as sequence don t wrap this works Otherwise things can get ugly February 20 2003 Abhay Parekh EECS 122 Lecture 10 19 Example Network 5 4 7 8 6 11 2 1 10 3 February 20 2003 13 Abhay Parekh EECS 122 Lecture 10 12 20 Example Network 5 4 7 8 6 11 2 1 10 3 February 20 2003 13 Abhay Parekh EECS 122 Lecture 10 12 21 Example Network 5 4 7 8 6 11 2 1 10 3 February 20 2003 13 Abhay Parekh EECS 122 Lecture 10 12 22 Example Network 5 4 7 8 6 11 2 1 10 3 February 20 2003 13 Abhay Parekh EECS 122 Lecture 10 12 23 Real story Sequence numbers from some router s wrapped around A B C A Router t has a buffer with LSPs from s of all three values in order A B C Store and flood A Replace A with B and flood B Replace B with C and flood C Router u receives the LSPs in order ABC and goes through the same cycle and sends to v The entire Arpanet was sending these LSPs and crashed LSPs did not wait in buffers long enough to age October 9 2002 Abhay K Parekh Topics in Routin g 24 Some Issues What happens if some routers are much faster at transmitting LSPs What happens if sequence numbers wrap What happens when a partitioned …
View Full Document
Unlocking...