docs: Update FIB documentation

Type: docs

Signed-off-by: Neale Ranns <nranns@cisco.com>
Change-Id: I3dfde4520a48c945ca9707accabbe1735c1a8799

1 files changed, 68 insertions, 0 deletions

diff --git a/docs/gettingstarted/developers/fib20/marknsweep.rst b/docs/gettingstarted/developers/fib20/marknsweep.rst
new file mode 100644
index 00000000000..e9e38a33f3a
--- /dev/null
+++ b/docs/gettingstarted/developers/fib20/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.
+