| .. _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. |