Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming

doi:10.1109/ACCESS.2024.3440828

Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming

2024-01-01

0

OA

AI

A

Alitzel Galilea Torres-Macías *

Antonio Ramírez‐Treviño

H

Héctor Blanco-Alcaine

DOI：10.1109/ACCESS.2024.3440828

Original

Original request for help

Save

Abstract

En 中文

Time-Sensitive Networking (TSN) is an in-development technology that enables predictability over Ethernet or wireless networks. Network interfaces compliant with the IEEE 802.1Qbv standard provide different queues/gates on each bridge egress port. In this way, a global network schedule can be set by defining the opening and closing times (Gate Control List, GCL) for each gate. In this paper, we propose a new method to schedule GCLs by dividing the problem into several subproblems. We use Weighted Fair Queuing (WFQ) to set the ordering of frames, and then generate an Integer Linear Programming (ILP) model to optimize the TSN scenario. Next, we assign gates to the scheduled windows, trying to ensure frame isolation whenever possible. Our results show that we can schedule GCLs around 2 times faster than previous studies and up to 5.5 orders of magnitude faster if we choose to obtain any valid solution instead of the optimal one. In addition, we are able to schedule systems with utilization up to 85%, whereas previous papers reach 65%. Moreover, our approach does not need to predefine the number of windows or gates, as required by other methods.

Keywords:

Streams

Scheduling

Logic gates

Peer-to-peer computing

Bridges

Job shop scheduling

Jitter

Sensitivity analysis

802.1Qbv

delay

GCL

ILP

jitter

real-time

scheduling

TAS

time-sensitive networking

TSN

Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming

Abstract

Journal

Organization