2/16/2008115-441 Computer NetworkingLecture 11 – Routing1Peter SteenkisteDepartments of Computer Science andElectrical and Computer Engineering15-441 Networking, Spring 2008http://www.cs.cmu.edu/~dga/15-441/S08Outlinez Link Statez OSPF22z IP Multicast Service Basicsz Host/Router Interactionz MOSPF/DVMRPLink State Protocol Conceptz Every node gets complete copy of graph»Every node “floods” network with data about its outgoing links33z Every node computes routes to every other node»Using single-source, shortest-path algorithmz Process performed whenever needed»When connections die / reappearSending Link States by Floodingz X Wants to Send Information» Sends on all outgoing linksz When Node Y Receives X AC B D(a)X AC B D(b)44Information from Z» Send on all links other than ZX AC B D(c)X AC B D(d)z Need to stop propagation» Use sequence number to recognize and discard old packets» Also: limit hop count or time in the networkDijkstra’s Algorithmz Given»Graph with source node s and edge costs c(u,v)55»Determine least cost path from s to every node vz Shortest Path First Algorithm»Traverse graph in order of least cost from sourceDijkstra’s Algorithm: ConceptAEFCD23631123SourceNode0253∞∞Current Path Costs66zNode Sets» Done–Already have least cost path to it» Horizon:–Reachable in 1 hop from node in Done» Unseen:–Cannot reach directly from node in Donez Label» d(v) = path cost– From s to vz Path» Keep track of last link in pathBDoneHorizonUnseen2/16/20082Dijkstra’s Algorithm: InitiallyAEFCD23631123SourceNode0∞∞∞∞∞Current Path Costs77z No nodes donez Source in horizonBDoneHorizonUnseenDijkstra’s Algorithm: InitiallyAEFCD23631123SourceNode0263∞∞Current Path Costs88z d(v) to node A shown in red»Only consider links from done nodes BDoneHorizonUnseenDijkstra’s AlgorithmAEFCD2361123SourceNd023∞∞Current Path Costs6599z Select node v in horizon with minimum d(v)z Add link used to add node to shortest path treez Update d(v) informationAB3NodeDoneHorizonUnseen3Dijkstra’s AlgorithmC2361123SourceHorizon0253∞∞Current Path CostsFDE1010z Repeat…A33NodeDoneUnseen3BDDijkstra’s Algorithm2631123SourceNodeUnseen0243∞6Current Path CostsAC3DEF1111z Update d(v) values» Can cause addition of new nodes to horizon3NodeDoneHorizonABDijkstra’s Algorithm2631123SourceNode024356AC3DEF1212z Final tree shown in green3NodeAB2/16/20083Link State Characteristicsz With consistent LSDBs*, all nodes compute consistent loop-free pathsCan still have transientABC1311313zCan still have transient loops» Routers may update database at slightly different timesD52Packet from CÆAmay loop around BDCif B knows about failureand C & D do notOSPF Routing Protocolz Open»Open standard created by IETFz Shortest-path first1414»Another name for Dijkstra’s algorithmz More prevalent than RIPOSPF Reliable Floodingz Transmit link state advertisements» Originating router– Typically, minimum IP address for router» Link ID1515–ID of router at other end of link» Metric– Cost of link» Link-state age– Incremented each second– Packet expires when reaches 3600» Sequence number– Incremented each time sending new link informationOSPF Flooding Operationz Node X Receives LSA from Node Y» With Sequence Number q» Looks for entry with same origin/link IDz Cases»No entry present1616»No entry present– Add entry, propagate to all neighbors other than Y» Entry present with sequence number p < q– Update entry, propagate to all neighbors other than Y» Entry present with sequence number p > q– Send entry back to Y– To tell Y that it has out-of-date information» Entry present with sequence number p = q– Ignore itFlooding Issuesz When should it be performed» Periodically» When status of link changes– Detected by connected node&1717z What happens when router goes down & back up» Sequence number reset to 0– Other routers may have entries with higher sequence numbers» Router will send out LSAs with number 0» Will get back LSAs with last valid sequence number p» Router sets sequence number to p+1 & resendsAdoption of OSPFz RIP viewed as outmoded»Good when networks small and routers had limited memory & 1818computational powerz OSPF Advantages»Fast convergence when configuration changes2/16/20084Comparison of LS and DV AlgorithmsMessage complexityz LS: with n nodes, E links, O(nE) messagesz DV: exchange between neighbors onlySpace requirements:» LS maintains entire topology» DV maintains only neighbor state1919Speed of Convergencez LS: Complex computation» But…can forward before computation» may have oscillationsz DV: convergence time varies» may be routing loops» count-to-infinity problem» (faster with triggered updates)Robustness: what happens if router malfunctions?LS:• node can advertise incorrect link cost• each node computes only its own tableDV:Comparison of LS and DV Algorithms2020• DV node can advertise incorrect path cost• each node’s table used by others • errors propagate thru network• Other tradeoffs• Making LSP flood reliableOutlinez Link Statez OSPF2121z IP Multicast Service Basicsz Host/Router Interactionz MOSPF/DVMRPMulticast Routingz Unicast: one source to one destination2222z Multicast: one source to many destinationsz Main goal: efficient data distribution Multicast – Efficient Data DistributionSrc Src2323Example Applicationsz Broadcast audio/videoz Push-based systemsz Software distributionWbhdt2424zWeb-cache updates z Teleconferencing (audio, video, shared whiteboard, text editor)z Multi-player gamesz Server/service locationz Other distributed applications2/16/20085IP Multicast ArchitectureHostsRtService modelHost-to-router protocol(IGMP)2525RoutersMulticast routing protocols(various)Logical Namingz Single name/address maps to logically related set of destinations2626»Destination set = multicast group z Key challenge: scalability»Single name/address independent of group growth or changesMulticast Router Responsibilitiesz Learn of the existence of multicast groups (through advertisement)z Identify links with group members2727z Establish state to route packets»Replicate packets on appropriate interfaces»Routing entry:Src, incoming interface List of outgoing interfacesIP Multicast Service Model (rfc1112)z Each group identified by a single IP addressz Groups may be of any sizez Members of groups may be located anywhere in the Internet2828in the Internetz Members of groups can join and leave at willz
View Full Document
Unlocking...