network module

class panco.descriptor.network.Network(servers: List[Server], flows: List[Flow], arrival_shaping=None)

Bases: object

The class Network encodes a network. A network is described by

• a list of servers (with minimal and maximal service curves)

• a list of flows (with a path and an arrival curve)

• some shaping parameters: if flows are shaped at the entrance of the network.

Parameters:

• servers – the list of server description

• flows – the list of flows circulating in the network

• arrival_shaping (List[(int, List[int], List[TokenBucket])] if not None) – the potential shaping for groups of flows (server, list of flows, maximum service curve)

• self.num_servers – number of servers in the network (int)

• self.num_flows – number of flows in the network (int)

• self.path – list of paths of the flows (List[List[int]])

• self.predecessors – list of predecessors of the servers (List[List[int]])

• self.successors – list of successors of the servers (List[List[int]])

• self.flows_in_server – list of flows crossing each server (List[List[int]])

>>> flows = [Flow([TokenBucket(2, 1)], [0, 1]), Flow([TokenBucket(3, 2)], [1, 0])]
>>> servers = [Server([RateLatency(5, 1)], []), Server([RateLatency(6, 2)], [])]
>>> arrival_shaping = [(0, [0], [TokenBucket(1, 6)])]
>>> network = Network(servers, flows, arrival_shaping)
>>> network.num_servers
2
>>> network.num_flows
2
>>> network.flows == flows
True
>>> network.servers == servers
True
>>> network.path
[[0, 1], [1, 0]]
>>> network.predecessors
[[1], [0]]
>>> network.successors
[[1], [0]]
>>> network.flows_in_server
[[0, 1], [0, 1]]

aggregate_aux(flow_list: List[int], foi: int) → List[Flow]

Aggregates flows in flow_list, not being the foi having the same source and destination

Parameters:

• flow_list – list of flows

• foi – the flow of interest

Returns:

the list of aggregated flows

aggregate_network(foi: int)

Builds a new network where flows following the same path and having the same shaping / absence of shaping are aggretated together. The flow of interest is never aggregated to others. This method only applies to well-numbered trees

Parameters:

foi – the flow of interest

Returns:

the new network and the new number of the flow of interest

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(3, 4)], [0, 1, 2]),
...          Flow([TokenBucket(1, 2)], [0, 1]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2]), Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> arrival_shaping = [(0, [0, 1, 2, 3], [TokenBucket(0, 20)]), (1, [4, 5], [TokenBucket(0, 5)])]
>>> tandem = Network(servers, flows, arrival_shaping)
>>> tandem.aggregate_network(0)
(<Network:
Flows:
      0: α(t) = min [3 + 4t]; π = [0, 1, 2]
      1: α(t) = min [3 + 4t]; π = [0, 1, 2]
      2: α(t) = min [2 + 4t]; π = [0, 1]
      3: α(t) = min [4 + 2t]; π = [1, 2]
Servers:
      0: β(t) = max [8(t - 1)_+]
         σ(t) = min []
      1: β(t) = max [10(t - 3)_+]
         σ(t) = min [0 + 10t]
      2: β(t) = max [6(t - 0)_+]
         σ(t) = min []>, 0)
>>> tandem.aggregate_network(0)[0].arrival_shaping
[(0, [0, 1, 2], [0 + 20t]), (1, [3], [0 + 5t])]

decomposition(keep_edges: List[int, int])

Decomposition of the network by keeping edges in keep_edges, and cutting the flows. returns a new network with arrival curve[0] for all flows obtained from one flow returns list_first the list of the first path of the initial flows

Parameters:

keep_edges – the edges to keep in the network

Returns:

the new network, the list of the number of flows that are the start of the original flows, the list of edges removed in the network.

>>> flows = [Flow([TokenBucket(1, 1)], [3, 4]), Flow([TokenBucket(2, 2)], [0, 3]),
...          Flow([TokenBucket(3, 3)], [2, 4]), Flow([TokenBucket(4, 4)], [1, 3, 4])]
>>> servers = [Server([RateLatency(10, 1)], []), Server([RateLatency(20, 2)], []),
...            Server([RateLatency(30, 3)], []), Server([RateLatency(40, 3)], [TokenBucket(0, 40)]),
...            Server([RateLatency(50, 5)], [])]
>>> arrival_shaping = [(0, [1], [TokenBucket(10, 0)])]
>>> tree = Network(servers, flows, arrival_shaping)
>>> tree.decomposition([(0, 3), (1, 3), (2, 4)])
(<Network:
Flows:
      0: α(t) = min [1 + 1t]; π = [3]
      1: α(t) = min [1 + 1t]; π = [4]
      2: α(t) = min [2 + 2t]; π = [0, 3]
      3: α(t) = min [3 + 3t]; π = [2, 4]
      4: α(t) = min [4 + 4t]; π = [1, 3]
      5: α(t) = min [4 + 4t]; π = [4]
Servers:
      0: β(t) = max [10(t - 1)_+]
         σ(t) = min []
      1: β(t) = max [20(t - 2)_+]
         σ(t) = min []
      2: β(t) = max [30(t - 3)_+]
         σ(t) = min []
      3: β(t) = max [40(t - 3)_+]
         σ(t) = min [0 + 40t]
      4: β(t) = max [50(t - 5)_+]
         σ(t) = min []>, [0, 2, 3, 4], dict_keys([(3, 4)]))
>>> tree.decomposition([(0, 3), (1, 3), (2, 4)])[0].arrival_shaping
[(0, [2], [10 + 0t]), (4, [1, 5], [0 + 40t])]

property depth: List[int]

Returns the depth of each server in a rooted-forest (the root of each tree is the unique sink of the connected component). Sinks have depth 0 and a node has the depth of its successor + 1

Returns:

the list of depths for each server (List[int])

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.depth
[2, 1, 0]

property edges: defaultdict[Tuple[int, int], List[int]]

Builds the dictionary of the edges of the networks. The keys are a pair in integers and the value is the set of flows crossing that edge.

Returns:

The dictionary of the edges.

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.edges
defaultdict(<class 'list'>, {(0, 1): [0, 1], (1, 2): [0, 2]})

property is_elementary: bool

checks if the network has only paths of length 1

Returns:

True if the network has ony paths of length 1, False otherwise

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.is_elementary
False
>>> flows = [Flow([TokenBucket(3, 4)], [0]), Flow([TokenBucket(1, 2)], [1]),
...          Flow([TokenBucket(2, 1)], [2]),Flow([TokenBucket(2, 1)], [2]), ]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> elementary = Network(servers, flows)
>>> elementary.is_elementary
True

property is_feed_forward: bool

Checks is the network in feed-forward, and the servers numbered in increasing order according to the topological sort of the network

Returns:

True if the network is feed-forward, False otherwise

>>> flows = [Flow([TokenBucket(2, 1)], [0, 1]), Flow([TokenBucket(3, 2)], [1, 0])]
>>> servers = [Server([RateLatency(5, 1)], []), Server([RateLatency(6, 2)], [])]
>>> network = Network(servers, flows)
>>> network.is_feed_forward
False
>>> flows_ff = [Flow([TokenBucket(3, 4)], [0, 1, 3]), Flow([TokenBucket(1, 2)], [0, 2, 3])]
>>> servers_ff = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...               Server([RateLatency(10, 3)], [TokenBucket(0, 10)]), Server([RateLatency(6, 0)], [])]
>>> feed_forward = Network(servers_ff, flows_ff)
>>> feed_forward.is_feed_forward
True

is_sink(server) → bool

Checks if the server is a sink (has no successor)

Parameters:

server – the server under consideration

Returns:

True if it is a sink, False otherwise

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.is_sink(2)
True
>>> tandem.is_sink(0)
False

property is_sink_tree: bool

Checks if self is a sink-tree (a tree and all flows end at the last server)

Returns:

True if self is a sink-tree, False otherwise

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.is_sink_tree
False
>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> sink_tree = Network(servers, flows)
>>> sink_tree.is_sink_tree
True

property is_tree: bool

checks if the network is a rooted-forest, and the servers numbered in increasing number

Returns:

True if the network is rooted-forest, False otherwise

>>> flows_ff = [Flow([TokenBucket(3, 4)], [0, 1, 3]), Flow([TokenBucket(1, 2)], [0, 2, 3])]
>>> servers_ff = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...               Server([RateLatency(10, 3)], [TokenBucket(0, 10)]), Server([RateLatency(6, 0)], [])]
>>> feed_forward = Network(servers_ff, flows_ff)
>>> feed_forward.is_tree
False
>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.is_tree
True

property list_loads: List[float]

Computes the load of the servers: the list of the ratio between the sum of arrival rates of flows crossing this server and the service rate of the server.

Returns:

the list of the usage of all servers

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.list_loads == [0.75, 0.7, 5/6]
True

property load: float

Computes the load of the network: the minimum on all servers of the ratio between the sum of arrival rates of flows crossing this server and the service rate of the server.

Returns:

the load / usage of the network

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.load == 5/6
True

make_feed_forward() → Network

Transforms a network without cyclic dependencies into a feed-forward network with renumbered the nodes in the topological order.

Returns:

the same network with good numbering. The order of the flows is unchanged.

>>> flows_ff = [Flow([TokenBucket(3, 4)], [1, 0, 2]), Flow([TokenBucket(1, 2)], [1, 3, 2])]
>>> servers_ff = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...               Server([RateLatency(10, 3)], [TokenBucket(0, 10)]), Server([RateLatency(6, 0)], [])]
>>> feed_forward = Network(servers_ff, flows_ff)
>>> feed_forward.make_feed_forward()
<Network:
Flows:
      0: α(t) = min [3 + 4t]; π = [0, 2, 3]
      1: α(t) = min [1 + 2t]; π = [0, 1, 3]
Servers:
      0: β(t) = max [10(t - 3)_+]
         σ(t) = min [0 + 10t]
      1: β(t) = max [6(t - 0)_+]
         σ(t) = min []
      2: β(t) = max [8(t - 1)_+]
         σ(t) = min []
      3: β(t) = max [10(t - 3)_+]
         σ(t) = min [0 + 10t]>

property residual_network: List[Server]

” Computes the residual service curves of all servers (to be used for lower priority flows for example) This method only applies to feed-forward networks

Returns:

the list of residual service curves.

>>> flows = [Flow([TokenBucket(3, 4)], [0]), Flow([TokenBucket(1, 2)], [1]),
...          Flow([TokenBucket(2, 1)], [2]),Flow([TokenBucket(2, 1)], [2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> elementary = Network(servers, flows)
>>> elementary.residual_network
[<Server: β(t) = max [4(t - 2.75)_+]
         σ(t) = min []>
, <Server: β(t) = max [8(t - 3.875)_+]
         σ(t) = min [0 + 10t]>
, <Server: β(t) = max [4(t - 1.0)_+]
         σ(t) = min []>
]

residual_rate(foi: int) → float

Computes the residual rate of flow foi: the minimum on all the servers of its path of the difference between the service rate and the other flow’s arrival rate

Parameters:

foi – flow of interest

Returns:

the residual rate

>>> flows = [Flow([TokenBucket(3, 4)], [0, 1, 2]), Flow([TokenBucket(1, 2)], [0, 1]),
...          Flow([TokenBucket(2, 1)], [1, 2])]
>>> servers = [Server([RateLatency(8, 1)], []), Server([RateLatency(10, 3)], [TokenBucket(0, 10)]),
...            Server([RateLatency(6, 0)], [])]
>>> tandem = Network(servers, flows)
>>> tandem.residual_rate(0)
5

sub_network(foi: int)

Builds a sub-network with sink the last server crossed by the flow foi This methods applies only to well-numbered feed-forward networks

Parameters:

foi – the flow of interest

Returns:

the sub-network, the flow number of the foi in this new network, the list of the number

of flows of the original network and the list of the number of servers of the original network.

>>> fls = [Flow([TokenBucket(1, 1)], [3, 4]), Flow([TokenBucket(2, 2)], [0, 3]),
...          Flow([TokenBucket(3, 3)], [2, 4]), Flow([TokenBucket(4, 4)], [1, 3, 4])]
>>> sers = [Server([RateLatency(10, 1)], []), Server([RateLatency(20, 2)], []),
...            Server([RateLatency(30, 3)], []), Server([RateLatency(40, 3)], []),
...            Server([RateLatency(50, 5)], [])]
>>> arr_shaping = [(3, [0], [TokenBucket(0, 10)]), (1, [3], [TokenBucket(0, 20)]),
...                    (2, [2], [TokenBucket(0, 30)]), (0, [1], [TokenBucket(0, 40)])]
>>> tree = Network(sers, fls, arr_shaping)
>>> tree.sub_network(1)
(<Network:
Flows:
      0: α(t) = min [1 + 1t]; π = [2]
      1: α(t) = min [2 + 2t]; π = [0, 2]
      2: α(t) = min [4 + 4t]; π = [1, 2]
Servers:
      0: β(t) = max [10(t - 1)_+]
         σ(t) = min []
      1: β(t) = max [20(t - 2)_+]
         σ(t) = min []
      2: β(t) = max [40(t - 3)_+]
         σ(t) = min []>, 1, [0, 1, 3], [0, 1, 3])
>>> tree.sub_network(1)[0].arrival_shaping
[(2, [0], [0 + 10t]), (1, [2], [0 + 20t]), (0, [1], [0 + 40t])]

unfold(foi: int) → Tuple[Network, int]

Unfolds a feed-forward network into a tree, from the last server visited by the flows of interest. This method can be aplied to any acyclic network (not necessarily well-numbered), and will not end if there are cycles.

Parameters:

foi – flow of interest

Returns:

the unfolded network and the new number of the flows of interest

>>> flows = [Flow([TokenBucket(1, 1)], [2, 1, 0, 3]), Flow([TokenBucket(2, 2)], [1, 3])]
>>> servers = [Server([RateLatency(10, 1)], []), Server([RateLatency(20, 2)], [TokenBucket(0, 20)]),
...            Server([RateLatency(30, 3)], []), Server([RateLatency(40, 3)], [])]
>>> arrival_shaping = [(2, [0], [TokenBucket(0, 10)])]
>>> tree = Network(servers, flows, arrival_shaping)
>>> tree.unfold(0)
(<Network:
Flows:
      0: α(t) = min [1 + 1t]; π = [0, 2, 4, 5]
      1: α(t) = min [1 + 1t]; π = [1, 3]
      2: α(t) = min [2 + 2t]; π = [2]
      3: α(t) = min [2 + 2t]; π = [3, 5]
Servers:
      0: β(t) = max [30(t - 3)_+]
         σ(t) = min []
      1: β(t) = max [30(t - 3)_+]
         σ(t) = min []
      2: β(t) = max [20(t - 2)_+]
         σ(t) = min [0 + 20t]
      3: β(t) = max [20(t - 2)_+]
         σ(t) = min [0 + 20t]
      4: β(t) = max [10(t - 1)_+]
         σ(t) = min []
      5: β(t) = max [40(t - 3)_+]
         σ(t) = min []>, 0)
>>> tree.unfold(0)[0].arrival_shaping
[(0, [0], [0 + 10t]), (1, [1], [0 + 10t])]

panco.descriptor.network.backward_search(sink: int, predecessors: List[List[int]]) → List[int]

Performs the backward search of the servers having a path directed to sink.

Parameters:

• sink – the server from which the backward search is done

• predecessors – list of the list of predecessors of each server

Returns:

the list of servers having a path to sink (List[int])

>>> backward_search(3, [[2], [0], [1, 3], [1]])
[0, 1, 2, 3]
>>> backward_search(3, [[1], [0], [1, 3], [1]])
[0, 1, 3]

panco.descriptor.network.dfs(u: int, num_servers: int, successors: List[List[int]], state: List[int], queue: List[int], sort: List[int]) → Tuple[List[int], List[int], List[int]] | None

Depth-first-search implementation of a graph without cycles

Parameters:

• u – source node

• num_servers – size of the network

• successors – adjacency list of the nodes (list of successors)

• state – state of the nodes (‘white’/’gray’/’black’)

• queue – set of nodes queued for analysis

• sort – list of nodes in the reversed order of end of discovery (when they become ‘black’)

Returns:

the new state after exploration from u, new queue, update order

>>> dfs(4, 6, [[], [0], [1, 4], [], [0, 3, 5], [3]], [0, 0, 0, 0, 0, 0], [], [])
(array([2, 0, 0, 2, 2, 2]), [], [4, 5, 3, 0])

panco.descriptor.network.inverse_permutation(tab: List[int]) → List[int]

Function that inverses a list. It gives the position in the decreasing order.

Parameters:

tab – the inverse of the list

Returns:

the permutation of th ordering: tab[inverse_tab[i]] = i

>>> inverse_permutation([1, 3, 0, 2])
[2, 0, 3, 1]

panco.descriptor.network.list_to_str(lis: list) → str

panco.descriptor.network.print_list(lis: list)

panco.descriptor.network.reindexing(lis: List[int]) → Dict[int, int]

Builds a disciotany from a list. dict[key] is the place of key/

Parameters:

lis – list

Returns:

the dicionnart of the indices of the list

>>> reindexing([3, 1, 4, 6])
{3: 0, 1: 1, 4: 2, 6: 3}

panco.descriptor.network.server_depth(num_servers: int, successors: List[List[int]]) → List[int]

Returns the depth of each server in a rooted-forest (the root of each tree is the unique sink of the connected component). Sinks have depth 0 and a node has the depth of its successor + 1 The servers must be ordered by their depth (a node has a successor with higher number)

Parameters:

• num_servers – the number of servers in the network

• successors – The list of successors in of each server

Returns:

the list of depths for each server (List[int])

>>> server_depth(8, [[2], [3], [7], [4], [7], [7], [7], []])
[2, 3, 1, 2, 1, 1, 1, 0]

panco.descriptor.network.topological_sort(successors: List[List[int]], num_servers: int) → List[int]

Function that sorts the servers in a topological order given by its lists of successors (adjacency)

Parameters:

• successors – the list of successors of each node

• num_servers – the number of nodes of the graph

Returns:

the topological order of the nodes, and an error if the graph has cycles.

>>> topological_sort([[], [0], [1, 4], [], [0, 3, 5], [3]], 6)
[2, 4, 5, 3, 1, 0]

panco.descriptor.network.topology(num_servers: int, num_flows: int, path: List[List[int]])

” Topology builds the set of successors and predecessors of the network, also builds for each server the list of flows crossing it.

Parameters:

• num_servers (int) – the number of servers in the network

• num_flows (int) – the number of flows in the network

• path (List[List[int]]) – list of paths followed by the flows

Return predecessors:

the list of the predecessor’s list for each server (List[List[int]])

Return successors:

the list of the successor’s list for each server (List[List[int]])

Return flows_in_server:

the list of flows that cross each server (List[List[int]])

>>> paths = [[0, 1, 3], [3, 2, 0], [1, 2]]
>>> topology(4, 3, paths)
([[2], [0], [1, 3], [1]], [[1], [2, 3], [0], [2]], [[0, 1], [0, 2], [1, 2], [0, 1]])

panco.descriptor.network.trunc_path(path: List[List[int]], list_servers: [List[int]]) → List[List[int]]

Computes the sub-path of servers in list_servers for each path in path

Parameters:

• path – list of paths

• list_servers – list of servers

Returns:

the list of sub_paths (List[List[int]])

>>> trunc_path([[0, 1, 2, 3], [2, 3, 4], [3, 2, 5, 1]], [0, 1, 3])
[[0, 1, 3], [3], [3, 1]]