Open Shortest Path First

from Wikipedia, the free encyclopedia
The articles Link_State_Advertisement and Open_Shortest_Path_First overlap thematically. Help me to better differentiate or merge the articles (→  instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Xvschmidt ( discussion ) 5:34 p.m. , Sep 28. 2016 (CEST)
OSPF, IP (IPv4 / IPv6) in the TCP / IP protocol stack :
application HTTP IMAP SMTP DNS ...
transport TCP UDP
Internet OSPF, IP (IPv4 / IPv6)
Network access Ethernet Token
bus 		Token
ring 		FDDI ...

Open Shortest Path First ( OSPF ) refers to a by the IETF developed link-state - routing protocol. It is specified in RFC 2328 (obsolete: RFC 1247 from 1991) and is based on the " shortest path " algorithm developed by Edsger W. Dijkstra .

OSPF is perhaps the most widely used Interior Gateway Protocol (IGP) in large corporate networks . The most commonly used Exterior Gateway Protocol (EGP) is the Border Gateway Protocol (BGP), the main routing protocol between autonomous systems on the Internet.

overview

In order to compensate for the disadvantages of RIP ( Routing Information Protocol ), the Open-Shortest-Path-First-Procedure (OSPF) was developed from 1988. The main advantages of OSPF over RIP are faster convergence and better scalability for larger networks. As the name suggests, OSPF has two characteristics, that of being open in the sense of a public specification as RFC 2328 and that of using the SPF algorithm . In UNIX systems, OSPF is implemented as a gated daemon. OSPF belongs to the class of link-state routing protocols. RFC 5340 applies to IPv6 .

The standard does not define how the costs are to be calculated. The basis of the SPF algorithm is not, as the name suggests, the number of hops, but the path costs. The decision criterion for the advantageousness of a route and thus the metric is the nominal data rate.

More recent trends among operators of IP networks show that there is increasing use of IS-IS in connection with MPLS because the IS-IS features are sufficient, the protocol is less complex than OSPF and, in comparison, scales better. Nevertheless, OSPF is still the predominantly used routing protocol today.

Features of OSPF

  • OSPF guarantees loop-free routing in contrast to RIP
  • It uses the Hello protocol to monitor neighbors
  • It supports VLSM as well as CIDR
  • OSPF is well suited for large, scalable networks
  • The area concept simplifies communication and maintenance
  • OSPF can use the BFD protocol to enable convergence times in the millisecond range in the event of an error

Hierarchical structure through areas

A fundamental and important concept in OSPF is the hierarchy in so-called areas . All OSPF routers can be assigned to different areas . The so-called backbone area (area 0) has a special position. All other regular areas must be connected directly to this backbone area . If a direct connection is not possible, this remote can Areas through virtual links with the backbone area are connected.

Backbone area

If more than one area is used, they must be linked directly or indirectly using a virtual link via a backbone area . This backbone area always has the number 0 and, as the highest OSPF hierarchy instance, represents the connecting bridge between all areas.

Regular area

All other areas except the backbone area are regular areas . The area number can be a numerical value between 1 and 4294967295 (= 2 32 - 1) or an equivalent network ID (e.g. 192.168.1.0).

Transit area

Normally, a regular area must be directly connected to the backbone area . However, if a regular area cannot be connected directly to the backbone area for design reasons , virtual links must be configured as an aid. This bridge an intermediate area , which then to transit area is. The virtual links represent a type of tunnel connection between an area and the backbone area ; however, the traffic between participants in the remote area and the transit area is switched directly, ie not via the backbone area.

Stub area

A stub area is a regular area in which the area border routers filter the forwarding of type 5 LSA messages. This means that for all normal routers in a stub area, their area border router is propagated as a gateway.

Totally stubby area

A Totally Stubby Area (TSA) is a regular area in which its area border routers filter the forwarding of LSA messages of type 3, 4 and 5. This means that for all normal routers in a Totally Stubby Area, only their area border router is propagated as a gateway.

Not So Stubby Area

A Not So Stubby Area (NSSA) is a stub area that learns external routes through another IGP or EGP protocol, but in which their area border routers filter the forwarding of type 5 LSA messages. This external routing information would normally not be propagated in a stub area . However, if the stub area is configured as a Not So Stubby Area , external routing updates with LSA messages of type 7 are forwarded to the area border router of the stub area . These in turn convert these type 7 LSA messages into type 5 LSA messages and propagate these external routes into the backbone area .

Totally Not-So-Stubby Area (TNSSA)

A Totally Not-So-Stubby Area (Totally NSSA) is a regular area in which its area border routers filter the forwarding of LSA messages of type 3, 4 and 5. As with NSSA, external routes are propagated with LSA messages of type 7 and converted into LSA messages of type 5 by ABR.

Designated router

In each (N) BMA network (LAN segment), one OSPF router is automatically selected as the designated router and another as the backup designated router . All regular routers send their updates to the designated router , which in turn is the only one that forwards updates to all other routers. If a designated router fails , the backup designated router takes over its tasks and becomes the designated router itself . Another router in the LAN segment is immediately selected as the Backup Designated Router .

Area border router

Each area has an area border router (ABR). This ABR serves as an interface between a regular area and the backbone area . If there is only one router in an area , this is automatically also the designated router (DR). If there are several routers in an area , an algorithm is used to automatically propagate one router to the ABR and another to the backup ABR. All other routers are treated as normal routers.

An ABR can filter LSA messages and use route summarization to combine several routes in order to simplify routing tables.

Autonomous System Boundary Router

If a router learns external routes via an IGP or EGP protocol and propagates them in the OSPF network, it represents an Autonomous System Boundary Router (ASBR).

Load sharing

If alternative network paths have the same metric path costs from the point of view of OSPF, then these paths are used alternately in order to enable load distribution .

Working method

OSPF topology

The core of OSPF is the neighborhood database (adjacency database) / LSD (Link State Database) , which contains a list of all neighboring routers to which there is a bidirectional connection. It reflects the topology of the network. Routing information must be exchanged so that this database is set up or updated when the topology changes. These are transmitted by means of flooding . In order to keep the amount of information to be exchanged low, OSPF routers choose a designated router (DR) and a backup router BDR (Backup Designated Router ) , which serve as interfaces for the exchange. The OSPF router whose multi-access interface has the highest router priority becomes DR . If two routers have the same priority, the router with the higher router ID is selected. The IP address of a loopback interface or - depending on the manufacturer - the interface with the numerically highest IP address / the first active interface is automatically selected as the router ID.

Link State Advertisements LSA

OSPF routers exchange information about the accessible networks with so-called LSA messages (Link State Advertisements). The following LSA types are defined here:

  • Router-LSA (type 1): An entry is created in the router-LSA for each active link of the router that belongs to the area to be considered. In addition to the IP address of the link, the network mask of the link and the network type (loopback, point-to-point, normal network) are entered in it.
  • Network-LSA (type 2): The designated router (DR) of a network segment creates a network-LSA for this network which, in addition to the network address and mask, also contains a list of the other adjacent routers.
  • Summary-LSA (type 3/4): Information about destinations outside an area can be sent from the ABR (area border router) depending on the configuration as LSA type 3 (if it is network information) or LSA type 4 ( in the case of routed router accessibility) can be passed on to another area. Type 3 LSAs are also used to propagate default routes in (stub) areas.
  • AS-External LSA (type 5): Routers that lock their own autonomous system from the point of view of the OSPF can generate type 5 LSAs for externally learned or manually configured routes. These contain the network address and mask of the target network as well as a reference to the announcing router. A common use of type 5 LSAs is to inject default routes into the backbone area.
  • NSSA External LSA (Type 7): LSA Type 7 is generated on the NSSA ASBR. Type-5 LSAs are not allowed in NSSA areas, so the NSSA ASBR generates Type-7 LSAs for them. An NSSA external LSA is almost identical to an AS external LSA. In contrast to the AS-External-LSAs, which are flooded by an entire OSPF-AS, NSSA-External-LSAs are only flooded within the NSSA area in which they were generated.
  • Opaque-LSA (type 9): This type of LSA is distributed link locally and therefore not across routers. This type of LSA is currently used for a graceful restart function.
  • Opaque LSA (type 10): This type of LSA is distributed locally to the area. This type of LSA is currently used for traffic engineering functions.
  • Opaque-LSA / Graceful Restart (Type 11): This type of LSA is flooded AS widely. RFC 5187 replaces the Opaque-LSA type with Graceful Restart LSA. However, this change only applies to OSPFv3. Use of this type of LSA is currently not known.

Designated router

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

Designated router (German: nominated router) is optionally used in Open Shortest Path First to reduce the network load generated by the routing process in broadcast networks with many OSPF routers.

In order to curb the amount of LSAs to be transmitted, a designated router (DR) is chosen in networks that do not consist of isolated point-to-point connections. The DR is responsible for distributing the update information within its network segment. The DR thus rises to become the administrative center of an area. The Backup-Designated Router (BDR) takes on the role of its deputy.

The choice of a designated router is transparent. The decision criterion is the highest router priority, this is determined by the Hello protocol. If no router priorities have been configured or the router priorities should be the same, the router ID is used to decide who will be the designated router. The router ID is the loopback address, if one is not configured, the highest configured IP address of the router is selected. In special cases, the selection process can be influenced directly by configuring a router ID or generating a loopback address as a substitute. The election process takes place via the exchange of Hello packets. If the DR fails, the BDR takes on its role almost seamlessly without first initiating a new election process for a DR. This does not happen even if new routers with a higher IP address have been added in the meantime. Finally, a BDR is elected.

protocol

Hello protocol

The Hello protocol is an integral part of the overall routing process in Open Shortest Path First for network operations. It is responsible for:

  • Sending keepalives at certain intervals (this confirms whether the neighboring router is still working and its routes are still valid),
  • To discover a newly added neighbor router,
  • Negotiation of parameters, such as hello and dead timer intervals,
  • Choice of a Designated Router (DR) and the backup DR.

All incoming Hello packets are checked for the Area ID and other parameters. If these match the local settings, this router is entered as a neighbor.

OSPF version 2

OSPF header
0 1 2 3 4th 5 6th 7th 8th 9 10 11 12 13 14th 15th 16 17th 18th 19th 20th 21st 22nd 23 24 25th 26th 27 28 29 30th 31
version Type Length
Router ID
Area ID
Checksum AuType
Authentication
Data
  • The size of the Version field is 8 bits.
  • The size of the Type field is 8 bits.
Type description reference
1 Hello RFC 2328 , RFC 5340
2 Database description RFC 2328 , RFC 5340
3 Link state request RFC 2328 , RFC 5340
4th Link state update RFC 2328 , RFC 5340
5 Link state acknowledgment RFC 2328 , RFC 5340
  • The size of the Length field is 16 bits. It contains the total package length.
  • The size of the Router ID field is 32 bits.
  • The size of the Area ID field is 32 bits.
  • The size of the checksum field is 16 bits. It contains the standard IP checksum.
  • The size of the AuType field (authentication type) is 16 bits.
Authentication type description reference
0 None RFC 2328
1 Simple password authentication RFC 2328
2 Cryptographic authentication RFC 2328
3 to 65535 Reserved
  • The size of the Authentication field is 64 bits.

OSPF version 3

OSPF header version 3
0 1 2 3 4th 5 6th 7th 8th 9 10 11 12 13 14th 15th 16 17th 18th 19th 20th 21st 22nd 23 24 25th 26th 27 28 29 30th 31
Version
(version) 		Type
(type) 		Length
(length)
Router ID
(router identifier)
Area ID
(area identifier)
Checksum
(checksum) 		Instance ID
(instance identifier) 		Reserved
(reserved)
Data
(data)
  • Version 3 of the OSPF is intended for IPv6 and is defined in RFC 5340 .
  • The Instance ID (instance identifier) ​​is 8 bits.
  • Reserved is 8 bits.

Differences between OSPFv2 and OSPFv3

The protocol definition of OSPFv3 introduced some differences to OSPFv2 in addition to the extension to include IPv6 functionality. The differences are listed below:

  • The term “subnet” has been replaced by “link”. The background is the definition of an interface. In OSPFv2, an interface is viewed as a subnet, which means that only one neighborhood relationship in one subnet can take place on an interface. However, an interface can also contain several subnets and want to establish a neighborhood relationship using this. This redefinition eliminates the situation and increases the opportunities for neighborhood formation.
  • Neighborhood detection based on the router ID. In OSPFv2, neighbors on NBMA links are recognized via the interface addresses. With point-to-point links, the neighbors are identified via the router ID. This difference is canceled in OSPFv3, and all neighbors are identified via the router ID.
  • Authentication removed. In OSPFv2 an authentication is carried out in the header. This was completely removed in OSPFv3. The function is now replaced by the IPv6 Authentication Header (function moved to the lower layer).
  • Forwarding of unknown LSA types. In OSPFv2, unknown LSA types are deleted and not distributed any further. OSPFv3 implementations should also forward unknown LSA types.

Free software implementations

  • Quagga (further development of GNU Zebra)
  • BIRD (open source implementation of an Ipv4 and Ipv6 capable TCP / IP routing daemon)
  • XORP (eXtensible Open Router Platform)
  • OpenOSPFD (Unix system service)

See also

literature

  • Wolfgang Schulte: Handbook of the routing protocols of the networks . SVH Verlag, 2009, ISBN 978-3-8381-1066-0 .
  • John T. Moy: OSPF: Anatomy of an Internet Routing Protocol . Addison-Wesley Longman Verlag, 1998, ISBN 0-201-63472-4 .

Web links

Individual evidence

  1. ^ EW Dijkstra: A Note on Two Problems in Connexion with Graphs. In: Numerical Mathematics. 1, 1959, pp. 269-271 ( www-m3.ma.tum.de PDF; 739 kB).
  2. ↑ What Are OSPF Areas and Virtual Links? cisco.com.
  3. ^ OSPF Not-So-Stubby Area (NSSA) cisco.com.
  4. ↑ Mike's Technology and Finance Blog: The OSPF Totally Not-So-Stubby-Area (NSSA).
  5. ↑ RFC 2328  - OSPF Version 2 . [Errata: RFC 2328 ]. April 1998. p. 75. (Replaces RFC 2178 - Section: 9.4: Electing the Designated Router  - English).
  6. ↑ ASBR - Autonomous System Boundary Router. In: Mpirical. Retrieved April 9, 2019 (UK English).