summaryrefslogtreecommitdiffstats
path: root/docs/developer/corefeatures/fib/graphs.rst
diff options
context:
space:
mode:
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.