OSPF Fundamentals
=================

OSPF is, mostly, a link-state routing protocol. In contrast to distance-vector protocols, such as RIP or BGP, where routers describe available paths (i.e. routes) to each other, in link-state protocols routers instead describe the state of their links to their immediate neighbouring routers.

Each router describes their link-state information in a message known as an LSA (Link State Advertisement), which is then propogated through to all other routers in a link-state routing domain, by a process called flooding. Each router thus builds up an LSDB (Link State Database) of all the link-state messages. From this collection of LSAs in the LSDB, each router can then calculate the shortest path to any other router, based on some common metric, by using an algorithm such as Edgser Dijkstra (http://www.cs.utexas.edu/users/EWD/)'s SPF (Shortest Path First).

By describing connectivity of a network in this way, in terms of routers and links rather than in terms of the paths through a network, a link-state protocol can use less bandwidth and converge more quickly than other protocols. A link-state protocol need distribute only one link-state message throughout the link-state domain when a link on any single given router changes state, in order for all routers to reconverge on the best paths through the network. In contrast, distance vector protocols can require a progression of different path update messages from a series of different routers in order to converge.

The disadvantage to a link-state protocol is that the process of computing the best paths can be relatively intensive when compared to distance-vector protocols, in which near to no computation need be done other than (potentially) select between multiple routes. This overhead is mostly negligible for modern embedded CPUs, even for networks with thousands of nodes. The primary scaling overhead lies more in coping with the ever greater frequency of LSA updates as the size of a link-state area increases, in managing the LSDB and required flooding.

This section aims to give a distilled, but accurate, description of the more important workings of OSPF which an administrator may need to know to be able best configure and trouble-shoot OSPF.

OSPF Mechanisms
---------------

OSPF defines a range of mechanisms, concerned with detecting, describing and propogating state through a network. These mechanisms will nearly all be covered in greater detail further on. They may be broadly classed as:

The Hello Protocol

     The OSPF Hello protocol allows OSPF to quickly detect changes in two-way reachability between routers on a link. OSPF can additionally avail of other sources of reachability information, such as link-state information provided by hardware, or through dedicated reachability protocols such as BFD (Bi-directional Forwarding Detection).

     OSPF also uses the Hello protocol to propagate certain state between routers sharing a link, for example:

       * Hello protocol configured state, such as the dead-interval.

       * Router priority, for DR/BDR election.

       * DR/BDR election results.

       * Any optional capabilities supported by each router.

     The Hello protocol is comparatively trivial and will not be explored in greater detail than here.

LSAs

     At the heart of OSPF are LSA (Link State Advertisement) messages. Despite the name, some LSAs do not, strictly speaking, describe link-state information. Common LSAs describe information such as:

       * Routers, in terms of their links.

       * Networks, in terms of attached routers.

       * Routes, external to a link-state domain:

            * External Routes

               Routes entirely external to OSPF. Routers originating such routes are known as ASBR (Autonomous-System Border Router) routers.

            * Summary Routes

               Routes which summarise routing information relating to OSPF areas external to the OSPF link-state area at hand, originated by ABR (Area Boundary Router) routers.

LSA Flooding
     OSPF defines several related mechanisms, used to manage synchronisation of LSDBs between neighbours as neighbours form adjacencies and the propogation, or flooding of new or updated LSAs.

     See OSPF Flooding.

Areas
     OSPF provides for the protocol to be broken up into multiple smaller and independent link-state areas. Each area must be connected to a common backbone area by an ABR (Area Boundary Router). These ABR routers are responsible for summarising the link-state routing information of an area into Summary LSAs, possibly in a condensed (i.e. aggregated) form, and then originating these summaries into all other areas the ABR is connected to.

     Note that only summaries and external routes are passed between areas. As these describe paths, rather than any router link-states, routing between areas hence is by distance-vector, not link-state.

     See OSPF Areas.

OSPF LSAs
---------

LSAs are the core object in OSPF. Everything else in OSPF revolves around detecting what to describe in LSAs, when to update them, how to flood them throughout a network and how to calculate routes from them.

There are a variety of different LSAs, for purposes such as describing actual link-state information, describing paths (i.e. routes), describing bandwidth usage of links for TE (Traffic Engineering) purposes, and even arbitrary data by way of Opaque LSAs.

LSA Header
..........

All LSAs share a common header with the following information:

  * Type

     Different types of LSAs describe different things in OSPF. Types include:

       * Router LSA

       * Network LSA

       * Network Summary LSA

       * Router Summary LSA

       * AS-External LSA

     The specifics of the different types of LSA are examined below.

  * Advertising Router

     The Router ID of the router originating the LSA, see ospf router-id.

  * LSA ID

     The ID of the LSA, which is typically derived in some way from the information the LSA describes, e.g. a Router LSA uses the Router ID as the LSA ID, a Network LSA will have the IP address of the DR as its LSA ID.

     The combination of the Type, ID and Advertising Router ID must uniquely identify the LSA. There can however be multiple instances of an LSA with the same Type, LSA ID and Advertising Router ID, see LSA Sequence Number.

  * Age

     A number to allow stale LSAs to, eventually, be purged by routers from their LSDBs.

     The value nominally is one of seconds. An age of 3600, i.e. 1 hour, is called the MaxAge. MaxAge LSAs are ignored in routing calculations. LSAs must be periodically refreshed by their Advertising Router before reaching MaxAge if they are to remain valid.

     Routers may deliberately flood LSAs with the age artificially set to 3600 to indicate an LSA is no longer valid. This is called flushing of an LSA.

     It is not abnormal to see stale LSAs in the LSDB, this can occur where a router has shutdown without flushing its LSA(s), e.g. where it has become disconnected from the network. Such LSAs do little harm.

  * Sequence Number

     A number used to distinguish newer instances of an LSA from older instances.

Link-State LSAs
...............

Of all the various kinds of LSAs, just two types comprise the actual link-state part of OSPF, Router LSAs and Network LSAs. These LSA types are absolutely core to the protocol.

Instances of these LSAs are specific to the link-state area in which they are originated. Routes calculated from these two LSA types are called intra-area routes.

  * Router LSA

     Each OSPF Router must originate a router LSA to describe itself. In it, the router lists each of its OSPF enabled interfaces, for the given link-state area, in terms of:

       * Cost

          The output cost of that interface, scaled inversely to some commonly known reference value, see auto-cost reference-bandwidth.

       * Link Type

            * Transit Network

               A link to a multi-access network, on which the router has at least one Full adjacency with another router.

            * PtP (Point-to-Point)

               A link to a single remote router, with a Full adjacency. No DR (Designated Router) is elected on such links; no network LSA is originated for such a link.

            * Stub

               A link with no adjacent neighbours, or a host route.

       * Link ID and Data

          These values depend on the Link Type:

          Link Type   Link ID   Link Data

          Transit
          Link IP address of the DR
          Interface IP address

          Point-to-Point
          Router ID of the remote router
          Local interface IP address,
          or the ifindex (MIB-II interface index)
          for unnumbered links

          Stub
          IP address
          Subnet Mask

     Links on a router may be listed multiple times in the Router LSA, e.g. a PtP interface on which OSPF is enabled must always be described by a Stub link in the Router LSA, in addition to being listed as PtP link in the Router LSA if the adjacency with the remote router is Full.

     Stub links may also be used as a way to describe links on which OSPF is not spoken, known as passive interfaces, see passive-interface.

  * Network LSA

     On multi-access links (e.g. ethernets, certain kinds of ATM and X.25 configurations), routers elect a DR. The DR is responsible for originating a Network LSA, which helps reduce the information needed to describe multi-access networks with multiple routers attached. The DR also acts as a hub for the flooding of LSAs on that link, thus reducing flooding overheads.

     The contents of the Network LSA describes the:

       * Subnet Mask

          As the LSA ID of a Network LSA must be the IP address of the DR, the Subnet Mask together with the LSA ID gives you the network address.

       * Attached Routers

          Each router fully-adjacent with the DR is listed in the LSA, by their Router-ID. This allows the corresponding Router LSAs to be easily retrieved from the LSDB.

Summary of Link State LSAs:

LSA Type   LSA ID Describes   LSA Data Describes

Router LSA
The Router ID
The OSPF enabled links of the router, within
a specific link-state area.

Network LSA
The IP address of the DR for the network
The Subnet Mask of the network, and the Router IDs of all routers
on the network.

With an LSDB composed of just these two types of LSA, it is possible to construct a directed graph of the connectivity between all routers and networks in a given OSPF link-state area. So, not surprisingly, when OSPF routers build updated routing tables, the first stage of SPF calculation concerns itself only with these two LSA types.

Link-State LSA Examples
.......................

The example below (see OSPF Link-State LSA Example) shows two LSAs, both originated by the same router (Router ID 192.168.0.49) and with the same LSA ID (192.168.0.49), but of different LSA types.

The first LSA being the router LSA describing 192.168.0.49's links: 2 links to multi-access networks with fully-adjacent neighbours (i.e. Transit links) and 1 being a Stub link (no adjacent neighbours).

The second LSA being a Network LSA, for which 192.168.0.49 is the DR, listing the Router IDs of 4 routers on that network which are fully adjacent with 192.168.0.49.

     # show ip ospf database router 192.168.0.49

            OSPF Router with ID (192.168.0.53)

                     Router Link States (Area 0.0.0.0)

       LS age: 38
       Options: 0x2  : *|-|-|-|-|-|E|*
       LS Flags: 0x6
       Flags: 0x2 : ASBR
       LS Type: router-LSA
       Link State ID: 192.168.0.49
       Advertising Router: 192.168.0.49
       LS Seq Number: 80000f90
       Checksum: 0x518b
       Length: 60
        Number of Links: 3

         Link connected to: a Transit Network
          (Link ID) Designated Router address: 192.168.1.3
          (Link Data) Router Interface address: 192.168.1.3
           Number of TOS metrics: 0
            TOS 0 Metric: 10

         Link connected to: a Transit Network
          (Link ID) Designated Router address: 192.168.0.49
          (Link Data) Router Interface address: 192.168.0.49
           Number of TOS metrics: 0
            TOS 0 Metric: 10

         Link connected to: Stub Network
          (Link ID) Net: 192.168.3.190
          (Link Data) Network Mask: 255.255.255.255
           Number of TOS metrics: 0
            TOS 0 Metric: 39063
     # show ip ospf database network 192.168.0.49

            OSPF Router with ID (192.168.0.53)

                     Net Link States (Area 0.0.0.0)

       LS age: 285
       Options: 0x2  : *|-|-|-|-|-|E|*
       LS Flags: 0x6
       LS Type: network-LSA
       Link State ID: 192.168.0.49 (address of Designated Router)
       Advertising Router: 192.168.0.49
       LS Seq Number: 80000074
       Checksum: 0x0103
       Length: 40
       Network Mask: /29
             Attached Router: 192.168.0.49
             Attached Router: 192.168.0.52
             Attached Router: 192.168.0.53
             Attached Router: 192.168.0.54

Note that from one LSA, you can find the other. E.g. Given the Network-LSA you have a list of Router IDs on that network, from which you can then look up, in the local LSDB, the matching Router LSA. From that Router-LSA you may (potentially) find links to other Transit networks and Routers IDs which can be used to lookup the corresponding Router or Network LSA. And in that fashion, one can find all the Routers and Networks reachable from that starting LSA.

Given the Router LSA instead, you have the IP address of the DR of any attached transit links. Network LSAs will have that IP as their LSA ID, so you can then look up that Network LSA and from that find all the attached routers on that link, leading potentially to more links and Network and Router LSAs, etc. etc.

From just the above two LSAs, one can already see the following partial topology:

        --------------------- Network: ......
                 |            Designated Router IP: 192.168.1.3
                 |
           IP: 192.168.1.3
            (transit link)
             (cost: 10)
        Router ID: 192.168.0.49(stub)---------- IP: 192.168.3.190/32
             (cost: 10)        (cost: 39063)
            (transit link)
           IP: 192.168.0.49
                 |
                 |
     ------------------------------ Network: 192.168.0.48/29
       |        |           |       Designated Router IP: 192.168.0.49
       |        |           |
       |        |     Router ID: 192.168.0.54
       |        |
       |   Router ID: 192.168.0.53
       |
     Router ID: 192.168.0.52

Note the Router IDs, though they look like IP addresses and often are IP addresses, are not strictly speaking IP addresses, nor need they be reachable addresses (though, OSPF will calculate routes to Router IDs).

External LSAs
.............

External, or "Type 5", LSAs describe routing information which is entirely external to OSPF, and is "injected" into OSPF. Such routing information may have come from another routing protocol, such as RIP or BGP, they may represent static routes or they may represent a default route.

An OSPF router which originates External LSAs is known as an ASBR (AS Boundary Router). Unlike the link-state LSAs, and most other LSAs, which are flooded only within the area in which they originate, External LSAs are flooded through-out the OSPF network to all areas capable of carrying External LSAs (see OSPF Areas).

Routes internal to OSPF (intra-area or inter-area) are always preferred over external routes.

The External LSA describes the following:

  * IP Network number

     The IP Network number of the route is described by the LSA ID field.

  * IP Network Mask

     The body of the External LSA describes the IP Network Mask of the route. This, together with the LSA ID, describes the prefix of the IP route concerned.

  * Metric

     The cost of the External Route. This cost may be an OSPF cost (also known as a "Type 1" metric), i.e. equivalent to the normal OSPF costs, or an externally derived cost ("Type 2" metric) which is not comparable to OSPF costs and always considered larger than any OSPF cost. Where there are both Type 1 and 2 External routes for a route, the Type 1 is always preferred.

  * Forwarding Address

     The address of the router to forward packets to for the route. This may be, and usually is, left as 0 to specify that the ASBR originating the External LSA should be used. There must be an internal OSPF route to the forwarding address, for the forwarding address to be useable.

  * Tag

     An arbitrary 4-bytes of data, not interpreted by OSPF, which may carry whatever information about the route which OSPF speakers desire.

AS External LSA Example
.......................

To illustrate, below is an example of an External LSA in the LSDB of an OSPF router. It describes a route to the IP prefix of 192.168.165.0/24, originated by the ASBR with Router-ID 192.168.0.49. The metric of 20 is external to OSPF. The forwarding address is 0, so the route should forward to the originating ASBR if selected.

     # show ip ospf database external 192.168.165.0
       LS age: 995
       Options: 0x2  : *|-|-|-|-|-|E|*
       LS Flags: 0x9
       LS Type: AS-external-LSA
       Link State ID: 192.168.165.0 (External Network Number)
       Advertising Router: 192.168.0.49
       LS Seq Number: 800001d8
       Checksum: 0xea27
       Length: 36
       Network Mask: /24
             Metric Type: 2 (Larger than any link state path)
             TOS: 0
             Metric: 20
             Forward Address: 0.0.0.0
             External Route Tag: 0

We can add this to our partial topology from above, which now looks like:

        --------------------- Network: ......
                 |            Designated Router IP: 192.168.1.3
                 |
           IP: 192.168.1.3      /---- External route: 192.168.165.0/24
            (transit link)     /                Cost: 20 (External metric)
             (cost: 10)       /
        Router ID: 192.168.0.49(stub)---------- IP: 192.168.3.190/32
             (cost: 10)        (cost: 39063)
            (transit link)
           IP: 192.168.0.49
                 |
                 |
     ------------------------------ Network: 192.168.0.48/29
       |        |           |       Designated Router IP: 192.168.0.49
       |        |           |
       |        |     Router ID: 192.168.0.54
       |        |
       |   Router ID: 192.168.0.53
       |
     Router ID: 192.168.0.52

Summary LSAs
............

Summary LSAs are created by ABRs to summarise the destinations available within one area to other areas. These LSAs may describe IP networks, potentially in aggregated form, or ASBR routers.

OSPF Flooding
-------------

OSPF Areas
----------