Because of its hierarchical design, OSPF is more efficient and scalable. The OSPF segments the network into different areas. An area is a group of routers sharing the same link-state information in their Link-State Databases (LSDBs). We can implement the OSPF in two ways.
Single Area OSPF
Multi-Area OSPF
Single Area OSPF (Area 0)
Area 0 is also known as the backbone area for OSPF, which links all other smaller areas within the hierarchy. The single area OSPF is helpful in smaller networks where only a few routers are working, the web of router links is not complex, and paths to individual destinations are easy. If an area becomes too big, the network will be affected.
Large routing table
Extensive link-state database (LSDB)
Frequent SPF algorithm calculations
OSPF supports hierarchical routing using areas, which makes OSPF more efficient and scalable. An area is a group of routers sharing the same link-state information in their databases. The figure below illustrates the single-area OSPF network.
Multi-Area OSPF
When a large OSPF area is separated into several smaller areas, this is called multi-area OSPF. It is helpful in larger network deployments to decrease processing and memory overhead. The network contains OSPF areas in a hierarchal design. All areas are connected to area 0, known as the backbone area—the interconnecting routers between the backbone area and other areas are known as area border routers (ABR).
The figure shows that multi-area OSPF segments one large network into several networks. One autonomous system ( AS) has been divided into multiple areas to support hierarchical routing. The routing occurs between the multiple areas. The more operations that require system resources, such as recalculating the database, are done only within a relevant area.
For example, when changes occur in the topology, like addition, deletion, or modification of the link, the router must rerun the SPD algorithm to create a new SPF tree and update the routing table in the same area where changes occur. However, changes have been shared with routers in other areas in a distance-vector format to update their routing tables, and these routers and areas do not need to rerun the SPF algorithm. As illustrated in Figure 1, the hierarchical-topology possibilities of multi-area OSPF have these advantages:
Smaller routing tables—Fewer routing table entries as network addresses can be summarized between areas. For example, R1 summarizes the routes from Area 1 to Area 0, and R2 summarizes the routes from Area 51 to Area 0. R1 and R2 also propagate a default static route to Area 1 and 51.
Reduced link-state update overhead– Minimizes processing and memory requirements because fewer routers exchange LSAs.
Reduced frequency of SPF calculations—This Minimizes the impact of a topology change within an area. For instance, it minimizes the impact of routing updates because LSA flooding stops at the area boundary.
Small Link-State Data Base. Multi-areas OSPF efficiently partitions a potentially large database into smaller, more manageable ones.
OSPF Two-Layer Area Hierarchy
Multiarea OSPF is implemented in a two-layer area hierarchy:
Backbone (Transit) area—An OSPF area transfers IP packets fast and efficiently. Backbone areas interconnect multiple OSPF areas. End users are usually not found within a backbone area.
Regular (Non-backbone) area –This area connects users and other resources. The areas are usually set up along functional or geographical groupings. By default, a regular area does not allow traffic from another area. Traffic from other areas must forward through a transit area. A regular can contain several subtypes, including a standard area, stub area, totally stubby area, and not-so-stubby area (NSSA). The Cisco recommends the following guidelines for areas:
The maximum number of routers per area is 50.
One router can join a maximum of three areas.
The maximum number of neighbors for a single router is 60.
Link state is the most used routing protocol; therefore, the link state operation is essential for networking students. In this article, we are discussing the link state operation. Link State Routing protocols reduce broadcast traffic as they do not send periodic updates. It also does not send entire routing tables with each broadcast.
Link state only exchanges entire routing tables during initialization. After initialization, routing updates are only multicast when a change occurs. It also sends only the change in the update, not the entire routing table. The changes in the topology are flooded immediately and computed in parallel. If no changes occur, they do not generate any periodic updates.
The event-triggered updates improve network convergence time because on the event required, the router sends an update message right away. An event such as a new link installation or an existing link failing or removed triggers the link-state update when link-state changes occur.
The link-state protocols support VLSM, which enables routers to recognize and forward traffic to subnets within a network. The link-state updates also include the subnet mask, which allows a router to identify the exact subnet to forward traffic.
All Link State protocols build and maintain three types of tables called databases: The Adjacency database, the Link State database, and the Forwarding database. To maintain routing information, OSPF routers do the following generic link-state operation to achieve a state of convergence:
Establish Neighbor Adjacencies
All OSPF-enabled routers must establish Neighbor Adjacencies and relationships with one another. The OSPF-enabled routers must recognize each other on the network before sharing information. Adjacent routers establish this relationship using the exchange of hello packets.
OSPF enables routers to send hello packets to all OSPF enabled interfaces, as shown in the figure below. The routers build the adjacency table using these hello packets. Within hello messages packets, routers announce themselves and also identify directly connected links and the state of these links.
Exchange of LSAs
Once the adjacency relationship is completed, the routers exchange link-state advertisements (LSAs). LSAs contain the router’s state and the cost of each directly connected link. Each router floods its LSA to adjacent neighbors.
The adjacent neighbours which receive the LSA, immediately flood the LSA to other directly connected neighbours without any changes, the process is continued until all routers in the area received all routers LSA. The figure below illustrates the exchange of LSAs
Building a Link state database (LSDB)
After exchanging LSAs, each router builds a topology table or link-state database (LSDB) and places itself in the root position. This database holds all information about the network’s topology.
SPF Tree
After building a Link State database on all the routers, the routing protocol executes the SPF Algorithm (Dijkstra’s algorithm). The SPF algorithm creates the SPF tree for each router based on LSDB. The SPF tree includes each possible path to the destination with its cost. The figure below illustrates the SPF tree.
Forwarding Database
From the SPF tree, the best paths are inserted into the routing table, also known as the forwarding database, and the router makes routing decisions based on entries in the routing table.
Open Shortest Path First (OSPF) is a link-state routing protocol replacing distance vector routing protocol, RIP. RIP was acceptable in the early days of networking. RIP uses hop count as the metric which is not working better in the larger network.
Open Shortest Path First (OSPF) has many advantages over RIP. It can scale a larger network and offer a faster convergence. It is a classless routing protocol using the concept of areas for scaling the network. Open Shortest Path First (OSPF) uses the Dijkstra algorithm created a famous programmer Edsger Wybe Dijkstra.
Development of Open Shortest Path First (OSPF)
The Internet Engineering Task Force (IETF) starts initial working on OSPF in 1987. Meanwhile, the internet was not public; it only used as an academic and research network funded by the government of the United States. In 1989 the OSPF version 1 specification was published in RFC 1131; only for running on routers and UNIX workstations. Later its implementation became a widespread UNIX process known as GATED.
Version 1 of the OSPF is an experimental routing protocol and was never deployed. In 1991, John Moy introduced OSPF version 2 in RFC 1247. Version 2 gives significant improvements over version 1. It is classless and supporting VLSM and CIDR. It the same time the IETF chose Open Shortest Path First (OSPF) as their recommended interior gateway protocol(IGP)
In 1998, version 2 was updated in RFC 2328; which remains the current RFC for OSPF. In 1999, OSPF version 3 was introduced in RFC 2740. It was created by John Moy, Rob Count; and Dennis for IPv6. In 2008, OSPFv3 has updated in RFC 5340 as OSPF for IPv6.
Features of Open Shortest Path First (OSPF)
The Open Shortest Path First (OSPF) has many features included:
Classless– OSPF is classless by design, so, it supports VLSM and CIDR.
Fast convergence– it is fast convergence and quickly propagates network changes.
Efficient– OSPF has no periodic update, it only triggers routing updates on the event. It uses the SPF algorithm to choose the best path.
Scalable– It works well both in small and large networks. We can group the routers into areas to support a hierarchical system.
Secure– OSPF supports MD5 (Message Digest 5) authentication. When MD5 has enabled, routers only accept encrypted routing updates from peers with the same pre-shared password.
Trustworthiness – Administrative distance is the trustworthiness of the route source. Open Shortest Path First (OSPF) has a default administrative distance of 110 and preferred over IS-IS and RIP.
Components of Open Shortest Path First (OSPF)
OSPF uses smaller routing tables due to the segmentation of the entire network into smaller areas. The network segmentation into area enables better administration.
OSPF consists of a backbone Area “0”. The Area “0” links all other smaller areas within the hierarchy. The important components of an OSPF network are hardware components, areas, databases, Messages and algorithm:
Hardware Components
Hardware components are included area border router (ABR) and AS boundary router.
Area Border Routers (ABR)
ABR is a router located near the border between one or more one OSPF areas. It establishes a link between backbone networks and the OSPF areas.
AS Boundary Routers
It is a router exchanging routing information with non-OSPF networks. AS boundary routers advertise externally learned routes throughout the OSPF AS.
The AS Boundary Routers can also work as an ABR, backbone router or an internal router depending on the location. A router within a stub area cannot be an AS boundary router because the stub area cannot contain any type 5 LSAs.
OSPF Areas
In OSPF a single autonomous system (AS) can be divided into smaller groups. These smaller groups called areas. Areas reduce the number of LSAs and also reduce other overhead traffic sent on the network. The areas also reduce the topology database size maintaining each router.
Backbone Areas
The backbone area consists of all networks in area ID 0.0.0.0, including attached routing devices, and all Area Border Routers. It distributes routing information between areas. The backbone is itself an area, so the rules and terminology of an area also apply.
Stub Areas
Areas where AS external advertisements are not flooded called stub areas. Stub areas are shielded from external routes but receive information about networks that belong to other areas of the same OSPF domain
Routing devices within a stub area rely on the default routes originated by the area’s ABR to reach external AS destinations. The default-metric must be configured on the ABR before it advertises a default route.
The ABR advertises a default route in place of the external routes that are not being advertised within the stub area so that routing devices in the stub area can reach destinations outside the area.
Not-So-Stubby Areas (NSSA)
It enables the network administrator to configure OSPFv2 areas that provide the benefits of stub areas capable of importing external route information. These routes are then leaked into other areas. But, external routes from other areas still do not enter the NSSA.
Totally Stubby Area
This area filters out information of OSPF database on the bases of LSA types. An Area Border Router (ABR) in a Totally Stubby Area prevents LSA type 3, 4 and 5 to be flooded into a Totally Stub Area. It replaces all these types of LSA with a default route.
Transit Areas
The area through which we can configure the virtual link called transit area. The transit area must be in a position of full routing information. The transit area cannot be a stub area.
OSPF Databases
The OSPF databases including adjacency database, link-state database (LSDB) and forwarding database. The introduction to the databases are the following:
Adjacency database
OSPF adjacency database maintains the neighbour database. This database allows routers to exchange routing information. The routers must be neighbours, then they can become adjacent. Two routers only become adjacent if at least one of them is DR or BDR.
The database contains the list of all neighbours routers establishes bidirectional communication. The adjacent database table is unique for each router. We can view this database using “show ip ospf neighbor” command.
Link-state database (LSDB)
The LSDB creates the topology table for every area to which the router belongs. The router links advertisements; network links advertisements, and summary link advertisements are the components of LSDB.
The link-state database also maintains the list of all routers in the network. We can view LSDB using the “show ip ospf database” command.
Forwarding database
This database creates and lists the routing table of the router. Each router routing table is unique and containing information on how and where to send a packet to other routers. We can view the forwarding database using the “show ip route” command.
Routing Protocol Messages
OSPF exchange information between routers using different messages. The messages packet populates the routing table with the routing protocol’s choice of best paths.
These packets discover neighbouring routers and also to exchange routing information to maintain accurate information about the network. There are five types of messages packet in OSPF also illustrates in the figure below:
Hello packet
Link-state request packet
Database description packet
Link-state update packet
Link-state acknowledgement packet
Algorithm
The Open Shortest Path First (OSPF) is a link-state routing protocol and using the CPU processes the neighbour and topology tables using Dijkstra’s SPF algorithm. The SPF algorithm cumulative cost-based algorithm to reach a destination.
The SPF algorithm creates an SPF tree and calculates the shortest and the best path to each node. OSPF places the best routes into the forwarding database and makes routing table using the forwarding database.
The best route is the longest match route to the destination IP address. The route lookup process matches the destination IP address with the route available in the routing table and chooses the longest to match route as the forwarding route.
To match the destination IPv4 address of a packet with the routes in the routing table, the minimum number of far-left bits must match the IPv4 address of the packet and the route in the routing table.
The router found the best route in the routing table for the packet using the subnet mask. The data packet never contains the subnet mask in the packet header.
The best route is the longest match or the most significant number of equivalent far-left bits. The figure below illustrates the maximum bits match, which is the best route for the packet.
If the router receives a packet destined for 172.16.2.100, the router has three possible routes for the packet: 172.16.0.0/16, 172.16.1.0/24, and 172.16.2.0/24. Look at the table above in the figure to understand the most prolonged match routing process.
172.16.2.0/24 has the longest match, so the router has selected this route as the best route and forwards the packet to Ethernet 1/1. For any of these routes to be considered a match, there must be at least the number of matching bits indicated by the route’s subnet mask.
Routing Table Terms
The Cisco IP routing table is a hierarchical structure that speeds up the lookup process when locating routes and forwarding packets. Within this structure, the hierarchy includes:
Ultimate route
Level1 route
Level1 parent route
Level2 child routes
Ultimate Route
This route contains either a next-hop IPv4 address or an exit interface. Directly connected, dynamically learned, and local routes are also ultimate routes. The figure below illustrates the ultimate routes.
Level 1 Route
The route that is equal to a subnet mask or less than the classful mask of the network address. The source of the level 1 route can be a directly connected network, a static route, and a dynamic routing protocol. Therefore, a level 1 route is also the ultimate route. The type of level 1 route included:
Network route– A route with a subnet mask equal to the classful network is called a network route.
Default route– This is a static route for the packet whose destination is unknown to the router. The address of the default static route is 0.0.0.0/0.
Supernet route– This route has a network address with a maskless than the classful mask.
Level 1 Parent Route
The Level 1 parent route is a Level 1 network route that is subnetted. A parent route can never be an ultimate route. The figure below illustrates the level 1 parent route highlighted.
The level 1 parent route is the heading for the specific subnets. Each entry displays the classful network address, the number of subnets, and the number of different subnet masks.
Level 2 Child Route
This is a subnet of a classful network address. As illustrated in Figure 1, a level 1 parent route is a level 1 network route that is subnetted. A Level 1 parent route contains Level 2 child routes, as shown in the Figure below.
There are two level 2 child routes for level 1 parent route 10.0.0.0 and three level 2 child routes for level 1 parent route 172.16.0.0. The source of a level 2 route can be a directly connected network, a static route, or a dynamically learned route. Level 2 child routes are also ultimate routes.
Route Lookup Process
When a router receives a packet on an interface, the router examines the packet’s header, identifies the destination IPv4 address, and proceeds through the router lookup process.
Step-1
The router examines level 1 routes, network routes, and supernet routes for the best match with the destination address of the IP packet.
If the best match is a level 1, ultimate, or supernet route, the packet is forwarded to the destination using the best match route.
If the best match is a level 1 parent route, continue to the next step.
Step-2
The router examines level 2 child routes of the level 1 parent route for the best match.
If a match with a level 2 child route is found, the router forwards the packet to the destination using this route.
Continue to the next step if no match is found with any level 2 child routes.
Step-3
The router starts looking up the best match in level 1 supernet routes in the routing table, including the default route.
If there is now a minor match with a level 1 supernet or default route, the router uses that route to forward the packet.
The router drops the packet if a match to the destination is not found with any route in the routing table.
The routers are typically responsible for directing traffic across multiple networks. Each router maintains a list of known networks and directions calling routing table. The router performs a routing table entries lookup to find the proper interface that leads to the destination address. Each entry in a routing table is called a “route entry: or “route”.
The route identifies the destination network to which traffic can be forwarded. The destination network, in the form of an IP address and netmask, can be an IP network, subnetwork, supernet, or host. Routing table entries can originate from the following sources:
Directly connected networks
Dynamic routing protocols, such as EIGRP, OSPF, and RIP
Routes imported from other routers or virtual routers
Statically configured routes
Directly Connected Entries
When the router interface is configured with an IP address and the interface state is up and up, the directly connected route is automatically added to the router’s routing table.
Connected routes always precede static or dynamically discovered routes because they have the administrative distance value of 0 (the lowest possible value). The directly connected routes contain the following information.
Route source is the entry from where the route has been learned. C and L are two route source codes for directly connected routes. C identifies a directly connected network automatically created when an interface is activated and configured with an IP address. L identifies the local route created whenever an interface is configured with an IP address and activated. The L entry did not appear in routing table entries before IOS resale 15.
Destination network– This is the address of the destination network that also shows the connectivity.
The outgoing interface shows the exit interface for packet forwarding to the destination network.
Remote Route Source
A router stores information about both directly connected and remote routes. As with directly connected networks, the route source identifies how the route learned. Common codes for remote networks include:
S– This code Identifies an administrator’s static route to reach a specific network.
D– This code Identifies the dynamically learned route using the EIGRP routing protocol.
O– This code Identifies the dynamically learned route using the OSPF routing protocol.
R– This code Identifies the route learned dynamically from another router using the RIP routing protocol.
Remote Network Routing Table Entries
The figure below displays an IPv4 routing table entry for the route to remote network 192.168.0.0. We can identify the following information from this entry:
Route source– discussed earlier in this lesson.
Destination network– discussed earlier in this lesson.
Administrative distance– Identifies the trustworthiness of the route.
Metric– This is the value assigned to reach the remote network. Lower values indicate preferred routes.
Next hop– Identifies the IPv4 address of the next router.
Route timestamp– Identifies from when the route was last heard.
Outgoing interface– This is the outgoing interface towards the destination.
Only two routing protocols use link-state: Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS) share many similarities and differences. Both routing protocols provide the necessary routing functionality.
Open Shortest Path First (OSPF)
The Open Shortest Path First (OSPF) protocol is the most popular protocol that uses link-state. The Internet Engineering Task Force (IETF) designed OSPF in 1987. Currently, the OSPF has two working versions. OSPFv2 for IPv4 networks, as explained in RFC 2328, is an open standard. The second version is OSPFv3 for IPv6 networks, as stated in RFC 2740. The OSPFv3 also supports IPv4 addresses. Open Shortest Path First (OSPF) is an open standard that will run on most routers. Open Shortest Path First (OSPF) uses the Dijkstra algorithm to provide a loop-free topology. It provides fast convergence with triggered and incremental updates via Link State Advertisements (LSAs). It is also a classless protocol and allows for a hierarchical design with VLSM and route summarization.
Intermediate System to Intermediate System (IS-IS)
Intermediate System to Intermediate System (IS-IS) is an open standard routing protocol designed by the International for Standardization (ISO) and described in ISO 10589. It was initially designed for the Open System Interconnection (OSI) protocol suite and not for the TCP/IP protocol suite. Later, Integrated IS-IS, or Dual IS-IS, started providing support for IP networks. Though IS-IS is known as the routing protocol for Internet Service Providers(ISPs) and carriers, more enterprise networks are beginning to use IS-IS. The ISPs and carriers use IS-IS because of its scalability and strength. It is much easier than OSPF to build a large network. IS-IS carries a payload of reachability data, but for the most part, it doesn’t care what’s in the payload.
Link-state routing protocols have several advantages and disadvantages compared to distance vector routing protocols. This article will discuss these advantages and disadvantages.
Advantages of link-state
Fast Network Convergence—Fast network convergence is the main advantage of the link state routing protocol. On receiving an LSP, link state routing protocols immediately flood the LSP out of all interfaces without any changes except for the interface from which the LSP was received.
Topological Map—Link state routing creates the network topology using a topological map or SPF tree. Using the SPF tree, each router can determine the shortest path to each network separately.
Hierarchical Design—Link state routing protocols use multiple areas and create a hierarchical design for the network areas. The multiple areas allow better route summarization.
Event-driven Updates– After the initial flooding of LSPs, the LSPs are sent only when there is a change in the topology and contain only the information regarding that change. The LSP contains only the information about the affected link. The link state never sends periodic updates.
Disadvantages of Link State
The Link-state also has some disadvantages compared to distance vector routing protocols:
Memory Requirements—The link state routing protocol creates and maintains a database and SPF tree, which require more memory than a distance vector protocol.
Processing Requirements—Link state routing protocols require more CPU processing because the SPF algorithm requires more CPU time than distance-vector algorithms, like Bellman-Ford. After all, link-state protocols build a complete map of the topology.
Bandwidth Requirements–The link state routing protocol floods the link-state packet duringinitial startup and at events like network breakdown and network topology changes, affecting the network’s available bandwidth. If the network is not stable, it also creates issues with the bandwidth.
Link-state routing protocols are also known as shortest-path first protocols. They maintain a complete picture of all the routers running a link-state routing protocol in the complete network. All routers running a link-state routing protocol originate information about themselves and their directly connected routers, links, and the state of those links as multicast messages.
The link-state router tries to maintain complete network topology by updating itself whenever a change occurs. Link-state routing protocols are based on the Shortest Path First (SPF) algorithm to find the best path to a destination. The shortest Path First (SPF) algorithm is also known as the Dijkstra algorithm. The OSPF is an example of a Link-State Routing Protocol.
Link State Process
Following is the process of the link-state routing protocol. The process is the same for both OSPF for IPv4 and OSPF for IPv6.
Link and Link-State
Link and Link-state is the first step in the routing process. Each router learns about its links and directly connected networks. When a router interface is configured with an IP address and subnet mask and also in the state of no shutdown, it becomes part of that network. Refer to the topology in the Figure below. R3 has just been added to the network, and the IP addresses on the router interface are not configured yet; only the physical connectivity has been done. So, the router is not part of Link-State.
The network administrator now configured the IP addresses of the router interfaces connected to R2 and R5 and changed the state of interfaces from shutdown to no shutdown. As they become active, R3 learns about its own directly connected networks. Without any routing protocols, these directly connected networks are now entries in the routing table.
The router’s interfaces must be accurately configured with IP addresses and subnet masks, and the link must be in the state of no shutdown before the link-state routing protocol can learn about a link. Also, like distance vector protocols, the interface must be included in one of the network router configuration statements before participating in the link-state routing process.
Link-state routers have direct information from all their neighbor routers. Each router originates information about itself, its directly connected links, and the state of those links. This information is passed around the network from router to router, and each router makes a copy of it without changing it. So, every router gets identical information about the internetwork, and each router will independently calculate its best paths.
In the reference topology, the R3 link to its directly connected networks are:
FastEthernet 0/0 – 192.168.2.0/24
FastEthernet 0/1 – 192.168.3.0/24
The link-state information includes the following information:
The interface’s IPv4 address and subnet mask
The type of network, such as Ethernet or Serial link
The cost of that link
Any neighbor routers on that link
The link state of R3 is the following:
Link1
Network: 192.168.2.0/24
IP address: 192.168.2.1
Type of network: Ethernet
Cost of that link: 10
Neighbours: None
Link2
Network: 192.168.3.0/24
IP address: 192.168.3.1
Type of network: Serial
Cost of that link: 64
Neighbours: None
Hello Protocol
The second step in the link-state routing process is the responsibility of meeting with neighbors on directly connected networks. Routers with the link-state routing protocol use a Hello protocol for establishing and maintaining router-neighbor relationships. A neighbor is any other router enabled with the same link-state routing protocol. The link-state routing protocol uses Hello packets for neighbour discovery and also for recovery.
The protocol continues exchanging Hello packets between two adjacent neighbors and serves as a keep-alive function to monitor the neighbor’s state. Suppose any router stops receiving Hello packets from a particular neighbor. This neighbor is considered unreachable, so the link-state protocol clears this router from adjacency.
Now refer to Figure 1 above, R1 sends Hello packets to it’s all interfaces when the administrator configures it, to discover the link-state neighbours .R2, and R3 respond to the Hello packet with their own Hello packets as these routers have configured with the same link-state routing protocol as shown in figure 2. The FastEthernet 0/0 interface has no neighbors. So R1 did not receive any hello on this interface; therefore, it does not continue with the link-state routing process steps for the FastEthernet 0/0 link.
OSPF Hello Packet
After the primary exchange of Hello Packet, the routers add each other to their Neighbor Tables. The Neighbour table is the list of connected OSFP-enabled routers. Hello, packets are not recorded in the OSPF database, but if the hello packet has not been received from a particular neighbor for 40 seconds. The link-state routing protocol marked this particular neighbor as down. For example, OSPF will not take any notice if a link goes down for 20 seconds and again comes back to up status.
If a link goes down from a minute to half an hour, OSPF floods an LSA when it goes down and another LSA when it is up again. If a link is down for over half an hour, LSAs originated by remote routers begin to age out. When the link returns, all these LSAs will be flooded again. If a link is down for over an hour, any LSAs originated by remote routers will have aged out and been flushed. The link will be like a new OSPF route when it comes back up.
Building the Link State Packet (LSP)
The third step in the link-state routing process is building the link-state packet (LSP) containing the state of each directly connected link. It carries the information a network router generates in a link-state routing protocol that lists the router’s neighbors. It is a datagram determining the names of routers, including the cost or distance to any neighboring routers and linked local networks. It can also choose a new neighbor In case of link failure. The LSP also determines what the new neighbor is if a link fails and the cost of changing a link if required.
LSPs are queued for transmission and must time out at about the same time. The network is used to distribute the LSP but cannot use the routing database. When a router has established adjacencies to other routers, it can build its LSP containing the link-state information about its links. Now refer to the figure below. The LSP from R1 should contain the information like the following:
R1; FastEthernet network 192.168.0.0/24; Cost 1
R1 -> R2; Serial point-to-point network; 192.168.1.0/24; Cost 1
R1 -> R3; Serial point-to-point network; 192.168.3.0/24; Cost 1
Flooding LSP
After building the LSP, each router floods the LSP to all neighbours in the link-state routing process. This is the fourth step in the link-state routing process. The neighbor routers receive the LSP and save it in the database. All routers in the same routing area flood the link-state information to each other.
When a router receives the LSP from any of its interfaces, then the receiving router immediately sends that LSP out to all interfaces except the receiving interface. This process continues from router to router in the same area until all routers receive the LSP. When flooding LSP is completed then the link-state routing protocol calculates the SPF algorithm, thus the link-state routing convergence speed is very high.
The routers do not send LSPs periodically like the hello packet. They are only sent during the initial startup of the routing protocol on the router. After that, the LSPs are needed to flood when network changes occur in the topology. They are also required when a network breakdown occurs or after the network comes back.
The LSPs also included information, such as sequence numbers and aging information, to help manage the flooding LSP process. Each router uses this information to determine if it has received the LSP from another router or has new and updated information than the LSP already contained in the link-state database. This process allows a router to keep only the most current information in its link-state database. Suppose we discuss the topology in the previous lesson, building the Link State Packet. The R1 will flood the LSP packet to all its interfaces containing the following data.
R1; FastEthernet network 192.168.0.0/24; Cost 1
R1 -> R2; Serial point-to-point network; 192.168.1.0/24; Cost 1
R1 -> R3; Serial point-to-point network; 192.168.3.0/24; Cost 1
Building the SPF Tree
The routers in the same area use the link-state database and SPF algorithm to build the SPF tree. For example, in the figure below, R1 builds the SPF tree using the link-state information from all other routers. The SPF algorithm reads the router’s LSP to recognize networks and the link’s costs.
In the first step, R1 identifies its directly connected networks and their costs. After identifying the directly connected network, R1 begins identifying unknown networks from R2 and R3. Then, the SPF algorithm calculates the shortest paths to reach each network.
The SPF algorithm then calculates the shortest paths to reach each network. Each router in the area builds its own SPF tree separately from all other routers. To ensure accurate routing, the link-state databases used to construct those trees must be identical on all routers.
Building the Link-State Database
Link-state database building is the last step in the link-state routing process. Each router in the link-state uses the database to build a complete map of the topology and computes the best path to each destination network. All routers receive LSPs from every other link-state router in the same routing area. the
These LSPs are stored in the link-state database. Each router maintains a separate link-state database for every area to which it belongs, in case more than one area is configured in the network. The link-state database is also referred to as the topological database, and routers belonging to the same area have the same topological database for the area.
The databases for each area always process separately and calculate the link-state shortest path separately for each area and the topological database. The shortest path is flooded throughout the respected area only. The area database build of router links advertisements, network links advertisements, and summary link advertisements included external routes in all non-stub area databases.
Summary of Link-State Process
Every router in an OSPF area will complete the following link-state process to exchange a state of convergence:
Each router learns about its own directly connected networks and Links by detecting the interfaces in the upstate.
All routers are responsible for “saying hello” to their neighbors on directly connected networks.
Each router builds a Link-State Packet (LSP) containing the state of each directly connected link—the LSP contains neighbor, neighbor ID, link type, and link bandwidth.
Each router floods the LSP to all neighbors. Those neighbors store all LSPs received in a database. They then flood the LSPs to their neighbors until all area routers have received them LSPs. Each router stores a copy of each LSP received from its neighbors in a local database.
Each router floods the LSP to all neighbors, storing all LSPs received in a database.
All routers use the database to build a complete topology map and calculate the best path to each destination network using Dijkstra’s Algorithm.
Important Term of Link-State Protocol
Topological database – It is a set of information collected from LSAs.
SPF algorithm– The shortest path first (SPF) algorithm is a calculate the SPF tree on the bases of information in the database.
Routing tables – A list of the known paths and interfaces.
LSA – A link-state advertisement (LSA); is a small packet of routing information that is sent among routers. It is a basic communication way of the OSPF routing protocol for the Internet Protocol (IP). It communicates the router’s local routing topology to all other local routers in the same OSPF area.
LSP – It is a packet containing information generated by a network router in a link-state routing protocol that lists the router’s neighbours. It is a special datagram determining the names of routers including the cost or distance to any neighbouring routers and linked local networks. It can also determine the new neighbour In case of link failure.
The shortest path first protocol, or Link-state routing protocol, uses Edsger Dijkstra’s shortest path first (SPF) algorithm. Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS) are commonly used link-state routing protocols. Link-state routing protocols are more complex than the distance vector routing protocol. However, their basic functionality and configuration are just a sample. We can configure the basic Open Shortest Path First (OSPF) routing protocol using the following command.
Router(config)#router ospf <process-id>
Router(config-router)#network <network ID>
Dijkstra’s Algorithm
Dijkstra’s algorithm was published in 1959, and the creator’s name was Edsger Dijkstra, so it was named after its creator. OSPF(Open Shortest Path First) and IS-IS (Intermediate System-to-Intermediate System )protocols use Dijkstra’s algorithm to calculate the best path for a source to destination. Dijkstra’s algorithm is usually called the shortest path first (SPF) algorithm. The algorithm uses the addition of cost beside each path, from source to destination, to determine the total cost of a route. The route with the lowest price is considered the best route, and the route with the highest cost is regarded as the worst.
Shortest Path First Protocol (SPF) Example
The link between each router is labelled in the figure below with a cost value. There are three paths from R1 LAN to R6 LAN and vice versa. The figure shows that the lowest cost is 37, so this is the shortest path for sending data between LAN R1 and LAN R6. Each router containing the SPF (Shortest path first) Algorithm determines its own cost to each destination in the topology.
If you notice that path 2 has the least hop count, but the shortest path is path 3; the cost to reach R2 to R5 is 20 and higher than the cost from R2 to R5 through R4, which is 11.
IPv6 Routing Information Protocol (RIP), also known as RIPng (RIP Next Generation), supports IPv6 addresses. It is a Distance Vector routing protocol that uses a hop count as a routing metric. After enabling IPv6 RIP, we also need to configure the advertisement of IPv6 RIP routes. We can display IPv6 RIP settings to verify the configuration of RIPng.
It is helpful as a foundation for understanding basic network routing. Now, examine the reference topology in the figure. In this topology, all routers’ basic configurations have been completed, and all router interfaces have been configured and enabled. However, there are no dynamic routing and static routes configured on the routers, so remote network access is currently not possible.
The IPv6 unicast routing must be configured on all routers before configuring an IPv6 route to forward IPv6 packets. In the RIPv2, we enable RIP on the router configuration mode only, but RIPng is needed to allow for on each interface of the router on interface mode. There is no <network network-address> command available in RIPng.
Configuration
So, let’s come to the above topology configuration. As I said earlier, all basic configuration and IP address configuration on router interfaces has been done, so we only now require the configuration of RIP next-generation on all interfaces:
Router0
Router1
Enable IPv6 unicast-routing on Router2, Router3, Router4, and Router5 and configure all RIPng interfaces using command <IPv6 rip fschubRIPng enable> command.
Propagate Default IPv6 Route
The default IPv6 static route propagating process in RIPng is equal to RIPv2, except that an IPv6 default static route must be specific. The command for propagating a default static IPv6 route is the following:
The IPv6 route is the global configuration mode command, and the IPv6 rip is the interface mode command.
Verifying the RIPng Configuration
We can verify and examine the configuration using the show ipv6 protocol command, but the amount of information, as it is for its IPv4 counterpart, is not the same. However, we can confirm the following parameters using the command:
RIPng is configured on the router and also running.
The interfaces where RIPng is enabled.
We can also use the show ipv6 route command to display the routing table information, as shown in Figure. The output can confirm the IPv6 routes installed in the routing table.
Examine the routing table to see the hop count from Router0 to Router2. Notice that Router0 has two hops for the Router2 network if we configure RIPv1 or RIPv2 for the same Router2. The hop count will be one. This is because the IPv4 routing count of the next-hop router is the first hop, but the RIPng count of the sending router is the first hop.
