Online Bandwidth Allocation
Online Bandwidth Allocation
复制标题
在线带宽分配
DOI：
10.1007/978-3-540-75520-3_49
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
B. Rovan
中科院分区：
文献类型：
--
作者：
Michal Forisek;Branislav Katreniak;J. Katreniaková;Rastislav Kralovic;Richard Královic;Vladimír Koutný;Dana Pardubská;T. Plachetka;B. Rovan
本文研究了无线网络中出现的资源分配问题的一个版本，即 OVSF 代码重新分配过程。在此设置中，考虑给定高度的完整二叉树，以及必须以在线方式提供服务的请求序列。请求有两种类型：插入请求要求分配给定高度的完整子树，删除请求释放给定分配的子树。为了满足插入请求，可能需要将一些已经分配的子树移动到其他位置，以便释放足够大的子树。我们感兴趣的是服务请求所需的此类重新分配的最坏情况平均数量。在[4]中，作者给出了解决该问题的在线算法的竞争比的界限，并表明该比率在 1.5 和 O(n) 之间。我们通过给出一个 O(1) 竞争性在线算法来部分回答他们关于确切值的问题。在[3]中，作者在内存管理系统的上下文中使用相同的模型，并分析在最坏情况下服务请求所需的重新分配数量。在这种情况下，我们的结果是相应的摊销分析。
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 heightnis 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 [4] the authors delivered bounds on the competitive ratio of online algorithm solving this problem, and showed that the ratio is between 1.5 andO(n). We partially answer their question about the exact value by giving anO(1)-competitive online algorithm.In [3], authors 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.