Module snowcap::strategies[][src]

Expand description


This module contains the source codes for different strategies for finding a valid update sequence. It contains the trait definition for Strategy, which Snowcap will use.

Modifier Dependency Properties

  • Statically Determinable: If a dependency can be identified using domain-specific knowledge, without simulating it, it is called statically determinable.

    Example: A router has a single BGP session before reconfiguration, and a singe, but different session after reconfiguration, the new session must be added before the old one can be removed.

  • Immediate Effect: If the order of the dependency is incorrect, and the problem is visible immediately after the wrong modifier is applied, then it has an immediate effect. This property must hold for all possible orderings, in order for a dependency to have an immediate effect.

    Example: ChainGadget has an immediate effect, since every wrong modifier will immediately cause a forwarding loop. The DifficultGadget has no immediate effect, since the problem only arises when a specific modifier is applied.

  • Sparse Solution: A modifier dependency has sparse solutions if the number of correct solutions is very small compared to the total possible orderings of this dependency. If there exists one or two valid sequences, we call this dependency to have a sparse solution.

    Example: ChainGadget has a sparse solution, since only a single ordering is valid. The BipartiteGadget with N >> 2 has no sparse solution, since the only requirement is that one single modifier is applied first.

  • State Specific: If a modifier dependency is only problematic at a specific state of the network, it is called state specific. It might only be a problem when it is applied at the beginning of the sequence, or at the end, or only in between.

    Example: StateSpecificChainGadget has a sparse, state specific dependency with immediate effect. The immediate effect is only the case in this special state, but neither in the initial and the final state of the network. In the initial and final configuration, the dependency is not actually there.

    Note: This can also be modelled by extending the modifier dependency to include other modifiers.


  • One Strategy To Rule Them All (StrategyTRTA): This strategy combines the best of both the simple TreeStrategy, and the more complex, DepGroupsStrategy. It does this by exploring the search space similar to the tree strategy. But as soon as we would need to backtrace, we try to find a single dependency. If it succeeds, we repeat the tree traversal using the new dependency. Using this approach, we only search for the dependencies, which are not solvable by using the naive Tree strategy.

    Type Arguments: None, this algorithm is as good as it gets (using this approach)

  • PermutationStrategy: This is the simplest strategy, naively checking every single permutation one after the other. It does benefit from dependencies, which have an immediate effect (only if the permutator makes use of the feedback mechanism, when the function fail_pos is reimplemented), and has problems if the problem has a sparse solution. This strategy is an ExhaustiveStrategy.

    Type Arguments: The first type argument P is the chosen Permutator, with an ordering of your choice.

  • TreeStrategy: This is a strategy trying out all possible permutations, in a similar fashion to the LexicographicPermutator. However, as soon as a problem was found for a given ordering up to a specific modifier, it does not need to check again all permutations starting with the same modifiers in the same ordering. Thus, this strategy benefits from from dependencies with an immediate effect, and is able to solve the ChainGadget in O(n^3) time. This strategy is an ExhaustiveStrategy.

    Type Arguments: The first type argument O represents the chosen ModifierOrdering, which is used to order the modifiers before the tree algorithm starts.

  • PushBackTreeStrategy: This is a strategy very similar to the TreeStrategy. However, once a modifier is causing an error, it is pushed back in the queue of remaining modifiers, and another is tried. As the TreeStrategy, the PushBackTreeStrategy benefits from dependencies with an immediate effect, and is an ExhaustiveStrategy. Additionally, the PushBackTreeStrategy implements GroupStrategy.

    Type Arguments: The first type argument O represents the chosen ModifierOrdering, which is used to order the modifiers before the tree algorithm starts.

  • DepGroupsStrategy: This is a sophisticated algoirthm. It builds a set of groups of dependencies, which are solvable by their own. Then, it tries to use these to either build larger dependency groups, or find a solution to the entire problem. This strategy benefits from dependencies with an immediate effect, and having a sparse solution. However, this strategy cannot capture state specific dependencies, and may build larger dependencies than are actually needed. By adding more groups, the strategy scales with O(g^4), but increasing each group size (with no immediate effect) scales with O(n!). This strategy is not exhaustive.

    Type Arguments: The first type argument is a GroupStrategy, used to solve a smaller problem with the group information learned before. The last type argument P is a Permutator<usize>, used to generate all permutations of the groups. As soon as a new group is formed, the permutator is reset.

  • NaiveRandomStrategy: This strategy just exists for evaluation purpose. It simply shuffles the sequence and checks if this sequence is correct.

  • NaiveRandomIBRStrategy: This strategy is similar to the random strategy, but it always schedules insert before modify before remove commands.


The Dependency Groups Builder Strategy

The Random Strategy with Insert before Remove

The Naive Random Strategy

The Permutation Strategy

The Push-Back Tree Strategy

One Strategy To Rule Them All

The Tree Strategy


Marking to tell that this strategy is exhaustive.

Trait for a strategy being able to solve groups of modifiers

Infterface for all strategies