Open Shortest Path First
From Wikipedia, the free encyclopedia
| Internet protocol suite |
| 5. Application layer |
|
DHCP • DNS • FTP • HTTP • IMAP4 • IRC • MIME • POP3 • SIP • SMTP • SNMP • SSH • TELNET • TLS/SSL • RPC • RTP • SDP • SOAP • … |
| 4. Transport layer |
| 3. Network layer |
| 2. Data link layer |
|
ATM • Bluetooth (PAN-Profile) • DTM • Ethernet • FDDI • Frame Relay • GPRS • Modems • PPP • Wi-Fi • … |
| 1. Physical layer |
|
Bluetooth RF • Ethernet physical layer • ISDN • Modems • RS232 • SONET/SDH • USB • Wi-Fi • … |
The Open Shortest Path First (OSPF) protocol is a link-state, hierarchical interior gateway protocol (IGP) for network routing. Dijkstra's algorithm is used to calculate the shortest path tree. It uses cost as its routing metric. A link state database is constructed of the network topology which is identical on all routers in the area.
OSPF is perhaps the most widely used IGP in large networks. It can operate securely, using MD5 to authenticate peers before forming adjacencies, and before accepting link-state advertisements (LSA). A natural successor to the Routing Information Protocol (RIP), it was VLSM-capable or classless from its inception. A newer version of OSPF (OSPFv3) now supports IPv6 as well. Multicast extensions to OSPF, the Multicast Open Shortest Path First (MOSPF) protocols, have been defined, but these are not widely used at present. OSPF can "tag" routes, and propagate the tags along with the routes.
An OSPF network can be broken up into smaller networks. A special area called the backbone area forms the core of the network, and other areas are connected to it. Inter-area routing goes via the backbone. All areas must connect to the backbone; if no direct connection is possible, a virtual link may be established.
Routers in the same broadcast domain or at each end of a point-to-point telecommunications link form adjacencies when they have detected each other. This detection occurs when a router "sees" itself in a hello packet. This is called a two way state and is the most basic relationship. The routers elect a designated router (DR) and a backup designated router (BDR) which act as a hub to reduce traffic between routers. OSPF uses both unicast and multicast to send "hello packets" and link state updates. Multicast addresses 224.0.0.5 and 224.0.0.6 are reserved for OSPF. In contrast to the Routing Information Protocol (RIP) or the Border Gateway Protocol (BGP), OSPF does not use TCP or UDP but uses IP directly, via IP protocol 89.
Contents |
[edit] Area types
An OSPF network is divided into areas. These are logical groupings of routers whose information may be summarized towards the rest of the network. Several "special" area types are defined:
[edit] Backbone area
The backbone area (also known as area zero) forms the core of an OSPF network. All other areas are connected to it, and inter-area routing happens via a router connected to the backbone area. It is the logical and physical structure for the 'autonomous system' (AS) and is attached to multiple areas. The backbone area is responsible for distributing routing information between nonbackbone areas. The backbone must be contiguous, but it does not need to be physically contiguous; backbone connectivity can be established and maintained through the configuration of virtual links.
Note: All OSPF areas must connect to the backbone area.
[edit] Stub area
A stub area is an area which does not receive external routes. External routes are defined as routes which were distributed in OSPF from another routing protocol. Therefore, stub areas typically need to rely on a default route to send traffic to routes outside the present domain. This implies that AS-external routes (Type 5 LSAs) are not fed into Stub Areas.
[edit] Totally stubby area
A totally stubby area (TSA) is similar to a stub area, however this area does not allow summary routes in addition to the external routes, that is, inter-area (IA) routes are not summarized into totally stubby areas. The only way for traffic to get routed outside of the area is a default route which is the only Type-3 LSA advertised into the area. When there is only one route out of the area, fewer routing decisions have to be made by the route processor, which lowers system resource utilization.
[edit] Not-so-stubby area
A not-so-stubby area (NSSA) is a type of stub area that can import autonomous system (AS) external routes and send them to the backbone, but cannot receive AS external routes from the backbone or other areas. Cisco also implements a proprietary version of a NSSA called a NSSA totally stubby area. It takes on the attributes of a TSA, meaning that type 3 and type 4 summary routes are not flooded into this type of area.
[edit] OSPF router types
OSPF defines various router types. These are logical definitions, and a router that uses OSPF may be classified as more than one of the following types. For example, a router that is connected to more than one area, and which receives routes from a BGP process connected to another AS, is both an ABR and an ASBR.
[edit] Area border router
An area border router (ABR) is a router that connects one or more OSPF areas to the main backbone network. It is considered a member of all areas it is connected to. An ABR keeps multiple copies of the link-state database in memory, one for each area.
[edit] Autonomous system boundary router
An autonomous system boundary router (ASBR) is a router that is connected to more than one AS and that exchanges routing information with routers in other AS's. ASBR's typically also run a non-IGP routing protocol, such as BGP. An ASBR is used to distribute routes received from other ASs throughout its own AS.
[edit] Internal router
A router is called an internal router (IR) if it has only OSPF adjacencies with routers in the same area.
Area Border Routers: These are routers that connect to routers or networks in more than one area. They maintain an LSDB for each area of which they are a part. They also participate in the backbone.
Backbone Routers: These are routers that are part of the OSPF backbone. By definition, this includes all area border routers, since those routers pass routing information between areas. However, a backbone router may also be a router that connects only to other backbone (or area border) routers, and is therefore not part of any area (other than Area 0).
To summarize: an area border router is always also a backbone router, but a backbone router is not necessarily an area border router.
[edit] Designated router
A designated router (DR) is the router elected by the network by elections. The DR is elected based on the following default criteria:
- If the priority setting on a OSPF router is set to 0, that means it can NEVER become a DR or BDR.
- When a DR fails and the BDR takes over, there is another election to see who becomes the replacement BDR.
- The router sending the Hello packets with the highest priority.
- If two or more routers tie with the highest priority setting, the router sending the Hello with the highest RID (Router ID) wins.
- (NOTE) A RID is the highest logical (loopback) IP address configured on a router, if no logical/loopback IP address is set then the Router uses the highest IP address configured on its active interfaces. (e.g. 192.168.0.1 would be higher than 10.1.1.2)
- Usually the router with the second highest priority number becomes the BDR (Backup Designated Router)
- The range of priority values range from 1 - 255, with a higher value increasing its chances of becoming DR or BDR.
- IF a HIGHER priority OSPF router comes online AFTER the election has taken place, it will not become DR or BDR until (at least) the DR and BDR fail.
DR's exist for the purpose of reducing network traffic by providing a source for routing updates, the DR maintains a complete topology table of the network and sends the updates to the other routers via multicast. This way all the routers do not have to constantly update each other, and can rather get all their updates from a single source. The use of multicasting further reduces the network load. DRs and BDRs are always setup/elected on Broadcast networks (Ethernet). DR's can also be elected on NBMA (Non-Broadcast Multi-Access) networks such as Frame Relay. DRs or BDRs do not configure on point-to-point links (such as a point-to-point WAN connection) because the bandwidth between two hosts cannot be further optimized.
[edit] Backup designated router
A backup designated router (BDR) is a router that becomes the designated router if the current designated router has a problem or fails. The BDR is the OSPF router with second highest priority at the time of the last election.
[edit] OSPF Packet Header
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| version | type | packet length |
+---------------+---------------+-------------------------------+
| router ID |
+---------------------------------------------------------------+
| area ID |
+-------------------------------+-------------------------------+
| checksum | authentication type |
+-------------------------------+-------------------------------+
| authentication |
+---------------------------------------------------------------+
| authentication |
+---------------------------------------------------------------+
[edit] OSPF Hello Packet
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| version | type | packet length |
+---------------+---------------+-------------------------------+
| router ID |
+---------------------------------------------------------------+
| area ID |
+-------------------------------+-------------------------------+
| checksum | authentication type |
+-------------------------------+-------------------------------+
| authentication |
+---------------------------------------------------------------+
| authentication |
+---------------------------------------------------------------+
| network mask |
+-------------------------------+---------------+---------------+
| hello interval | options |router priority|
+-------------------------------+---------------+---------------+
| router dead interval |
+---------------------------------------------------------------+
| designated router |
+---------------------------------------------------------------+
| backup designated router |
+---------------------------------------------------------------+
| neighbor ID |
+---------------------------------------------------------------+
| neighbor ID |
+---------------------------------------------------------------+
| ... |
[edit] RFC history
- 1989, October - First put forward as a proposed standard as RFC 1131.
- 1994, The OSPF NSSA Option, RFC 1587.
- 1994, March - Multicast extensions to OSPF proposed as RFC 1584.
- 1997, July - OSPF version 2, as proposed in RFC 2178
- 1999, December - OSPFv3, IPv6, RFC 2740.
- 2003, January - The OSPF NSSA Option updated, RFC 3101.
[edit] Implementations
- GNU Zebra, a GPL routing suite for Unix-like systems supporting OSPF
- Quagga, a fork of GNU Zebra for Unix-like systems
- OpenBGPD, includes an OSPF implementation
- XORP, a routing suite including a limited OSPF daemon
- BIRD (http://bird.network.cz) implements RFC2328 OSPF
- GateD project included an RFC1583 OSPF implementation (UMD OSPF by University of Maryland).
