Struct snowcap::netsim::Network[][src]

pub struct Network { /* fields omitted */ }
Expand description

Network struct

The struct contains all information about the underlying physical network (Links), a manages all (both internal and external) routers, and handles all events between them. Configuration is applied on the network itself, treated as network-wide configuration.

Undo Funcitonality

The Undo funcitonality is implemented by two interacting parts. First, the network keeps track of all past events (in the event_history). Second, every network device keeps a local stack, in which all information is present to undo an event.

The network is responsible for calling undo on the correct network device, since the network device does not check if the event matches the one which caused the modifications in the first place. This is trivial for all BGP messages exchanged, but not for configuration modifications and other user interactions with the network. For changes in external advertised routes, we need not to do something, except changing the external routers. For the configuraiton changes, we reverse the modifier (delete becomes insert, and modify swaps the old and the new expression), and call the same function as appyling a normal modifier, but set the undo flag to true. Then, instead of updating the bgp tables on the routers, the function will call undo_last_event on the same router as the action before has updated the BGP tables.

Along with each event, the network stores the parent event ID in the event history. This allows us to recreate the exact event queue when undoing a single event. When we undo an event, we check the queue if any of them have as parent ID the ID of the event that was restored. If so, they will be removed. When undoing an entire action (like applying a config modification), we do not keep track of the queue, but just delete it in the end, since we require the queue to be empty when applying a new modifier.

Transient State

NOTE This part of the code is currently commented out due to legacy hard policy use. Additionally, we have figured out that for some networks, this approach may lead to an infinite loop of messages. This approach does not work, and therefore, it should not be used.

By calling apply_modifier_check_constraint, we explore the entire space of event orderings. This is done by checking if two events do commute or not. The exact algorithm works as follows:

  1. First, we apply the modifier as normal, and check that it does converge. Then, we compute the set of prefixes, which were affected by the modification. We then undo all events as before, and reapply the modifier without executing the queue.

  2. The following sequence is then repeated for each prefix that affected by the modification:

    1. We create a stack that keeps track of all event reordering at every step, that still needs to be explored.
    2. Then, we continue as follows:
      1. If the current branch is not yet entered, we take the next event from the queue, and build a set of non-commuting events from the events that are still inside the queue (see Commutativity). If the event does not correspond to the chosen prefix, we ignore all non-commuting events and use an empty set. Then, We push this set onto the stack.
      2. If the current branch is already entered, take out one event form the stack and continue with this event.
    3. Next, we execute the the chosen event (from 2.2.1 or 2.2.2). If the event changed the forwarding state of the network, we check the hard hard_policy (but only for the chosen prefix). If they fail, we return the from the procedure with an error.
    4. Finally, there are three different ways in which we continue:
      1. If the queue is not empty, we continue with step 2.2.1.
      2. If the queue is empty, and there are no branches left to explore, we call this prefix ok and continue with the next prefix on step 2.
      3. If the queue is empty, and there are still branches left to explore, we undo all events on the network until we reach the most recent point where there are still branches to explore. At the same time, we pop the stack to keep it consistent with the network state. Then, continue with step 2.2.2.

Notes and Details

  • TCP Streams: BGP is a Distance-Vector protocol that exchanges messages via TCP. This means, that two BGP routers with an active BGP session also have an active TCP session open. Since TCP is a reliable transport protocol, we can be sure that all BGP messages are received by the destination router, and that the messages of one BGP session are always received in the same order as they are sent. This means, that two BGP messages that both have the same source and destination cannot be reordere (at least if they are caused at different time instances). Hence, in step 2.2.1, two things need to happen:

    1. When taking the next event from the queue, we check if the TCP transmission order is validated. If so, then choose the event which must be handled first by the destination router.
    2. When preparing the set of events that may not commute with the cosen one, we need also to consider the event ordering. We are not allowed to add events to the set if it does not comply with the TCP order. This is achieved by checking every event if it must be freezed.

    However, something is very important: while computing the non-commutive events for event $e_A$, and when event $e_B$ is freezed due to TCP ordering with event $e_C$, then events $e_A$ and $C$ do not commute, since applying $e_C$ might cause $e_B$ to be applied, which in terms might commute with $e_A$.

  • Decoupling Prefixes In step 2 of the algorithm, we iterate over all prefixes that are updated during convergence. First, we are allowed to do this, because all events talking about two different prefixes do commute. Also, it reduces the complexity of the algorithm dramatically. Assume events $e_{11}$, $e_{12}$ and $e_{13}$ are for prefix 1 and all are not commutative, and $e_{21}$, $e_{22}$, and $e_{23}$ are for prefix 2, which also do not commute. When not decoupling the prefixes, we need to check $3! \cdot 3! = 36$ orderings. However, when decoupling the two prefixes, we only need to check $3! + 3! = 12$ orderings.

Implementations

Generate an empty Network

Add a new router to the topology. Note, that the AS id is always set to AsId(65001). This function returns the ID of the router, which can be used to reference it while confiugring the network.

Add a new external router to the topology. An external router does not process any BGP messages, it just advertises routes from outside of the network. This function returns the ID of the router, which can be used to reference it while configuring the network.

This function creates an link in the network The link will have infinite weight for both directions. The network needs to be configured such that routers can use the link, since a link with infinte weight is treated as not connected.

let mut net = Network::new();
let r1 = net.add_router("r1");
let r2 = net.add_router("r2");
net.add_link(r1, r2);
net.apply_modifier(&ConfigModifier::Insert(ConfigExpr::IgpLinkWeight {
    source: r1,
    target: r2,
    weight: 5.0,
}))?;
net.apply_modifier(&ConfigModifier::Insert(ConfigExpr::IgpLinkWeight {
    source: r2,
    target: r1,
    weight: 4.0,
}))?;

Set the provided network-wide configuration. The network first computes the patch from the current configuration to the next one, and applies the patch. If the patch cannot be applied, then an error is returned. Note, that this function may apply a large number of modifications in an order which cannot be determined beforehand. If the process fails, then the network is in an undefined state.

Apply a configuration patch. The modifications of the patch are applied to the network in the order in which they appear in patch.modifiers. After each modifier is applied, the network will process all necessary messages to let the network converge. The process may fail if the modifiers cannot be applied to the current config, or if there was a problem while applying a modifier and letting the network converge. If the process fails, the network is in an undefined state.

Apply a single configuration modification. The modification must be applicable to the current configuration. All messages are exchanged. The process fails, then the network is in an undefined state, and it should be rebuilt.

Transient condition verification

This method is only available if the "transient-violation" feature is enabled!

This function applies the modifier n_iter times, each time in a different ordering. At every intermediate state, it checks the condition, which must hold at each and every state. Notice, that for the condition, it only allows Condition::Reachable and Condition::NotReachable. This function then returns the number of convergence series, in which every condition is satisfied at all intermediate states of this convergence process.

It does this by shuffling the queue each ane very time before performing the next step. If there exists no message to be reordered, this function returns NetworkError::NoEventsToReorder.

Advertise an external route and let the network converge, The source must be a RouterId of an ExternalRouter. If not, an error is returned. When advertising a route, all eBGP neighbors will receive an update with the new route. If a neighbor is added later (after advertise_external_route is called), then this new neighbor will receive an update as well.

Retract an external route and let the network converge. The source must be a RouterId of an ExternalRouter. All current eBGP neighbors will receive a withdraw message.

Undo the last action of the network, causing the network to be in the earlier state. If there was no action to be undone, then Ok(false) is returned. If something has changed, then Ok(true) is returned.

The following are considered actions:

  • apply_modifier
  • advertise_external_route
  • retract_external_route

After undo, the event queue will be empty.

Warning

Once the network is cloned, the copy will not contain the information to undo!

Compute and return the current forwarding state.

Returns a reference to the network topology (PetGraph struct)

Returns the number of devices in the topology

Returns a reference to the network device.

Returns a list of all internal router IDs in the network

Returns a list of all external router IDs in the network

Get the RouterID with the given name. If multiple routers have the same name, then the first occurence of this name is returned. If the name was not found, an error is returned.

Returns a hashset of all known prefixes

Return a reference to the current config.

Returns an iterator over all (undirected) links in the network.

Configure the topology to pause the queue and return after a certain number of queue have been executed. The job queue will remain active. If set to None, the queue will continue running until converged.

Returns the name of the router, if the ID was found.

Returns the number of messages exchanged in the last operation. Such an operation might be set_config, apply_modifier, apply_patch, advertise_external_route, …. If the network has been cloned, then the number of msg exchanged is reset to zero.

Clear the undo stack of all routers, and reset the event history. This does not change anything on the state of the network itself.

Return the route for the given prefix, starting at the source router, as a list of RouterIds, starting at the source, and ending at the (probably external) router ID that originated the prefix. The Router ID must be the ID of an internal router.

Print the route of a routerID to the destination. This is a helper function, wrapping self.get_route(source, prefix) inside some print statements. The router ID must he the ID of an internal router

Print the igp forwarding table for a specific router.

Checks for weak equivalence, by only comparing the BGP tables. This funciton assumes that both networks have identical routers, identical topologies, identical configuration and that the same routes are advertised by the same external routers.

Trait Implementations

Cloning the network does not clone the event history, and any of the undo traces.

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Returns the “default value” for a type. Read more

The PartialEq implementation checks if two networks are identica. The implementation first checks “simple” conditions, like the configuration, before checking the state of each individual router. Use the Network::weak_eq function to skip some checks, which can be known beforehand. This implementation will check the configuration, advertised prefixes and all routers.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Performs the conversion.

Performs the conversion.

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

🔬 This is a nightly-only experimental API. (toowned_clone_into)

recently added

Uses borrowed data to replace owned data, usually by cloning. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.