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 topologyShortest-Path RoutingShortest-Path ProblemDijkstra’s Shortest-Path AlgorithmDijsktra’s AlgorithmDijkstra’s Algorithm ExampleSlide 19Shortest-Path TreeLearning the Topology by the routers talk amongst themselvesLink-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 RoutingConclusionsLink-State RoutingReading: Sections 4.2 and 4.3.4COS 461: Computer NetworksSpring 2009 (MW 1:30-2:50 in COS 105)Michael FreedmanTeaching Assistants: Wyatt Lloyd and Jeff Terracehttp://www.cs.princeton.edu/courses/archive/spring09/cos461/1Goals 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 First2What 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 Postel3Routing 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 table4Data and Control Planes5SwitchingFabricProcessorLine cardLine cardLine cardLine cardLine cardLine carddata planecontrol planeRouter Physical Layout6Juniper T seriesCisco 12000SwitchLinecardsLine 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–Measurement7to/from linkto/from switchlookupReceiveTransmitSwitching 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 cells8Packet Switching9R1Link 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”Router 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 cards10Where 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 in11Computing 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 z1212.34.158.0/24Interface along the path to z uzRouter z that can reach destinationComputing the Shortest Pathsassuming you already knowthe topology13Shortest-Path Routing•Path-selection model–Destination-based–Load-insensitive (e.g., static link weights)–Minimum hop count or sum of link weights 143221141453Shortest-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 v153221141453uvp(v)Dijkstra’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 learned16Dijsktra’s Algorithm171 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 SDijkstra’s Algorithm Example183221141453322114145332211414533221141453Dijkstra’s Algorithm Example193221141453322114145332211414533221141453Shortest-Path Tree•Shortest-path tree from u•Forwarding table at u203221141453uvwxyzstv (u,v)w (u,w)x(u,w)y (u,v)z(u,v)links (u,w)t(u,w)Learning the Topologyby the routers talk amongst themselves21Link-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)22Detecting Topology Changes•Beaconing–Periodic “hello” messages in both directions–Detect a failure after a few missed “hellos”•Performance
View Full Document
Unlocking...