Open Shortest Path First
From Wikipedia, the free encyclopedia
| The five-layer TCP/IP model |
| 5. Application layer |
|
DHCP · DNS · FTP · Gopher · HTTP · IMAP4 · IRC · NNTP · XMPP · POP3 · SIP · SMTP · SNMP · SSH · TELNET · RPC · RTP · RTCP · RTSP · TLS/SSL · SDP · SOAP · BGP · GTP · STUN · NTP · RIP· ... |
| 4. Transport layer |
| 3. Network/Internet Layer |
| 2. Data link layer |
|
802.11 · Wi-Fi · WiMAX · ATM · DTM · Token Ring · Ethernet · FDDI · Frame Relay · GPRS · EVDO · HSPA · HDLC · PPP · PPTP · L2TP · ... |
| 1. Physical layer |
|
Ethernet physical layer · ISDN · Modems · PLC · SONET/SDH · G.709 · OFDM ·Optical Fiber · Coaxial Cable · Twisted Pair · ... |
The Open Shortest Path First (OSPF) protocol is a hierarchical interior gateway protocol (IGP) for routing in Internet Protocol, using a link-state in the individual areas that make up the hierarchy. A computation based on Dijkstra's algorithm is used to calculate the shortest path tree inside each area.
A link state database (LSDB) is constructed as a tree-image of the network topology, and identical copies of the LSDB are periodically updated on all routers in each OSPF-aware area (region of the network included in an OSPF area type--see "Area types" below). By convention, area 0 represents the core or "backbone" region of an OSPF-enabled network, and other OSPF area numbers may be designated to serve other regions of an enterprise (large, business) network--however every additional OSPF area must have a direct connection to the backbone OSPF area. The backbone area has the identifier 0.0.0.0.
OSPF is perhaps the most widely-used IGP in large enterprise networks; IS-IS is more common in large service provider networks. The most widely-used exterior gateway protocol (EGP) is BGP. OSPF Protocol can operate (communicate with other routers about "best-path" routes to save in their LSDBs) 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. A virtual link must have at least one endpoint in the backbone, and virtual links with both endpoints in the backbone can be defined to heal failures that make the backbone discontiguous.
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 (all SPF/link state routers) and 224.0.0.6 (all Designated Routers) 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. OSPF handles its own error detection and correction, so does not need TCP or UDP functions.
Contents |
[edit] Area types
An OSPF network is divided into areas, which have 32-bit area identifiers commonly, but not always, written in the dotted decimal format of an IP address. Area identifiers are not IP addresses and may duplicate, without conflict, any IP address. While most OSPF implementations will right-justify an area number written in other than dotted decimal format (e.g., area 1), it is wise always to use dotted decimal formats. Most implementations would expand area 1 to the area identifier 0.0.0.1, but some have been known to expand it as 1.0.0.0.
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 or area 0.0.0.0) forms the core of an OSPF network. All other areas are connected to it, and inter-area routing happens via routers connected to the backbone area and to their own non-backbone areas. It is the logical and physical structure for the 'OSPF domain' and is attached to all nonzero areas in the OSPF domain. Note that the term ASBR, in OSPF, is historic in the sense that many OSPF domains can coexist in the same Internet-visible autonomous system [1].
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! This connection, however, can be through a virtual link. For example, assume area 0.0.0.1 has a physical connection to area 0.0.0.0. Further assume that area 0.0.0.2 has no direct connection to the backbone, but this area does have a connection to area 0.0.0.1. Area 0.0.0.2 can use a virtual link through the transit area 0.0.0.1 to reach the backbone. To be a transit area, an area has to have the transit attribute, so cannot be stubby in any way.
[edit] Stub area
A stub area is an area which does not receive external routes, but does receive inter-area routes. This kind of area is useful when, for example, all Internet access goes through autonomous system border routers (ASBRs) in Area 0.0.0.0, but there are multiple paths to other nonzero areas in the OSPF domain.
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) and ASBR Summary LSAs (Type 4 LSAs) are not fed into Stub Areas by area border routers (ABRs).
Stub areas do receive inter-area (IA) routes, advertised with Type 3 and Type 4 LSAs. If the stub area has more than one ABR, the information on other non-backbone areas allows the routers in the stub area to pick the best route to another area.
For external destinations, the ABRs will use the default route, which is the only Type 5 LSA allowed into a stub area.
Stub areas do not have the transit attribute and thus cannot be traversed by a virtual link.
[edit] Totally stubby area
A totally stubby area (TSA), which is a nonstandard but useful extension by Cisco [2], 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.
Occasionally, it is said that a TSA can have only one ABR. This is not true. If there are multiple ABRs, as might be required for high availability, routers interior to the TSA will send non-intra-area traffic to the ABR with the lowest intra-area metric (the "closest" ABR).
An area can simultaneously be not-so-stubby and totally stubby. This is done when the practical place to put an ASBR, as, for example, with a newly acquired enterprise subsidiary, is on the edge of a totally stubby area. In such a case, the ASBR does send externals into the totally stubby area, and they are available to OSPF speakers within that area. In Cisco's implementation, the external routes can be summarized before injecting them into the totally stubby area. In general, the ASBR should not advertise default into the TSA-NSSA, although this can work with extremely careful design and operation, for the limited special cases in which such an advertisement makes sense.
By declaring the totally stubby area as NSSA, no external routes from the backbone, except the default route, enter the area being discussed. The externals do reach area 0.0.0.0 via the TSA-NSSA, but no routes other than the default route enter the TSA-NSSA. Routers in the TSA-NSSA send all traffic to the ABR, except to routes advertised by the ASBR.
[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. The NSSA is a non-proprietary extension of the existing stub area feature that allows the injection of external routes in a limited fashion into the stub area.
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. It is also possible to declare an area both totally stubby and not-so-stubby, which means that the area will receive only the default route from area 0.0.0.0, but can also contain an autonomous system border router (ASBR) that accepts external routing information and injects it into the local area, and from the local area into area 0.0.0.0.
Redistribution into an NSSA area creates special type of LSA known as TYPE 7, which can exist only in an NSSA area. An NSSA ASBR generates this LSA, and an NSSA ABR router translates it into type 5 LSA which gets propagated into the OSPF domain.
[edit] Path Preference
OSPF uses path cost as its basic routing metric, which was defined by the standard not to equate to any standard value such as speed, so the network designer could pick a metric important to the design. In practice, it is determined by the speed (bandwidth) of the interface addressing the given route, although that tends to need network-specific scaling factors now that links faster than 100 Mbit/s are common.
Metrics, however, are only directly comparable when of the same type. There are four types of metrics, with the most preferred type listed in order below. An intra-area route is always preferred to an inter-area route regardless of metric, and so on for the other types.
- Intra-area
- Inter-area
- External Type 1, which includes both the external path cost and the sum of internal path costs to the ASBR that advertises the route,
- External Type 2, the value of which is solely that of the external path cost
[edit] Traffic Engineering
Further extending the idea of route preference in OSPF include traffic engineering extensions to OSPF[3]. OSPF-TE is an extension to the IGP routing protocol OSPF. OSPF determines the shortest path to a node via a number of statically defined link metrics, the default and most commonly used metric is related to the bandwidth of the link. The Traffic Engineering extensions to OSPF add dynamic properties to the route calculation algorithm. The properties are:
- Maximum Reservable bandwidth
- Unreserved bandwidth
- Available bandwidth
These fields are distributed between network nodes via the TLV fields of an opaque LSA.
OSPF-TE is commonly used within MPLS and GMPLS networks
[edit] Other Extensions
Work in optical routing for IP is based on "constraint-based" extensions to OSPF and ISIS. [4].
[edit] OSPF router types
OSPF defines various router types. Each router has a router identifier, customarily written in the dotted decimal format (e.g., 1.2.3.4) of an IP address. The way in which the router ID is determined is implementation-specific. The router ID, however, does not have to be a valid IP address or any IP address present in the routing domain, although it frequently will be advertised within the domain for troubleshooting purposes. Do not assume, until it is known how it is configured, that the router ID is anything more than a 32-bit number (e.g., 255.254.253.252 is legal as a router ID).
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.
The area border router (ABR), autonomous system border router (ASBR), internal router (IR), and backbone router (BR) are all attributes of an OSPF process. A given physical router may have one or more OSPF processes.
Do not confuse these with designated router (DR), or backup designated router (BDR), which is an attribute of a router interface.
[edit] Area border router
An 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 to which that router is connected.
[edit] Autonomous system boundary router
An ASBR is a router that is connected to more than one AS and that exchanges routing information with routers in other ASs. ASBRs typically also run a non-IGP routing protocol (e.g., BGP), or use static routes, or both. An ASBR is used to distribute routes received from other ASs throughout its own AS.
[edit] Internal router
An IR is a router that has only OSPF neighbor relationships with routers in the same area.
[edit] Backbone router
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 interface elected among all routers on a particular multiaccess network segment, generally assumed to be broadcast multiaccess. Special techniques, often vendor-dependent, may be needed to support the DR function on nonbroadcast multiaccess (NBMA) media. It is usually wise to configure the individual virtual circuits of a NBMA subnet as individual point-to-point lines; the techniques used are implementation-dependent.
Do not confuse the DR with an OSPF router type. A given physical router can have some interfaces that are designated, others that are backup designated (BDR), and others that are non-designated. If no router is DR or BDR on a given subnet, the BDR is first elected, and then a second election is held if there is more than one BDR. The router winning the second election becomes DR, or, if there is no other BDR, designates itself DR. 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 (Backup Designated Router).
- 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 wins the election.
- 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.
- The priority values range between 0 - 254, 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.
- If the current DR 'goes down' the current BDR becomes the new DR and a new election takes place to find another BDR. If the new DR then 'goes down' and the original DR is now available, it then becomes DR again, but no change is made to the current BDR.
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 or ATM. DRs or BDRs are not elected on point-to-point links (such as a point-to-point WAN connection) because the two routers on either sides of the link must become fully adjacent and the bandwidth between them 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 Hello Packet
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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] Applications
OSPF was the first widely deployed routing protocol that could converge a network in the low seconds, and guarantee loop-free paths. It has a great many features that allow the imposition of policies about the propagation of routes that it may be appropriate to keep local, for load sharing, and for selective route importing more than IS-IS. IS-IS, in contrast, can be tuned for lower overhead in a stable network, the sort more common in ISP than enterprise networks. There are some historical accidents that made IS-IS the preferred IGP for ISPs, but ISP's today may well choose to use the features of the now-efficient implementations of OSPF [5] [6].
As mentioned, OSPF can provide better load-sharing on external links than other IGPs. When the default route to an ISP is injected, and the same external cost specified, from multiple ASBRS, into OSPF as a Type I external route, other routers will go to the ASBR with the least path cost from its location. This can be tuned further by adjusting the external cost.
In contrast, if the default route from different ISPs is injected with different external costs, as a Type II external route, the lower-cost default becomes the primary exit and the higher-cost becomes the backup only.
[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 - OSPF for IPv6, RFC 2740.
- 2003, January - The OSPF NSSA Option updated, RFC 3101
- 2005, October - Prioritized Treatment of Specific OSPF Version 2 Packets and Congestion Avoidance, RFC 4222
- 2006, December - OSPF Version 2 Management Information Base, RFC 4750
- 2007, May - OSPF Version 3 Management Information Base, draft state
[edit] Implementations
- 6WINDGate, commercial embedded open-source routing modules from 6WIND including OSPFv2 and OSPFv3
- Vyatta, a commercial open-source router / firewall.
- 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 implementing RFC2328 (OSPFv2) and RFC2740 (OSPFv3) for both IPv4 and IPv6
- BIRD (http://bird.network.cz) implements RFC2328 OSPF
- GateD project included an RFC1583 OSPF implementation (UMD OSPF by University of Maryland).
[edit] References
- ^ Guidelines for creation, selection, and registration of an Autonomous System,RFC 1930, J. Hawkinson & T. Bates, March 1996
- ^ What Are OSPF Areas and Virtual Links?,Cisco Document ID: 13703,December 2005
- ^ Traffic Engineering (TE) Extensions to OSPF Version 2,RFC 3630, D. Katz et al.,September 2003
- ^ IP over Optical Networks: A Framework,RFC 3717, B. Rajagopalan et al.,March 2004
- ^ [|Berkowitz, Howard] (1999), "OSPF Goodies for ISPs", North American Network Operator Group NANOG 17, Montreal
- ^ Kata, Dave (2000), "OSPF and IS-IS: A Comparative Anatomy", North American Network Operator Group NANOG 19, Albuquerque
[edit] External links
- IETF OSPF Working Group
- OSPF Basics
- Design and Implementation of OpenOSPFD (Paper)
- Design and Implementation of OpenOSPFD (Presentation)
- Cisco OSPF
- Cisco OSPF Areas and Virtual Links
- OSPF Tutorial
- OSPF Lecture Notes
- Summary of OSPF v2
- IS-IS and OSPF difference discussion (Vishwas Manral, Manav bhatia and Yasuhiro Ohara)
[edit] Further reading
- Andrew Colton, OSPF for Cisco Routers http://www.amazon.com/OSPF-Cisco-Routers-CCIE-Library/dp/0972286217/
- William R. Parkhurst, Cisco OSPF Command and Configuration Handbook. ISBN 978-1-58705-071-8
- John T. Moy, OSPF - Anatomy of a Internet Routing Protocol.
- Jeff Doyle, Jennifer Carroll, Routing TCP/IP, Volume 1, 2nd Edition http://www.ciscopress.com/bookstore/product.asp?isbn=1587052024
