Layered Stochastic Networks

Layered queueing network analysis.

The lsn module provides algorithms for layered stochastic networks and layered queueing networks (LQNs).

Key function categories:

Layered Stochastic Network (LSN) utilities.

Native Python implementations for layered queueing network analysis.

Key functions:

lsn_max_multiplicity: Compute maximum multiplicity for tasks in a layered network.

Key classes:

LayeredNetworkStruct: Structure representing a layered network. LayeredNetworkElement: Enumeration of layered network element types.

class LayeredNetworkElement(*values)[source]

Bases: IntEnum

Element types in layered queueing networks.

THE single definition; layered.py, the LN solver and api/lsn import it. Values are the JAR’s jline.lang.layered.LayeredNetworkElement constants, which is what lsn.type carries (see LayeredNetwork.getStruct). MATLAB has no such enumeration: LayeredNetworkElement.m is the BASE CLASS the layered elements derive from, so the JAR is ground truth here.

api/lsn/max_multiplicity.py used to declare a third copy numbering PROCESSOR 4 and inventing a HOST 5, against the lsn.type it reads; it only ever compared TASK and ENTRY, which happen to agree, so the wrong numbering never showed.

PROCESSOR = 0
HOST = 0
TASK = 1
ENTRY = 2
ACTIVITY = 3
CALL = 4
class LayeredNetworkStruct(dag, mult, type, isref, arrival=None, hassetup=None, repl=None, parent=None)[source]

Bases: object

Structure representing a layered network for LSN analysis.

Variables:

  • dag (numpy.ndarray) – Directed acyclic graph adjacency matrix (n x n). dag[i,j] > 0 indicates an edge from node i to node j.

  • mult (numpy.ndarray) – Multiplicity (max concurrent instances) for each node (n,).

  • type (numpy.ndarray) – Node type for each node (n,), using LayeredNetworkElement values.

  • isref (numpy.ndarray) – Reference task flags (n,). Non-zero indicates a reference task.

  • arrival (object | None) – Optional open-arrival processes per entry (dict or list indexed by node; a non-None entry marks an open arrival).

  • hassetup (numpy.ndarray | None) – Optional setup/delay-off flags per node (n,).

  • repl (numpy.ndarray | None) – Optional replication per node (n,); entries and activities take their task’s from parent.

  • parent (numpy.ndarray | None) – Optional parent index per node (n,): the task of an entry or activity, the processor of a task.

dag: ndarray
mult: ndarray
type: ndarray
isref: ndarray
arrival: object | None = None
hassetup: ndarray | None = None
repl: ndarray | None = None
parent: ndarray | None = None
kahn_topological_sort(adjacency)[source]

Perform Kahn’s algorithm for topological sorting.

Parameters:

adjacency (ndarray) – Adjacency matrix where adjacency[i,j] > 0 means edge i -> j.

Returns:

List of node indices in topological order.

Raises:

ValueError – If the graph contains a cycle.

Return type:

List[int]

lsn_max_multiplicity(lsn)[source]

Compute the maximum multiplicity for each task in a layered network.

Uses flow analysis based on Kahn’s topological sorting algorithm to determine the maximum sustainable throughput for each task, considering both the incoming flow and the multiplicity constraints.

Parameters:

lsn (LayeredNetworkStruct) – The layered network structure containing task dependencies and constraints.

Returns:

Matrix of maximum multiplicities for each task in the network (n x 1).

Return type:

ndarray

Algorithm:

  1. Build binary adjacency graph from DAG

  2. Apply Kahn’s topological sort to determine processing order

  3. Initialize inflow from reference tasks

  4. For each node in topological order: - outflow = min(inflow, multiplicity constraint) - Propagate outflow to downstream nodes

  5. Handle unreachable tasks (infinite multiplicity)

Replication (BUG-111): what flows is threads totalled over the replicas (a reference task seeds mult*r, an open-arrival entry one thread per task replica, an element passes on min(inflow, mult*r)), while the value returned is what one replica holds, min(inflow, mult), the divisor of the hosts’ utilisation. A processor replica receives only the r(task)/r(processor) task replicas it runs, each holding at most its own reach.

Example

>>> lsn = LayeredNetworkStruct(
...     dag=np.array([[0, 1, 0], [0, 0, 1], [0, 0, 0]]),
...     mult=np.array([2, 3, 5]),
...     type=np.array([1, 1, 1]),
...     isref=np.array([1, 0, 0])
... )
>>> max_mult = lsn_max_multiplicity(lsn)