Artikel in Tagungsband INPROC-2016-32

Dürr, Frank; Nayak, Naresh Ganesh: No-wait Packet Scheduling for IEEE Time-sensitive Networks (TSN).
In: 24th International Conference on Real-Time Networks and Systems, RTNS-2016.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik.
S. 1-10, englisch.
Brest, France: ACM, 19. Oktober 2016.
Artikel in Tagungsband (Konferenz-Beitrag).
CR-Klassif.C.2.1 (Network Architecture and Design)
C.2.3 (Network Operations)
KeywordsTime-sensitive network, TSN, Real-time communication, Job shop scheduling problem, Tabu search, IEEE 802.1Qbv

The IEEE Time-sensitive Networking (TSN) Task Group has recently standardized enhancements for IEEE 802.3 networks for enabling it to transport time-triggered traffic (aka scheduled traffic) providing them with stringent bounds on network delay and jitter while also transporting best-effort traffic. These enhancements primarily include dedicating one queue per port of the switch for scheduled traffic along with a programmable gating mechanism that dictates which of the queues are to be considered for transmission. While the IEEE 802.1Qbv standards define these mechanisms to handle scheduled traffic, it stops short of specifying algorithms to compute fine-grained link schedules for the streams of scheduled traffic. Further, the mechanisms in TSN require creation of so-called guard bands to isolate scheduled traffic from the best-effort traffic. These guard bands may potentially result in bandwidth wastage, and hence schedules with lower number of guard bands are preferred. In this paper, we introduce the No-wait Packet Scheduling Problem (NWPSP) for modelling the scheduling in IEEE Time-sensitive Networks and map it to the No-wait Job-shop Scheduling Problem (NW-JSP), a well-known problem from the field of operational research. In particular, we present a Tabu search algorithm for efficient computing of schedules and a schedule compression technique to reduce number of guard bands in schedule. Our evaluations show that our Tabu search algorithm can compute near-optimal schedules for over 1500 flows and the subsequent schedule compression reduces the number of guard bands on an average by 24%.

Volltext und
andere Links
PDF (605414 Bytes)
Copyright© ACM, 2016. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in proceedings of 24th International Conference on Real-Time Networks and Systems, Brest, France, 19-21 October 2016.
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
Eingabedatum23. September 2016
   Publ. Abteilung   Publ. Institut   Publ. Informatik