• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Heterogeneous Resource Allocation under Degree Constraints
【24h】

Heterogeneous Resource Allocation under Degree Constraints

机译：度约束下的异构资源分配

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we consider the problem of assigning a set of clients with demands to a set of servers with capacities and degree constraints. The goal is to find an allocation such that the number of clients assigned to a server is smaller than the server's degree and their overall demand is smaller than the server's capacity, while maximizing the overall throughput. This problem has several natural applications in the context of independent tasks scheduling or virtual machines allocation. We consider both the offline (when clients are known beforehand) and the online (when clients can join and leave the system at any time) versions of the problem. We first show that the degree constraint on the maximal number of clients that a server can handle is realistic in many contexts. Then, our main contribution is to prove that even if it makes the allocation problem more difficult (NP-Complete), a very small additive resource augmentation on the servers degree is enough to find in polynomial time a solution that achieves at least the optimal throughput. After a set of theoretical results on the complexity of the offline and online versions of the problem, we propose several other greedy heuristics to solve the online problem and we compare the performance (in terms of throughput) and the cost (in terms of disconnections and reconnections) of all proposed algorithms through a set of extensive simulation results.
机译：在本文中，我们考虑将具有需求的一组客户端分配给具有容量和程度约束的一组服务器的问题。目的是找到一种分配，以使分配给服务器的客户端数量小于服务器的程度，并且其总体需求小于服务器的容量，同时最大程度地提高总体吞吐量。在独立任务调度或虚拟机分配的情况下，此问题具有多种自然应用。我们考虑问题的脱机版本（事先知道客户端）和在线版本（当客户端可以随时加入和离开系统）。我们首先显示，在许多情况下，服务器可以处理的最大客户端数量上的度数约束是现实的。然后，我们的主要贡献是证明，即使这使分配问题变得更加困难（NP完全），服务器度上很小的附加资源增量也足以在多项式时间内找到至少达到最佳吞吐量的解决方案。 。在获得有关离线和在线版本问题的复杂性的一组理论结果之后，我们提出了其他几种贪婪启发式方法来解决在线问题，并比较了性能（就吞吐量而言）和成本（就断开连接和一组广泛的仿真结果，对所有提议的算法进行重新连接）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号