docs/gettingstarted/developers/fib20/graphwalks.rst - fdio/vpp - Gitiles

 .. _graphwalks:

 Graph Walks
 ^^^^^^^^^^^^

 All FIB object types are allocated from a VPP memory pool [#f13]_. The objects are thus
 susceptible to memory re-allocation, therefore the use of a bare "C" pointer to refer
 to a child or parent is not possible. Instead there is the concept of a *fib_node_ptr_t*
 which is a tuple of type,index. The type indicates what type of object it is
 (and hence which pool to use) and the index is the index in that pool. This allows
 for the safe retrieval of any object type.

 When a child resolves via a parent it does so knowing the type of that parent. The
 child to parent relationship is thus fully known to the child, and hence a forward
 walk of the graph (from child to parent) is trivial. However, a parent does not choose
 its children, it does not even choose the type. All object types that form part of the
 FIB control plane graph all inherit from a single base class14; *fib_node_t*. A *fib_node_t*
 identifies the object's index and its associated virtual function table provides the
 parent a mechanism to visit that object during the walk. The reason for a back-walk
 is to inform all children that the state of the parent has changed in some way, and
 that the child may itself need to update.

 To support the many to one, child to parent, relationship a parent must maintain a
 list of its children. The requirements of this list are;

 - O(1) insertion and delete time. Several child-parent relationships are made/broken during route addition/deletion.
 - Ordering. High priority children are at the front, low priority at the back (see section Fast Convergence)
 - Insertion at arbitrary locations.

 To realise these requirements the child-list is a doubly linked-list, where each element
 contains a *fib_node_ptr_t*. The VPP pool memory model applies to the list elements, so
 they are also identified by an index. When a child is added to a list it is returned the
 index of the element. Using this index the element can be removed in constant time.
 The list supports 'push-front' and 'push-back' semantics for ordering. To walk the children
 of a parent is then to iterate of this list.

 A back-walk of the graph is a depth first search where all children in all levels of the
 hierarchy are visited. Such walks can therefore encounter all object instances in the
 FIB control plane graph, numbering in the millions. A FIB control-plane graph is cyclic
 in the presence of a recursion loop, so the walk implementation has mechanisms to detect
 this and exit early.

 A back-walk can be either synchronous or asynchronous. A synchronous walk will visit the
 entire section of the graph before control is returned to the caller, an asynchronous
 walk will queue the walk to a background process, to run at a later time, and immediately
 return to the caller. To implement asynchronous walks a *fib_walk_t* object it added to
 the front of the parent's child list. As children are visited the *fib_walk_t* object
 advances through the list. Since it is inserted in the list, when the walk suspends
 and resumes, it can continue at the correct location. It is also safe with respect to
 the deletion of children from the list. New children are added to the head of the list,
 and so will not encounter the walk, but since they are new, they already have the up to
 date state of the parent.

 A VLIB process 'fib-walk' runs to perform the asynchronous walks. VLIB has no priority
 scheduling between respective processes, so the fib-walk process does work in small
 increments so it does not block the main route download process. Since the main download
 process effectively has priority numerous asynchronous back-walks can be started on the
 same parent instance before the fib-walk process can run. FIB is a 'final state' application.
 If a parent changes n times, it is not necessary for the children to also update n
 times, instead it is only necessary that this child updates to the latest, or final,
 state. Consequently when multiple walks on a parent (and hence potential updates to a
 child) are queued, these walks can be merged into a single walk.

 Choosing between a synchronous and an asynchronous walk is therefore a trade-off between
 time it takes to propagate a change in the parent to all of its children, versus the
 time it takes to act on a single route update. For example, if a route update where to
 affect millions of child recursive routes, then the rate at which such updates could be
 processed would be dependent on the number of child recursive route which would not be
 good. At the time of writing FIB2.0 uses synchronous walk in all locations except when
 walking the children of a path-list, and it has more than 32 [#f15]_ children. This avoids the
 case mentioned above.

 .. rubric:: Footnotes:

 .. [#f13] Fast memory allocation is crucial to fast route update times.
 .. [#f14] VPP may be written in C and not C++ but inheritance is still possible.
 .. [#f15] The value is arbitrary and yet to be tuned.
	.. _graphwalks:

	Graph Walks
	^^^^^^^^^^^^

	All FIB object types are allocated from a VPP memory pool [#f13]_. The objects are thus
	susceptible to memory re-allocation, therefore the use of a bare "C" pointer to refer
	to a child or parent is not possible. Instead there is the concept of a fib_node_ptr_t
	which is a tuple of type,index. The type indicates what type of object it is
	(and hence which pool to use) and the index is the index in that pool. This allows
	for the safe retrieval of any object type.

	When a child resolves via a parent it does so knowing the type of that parent. The
	child to parent relationship is thus fully known to the child, and hence a forward
	walk of the graph (from child to parent) is trivial. However, a parent does not choose
	its children, it does not even choose the type. All object types that form part of the
	FIB control plane graph all inherit from a single base class14; fib_node_t. A fib_node_t
	identifies the object's index and its associated virtual function table provides the
	parent a mechanism to visit that object during the walk. The reason for a back-walk
	is to inform all children that the state of the parent has changed in some way, and
	that the child may itself need to update.

	To support the many to one, child to parent, relationship a parent must maintain a
	list of its children. The requirements of this list are;

	- O(1) insertion and delete time. Several child-parent relationships are made/broken during route addition/deletion.
	- Ordering. High priority children are at the front, low priority at the back (see section Fast Convergence)
	- Insertion at arbitrary locations.

	To realise these requirements the child-list is a doubly linked-list, where each element
	contains a fib_node_ptr_t. The VPP pool memory model applies to the list elements, so
	they are also identified by an index. When a child is added to a list it is returned the
	index of the element. Using this index the element can be removed in constant time.
	The list supports 'push-front' and 'push-back' semantics for ordering. To walk the children
	of a parent is then to iterate of this list.

	A back-walk of the graph is a depth first search where all children in all levels of the
	hierarchy are visited. Such walks can therefore encounter all object instances in the
	FIB control plane graph, numbering in the millions. A FIB control-plane graph is cyclic
	in the presence of a recursion loop, so the walk implementation has mechanisms to detect
	this and exit early.

	A back-walk can be either synchronous or asynchronous. A synchronous walk will visit the
	entire section of the graph before control is returned to the caller, an asynchronous
	walk will queue the walk to a background process, to run at a later time, and immediately
	return to the caller. To implement asynchronous walks a fib_walk_t object it added to
	the front of the parent's child list. As children are visited the fib_walk_t object
	advances through the list. Since it is inserted in the list, when the walk suspends
	and resumes, it can continue at the correct location. It is also safe with respect to
	the deletion of children from the list. New children are added to the head of the list,
	and so will not encounter the walk, but since they are new, they already have the up to
	date state of the parent.

	A VLIB process 'fib-walk' runs to perform the asynchronous walks. VLIB has no priority
	scheduling between respective processes, so the fib-walk process does work in small
	increments so it does not block the main route download process. Since the main download
	process effectively has priority numerous asynchronous back-walks can be started on the
	same parent instance before the fib-walk process can run. FIB is a 'final state' application.
	If a parent changes n times, it is not necessary for the children to also update n
	times, instead it is only necessary that this child updates to the latest, or final,
	state. Consequently when multiple walks on a parent (and hence potential updates to a
	child) are queued, these walks can be merged into a single walk.

	Choosing between a synchronous and an asynchronous walk is therefore a trade-off between
	time it takes to propagate a change in the parent to all of its children, versus the
	time it takes to act on a single route update. For example, if a route update where to
	affect millions of child recursive routes, then the rate at which such updates could be
	processed would be dependent on the number of child recursive route which would not be
	good. At the time of writing FIB2.0 uses synchronous walk in all locations except when
	walking the children of a path-list, and it has more than 32 [#f15]_ children. This avoids the
	case mentioned above.

	.. rubric:: Footnotes:

	.. [#f13] Fast memory allocation is crucial to fast route update times.
	.. [#f14] VPP may be written in C and not C++ but inheritance is still possible.
	.. [#f15] The value is arbitrary and yet to be tuned.