...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>電子情報通信学会技術研究報告. コンピュテ-ション. Theoretical Foundations of Computing >On the Competitive Analysis of Stream Merging Algorithms for Video-on-Demand
【24h】

On the Competitive Analysis of Stream Merging Algorithms for Video-on-Demand

机译：视频点播流合并算法的竞争分析

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

摘要

A video-on-demand (VoD) is a system in which each client requests to receive a hot video and the video server immediately responds its request. In VoD system, bandwidth requirement is one of the most important measures, e.g., the maximum bandwidth and the total bandwidth, and it is known that online stream merging can reduce the bandwidth requirement. Recently, Chan et al. proposed the modified greedy algorithm MGRD{sub}λ with catch-up parameterλ≥1 and showed that for any integerλ≥1, it is (2+ε)-competitive w.r.t. the maximum bandwidth and is 2.5-competitive w.r.t. the total bandwidth. In this paper, we precisely analyze the competitive ratio of the modified greedy algorithm MGRD{sub}λ, and show that w.r.t. the maximum bandwidth, (1) the competitive ratio of the algorithm MGRD{sub}λ is at most 2 for any integerλ≥1; (2) the competitive ratio of the algorithm MGRD{sub}λ is at least 2 for any integerλ≥1; and that w.r.t. the total bandwidth, (3) the competitive ratio of the algorithm MGRD{sub}λ is at most 2 for any integerλ≥2; (4) the competitive ratio of the algorithm MGRD{sub}λ is at least (5λ+4)/(3λ+3)≥1.5 for any integer λ≥1.
机译：视频点播（VoD）是一种系统，其中每个客户端都请求接收热视频，而视频服务器立即响应其请求。在VoD系统中，带宽需求是最重要的措施之一，例如最大带宽和总带宽，并且已知在线流合并可以减少带宽需求。最近，Chan等。提出了一种改进的贪婪算法MGRD {sub}λ，其追赶参数λ≥1，并表明对于任何λ≥1的整数，它的竞争性为（2 +ε）。最大带宽，并且是2.5竞争w.r.t.总带宽。在本文中，我们精确分析了改进的贪婪算法MGRD {sub}λ的竞争比，并证明了最大带宽，（1）对于任何≥1的整数，算法MGRD {sub}λ的竞争比最大为2; （2）对于任何大于等于1的整数，算法MGRD {sub}λ的竞争比至少为2;还有那个总带宽，（3）对于任何≥2的整数，算法MGRD {sub}λ的竞争比最大为2; （4）对于任何整数λ≥1，算法MGRD {sub}λ的竞争比至少为（5λ+ 4）/（3λ+ 3）≥1.5。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号