Link-State Routing Reading: Sections 4.2 and 4.3.4Goals of Today’s LectureWhat is Routing?Routing vs. ForwardingData and Control PlanesRouter Physical LayoutLine Cards (Interface Cards, Adaptors)Switching FabricPacket SwitchingRouter ProcessorWhere do Forwarding Tables Come From?Computing Paths Between RoutersComputing the Shortest Paths (assuming you already know the topology)Shortest-Path RoutingShortest-Path ProblemDijkstra’s Shortest-Path AlgorithmDijsktra’s AlgorithmDijkstra’s Algorithm ExampleSlide 19Shortest-Path TreeLearning the Topology (by the routers talk amongst themselves)Link-State RoutingDetecting Topology ChangesBroadcasting the Link StateSlide 25When to Initiate FloodingWhen the Routers Disagree (during transient periods)ConvergenceTransient DisruptionsSlide 30Convergence DelayReducing Convergence DelayScaling Link-State RoutingConclusions1Link-State RoutingReading: Sections 4.2 and 4.3.4COS 461: Computer NetworksSpring 2008 (MW 1:30-2:50 in COS 105)Jennifer RexfordTeaching Assistants: Sunghwan Ihm and Yaping Zhuhttp://www.cs.princeton.edu/courses/archive/spring08/cos461/2Goals of Today’s Lecture•Inside a router–Control plane: routing protocols–Data plane: packet forwarding•Path selection–Minimum-hop and shortest-path routing–Dijkstra’s algorithm•Topology change–Using beacons to detect topology changes–Propagating topology information•Routing protocol: Open Shortest Path First3What is Routing?•A famous quotation from RFC 791 “A name indicates what we seek.An address indicates where it is.A route indicates how we get there.” -- Jon Postel4Routing vs. Forwarding•Routing: control plane–Computing paths the packets will follow–Routers talking amongst themselves–Individual router creating a forwarding table•Forwarding: data plane–Directing a data packet to an outgoing link–Individual router using a forwarding table5Data and Control PlanesSwitchingFabricProcessorLine cardLine cardLine cardLine cardLine cardLine carddata planecontrol plane6Router Physical LayoutJuniper T seriesCisco 12000SwitchLinecards7Line Cards (Interface Cards, Adaptors)•Interfacing –Physical link–Switching fabric•Packet handling–Packet forwarding–Decrement time-to-live–Buffer management–Link scheduling–Packet filtering–Rate limiting–Packet marking–Measurementto/from linkto/from switchlookupReceiveTransmit8Switching Fabric•Deliver packet inside the router–From incoming interface to outgoing interface–A small network in and of itself•Must operate very quickly–Multiple packets going to same outgoing interface–Switch scheduling to match inputs to outputs•Implementation techniques–Bus, crossbar, interconnection network, …–Running at a faster speed (e.g., 2X) than links–Dividing variable-length packets into fixed-size cells9Packet SwitchingR1Link 1Link 2Link 3Link 4Link 1, ingress Link 1, egressLink 2, ingress Link 2, egressLink 3, ingress Link 3, egressLink 4, ingress Link 4, egressChooseEgressChooseEgressChooseEgressChooseEgress“4”“4”10Router Processor•So-called “Loopback” interface–IP address of the CPU on the router•Interface to network administrators–Command-line interface for configuration–Transmission of measurement statistics •Handling of special data packets–Packets with IP options enabled–Packets with expired Time-To-Live field•Control-plane software–Implementation of the routing protocols–Creation of forwarding table for the line cards11Where do Forwarding Tables Come From?•Routers have forwarding tables–Map IP prefix to outgoing link(s)•Entries can be statically configured–E.g., “map 12.34.158.0/24 to Serial0/0.1”•But, this doesn’t adapt –To failures–To new equipment–To the need to balance load•That is where routing protocols come in12Computing Paths Between Routers•Routers need to know two things–Which router to use to reach a destination prefix–Which outgoing interface to use to reach that router•Today’s class: just how routers reach each other–How u knows how to forward packets toward z12.34.158.0/24Interface along the path to z uzRouter z that can reach destination13Computing the Shortest Paths(assuming you already know the topology)14Shortest-Path Routing•Path-selection model–Destination-based–Load-insensitive (e.g., static link weights)–Minimum hop count or sum of link weights 322114145315Shortest-Path Problem •Given: network topology with link costs–c(x,y): link cost from node x to node y–Infinity if x and y are not direct neighbors•Compute: least-cost paths to all nodes–From a given source u to all other nodes–p(v): predecessor node along path from source to v3221141453uvp(v)16Dijkstra’s Shortest-Path Algorithm•Iterative algorithm–After k iterations, know least-cost path to k nodes•S: nodes whose least-cost path definitively known–Initially, S = {u} where u is the source node–Add one node to S in each iteration•D(v): current cost of path from source to node v–Initially, D(v) = c(u,v) for all nodes v adjacent to u–… and D(v) = ∞ for all other nodes v–Continually update D(v) as shorter paths are learned17Dijsktra’s Algorithm1 Initialization: 2 S = {u} 3 for all nodes v 4 if (v is adjacent to u)5 D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in S with the smallest D(w)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 S18Dijkstra’s Algorithm Example322114145332211414533221141453322114145319Dijkstra’s Algorithm Example322114145332211414533221141453322114145320Shortest-Path Tree•Shortest-path tree from u•Forwarding table at u3221141453uvwxyzstv (u,v)w (u,w)x(u,w)y (u,v)z(u,v)links (u,w)t(u,w)21Learning the Topology(by the routers talk amongst themselves)22Link-State Routing•Each router keeps track of its incident links–Whether the link is up or down–The cost on the link•Each router broadcasts the link state–To give every router a complete view of the graph•Each router runs Dijkstra’s algorithm–To compute the shortest paths–… and construct the forwarding table•Example protocols–Open Shortest Path First (OSPF)–Intermediate System – Intermediate System (IS-IS)23Detecting Topology Changes•Beaconing–Periodic “hello” messages in both directions–Detect a failure after a few missed “hellos”•Performance
View Full Document
Unlocking...