# Perfectly Periodic Scheduling of Collective Data Streams

Tutkimustuotos: Lehtiartikkeli › › vertaisarvioitu

### Standard

**Perfectly Periodic Scheduling of Collective Data Streams.** / Rottenstreich, Ori; Di Francesco, Mario; Revah, Yoram.

Tutkimustuotos: Lehtiartikkeli › › vertaisarvioitu

### Harvard

*IEEE-ACM TRANSACTIONS ON NETWORKING*, Vuosikerta. 25, Nro 3, Sivut 1332-1346. https://doi.org/10.1109/TNET.2016.2629092

### APA

*IEEE-ACM TRANSACTIONS ON NETWORKING*,

*25*(3), 1332-1346. https://doi.org/10.1109/TNET.2016.2629092

### Vancouver

### Author

### Bibtex - Lataa

}

### RIS - Lataa

TY - JOUR

T1 - Perfectly Periodic Scheduling of Collective Data Streams

AU - Rottenstreich, Ori

AU - Di Francesco, Mario

AU - Revah, Yoram

PY - 2017/6

Y1 - 2017/6

N2 - 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).

AB - 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).

U2 - 10.1109/TNET.2016.2629092

DO - 10.1109/TNET.2016.2629092

M3 - Article

VL - 25

SP - 1332

EP - 1346

JO - IEEE-ACM TRANSACTIONS ON NETWORKING

JF - IEEE-ACM TRANSACTIONS ON NETWORKING

SN - 1063-6692

IS - 3

ER -

ID: 10372315