ALCOMFT-TR-01-64

John Garofalakis, Sotiris Nikoletseas and Paul Spirakis
Latency Lower Bounds for Randomized Dynamic Bandwidth Allocation
Patras. Work packages 2 and 4. May 2001.

Abstract: In this work we study the limitations of on-line schemes used to deal with the interplay of latency and utilization parameters in bandwidth allocation for tasks with varying and unpredictable bandwidth demands. We provide tight latency lower bounds to any randomized adaptive bandwidth allocation scheme for a single worst-case input stream of packets (session). We achieve this by employing the min-max principle of Yao and by characterizing the optimal (with respect to average queue size) deterministic scheme, which is subjected to a suitably chosen (``worst case'') random input.

Postscript file: ALCOMFT-TR-01-64.ps.gz (87 kb).