docs/developer/corefeatures/fib/graphs.rst

   1 .. _graphs:
   2
   3 Graphs
   4 ^^^^^^
   5
   6 The FIB is essentially a collection of related graphs. Terminology from graph theory
   7 is often used in the sections that follow. From Wikipedia:
   8
   9 *... a graph is a representation of a set of objects where some pairs of objects are
  10 connected by links. The interconnected objects are represented by mathematical
  11 abstractions called vertices (also called nodes or points), and the links that
  12 connect some pairs of vertices are called edges (also called arcs or lines) ...
  13 edges may be directed or undirected.*
  14
  15 In a directed graph the edges can only be traversed in one direction - from child to
  16 parent. The names are chosen to represent the many to one relationship. A child has
  17 one parent, but a parent many children.  In undirected graphs the edge traversal
  18 can be in either direction, but in FIB the parent child nomenclature remains to
  19 represent the many to one relationship. Children of the same parent are termed
  20 siblings. When the traversal is from child to parent it is considered to be a
  21 forward traversal, or walk, and from parent to the many children a back walk.
  22 Forward walks are cheap since they start from the many and move toward the few.
  23 Back walks are expensive as the start from the few and visit the many.
  24
  25 The many to one relationship between child and parent means that the lifetime of a
  26 parent object must extend to the lifetime of its children. If the control plane
  27 removes a parent object before its children, then the parent must remain, in an
  28 **incomplete** state, until the children are themselves removed. Likewise if a child
  29 is created before its parent, the parent is created in an *incomplete* state. These
  30 incomplete objects are needed to maintain the graph dependencies. Without them when
  31 the parent is added finding the affected children would require a search through many
  32 databases for those children. To extend the lifetime of parents all children thereof
  33 hold a **lock** on the parent. This is a simple reference count. Children then follow
  34 the add-or-lock/unlock semantics for finding a parent, as opposed to a malloc/free.