• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Hardness of Low Delay Network Scheduling
【24h】

Hardness of Low Delay Network Scheduling

机译：低延迟网络调度的难度

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

摘要

We consider a communication network and study the problem of designing a high-throughput and low-delay scheduling policy that only requires a polynomial amount of computation at each time step. The well-known maximum weight scheduling policy, proposed by Tassiulas and Ephremides (1992), has favorable performance in terms of throughput and delay but, for general networks, it can be computationally very expensive. A related randomized policy proposed by Tassiulas (1998) provides maximal throughput with only a small amount of computation per step, but seems to induce exponentially large average delay. These considerations raise some natural questions. Is it possible to design a policy with low complexity, high throughput, and low delay for a general network? Does Tassiulas' randomized policy result in low average delay? In this paper, we answer both of these questions negatively. We consider a wireless network operating under two alternative interference models: (a) a combinatorial model involving independent set constraints and (b) the standard SINR (signal to interference noise ratio) model. We show that unless ${bf NP}subseteq {bf BPP}$ (or ${bf P} ={bf NP}$ for the case of determistic arrivals and deterministic policies), and even if the required throughput is a very small fraction of the network's capacity, there does not exist a low-delay policy whose computation per time step scales polynomially with the number of queues. In particular, the average delay of Tassiulas' randomized algorithm must grow super-polynomially. To establish our results, we employ a clever graph transformation introduced by Lund and Yannakakis (1994).
机译：我们考虑一个通信网络，并研究设计高吞吐量和低延迟的调度策略的问题，该策略在每个时间步仅需要多项式的计算量。 Tassiulas和Ephremides（1992）提出的众所周知的最大权重调度策略在吞吐量和延迟方面具有良好的性能，但是对于一般网络而言，它的计算成本非常高。 Tassiulas（1998）提出的相关随机策略提供了最大吞吐量，每步仅需少量计算，但似乎会导致指数级的平均延迟。这些考虑提出了一些自然的问题。对于一般网络，是否可以设计具有低复杂度，高吞吐量和低延迟的策略？ Tassiulas的随机政策是否会导致平均延迟较低？在本文中，我们否定地回答了这两个问题。我们考虑一种在两种备选干扰模型下运行的无线网络：（a）涉及独立集合约束的组合模型，以及（b）标准SINR（信噪比）模型。我们表明，除非$ {bf NP} subseteq {bf BPP} $（或确定性到达和确定性策略的情况下$ {bf P} = {bf NP} $），即使所需的吞吐量很小在网络容量方面，不存在低延迟策略，该策略的每个时间步长的计算随队列数量成倍增长。特别是，Tassiulas随机算法的平均延迟必须以超多项式增长。为了建立我们的结果，我们采用了隆德和亚纳卡基斯（1994）引入的聪明的图变换。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号