Implementation of Scheduling Algorithms

Supported algorithms

Currently, the following scheduling algorithms are implemented in tsnkit. You can use them by running

## python3 -m tsnkit.algorithms.<algorithm> <task_file> <topo_file>
## For example:

python3 -m tsnkit.algorithms.smt_wa ./task.csv ./topo.csv

Method	Paper
SMT-WA	Scheduling Real-Time Communication in IEEE 802.1Qbv Time Sensitive Networks
AT	IEEE 802.1Qbv Gate Control List Synthesis Using Array Theory Encoding
JRS-WA	ILP-based joint routing and scheduling for time-triggered networks
JRS-NW	How to Optimize Joint Routing and Scheduling Models for TSN Using Integer Linear Programming
JRS-NW-L	Exploring Practical Limitations of Joint Routing and Scheduling for TSN with ILP
JRS-MC	ILP-Based Routing and Scheduling of Multicast Realtime Traffic in Time-Sensitive Networks
SMT-NW	No-wait Packet Scheduling for IEEE Time-sensitive Networks (TSN)
LS-TB	Large-scale periodic scheduling in time-sensitive networks
LS	Heuristic List Scheduler for Time Triggered Traffic in Time Sensitive Networks
SMT-FR	Joint Algorithm of Message Fragmentation and No-Wait Scheduling for Time-Sensitive Networks
I-ILP	Routing and Scheduling of Time-Triggered Traffic in Time-Sensitive Networks
CP-WA	Constraint programming approaches to joint routing and scheduling in time-sensitive networks
I-OMT	Real-Time Scheduling of Massive Data in Time Sensitive Networks With a Limited Number of Schedule Entries
SMT-PR	Time-Triggered Scheduling for Time-Sensitive Networking with Preemption
CG	Time-Triggered Traffic Planning for Data Networks with Conflict Graphs
DT	Efficient Flow Scheduling for Industrial Time-Sensitive Networking: A Divisibility Theory-Based Method
LS-PL	HERMES: Heuristic Multi-queue Scheduler for TSN Time-Triggered Traffic with Zero Reception Jitter Capabilities

The detailed description of each algorithm and their corresponding system model can be found in our paper.

Contribution

Contributing new algorithms

It is very welcome to contribute new algorithms to tsnkit. To do so, you need to create a new class in tsnkit.algorithms with a new .py file that implements the interface class _Method. The full description can be found in tsnkit.algorithms.__init__.py file. You can refer the implementation of other algorithms in tsnkit.algorithms folder.

class _Method(ABC):

    @abstractmethod
    def init(self, task_path: str, network_path: str) -> bool

    @abstractmethod
    def prepare(self) -> bool

    @abstractmethod
    def solve(self) -> Statistics

    @abstractmethod
    def output(self) -> Config

We use github flow to propose changes to the codebase. Make sure you have done local testing with the provided simulation tool or by your hand before submitting a pull request.

Coding style:

• Avoid directly loading algorithm input files. Instead, utilize the load_stream and load_network functions provided by tsnkit.core. These functions are essential as they perform checks on the input file format and ensure the integrity and fairness of benchmarking results. It is also recommended to use the Stream and Network data structure.

• It is crucial to implement the benchmark entry function in your code. You may replicate this function from existing model files, ensuring to update the class name appropriately to fit your model.

• This project follows PEP 484 type hints. Please make sure all the functions are annotated with type hints and pass the type check. Mypy static type checker is recommended during development process.