doc: Add 'OSPF Fundamentals' section to OSPF docs

* ospf_fundamentals.texi: New section explaining the fundamentals of OSPF
  for system admins, to help them debug their networks.
* {Makefile.am,ospfd.texi}: include and build previous

Conflicts:
	doc/Makefile.am

(cherry picked from commit e56aab94a615a2b676473fbd09145b444a348029)

3 files changed, 586 insertions, 1 deletions

diff --git a/doc/Makefile.am b/doc/Makefile.am
index 18f7108ee..415dfaf6f 100644
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -50,7 +50,7 @@ quagga_TEXINFOS = appendix.texi basic.texi bgpd.texi filter.texi \
 	install.texi ipv6.texi kernel.texi main.texi ospf6d.texi ospfd.texi \
 	overview.texi protocol.texi ripd.texi ripngd.texi routemap.texi \
 	snmp.texi vtysh.texi routeserver.texi defines.texi $(figures_png) \
-	snmptrap.texi $(figures_txt)
+	snmptrap.texi ospf_fundamentals.texi $(figures_txt)
 
 .png.eps:
 	$(PNGTOEPS) $< "$@"
diff --git a/doc/ospf_fundamentals.texi b/doc/ospf_fundamentals.texi
new file mode 100644
index 000000000..82218e601
--- /dev/null
+++ b/doc/ospf_fundamentals.texi
@@ -0,0 +1,582 @@
+@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
diff --git a/doc/ospfd.texi b/doc/ospfd.texi
index 5b1b2acb2..45d1ad7cd 100644
--- a/doc/ospfd.texi
+++ b/doc/ospfd.texi
@@ -11,6 +11,7 @@ convergence times.  OSPF is widely used in large networks such as
 networks.
 
 @menu
+* OSPF Fundamentals::
 * Configuring ospfd::           
 * OSPF router::                 
 * OSPF area::                   
@@ -21,6 +22,8 @@ networks.
 * OSPF Configuration Examples::
 @end menu
 
+@include ospf_fundamentals.texi
+
 @node Configuring ospfd
 @section Configuring ospfd