Jitter regulation for multiple streams

David Hay and Gabriel Scalosub
European Conference on Algorithms (ESA),
Conferences & Workshops
Resource management, Switch and router design


For widely-used interactive communication, it is essential that traffic is kept as smooth as possible; the smoothness of a traffic is typically captured by its delay jitter, i.e., the difference between the maximal and minimal end-to-end delays. The task of minimizing the jitter is done by jitter regulators that use a limited-size buffer in order to shape the traffic. In many real-life situations regulators must handle multiple streams simultaneously and provide low jitter on each of them separately. This paper investigates the problem of minimizing jitter in such an environment, using a fixed-size buffer.

We show that the offline version of the problem can be solved in polynomial time, by introducing an efficient offline algorithm that finds a release schedule with optimal jitter. When regulating M streams in the online setting, we take a competitive analysis point of view and note that previous results in [1] can be extended to an online algorithm that uses a buffer of size 2MB and obtains the optimal jitter possible with a buffer of size B. The question arises whether such a resource augmentation is essential. We answer this question in the affirmative, by proving a lower bound that is tight up to a factor of 2, thus showing that jitter regulation does not scale well as the number of streams increases unless the buffer is sized-up proportionally.

author = {Hay, David and Scalosub, Gabriel},
title = {Jitter Regulation for Multiple Streams},
year = {2005},
isbn = {3540291180},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
url = {https://doi.org/10.1007/11561071_45},
doi = {10.1007/11561071_45},
booktitle = {Proceedings of the 13th Annual European Conference on Algorithms},
pages = {496–507},
numpages = {12},
location = {Palma de Mallorca, Spain},
series = {ESA’05}