1.0 OSPF routing protocol
1.1 What is Routing Protocols?
Routing protocol is used to gather routing entry information to route anything successfully
1.2 Distance Vector Vs Link-state Routing Protocols
1.3 OSPF Protocol
Link-state protocols receive link-state packet information and store it in a database local to the router. Each link-state router then calculates its own routing table to each destination in the network, based on the link-state costs. The mathematical algorithm which is Dijkstra (SPF) algorithm used to calculate the routing table [7].
1.4 OSPF Network Types
1.5 OSPF Router Types
1.6 OSPF Link-State Advertisement
1.7 Content of the OSPF Link-Sate Database
Link-Sate Database is a list of information about all other routers in the internetworking. All routers within an area have identical link-state database.
2.0 Steps of the OSPF operation
2.1 Establish routers adjacencies
Hello packets contain the following router information
Main steps of the Hello packets exchanged process
I. Router A is OSPF down state because it has not exchanged information with other routers. Router A sends hello packet to the network.
II. All other OSPF routers receive the hello packet and add router A to their adjacencies database. This is Init state.
III. All routers send a reply hello packet with their information. Neighbour field includes all other neighbouring routers.
IV. When Router receives these packets, it adds adjacencies database. This state is Two-way state.
V. Periodically the routers within a networks exchange hello packets to ensure communication. (By default 10 seconds)
4.5 Maintaining Routing Information.
1.1 What is Routing Protocols?
Routing protocol is used to gather routing entry information to route anything successfully
across the network. For this Router needs to know following key information:
· The destination of the packet that need to be routed.
· A routing entry for that destination. (This can include unknown default route)
Routing protocol uses a different method to gather information about available networks
and distance, or cost. Routing protocol can be classified into two main categories.
and distance, or cost. Routing protocol can be classified into two main categories.
1. Distance vector routing protocols – RIP, IPX, IPX RIP, AppleTalk RTMP, IGRP
2. Link-state routing protocols – OSPF,IPX NLSP, IS-IS
1.2 Distance Vector Vs Link-state Routing Protocols
Distance Vector | Link State |
Designed to use in smaller network environments | Designed for growing network environments |
Maintain list of the distance to another network in hops (number of routers crossed). It consider more than 15 hops as too far | Use a Link-speed-based metric to define the distance to another network. Maintains a map of the entire internetwork, allowing it to see alternative or parallel paths for load balancing. |
Identifying Neighbours | |
Does not have formal way of leaning about neighbours. | Establish a formal connection (Link – Sate) with each directly connected neighbour using hello packets. |
Detect changes only when three consecutive routing update is missing for a certain route for a specific period of time. | Detect changes when three hello packets are not received in a row |
Discovering Routers | |
Each router builds a routing table that includes its directly connected networks & sends it to its directly connected neighbours. Distance vector routers follow the split horizon algorithm to send out the routing table [4]. | Each router builds a link-state table that includes about the entries network. Normally router builds its table by determining what routes it has to each network and selecting the best route as the best path. |
The neighbour includes all routing table into its own routing table & send the update routing table to its neighbours. | Each router floods the information about the links and Each neighbouring router receives the update packet, copy the contents, & continue sending it. |
Selecting a Route | |
The typical metric used is to calculate the number of hopes on the path from the source to the destination. | Cost (a value base on the band width of the link) is use to calculate the best path. |
The lowest number of hops is the best path. Normally the maximum number of hops will be 15. Bellman Ford algorithm is used to choose the shortest path [5]. | The lowest total cost is the best path. The maximum possible cost is almost unlimited. Dijkstra algorithm (SPF) is used to select the lowest cost path. |
Maintaining Routing Information | |
The router updates its routing table with the changes and propagates it to other routers when router broadcast its update. | When the changers are available in the internetwork a router learns about it and updates its link-state table. Sends an update only about changed entries to all routers in the internetwork. |
Neighbouring routers include the new routing information into their routing table and broadcast it when their next update process occurs. | Each router receives the update and adds it to their link-state table. |
This process continues until all routers converge. | The routers then run the SPF algorithm to determine the best paths. |
If there is no change in the internetwork at a periodic interval (usually 60 seconds), each router sends out its routing table to its neighbours [6]. | If no change occurs in the internetwork, the routers will send updates only for those route entries that have not been updated periodically-from 30 minutes to two hours-depending on the routing protocol. |
Open Shortest Path First (OSPF) protocol was developed due to a need in the internet community to introduce a high functionality non-proprietary Internal Gateway Protocol (IGP) for the TCP/IP protocol family. OSPF was designed to overcome the limitations of RIP, which included limited scalability, slow convergence, and vulnerability to routing loops. Furthermore OSPF routing protocol is a Link State protocol based on cost rather than hops. It is not a vector based routing protocol. OSPF has introduced new concepts such as authentication of routing updates, Variable Length Subnet Masks (VLSM), route summarization, and so on.
Link-state protocols receive link-state packet information and store it in a database local to the router. Each link-state router then calculates its own routing table to each destination in the network, based on the link-state costs. The mathematical algorithm which is Dijkstra (SPF) algorithm used to calculate the routing table [7].
1.4 OSPF Network Types
There are three types of network connection for the OSPF routing protocol:
· Point-to-point
Point-to-point network type is where neighbour relationships are formed only with the other router on the point-to-point. Both routers can communicate with all other OSPF routers independently.
For example: ISDN or TI connection.
· Broadcast multiaccess
In a Broadcast multiaccess network, First routers perform the hello process and then select the Designated Router (DR) and Backup Designated Router (BDR). These routers communicate with all other OSPF routers in the LAN network. But BDR does not perform any DR function and it receives only all the information when DR is operating. If DR fails BDR perform the DR task and BDR automatically becomes the DR and a new BDR selection occurs.
DR router shares learned information with other local routers. Neighbour relationships are formed based on a dynamic learning process using multicast Hello packets. DR performs the LSA forwarding
and LSDB synchronization tasks.
and LSDB synchronization tasks.
For example: Ethernet network segment.
§ Packets to the DR and the BDR use 224.0.0.6
§ Packets from DR to the all other routes use 224.0.0.5 [8]
· Nonbroadcast multiaccess
Nonbroadcast multiaccess network is a network where all routers might not communicate with other OSPF routers. Because multicasts are not available in a nonbroadcast environment (for example, Switched Multimegabit Data Service (SMDS) environment). Neighbour relationships are usually formed by a manual configuration process or some other configuration.
For example: Frame Relay, ATM, and X.25
[9]
[9]
1.5 OSPF Router Types
OSPF routers are categorized based on the function they perform in the routing domain. There are four classes of OSPF router types:
· Internal OSPF Router
Routers that have all their interfaces in the same area and have identical Link-state databases (LSDBs). (Also includes routers with only backbone interfaces.)
· Area Border Router (ABR)
ABR is a router that attaches to multiple areas, including area 0. It is between routers of the area. These routers maintain separate LSDBs for each area to which they are connected, and router traffic
destined for or arriving from other areas.
destined for or arriving from other areas.
ABRs summarize information from their link-state databases of their attached areas and distribute information into the backbone area 0. The backbone ABRs then forward the information to all other connected areas. An area can have one or more ABR. [10]
· Backbone Router (BBR)
Routers that are on the edge of the backbone area and have at least one interface connected to area 0. Backbone routers maintain OSPF routing information using the same procedures and algorithms as internal routers.
· Autonomous System Boundary Router (ASBR)
Routers that have at least one interface into another autonomous system such as a non- OSPF network. These routers can redistribute non – OSPF network information to the OSPF network, and vice-versa.
Following diagrams shows various types of routers.
Internal Routers – A, F, G, H (These routers are completely within an area and do not interconnect to any other area or autonomous system (AS)
Backbone Routers – A, B, C, D, E
Area Border Routers – A, D, E (ABRs attach all other areas to area 0)
OSPF routers communicate link status changes with link-state advertisement (LSAs). LSAs are the building blocks of the OSPF LSDB. Individually, they act as database records. In combination, they describe the entire topology of an OSPF network or area. LSAs are always recognized and tagged with a sequence number.
All LSA types have 20-byte headers. One of the LSA header fields is the link-state ID. The link-state ID of the type 1 LSA is the originating router ID.
Different types of LSAs
· Type 1 LSA- Router links advertisement
- Contains information about the sending router’s links to neighbour routers.
- These are only flooded within a particular area.
- Includes list of all directly connected links.
· Type 2 LSA - Network links advertisement
- Contains list of routers connected to a network segment.
- Generated by the designated router in a multiaccess network, such as Ethernet.
- Flooded within the area that contains the network only (Does not cross ABR).
· Type 3 or 4 LSA - Summary links advertisement
-Describe networks reachable from outside the area.
-Describe the links between the ABR and the internal routers of a local area.
- Flooded throughout the backbone area to the other ABRs.
-Type 3 is sourced by sourced by ABR and type 4 is source by ASBRs.
· Type 5 - External links advertisement
-Describe routes to destination in another AS or separate routing process (External to the AS).
-Describe routes to destination in another AS or separate routing process (External to the AS).
-Originate by the ASBR [11]
show ip ospf database can be used to display OSPF LSDB. It contains following information.
- Link ID: Identifies each LSA.
- ADV Router: Advertising router; the source router of the LSA.
- Age: The maximum age counter in seconds. The maximum age is 1 hour, or 3,600 seconds.
- Seq#: Sequence number of the LSA. This number begins at 0x80000001 and increases with each
update of the LSA. - Checksum: Checksum of the individual LSA to ensure reliable receipt of that LSA.
- Link count: Total number of directly attached links, used only on router LSAs. The link count includes all point-to-point, transit, and stub links. Each point-to-point serial link counts as two; all other links count as one, including Ethernet links. [12]
A broadcast multiaccess network has a designated router (DR) and a backup designated router (BDR).
The DR sends LSA instead of all the routers on the muiltiaccess network. The designated router is a connection point for LSAs for a given broadcast network (that is, it gets an LSA via a multiaccess network then forwards it out)
The BDR will automatically become the DR in the event that the DR fails or becomes unreachable. Each area router forms an adjacency to both the DR and BDR. Neighbour routers regularly exchange Hello messages to verify reachability. This frequency is determined by the Hello interval, which defaults to 10
seconds. Increasing this interval time is sometimes important over high congested links because if there is high traffic on a given link, you may miss ‘hello messages because they are sent too frequently. The smaller Hello
interval, the faster topological changes will be detected, but more Hello traffic will fill up the links.
seconds. Increasing this interval time is sometimes important over high congested links because if there is high traffic on a given link, you may miss ‘hello messages because they are sent too frequently. The smaller Hello
interval, the faster topological changes will be detected, but more Hello traffic will fill up the links.
The designated router has highest priority number. The router with the next highest priority is the BDR. The router with a priority of 0 cannot become a DR or a BDR. The OSPF priority for each interface is a numeric value, set to 1 by default. In a case of a tie, the Router ID is used as a tie breaker. The router with the highest ID number becomes the DR.
Generally, DR/BDR will be the most powerful (memory, CPU, and so on) router on the broadcast network. Therefore other routers that you want not to be the DR/DBR to have an OSPF priority set to 0 on each interface.
Priority can be set with the ip ospf priority interface command.
2.0 Steps of the OSPF operation
1. Establish routers adjacencies
2. Elect a DR and a BDR
3. Discover routes
4. Select appropriate routes to use
5. Maintain routing information
2.1 Establish routers adjacencies
This process is done using the Hello protocol. This protocol enables neighbours routers to establish links and to ensure communication with each other before exchanging link – state information.
Hello packets contain the following router information
- Router ID
- Hello / Dead Intervals *
- Neighbors
- Area ID *
- Router Priority
- DR IP address
- BDR IP address
- Authentication Password *
- Stub Area Flag
* Entry must match on adjacent routers [13]
OSPF routers go though several stages prior to establishing an adjacency, as shown in the following list.
Step 1 Initialization
Step 2 Establish two-way communications
Step 3 Exstart state
Step 4 Exchange state
Step 5 Loading state
Step 6 Full state
Main steps of the Hello packets exchanged process
I. Router A is OSPF down state because it has not exchanged information with other routers. Router A sends hello packet to the network.
II. All other OSPF routers receive the hello packet and add router A to their adjacencies database. This is Init state.
III. All routers send a reply hello packet with their information. Neighbour field includes all other neighbouring routers.
IV. When Router receives these packets, it adds adjacencies database. This state is Two-way state.
V. Periodically the routers within a networks exchange hello packets to ensure communication. (By default 10 seconds)
2.2 Electing the DR and BDR
When routers first come up on a network, they perform the hello process and also they must select a DR and BDR to build the network entry in the link-state database.
Each router forms adjacency with DR and BDR
After DR and BDR have been selected, the routers are on the Exstart state and routers are ready to discover the link-state information about the internetwork.
I. During the DR/BRD and other routers establish adjacencies, master and slave relationship is created between other routers and DR/BDR. ( Higher router ID acts as the master)
II. Master and slaves routers exchange database description packets (DBDs or DDPs). This state is Exchanged state.
- DBD includes the LSA entries that appear in the master’s routers link-state database.
III. When slave receive DBD,
- Sends link-state acknowledgment (LSAck) packts.
- Compare the information it received with the information it has. If DBD has more up to date link-state entry, then slave sends link-state request (LSR) to the master.
- Master responds with complete information about the requested entry in a link-state update (LSU) packet. After receiving the slave sends LSAck again. This process referred as Loading state.
IV. After updating all LSR the routers is in full state. At this point routers should have identical link-state database.
After router has a complete link- state database, router is ready to build its routing table. Link-state protocols use cost metric to determine the best path to destination.
OSPF Cost
The cost of an interface in OSPF is overhead required to send packets across a certain interface. The default cost metric is base on the bandwidth of an interface. A higher bandwidth indicates a lower cost.
For Example, 10Mbps Ethernet has lower cost than 56kbps serial line. That mean 10Mbps is faster than 56kbps line.
The following table gives some guidelines for costs:
| Network Type | Cost |
| FDDI/ Fast Ethernet | 1 |
| Token Ring ( 16Mbps) | 6 |
| Ethernet | 10 |
| E1 | 48 |
| T1 | 64 |
| 64kbps | 156 |
| 56kbps | 178 |
How to calculate the cost
The formula used to calculate the cost is:
Cost=1000, 000,000/bandwith in bps
For example:
Cost for 10 Mbps Ethernet line = 108/107=10
Cost for T1 line (1.544Mbps) = 108/1544000 = 64
It will cost 10 to cross 10Mbps Ethernet Line and It will cost 64 to cross T1 line.
By default, the cost of an interface is calculate based on the bandwidth; you can force the cost of an interface by using the ip ospf cost cost interface subcommand [14]
Shortest Path Algorithm (Dijkstra algorithm)
To calculate the lower cost to a destination OSPF uses Dijkstra algorithm. The algorithm adds up the total cost between source and to the each destination network. If there are multiple path to a destination the lowest cost path is selected. But OSPF keeps up to six equal cost routes in the routing table for load balancing.
Each router will have its own view of the network even though all the routers will build a shortest path tree using the same link-state database.
How to build Shortest Path Tree
In order to built shortest path tree for A in the following diagram, we have to make Router A the root of the tree and calculate the smallest cost for each destination.
* Direction of the arrows in calculating the cost.
For example, the Router B’s interface cost (8) to network 128.213.0.0 is not relevant when calculating the cost to 192.213.11.0 network.
* Cost for from Router A to Destination Network 192.213.11.0
- 10 + 5 = 15 ( Through Router B)
* Cost for from Router A to Destination Network 222.211.10.0
- 10 + 10 = 20 ( Through Router C)
- 10 + 5 + 5 =20 ( Through Router B)
* When equal cost paths exist to the same destination OSPF will keep up to six entries in the routing table.
* After building the shortest path tree, it will build the routing table accordingly.
* For directly connected networks cost is 0 and other networks will be reached according to the calculation of the tree.
4.5 Maintaining Routing Information.
Router uses flooding process to notify to the other routers when there is a change in a link- state.
1. When a router notices a change in a link sate, it multicast LSU packets ( updated LSA entry ) to 224.0.0.6, the all OSPF DRs and BDRs address
2. The DR receives the changes and floods the LSU to others on the network using the OSPF multicast address 224.0.0.5. After receiving the LSU, other routers respond to the DR with LSAck.
3. If a router is connected to another network It will send LSU to the DR of the other multiaccess network or it will sent LSU to next router if it is point to point network. Then DR multicast LSU to the other routers.
4. When a router received LSU with changes, the router updates its link-state database. Then use the SPF algorithm with new database to generate a new routing table.
When a router receives the LSU it will do the following steps.
* If entry already exists and LSU has same information then it will ignores.
* If entry already exists and LSU has new information It sends LSAck to the DR and adds the entry to its Link state database and also update its routing table.
* If entry already exists and LSU has older information, it sends an LSU with its information.[15]
