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.
|