ch6.pdf

JTO PH-II IT OSPF 6 OPEN SHORTEST PATH FIRST PROTOCOL 6.1 OBJECTIVE The objectives of this chapter is to understand  Introduction to Link state routing protocol  Why OSPF preferred in larg...

JTO PH-II IT OSPF 6 OPEN SHORTEST PATH FIRST PROTOCOL 6.1 OBJECTIVE The objectives of this chapter is to understand  Introduction to Link state routing protocol  Why OSPF preferred in larger networks  Features of OSPF & Metric calculation  OSPF Tables & Message types  OSPF Message format  DR BDR Election process  LSDB Exchange process  OSPF LSA types  OSPF Area types 6.2 OSPF – LINK STATE ROUTING PROTOCOL INTRODUCTION Distance vector protocol has limitations in multifold. Maximum number of routers in a chain not more than 15, constant periodic routing announcements exchanged even then there is no change in network topology. RIP does not consider the bandwidth supported on links, it just counts the number of routers to cross to reach destination, that too as told by a neighbor. Because of these limitations, as network grows link state routing protocol is preferred over distance vector protocol. Link-state protocols build routing tables based on a topology database. This database is built from link-state packets that are passed between all the routers to describe the state of a network. The shortest path first algorithm uses the database to build the routing table. Figure shows the components of a link-state protocol. Figure 36: Components of link state protocol Understanding the operation of link-state routing protocols is critical to being able to enable, verify, and troubleshoot their operation. JTO-PH-II IT Version Page 62 of 136 For Restricted Circulation  JTO PH-II IT OSPF Link-state-based routing algorithms—also known as shortest path first (SPF) algorithms— maintain a complex database of topology information. Whereas the distance vector algorithm has nonspecific information about distant networks and no knowledge of distant routers, a link-state routing algorithm maintains full knowledge of distant routers and how they interconnect. Link-state routing uses link-state advertisements (LSA), a topological database, the SPF algorithm, the resulting SPF tree, and, finally, a routing table of paths and ports to each network. Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS) are classified as link-state routing protocols. Link-state routing protocols collect routing information from all other routers in the network or within a defined area of the internetwork. After all the information is collected, each router, independently of the other routers, calculates its best paths to all destinations in the network. Because each router maintains its own view of the network, it is less likely to propagate incorrect information provided by any one particular neighboring router. Link-state routing protocols were designed to overcome the limitations of distance vector routing protocols. Link-state routing protocols respond quickly to network changes, send triggered updates only when a network change has occurred, and send periodic updates (known as link-state refreshes) at long intervals, such as every 30 minutes. A hello mechanism determines the reachability of neighbors. When a failure occurs in the network, such as a neighbor becomes unreachable, link-state protocols flood LSAs using a special multicast address throughout an area. Each link-state router takes a copy of the LSA, updates its link-state (topological) database, and forwards the LSA to all neighboring devices. LSAs cause every router within the area to recalculate routes. Because LSAs need to be flooded throughout an area and all routers within that area need to recalculate their routing tables, you should limit the number of link-state routers that can be in an area. A link is similar to an interface on a router. The state of the link is a description of that interface and of its relationship to its neighboring routers. A description of the interface would include, for example, the IP address of the interface, the mask, the type of network to which it is connected, the routers connected to that network, and so on. The collection of link states forms a link-state, or topological, database. The link-state database is used to calculate the best paths through the network. Link-state routers find the best paths to a destination by applying Edsger Dijkstra's SPF algorithm against the link-state database to build the SPF tree. The best paths are then selected from the SPF tree and placed in the routing table. 6.3 WHY LINK STATE PROTOCOL IS PREFERRED IN LARGER NETWORKS? As networks become larger in scale, link-state routing protocols become more attractive for the following reasons:  Link-state protocols always send updates when a topology changes. JTO-PH-II IT Version Page 63 of 136 For Restricted Circulation  JTO PH-II IT OSPF  Periodic refresh updates are more infrequent than for distance vector protocols.  Networks running link-state routing protocols can be segmented into area hierarchies, limiting the scope of route changes.  Networks running link-state routing protocols support classless addressing.  Networks running link-state routing protocols support route summarization. Link-state protocols use a two-layer network hierarchy, as shown in Figure below Figure 37: Link-State Network Hierarchy The two-layer network hierarchy contains two primary elements:  Area: An area is a grouping of networks. Areas are logical subdivisions of the autonomous system (AS).  Autonomous system: An AS consists of a collection of networks under a common administration that share a common routing strategy. An AS, sometimes called a domain, can be logically subdivided into multiple areas. Within each AS, a contiguous backbone area must be defined. All other non- backbone areas are connected to the backbone area. The backbone area is the transition area because all other areas communicate through it. For OSPF, the nonbackbone areas can be additionally configured as a stub area, a totally stubby area, a not-so-stubby area (NSSA), or a totally not-so-stubby area to help reduce the link-state database and routing table size. JTO-PH-II IT Version Page 64 of 136 For Restricted Circulation  JTO PH-II IT OSPF Figure 38: OSPF Routers nomenclature Routers operating within the two-layer network hierarchy have different routing entities. The terms used to refer to these entities are different for OSPF than IS-IS. Refer to the following examples from Figure2:  Routers A, B are called as the backbone routers. All their interfaces participate in AREA 0  Routers C, D, E are called area border routers (ABR), ABR routers attach to multiple areas, maintain separate link-state databases for each area to which they are connected, and route traffic destined for or arriving from other areas.  Routers F, G and H are called non-backbone internal routers. Nonbackbone internal routers are aware of the topology within their respective areas and maintain identical link-state databases about the areas.  The ABR router will advertise a default route to the non-backbone internal router. The internal router will use the default route to forward all inter area or interdomain traffic to the ABR router. This behavior can be different for OSPF, depending on how the OSPF non-backbone area is configured (stub area, totally stubby area, or not-so-stubby area).  ASBR Autonomous system boundary router. A router that is connected to two or more routing domains, that exchanges routing information between different routing protocols. 6.4 LINK-STATE ROUTING PROTOCOL ALGORITHMS Link-state routing algorithms, known as SPF protocols, maintain a complex database of the network topology. Unlike distance vector protocols, link-state protocols develop and maintain full knowledge of the network routers and how they interconnect. This is achieved through the exchange of link-state packets (LSP) with other routers in a network. JTO-PH-II IT Version Page 65 of 136 For Restricted Circulation  JTO PH-II IT OSPF Each router that has exchanged LSPs constructs a topological database using all received LSPs. An SPF algorithm is then used to compute reachability to networked destinations. This information is employed to update the routing table. The process can discover changes in the network topology caused by component failure or network growth. In fact, the LSP exchange is triggered by an event in the network, instead of running periodically. This can greatly speed up the convergence process because it is unnecessary to wait for a series of timers to expire before the networked routers can begin to converge. If the network shown in Figure 4 uses a link-state routing protocol, connectivity between remote areas is not a concern. Depending on the actual protocol employed and the metrics selected, it is highly likely that the routing protocol could discriminate between the two paths to the same destination and try to use the best one. Figure 39: Link-State Algorithms Router Destination Ne Cost xt Hop A 185.134.0.0 B 1 192.168.33.0 C 1 JTO-PH-II IT Version Page 66 of 136 For Restricted Circulation  JTO PH-II IT OSPF 192.168.157.0 B 2 192.168.157.0 C 2 B 10.0.0.0 A 1 192.168.33.0 C 1 192.168.157.0 D Route Destination Next Hop C r ost C 10.0.0.0 A 1 185.134.0.0 B 1 192.168.157.0 D 1 D 10.0.0.0 B 2 10.0.0.0 C 2 185.134.0.0 B 1 192.168.33.0 C 1 Table 10. Routing database of each router As shown in the table link-state database entries for the Router A to Router D routes, a link-state protocol would remember both routes. Some link-state protocols can even provide a way to assess the performance capabilities of these two routes and bias toward the better-performing one. If the better-performing path, such as the route through Router C, experienced operational difficulties of any kind, including congestion or component failure, the link-state routing protocol would detect this change and begin forwarding packets through Router B. Link-state routing might flood the network with LSPs during initial topology discovery and can be both memory- and processor-intensive. The following list highlights some of the many benefits that link-state routing protocols have over the traditional distance vector algorithms  Link-state protocols use cost metrics to choose paths through the network. For Cisco IOS devices, the cost metric reflects the capacity of the links on those paths. JTO-PH-II IT Version Page 67 of 136 For Restricted Circulation  JTO PH-II IT OSPF  By using triggered, flooded updates, link-state protocols can immediately report changes in the network topology to all routers in the network. This immediate reporting generally leads to fast convergence times.  Because each router has a complete and synchronized picture of the network, it is difficult for routing loops to occur.  Because LSPs are sequenced and aged, routers always base their routing decisions on the latest set of information.  With careful network design, the link-state database sizes can be minimized, leading to smaller SPF calculations and faster convergence. The link-state approach to dynamic routing can be useful in networks of any size. In a well-designed network, a link-state routing protocol enables your network to gracefully adapt to unexpected topology changes. Using events, such as changes, to drive updates, rather than fixed-interval timers, enables convergence to begin that much more quickly after a topological change. The overhead of the frequent, time-driven updates of a distance vector routing protocol is also avoided. This makes more bandwidth available for routing traffic rather than for network maintenance, provided you design your network properly. When compared to the limitations of static routes or distance vector protocols, you can easily see that link-state routing is best in larger, more complex networks, or in networks that must be highly scalable. Initially configuring a link-state protocol in a large network can be challenging, but it is well worth the effort in the long run. 6.5 FEATURES OF OSPF PROTOCOL: 1 OSPF is open standard protocol supported all by many vendors, 2 OSPF can run many instances in parallel... 3 Metric used by OSPF is called as Cost which is equal to 100Mbps / BW in Mbps 4 OSPF update messages are triggered and incremental updates are sent as multicast messages using the addresses 224.0.0.5 & 224.0.0.6 5 OSPF periodically sends LSA refresh update messages every 30mins 6 OSPF update messages are called as LSU - Link state Update, which may contain many LSAs - Link State Advertisement. There are as many as 11 types of LSUs in OSPF. 7. The Administrative Distance of OSPF protocol is 110. 8 OSPF protocol supports manual summarization and VLSM. 9 Route announcements carry subnet mask. JTO-PH-II IT Version Page 68 of 136 For Restricted Circulation  JTO PH-II IT OSPF 10 OSPF protocol maintains three tables for efficient routing. 11 Each OSPF speaking router is identified by router id. 6.6 OSPF METRIC CALCULATION: The metric used by OSPF protocol is called as COST. OSPF default Cost is calculated using the formula 100Mbps/ (bandwidth in Mpbs). OSPF uses cumulative cost of all the interfaces to find the best path. See Figure:5 The reference bandwidth can be altered by network administrator. Figure 40: Calculation of OSPF cost metric 6.7 OSPF’S THREE TABLES: Neighbor table This table contains the details of OSPF neighbors with which the router has built adjacency with their Router Ids and state information. OSPF maintains neighborship with other OSPF routers by exchanging periodic HELLO message for every 10 seconds. If from a neighbor hello messages are not heard for more than 10 seconds OSPF router invalidates all the routes learnt from that neighbor are tries to find alternate path to those destinations. Topology Table Topology table contains the Link state information flooded by all the OSPF routers of an area. This table is referred as LSDB Link State Data Base - the resource from which best routes are calculated. See Figure Each router has a clear picture of entire area. Every OSPF router individually runs Dijkstra‘s SPF Algorithm on its Link State Data Base, JTO-PH-II IT Version Page 69 of 136 For Restricted Circulation  JTO PH-II IT OSPF builds SPF tree and finds best route all remote networks independently. But in case of Distance Vector routing protocol, the best routes (rumors) are informed by neighbors. Routing table This table contains the best routes to reach all the networks in the entire topology similar to other routing protocols. OSPF supports equal cost load balancing by default. 6.8 CONDITIONS FOR TWO OSPF ROUTERS TO BECOME NEIGHBORS: If we want two OSPF routers to make as neighbors to make them share link state information, these parameters must match between them. 1 Subnets of router interfaces must be same 2 Hello and dead timers must match 3 Hello – 10 sec (this defines how often OSPF sends the hello packet) 4 Dead interval – 40 sec: (this defines how long OSPF router should wait for hello packets before it declares a neighbor dead.) 5 Area ID should match 6 Stub area flags (Area type) must match 7 Authentication type & password should match 6.9 OSPF MESSAGE TYPES: OSPF Messages are used to exchange link state information. OSPF uses five types of messages: Hello message This message is used to establish and maintain adjacency. This message contains many parameters that are exchanged by two OSPF routers for negotiating neighborship. They are router ID, area ID, DR ID, BDR ID, neighbor‘s router Id, router priority, hello interval, dead interval = 4* hello interval, authentication type and authentication key. Database description message (DBD) This message contains summary of LSU, router ID, sequence number to detect old LSA record and checksum value. Link state request (LSR) - Link state request message to request a particular link state record from another router JTO-PH-II IT Version Page 70 of 136 For Restricted Circulation  JTO PH-II IT OSPF Link State Update (LSU) – Link state records are sent by Link State Update Messages. LSAck – Used to acknowledgement for the other OSPF messages 6.10 OSPF MESSAGE FORMAT: Figure represents the various fields available in OSPF message. The short description of each field is given below. 1 Version Number: Set to 2 for OSPF version 2. 2 Type: Hello, Database description, LSR, LSU, LSAck 3 Packet Length: The length of the message, in bytes, including the 24 bytes of this header. 4 Router ID: The ID of the router that generated this message (generally its IP address on the interface over which the message was sent). 5 Area ID: An identification of the OSPF area to which this message belongs, when areas are used. Figure 41: OSPF Message Format 6 Checksum: A 16-bit checksum computed in a manner similar to a standard IP checksum. The entire message is included in the calculation except the Authentication field. JTO-PH-II IT Version Page 71 of 136 For Restricted Circulation  JTO PH-II IT OSPF 7 Authentication Type: Plaintext, no authentication or MD5 type is sent 8 Authentication: A 64-bit field used for authentication of the message, as needed. 9 Data: Contain different information depending upon OSPF packet type. 6.10.1 OSPF ROUTER ID: When the OSPF process initializes, OSPF router selects the highest IP address on a router‘s loopback address as the router ID for the OSPF process. If no loopback interfaces are configured then router selects the highest IP addresses of running interfaces as Router ID. This router ID uniquely identifies a router within an OSPF domain. OSPF router ID can also be configured manually by network administrator. 6.10.2 OSPF AREA ID: OSPF Area ID is a number that is used to name an area. 6.11 OSPF DR AND BDR & ELECTION PROCESS: When OSPF routers are connected using a broadcast network like Ethernet, they will be participating in a same subnet. In such cases for efficient exchange of routing information, they elect two routers as DR Designated Router and BDR Backup Designated router. Other non DR routers are called DROther routers. Figure 42: DR BDR and DRO OSPF Routers DR and BDR act as a central point for exchanging of OSPF information between multiple routers on the same, multi-access broadcast network segment. Each non-DR and non-BDR router only exchanges routing information with the DR and BDR, instead of the exchanging updates with every router on the segment. This significantly reduces the amount of OSPF routing updates sent across the network. Election process: JTO-PH-II IT Version Page 72 of 136 For Restricted Circulation  JTO PH-II IT OSPF A router with the highest OSPF priority will become a DR. By default, all routers have a priority of 1 in their OSPF enabled interfaces. If there is a tie, a router with the highest router ID wins the election. The router with the second highest OSPF priority or router ID will become a BDR. All other routers remain as DROther routers. To make OSPF router not to participate in DR BDR election process that router‘s OSPF priority is set to 0. Other routers send route advertisements to DR and BDR routers using multicast address 224.0.0.6. DR router use multicast address 224.0.0.5 to forward the link state information to other DROther routers. 6.12 OSPF LSDB EXCHANGE PROCESS: There are seven stages before two OSPF routers‘ LSDB gets synchronized. Figure 43: LSDB Exchange process Down: Initial state for a neighbor. Mostly seen when a working adjacency to a neighbor is torn down or when a manually configured neighbor does not respond to our initial Hello packets. Note that having a neighbor in the Down state implies that the router already knows about this neighbor‘s IP address. Init: This router can hear the other router but it is not certain whether the other router can hear this router. 2-Way: This state confirms a bidirectional visibility between the two routers. The 2-Way is a stable state between routers on multiaccess networks that do not intend to become fully adjacent. (Between DROthers) JTO-PH-II IT Version Page 73 of 136 For Restricted Circulation  JTO PH-II IT OSPF ExStart: The purpose of the ExStart state is to establish the Master/Slave relationship. In the ExStart state, routers exchange empty Database Description packets to compare their Router IDs, determine the Master and Slave roles for each router, and agree on a common starting sequence number used to acknowledge subsequent Database Description packets used in the Exchange state. Exchange: During this state, Database Description packets are exchanged between the routers carrying the list of link-state database elements DBD (list of LSAs; not the LSA data itself.) known by each router. Each router builds a list of LSAs to be subsequently downloaded from the other router. Loading: A neighbor is moved from the Exchange to Loading state after it has advertised the complete list of LSAs and this router needs to download some of the LSAs from the neighbor. The neighbor is kept in the Loading state during LSA download. Full: A neighbor is moved from the Exchange or Loading state to the Full state when all required LSAs have been downloaded from the neighbor, so all missing or outdated LSAs have been acquired. The Full state is a stable state between routers that have become fully adjacent 6.13 OSPF LSA TYPES: Type 1 – Router LSA: The Router LSA is generated by each router for each area it is located. Type 2 – Network LSA: Network LSAs are generated by the DR. Type 3 – Summary LSA: The summary LSA is created by the ABR and flooded into other areas. Type 4 – Summary ASBR LSA: Other routers need to know where to find the ASBR. ABR will generate a summary ASBR LSA which will include the router ID of the ASBR Type 5 – External LSA: also known as autonomous system external LSA: The external LSAs are generated by the ASBR. Type 6 – Multicast OSPF LSA. Type 7 – External LSA: also known as not-so-stubby-area (NSSA) LSA Type 8 – Used to internetwork OSPF and BGP Type 9, 10, 11 – Designated for future use, for application specify purposes. Used along with MPLS. 6.14 OSPF AREA TYPES: Standard Area: This area type accepts link updates, summary routes an external OSPF routes. JTO-PH-II IT Version Page 74 of 136 For Restricted Circulation  JTO PH-II IT OSPF Backbone area (transit area): This area is named as Area 0, which has all properties of standard area. Stub area: This area do not accept external routes, they use default route to reach external routing domains. Stub area cannot contain ASBRs (Unless it is an ABR) Totally stubby area: This area does not accept external routes or summary routes from other areas. Uses default route to reach non-local area networks. Totally stubby area cannot contain ASBR (unless it is also an ABR). Not So Stubby Area NSSA: This has the properties of stub area, but it can contain ASBR which is against the stub area. Totally Stubby Not So Stubby Area NSSA: This has the properties of totally stub area, but it can contain ASBR which is against the totally stub area. Figure 44: OSPF Area Types & LSAs that are allowed JTO-PH-II IT Version Page 75 of 136 For Restricted Circulation  JTO PH-II IT OSPF 6.15 CONCLUSION Open shortest path first (OSPF) is a link-state routing protocol which is used to find the best path between the source and the destination router using its own shortest path first (SPF) algorithm. It is one of the mostly used and reliable Interior Gateway protocol for large scale network. JTO-PH-II IT Version Page 76 of 136 For Restricted Circulation