diff options
Diffstat (limited to 'docs/gettingstarted/developers/fib20/marknsweep.rst')
| -rw-r--r-- | docs/gettingstarted/developers/fib20/marknsweep.rst | 68 |
1 files changed, 0 insertions, 68 deletions
diff --git a/docs/gettingstarted/developers/fib20/marknsweep.rst b/docs/gettingstarted/developers/fib20/marknsweep.rst deleted file mode 100644 index e9e38a33f3a..00000000000 --- a/docs/gettingstarted/developers/fib20/marknsweep.rst +++ /dev/null @@ -1,68 +0,0 @@ -.. _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. - |