On this page
|
| SUMMARY | |
| Protocol |
: |
Open Shortest Path First Routing Protocol |
| Protocol suite |
: |
TCP/IP |
| Layer |
: |
Network Layer |
| Type |
: |
Network Layer interior link state routing protocol |
| SNMP MIBs |
: |
iso.org.dod.internet.mgmt.mib-2.ospf (1.3.6.1.2.1.14)
Working groups: ospf, Open Shortest Path First IGP |
| Multicast addresses |
: |
224.0.0.5 (all routers), 224.0.0.6 (designated routers) |
| Related protocols |
: |
IP,
TCP |
|
| DESCRIPTION |
OSPF is an interior gateway protocol used for routing between routers belonging to a single Autonomous System. OSPF is classified as an Interior Gateway Protocol (IGP). This means that it distributes routing information between routers belonging to a single Autonomous System. The OSPF protocol is based on link-state or SPF technology. This is a departure from the Bellman-Ford base usedby traditional TCP/IP internet routing protocols.
The OSPF protocol was developed by the OSPF working group of the Internet Engineering Task Force. It has been designed expressly for the TCP/IP internet environment, including explicit support for CIDR and the tagging of externally-derived routing information OSPF also provides for the authentication of routing updates, and utilizes IP multicast when sending/receiving the updates. In addition, much work has been done to produce a protocol that responds quickly to topology changes, yet involves small amounts of routing protocol traffic.
OSPF routes IP packets based solely on the destination IP address found in the IP packet header. IP packets are routed "as is" -- they are not encapsulated in any further protocol headers as they transit the Autonomous System. OSPF is a dynamic routing protocol. It quickly detects topological changes in the AS (such as router interface failures) and calculates new loop-free routes after a period of convergence. This period of convergence is short and involves a minimum of routing traffic.
In a link-state routing protocol, each router maintains a database describing the Autonomous System's topology. This database is referred to as the link-state database. Each participating router has an identical database. Each individual piece of this database is a particular router's local state (e.g., the router's usable interfaces and reachable neighbors). The router distributes its local state throughout the Autonomous System by flooding.
All routers run the exact same algorithm, in parallel. From the link-state database, each router constructs a tree of shortest paths with itself as root. This shortest-path tree gives the route to each destination in the Autonomous System. Externally derived routing information appears on the tree as leaves.
When several equal-cost routes to a destination exist, traffic is distributed equally among them. The cost of a route is described by a single dimensionless metric.
OSPF allows sets of networks to be grouped together. Such a grouping is called an area. The topology of an area is hidden from the rest of the Autonomous System. This information hiding enables a significant reduction in routing traffic. Also, routing within the area is determined only by the area's own topology, lending the area protection from bad routing data. An area is a generalization of an IP subnetted network.
OSPF enables the flexible configuration of IP subnets. Each route distributed by OSPF has a destination and mask. Two different subnets of the same IP network number may have different sizes (i.e., different masks). This is commonly referred to as variable length subnetting. A packet is routed to the best (i.e., longest or most specific) match. Host routes are considered to be subnets whose masks are "all ones" (0xffffffff).
All OSPF protocol exchanges are authenticated. This means that only trusted routers can participate in the Autonomous System's routing. A variety of authentication schemes can be used; in fact, separate authentication schemes can be configured for each IP subnet.
Externally derived routing data (e.g., routes learned from an Exterior Gateway Protocol such as BGP) is advertised throughout the Autonomous System. This externally derived data is kept separate from the OSPF protocol's link state data. Each external route can also be tagged by the advertising router, enabling the passing of additional information between routers on the boundary of the Autonomous System.
Version 2 header
8 | 16 | 32 bits | Version No. | Packet Type | Packet length | Router ID | Area ID | Checksum | AU type | Authentication |
- Version
OSPF version number.
- Type
OSPF request/reply code.
- Packet type
Valid types are as follows:
| Type | Description | | 1 | Hello. | | 2 | Database description. | | 3 | Link state request. | | 4 | Link state update. | | 5 | Link state acknowledgment. |
- Packet length
The length of the protocol packet in bytes. This length includes the standard OSPF header.
- Router ID
The router ID of the packet¡¯s source. In OSPF, the source and destination of a routing protocol packet are the two ends of an (potential) adjacency.
- Area ID
Area ID is a 32-bit number identifying the area that this packet belongs to. All OSPF packets are associated with a single area. Most travel a single hop only. Packets traveling over a virtual link are labeled with the back bone area ID of 0.0.0.0.
- Checksum
The standard IP checksum of the entire contents of the packet, starting with the OSPF packet header but excluding the 64-bit authentication field. This checksum is calculated as the 16-bit one¡¯s complement of the one¡¯s complement sum of all the 16-bit words in the packet, except for the authentication field. If the packet length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming.
- AU type
Identifies the authentication scheme to be used for the packet.
- Authentication
Authentication is a field for use by the authentication scheme.
| Authentication | Description | | 0 | None. | | 1 | Simple password authentication. | | 2 | Cryptographic authentication. | | 3-65535 | Reserved. |
OSPF version 3 header
This version is designed to support OSPF over IPv6 links.
8 | 16 | 24 | 32 bit | Version No. | Packet Type | Packet length | Router ID | Area ID | Checksum | Instance ID | Reserved | Authentication |
- Version
Always set to 3. OSPF version number.
- Checksum
OSPF uses the standard checksum calculation for IPv6 applications: The 16-bit one's complement of the one's complement sum of the entire contents of the packet, starting with the OSPF packet header, and prepending a "pseudo-header" of IPv6 header fields. The "Upper-Layer Packet Length" in the pseudo-header is set to value of the OSPF packet header's length field. The Next Header value used in the pseudo-header is 89. If the length of the packet is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming. Before computing the checksum, the checksum field in the OSPF packet header is set to 0.
- Instance ID
Enables multiple instances of OSPF to be run over a single link. Each protocol instance would be assigned a separate Instance ID; the Instance ID has local link significance only. Received packets whose Instance ID is not equal to the receiving interface's Instance ID are discarded.
- reserved
Must be cleared to 0.
Functional Summary
A separate copy of OSPF's basic routing algorithm runs in each area. Routers having interfaces to multiple areas run multiple copies of the algorithm. A brief summary of the routing algorithm follows.
When a router starts, it first initializes the routing protocol data structures. The router then waits for indications from the lower-level protocols that its interfaces are functional.
A router then uses the OSPF's Hello Protocol to acquire neighbors. The router sends Hello packets to its neighbors, and in turn receives their Hello packets. On broadcast and point-to-point networks, the router dynamically detects its neighboring routers by sending its Hello packets to the multicast address AllSPFRouters. On non-broadcast networks, some configuration information is necessary in order to discover neighbors. On all multi-access networks (broadcast or non-broadcast), the Hello Protocol also elects a Designated router for the network.
The router will attempt to form adjacencies with some of its newly acquired neighbors. Topological databases are synchronized between pairs of adjacent routers. On multi-access networks, the Designated Router determines which routers should become adjacent.
Adjacencies control the distribution of routing protocol packets. Routing protocol packets are sent and received only on adjacencies. In particular, distribution of topological database updates proceeds along adjacencies.
A router periodically advertises its state, which is also called link state. Link state is also advertised when a router's state changes. A router's adjacencies are reflected in the contents of its link state advertisements. This relationship between adjacencies and link state allows the protocol to detect dead routers in a timely fashion.
Link state advertisements are flooded throughout the area. The flooding algorithm is reliable, ensuring that all routers in an area have exactly the same topological database. This database consists of the collection of link state advertisements received from each router belonging to the area. From this database each router calculates a shortest-path tree, with itself as root. This shortest-path tree in turn yields a routing table for the protocol.
|
 Top of Page
|
| EXAMPLES |
The following figure shows an example of an adjacency forming. Routers RT1 and RT2
are both connected to a broadcast network. It is assumed that RT2 is the Designated
Router for the network, and that RT2 has a higher Router ID than Router RT1.
The neighbor state changes realized by each router are listed on the sides of the
figure.
At the beginning of Figure 14, Router RT1's interface to the network becomes
operational. It begins sending Hello Packets, although it doesn't know the identity
of the Designated Router or of any other neighboring routers. Router RT2 hears
this hello (moving the neighbor to Init state), and in its next Hello Packet indicates
that it is itself the Designated Router and that it has heard Hello Packets from RT1.
This in turn causes RT1 to go to state ExStart, as it starts to bring up the adjacency.
RT1 begins by asserting itself as the master. When it sees that RT2 is indeed the
master (because of RT2's higher Router ID), RT1 transitions to slave state and adopts
its neighbor's DD sequence number. Database Description packets are then exchanged,
with polls coming from the master (RT2) and responses from the slave (RT1). This
sequence of Database Description Packets ends when both the poll and associated
response has the M-bit off.
+---+ +---+
|RT1| |RT2|
+---+ +---+
Down Down
Hello(DR=0,seen=0)
------------------------------>
Hello (DR=RT2,seen=RT1,...) Init
<------------------------------
ExStart D-D (Seq=x,I,M,Master)
------------------------------>
D-D (Seq=y,I,M,Master) ExStart
<------------------------------
Exchange D-D (Seq=y,M,Slave)
------------------------------>
D-D (Seq=y+1,M,Master) Exchange
<------------------------------
D-D (Seq=y+1,M,Slave)
------------------------------>
...
...
...
D-D (Seq=y+n, Master)
<------------------------------
D-D (Seq=y+n, Slave)
Loading ------------------------------>
LS Request Full
------------------------------>
LS Update
<------------------------------
LS Request
------------------------------>
LS Update
<------------------------------
Full
In this example, it is assumed that RT2 has a completely up to date database. In
that case, RT2 goes immediately into Full state. RT1 will go into Full state after
updating the necessary parts of its database. This is done by sending Link State
Request Packets, and receiving Link State Update Packets in response. Note that, while
RT1 has waited until a complete set of Database Description Packets has been received
(from RT2) before sending any Link State Request Packets, this need not be the case.
RT1 could have interleaved the sending of Link State Request Packets with the
reception of Database Description Packets. |
Top of Page
|
| PROTOCOL RELATIONS |
■ Parent layer
■ Child layer
|
Top of Page
|
| GLOSSARY |
|
AS
AS (Autonomous system) is the unit of router policy, either a single network or a group of networks that is controlled by a common network administrator (or group of administrators) on behalf of a single administrative entity.
Adjacency
Adjacency is a relationship formed between selected neighboring routers for the purpose of exchanging routing information. Not every pair of neighboring routers become adjacent.
Algorithm
Algorithm is a formula or set of steps for solving a particular problem. To be an algorithm, a set of rules must be unambiguous and have a clear stopping point. Algorithms can be expressed in any language, from natural languages like English or French to programming languages like FORTRAN.
We use algorithms every day. For example, a recipe for baking a cake is an algorithm. Most programs, with the exception of some artificial intelligence applications, consist of algorithms. Inventing elegant algorithms -- algorithms that are simple and require the fewest steps possible -- is one of the principal challenges in programming.
Authentication
The process of identifying an individual, usually based on a username and password. In security systems, authentication is distinct from authorization , which is the process of giving individuals access to system objects based on their identity. Authentication merely ensures that the individual is who he or she claims to be, but says nothing about the access rights of the individual.
CIDR
CIDR (Classless Inter-Domain Routing) is a new addressing scheme for the Internet which allows for more efficient allocation of IP addresses than the old Class A, B, and C address scheme. A CIDR IP address looks like a normal IP address except that it ends with a slash followed by a number, called the IP network prefix.
Configuration
The way a system is set up, or the assortment of components that make up the system. Configuration can refer to either hardware or software, or the combination of both. For instance, a typical configuration for a PC consists of 32MB (megabytes) main memory, a floppy drive, a hard disk, a modem, a CD-ROM drive, a VGA monitor, and the Windows operating system.
Database
A database is an organized collection of data. The term originated within the computer industry, but its meaning has been broadened by popular use, to the extent that the European Database Directive (which creates intellectual property rights for databases) includes non-electronic databases within its definition. This article is confined to a more technical use of the term; though even amongst computing professionals, some attach a much wider meaning to the word than others.
Designated Router
Each broadcast and NBMA network that has at least two attached routers has a Designated Router. The Designated Router generates an LSA for the network and has other special responsibilities in the running of the protocol. The Designated Router is elected by the Hello Protocol.
Hello Protocol
Hello Protocol is the part of the OSPF protocol used to establish and maintain neighbor relationships. On broadcast networks the Hello Protocol can also dynamically discover neighboring routers.
IGP
IGP (Interior Gateway Protocol) is a protocol for exchanging routing information between gateways (hosts with routers) within an autonomous network. such as a enterprise LAN. IGPs typically support confined geographical areas.
RIP and OSPF are two examples of an IGP.
IP
The IP (Internet Protocol) is a protocol which uses datagrams to communicate over a packet-switched network. IP specifies the format of packets, also called datagrams, and the addressing scheme. Most networks combine IP with a higher-level protocol called Transmission Control Protocol (TCP), which establishes a virtual connection between a destination and a source.
IP by itself is something like the postal system. It allows you to address a package and drop it in the system, but there's no direct link between you and the recipient. TCP/IP, on the other hand, establishes a connection between two hosts so that they can send messages back and forth for a period of time.
The current version of IP is IPv4. A new version, called IPv6 or IPng, is under development.
IP address
IP address is an identifier for a computer or device on a TCP/IP network. Networks using the TCP/IP protocol route messages based on the IP address of the destination. The format of an IP address is a 32-bit numeric address written as four numbers separated by periods. Each number can be zero to 255. For example, 1.160.10.240 could be an IP address. Within an isolated network, you can assign IP addresses at random as long as each one is unique. However, connecting a private network to the Internet requires using registered IP addresses (called Internet addresses) to avoid duplicates.
The four numbers in an IP address are used in different ways to identify a particular network and a host on that network. Four regional Internet registries -- ARIN, RIPE NCC, LACNIC and APNIC -- assign Internet addresses from the following three classes.
Class A - supports 16 million hosts on each of 126 networks
Class B - supports 65,000 hosts on each of 16,000 networks
Class C - supports 254 hosts on each of 2 million networks
The number of unassigned Internet addresses is running out, so a new classless scheme called CIDR is gradually replacing the system based on classes A, B, and C and is tied to adoption of IPv6.
Interface
Interface is the connection between a router and one of its attached networks. An interface has state information associated with it, which is obtained from the underlying lower level protocols and the routing protocol itself. An interface to a network has associated with it a single IP address and mask (unless the network is an unnumbered point-to-point network). An interface is sometimes also referred to as a link.
Internet
A global network connecting millions of computers. More than 100 countries are linked into exchanges of data, news and opinions.
Unlike online services, which are centrally controlled, the Internet is decentralized by design. Each Internet computer, called a host, is independent. Its operators can choose which Internet services to use and which local services to make available to the global Internet community. Remarkably, this anarchy by design works exceedingly well.
There are a variety of ways to access the Internet. Most online services, such as America Online, offer access to some Internet services. It is also possible to gain access through a commercial Internet Service Provider (ISP).
Link state advertisement
Link state advertisement is the unit of data describing the local state of a router or network. For a router, this includes the state of the router's interfaces and adjacencies. Each link state advertisement is flooded throughout the routing domain. The collected link state advertisements of all routers and networks forms the protocol's link state database. Throughout this memo, link state advertisement is abbreviated as LSA.
Lower-level protocols
Lower-level protocols are the underlying network access protocols that provide services to the Internet Protocol and in turn the OSPF protocol. Examples of these are the X.25 packet and frame levels for X.25 PDNs, and the ethernet data link layer for ethernets.
Multicast
Multicast is designed to transmit a single message to a select group of recipients. A simple example of multicasting is sending an e-mail message to a mailing list. Teleconferencing and videoconferencing also use multicasting, but require more robust protocols and networks.
Neighboring routers
Neighboring routers are the two routers that have interfaces to a common network. Neighbor relationships are maintained by, and usually dynamically discovered by, OSPF's Hello Protocol.
Network
Network is a group of two or more computer systems linked together. There are many types of computer networks, including:
LANs (local-area networks), WANs (wide-area networks), CANs (campus-area networks), MANs (metropolitan-area networks) and HANs (home-area networks).
In addition to these types, the following characteristics are also used to categorize different types of networks: Topology, protocol and architecture.
Non-broadcast networks
Networks supporting many (more than two) routers, but having no broadcast capability. Neighboring routers are maintained on these nets using OSPF's Hello Protocol. However, due to the lack of broadcast capability, some configuration information may be necessary to aid in the discovery of neighbors. On non-broadcast networks, OSPF protocol packets that are normally multicast need to be sent to each neighboring router, in turn. An X.25 Public Data Network (PDN) is an example of a non-broadcast network.
OSPF
OSPF is an interior gateway protocol which is used for routing within a group of routers. It uses link-state technology in which routers send each other information about the direct connections and links which they have to other routers.
Packet
A packet is the unit of data that is routed between an origin and a destination on the Internet or any other packet-switched network. When any file (e-mail message, HTML file, Graphics Interchange Format file, Uniform Resource Locator request, and so forth) is sent from one place to another on the Internet, the Transmission Control Protocol (TCP) layer of TCP/IP divides the file into "chunks" of an efficient size for routing. Each of these packets is separately numbered and includes the Internet address of the destination. The individual packets for a given file may travel different routes through the Internet. When they have all arrived, they are reassembled into the original file (by the TCP layer at the receiving end).
Path
The route taken by the SCTP packets sent by one SCTP endpoint to a specific destination transport address of its peer SCTP endpoint. Sending to different destination transport addresses does not necessarily guarantee getting separate paths.
Point-to-point networks
Point-to-point networks is a network that joins a single pair of routers. A 56Kb serial line is an example of a point-to-point network.
Router
A device that forwards data packets along networks. A router is connected to at least two networks, commonly two LANs or WANs or a LAN and its ISP network. Routers are located at gateways, the places where two or more networks connect.
Routers use headers and forwarding tables to determine the best path for forwarding the packets, and they use protocols such as ICMP to communicate with each other and configure the best route between any two hosts.
Subnet
Subnet is a portion of a network that shares a common address component. On TCP/IP networks, subnets are defined as all devices whose IP addresses have the same prefix. For example, all devices with IP addresses that start with 100.100.100. would be part of the same subnet. Dividing a network into subnets is useful for both security and performance reasons. IP networks are divided using a subnet mask.
|
Top of Page
|
| REFERENCES |
Related links:
OSPF authentication codes
OSPF Opaque types
OSPF signature algorithms
OSPF Traffic Engineering TLVs
RFCs:
[ RFC 1131] The OSPF Specification.
Obsoleted by: RFC 1247.
This document is only available in Postscript format.
[ RFC 1245] OSPF protocol analysis.
[ RFC 1246] Experience with the OSPF protocol.
[ RFC 1349] Type of Service in the Internet Protocol Suite.
Updates: RFC 791, RFC 1060, RFC 1122, RFC 1123, RFC 1195, RFC 1247, RFC 1248.
[ RFC 1370] Applicability Statement for OSPF.
[ RFC 1403] BGP OSPF Interaction.
Obsoletes: RFC 1364.
[ RFC 1745] BGP4/IDRP for IP---OSPF Interaction.
[ RFC 1586] Guidelines for Running OSPF Over Frame Relay Networks.
[ RFC 1765] OSPF Database Overflow.
[ RFC 1793] Extending OSPF to Support Demand Circuits.
Updated by: RFC 3883.
[ RFC 1812] Requirements for IP Version 4 Routers.
[ RFC 1850] OSPF Version 2 Management Information Base.
Obsoletes: RFC 1253.
[ RFC 2154] OSPF with Digital Signatures.
[ RFC 2328] OSPF Version 2.
Obsoletes: RFC 2178.
[ RFC 2329] OSPF Standardization Report.
[ RFC 2370] The OSPF Opaque LSA Option.
Updated by: RFC 3630.
[ RFC 2676] QoS Routing Mechanisms and OSPF Extensions.
Defines extensions to OSPF to support QoS routes.
[ RFC 2740] OSPF for IPv6.
[ RFC 2844] OSPF over ATM and Proxy-PAR.
[ RFC 2991] Multipath Issues in Unicast and Multicast Next-Hop Selection.
[ RFC 3101] The OSPF Not-So-Stubby Area (NSSA) Option.
Obsoletes: RFC 1587.
[ RFC 3137] OSPF Stub Router Advertisement.
[ RFC 3166] Request to Move RFC 1403 to Historic Status.
[ RFC 3167] Request to Move RFC 1745 to Historic Status.
[ RFC 3509] Alternative Implementations of OSPF Area Border Routers.
[ RFC 3623] Graceful OSPF Restart.
[ RFC 3630] Traffic Engineering (TE) Extensions to OSPF Version 2.
Updates: RFC 2370.
[ RFC 3883] Detecting Inactive Neighbors over OSPF Demand Circuits (DC).
Updates: RFC 1793.
[ RFC 4061] Benchmarking Basic OSPF Single Router Control Plane Convergence.
[ RFC 4062] OSPF Benchmarking Terminology and Concepts.
[ RFC 4063] Considerations When Using Basic OSPF Convergence Benchmarks.
[ RFC 4124] Protocol Extensions for Support of Diffserv-aware MPLS Traffic Engineering.
Defines IS-IS sub-TLV (22, 22) Bandwidth Constraints.
Defines OSPF sub-TLV (2, 17) Bandwidth Contraints.
Defines RSVP class 66 (CLASSTYPE).
[ RFC 4136] OSPF Refresh and Flooding Reduction in Stable Topologies.
[ RFC 4167] Graceful OSPF Restart Implementation Report.
Obsolete RFCs:
[ RFC 1131] The OSPF Specification.
Obsoleted by: RFC 1247.
[ RFC 1247] OSPF Version 2.
Obsoleted by: RFC 1583.
Obsoletes: RFC 1131.
[ RFC 1248] OSPF Version 2 Management Information Base.
Obsoleted by: RFC 1252.
[ RFC 1252] OSPF Version 2 Management Information Base.
Obsoleted by: RFC 1253.
Obsoletes: RFC 1248.
[ RFC 1253] OSPF Version 2 Management Information Base.
Obsoleted by: RFC 1850.
Obsoletes: RFC 1252.
[ RFC 1364] BGP OSPF Interaction.
Obsoleted by: RFC 1403.
[ RFC 1583] OSPF Version 2.
Obsoleted by: RFC 2178.
Obsoletes: RFC 1247.
[ RFC 1587] The OSPF NSSA Option.
Obsoleted by: RFC 3101.
[ RFC 2178] OSPF Version 2.
Obsoleted by: RFC 2328.
Obsoletes: RFC 1583.
Publications:
[ISBN 0201634724] OSPF: Anatomy of An Internet Routing Protocol.
[ISBN 0201309661] OSPF: Complete Implementation.
|
Top of Page
|
| OTHER PROTOCOLS OF TCP/IP SUITE |
|
|
|
|
|
Hello
Data Desc
Link State Ack