Menu

August 2019

Introduction and Exclusive Explanation of OSPF Operation

Introduction and Exclusive Explanation of OSPF Operation

/ /

If the router interface is configured with OSPF, the router must determine if another OSPF neighbor is on the link. To do this, the router forwards a Hello packet containing its router ID to all OSPF-enabled interfaces as multicast. The Open Shortest Path First process uses the router ID to recognize every router individually in the OSPF area.

A router ID is an IP address assigned to identify a specific router among OSPF links. When a neighboring router configured with Open Shortest Path First receives a Hello packet containing a router ID that is not listed with the receiving router, it attempts to establish an adjacency with the initiating router.

OSPF

For example, as shown in figure-1 above, when OSPF is enabled on Rouer1, the enabled Fast Ethernet 0/1 interface transitions from the Downstate to the Init state and starts sending Hello packets to all OSPF-enabled interfaces to discover OSPF neighbors with whom to develop adjacencies.

The Router2 receives the Hello packet from Router1 and adds the Router1 ID to its neighbor list. Then, Router2 sends a Hello packet to Router1. The packet contains the Router2 Router ID, including the Router1 ID in its neighbors’ list on the same interface.

When Router1 receives the Hello packet and adds the Router2 Router ID to its OSPF neighbors list, Router1 also notices its Router ID in the Hello packet’s list of neighbors. When Router1 receives a Hello packet with its Router ID listed in the neighbor’s list, it transitions from the Init state to the Two-Way state.

The action in a Two-Way state depends on the type of interconnection between the adjacent routers. If the two adjacent neighbors are connected over a point-to-point link, they instantly transition from the Two-Way state to the database synchronization stage. A DR and BDR must be elected if the routers are interconnected over a general Ethernet network.

Note: Hello packets are repeatedly exchanged to maintain router information.

DR and BDR Election

A DR and BDR election occurs because Router1 and Router2 are connected over an Ethernet network. The figure below illustrates the election between Router1 and Router2.

Router2 becomes the DR because of the highest router ID (192.168.10.2), and Router1 becomes the BDR because of the second-highest router ID (192.168.10.1). This process only takes place on multi-access networks such as Ethernet LANs.

DR and BDR election is necessary because multi-access networks can create two challenges for OSPF about the flooding of LSAs:

  • Creation of multiple adjacencies – The routers on Ethernet networks interconnect to many Open Shortest Path First routers over a common link. So, creating adjacencies with every router is not important and wanted. The interconnection to many routers leads to an unnecessary number of LSAs exchanged between routers on the same network.
  • Extensive flooding of LSAs – Link-state routers flood their LSAs when OSPF is initialized, or when there is a modification in the topology. This flooding can become very excessive.

Adjacencies formula

The formula for understanding the problem with multiple adjacencies is following:

n(n – 1) / 2

n is the number of the router in the OSPF topology. For example, if there are 4 routers in the topology, as shown in Figure 3, and all routers are attached to the same multi-access network, there are n (n– 1) / 2 adjacencies in the topology. Without a mechanism to reduce the number of adjacencies, collectively, these routers would form 6 adjacencies:

4 (4 – 1) / 2 = 6

This does not seem like too much, but as routers are added to the network, the number of adjacencies increases dramatically, as shown in the calculation below.

10 routers = 10(10-1) = 45 adjacencies

20 routers = 20(20-1) = 190 Adjacencies

50 routers = 50(50-1) = 1225 Adjacencies

100 routers = 100(100-1) = 4950 Adjacencies

To understand the problem of extensive flooding of LSAs, if DR and BDR are not available in the network When changing occurs in the network or during initializing. Each router sends LSA and also required acknowledgements are sent for every LSA received.

If every router in a multi-access network had to flood and acknowledge all received LSAs to all other routers on that same multi-access network, the network traffic would become quite confusing. Suppose there are 50 routers on the network without DR and BDR. Each router will send 1225 LSAs and receive 1225 Acknowledgments, which is very extensive.

The solution to managing the number of adjacencies and the flooding of LSAs on a multi-access network is the DR and BDR. OSPF elects a DR on multi-access networks as the collection and distribution point for LSAs sent and received. A BDR is also elected for the same purpose in case the DR fails. All other routers turn into brothers. A DROTHER is a router that is not a DR or the BDR.

Database Synchronization Stage

After the Two-Way state, routers transit to database synchronization stage. As the Hello packet used to launch neighbour adjacencies, the other four types of Open Shortest Path First packets has used in the process of exchanging and synchronizing LSDBs.

In the database synchronization stage, the first state is ExStart state, in this state a master and slave relationship created between each router and its adjacent DR and BDR. The router with the higher router ID acts as the master for the Exchange state. In Figure-4 below, Router2 becomes the master.

In the Exchange state, the master and slave routers exchange one or more DBD packets. A DBD packet also includes information about the LSA entry header in the router’s LSDB.

The entries can be about a network or a link, and each LSA entry header also includes information about the type of link state, the advertising router address, the cost of the link, and the sequence number. The sequence number determines the newness of the received link state information.

In Figure-5, Router2 sends a DBD packet to Router1, and Router1 receives the DBD packet and does the following actions:

  • It acknowledges the receipt of the DBD packet using the LSAck packet.
  • Sends DBD packets to Router2.
  • Router2 acknowledges Router1.

Router1 compares the received information with the information it has in its LSDB. If the DBD packet has a more current link-state entry, the router transitions to the Loading state. For example, in Figure 6, Router1 sends an LSR about network 192.168.20.0 to Router2 and Router2 reply with the complete information about 192.168.20.0 in an LSU packet.

On reception of LSU, Router1 sends an LSAck. Router1 then adds the new link-state entries into its LSDB. When all LSRs are fulfilled for a particular router, the adjacent routers are considered synchronized and in a full state.

If the neighboring routers continue receiving Hello packets, the network in the transmitted LSAs will stay in the topology database. After the topological databases get synchronized, Link-state updates are sent only to neighbors when:

  • A change is apparent
  • Every 30 minutes
Introduction to the Different OSPF States and Process

Introduction to the Different OSPF States and Process

/ /

When an OSPF router is initially connected to a network it completes the following generic link-state routing OSPF process and gets the state of convergence through changing different states. Before discussing OSPF states, I am going to discuss OSPF Process.

Create adjacencies with neighbours

OSPF configured router form adjacencies with their neighbours before share information with that neighbour. It sends Hello packets out all OSPF-enabled interfaces to resolve connected OSPF neighbours on those interfaces. If a neighbour is found, it attempts to establish neighbour adjacency with that neighbour.

Exchange routing information Using LSAs

When adjacencies are established between neighbours, then they exchange link-state advertisements (LSAs) with each other’s containing the state and cost of each directly connected link. Routers flood their LSAs to adjacent neighbours and adjacent neighbours receive the LSAs and flood it immediately to other directly connected neighbours until all routers in the area have all LSAs.

Build the topology table

After receiving the LSAs, OSPF-enabled routers build the topology table based on the received LSAs. It holds all the information about the topology of the network. All routers in the area must have the same information in the topology table.

Execute the SPF algorithm

Routers then execute the SPF algorithm. The SPF algorithm creates the SPF tree.

Calculate the best routes

After creating the SPF tree the router inserts the best path into the routing table. Routing decisions are made based on the entries in the routing table.

Reach convergence

This is the real OSPF state of the router which is required for the actual operation of the routing. The OSPF progresses through different OSPF states while attempt to reach convergence. The figure below illustrates the different OSPF states progress:

OSPF States

Downstate.

  • This is the OSPF state when the router is down.
  • When it is Power Up it sends Hello Packet
  • If the router is exciting to init state.

Init state

  • The state is another OSPF state when the router has just received the hello packet from the neighbours containing the sending router ID.
  • Transition to Two-Way State

Two-Way state

  • In the OSPF state, the route elect a DR or BDR on Ethernet links
  • Transition to ExStart State

ExStart state

  • Negotiate master / Slave relationship, also DBD packet sequence number
  • The master initiates the DBD packet exchange

Exchange state

  • In this state Routers Exchange DBD Packets.
  • In case of additional requirement of information router transit to loading state, otherwise, the transition to the full state.

Loading state

  • To gain more information router uses LSRs and LSUs.
  • The route is processed using the SPF algorithm
  • Transition to full state

Full state

  • This is the actual state which is required also know as a converged state.

[qsm quiz=14]

Introduction to Hello Packets

Introduction to Hello Packets

/ /

Hello, Packets Type 1 are OSPF packets sent periodically on all interfaces, including virtual links, to establish and maintain neighbor adjacency. It is a multicast packet with a multicast and broadcast capability, enabling dynamic discovery of neighboring routers. Hello packets advertise parameters on which routers agree to become neighbors. It also elects the Designated Router (DR) and Backup Designated Router (BDR) on multi-access networks. Point-to-point links do not require DR or BDR. The figure below illustrates the hello packet:

#image_title
  • Type—This is an eight-bit field that identifies the type of packet. It has three types: Type 1 indicates a Hello packet, Type 2 indicates a DBD packet, Type 3 indicates an LSR packet, Type 4 indicates an LSU packet and Type 5 is an LSAck packet.
  • Router ID—This is a 32-bit field expressed in dotted decimal notation that uniquely identifies the originating router.
  • Area ID– Area ID is also a 32 bit file that identifies the originated area of the packet.
  • Network Mask– Network mask associated with the sending interface

Note:– the above four fields are the part of OSPF header and the below six fields are the parts of OSPF hello Field.

  • Hello Interval– This field defines how often we send the hello packet. Hello interval also defines the frequency, in seconds, at which a router sends Hello packets. The default Hello interval on multi-access networks is 10 seconds. This hello-interval timer must be the same on neighbouring routers if not, an adjacency is not possible.
  • Router Priority– This field is used in a DR/BDR election. The default priority for all OSPF routers is 1 but we can also manually configure router priority from 0 to 255. The higher the value, the router becomes the DR on the link.
  • Dead Interval– This field defines how long we should wait for hello packets before declaring the neighbor dead and out of service. By default, the router Dead Interval is four times the Hello interval. This timer must be the same on neighboring routers; otherwise, an adjacency will not be established.
  • Designated Router (DR)– This is the Router ID of the DR.
  • Backup Designated Router (BDR)– This field defines the Router ID of the BDR.
  • List of Neighbors– This field identifies the router IDs of all adjacent routers.
How to Encapsulate OSPF Messages

How to Encapsulate OSPF Messages

/ /

Open Shortest Path First (OSPF) runs over the Internet Protocol’s network layer. So, Open Shortest Path First (OSPF) encapsulated only by IP and local data-link headers. Encapsulating OSPF messages transmitting over an Ethernet link contain the following information:

OSPF Messages

  • Data Link Frame Header– This header contains the destination multicast MAC addresses.
  • IP Packet Header–This header contains the IPv4 protocol field 89 indicates an OSPF packet. It also identifies one of two OSPF multicast addresses, 224.0.0.5 or 224.0.0.6.
  • OSPF Packet Header–This header shows the OSPF packet type and also show the router ID and the area ID.
  • OSPF Packet Type Specific Data– This header contains the OSPF packet type information
Explanation of OSPF Packets Types

Explanation of OSPF Packets Types

/ /

Open Shortest Path First (OSPF) uses link-state packets (LSPs) to establish and maintain neighbour adjacencies. It also uses LSPs to exchange routing updates. There are five different OSPF packets type. The beginning of all OSPF packets is specified by the standard header of 24 bytes. A list of link state advertisements is to deal with all OSPF packets type. The figure below illustrates the five different OSPF packets types. Each link-state packet (LSPs) serves a specific purpose in the OSPF routing process:

Hello packet– This packet establishes and maintains adjacency with other Open Shortest Path First (OSPF) routers. The Open Shortest Path First (OSPF) protocol sends these packets periodically on all interfaces. This is a multicast packet discovering neighbouring routers dynamically.

Database Description (DBD) packet– This packet has an abbreviated list of the sending router’s Link-state Database (LSDBs). The receiving routers used DBD to check against the local Link-state Database (LSDBs). The Link-state Database (LSDBs); must be equal on all link-state routers within an area to build a perfect SPF tree. The database is designed from multiple packets.

Link-State Request (LSR) packet – When receiving routers read the DBD then receiving router can request more information about any entry in the DBD, sending an LSR packet. The router uses LSR packets for requesting the pieces of the neighbour’s database which are more up to date and complete. The router can also send multiple Link State Request packets.

Link-State Update (LSU) packet – This packet is used to reply link-state request (LRS) packet. The link-state update (LSU) contain further seven types of packets.

Link-State Acknowledgment (LSAck) packet – When the router receives an LSU packet, it sends an LSAck packet to the sender router to confirm receipt of the LSU packet. The LSAck data field is empty. Single Link State Acknowledgement packet can acknowledge the multiple link state advertisements.

Introduction to Single-Area OSPF and Multi-Area OSPF

Introduction to Single-Area OSPF and Multi-Area OSPF

/ /

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.

single area

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.
Multi-Area OSPF

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:
  1. The maximum number of routers per area is 50.
  2. One router can join a maximum of three areas.
  3. The maximum number of neighbors for a single router is 60.
Link State Operation – Exclusive Explanation

Link State Operation – Exclusive Explanation

/ /

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.

link state

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

Link State Operation

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.

Introduction to Open Shortest Path First (OSPF)

Introduction to Open Shortest Path First (OSPF)

/ /

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

Open Shortest Path First

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.

Best Route, Routing Table Terms, and Lookup Process

Best Route, Routing Table Terms, and Lookup Process

/ /

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.

best route

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

  1. The router examines level 1 routes, network routes, and supernet routes for the best match with the destination address of the IP packet.
  2. If the best match is a level 1, ultimate, or supernet route, the packet is forwarded to the destination using the best match route.
  3. If the best match is a level 1 parent route, continue to the next step.

Step-2

  1. The router examines level 2 child routes of the level 1 parent route for the best match.
  2. If a match with a level 2 child route is found, the router forwards the packet to the destination using this route.
  3. Continue to the next step if no match is found with any level 2 child routes.

Step-3

  1. The router starts looking up the best match in level 1 supernet routes in the routing table, including the default route.
  2. If there is now a minor match with a level 1 supernet or default route, the router uses that route to forward the packet.
  3. The router drops the packet if a match to the destination is not found with any route in the routing table.
What is the Routing Table Entries

What is the Routing Table Entries

/ /

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.

Load More