diff options
Diffstat (limited to 'docs/developer/corefeatures/fib/graphs.rst')
| -rw-r--r-- | docs/developer/corefeatures/fib/graphs.rst | 34 |
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. |