summaryrefslogtreecommitdiffstats
path: root/docs/gettingstarted/developers/fib20/graphs.rst
diff options
context:
space:
mode:
authorjdenisco <jdenisco@cisco.com>2018-08-29 13:19:43 -0400
committerNeale Ranns <nranns@cisco.com>2018-08-30 15:14:49 +0000
commit0923a2376fcdc07fc298b9422233f4a5c1777e7d (patch)
tree7164f6f7083d48c7cd47abdbea7377d4f323dc26 /docs/gettingstarted/developers/fib20/graphs.rst
parent5e2c54d02906a7b4787a1f41b59baf97c3a4a840 (diff)
docs: FIB 2.0 start
Change-Id: I87cd2eae133c9f5b9f7764a0f7a41bcc28523e4c Signed-off-by: jdenisco <jdenisco@cisco.com>
Diffstat (limited to 'docs/gettingstarted/developers/fib20/graphs.rst')
-rw-r--r--docs/gettingstarted/developers/fib20/graphs.rst34
1 files changed, 34 insertions, 0 deletions
diff --git a/docs/gettingstarted/developers/fib20/graphs.rst b/docs/gettingstarted/developers/fib20/graphs.rst
new file mode 100644
index 00000000000..ec4c6760062
--- /dev/null
+++ b/docs/gettingstarted/developers/fib20/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 completed 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 be 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.