Quản trị mạng - Link - State Routing Protocols

Link-State Routing ProtocolsRouting Protocols and Concepts – Chapter 10ObjectivesDescribe the basic features & concepts of link-state routing protocols.List the benefits and requirements of link-state routing protocols.IntroductionLink-State RoutingLink state routing protocolsAlso known as shortest path first algorithmsThese protocols built around Dijkstra’s SPF Link-State RoutingDikjstra’s algorithm also known as the shortest path first (SPF) algorithmLink-State RoutingThe shortest path to a destination is not necessarily the path with the least number of hopsLink-State RoutingLink-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 RoutingDirectly Connected NetworksLinkThis is an interface on a routerLink stateThis is the information about the state of the linksLink-State RoutingSending 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 RoutingSending Hello Packets to NeighborsConnected interfaces that are using the same link state routing protocols will exchange hello packetsOnce routers learn it has neighbors they form an adjacency2 adjacent neighbors will exchange hello packets These packets will serve as a keep alive functionLink-State RoutingBuilding 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 RoutingFlooding 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 RoutingLSPs are sent out under the following conditions:Initial router start up or routing processWhen there is a change in topologyLink-State RoutingConstructing a link state data baseRouters use a database to construct a topology map of the networkLink-State RoutingLink-State RoutingShortest Path First (SPF) TreeBuilding a portion of the SPF treeProcess begins by examining R2’s LSP informationR1 ignores 1st LSPReason: R1 already knows it’s connected to R2 Link-State RoutingBuilding a portion of the SPF treeR1 uses 2nd LSPReason: R1 can create a link from R2 to R5 - this information is added to R1’s SPF tree Link-State RoutingBuilding a portion of the SPF treeR1 uses 3rd LSPReason: R1 learns that R2 is connected to 10.5.0.0/16This link is added to R1’s SPF treeLink-State RoutingDetermining the shortest path The shortest path to a destination determined by adding the costs & finding the lowest costLink-State RoutingOnce the SPF algorithm has determined the shortest path routes, these routes are placed in the routing tableLink-State Routing ProtocolsRoutingprotocolBuildsTopological mapRouter can independently determine the shortest path to every network.ConvergenceA periodic/event driven routing updatesUseof LSPDistance vector NoNoSlowGenerally NoNoLink StateYesYesFastGenerally YesYesAdvantages of a Link-State Routing ProtocolLink-State Routing ProtocolsRequirements 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 Protocols2 link state routing protocols used for routing IP Open Shortest Path First (OSPF)Intermediate System-Intermediate System (IS-IS)SummaryLink 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 destinationSummaryLinkAn interface on the routerLink StateInformation about an interface such asIP addressSubnet maskType of networkCost associated with linkNeighboring routers on the linkSummaryLink State PacketsAfter initial flooding, additional LSP are sent out when a change in topology occursExamples of link state routing protocolsOpen shortest path firstIS-IS