6 .. index:: Link-state routing protocol
7 .. index:: Distance-vector routing protocol
9 :abbr:`OSPF` is, mostly, a link-state routing protocol. In contrast to
10 :term:`distance-vector` protocols, such as :abbr:`RIP` or :abbr:`BGP`, where
11 routers describe available `paths` (i.e. routes) to each other, in
12 :term:`link-state` protocols routers instead describe the state of their links
13 to their immediate neighbouring routers.
15 .. index:: Link State Announcement
16 .. index:: Link State Advertisement
17 .. index:: LSA flooding
18 .. index:: Link State Database
20 Each router describes their link-state information in a message known as an
21 :abbr:`LSA (Link State Advertisement)`, which is then propagated through to all
22 other routers in a link-state routing domain, by a process called `flooding`.
23 Each router thus builds up an :abbr:`LSDB (Link State Database)` of all the
24 link-state messages. From this collection of LSAs in the LSDB, each router can
25 then calculate the shortest path to any other router, based on some common
26 metric, by using an algorithm such as
27 `Edgar Djikstra's <http://www.cs.utexas.edu/users/EWD/>`_
28 :abbr:`SPF (Shortest Path First)` algorithm.
30 .. index:: Link-state routing protocol advantages
32 By describing connectivity of a network in this way, in terms of
33 routers and links rather than in terms of the paths through a network,
34 a link-state protocol can use less bandwidth and converge more quickly
35 than other protocols. A link-state protocol need distribute only one
36 link-state message throughout the link-state domain when a link on any
37 single given router changes state, in order for all routers to
38 reconverge on the best paths through the network. In contrast, distance
39 vector protocols can require a progression of different path update
40 messages from a series of different routers in order to converge.
42 .. index:: Link-state routing protocol disadvantages
44 The disadvantage to a link-state protocol is that the process of
45 computing the best paths can be relatively intensive when compared to
46 distance-vector protocols, in which near to no computation need be done
47 other than (potentially) select between multiple routes. This overhead
48 is mostly negligible for modern embedded CPUs, even for networks with
49 thousands of nodes. The primary scaling overhead lies more in coping
50 with the ever greater frequency of LSA updates as the size of a
51 link-state area increases, in managing the :abbr:`LSDB` and required
54 This section aims to give a distilled, but accurate, description of the
55 more important workings of :abbr:`OSPF` which an administrator may need
56 to know to be able best configure and trouble-shoot :abbr:`OSPF`.
61 :abbr:`OSPF` defines a range of mechanisms, concerned with detecting,
62 describing and propagating state through a network. These mechanisms
63 will nearly all be covered in greater detail further on. They may be
67 .. index:: OSPF Hello Protocol
72 The OSPF Hello protocol allows OSPF to quickly detect changes in two-way
73 reachability between routers on a link. OSPF can additionally avail of other
74 sources of reachability information, such as link-state information provided by
75 hardware, or through dedicated reachability protocols such as
76 :abbr:`BFD (Bidirectional Forwarding Detection)`.
78 OSPF also uses the Hello protocol to propagate certain state between routers
79 sharing a link, for example:
81 - Hello protocol configured state, such as the dead-interval.
82 - Router priority, for DR/BDR election.
83 - DR/BDR election results.
84 - Any optional capabilities supported by each router.
86 The Hello protocol is comparatively trivial and will not be explored in greater
89 .. index:: OSPF LSA overview
95 At the heart of :abbr:`OSPF` are :abbr:`LSA (Link State Advertisement)`
96 messages. Despite the name, some :abbr:`LSA` s do not, strictly speaking,
97 describe link-state information. Common :abbr:`LSA` s describe information
100 - Routers, in terms of their links.
101 - Networks, in terms of attached routers.
102 - Routes, external to a link-state domain:
105 Routes entirely external to :abbr:`OSPF`. Routers originating such
106 routes are known as :abbr:`ASBR (Autonomous-System Border Router)`
110 Routes which summarise routing information relating to OSPF areas
111 external to the OSPF link-state area at hand, originated by
112 :abbr:`ABR (Area Boundary Router)` routers.
114 .. _ospf-lsa-flooding:
119 OSPF defines several related mechanisms, used to manage synchronisation of
120 :abbr:`LSDB` s between neighbours as neighbours form adjacencies and the
121 propagation, or `flooding` of new or updated :abbr:`LSA` s.
123 .. index:: OSPF Areas overview
130 OSPF provides for the protocol to be broken up into multiple smaller and
131 independent link-state areas. Each area must be connected to a common backbone
132 area by an :abbr:`ABR (Area Boundary Router)`. These :abbr:`ABR` routers are
133 responsible for summarising the link-state routing information of an area into
134 `Summary LSAs`, possibly in a condensed (i.e. aggregated) form, and then
135 originating these summaries into all other areas the :abbr:`ABR` is connected
138 Note that only summaries and external routes are passed between areas. As
139 these describe *paths*, rather than any router link-states, routing between
140 areas hence is by :term:`distance-vector`, **not** link-state.
145 The core objects in OSPF are :abbr:`LSA` s. Everything else in OSPF revolves
146 around detecting what to describe in LSAs, when to update them, how to flood
147 them throughout a network and how to calculate routes from them.
149 There are a variety of different :abbr:`LSA` s, for purposes such as describing
150 actual link-state information, describing paths (i.e. routes), describing
151 bandwidth usage of links for :abbr:`TE (Traffic Engineering)` purposes, and
152 even arbitrary data by way of *Opaque* :abbr:`LSA` s.
157 All LSAs share a common header with the following information:
161 Different types of :abbr:`LSA` s describe different things in
162 :abbr:`OSPF`. Types include:
166 - Network Summary LSA
170 The specifics of the different types of LSA are examined below.
174 The Router ID of the router originating the LSA.
178 :clicmd:`ospf router-id A.B.C.D`.
182 The ID of the LSA, which is typically derived in some way from the
183 information the LSA describes, e.g. a Router LSA uses the Router ID as
184 the LSA ID, a Network LSA will have the IP address of the :abbr:`DR`
187 The combination of the Type, ID and Advertising Router ID must uniquely
188 identify the :abbr:`LSA`. There can however be multiple instances of
189 an LSA with the same Type, LSA ID and Advertising Router ID, see
190 :ref:`sequence number <ospf-lsa-sequence-number>`.
194 A number to allow stale :abbr:`LSA` s to, eventually, be purged by routers
195 from their :abbr:`LSDB` s.
197 The value nominally is one of seconds. An age of 3600, i.e. 1 hour, is
198 called the `MaxAge`. MaxAge LSAs are ignored in routing
199 calculations. LSAs must be periodically refreshed by their Advertising
200 Router before reaching MaxAge if they are to remain valid.
202 Routers may deliberately flood LSAs with the age artificially set to
203 3600 to indicate an LSA is no longer valid. This is called
204 `flushing` of an LSA.
206 It is not abnormal to see stale LSAs in the LSDB, this can occur where
207 a router has shutdown without flushing its LSA(s), e.g. where it has
208 become disconnected from the network. Such LSAs do little harm.
210 .. _ospf-lsa-sequence-number:
214 A number used to distinguish newer instances of an LSA from older instances.
219 Of all the various kinds of :abbr:`LSA` s, just two types comprise the
220 actual link-state part of :abbr:`OSPF`, Router :abbr:`LSA` s and
221 Network :abbr:`LSA` s. These LSA types are absolutely core to the
224 Instances of these LSAs are specific to the link-state area in which
225 they are originated. Routes calculated from these two LSA types are
226 called `intra-area routes`.
230 Each OSPF Router must originate a router :abbr:`LSA` to describe
231 itself. In it, the router lists each of its :abbr:`OSPF` enabled
232 interfaces, for the given link-state area, in terms of:
235 The output cost of that interface, scaled inversely to some commonly known
236 reference value, :clicmd:`auto-cost reference-bandwidth (1-4294967`.
241 A link to a multi-access network, on which the router has at least one
242 Full adjacency with another router.
244 :abbr:`PtP (Point-to-Point)`
245 A link to a single remote router, with a Full adjacency. No
246 :abbr:`DR (Designated Router)` is elected on such links; no network
247 LSA is originated for such a link.
250 A link with no adjacent neighbours, or a host route.
254 These values depend on the Link Type:
256 +----------------+-----------------------------------+------------------------------------------+
257 | Link Type | Link ID | Link Data |
258 +================+===================================+==========================================+
259 | Transit | Link IP address of the :abbr:`DR` | Interface IP address |
260 +----------------+-----------------------------------+------------------------------------------+
261 | Point-to-Point | Router ID of the remote router | Local interface IP address, or the |
262 | | | :abbr:`ifindex (MIB-II interface index)` |
263 | | | for unnumbered links |
264 +----------------+-----------------------------------+------------------------------------------+
265 | Stub | IP address | Subnet Mask |
266 +----------------+-----------------------------------+------------------------------------------+
268 Links on a router may be listed multiple times in the Router LSA, e.g. a
269 :abbr:`PtP` interface on which OSPF is enabled must *always* be described
270 by a Stub link in the Router :abbr:`LSA`, in addition to being listed as
271 PtP link in the Router :abbr:`LSA` if the adjacency with the remote router
274 Stub links may also be used as a way to describe links on which OSPF is
275 *not* spoken, known as `passive interfaces`, see
276 :clicmd:`passive-interface INTERFACE`.
280 On multi-access links (e.g. ethernets, certain kinds of ATM and X.25
281 configurations), routers elect a :abbr:`DR`. The :abbr:`DR` is
282 responsible for originating a Network :abbr:`LSA`, which helps reduce
283 the information needed to describe multi-access networks with multiple
284 routers attached. The :abbr:`DR` also acts as a hub for the flooding of
285 :abbr:`LSA` s on that link, thus reducing flooding overheads.
287 The contents of the Network LSA describes the:
291 As the :abbr:`LSA` ID of a Network LSA must be the IP address of the
292 :abbr:`DR`, the Subnet Mask together with the :abbr:`LSA` ID gives
293 you the network address.
297 Each router fully-adjacent with the :abbr:`DR` is listed in the LSA,
298 by their Router-ID. This allows the corresponding Router :abbr:`LSA` s to be
299 easily retrieved from the :abbr:`LSDB`.
301 Summary of Link State LSAs:
303 +-------------+----------------------------+--------------------------------------------+
304 | LSA Type | LSA ID | LSA Data Describes |
305 +=============+============================+============================================+
306 | Router LSA | Router ID | The :abbr:`OSPF` enabled links of the |
307 | | | router, within a specific link-state area. |
308 +-------------+----------------------------+--------------------------------------------+
309 | Network LSA | The IP address of the | The subnet mask of the network and the |
310 | | :abbr:`DR` for the network | Router IDs of all routers on the network |
311 +-------------+----------------------------+--------------------------------------------+
313 With an LSDB composed of just these two types of :abbr:`LSA`, it is
314 possible to construct a directed graph of the connectivity between all
315 routers and networks in a given OSPF link-state area. So, not
316 surprisingly, when OSPF routers build updated routing tables, the first
317 stage of :abbr:`SPF` calculation concerns itself only with these two
320 .. _ospf-link-state-lsa-examples:
322 Link-State LSA Examples
323 ^^^^^^^^^^^^^^^^^^^^^^^
325 The example below shows two :abbr:`LSA` s, both originated by the same router
326 (Router ID 192.168.0.49) and with the same :abbr:`LSA` ID (192.168.0.49), but
327 of different LSA types.
329 The first LSA being the router LSA describing 192.168.0.49's links: 2 links
330 to multi-access networks with fully-adjacent neighbours (i.e. Transit
331 links) and 1 being a Stub link (no adjacent neighbours).
333 The second LSA being a Network LSA, for which 192.168.0.49 is the
334 :abbr:`DR`, listing the Router IDs of 4 routers on that network which
335 are fully adjacent with 192.168.0.49.
339 # show ip ospf database router 192.168.0.49
341 OSPF Router with ID (192.168.0.53)
343 Router Link States (Area 0.0.0.0)
346 Options: 0x2 : *|-|-|-|-|-|E|*
350 Link State ID: 192.168.0.49
351 Advertising Router: 192.168.0.49
352 LS Seq Number: 80000f90
357 Link connected to: a Transit Network
358 (Link ID) Designated Router address: 192.168.1.3
359 (Link Data) Router Interface address: 192.168.1.3
360 Number of TOS metrics: 0
363 Link connected to: a Transit Network
364 (Link ID) Designated Router address: 192.168.0.49
365 (Link Data) Router Interface address: 192.168.0.49
366 Number of TOS metrics: 0
369 Link connected to: Stub Network
370 (Link ID) Net: 192.168.3.190
371 (Link Data) Network Mask: 255.255.255.255
372 Number of TOS metrics: 0
374 # show ip ospf database network 192.168.0.49
376 OSPF Router with ID (192.168.0.53)
378 Net Link States (Area 0.0.0.0)
381 Options: 0x2 : *|-|-|-|-|-|E|*
384 Link State ID: 192.168.0.49 (address of Designated Router)
385 Advertising Router: 192.168.0.49
386 LS Seq Number: 80000074
390 Attached Router: 192.168.0.49
391 Attached Router: 192.168.0.52
392 Attached Router: 192.168.0.53
393 Attached Router: 192.168.0.54
396 Note that from one LSA, you can find the other. E.g. Given the
397 Network-LSA you have a list of Router IDs on that network, from which
398 you can then look up, in the local :abbr:`LSDB`, the matching Router
399 LSA. From that Router-LSA you may (potentially) find links to other
400 Transit networks and Routers IDs which can be used to lookup the
401 corresponding Router or Network LSA. And in that fashion, one can find
402 all the Routers and Networks reachable from that starting :abbr:`LSA`.
404 Given the Router LSA instead, you have the IP address of the
405 :abbr:`DR` of any attached transit links. Network LSAs will have that IP
406 as their LSA ID, so you can then look up that Network LSA and from that
407 find all the attached routers on that link, leading potentially to more
408 links and Network and Router LSAs, etc. etc.
410 From just the above two :abbr:`LSA` s, one can already see the
411 following partial topology:
415 ------------------------ Network: ......
416 | Designated Router IP: 192.168.1.3
421 Router ID: 192.168.0.49(stub)---------- IP: 192.168.3.190/32
422 (cost: 10) (cost: 39063)
427 ------------------------------ Network: 192.168.0.48/29
428 | | | Designated Router IP: 192.168.0.49
430 | | Router ID: 192.168.0.54
432 | Router ID: 192.168.0.53
434 Router ID: 192.168.0.52
437 Note the Router IDs, though they look like IP addresses and often are
438 IP addresses, are not strictly speaking IP addresses, nor need they be
439 reachable addresses (though, OSPF will calculate routes to Router IDs).
444 External, or "Type 5", :abbr:`LSA` s describe routing information which is
445 entirely external to :abbr:`OSPF`, and is "injected" into
446 :abbr:`OSPF`. Such routing information may have come from another
447 routing protocol, such as RIP or BGP, they may represent static routes
448 or they may represent a default route.
450 An :abbr:`OSPF` router which originates External :abbr:`LSA` s is known as an
451 :abbr:`ASBR (AS Boundary Router)`. Unlike the link-state :abbr:`LSA` s, and
452 most other :abbr:`LSA` s, which are flooded only within the area in
453 which they originate, External :abbr:`LSA` s are flooded through-out
454 the :abbr:`OSPF` network to all areas capable of carrying External
455 :abbr:`LSA` s (:ref:`ospf-areas`).
457 Routes internal to OSPF (intra-area or inter-area) are always preferred
458 over external routes.
460 The External :abbr:`LSA` describes the following:
463 The IP Network number of the route is described by the :abbr:`LSA` ID field.
466 The body of the External LSA describes the IP Network Mask of the route.
467 This, together with the :abbr:`LSA` ID, describes the prefix of the IP route
471 The cost of the External Route. This cost may be an OSPF cost (also known as
472 a "Type 1" metric), i.e. equivalent to the normal OSPF costs, or an
473 externally derived cost ("Type 2" metric) which is not comparable to OSPF
474 costs and always considered larger than any OSPF cost. Where there are both
475 Type 1 and 2 External routes for a route, the Type 1 is always preferred.
478 The address of the router to forward packets to for the route. This may be,
479 and usually is, left as 0 to specify that the ASBR originating the External
480 :abbr:`LSA` should be used. There must be an internal OSPF route to the
481 forwarding address, for the forwarding address to be usable.
484 An arbitrary 4-bytes of data, not interpreted by OSPF, which may carry
485 whatever information about the route which OSPF speakers desire.
487 AS External LSA Example
488 ^^^^^^^^^^^^^^^^^^^^^^^
490 To illustrate, below is an example of an External :abbr:`LSA` in the
491 :abbr:`LSDB` of an OSPF router. It describes a route to the IP prefix of
492 192.168.165.0/24, originated by the ASBR with Router-ID 192.168.0.49. The
493 metric of 20 is external to OSPF. The forwarding address is 0, so the route
494 should forward to the originating ASBR if selected.
498 # show ip ospf database external 192.168.165.0
500 Options: 0x2 : *|-|-|-|-|-|E|*
502 LS Type: AS-external-LSA
503 Link State ID: 192.168.165.0 (External Network Number)
504 Advertising Router: 192.168.0.49
505 LS Seq Number: 800001d8
509 Metric Type: 2 (Larger than any link state path)
512 Forward Address: 0.0.0.0
513 External Route Tag: 0
516 We can add this to our partial topology from above, which now looks
519 --------------------- Network: ......
520 | Designated Router IP: 192.168.1.3
522 IP: 192.168.1.3 /---- External route: 192.168.165.0/24
523 (transit link) / Cost: 20 (External metric)
525 Router ID: 192.168.0.49(stub)---------- IP: 192.168.3.190/32
526 (cost: 10) (cost: 39063)
531 ------------------------------ Network: 192.168.0.48/29
532 | | | Designated Router IP: 192.168.0.49
534 | | Router ID: 192.168.0.54
536 | Router ID: 192.168.0.53
538 Router ID: 192.168.0.52
544 Summary LSAs are created by :abbr:`ABR` s to summarise the destinations
545 available within one area to other areas. These LSAs may describe IP networks,
546 potentially in aggregated form, or :abbr:`ASBR` routers.