• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Multicast Routing with Delay and Delay Variation Constraints for Collaborative Applications on Overlay Networks
【24h】

Multicast Routing with Delay and Delay Variation Constraints for Collaborative Applications on Overlay Networks

机译：具有延迟和时延变化约束的组播路由，用于重叠网络上的协作应用

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

摘要

Computer supported collaborative applications on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include video-conferencing, distributed database replication, and online games. This type of application requires a multicasting subnetwork, using which messages should arrive at the destinations within a specified delay bound. These applications also require that destinations receive the message from the source at approximately the same time. The problem of finding a multicasting subnetwork with delay and delay-variation bound has been proved to be an NP Complete problem in the literature and heuristics have been proposed for this problem. In this paper, we provide an efficient heuristic to obtain a multicast subnetwork on an overlay network, given a source and a set of destinations that is within a specified maximum delay and a specified maximum variation in the delays from a source to the destinations. The time-complexity of our algorithm is O(|E| + nk log(|E|) + m^{2}k), where n and |E| are the number of nodes and edges in the network, respectively, k is the number of shortest paths determined, and m is the number of destinations. We have shown that our algorithm is significantly better in terms of time-complexity than existing algorithms for the same problem. Our extensive empirical studies indicate that our heuristic uses significantly less runtime in comparison with the best-known heuristics while achieving the tightest delay variation for a given end-to-end delay bound.
机译：覆盖网络上的计算机支持的协作应用程序在地理位置分散的用户中越来越受欢迎。这些类型的应用程序的示例包括视频会议，分布式数据库复制和在线游戏。这种类型的应用程序需要多播子网，通过该子网，消息应在指定的延迟范围内到达目的地。这些应用程序还要求目标大约在同一时间从源接收消息。在文献中，找到具有时延和时延-变异边界的多播子网的问题已被证明是NP完全问题，并且针对该问题提出了启发式方法。在本文中，我们提供了一种有效的启发式方法，可在给定源和一组目标在指定的最大延迟内以及从源到目标的延迟的指定最大变化范围内的情况下，在覆盖网络上获取多播子网。我们算法的时间复杂度为O（| E | + nk log（| E | / n）+ m ^ {2} k），其中n和| E |是网络中节点和边缘的数量，k是确定的最短路径的数量，m是目的地的数量。我们已经表明，对于相同的问题，我们的算法在时间复杂度方面明显优于现有算法。我们广泛的经验研究表明，与最著名的启发式算法相比，我们的启发式算法使用的运行时间明显更少，同时在给定的端到端延迟范围内实现了最严格的延迟变化。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号