| jdenisco | 0923a23 | 2018-08-29 13:19:43 -0400 | [diff] [blame] | 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 completed 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 be 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. |