doc/ospf_fundamentals.texi - quagga - Gitiles

 @c Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
 @cindex OSPF Fundamentals
 @node OSPF Fundamentals
 @section OSPF Fundamentals

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

 @cindex Link State Announcement
 @cindex Link State Advertisement
 @cindex LSA flooding
 @cindex Link State DataBase
 Each router describes their link-state information in a message known
 as an @acronym{LSA,Link State Advertisement}, which is then propogated
 through to all other routers in a link-state routing domain, by a
 process called @dfn{flooding}. Each router thus builds up an
 @acronym{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 @url{http://www.cs.utexas.edu/users/EWD/,
 Edgser Dijkstra}'s @acronym{SPF,Shortest Path First}.

 @cindex 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.

 @cindex 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 @acronym{LSDB} and required
 flooding.

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

 @subsection OSPF Mechanisms

 @acronym{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:

 @table @dfn
 @cindex OSPF Hello Protocol overview
 @item The Hello Protocol

 @cindex OSPF 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 @acronym{BFD,Bi-directional Forwarding Detection}.

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

 @itemize @bullet
 @item Hello protocol configured state, such as the dead-interval.
 @item Router priority, for DR/BDR election.
 @item DR/BDR election results.
 @item Any optional capabilities supported by each router.
 @end itemize

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

 @cindex OSPF LSA overview
 @item LSAs

 At the heart of @acronym{OSPF} are @acronym{LSA,Link State
 Advertisement} messages. Despite the name, some @acronym{LSA}s do not,
 strictly speaking, describe link-state information. Common
 @acronym{LSA}s describe information such as:

 @itemize @bullet
 @item
 Routers, in terms of their links.
 @item
 Networks, in terms of attached routers.
 @item
 Routes, external to a link-state domain:

 @itemize @bullet
 @item External Routes

 Routes entirely external to @acronym{OSPF}@. Routers originating such
 routes are known as @acronym{ASBR,Autonomous-System Border Router}
 routers.

 @item Summary Routes

 Routes which summarise routing information relating to OSPF areas
 external to the OSPF link-state area at hand, originated by
 @acronym{ABR,Area Boundary Router} routers.
 @end itemize
 @end itemize

 @item LSA Flooding
 OSPF defines several related mechanisms, used to manage synchronisation of
 @acronym{LSDB}s between neighbours as neighbours form adjacencies and
 the propogation, or @dfn{flooding} of new or updated @acronym{LSA}s.

 @xref{OSPF Flooding}.

 @cindex OSPF Areas overview
 @item 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 @acronym{ABR,Area Boundary Router}. These
 @acronym{ABR} routers are responsible for summarising the link-state
 routing information of an area into @dfn{Summary LSAs}, possibly in a
 condensed (i.e. aggregated) form, and then originating these summaries
 into all other areas the @acronym{ABR} is connected to.

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

 @xref{OSPF Areas}.
 @end table

 @subsection OSPF LSAs

 @acronym{LSA}s 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 @acronym{LSA}s, for purposes such
 as describing actual link-state information, describing paths (i.e.
 routes), describing bandwidth usage of links for
 @acronym{TE,Traffic Engineering} purposes, and even arbitrary data
 by way of @emph{Opaque} @acronym{LSA}s.

 @subsubsection LSA Header
 All LSAs share a common header with the following information:

 @itemize @bullet
 @item Type

 Different types of @acronym{LSA}s describe different things in
 @acronym{OSPF}@. Types include:

 @itemize @bullet
 @item Router LSA
 @item Network LSA
 @item Network Summary LSA
 @item Router Summary LSA
 @item AS-External LSA
 @end itemize

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

 @item Advertising Router

 The Router ID of the router originating the LSA, see @ref{ospf router-id}.

 @item 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 @acronym{DR}
 as its LSA ID@.

 The combination of the Type, ID and Advertising Router ID must uniquely
 identify the @acronym{LSA}@. There can however be multiple instances of
 an LSA with the same Type, LSA ID and Advertising Router ID, see
 @ref{OSPF LSA sequence number,,LSA Sequence Number}.

 @item Age

 A number to allow stale @acronym{LSA}s to, eventually, be purged by routers
 from their @acronym{LSDB}s.

 The value nominally is one of seconds. An age of 3600, i.e. 1 hour, is
 called the @dfn{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
 @dfn{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.

 @anchor{OSPF LSA sequence number}
 @item Sequence Number

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

 @subsubsection Link-State LSAs
 Of all the various kinds of @acronym{LSA}s, just two types comprise the
 actual link-state part of @acronym{OSPF}, Router @acronym{LSA}s and
 Network @acronym{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 @dfn{intra-area routes}.

 @itemize @bullet
 @item Router LSA

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

 @itemize @bullet
 @item Cost

 The output cost of that interface, scaled inversely to some commonly known
 reference value, @xref{OSPF auto-cost reference-bandwidth,,auto-cost
 reference-bandwidth}.

 @item Link Type
 @itemize @bullet
 @item Transit Network

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

 @item @acronym{PtP,Point-to-Point}

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

 @item Stub

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

 @item Link ID and Data

 These values depend on the Link Type:

 @multitable @columnfractions .18 .32 .32
 @headitem Link Type @tab Link ID @tab Link Data

 @item Transit
 @tab Link IP address of the @acronym{DR}
 @tab Interface IP address

 @item Point-to-Point
 @tab Router ID of the remote router
 @tab Local interface IP address,
 or the @acronym{ifindex,MIB-II interface index}
 for unnumbered links

 @item Stub
 @tab IP address
 @tab Subnet Mask

 @end multitable
 @end itemize

 Links on a router may be listed multiple times in the Router LSA, e.g.
 a @acronym{PtP} interface on which OSPF is enabled must @emph{always}
 be described by a Stub link in the Router @acronym{LSA}, in addition to
 being listed as PtP link in the Router @acronym{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
 @emph{not} spoken, known as @dfn{passive interfaces}, see @ref{OSPF
 passive-interface,,passive-interface}.

 @item Network LSA

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

 The contents of the Network LSA describes the:

 @itemize @bullet
 @item Subnet Mask

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

 @item Attached Routers

 Each router fully-adjacent with the @acronym{DR} is listed in the LSA,
 by their Router-ID. This allows the corresponding Router @acronym{LSA}s to be
 easily retrieved from the @acronym{LSDB}@.
 @end itemize
 @end itemize

 Summary of Link State LSAs:

 @multitable @columnfractions .18 .32 .40
 @headitem LSA Type @tab LSA ID Describes @tab LSA Data Describes

 @item Router LSA
 @tab The Router ID
 @tab The @acronym{OSPF} enabled links of the router, within
      a specific link-state area.

 @item Network LSA
 @tab The IP address of the @acronym{DR} for the network
 @tab The Subnet Mask of the network, and the Router IDs of all routers
      on the network.
 @end multitable

 With an LSDB composed of just these two types of @acronym{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 @acronym{SPF} calculation concerns itself only with these two
 LSA types.

 @subsubsection Link-State LSA Examples

 The example below (@pxref{OSPF Link-State LSA Example}) shows two
 @acronym{LSA}s, both originated by the same router (Router ID
 192.168.0.49) and with the same @acronym{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
 @acronym{DR}, listing the Router IDs of 4 routers on that network which
 are fully adjacent with 192.168.0.49.

 @anchor{OSPF Link-State LSA Example}
 @example
 # 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
 @end example

 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 @acronym{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 @acronym{LSA}@.

 Given the Router LSA instead, you have the IP address of the
 @acronym{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 @acronym{LSA}s, one can already see the
 following partial topology:
 @example
 @group


    --------------------- 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
 @end group
 @end example

 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).

 @subsubsection External LSAs

 External, or "Type 5", @acronym{LSA}s describe routing information which is
 entirely external to @acronym{OSPF}, and is "injected" into
 @acronym{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 @acronym{OSPF} router which originates External @acronym{LSA}s is known as an
 @acronym{ASBR,AS Boundary Router}. Unlike the link-state @acronym{LSA}s, and
 most other @acronym{LSA}s, which are flooded only within the area in
 which they originate, External @acronym{LSA}s are flooded through-out
 the @acronym{OSPF} network to all areas capable of carrying External
 @acronym{LSA}s (@pxref{OSPF Areas}).

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

 The External @acronym{LSA} describes the following:

 @itemize @bullet
 @item IP Network number

 The IP Network number of the route is described by the @acronym{LSA} ID
 field.

 @item IP Network Mask

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

 @item 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.

 @item 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 @acronym{LSA} should be used. There must be an internal OSPF
 route to the forwarding address, for the forwarding address to be
 useable.

 @item Tag

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

 @subsubsection AS External LSA Example

 To illustrate, below is an example of an External @acronym{LSA} in the
 @acronym{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.

 @example
 @group
 # 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
 @end group
 @end example

 We can add this to our partial topology from above, which now looks
 like:
 @example
 @group
    --------------------- 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
 @end group
 @end example

 @subsubsection Summary LSAs

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

 @anchor{OSPF Flooding}
 @subsection OSPF Flooding

 @anchor{OSPF Areas}
 @subsection OSPF Areas
	@c Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
	@cindex OSPF Fundamentals
	@node OSPF Fundamentals
	@section OSPF Fundamentals

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

	@cindex Link State Announcement
	@cindex Link State Advertisement
	@cindex LSA flooding
	@cindex Link State DataBase
	Each router describes their link-state information in a message known
	as an @acronym{LSA,Link State Advertisement}, which is then propogated
	through to all other routers in a link-state routing domain, by a
	process called @dfn{flooding}. Each router thus builds up an
	@acronym{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 @url{http://www.cs.utexas.edu/users/EWD/,
	Edgser Dijkstra}'s @acronym{SPF,Shortest Path First}.

	@cindex 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.

	@cindex 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 @acronym{LSDB} and required
	flooding.

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

	@subsection OSPF Mechanisms

	@acronym{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:

	@table @dfn
	@cindex OSPF Hello Protocol overview
	@item The Hello Protocol

	@cindex OSPF 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 @acronym{BFD,Bi-directional Forwarding Detection}.

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

	@itemize @bullet
	@item Hello protocol configured state, such as the dead-interval.
	@item Router priority, for DR/BDR election.
	@item DR/BDR election results.
	@item Any optional capabilities supported by each router.
	@end itemize

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

	@cindex OSPF LSA overview
	@item LSAs

	At the heart of @acronym{OSPF} are @acronym{LSA,Link State
	Advertisement} messages. Despite the name, some @acronym{LSA}s do not,
	strictly speaking, describe link-state information. Common
	@acronym{LSA}s describe information such as:

	@itemize @bullet
	@item
	Routers, in terms of their links.
	@item
	Networks, in terms of attached routers.
	@item
	Routes, external to a link-state domain:

	@itemize @bullet
	@item External Routes

	Routes entirely external to @acronym{OSPF}@. Routers originating such
	routes are known as @acronym{ASBR,Autonomous-System Border Router}
	routers.

	@item Summary Routes

	Routes which summarise routing information relating to OSPF areas
	external to the OSPF link-state area at hand, originated by
	@acronym{ABR,Area Boundary Router} routers.
	@end itemize
	@end itemize

	@item LSA Flooding
	OSPF defines several related mechanisms, used to manage synchronisation of
	@acronym{LSDB}s between neighbours as neighbours form adjacencies and
	the propogation, or @dfn{flooding} of new or updated @acronym{LSA}s.

	@xref{OSPF Flooding}.

	@cindex OSPF Areas overview
	@item 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 @acronym{ABR,Area Boundary Router}. These
	@acronym{ABR} routers are responsible for summarising the link-state
	routing information of an area into @dfn{Summary LSAs}, possibly in a
	condensed (i.e. aggregated) form, and then originating these summaries
	into all other areas the @acronym{ABR} is connected to.

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

	@xref{OSPF Areas}.
	@end table

	@subsection OSPF LSAs

	@acronym{LSA}s 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 @acronym{LSA}s, for purposes such
	as describing actual link-state information, describing paths (i.e.
	routes), describing bandwidth usage of links for
	@acronym{TE,Traffic Engineering} purposes, and even arbitrary data
	by way of @emph{Opaque} @acronym{LSA}s.

	@subsubsection LSA Header
	All LSAs share a common header with the following information:

	@itemize @bullet
	@item Type

	Different types of @acronym{LSA}s describe different things in
	@acronym{OSPF}@. Types include:

	@itemize @bullet
	@item Router LSA
	@item Network LSA
	@item Network Summary LSA
	@item Router Summary LSA
	@item AS-External LSA
	@end itemize

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

	@item Advertising Router

	The Router ID of the router originating the LSA, see @ref{ospf router-id}.

	@item 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 @acronym{DR}
	as its LSA ID@.

	The combination of the Type, ID and Advertising Router ID must uniquely
	identify the @acronym{LSA}@. There can however be multiple instances of
	an LSA with the same Type, LSA ID and Advertising Router ID, see
	@ref{OSPF LSA sequence number,,LSA Sequence Number}.

	@item Age

	A number to allow stale @acronym{LSA}s to, eventually, be purged by routers
	from their @acronym{LSDB}s.

	The value nominally is one of seconds. An age of 3600, i.e. 1 hour, is
	called the @dfn{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
	@dfn{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.

	@anchor{OSPF LSA sequence number}
	@item Sequence Number

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

	@subsubsection Link-State LSAs
	Of all the various kinds of @acronym{LSA}s, just two types comprise the
	actual link-state part of @acronym{OSPF}, Router @acronym{LSA}s and
	Network @acronym{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 @dfn{intra-area routes}.

	@itemize @bullet
	@item Router LSA

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

	@itemize @bullet
	@item Cost

	The output cost of that interface, scaled inversely to some commonly known
	reference value, @xref{OSPF auto-cost reference-bandwidth,,auto-cost
	reference-bandwidth}.

	@item Link Type
	@itemize @bullet
	@item Transit Network

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

	@item @acronym{PtP,Point-to-Point}

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

	@item Stub

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

	@item Link ID and Data

	These values depend on the Link Type:

	@multitable @columnfractions .18 .32 .32
	@headitem Link Type @tab Link ID @tab Link Data

	@item Transit
	@tab Link IP address of the @acronym{DR}
	@tab Interface IP address

	@item Point-to-Point
	@tab Router ID of the remote router
	@tab Local interface IP address,
	or the @acronym{ifindex,MIB-II interface index}
	for unnumbered links

	@item Stub
	@tab IP address
	@tab Subnet Mask

	@end multitable
	@end itemize

	Links on a router may be listed multiple times in the Router LSA, e.g.
	a @acronym{PtP} interface on which OSPF is enabled must @emph{always}
	be described by a Stub link in the Router @acronym{LSA}, in addition to
	being listed as PtP link in the Router @acronym{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
	@emph{not} spoken, known as @dfn{passive interfaces}, see @ref{OSPF
	passive-interface,,passive-interface}.

	@item Network LSA

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

	The contents of the Network LSA describes the:

	@itemize @bullet
	@item Subnet Mask

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

	@item Attached Routers

	Each router fully-adjacent with the @acronym{DR} is listed in the LSA,
	by their Router-ID. This allows the corresponding Router @acronym{LSA}s to be
	easily retrieved from the @acronym{LSDB}@.
	@end itemize
	@end itemize

	Summary of Link State LSAs:

	@multitable @columnfractions .18 .32 .40
	@headitem LSA Type @tab LSA ID Describes @tab LSA Data Describes

	@item Router LSA
	@tab The Router ID
	@tab The @acronym{OSPF} enabled links of the router, within
	a specific link-state area.

	@item Network LSA
	@tab The IP address of the @acronym{DR} for the network
	@tab The Subnet Mask of the network, and the Router IDs of all routers
	on the network.
	@end multitable

	With an LSDB composed of just these two types of @acronym{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 @acronym{SPF} calculation concerns itself only with these two
	LSA types.

	@subsubsection Link-State LSA Examples

	The example below (@pxref{OSPF Link-State LSA Example}) shows two
	@acronym{LSA}s, both originated by the same router (Router ID
	192.168.0.49) and with the same @acronym{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
	@acronym{DR}, listing the Router IDs of 4 routers on that network which
	are fully adjacent with 192.168.0.49.

	@anchor{OSPF Link-State LSA Example}
	@example
	# 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
	@end example

	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 @acronym{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 @acronym{LSA}@.

	Given the Router LSA instead, you have the IP address of the
	@acronym{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 @acronym{LSA}s, one can already see the
	following partial topology:
	@example
	@group


	--------------------- 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
	@end group
	@end example

	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).

	@subsubsection External LSAs

	External, or "Type 5", @acronym{LSA}s describe routing information which is
	entirely external to @acronym{OSPF}, and is "injected" into
	@acronym{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 @acronym{OSPF} router which originates External @acronym{LSA}s is known as an
	@acronym{ASBR,AS Boundary Router}. Unlike the link-state @acronym{LSA}s, and
	most other @acronym{LSA}s, which are flooded only within the area in
	which they originate, External @acronym{LSA}s are flooded through-out
	the @acronym{OSPF} network to all areas capable of carrying External
	@acronym{LSA}s (@pxref{OSPF Areas}).

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

	The External @acronym{LSA} describes the following:

	@itemize @bullet
	@item IP Network number

	The IP Network number of the route is described by the @acronym{LSA} ID
	field.

	@item IP Network Mask

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

	@item 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.

	@item 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 @acronym{LSA} should be used. There must be an internal OSPF
	route to the forwarding address, for the forwarding address to be
	useable.

	@item Tag

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

	@subsubsection AS External LSA Example

	To illustrate, below is an example of an External @acronym{LSA} in the
	@acronym{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.

	@example
	@group
	# 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
	@end group
	@end example

	We can add this to our partial topology from above, which now looks
	like:
	@example
	@group
	--------------------- 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
	@end group
	@end example

	@subsubsection Summary LSAs

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

	@anchor{OSPF Flooding}
	@subsection OSPF Flooding

	@anchor{OSPF Areas}
	@subsection OSPF Areas