Routing: Open Shortest Path First
What is OSPF?
Open Shortest Path First (OSPF) is a link state routing protocol. It is used to allow routers to dynamically learn routes from other routers and to advertise routes to other routers. Advertisements containing routes are referred to as Link State Advertisements (LSAs) in OSPF.
OSPF router keeps track of the state of all the various network connections (links) between itself and a network it is trying to send data to. This makes it a linkstate routing protocol. OSPF supports the use of classless IP address ranges and is very efficient.
OSPF uses areas to organize a network into a hierarchal structure; it summarizes route information to reduce the number of advertised routes and thereby reduce network load and uses a designated router (elected via a process that is part of OSPF) to reduce the quantity and frequency of Link State Advertisements. OSPF does require the router have a more powerful processor and more memory than other routing protocols.
OSPF selects the best routes by finding the lowest cost paths to a destination. All router interfaces (links) are given a cost. The cost of a route is equal to the sum of all the costs configured on all the outbound links between the router and the destination network, plus the cost configured on the interface that OSPF received the Link State Advertisement on.
What are the different tables in OSPF?
There are three tables in OSPF same like in EIGRP:
- OSPF Neighbors table
- OSPF Topology table
- OSPF Routing table
OSPF Topology table: In OSPF, each router has a full road map of its entire area. All such information in OSPF is stored in
OSPF topology table. The difference between OSPF and EIGRP topology table is that EIGRP only know about it connected neighbor where as OSPF has full road map of entire area. You can view the topology structure on a Cisco router by following command:
router#show ip OSPf 1 database
OSPF Routing table:
Can you explain different areas in OSPF?
OSPF areas are used to impose a hierarchical structure to the flow of data over the network. A network using OSPF will always have at least one area and if there is more than one area, one of the two areas must be the backbone area. OSPF has only 2 levels to its hierarchy, the backbone, and all other areas attached to it. Areas are used to group routers into manageable groups that exchange routing information locally, but summarize that routing information when advertising the routes externally. A standard OSPF network looks something like a big bubble (the backbone area) with a lot of smaller bubbles (stub areas) attached directly to it. Area Border Routers (ABR) are used to connect the areas. Each area will elect a designated router (DR) and a backup designated router (BDR) to assist in flooding Link State Advertisements (LSAs)throughout the area.
Backbone (Area 0)
The backbone is the first area you should always build in any network using OSPF and the backbone is always Area 0 (zero). All areas are connected directly to the OSPF backbone area.
Totally Stub Area
A totally stubby area is only connected to the backbone area. A totally stubby / totally stub area does not advertise the routes it knows. It does not send any Link State Advertisements. The only route a totally stub area receives is the default route from an external area, which must be the backbone area. This default route allows the totally stub area to communicate with the rest of the network.
Stub areas are connected only to the backbone area. Stub areas do not receive routes from outside the autonomous system, but do receive the routes from within the autonomous system, even if the route comes from another area.
Frequently, it is advisable to use a separate network to connect the internal enterprise network to the Internet. OSPF makes provisions for placing an Autonomous System Boundary Router (ASBR) within a non-backbone area. In this case, the stub area must learn routes from outside the OSPF autonomous system. Thus, a new type of LSA was requiredthe Type 7LSA. Type 7 LSA's are created by the Autonomous System Boundary Router and forwarded via the stub area's border router (ABR) to the backbone. This allows the other areas to learn routes that are external to the OSPF routing domain.
Virtual links are used when you have a network that must be connected to an existing OSPF system, but cannot be physically connected directly to the routers in the OSPF backbone area. You can configure an OSPF virtual link from the area to a backbone router, creating a virtual direct connection to the backbone area. This virtual link acts as a tunnel which forwards LSAs to the backbone via a second intermediate area.
Can you explain different router types in OSPF?
- Internal - Routers which have all interfaces in a single area
- Backbone routers - Routers with at least one interface in area 0
- Area Border Routers (ABRs) - Routers with at least two interfaces in different areas
- Autonomous System Boundary Routers (ASBR) – Routers which redistribute information from an external source.
Routers can fill multiple roles simultaneously (e.g. act as both a backbone router and an area border router).
Can you explain Designated Router and Backup designated router?
In the election process, adjacency is the next step after the neighboring process. Adjacent routers are routers that go beyond the simple Hello exchange and proceed into the database exchange process. In order to minimise the amount of information exchanged on a particular segment, OSPF elects one router to be a designated router (DR) and one router to be a backup designated router (BDR) on each multi-access segment.
The BDR is elected as a backup router in case the DR goes down. The idea behind this is that routers have a central point of contact for information exchange. Instead of each router exchanging updates with every other router on the segment, every router exchanges information with the DR and BDR. The DR and BDR then relay the information to everybody else.
Can you explain different router states in OSPF?
Down: This is the first OSPF neighbor state. It means that no information (hellos) has been received from this neighbor, but hello packets can still be sent to the neighbor in this state. During the fully adjacent neighbor state, if a router doesn't receive hello packet from a neighbor within the RouterDeadInterval time (RouterDeadInterval = 4*HelloInterval by default) or if the manually configured neighbor is being removed from the configuration, then the neighbor state changes from Full to Down.
Attempt: This state is only valid for manually configured neighbors in an NBMA environment. In Attempt state, the router sends unicast hello packets every poll interval to the neighbor, from which hellos have not been received within the dead interval.
Init: This state specifies that the router has received a hello packet from its neighbor, but the receiving router's ID was not included in the hello packet. When a router receives a hello packet from a neighbor, it should list the sender's router ID in its hello packet as an acknowledgment that it received a valid hello packet.
2Way: This state designates that bidirectional communication has been established between two routers. Bidirectional means that each router has seen the other's hello packet. This state is attained when the router receiving the hello packet sees its own Router ID within the received hello packet's neighbor field. At this state, a router decides whether to become adjacent with this neighbor. On broadcast media and non-broadcast multiaccess networks, a router becomes full only with the designated router (DR) and the backup designated router (BDR); it stays in the 2way state with all other neighbors. On Point-to-point and Point-to-multipoint networks, a router becomes full with all connected routers.At the end of this stage, the DR and BDR for broadcast and nonbroadcast multi-access networks are elected. For more information on the DR election process, refer to DR Election.Note: Receiving a Database Descriptor (DBD) packet from a neighbor in the init state will also a cause a transition to 2way state.
Exstart: Once the DR and BDR are elected, the actual process of exchanging link state information can start between the routers and their DR and BDR. In this state, the routers and their DR and BDR establish a masterslave relationship and choose the initial sequence number for adjacency formation. The router with the higher router ID becomes the master and starts the exchange, and as such, is the only router that can increment the sequence number. Note that one would logically conclude that the DR/BDR with the highest router ID will become the master during this process of masterslave relation. Remember that the DR/BDR election might be purely by virtue of a higher priority configured on the router instead of highest router ID. Thus, it is possible that a DR plays the role of slave. And also note that master/slave election is on a per neighbor basis.
Exchange: In the exchange state, OSPF routers exchange database descriptor (DBD) packets. Database descriptors contain linkstate advertisement (LSA) headers only and describe the contents of the entire linkstate database. Each DBD packet has a sequence number which can be incremented only by master which is explicitly acknowledged by slave. Routers also send linkstate request packets and linkstate update packets (which contain the entire LSA) in this state. The contents of the DBD received are compared to the information contained in the routers linkstate database to check if new or more current linkstate information is available with the neighbor.
Loading: In this state, the actual exchange of link state information occurs. Based on the information provided by the DBDs, routers send linkstate request packets. The neighbor then provides the requested linkstate information in linkstate update packets. During the adjacency, if a router receives an outdated or missing LSA, it requests that LSA by sending a linkstate request packet. All linkstate update packets are acknowledged.
Full: In this state, routers are fully adjacent with each other. All the router and network LSAs are exchanged and the routers' databases are fully synchronized. Full is the normal state for an OSPF router. If a router is stuck in another state, it's an indication that there are problems in forming adjacencies. The only exception to this is the 2way state, which is normal in a broadcast network. Routers achieve the full state with their DR and BDR only. Neighbors always see each other as 2way.
Can you explain different OSPF packet types?
- Hello - Used to establish communication with directly connected neighbors
- Database Descriptor (DBD) - Lists router IDs from which the router has an LSA and its current sequence number
- Link State Request (LSR) - Request for an LSA
- Link State Update (LSU) - Reply to an LSR with the requested information
- Link State Acknowledgment (LSAck) - Used to confirm receipt of linkstate information
What are the different types of OSPF timers?
The OSPF Hello Interval and Router Dead Interval are two timers that maintain the up/down state of OSPF neighbor relationships. They are among the variables that must match in order for an OSPF neighbor relationship to be established.
- Hello Interval: determines the interval between sending OSPF Hello messages on an interface
- Dead Interval: is the interval in which a router must receive an OSPF Hello message from a neighbor before it considers that neighbor to be down.
The HelloInterval and RouterDeadInterval are the two timers that you can adjust to speed up network convergence in an OSPF network.
Cisco IOS assigns a default HelloInterval and RouterDeadInterval to OSPF enabled interfaces.
Depending on the interface type, the HelloInterval will be either 10 seconds or 30 seconds.
The RouterDeadInterval will be four times the HelloInterval (40 or 120 seconds). A Cisco OSPF enabled device will maintain a count down timer for each neighbor based on the RouterDeadInterval. Each time receives a Hello message from a neighbor, it will reset this timer to the RouterDeadInterval. If it does not receive a Hello message before this timer expires, then the neighbor will be set to the OSPF DOWN state.
You can adjust the HelloInterval and RouterDeadInterval with the ip ospf hellointerval and ip ospf deadinterval interface configuration commands. Doing so can reduce OSPF convergence, but you should be careful to take into consideration the quality (and possibly speed) of your links before doing so.
How SPF algorithm does the route determination?
The key data structure maintained by each router in an OSPF autonomous system (AS) is the linkstate database (LSDB). The LSDB contains a representation of the topology of either the entire AS (in basic topology) or a single area (in hierarchical topology). As we have seen earlier in this section, each router in the AS or area has the same LSDB, so it represents a neutral view of the connections between routers and networks. Of course, each router needs to participate in keeping the LSDB up to date, but it also has its own “selfish” concerns. It needs to be able to determine what routes it should use for datagrams it receives from its connected networks—this is, after all, the entire point of a routing protocol.
The SPF Tree
To find the best route from any router, it must determine the shortest path between itself and each router or network in the AS or area. For this, it needs not a neutral view of the internetwork but a view of it from its own perspective. The router creates this perspective by taking the information in the LSDB and transforming it into a shortest path first tree or SPF tree. The term “tree” refers to a data structure with a root that has branches coming out that go to other nodes, which in turn have branches. The structure as a whole looks like an upsidedown tree. In this case, the SPF tree shows the topology information of the AS or area with the router constructing the tree at the top. Each directlyconnected router or network is one step down in the tree; each router or network connected to these firstlevel routers or networks is then connected, and so on, until the entire AS or area has been represented.
Again, the router doesn't really make the tree; it is just an algorithmic calculation performed by the computer within the router. Once this is done, however, this logical construct can be used to calculate the cost for that router to reach any router or network in the AS (or area). In some cases, there may be more than one way to reach a router or network, so the tree is constructed to show only the shortest (lowest cost) path to the network.
Of course, each router is only responsible for sending a datagram on the next leg of its journey, and not for what happens to the journey as a whole. After the SPF tree is done, the router will create a routing table with an entry for each network, showing the cost to reach it, and also the next hop router to use to reach it.
The SPF tree is created dynamically based on the current state of the LSDB. If the LSDB ever changes, the SPF tree and the routing information are recalculated.