The weighted k-server problem is a generalization of the k-server problem wherein the cost of moving a server of weight A through a distance d is beta(i ). d. On uniform metric spaces, this models caching with caches ...
详细信息
The weighted k-server problem is a generalization of the k-server problem wherein the cost of moving a server of weight A through a distance d is beta(i ). d. On uniform metric spaces, this models caching with caches having different page replacement costs. A memoryless algorithm is an online algorithm whose behavior is independent of the history given the positions of its kservers. In this article, we develop a framework to analyze the competitiveness of randomized memoryless algorithms. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. Using this, we establish tight bounds on the competitive ratio achievable by randomized memoryless algorithms for the weighted k-server problem on uniform metrics. We first prove that there is an alpha(k)-competitive memoryless algorithm for this problem, where alpha(k) = alpha(2)(k-)(1) + 3 alpha(k-1 )+1 alpha(1)= 1. We complement this result by proving that no randomized memoryless algorithm can have a competitive ratio less than alpha(k). Finally, we prove that the above bounds also hold for the generalized k-server problem on weighted uniform metrics.
In this paper, we study a multi-server queuing system wherein each user is constrained to get service only from a specified subset of servers. Fair packet scheduling in such a setting poses novel challenges that we ad...
详细信息
In this paper, we study a multi-server queuing system wherein each user is constrained to get service only from a specified subset of servers. Fair packet scheduling in such a setting poses novel challenges that we address in this paper. Specifically, we observe that max-min fair allocation of the available resource over different servers (notably bandwidth) in the presence of placement constraints results in different levels of fair service-rates. To achieve the max-min fair service rates, we propose a novel packet scheduler which is inspired by the deficit-round robin (DRR) algorithm. The scheduler allocates tokens to flows in a round-by-round manner, where token allocation to flows at the beginning of each round is weighted max-min fair. So, we have called it multi-server max-min fair DRR (MSMF-DRR). The performance of the MSMF-DRR algorithm in terms of achieving fairness is shown through a worst-case performance analysis. In addition to analytical results, numerical experiments are also carried out to illustrate service isolation and the delay guarantee that are provided by the algorithm. Generally, a scheduler for such a constrained multi-server queuing system can be applicable in many modern data-networking applications, especially in cloud computing wherein virtual machines and/or processes vie for different IT resources distributed over heterogenous servers, while different processes may have preferences over servers owing to their quality-of-service requirements and the heterogeneity of servers.
暂无评论