TY - GEN

T1 - Approximation algorithms for time-constrained scheduling on line networks

AU - Räcke, Harald

AU - Rosén, Adi

PY - 2009

Y1 - 2009

N2 - We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is to maximize the number of packets that arrive to their destinations by their respective deadlines, given the network constraints. We consider the line network, and a setting where each node has a buffer of size B packets (where B can be finite or infinite), and each edge has capacity C ≥ 1. To the best of our knowledge this is the first work to study time-constrained scheduling in a setting when buffers can be of limited size. We give approximation algorithms that achieve (expected) approximation ratio of O(max{log* n - log* B, 1} + max{log* Σ - log* C, 1}), where n is the length of the line, and Σ is the maximum slack a message can have (the slack is the number of time steps a message can be idle and still arrive within its deadline). A special case of our setting is the setting of buffers of unlimited capacity and edge capacities 1, which has been previously studied by Adler et al. [2]. For this case our results considerably improve upon previous results: Via a slight modification of our algorithms we also obtain an approximation ratio of O(min{log* n; log* Σ; log* M}) (where M is the number of messages in the instance), which is a significant improvement upon the results of Adler et al.

AB - We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is to maximize the number of packets that arrive to their destinations by their respective deadlines, given the network constraints. We consider the line network, and a setting where each node has a buffer of size B packets (where B can be finite or infinite), and each edge has capacity C ≥ 1. To the best of our knowledge this is the first work to study time-constrained scheduling in a setting when buffers can be of limited size. We give approximation algorithms that achieve (expected) approximation ratio of O(max{log* n - log* B, 1} + max{log* Σ - log* C, 1}), where n is the length of the line, and Σ is the maximum slack a message can have (the slack is the number of time steps a message can be idle and still arrive within its deadline). A special case of our setting is the setting of buffers of unlimited capacity and edge capacities 1, which has been previously studied by Adler et al. [2]. For this case our results considerably improve upon previous results: Via a slight modification of our algorithms we also obtain an approximation ratio of O(min{log* n; log* Σ; log* M}) (where M is the number of messages in the instance), which is a significant improvement upon the results of Adler et al.

KW - Approximation algorithms

KW - Line networks

KW - Packet scheduling

KW - Time constraints

UR - http://www.scopus.com/inward/record.url?scp=70449652345&partnerID=8YFLogxK

U2 - 10.1145/1583991.1584071

DO - 10.1145/1583991.1584071

M3 - Conference contribution

AN - SCOPUS:70449652345

SN - 9781605586069

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 337

EP - 346

BT - SPAA'09 - Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery (ACM)

T2 - 21st Annual Symposium on Parallelism in Algorithms and Architectures, SPAA'09

Y2 - 11 August 2009 through 13 August 2009

ER -