Link state routing protocol

Introduction of Link-state routing protocol

1. Link-state routing Protocol Aung Thu Rha Hein Chinnawat Noosrikong

2. 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

3. Overview One of two main classes of interior gateway routing protocols OSPF, IS-IS Performed by every switching node in the network Basic 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

4. Features of Link-state routing protocols Link-state advertisement (LSA ) or Link-state Packet(LSP)   a small packet of routing information that is sent between routers Topological database   or Link-state Database a collection of information gathered from LSAs SPF algorithm   a calculation performed on the database that results in the SPF tree Routing table a list of the known paths and interfaces

5. link-state routing algorithm 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 sent Each router constructs a LSP/LSA which consists of a list of names and cost for each of its neighbors . 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 Database 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

6. Dijkstra’s algorithm Nodes 2 3 4 5(b) 6 1(a) 7 9 ∞ ∞ 14 2 7 9<7+10 7+15 ∞ 14 3 7 9 22<11+10+7 ∞ 14<7+10+2 6 7 9 22 9+2+10+7 14 Also known as the shortest path first (SPF) algorithm

7. Dijkstra’s algorithm(Cont.)

8. 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

9. Open Shortest Path First (OSPF)  OSPF can operate within a hierarchy Collection of networks under a common administration that share a common routing strategy

10. Additional OSPF Features E qual-cost M ultipath routing R outing based on upper-layer type-of-service (TOS) requests

11. 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 network's topology IS-IS uses  Dijkstra's 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

12. Integrated IS-IS Integrated IS-IS is a version of the OSI IS-IS  T o support more network layer protocols than just CLNP Dual IS-IS I mplementations send only one set of routing updates S upporting multiple network layer protocols in a router

13. Advantages and Disadvantages of LS routing protocols Advantages 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.

14. Advantages and Disadvantages of LS routing 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.