diff options
Diffstat (limited to 'docs/gettingstarted/developers/fib20/graphs.rst')
| -rw-r--r-- | docs/gettingstarted/developers/fib20/graphs.rst | 34 |
1 files changed, 0 insertions, 34 deletions
diff --git a/docs/gettingstarted/developers/fib20/graphs.rst b/docs/gettingstarted/developers/fib20/graphs.rst deleted file mode 100644 index aec0e4b0135..00000000000 --- a/docs/gettingstarted/developers/fib20/graphs.rst +++ /dev/null @@ -1,34 +0,0 @@ -.. _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. |