Outline• Overview• Features of Link-State routing protocols• link-state routing algorithm• Dijkstra’s algorithm• OSPF• IS-IS• Advantages and Disadvantages of LS routing protocols
Overview• One of two main classes of interior gateway routing protocols • OSPF, IS-IS• Performed by every switching node in the networkBasic Concept• every node creates a map of the connectivity to the network • This graph shows which nodes are connected to which other nodes • Each node calculates the next best logical path to the destination • Collection of best paths form the routing table of the node
Features of Link-state routingprotocolsLink-state advertisement (LSA) or Link-state Packet(LSP)• a small packet of routing information that is sent between routersTopological database or Link-state Database• a collection of information gathered from LSAsSPF algorithm• a calculation performed on the database that results in the SPF treeRouting table• a list of the known paths and interfaces
link-state routing algorithm1. Each router is responsible for meeting its neighbors and learning their names. • Used a Hello Protocol, which send a data packet contains RID and address of the network on which the packet is being sent2. Each router constructs a LSP/LSA which consists of a list of names and cost for each of its neighbors.3. The LSP/LSA is transmitted to all other routers. Each router stores the most recently generated LSP/LSA from each other router. • Link-state flooding: Sequencing and Aging procedures • Each routers store the identical Link State Database4. Each router uses complete information on the network topology to compute the shortest path route to each destination node. • Use SPF or Dijkstra’s algorithm to calculate the shortest path
Dijkstra’s algorithm Also known as the shortest path first (SPF) algorithmNodes 2 3 4 5(b) 61(a) 7 9 ∞ ∞ 14 2 7 9<7+10 7+15 ∞ 14 3 7 9 22<11+ ∞ 14<7+1 10+7 0+2 6 7 9 22 9+2+10 14 +7
Open Shortest Path First (OSPF)• A routing protocol developed for Internet Protocol networks by the Interior Gateway Protocol (IGP)• Based on the Dijkstra’s Algorithm• Serving large, heterogeneous internetworks• OSPF Version 1 (1988)• OSPF Version 2 (1998) Supported IPv4• OSPF Version 3 (2008) Supported IPv6
Open Shortest Path First(OSPF)OSPF can operate within a hierarchyCollection of networks under a common administration that share acommon routing strategy
Additional OSPF Features• Equal-cost• Multipath routing• Routing based on upper-layer type-of-service (TOS) requests
IS-IS• Intermediate System-to-Intermediate System (IS-IS)• That floods the network with link-state information to build a complete, consistent picture of network topology • Each IS-IS router independently builds a database of the networks topology• IS-IS uses Dijkstras algorithm for computing the best path through the network• IS-IS Metrics• A single required default metric with a maximum path value of 1024• Three optional metrics (costs): • Delay • Expense • Error
Integrated IS-IS• Integrated IS-IS is a version of the OSI IS-IS• To support more network layer protocols than just CLNP• Dual IS-IS• Implementations send only one set of routing updates• Supporting multiple network layer protocols in a router
Advantages and Disadvantages of LSrouting protocolsAdvantages• Smaller routing tables • Only a single optimal route for each network ID is stored in the routing table.• Low network overhead • do not exchange any routing information when the internetwork has converged.• Ability to scale. • scale well to large and very large internetworks.• Lower convergence time. • have a much lower convergence time and the internetwork is converged without routing loops.
Advantages and Disadvantages of LSrouting protocols(cont.)Disadvantages• Complex • much more complex and difficult to understand than DV routing protocols.• More difficult to configure. • implementation requires additional planning and configuration.• Resource intensive. • For very large internetworks, the LS database and the calculation of routing table entries can be memory and processor intensive.