Layered Stochastic Networks

Layered queueing network analysis.

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

Key function categories:

Multiplicity analysis: lsn_max_multiplicity()

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)[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.

dag: ndarray

mult: ndarray

type: ndarray

isref: ndarray

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.

This function 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:

Build binary adjacency graph from DAG
Apply Kahn’s topological sort to determine processing order
Initialize inflow from reference tasks
For each node in topological order: - outflow = min(inflow, multiplicity constraint) - Propagate outflow to downstream nodes
Handle unreachable tasks (infinite multiplicity)

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)