Internet > How the Internet works > Routing > IGP Protocols >

Open Shortest Path First (OSPF)

Open Shortest Path First (OSPF) is a particularly efficient IGP routing protocol that is faster than RIP, but also more complex. The following sections describe how OSPF was invented, how OSPF works, and provide more OSPF information.

How OSPF was invented. The OSPF routing algorithm was created to provide an alternative to RIP, based on Shortest Path First algorithms instead of the Bellman-Ford algorithm. It uses a tree that describes the network topology to define the shortest path from each router to each destination address. Since OSPF keeps track of entire paths, it has more overhead than RIP, but provides more options.

How OSPF works. The main difference between OSPF and RIP is that RIP only keeps track of the closest router for each destination address, while OSPF keeps track of a complete topological database of all connections in the local network. The OSPF algorithm works as described below.

  • Startup. When a router is turned on it sends Hello packets to all of its neighbors, receives their Hello packets in return, and establishes routing connections by synchronizing databases with adjacent routers that agree to synchronize.
  • Update. At regular intervals each router sends an update message called its "link state" describing its routing database to all the other routers, so that all routers have the same description of the topology of the local network.
  • Shortest path tree. Each router then calculates a mathematical data structure called a "shortest path tree" that describes the shortest path to each destination address and therefore indicates the closest router to send to for each communication; in other words -- "open shortest path first".

More OSPF information. The following references provide more information on OSPF:

  • RFC 1370, Applicability Statement for OSPF, Lyman Chapin, in October, 1992.
  • RFC 1403, BGP OSPF Interaction, K. Varadhan, 1993.
  • RFC 1584, Multicast Extensions to OSPF, J. Moy, March 1994.
  • RFC 1587, The OSPF NSSA Option, R. Coltun and V. Fuller, March 1994.
  • RFC 1745, BGP4/IDRP for IP -- OSPF Interaction, K. Varadhan., S. Hares, and Y. Rekhter, Dec 1994.
  • RFC 1765, OSPF Database Overflow, J. Moy, 1995.
  • RFC 1793, Extending OSPF to Support Demand Circuits, J. Moy, April 1995.
  • RFC 1850, OSPF Version 2 Management Information Base, F. Baker and R. Coltun, Nov 1995.
  • RFC 2154, OSPF with Digital Signatures, S. Murphy, M. Badger, and B. Wellington, June 1997.
  • RFC 2328, OSPF Version 2, J. Moy, April 1998, also STD 54.
  • RFC 2370, The OSPF Opaque LSA Option, R. Coltun, July 1998.
 

__