×

Online bandwidth allocation. (English) Zbl 1151.90344

Arge, Lars (ed.) et al., Algorithms – ESA 2007. 15th annual European symposium, Eilat, Israel, October 8–10, 2007, Proceedings. Berlin: Springer (ISBN 978-3-540-75519-7/pbk). Lecture Notes in Computer Science 4698, 546-557 (2007).
Summary: The paper investigates a version of the resource allocation problem arising in the wireless networking, namely in the OVSF code reallocation process. In this setting a complete binary tree of a given height \(n\) is considered, together with a sequence of requests which have to be served in an online manner. The requests are of two types: an insertion request requires to allocate a complete subtree of a given height, and a deletion request frees a given allocated subtree. In order to serve an insertion request it might be necessary to move some already allocated subtrees to other locations in order to free a large enough subtree. We are interested in the worst case average number of such reallocations needed to serve a request.
In [“An algorithmic view on OVSF code assignment”, Lect. Notes Comput. Sci. 2996, 270–281 (2004; Zbl 1122.68457)], T. Erlebach et al. delivered bounds on the competitive ratio of online algorithm solving this problem, and showed that the ratio is between 1.5 and \(O(n)\). We partially answer their question about the exact value by giving an \(O(1)\)-competitive online algorithm.
In [“Upper bound for defragmenting buddy heaps”, in: Proc. 2005 ACM SIGPLAN/SIGBED conference on languages, compilers, and tools for embedded systems, LCTES’05, 222–229 (2005)], D. C. Defoe et al. use the same model in the context of memory management systems, and analyze the number of reallocations needed to serve a request in the worst case. In this setting, our result is a corresponding amortized analysis.
For the entire collection see [Zbl 1130.68001].

MSC:

90B18 Communication networks in operations research
68Q25 Analysis of algorithms and problem complexity
68W40 Analysis of algorithms

Citations:

Zbl 1122.68457
PDFBibTeX XMLCite
Full Text: DOI