docs: better docs, mv doxygen to sphinx

This patch refactors the VPP sphinx docs
in order to make it easier to consume
for external readers as well as VPP developers.

It also makes sphinx the single source
of documentation, which simplifies maintenance
and operation.

Most important updates are:

- reformat the existing documentation as rst
- split RELEASE.md and move it into separate rst files
- remove section 'events'
- remove section 'archive'
- remove section 'related projects'
- remove section 'feature by release'
- remove section 'Various links'
- make (Configuration reference, CLI docs,
  developer docs) top level items in the list
- move 'Use Cases' as part of 'About VPP'
- move 'Troubleshooting' as part of 'Getting Started'
- move test framework docs into 'Developer Documentation'
- add a 'Contributing' section for gerrit,
  docs and other contributer related infos
- deprecate doxygen and test-docs targets
- redirect the "make doxygen" target to "make docs"

Type: refactor

Change-Id: I552a5645d5b7964d547f99b1336e2ac24e7c209f
Signed-off-by: Nathan Skrzypczak <nathan.skrzypczak@gmail.com>
Signed-off-by: Andrew Yourtchenko <ayourtch@gmail.com>

1 files changed, 68 insertions, 0 deletions

diff --git a/docs/developer/corefeatures/fib/marknsweep.rst b/docs/developer/corefeatures/fib/marknsweep.rst
new file mode 100644
index 00000000000..e9e38a33f3a
--- /dev/null
+++ b/docs/developer/corefeatures/fib/marknsweep.rst
@@ -0,0 +1,68 @@
+.. _marknsweep:
+
+Mark and Sweep
+--------------
+
+The mark and sweep procedures, in FIB and in other subsystems, are
+built for the purpose of recovering from a control plane crash.
+
+In routing if the control plane (CP) crashes, when it restarts, the network
+topology may have changed. This means that some of the routes that
+were programmed in the FIB may no longer be needed, and perhaps some
+new ones are. If the CP were simply to insert all the new routes it
+learned after it restarts, then FIB could be left with old routes that
+never get removed, this would be bigly bad.
+
+At a high level the requirement is to delete routes from the old set
+that are not present in the new set; 'delete the diff' as it might
+be colloquially known.
+
+How should the control plane determine the old set? It could
+conceivably read back the FIB from VPP. But this presents two
+problems, firstly, it could be a large set of routes, numbering in the
+millions, this is not an efficient mechanism and not one one wants to
+perform at a point when the router is trying to converge
+ASAP. Secondly it represents a 'source of truth' inversion. The
+routing plane is the source of truth, not forwarding. Routing should
+not receive its 'input' from the layers below. Thirdly, on a practical
+note, the reading of VPP data structures to glean this sort of
+accurate information, would only happen in this scenario, i.e. it's
+not well tested and therefore not particularly reliable (see point 2).
+
+Enter 'mark and sweep' or m-n-s (not to be confused with the retail
+giant) as it's affectionately known.
+
+The Mark and Sweep algorithm proceeds in three steps:
+
+- Step 1; the CP declares to VPP that it wants to begin the process
+  (i.e. it has just restarted). At this point VPP will iterate through
+  all the objects that the CP owns and 'mark' then as being
+  stale. This process effectively declares a new 'epoch', a barrier in
+  time that separates the old objects from the new.
+- Step 2; The CP downloads all of its new objects. If one of these new
+  CP objects matches (has the same key as) an existing object, then
+  the CP add is considered an update, and the object's stale state is
+  removed.
+- Step 3: The CP declares it has 'converged'; it has no more updates
+  to give (at this time). VPP will then again iterate through all the
+  CP's objects and remove those that do not belong to the new epoch,
+  i.e. those that are still marked stale.
+
+After step 3, the CP and VPP databases are in sync.
+
+The cost of the process was to download all the new routes again. This
+is a highly-tuned and well-tested scenario.
+
+In VPP we use the synonym 'replace' to describe the mark-n-sweep
+action in the API. We use this term because it refers to the goals of
+the algorithm at a high level - the CP wants to replace the old DB
+with a new one - but it does not specify the algorithm by which that
+is achieved. One could equally perform this task by constructing a
+brand new DB in VPP, and then swapping them when the CP
+converges. Other subsystems may employ that approach, but FIB does
+not. Updates are typically faster than adds, since the update is
+likely a no-op, whereas a separate add would require the memory
+allocator, which is the long pole in FIB additions. Additionally, it requires
+twice the memory for a moment in time, which could be prohibitive when
+the FIB is large.
+