Crate snowcap

Snowcap: Synthesizing NetwOrk-Wide ConfigurAtion uPdates

This is a library for comparing two network configurations and generating a sequence of small configuration updates, which can be applied without producing anomalies.

This library was created during the Master Thesis: "Synthesizing Network-Wide Configuration Updates" by Tibor Schneider, supervised by Laurent Vanbever and Rüdiker Birkener.

Problem Statement

Given

• an initial network configuration $A$ and a target configuration $B$,
• a set of hard-constraints, which are satisfied by both configuration $A$ and $B$
• a set of soft-constraints

find an ordered set of configuration changes, such that the hard-constraints are satisfied throughout the entire reconfiguration process, and the soft-constraints are optimized.

Structure

This library is structured in the following way:

• NetSim: Network Simulator used in this project. See the main structure Network.

• Strategies: Collection of different strategies, which Snowcap shold use. Strategies can be described using different Permutators, ModifierOrderings, or even other Strategies. Strategies can either be exhaustive (when they implement ExhaustiveStrategy), or non-exhaustive (when they don't implemeht that trait). Also, strategies can implement GroupStrategy, which means that the strategy can use group information which was extracted previously.

• Optimizers: Collection of different optimization strategies for synthesizing network updates, while always requiring the hard policies to hold, and the cost of the soft policies to be minimized. Optimizers are very similar to strategies. They can also implement ExhaustiveStrategy, to tell that a given optimizer will check every possible combination.

• Permutators: Collection of different ways to iterate over all possible permutations of reconfiguration orderings, or over all possible permutations of any vector. Usually, they take a type argument ModifierOrdering, to configure how they are ordered. All Permutators return every possible permutation exactly once, except in the following case: Some permutators have the possibility of getting feedback from the strategy. The idea is that permutations don't need to be checked if an earlier permutation with the same beginning already failed at a position where both permutations are still the same (they only differ after the failed position). In this case, the permutator may skip all these permutations, resulting in a reduced number of permutations to try.

• ModifierOrdering: Collection of different orerings for modifiers. Some of these orderings are CompleteOrderings, which means that it only returns Ordering::Equal for modifiers which are actually equal. This ordering is used for several strategies, and permutators. Note, that there also exist ModifierOrderings which do not only apply to ConfigModifiers, but also to any other type which can be ordered.

• HardPolicy: Collection of Conditions, which can be combined with a LTL Formula to generate a Hard Policy for checking the policies while exploring the problem space.

• SoftPolicy: Collection of different soft policies which allows the synthetisized configuration update to minimize a cost function.

• ExampleNetworks: Collection of prepared networks and reconfiguration scenarios to test different strategies. Some of these networks can be scaled to arbitrary size.

• TopologyZoo: Functions to generate a network from a topology downloaded from TopologyZoo (as GML files). The configuration can be generated randomly.

Features

• count-states: If this feature is enabled, then strategies and optimizers will contain the method num_states, to get the number of network states that have been explored.

Usage

To use this module, you need to do first prepare your network to include all routers, the initial configuration, and you need to make sure that all routes are advertised by some routers. Then, you need to prepare the final configuration. Next, express your hard policies as constraints, and choose your strategy. Finally, call the synthesize method on the strategy.

use snowcap::hard_policies::*;
use snowcap::synthesize;
use snowcap::Error;
use snowcap::netsim::Network;
use snowcap::netsim::config::Config;

fn main() -> Result<(), Error> {
    // prepare the network
    // let net = ...
    // let initial_config = ...
    // let final_config = ...

    // prepare the policies
    // let hard_policy = ...

    // synthesize the reconfiguration
    let sequence = synthesize(net, initial_config, final_config, hard_policy, None)?;

    // Do something with the result
    println!("{:#?}", sequence);

    Ok(())
}

Modules

example_networks	Networks for testing
hard_policies	Hard Policies
modifier_ordering	ModifierOrdering
netsim	NetSim
optimizers	Optimizer
permutators	Permutators
soft_policies	Soft Policies
strategies	Strategies
topology_zoo	Import functions for importing topology zoo graphml files

Structs

Stopper

Stopper, to check when to stop, or to send the stop command

Enums

Error

Main error type

Functions

optimize	Synthesize Configuration Updates while optimizing soft policies
synthesize	Synthesize Configuration Updates
synthesize_parallel	Synthesize Configuration Updates using multiple parallel threads