admTFA module

This file is the implementation of the results of the paper:

[Bou] Anne Bouillard, Admission Shaping With Network Calculus. IEEE Networking Letter 6(2): 115-118 (2024) It generalizes the TFA analysis of a FIFO network by

  • allowing shaping flows together when they enter a system

  • computing a fixed point analysis when the arrival curves are a minimum of token-bucket curves

  • introducing the interleaved and per flow shaping in the resolution of the fixed point, as define in [TLM19].

[TLM19] Ludovic Thomas, Jean-Yves Le Boudec, Ahlem Mifdaoui. On Cyclic Dependencies and Regulators in Time-Sensitive Networks. RTSS 2019: 299-311

class panco.fifo.admTFA.AdmTfa(network: Network, filename='tfa_new.lp')

Bases: object

The class TfaLP computes delay bounds using the TFA++ method, using a linear program. For feed-forward networks, does the same as [Mifdaoui, Leydier RTSS17], except that it makes no assumption on the maximum service rate. For cyclic networks, it computes the same as [Thomas, Le Boudec, Mifdaoui, RTSS 19], without this same assumption, and directly computes the fix-point, without iterating. However, this takes into account only the first token-bucket of the arrival curves

Parameters:

  • network – the network to analyse.

  • filename – name of the file to write the linear program

expand_shaping is built from the expand_shaping_function

property all_backlogged_periods
property all_backlogs
property all_delays: List[float]

Returns the delay bounds for all the flows

Returns:

the list of delay bounds

delay(foi: int) → float

Returns the delay bound for flow foi

Parameters:

foi – the flow of interest

Returns:

the delay bound of foi

property delay_servers: List[float]

Computes the list of delays for all servers

Returns:

the list of delays for all servers

property dict_bursts

Computes the dictionary of the bursts parameters for all flows at each server

Returns:

the dictionary of the bursts parameters for all flows at each server

property dict_bursts_shaping

Computes the dictionary of the bursts parameters for all shaping.

Returns:

the dictionary of the bursts parameters for all shaping

property extract_regulators

Extracts the shaping regulators after ff_equiv hav been computed. - for IR, this is the arrival curve at the server - for PFR, this is the output of the previous regulator on the path (of the arrival curve)

:return:the list of the regulators

property ff_equiv: Network

The equivalent network decomposed into elementary servers

Returns:

a network

property idx_equiv

This is used to compute the equivalent network (made of elementary 1-server networks). Every path is then split into elementary path, and flows are renumbered. In the equivalent network, the flows are then (i, j) for all flows i and all servers j on the path of i. This computes the dictionary flow re-numbering in the equivalent network.

Returns:

dictionary of flow numbering of the equivalent network.

regulator_constraints(file)

Constraints for the regulators. Instead of propagating the bursts, when there is a regulator, takes the output process of a previous server according to the regulation.

Parameters:

file – file where to write the constraints

Returns:

None

regulator_on_path(i: int) → List[int]

For flow i, computes the list of the last regulator on its path: this gives the parameters of the regulator taken for the analysis. For example, if the path is [0, 1, 2, 3, 4], and regulators are (NO, IR, NO, PFR, NO), then the result is [0, 1, 1, 3, 2, 5], and the regulator for server 1 is according to the arrival curve at server 1 amd the regulator for server 3 is according to the arrival curve at server 2.

Parameters:

i – The flow number.

Returns:

the list of the last regulators.

>>> flow =  Flow([TokenBucket(1, 1)], [0, 1, 2, 3, 4])
>>> server_no = Server([RateLatency(10, 0)], [], NO)
>>> server_fpr = Server([RateLatency(10, 0)], [], PFR)
>>> server_ir = Server([RateLatency(10, 0)], [], IR)
>>> servers = [server_no, server_ir, server_no, server_fpr, server_no]
>>> network1 = Network(servers, [flow])
>>> AdmTfa(network1).regulator_on_path(0)
[0, 1, 1, 3, 2, 5]
single_server_backlog(server: int) → float
single_server_backlogged_period(server: int) → float
property solve: Tuple[ndarray, defaultdict, defaultdict]

Computes the delay bounds of all the servers, and the burst parameters for all flows and shaping at all servers.

Returns:

the list of the delays of the servers, and of the bursts

property solve_optim: Tuple[ndarray, ndarray]

Computes the delay bounds of all the servers, and the level at which the worst-case delay is computed for each server. (Used for optimization)

Returns:

the list of the delays of the servers and level at which the worst-case delay happens.

tfa_constraints_server(file)

Writes the TFA constraints for each server

Parameters:

file – the file where the constraints are written

Returns:

None

tfa_shaping_constraints(file)

Writes the shaping constraints, for the extended shaping.

Parameters:

file – file where to write the linear constraints

Returns:

None

tfa_variables(file)

Writes the constraints of the fix-point variables (the burst transmitted for each flow to the next server)

Parameters:

file – the file in which the constraints are written

Returns:

None

panco.fifo.admTFA.expand_shaping_fnc(network: Network) → List[Tuple[int, int, int, Tuple[List[int], int, List[TokenBucket]]]]

Expands the shaping at arrival to all servers: if flows [0, 1, 2, 3, 4] are shaped by some arrival curve, and flows [0, 1, 2] follow the same initial path until some other server, flows [0, 1, 2] will be shaped at this server, by an arrival curve that can be computed. Here we use the same arrival curves, the burst parameters will be computed in the linear program.

Parameters:

network – the network for the shaping

Returns:

the list of shaping and propagation. Each tuple is (number of the shaping, number of the previous shaping (from which it has been built), server of the previous shaping, (server, list of flows, arrival curve))

>>> flow1 = Flow([TokenBucket(1, 1)], [0, 1])
>>> flow2 = Flow([TokenBucket(1, 1)], [0, 2])
>>> flow3 = Flow([TokenBucket(1, 1)], [1, 2])
>>> flows = [flow1, flow1, flow1, flow2, flow2, flow3, flow3, flow3]
>>> arr_shaping = (0, [0, 1, 2, 3, 4], [TokenBucket(0, 5)])
>>> arr_shaping2 = (1, [5, 6, 7], [TokenBucket(0, 3)])
>>> server = Server([RateLatency(10, 1)], [], 0)
>>> network1 = Network([server, server, server], flows, [arr_shaping, arr_shaping2])
>>> expand_shaping_fnc(network1)
[(2, 0, 0, (1, [0, 1, 2], [0 + 5t])), (3, 0, 0, (2, [3, 4], [0 + 5t])), (4, 1, 1, (2, [5, 6, 7], [0 + 3t]))]
panco.fifo.admTFA.extract_keys(dic, i, j)

Function that extracts from a dictionary whose entries are triples, the second component, given that the first and third are respectively i and j

Parameters:

  • dic – the dictionary

  • i – the value of the first component

  • j – the value of the third component

Returns:

the sorted list of the second components

>>> dictionary = defaultdict()
>>> dictionary[(0, 1, 2)] = 1
>>> dictionary[(1, 2, 3)] = 4
>>> dictionary[(0, 3, 2)] =  0
>>> extract_keys(dictionary, 0, 2)
[(1, 1), (3, 0)]