Link state routing protocol

Link state routing protocol

• 1.
  Link-state routing Protocol Aung ThuRha 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 oftwo 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-staterouting 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 1. 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 2. 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 Database 4. 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 Also known as the shortest path first (SPF) 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+ ∞ 14<7+1 10+7 0+2 6 7 9 22 9+2+10 14 +7
• 7.
  Dijkstra’s algorithm(Cont.)
• 8.
  Open Shortest PathFirst (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 PathFirst (OSPF) OSPF can operate within a hierarchy Collection of networks under a common administration that share a common routing strategy
• 10.
  Additional OSPF Features •Equal-cost • Multipath routing • Routing based on upper-layer type-of-service (TOS) requests
• 11.
  IS-IS • Intermediate System-to-IntermediateSystem (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 • 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
• 13.
  Advantages and Disadvantagesof 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 Disadvantagesof 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.