summaryrefslogtreecommitdiffstats
path: root/docs/developer/corefeatures/fib/graphs.rst
diff options
context:
space:
mode:
authorNathan Skrzypczak <nathan.skrzypczak@gmail.com>2021-08-19 11:38:06 +0200
committerDave Wallace <dwallacelf@gmail.com>2021-10-13 23:22:32 +0000
commit9ad39c026c8a3c945a7003c4aa4f5cb1d4c80160 (patch)
tree3cca19635417e28ae381d67ae31c75df2925032d /docs/developer/corefeatures/fib/graphs.rst
parentf47122e07e1ecd0151902a3cabe46c60a99bee8e (diff)
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>
Diffstat (limited to 'docs/developer/corefeatures/fib/graphs.rst')
-rw-r--r--docs/developer/corefeatures/fib/graphs.rst34
1 files changed, 34 insertions, 0 deletions
diff --git a/docs/developer/corefeatures/fib/graphs.rst b/docs/developer/corefeatures/fib/graphs.rst
new file mode 100644
index 00000000000..aec0e4b0135
--- /dev/null
+++ b/docs/developer/corefeatures/fib/graphs.rst
@@ -0,0 +1,34 @@
+.. _graphs:
+
+Graphs
+^^^^^^
+
+The FIB is essentially a collection of related graphs. Terminology from graph theory
+is often used in the sections that follow. From Wikipedia:
+
+*... a graph is a representation of a set of objects where some pairs of objects are
+connected by links. The interconnected objects are represented by mathematical
+abstractions called vertices (also called nodes or points), and the links that
+connect some pairs of vertices are called edges (also called arcs or lines) ...
+edges may be directed or undirected.*
+
+In a directed graph the edges can only be traversed in one direction - from child to
+parent. The names are chosen to represent the many to one relationship. A child has
+one parent, but a parent many children. In undirected graphs the edge traversal
+can be in either direction, but in FIB the parent child nomenclature remains to
+represent the many to one relationship. Children of the same parent are termed
+siblings. When the traversal is from child to parent it is considered to be a
+forward traversal, or walk, and from parent to the many children a back walk.
+Forward walks are cheap since they start from the many and move toward the few.
+Back walks are expensive as the start from the few and visit the many.
+
+The many to one relationship between child and parent means that the lifetime of a
+parent object must extend to the lifetime of its children. If the control plane
+removes a parent object before its children, then the parent must remain, in an
+**incomplete** state, until the children are themselves removed. Likewise if a child
+is created before its parent, the parent is created in an *incomplete* state. These
+incomplete objects are needed to maintain the graph dependencies. Without them when
+the parent is added finding the affected children would require a search through many
+databases for those children. To extend the lifetime of parents all children thereof
+hold a **lock** on the parent. This is a simple reference count. Children then follow
+the add-or-lock/unlock semantics for finding a parent, as opposed to a malloc/free.