OSPF is an Interior Gateway Protocol, which means that it is used by all the routers inside the same Autonomous System in order to route packets inside the AS. In an internet, which is divided into several AS's, the routing between 2 hosts on different AS's is done as follows: first, the packet is sent from the original host to some Border Router using the Interior Gateway Protocol (IGP). The Border Router uses Border Gateway Protocol (BGP) to route the packet to the AS of the destination. Inside that AS, the packet is routed through the IGP of that AS.
The general idea behind OSPF is the following:
OSPF is a link-state routing protocol, which is based on the SPF (Shortest Path First) algorithm to find the least cost path to any destination in the network.
Each router sends the list of his neighbors to all the other routers. When a router has received that information from all other routers, it is ready to deduce the topology of the network, which will enable it, through the use of the Dijkstra algorithm, to find the least-cost path to any IP address on the entire network.
OSPF can be described as follows:
In OSPF, each router maintains a database that describes the current topology of the network. However, since OSPF is run inside ASs and since ASs can be very large, there is a division of ASs into small sets of networks which are called "Areas". The main idea is that each router should maintain a database of the topology of the area in which it resides.
This database is maintained in the following way:
At first, when a router comes online, it uses some protocol (The Hello Protocol) to find his network neighbors and the cost it takes to reach each neighbor. This information is referred to as the link-state information of the router. When, this is done, each router floods his list of neighbors (Link State Advertisement) throughout the entire area until all the routers have received it. This is continued until all the routers in the area, have the list of neighbors from all the other routers.
When this process is done, each router has in its database some representation of the topology of the area - each router has the list of neighbors of all other routers. This information is sufficient to know the exact topology of the area, and in addition, it can be used to build a routing table, to route packets inside the area using the best path (The path which is the most suitable for the Type Of Service needed by the packet which is to be delivered).
Whenever a change in the topology occurs (A router goes down, a new router comes up), this change is quickly discovered using a protocol (Again, the use of the Hello Protocol), and the router who discovered this change, changed his database, and updates all the routers in the area by flooding the update throughout the network. This ensures that all the routers in the same area have the same database.
In order to flood link state information throughout the area, OSPF introduces the notion of Designated Routers. Once Designated Routers have been selected, whenever some router want to send link state information, he will transfer it to the Designated router in an exchange protocol. Next, the designated router will transfer the information to all the other routers.
When all the routers are synchronized (All the routers have the same information in their database), they use the Dijkstra algorithm and build a shortest path tree, whereas shortest path means the least cost path (The quickest path to route a packet). In the case where there are more than one path to the same destination with the same cost, all the paths to the destination with the least cost are saved in the tree. This is later used for load balancing when routing packets. In addition, there can be a few such trees, each for a specified Type Of Service of packets, due to the fact that each Type Of Service, can have a different definition of a cost of a path. (For example, when routing packets of digital video, we would prefer a route with a very small delay).
The shortest-path tree (or trees) is later used to build the routing table of each router.
Some advanced features of OSPF:
- OSPF supports router authentication before exchange of Link State information. This enables other routers to verify that the Link State information they have received, was sent by an authenticated router. This feature is intended to prevent malicious users from interfering in the creation of routing tables.
- OSPF supports subnetting and supernetting - in OSPF each network is identified by both an IP address and a subnet mask.