Bài giảng Mạng máy tính nâng cao - Chapter10: Link-State routing protocols

Chapter10LINK-STATE ROUTING PROTOCOLSMẠNG MÁY TÍNH NÂNG CAOObjectives Describe the basic features & concepts of link-state routing protocols.List the benefits and requirements of link-state routing protocols.Introduction Link state routing protocolsAlso known as shortest path first algorithmsThese protocols built around Dijkstra’s SPF IntroductionDikjstra’s algorithm also known as the shortest path first (SPF) algorithmIntroductionThe shortest path to a destination is not necessarily the path with the least number of hopsLink-State Routing ProcessHow routers using Link State Routing Protocols reach convergenceEach routers learns about its own directly connected networksLink state routers exchange hello packet to “meet” other directly Connected link state routersEach router builds its own Link State Packet (LSP) which includes information about neighbors such as neighbor ID, link type, & bandwidthAfter the LSP is created the router floods it to all neighbors who then store the information and then forward it until all routers have the same informationOnce all the routers have received all the LSPs, the routers then construct a topological map of the network which is used to determine the best routes to a destinationLink-State Routing Directly Connected NetworksLinkThis is an interface on a routerLink stateThis is the information about the state of the linksLink-State Routing Sending Hello Packets to NeighborsLink state routing protocols use a hello protocolPurpose of a hello protocol:To discover neighbors (that use the same link state routing protocol) on its linkLink-State Routing Link-State Routing Building the Link State PacketEach router builds its own Link State Packet (LSP)Contents of LSP:State of each directly connected linkIncludes information about neighbors such as neighbor ID, link type, & bandwidthLink-State Routing Flooding LSPs to NeighborsOnce LSP are created they are forwarded out to neighborsAfter receiving the LSP the neighbor continues to forward it throughout routing areaLink-State Routing LSPs are sent out under the following conditions:Initial router start up or routing processWhen there is a change in topologyLink-State Routing Constructing a link state data baseRouters use a database to construct a topology map of the networkLink-State Routing Link-State Routing Determining the shortest path The shortest path to a destination determined by adding the costs & finding the lowest costLink-State Routing Once the SPF algorithm has determined the shortest path routes, these routes are placed in the routing tableLink-State Routing Protocols Advantages of a Link-State Routing ProtocolRoutingprotocolBuildsTopological mapRouter can independently determine the shortest path to every network.ConvergenceA periodic/event driven routing updatesUseof LSPDistance vector NoNoSlowGenerally NoNoLink StateYesYesFastGenerally YesYesLink-State Routing Protocols Requirements for using a link state routing protocolMemory requirementsTypically link state routing protocols use more memory Processing RequirementsMore CPU processing is required of link state routing protocolsBandwidth RequirementsInitial startup of link state routing protocols can consume lots of bandwidthLink-State Routing Protocols 2 link state routing protocols used for routing IP Open Shortest Path First (OSPF)Intermediate System-Intermediate System (IS-IS)Summary Link State Routing protocols are also known as Shortest Path First protocolsSummarizing the link state processRouters 1ST learn of directly connected networksRouters then say “hello” to neighborsRouters then build link state packetsRouters then flood LSPs to all neighborsRouters use LSP database to build a network topology map & calculate the best path to each destinationSummary LinkAn interface on the routerLink StateInformation about an interface such asIP addressSubnet maskType of networkCost associated with linkNeighboring routers on the linkSummary Link State PacketsAfter initial flooding, additional LSP are sent out when a change in topology occursExamples of link state routing protocolsOpen shortest path firstIS-IS