summaryrefslogtreecommitdiffstats
path: root/doc/user/ospf_fundamentals.rst
diff options
context:
space:
mode:
Diffstat (limited to 'doc/user/ospf_fundamentals.rst')
-rw-r--r--doc/user/ospf_fundamentals.rst558
1 files changed, 558 insertions, 0 deletions
diff --git a/doc/user/ospf_fundamentals.rst b/doc/user/ospf_fundamentals.rst
new file mode 100644
index 0000000..c566059
--- /dev/null
+++ b/doc/user/ospf_fundamentals.rst
@@ -0,0 +1,558 @@
+.. _ospf-fundamentals:
+
+OSPF Fundamentals
+=================
+
+.. index::
+ pair: Link-state routing protocol; OSPF
+ pair: Distance-vector routing protocol; OSPF
+
+
+:abbr:`OSPF` is, mostly, a link-state routing protocol. In contrast to
+:term:`distance-vector` protocols, such as :abbr:`RIP` or :abbr:`BGP`, where
+routers describe available `paths` (i.e. routes) to each other, in
+:term:`link-state` protocols routers instead describe the state of their links
+to their immediate neighbouring routers.
+
+.. index::
+ single: Link State Announcement
+ single: Link State Advertisement
+ single: LSA flooding
+ single: Link State Database
+
+
+Each router describes their link-state information in a message known as an
+:abbr:`LSA (Link State Advertisement)`, which is then propagated through to all
+other routers in a link-state routing domain, by a process called `flooding`.
+Each router thus builds up an :abbr:`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
+`Edsger Dijkstra's <http://www.cs.utexas.edu/users/EWD/>`_
+:abbr:`SPF (Shortest Path First)` algorithm.
+
+.. index::
+ pair: Link-state routing protocol; advantages
+
+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.
+
+.. index::
+ pair: Link-state routing protocol; disadvantages
+
+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 :abbr:`LSDB` and required
+flooding.
+
+This section aims to give a distilled, but accurate, description of the
+more important workings of :abbr:`OSPF` which an administrator may need
+to know to be able best configure and trouble-shoot :abbr:`OSPF`.
+
+OSPF Mechanisms
+---------------
+
+:abbr:`OSPF` defines a range of mechanisms, concerned with detecting,
+describing and propagating state through a network. These mechanisms
+will nearly all be covered in greater detail further on. They may be
+broadly classed as:
+
+
+.. index::
+ pair: Hello protocol; OSPF
+
+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
+:abbr:`BFD (Bidirectional 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 more
+detail.
+
+
+.. index::
+ pair: LSA; OSPF
+
+.. _ospf-lsas:
+
+LSAs
+^^^^
+
+At the heart of :abbr:`OSPF` are :abbr:`LSA (Link State Advertisement)`
+messages. Despite the name, some :abbr:`LSA` s do not, strictly speaking,
+describe link-state information. Common :abbr:`LSA` s 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 :abbr:`OSPF`. Routers originating such
+ routes are known as :abbr:`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
+ :abbr:`ABR (Area Boundary Router)` routers.
+
+.. _ospf-lsa-flooding:
+
+LSA Flooding
+""""""""""""
+
+OSPF defines several related mechanisms, used to manage synchronisation of
+:abbr:`LSDB` s between neighbours as neighbours form adjacencies and the
+propagation, or `flooding` of new or updated :abbr:`LSA` s.
+
+
+.. index::
+ pair: Area; OSPF
+
+.. _ospf-areas:
+
+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 :abbr:`ABR (Area Boundary Router)`. These :abbr:`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 :abbr:`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 :term:`distance-vector`, **not** link-state.
+
+OSPF LSAs
+---------
+
+The core objects in OSPF are :abbr:`LSA` s. 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 :abbr:`LSA` s, for purposes such as describing
+actual link-state information, describing paths (i.e. routes), describing
+bandwidth usage of links for :abbr:`TE (Traffic Engineering)` purposes, and
+even arbitrary data by way of *Opaque* :abbr:`LSA` s.
+
+LSA Header
+^^^^^^^^^^
+
+All LSAs share a common header with the following information:
+
+- Type
+
+ Different types of :abbr:`LSA` s describe different things in
+ :abbr:`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.
+
+.. seealso::
+
+ :clicmd:`ospf router-id A.B.C.D`.
+
+- 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 :abbr:`DR`
+ as its LSA ID.
+
+ The combination of the Type, ID and Advertising Router ID must uniquely
+ identify the :abbr:`LSA`. There can however be multiple instances of
+ an LSA with the same Type, LSA ID and Advertising Router ID, see
+ :ref:`sequence number <ospf-lsa-sequence-number>`.
+
+- Age
+
+ A number to allow stale :abbr:`LSA` s to, eventually, be purged by routers
+ from their :abbr:`LSDB` s.
+
+ 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.
+
+.. _ospf-lsa-sequence-number:
+
+- Sequence Number
+
+ A number used to distinguish newer instances of an LSA from older instances.
+
+Link-State LSAs
+^^^^^^^^^^^^^^^
+
+Of all the various kinds of :abbr:`LSA` s, just two types comprise the
+actual link-state part of :abbr:`OSPF`, Router :abbr:`LSA` s and
+Network :abbr:`LSA` s. 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 :abbr:`LSA` to describe
+ itself. In it, the router lists each of its :abbr:`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, :clicmd:`auto-cost reference-bandwidth (1-4294967)`.
+
+ Link Type
+ Transit Network
+
+ A link to a multi-access network, on which the router has at least one
+ Full adjacency with another router.
+
+ :abbr:`PtP (Point-to-Point)`
+ A link to a single remote router, with a Full adjacency. No
+ :abbr:`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 :abbr:`DR` | Interface IP address |
+ +----------------+-----------------------------------+------------------------------------------+
+ | Point-to-Point | Router ID of the remote router | Local interface IP address, or the |
+ | | | :abbr:`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
+ :abbr:`PtP` interface on which OSPF is enabled must *always* be described
+ by a Stub link in the Router :abbr:`LSA`, in addition to being listed as
+ PtP link in the Router :abbr:`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
+ :clicmd:`ip ospf passive [A.B.C.D]`.
+
+- Network LSA
+
+ On multi-access links (e.g. ethernets, certain kinds of ATM and X.25
+ configurations), routers elect a :abbr:`DR`. The :abbr:`DR` is
+ responsible for originating a Network :abbr:`LSA`, which helps reduce
+ the information needed to describe multi-access networks with multiple
+ routers attached. The :abbr:`DR` also acts as a hub for the flooding of
+ :abbr:`LSA` s on that link, thus reducing flooding overheads.
+
+ The contents of the Network LSA describes the:
+
+ - Subnet Mask
+
+ As the :abbr:`LSA` ID of a Network LSA must be the IP address of the
+ :abbr:`DR`, the Subnet Mask together with the :abbr:`LSA` ID gives
+ you the network address.
+
+ - Attached Routers
+
+ Each router fully-adjacent with the :abbr:`DR` is listed in the LSA,
+ by their Router-ID. This allows the corresponding Router :abbr:`LSA` s to be
+ easily retrieved from the :abbr:`LSDB`.
+
+Summary of Link State LSAs:
+
++-------------+----------------------------+--------------------------------------------+
+| LSA Type | LSA ID | LSA Data Describes |
++=============+============================+============================================+
+| Router LSA | Router ID | The :abbr:`OSPF` enabled links of the |
+| | | router, within a specific link-state area. |
++-------------+----------------------------+--------------------------------------------+
+| Network LSA | The IP address of the | The subnet mask of the network and the |
+| | :abbr:`DR` for the network | Router IDs of all routers on the network |
++-------------+----------------------------+--------------------------------------------+
+
+With an LSDB composed of just these two types of :abbr:`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 :abbr:`SPF` calculation concerns itself only with these two
+LSA types.
+
+.. _ospf-link-state-lsa-examples:
+
+Link-State LSA Examples
+^^^^^^^^^^^^^^^^^^^^^^^
+
+The example below shows two :abbr:`LSA` s, both originated by the same router
+(Router ID 192.168.0.49) and with the same :abbr:`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
+:abbr:`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 :abbr:`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 :abbr:`LSA`.
+
+Given the Router LSA instead, you have the IP address of the
+:abbr:`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 :abbr:`LSA` s, 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", :abbr:`LSA` s describe routing information which is
+entirely external to :abbr:`OSPF`, and is "injected" into
+:abbr:`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 :abbr:`OSPF` router which originates External :abbr:`LSA` s is known as an
+:abbr:`ASBR (AS Boundary Router)`. Unlike the link-state :abbr:`LSA` s, and
+most other :abbr:`LSA` s, which are flooded only within the area in
+which they originate, External :abbr:`LSA` s are flooded through-out
+the :abbr:`OSPF` network to all areas capable of carrying External
+:abbr:`LSA` s (:ref:`ospf-areas`).
+
+Routes internal to OSPF (intra-area or inter-area) are always preferred
+over external routes.
+
+The External :abbr:`LSA` describes the following:
+
+IP Network number
+ The IP Network number of the route is described by the :abbr:`LSA` ID field.
+
+IP Network Mask
+ The body of the External LSA describes the IP Network Mask of the route.
+ This, together with the :abbr:`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
+ :abbr:`LSA` should be used. There must be an internal OSPF route to the
+ forwarding address, for the forwarding address to be usable.
+
+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 :abbr:`LSA` in the
+:abbr:`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 :abbr:`ABR` s to summarise the destinations
+available within one area to other areas. These LSAs may describe IP networks,
+potentially in aggregated form, or :abbr:`ASBR` routers.