Link-state is most used routing protocol, therfore the link-state operation is very important for the networking student. In this article we are discussing the link-state operation. Link State Routing protocols reduce broadcast traffic as they do not send any periodic updates. It also not sends entire routing tables with each broadcast. Link state only exchange entire routing tables during initialization. After initialization routing updates are only multicast when a change has occurred. It is also send 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 update.
The event triggered updates improve network convergence time because on event required router sends an update message right away. The event such as new link installation, or an existing link failing or removing triggered link-state update. When link-state changes occurs, the
The link state protocols support VLSM, which enable 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 table called databases: The Adjacency database, Link State database and Forwarding database. To maintain routing information, OSPF routers done the following generic link-state operation to achieve a state of convergence:
Establish Neighbor Adjacencies
All OSPF enabled routers establish Neighbor Adjacencies and relationship with one another. The OSPF enabled routers must recognize each other on the network before they can share information with each others. Adjacent routers make this relationship using the exchange of hello packet. The OSPF enable routers sends hello packet out to all OSPF enabled interfaces as shown in the figure below. The routers build the adjacency table using these hello packets. Within hello messages packet 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 advertisement (LSAs). LSAs contain the state of the router and cost of each directly connected link. Each router flood their LSA to adjacent neighbors. The adjacent neighbors which receive the LSA, immediately flood the LSA to other directly connected neighbors without any changes, the process is continoues 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 exchange of LSAs each router builds a topology table or link-state database (LSDB) placing themselves in the root position. This database holds all the information about the topology of the network.
After building a Link-State database on all the routers the routing protocol execute the SPF Algorithm (Dijikstras algorithm) The SPF algorithm creates the SPF tree for each router on the bases of LSDB. The SPF tree included the each possible path to the destination with its cost. The figure below illustrates the SPF tree.
From the SPF tree, the best paths are inserted into the routing table also known as forwarding database and the router made routing decisions on the bases of 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 […]
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 match route as forwarding route. To match the destination IPv4 address of a packet with the routes in the routing table; […]
When a router receives a packet on an interface, the router examines the header of the packet and identifies the destination IPv4 address, and proceeds through the router lookup process. Step-1 The router examines level 1 route, as well as network routes and supernet routes; for the best match with the destination address of the […]
The Cisco IP routing table is a hierarchical structure that is used to speed 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 […]
The routers are typically responsible for directing traffic across multiple networks. Each router maintains a list of known network and directions calling routing table. The router performs a routing table lookup to find the proper interface that leads to the destination address. Each entry in a routing table called a “route entry: or “route”. The […]
There are 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 also have many differences. Both routing protocols provide the necessary routing functionality. Open Shortest Path First (OSPF) The Open […]
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 also computes the best path to each destination network. All routers receive LSPs from every other link-state router in the same routing area. These LSPs stores in […]