OSPF ( English Open Shortest Path First ) is a dynamic routing protocol based on link-state technology and using Dijkstra's algorithm to find the shortest path.
Ospf | |
---|---|
Title | Open shortest path first |
Level (by OSI model ) | Networked |
Family | TCP / IP |
Created by | 1988 |
Port / ID | |
Protocol assignment | Dynamic routing protocol |
Specification | RFC 2328 |
Basic implementations (clients) | OpenOSPFD , GNU Zebra , Quagga , Cisco IOS , Mikrotik RouterOS |
Basic implementations ( servers ) | OpenOSPFD, GNU Zebra, Quagga, Cisco IOS, Mikrotik RouterOS, HP Comware |
The OSPF protocol was developed by the IETF in 1988. The latest version of the protocol is presented in RFC 2328 (1998). The OSPF protocol is the Interior Gateway Protocol ( IGP ). OSPF spreads information about available routes between routers on a single autonomous system .
OSPF has the following advantages:
- High rate of convergence compared to distance vector routing protocols ;
- Support for network variable length masks ( VLSM );
- Optimum use of bandwidth with the construction of a tree of shortest paths.
Content
OSPF protocol terminology
- Interface - the connection between the router and one of the networks connected to it. When discussing OSPF, the terms interface and link are often used as synonyms.
- Link-State Advertisement (LSA) —An announcement describes all the channels of the router, all interfaces, and the state of the channels.
- Link state (link state) - link state between two routers; updates occur using LSA packages.
- Metric (metric) - a conditional indicator of the "cost" of sending data through the channel.
- An autonomous system (autonomous system) is a collection of networks under a single administrative control, providing a common routing policy for all members of an autonomous system of routers. Typically, an autonomous system is managed by one Internet service provider The autonomous system uses the IGP internal gateway protocols (RIP, OSPF and IS-IS).
- Area (area) - a set of networks and routers that have the same zone ID.
- Neighbors (neighbors) - routers that have interfaces in a common network (zone).
- The adjacency state is the interconnection between certain neighboring routers established for the exchange of routing information.
- Hello protocol (hello protocol) - used to maintain neighbor relations.
- Database neighbors (neighbors database) - a list of all neighbors.
- The link state database (LSDB) is a list of all channel status records. The term topological database is also used; it is used as a synonym for the channel status database.
- A router ID (RID) is a unique 32-bit number that uniquely identifies a router within a single autonomous system.
Protocol Job Description
The principle of operation is as follows:
- After turning on routers, the protocol looks for directly connected neighbors and establishes “friendly” relations with them.
- Then they exchange with each other information about the networks connected and accessible to them. That is, they build a network map (network topology). This card is the same on all routers.
- Based on the information received, an SPF (Shortest Path First — Choosing the best path) algorithm is run, which calculates the best route to each network. This process is similar to building a tree, the root of which is the router itself, and the branches are the paths to the available networks. This process, that is, convergence, occurs very quickly.
OSPF-supported network types
- Broadcast networks with multiple access ( Ethernet , Token Ring )
- Point-to-point (T1, E1, dial-up access)
- Non-broadcasting multiple access network (NBMA) ( Frame relay )
Dedicated Router (DR) and Backup Dedicated Router (BDR)
In multiple-access networks, neighborhood relations are established between all routers. If all routers in a neighborhood state exchanged topological information, this would result in sending a large number of LSAs. If, for example, the number of routers in a network with multiple access is n , then n (n-1) / 2 neighborhood relations will be established. Each router will send n-1 LSA to its neighbors, plus one LSA for the network, as a result, the network will generate n² LSA.
To prevent the problem of sending LSA copies on multiple-access networks, a dedicated router (DR) and a spare dedicated router (BDR) are selected.
Dedicated router (designated router, DR) - manages the process of sending LSA in the network. Each network router establishes an adjacency relationship with DR. Information about changes in the network is sent by the router that detected this change to the dedicated router, and the latter, in turn, is responsible for ensuring that this information is sent to the rest of the routers in the multiple access segment.
The disadvantage of working with a DR router is that when it fails, a new DR must be selected. New neighborhood relationships must be formed and, while the router databases are not synchronized with the new DR database, the network will not be available to forward packets. To eliminate this drawback, BDR is chosen.
Backup dedicated router (backup designated router, BDR). Each network router establishes a neighborhood relationship not only with DR, but also with BDR. DR and BDR also establish neighborhood relationships with each other. When DR fails, BDR becomes DR and performs all its functions. Since the network routers have established a neighborhood relationship with the BDR, the network downtime is minimized.
A router selected by a DR or BDR in one multi-access network connected to it may not be DR (BDR) in another attached multi-access network. The role of DR (BDR) is a property of the interface, and not a property of the entire router. In other words, in each segment of multiple access (for example, a switching segment of Ethernet) in which two or more OSPF routers communicate, the selection process and distribution of DR / BDR roles occurs independently of other segments of multiple access.
Protocol Timers
- HelloInterval - The time interval in seconds after which the router sends the next hello packet from the interface. For broadcast and point-to-point networks, the default is usually 10 seconds. For non-broadcast networks with multiple access, the default value is 30 seconds.
- RouterDeadInterval - The time interval in seconds after which the neighbor will be considered "dead." This interval must be a multiple of the HelloInterval value. As a rule, RouterDeadInterval is equal to 4 intervals of sending hello-packages, that is 40 seconds.
- Wait Timer - The time interval in seconds after which the router will select DR on the network. Its value is equal to the value of the interval RouterDeadInterval.
- RxmtInterval - The time interval in seconds after which the router re-sends a packet to which it did not receive an acknowledgment of receipt (for example, Database Description packet or Link State Request packets). This interval is also called the Retransmit interval. The interval value is 5 seconds.
Types of routers
Internal router (internal router) - a router, all interfaces of which belong to the same zone. These routers have only one link state database.
Border router (area border router, ABR) - connects one or more zones with the trunk zone and acts as a gateway for inter-zone traffic. The border router always has at least one interface belonging to the backbone. For each attached zone, the router maintains a separate link state database.
Backbone router (backbone router) - a router which always has at least one interface belonging to the backbone zone. The definition is similar to a border router, but a trunk router is not always a border router. The internal router, whose interfaces belong to the zero zone, is also a trunk.
An autonomous system border router (AS boundary router, ASBR) is a router, one of the ports of which is in the domain of the OSPF protocol and the other in the domain of any of the internal gateway protocols (for example, RIP or EIGRP). The autonomous system border router can be located anywhere on the autonomous system and be a border or trunk router.
Types of channel state advertisements (LSA)
Type 1 LSA - Router LSA - announcement of the status of the channels of the router. These LSAs are distributed by all routers. LSA contains a description of all the channels of the router and the cost (cost) of each channel. Distributed only within the same zone.
Type 2 LSA - Network LSA - announcement of the status of network channels. Distributed by DR in networks with multiple access. The LSA contains a description of all routers connected to the network, including DR. Distributed only within the same zone.
Type 3 LSA - Network Summary LSA - the summary announcement of the status of network channels. The announcement is distributed by border routers. The advertisement describes only routes to networks outside the zone and does not describe routes within the autonomous system. The border router sends a separate advertisement for each network it knows about.
When a router receives a Network Summary LSA from a border router, it does not run the shortest path calculation algorithm. The router simply adds to the cost of the route specified in the LSA the cost of the route to the border router. Then the route to the network through the border router is placed in the routing table.
Type 4 LSA - ASBR Summary LSA is a summary of the status of the channels of the autonomous system's border router. The announcement is distributed by border routers. ASBR Summary LSA differs from Network Summary LSA in that it does not provide information about the network, but about the autonomous system border router.
Type 5 LSA - AS External LSA - announcement of the state of the external channels of the autonomous system. The announcement is distributed by the autonomous system border router within the entire autonomous system. An advertisement describes routes that are external to an autonomous OSPF system, or default routes that are external routes to an autonomous OSPF system.
Type 6 LSA - Multicast OSPF LSA is a specialized LSA that uses multicast OSPF applications (not implemented by Cisco).
Type 7 LSA - AS External LSA for NSSA - announcements of the status of external channels of an autonomous system in the NSSA zone. This announcement can only be transmitted in the NSSA zone. At the edge of the zone, the border router converts type 7 LSA to type 5 LSA.
Type 8 LSA - Link LSA - announces the link-local address and prefix (s) of the router to all routers dividing the channel (link). Dispatched only if more than one router is present on the link. Distributed only within the channel (link).
Type 9 LSA - Intra-Area-Prefix LSA associates: a list of IPv6 prefixes and a router, pointing to Router LSA, a list of IPv6 prefixes and a transit network, pointing to Network LSA. Distributed only within the same zone.
Types of zones
When autonomous system is divided into zones, routers belonging to one zone are not aware of the detailed topology of other zones.
The division into zones allows you to:
- Reduce the load on the CPU of routers by reducing the number of recalculations using the OSPF algorithm
- Reduce the size of the routing tables
- Reduce the number of channel state update packages
Each zone is assigned an area ID. The identifier can be specified in decimal format or in the format of the IP address . However, zone IDs are not IP addresses and can match any assigned IP address.
There are several types of zones:
Backbone Area
The backbone zone (also known as zero zone or 0.0.0.0 zone) forms the core of the OSPF network. All other zones are connected to it, and inter-zone routing occurs through a router connected to the trunk zone. The trunk zone is responsible for distributing routing information between non-trunk zones. The trunk zone must be contiguous with other zones, but it does not have to be physically contiguous; connection to the trunk zone can also be established using virtual channels.
Standard area
Normal zone that is created by default. This zone accepts channel updates, summary routes and external routes.
Stub area (stub area)
The stub zone does not accept information about external routes for the autonomous system, but accepts routes from other zones. If routers from a dead-end zone need to send information across the autonomous system, then they use the default route. The ASBR cannot be in a dead-end zone.
Totally stubby area
Totally stubby area does not accept information about external routes for the autonomous system and routes from other zones. If routers need to send information outside the zone, then they use the default route. Cisco proprietary zone type.
Not-so-stubby area (NSSA)
The NSSA zone defines an additional type of LSA - LSA type 7. In the NSSA zone there may be an ASBR.
OSPF packet format
The OSPF packet is encapsulated directly in the data field of the IP packet . The value of the “upper layer protocol” field in the IP datagram header for OSPF is 89.
Package Header
Octet | 0 | one | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten | eleven | 12 | 13 | 14 | 15 | sixteen | 17 | 18 | nineteen | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | thirty | 31 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0—3 | Version | Type | Packet length | |||||||||||||||||||||||||||||
4-7 | Router ID | |||||||||||||||||||||||||||||||
8—11 | Area ID | |||||||||||||||||||||||||||||||
12—15 | Checksum | Authentication type | ||||||||||||||||||||||||||||||
16-19 | Authentication | |||||||||||||||||||||||||||||||
20–23 |
- Version — The OSPF protocol version number, the current OSPF version for IPv4 networks is 2;
- Type - type of OSPF packet;
- Packet length - the length of the packet, including the header;
- Router ID - the identifier of the router, a unique 32-bit number identifying the router within the autonomous system;
- Area ID - 32-bit zone ID;
- Checksum - checksum field, calculated for the entire package, including the header;
- Authentication type - type of authentication scheme used, possible values:
- 0 - authentication is not used
- 1 - plain text authentication
- 2 - MD5 authentication
- Authentication - authentication data field.
Hello Package
Hello package is designed to establish and maintain relations with neighbors. The packet is periodically sent to all interfaces of the router.
Octet | 0 | one | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten | eleven | 12 | 13 | 14 | 15 | sixteen | 17 | 18 | nineteen | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | thirty | 31 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0—3 | Version | Type = 1 | Packet length | |||||||||||||||||||||||||||||
4-7 | Router ID | |||||||||||||||||||||||||||||||
8—11 | Area ID | |||||||||||||||||||||||||||||||
12—15 | Checksum | Authentication type | ||||||||||||||||||||||||||||||
16-19 | Authentication | |||||||||||||||||||||||||||||||
20–23 | ||||||||||||||||||||||||||||||||
24–27 | Network mask | |||||||||||||||||||||||||||||||
28–31 | Hello interval | Options | Router priority | |||||||||||||||||||||||||||||
32—35 | Router dead interval | |||||||||||||||||||||||||||||||
36—39 | Designated router | |||||||||||||||||||||||||||||||
40—43 | Backup designated router | |||||||||||||||||||||||||||||||
44—47 | Neighbor ID | |||||||||||||||||||||||||||||||
... | ... |
- Network mask - the network mask of the interface through which the hello packet is sent;
- Hello interval - the interval that sets the frequency of sending welcome messages for finding neighbors in an autonomous system, the default value for LAN is 10 seconds;
- Options - 8-bit options field, describes the capabilities of the router;
- Router priority - router priority, an 8-bit number that symbolizes router priority when DR ( Designated router ) and BDR ( Backup designated router ) are selected;
- Router dead interval - the period of time during which the router waits for a response from neighbors;
- Designated router (DR) - DR IP address;
- Backup designated router (BDR) - BDR IP address;
- Neighbor ID - the ID of the neighbor. The list is made up of the identifiers of the neighbors from which the router received hello packets during the time specified in the router dead interval field;
Database Description
The Database Description package describes the contents of the channel status database. Packet exchange is performed when establishing the state of adjacency.
Octet | 0 | one | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten | eleven | 12 | 13 | 14 | 15 | sixteen | 17 | 18 | nineteen | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | thirty | 31 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0—3 | Version | Type = 2 | Packet length | |||||||||||||||||||||||||||||
4-7 | Router ID | |||||||||||||||||||||||||||||||
8—11 | Area ID | |||||||||||||||||||||||||||||||
12—15 | Checksum | Authentication type | ||||||||||||||||||||||||||||||
16-19 | Authentication | |||||||||||||||||||||||||||||||
20–23 | ||||||||||||||||||||||||||||||||
24–27 | Interface MTU | Options | 0 | 0 | 0 | 0 | 0 | I | M | MS | ||||||||||||||||||||||
28–31 | DD sequence number | |||||||||||||||||||||||||||||||
LSA headers |
- Interface MTU is the size in bytes of the largest IP datagram that can be sent through this interface without fragmentation;
- I-bit - set for the first packet in the sequence;
- M-bit - indicates the presence of subsequent additional packages;
- MS-bit - set for the master, cleared for the slave;
- DD sequence number - in the initial packet is set to a unique value, with the transmission of each subsequent packet increases by one, until the entire database is transferred;
- LSA headers - an array of channel state database headers.
Link State Request
The Link State Request packet is designed to request a part of the database of a neighboring router.
Octet | 0 | one | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten | eleven | 12 | 13 | 14 | 15 | sixteen | 17 | 18 | nineteen | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | thirty | 31 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0—3 | Version | Type = 3 | Packet length | |||||||||||||||||||||||||||||
4-7 | Router ID | |||||||||||||||||||||||||||||||
8—11 | Area ID | |||||||||||||||||||||||||||||||
12—15 | Checksum | Authentication type | ||||||||||||||||||||||||||||||
16-19 | Authentication | |||||||||||||||||||||||||||||||
20–23 | ||||||||||||||||||||||||||||||||
24–27 | LS Type | |||||||||||||||||||||||||||||||
28–31 | Link State ID | |||||||||||||||||||||||||||||||
32—35 | Advertising router | |||||||||||||||||||||||||||||||
... | ... |
- LS Type - type of channel status advertisement;
- Link State ID - routing domain identifier;
- Advertising Router - the identifier of the router that created the ad on the channel status.
Link State Update
Package Link State Update is designed to send announcements about the status of the channel. The packet is sent to the group address in one transit area .
Octet | 0 | one | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten | eleven | 12 | 13 | 14 | 15 | sixteen | 17 | 18 | nineteen | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | thirty | 31 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0—3 | Version | Type = 4 | Packet length | |||||||||||||||||||||||||||||
4-7 | Router ID | |||||||||||||||||||||||||||||||
8—11 | Area ID | |||||||||||||||||||||||||||||||
12—15 | Checksum | Authentication type | ||||||||||||||||||||||||||||||
16-19 | Authentication | |||||||||||||||||||||||||||||||
20–23 | ||||||||||||||||||||||||||||||||
24–27 | Number of LSA | |||||||||||||||||||||||||||||||
LSA |
- Number of LSA - the number of ads in the package.
Link State Acknowledgment
Confirms receipt of the Link State Update package.
Octet | 0 | one | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten | eleven | 12 | 13 | 14 | 15 | sixteen | 17 | 18 | nineteen | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | thirty | 31 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0—3 | Version | Type = 5 | Packet length | |||||||||||||||||||||||||||||
4-7 | Router ID | |||||||||||||||||||||||||||||||
8—11 | Area ID | |||||||||||||||||||||||||||||||
12—15 | Checksum | Authentication type | ||||||||||||||||||||||||||||||
16-19 | Authentication | |||||||||||||||||||||||||||||||
20–23 | ||||||||||||||||||||||||||||||||
LSA headers |
OSPF protocol versions
OSPF Version 1
OSPF Version 2
supports IPv4 version
OSPF Version 3
supports IPv6 version
Criticism
It is believed that due to the use of Dijkstra’s specific criterion for the quality of the distribution of input information, it absolutely does not protect the IP network from overload, which requires the implementation of additional methods to reduce the likelihood of overload. For example, it is proposed to use the residual bandwidth in the distribution criteria. [2]
At the same time, the relative simplicity of the practical implementation of the algorithm can be attributed to the positive qualities of the protocol.
See also
- Intermediate System Routing Protocol ( IS-IS )
- Shortest Path Bridging (SPB)
Notes
- ↑ https://www.iana.org/assignments/protocol-numbers/protocol-numbers.xhtml
- ↑ N. A. Kuznetsov , VN Fetisov, Queuing Systems , “Dijkstra's Algorithm with Improved Robustness for Routing Control in IP Networks” ( [1] ), PACS 02.10.Ox, Automation and Remote Control , № 2, 2008 .
Literature
- Tom M. Thomas II. Structure and implementation of networks based on the OSPF protocol. Cisco Guide = OSPF Network Design Solutions. - 2nd ed. - M .: “Williams” , 2004. - p. 816. - ISBN 1-58705-032-3 .