Article in Proceedings INPROC-2016-32

BibliographyDü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.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology.
pp. 1-10, english.
Brest, France: ACM, October 19, 2016.
Article in Proceedings (Conference Paper).
CR-SchemaC.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
Abstract

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%.

Full text and
other 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. http://dx.doi.org/10.1145/2997465.2997494
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Entry dateSeptember 23, 2016
   Publ. Department   Publ. Institute   Publ. Computer Science