Perfectly Periodic Scheduling of Collective Data Streams

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Tutkijat

Organisaatiot

  • Princeton University
  • MARVELL

Kuvaus

This paper addresses the problem of scheduling a single resource to handle requests for time-sensitive periodic services (i.e., data streams) jointly realizing a distributed application. We specifically consider the case, where the demand of each data stream is expressed as a weight relative to a network-wide cyclic schedule. Within this context, we consider the problem of minimizing the schedule length while satisfying the perfect periodicity constraints: the service intervals for the same data stream are fixed and each data stream is cyclically served exactly as many times as its demand. This problem is challenging, as serving a data stream in one time slot might enforce serving it at some specific time slots in the future. As a result, most of the existing solutions have relaxed either the periodicity or the demand constraints of the data streams. In contrast, we study the strict enforcement of both requirements through perfectly periodic schedules. We show that the considered problem is NP-hard and address special cases for which optimal schedules can be derived. We further discuss the more generic instance of the problem represented by an arbitrary number of data streams and demands. Specifically, we provide an approximation algorithm and an efficient greedy solution for such a general case of arbitrary weights. We conduct extensive simulations to evaluate the performance of the proposed solutions. Finally, we show that it is possible to relax the input demands to improve the communication performance at the cost of some other overhead (e.g., in terms of energy consumption).

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut1332-1346
Sivumäärä15
JulkaisuIEEE-ACM TRANSACTIONS ON NETWORKING
Vuosikerta25
Numero3
TilaJulkaistu - kesäkuuta 2017
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

ID: 10372315