commutativity_model

The commutativity model is a generalization of the cactus model.

In the generalized commutativity model, it must be ensured that node mappings are consistent. That means, if there are multiple paths between two request nodes, the end node has to be mapped to the same substrate node on all paths.

For doing that, the model creator (CommutativityModelCreator) uses a labeling algorithm (CommutativityLabels()).

In the context of the commutativity model, an end node is the end node of a cycle in the DAG, having at least two in-neighbors. The labels of a node or an edge are a set of end nodes. A node or edge is labeled with an end node if there is a simple cycle (a cycle without repetitions) through the node or edge ending in the end node.

For each edge, the labels are extracted. For each possible mapping of the edge labels, a EdgeSubLP is created.

A mapping of labels to substrate nodes is called commutativity index in this context.

Labeling algorithm

The labeling is done in four steps in CommutativityLabels.create_labels():

1. Determine the reachable end nodes of every request node. Start from leaf nodes going up.

2. Check pairwise overlaps of the children of every request node that has multiple children. Identify end nodes that are in at least one overlap of the children.

3. Reduce the overlapping sets by removing dominated nodes so that only the actual cycle end nodes of simple cycles remain.

   If it is not possible to find a path from a possible start node to an end node from the overlapping set without visiting one avoided node, the possible start node is not a start node of the end node (dominated). Try other nodes from the overlapping set as avoid node.

4. Propagate the labels to all nodes on paths between the start and end nodes.

LP model

Variables

node_mapping_agg (req, i, u)

aggregated node mappings

node_mapping (req, i, u, commutativity index)

node mappings

In edge sub-LPs:

node_flow_source (req, ij, u, commutativity index)

node flows of the sub-LP sources

edge_flow (req, ij, uv, commutativity index)

edge flows of the substrate copy

node_flow_sink (req, ij, v, commutativity_index)

node flows of the sub-LP sinks

Constraints

force_node_mapping_for_embedded_request (req)

force the embedding of the request

node_mapping_aggregation (req, i, u, bag)

aggregate node mappings

node_mapping_in_edge_to_bag (req, i, u, ji, commutativity index, bag)

connect sink variables of in-edges and node mapping variables

node_mapping (req, i, u, ij, commutativity index)

connect node mapping variables to source variables of out-edges

track_node_load (req, u, type)

track node loads

track_edge_load (req, uv)

track edge loads

In edge sub-LPs:

flow_preservation (req, ij, u, commutativity index)

flow preservation in an edge sub-LP

Classes

exception vnep_approx.commutativity_model.CommutativityModelError

class vnep_approx.commutativity_model.CommutativityModelCreator(scenario, gurobi_settings=None, optimization_callback=<function gurobi_callback>, lp_output_file=None, potential_iis_filename=None, logger=None)

Model creator of the generalized commutativity model.

classmethod _add_dag_edges_and_initialize_exploration_queue_with_leaf_nodes(req, dag_request)

Explore the original request and create the edges of the DAG.

Parameters:

• req – the original request
• dag_request – the DAG request

static _add_edge_to_dag_request(req, dag_request, edge, is_reversed)

Add an edge to the DAG.

Parameters:

• req (datamodel.Request) – the original request
• dag_request (datamodel.Request) – the DAG request
• edge –
• is_reversed –

_calculate_substrate_load_for_mapping(mapping)

Calculate the substrate load for the mapping.

Parameters:mapping – Returns:a load dict

_create_constraints_track_edge_loads()

Create constraints to track the edge loads.

_create_constraints_track_node_loads()

Create constraints to track the node loads.

_create_force_embedding_constraint()

Create a constraint for every request to force the embedding.

_create_node_mapping_aggregation_constraints(req, i, u, bag_key)

Create the node mapping aggregation constraints.

The sum of the node mapping variables of a bag should be equal to the aggregated node mapping variable.

Parameters:

• req (datamodel.Request) – the request
• i – request node
• u – substrate node of i
• bag_key – labels of the bag

_create_node_mapping_constraints()

Create the node mapping constraints.

_create_node_mapping_constraints_between_in_edges_and_bags(req, i, u, bag_key)

Create the node mapping constraints between the in-edges of a node and the bags (which contain its out-edges).

Parameters:

• req (datamodel.Request) – the request
• i – request node
• u – substrate node of i
• bag_key – labels of the bag

_create_node_mapping_constraints_within_bag(req, i, u, bag_key)

Create the node mapping constraints within a bag.

Parameters:

• req (datamodel.Request) – the request
• i – request node
• u – substrate node of i
• bag_key – labels of the bag

_create_node_mapping_variables()

Create a node mapping variable for every commutativity index of all request nodes. Also initialize the used flows.

_create_sub_lp_constraints()

Create the Gurobi constraints of every sub-LP.

_create_sub_lp_variables()

Create the Gurobi variables of every sub-LP.

_get_valid_substrate_nodes(req, labels)

Returns a dictionary mapping request nodes to sets of allowed and valid substrate nodes.

Parameters:

• req –
• labels – iterable of request nodes (usually labels)

Returns:

classmethod _initialize_dag_request(req)

Create a DAG request for the request.

Parameters:req – the request Returns:a rooted DAG request

_make_reversed_substrate()

Generate a copy of the substrate with all edges reversed.

All default substrate node and edge properties are preserved.

Returns:the reversed substrate Return type:datamodel.SubstrateX

_prepare_edge_sub_lp()

Create an EdgeSubLP for every commutativity index of all request edges.

create_constraints_other_than_bounding_loads_by_capacities()

Create the Gurobi constraints for the sub-LPs, the node mappings, the node and edge loads and the embedding constraints.

create_variables_other_than_embedding_decision_and_request_load()

Create node mapping and sub-LP Gurobi variables.

edge_sub_lp = None

request -> request edge -> commutativity index -> EdgeSubLP

extract_request_mapping(req, labels, mapping_count)

Extract a request mapping.

This is called by recover_fractional_solution_from_variables() as long as there is flow remaining. If there is remaining flow, this function should find a mapping.

Parameters:

• req (datamodel.Request) – the request
• labels (CommutativityLabels) – the labels of the request
• mapping_count (int) – the mapping count used for the mapping name

Returns:

a mapping of the request and the corresponding flow

Return type:

(solutions.Mapping, float)

generate_label_comm_index(req, labels, fixed_mappings=None)

For a set of labels, yield each possible commutativity index as a list of tuples.

Parameters:

• req (datamodel.Request) – the request
• labels – a label set
• fixed_mappings – nodes which should be included in the comm-index with a fixed mapping

static get_commutativity_index_from_mapping(labels, mapping)

Get the mapping of the labels that are already fixed.

Parameters:

• labels –
• mapping (solutions.Mapping) –

Returns:

the commutativity index

post_process_fractional_computation()

post_process_integral_computation()

preprocess_input()

Create labels and edge sub-LPs for every request.

recover_fractional_solution_from_variables()

Recover the fractional solution from the Gurobi variables.

Extract mappings as long as flow is remaining.

recover_integral_solution_from_variables()

reduce_flow(mapping, used_flow)

Reduce the flow on the mapping by increasing the used flows.

Parameters:

• mapping – the full mapping
• used_flow – the amount of flow to reduce

class vnep_approx.commutativity_model.EdgeSubLP(dag_request, substrate_oriented, ij, commutativity_index, is_reversed_edge)

An edge sub-LP handles the model variables and constraints and is used to extract the mapping.

extend_edge_load_constraints(load_constraint_dict)

Extend the edge load constraints by adding this sub-LP’s edge mapping variables.

The constraint is converted to a gurobipy.LinExpr and added to the model by the CommutativityModelCreator.

Node mapping load is handled in the ModelCreator using the (global) aggregation layer variables.

Parameters:load_constraint_dict – Dictionary mapping substrate edges to list of tuples of coefficients & gurobi variables Returns:the extended load_constraint_dict

extend_model_constraints(model)

Extend the Gurobi model with the flow preservation constraints of the edge sub-LP.

Parameters:model (gurobipy.Model) – the Gurobi model

extend_model_variables(model)

Extend the Gurobi model with the node and edge flow variables of the edge sub-LP.

Parameters:model (gurobipy.Model) – the Gurobi model

extract_edge_mapping(partial_mapping)

Extract the edge mapping of the sub-LP.

The partial mapping is used to specify the allowed entries (sources) and exits (sinks) of the sub-LP. The entry node should be fixed in the node mapping in CommutativityModelCreator.extract_request_mapping() before. The exit node can also be fixed if it was contained in the commutativity index before. Otherwise all sinks with a remaining flow larger than 0 are used.

The path between the entry and a allowed exit is found by using sub-LP edges with a remaining flow larger than 0.

Parameters:partial_mapping – the partial global mapping Returns:the path from an entry to an exit, the exit, the minimum flow on the path

reduce_flow(mapping, used_flow)

Reduce the flow on the edge mapping.

The flow reduction is done by increasing the used flow of the source, the sink and every substrate edge of the path.

Parameters:

• mapping – the full mapping
• used_flow – the amount of flow to reduce

class vnep_approx.commutativity_model.CommutativityLabels(node_labels, dag_request)

A CommutativityLabels object contains labels for all nodes of a DAG request.

A node is labeled with the end nodes of all possible cycles containing the node.

calculate_edge_label_bags(i)

Given a request node, group its outgoing edges into bags according to overlapping edge labels.

Parameters:i – request node Returns:dictionary (node label set -> set of edges in that bag)

classmethod create_labels(dag_request)

Calculate labels of a DAG request.

Parameters:dag_request – the DAG request Returns:the calculated labels Return type:CommutativityLabels

get_edge_labels(ij)

Calculate the labels of the request edge ij.

The labels of ij are the intersection of the labels of i and j.

Parameters:ij – the edge Returns:the labels of ij