The Open Shortest Path First (OSPF) protocol, defined in RFC 2328 , is an Interior Gateway Protocol used to distribute routing information within a single Autonomous System. This paper examines how OSPF works and how it can be used to design and build large and complicated networks.
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. The discussion of the creation of a common interoperable IGP for the Internet started in 1988 and did not get formalized until 1991. At that time the OSPF Working Group requested that OSPF be considered for advancement to Draft Internet Standard.
The OSPF protocol is based on link-state technology, which is a departure from the Bellman-Ford vector based algorithms used in traditional Internet routing protocols such as RIP. OSPF has introduced new concepts such as authentication of routing updates, Variable Length Subnet Masks (VLSM), route summarization, and so forth.
OSPF versus RIP
The rapid growth and expansion of today's networks has pushed RIP to its limits. RIP has certain limitations that can cause problems in large networks:
RIP has a limit of 15 hops. A RIP network that spans more than 15 hops (15 routers) is considered unreachable.
RIP cannot handle Variable Length Subnet Masks (VLSM). Given the shortage of IP addresses and the flexibility VLSM gives in the efficient assignment of IP addresses, this is considered a major flaw.
Periodic broadcasts of the full routing table consume a large amount of bandwidth. This is a major problem with large networks especially on slow links and WAN clouds.
RIP converges slower than OSPF. In large networks convergence gets to be in the order of minutes. RIP routers go through a period of a hold-down and garbage collection and slowly time-out information that has not been received recently. This is inappropriate in large environments and could cause routing inconsistencies.
RIP has no concept of network delays and link costs. Routing decisions are based on hop counts. The path with the lowest hop count to the destination is always preferred even if the longer path has a better aggregate link bandwidth and less delays.
RIP networks areflat networks. There is no concept of areas or boundaries. With the introduction of classless routing and the intelligent use of aggregation and summarization, RIP networks seem to have fallen behind.
Some enhancements were introduced in a new version of RIP called RIP2. RIP2 addresses the issues of VLSM, authentication, and multicast routing updates. RIP2 is not a big improvement over RIP (now called RIP 1) because it still has the limitations of hop counts and slow convergence which are essential in todays large networks.
OSPF, on the other hand, addresses most of the issues previously presented:
With OSPF, there is no limitation on the hop count.
The intelligent use of VLSM is very useful in IP address allocation.
OSPF uses IP multicast to send link-state updates. This ensures less processing on routers that are not listening to OSPF packets. Also, updates are only sent in case routing changes occur instead of periodically. This ensures a better use of bandwidth.
OSPF has better convergence than RIP. This is because routing changes are propagated instantaneously and not periodically.
OSPF allows for better load balancing.
OSPF allows fora logical definition of networks where routers can be divided into areas. This limits the explosion of link state updates over the whole network. This also provides a mechanism for aggregating routes and cutting down on the unnecessary propagation of subnet information.
OSPF allows for routing authentication by using different methods of password authentication.
OSPF allows for the transfer and tagging of external routes injected into an Autonomous System. This keeps track of external routes injected by exterior protocols such as BGP.
This of course leads to more complexity in the configuration and troubleshooting of OSPF networks. Administrators that are used to the simplicity of RIP are challenged with the amount of new information they have to learn in order to keep up with OSPF networks. Also, this introduces more overhead in memory allocation and CPU utilization. Some of the routers running RIP might have to be upgraded in order to handle the overhead caused by OSPF.
What Do We Mean by Link-States?
OSPF is a link-state protocol. We could think of a link as being an interface on the router. The state of the link is a description of that interface and of its relationship to its neighboring routers. A description of the interface would include, for example, the IP address of the interface, the mask, the type of network it is connected to, the routers connected to that network and so on. The collection of all these link-states would form a link-state database.
Shortest Path First Algorithm
OSPF uses a shorted path first algorithm in order to build and calculate the shortest path to all known destinations.The shortest path is calculated with the use of the Dijkstra algorithm. The algorithm by itself is quite complicated. This is a very high level, simplified way of looking at the various steps of the algorithm:
Upon initialization or due to any change in routing information, a routergenerates a link-state advertisement. This advertisement represents the collection of all link-states on that router.
All routers exchange link-states by means of flooding. Each router that receives a link-state update should store a copy in its link-state database and then propagate the update to other routers.
After the database of each router is completed, the router calculates a Shortest Path Tree to all destinations. The router uses the Dijkstra algorithm in order to calculate the shortest path tree. The destinations, the associated cost and the next hop to reach those destinations form the IP routing table.
In case no changes in the OSPF network occur, such as cost of a link or a network being added or deleted, OSPF should be very quiet. Any changes that occur are communicated through link-state packets, and the Dijkstra algorithm is recalculated in order to find the shortest path.
The algorithm places each router at the root of a tree and calculates the shortest path to each destination based on the cumulative cost required to reach that destination. Each router will have its own view of the topology even though all the routers will build a shortest path tree using the same link-state database. The following sections indicate what is involved in building a shortest path tree.
The cost (also called metric) of an interface in OSPF is an indication of the overhead required to send packets across a certain interface. The cost of an interface is inversely proportional to the bandwidth of that interface. A higher bandwidth indicates a lower cost. There is more overhead (higher cost) and time delays involved in crossing a 56k serial line than crossing a 10M ethernet line. The formula used to calculate the cost is:
cost= 10000 0000/bandwith in bps
For example, it will cost 10 EXP8/10 EXP7 = 10 to cross a 10M Ethernet line and will cost 10 EXP8/1544000 = 64 to cross a T1 line.
By default, the cost of an interface is calculated based on the bandwidth; you can force the cost of an interface with the ip ospf cost <value> interface subconfiguration mode command.