tsnkit

A simple scheduling toolkit and benchmark for Time-Sensitive Networking in Python.

@article{xue2023real,
  title={Real-Time Scheduling for Time-Sensitive Networking: A Systematic Review and Experimental Study},
  author={Xue, Chuanyu and Zhang, Tianyu and Zhou, Yuanbin and Han, Song},
  journal={arXiv preprint arXiv:2305.16772},
  year={2023}
}

Paper link: https://arxiv.org/abs/2305.16772

Documentation (work-in-progress): https://tsnkit.readthedocs.io

Install

Install from source (recommended):

git clone https://github.com/ChuanyuXue/tsnkit
cd tsnkit
python setup.py install

From pip:

pip install -U tsnkit

Usage

Testing:

python3 -m tsnkit.models.[METHOD] [STREAM PATH] [NETWORK PATH]

Reproducing benchmark paper results:

Check out to legacy branch.
Download data.gz from git-lfs, and unzip it to data folder. (Or generate it using data/input/generate_data.ipynb)
Go src foder and run python main.py --method=ALL --start=0 --end=38400.

Both main and legacy branches use the same logic (models & algorithms). However, we have refined the organization in the main branch by introducing a unified interface and standardized type notation to enhance maintainability and simplify the efforts to add new methods. The legacy branch houses the source code record used in the paper.

Code structure:

src/tsnkit/models: Inplementations of all supported scheduling methods.
src/tsnkit/simulation: TSN simulator to validate the scheduling output.
src/tsnkit/utils: Data structures and helper functions.
src/notebooks : A step-by-step implementation tutorial transitioning from paper to source code.

Supported methods:

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 Trafﬁc Planning for Data Networks with Conﬂict 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

IO format

All algorithm input and output are defined in csv format.

Input:

Follwing are the stream set and network descrption files as algorithm input.

Stream set format:

id	src	dst	size	period	deadline	jitter
0	0	[7,8,9]	50	100000	44600	0

id: Unique ID for each flow
src: Talker that the end-system where flow starts at.
dst: Listener that the the end-system where flow ends at, formatted as list for multicast
size: Packet size of each flow in Bytes.
period: Flow periods in Nanoseconds.
deadline: Relative flow deadline requirement in Nanoseconds.
jitter: Maximum end-to-end delay variance requirement in Nanoseconds.

Network for mat:

link	q_num	rate	t_proc	t_prop
(0, 1)	8	1	1000	0

link: Directional link connects two devices.
q_num: Number of available queues for time-triggered (critical) traffic.
rate: Bandwidth of link in bit / nanosecond, e.g., 1 = 1 Gbps, 0.1 = 100 Mbps, 0.01 = 10 Mbps.
t_proc: Processing time including switching fabric and ingress processing.
t_prop: Propogation delay on wire after transmission.

Output

Following are the output files (gcl, offset, route, queuing assignment) from the algorithm, which can be fed into the TSN simulator or testbed.

GCL:

link	queue	start	end	cycle
(0, 1)	0	1000	5000	12000000

queue: Indicator implies which queue is open between start and end time.
start: Relative time when queue opens in hyper period.
end: Relative time when queue opens in hyper period.
cycle: Cycle time of GCL.

Offset:

stream	frame	offset
0	0	1000

stream: Unique ID for each stream.
frame: The index of corresponding flow instance
offset: The traffic dispatching time on end-system for corresponding flow instance

Route:

stream	link
0	(8,1)
0	(1,2)
0	(2,3)

link: Directional link connects two devices.

Queueing assignment:

id	frame	link	queue
0	0	(8,1)	2

link: Directional link connects two devices.
queue: The egress queue for corresponding flow instance on corresponding link.

Contribute

Contributions are welcome! Feel free to add your own scheduling algorithm in this toolkit. And contact me to update your new scheduling method into our benchmark paper!

Refer to src/tsnkit/models/__init__.py to implement the required interface and benchmark entrance.

yh1198015532/tsnkit