• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Experimental and Efficient Algorithms(WEA 2005); 20050510-13; Santorini Island(GR) >The Necessity of Timekeeping in Adversarial Queueing
【24h】

The Necessity of Timekeeping in Adversarial Queueing

机译：对抗性排队中计时的必要性

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

摘要

We study queueing strategies in the adversarial queueing model. Rather than discussing individual prominent queueing strategies we tackle the issue on a general level and analyze classes of queueing strategies. We introduce the class of queueing strategies that base their preferences on knowledge of the entire graph, the path of the packet and its progress. This restriction only rules out time keeping information like a packet's age or its current waiting time. We show that all strategies without time stamping have exponential queue sizes, suggesting that time keeping is necessary to obtain subex-ponential performance bounds. We further introduce a new method to prove stability for strategies without time stamping and show how it can be used to completely characterize a large class of strategies as to their 1-stability and universal stability.
机译：我们研究对抗性排队模型中的排队策略。与其讨论个别的重要排队策略，不如从总体上解决该问题并分析排队策略的类别。我们介绍了排队策略的类别，这些策略基于对整个图的了解，数据包的路径及其进展情况来确定其偏好。该限制仅排除了诸如包的期限或当前等待时间之类的时间保持信息。我们表明，所有没有时间戳的策略都具有指数队列大小，这表明保持时间对于获得次指数性能界限是必要的。我们进一步介绍了一种新的方法来证明策略的稳定性而没有时间戳，并说明如何使用它来完全表征一大类策略的一阶稳定性和通用稳定性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号