Load Balancing in the Internet with Strict Delay Constraints

We study the problem of routing traffic in the Internet with strict delay constraints. This problem arises in the context of routing delay-sensitive traffic such as Voice-over-IP. We consider a set of demands that can be routed along a candidate set of paths. Each demand must be split among its paths in such a way that the total delay experienced by any of the traffic is less than a fixed threshold. In this paper we analyze the complexity of the problem and also present experimental results for heuristics that can be implemented in practice. In contrast to some other recent work on network optimization, our problem has a combinatorial aspect since we only enforce the delay bound on paths that have non-zero traffic. Our main theoretical result is that this causes the problem to be computationally hard, even if we only wish to approximately meet the delay bounds. We also discuss the limitations of online algorithms.