Internet > How
the Internet works > Routing > IGP
Shortest Path First (OSPF)
Path First (OSPF) is a particularly efficient IGP routing protocol that is faster
but also more complex. The following sections describe how
OSPF was invented, how OSPF works, and provide more
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
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
OSPF information. The following references provide more information on
- RFC 1370,
Applicability Statement for OSPF, Lyman Chapin, in October, 1992.
- RFC 1403,
OSPF Interaction, K. Varadhan, 1993.
1584, Multicast Extensions to OSPF, J. Moy, March 1994.
- RFC 1587,
OSPF NSSA Option, R. Coltun and V. Fuller, March 1994.
1745, BGP4/IDRP for IP -- OSPF Interaction, K. Varadhan., S. Hares,
and Y. Rekhter, Dec 1994.
1765, OSPF Database Overflow, J. Moy, 1995.
1793, Extending OSPF to Support Demand Circuits, J. Moy, April 1995.
- RFC 1850,
Version 2 Management Information Base, F. Baker and R. Coltun, Nov 1995.
- RFC 2154,
with Digital Signatures, S. Murphy, M. Badger, and B. Wellington, June 1997.
- RFC 2328,
Version 2, J. Moy, April 1998, also STD 54.
2370, The OSPF Opaque LSA Option, R. Coltun, July 1998.