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

Types of elements in a layered network.

TASK = 1

ENTRY = 2

ACTIVITY = 3

PROCESSOR = 4

HOST = 5

class LayeredNetworkStruct(dag, mult, type, isref)[source]

Bases: object

Structure representing a layered network for LSN analysis.

dag

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

Type:: numpy.ndarray

mult

Multiplicity (max concurrent instances) for each node (n,).

Type:: numpy.ndarray

type

Node type for each node (n,), using LayeredNetworkElement values.

Type:: numpy.ndarray

isref

Reference task flags (n,). Non-zero indicates a reference task.

Type:: numpy.ndarray

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)