• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Trade-Offs between Stretch Factor and Load-Balancing Ratio in Routing on Growth-Restricted Graphs
【24h】

Trade-Offs between Stretch Factor and Load-Balancing Ratio in Routing on Growth-Restricted Graphs

机译：增长受限图上路由中拉伸因子与负载均衡比之间的权衡

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

摘要

An unweighted graph has density rho and growth rate k if the number of nodes in every ball with radius r is bounded by rhork. The communication graphs of wireless networks and peer-to-peer networks often have constant bounded density and small growth rate. In this paper, we study the trade-off between two quality measures for routing in growth-restricted graphs. The two measures we consider are the stretch factor, which measures the lengths of the routing paths, and the load-balancing ratio, which measures the evenness of the traffic distribution. We show that if the routing algorithm is required to use paths with stretch factor c, then its load-balancing ratio is bounded by O(rho1/k(n/c)1-1/k), and the bound is tight in the worst case. We show the application and extension of the trade-off to the wireless network routing and VLSI layout design. We also present a load-balanced routing algorithm with the stretch factor constraint in an online setting, in which the routing requests come one by one.
机译：如果半径为r的每个球中的结点数受rhork限制，则未加权图的密度为rho，增长率为k。无线网络和对等网络的通信图通常具有恒定的有界密度和较小的增长率。在本文中，我们研究了增长受限图中用于路由的两种质量度量之间的权衡。我们考虑的两个度量是拉伸因子（用来衡量路由路径的长度）和负载均衡比（用来衡量流量分布的均匀性）。我们表明，如果要求路由算法使用拉伸因子为c的路径，则其负载均衡比以O（rho1 / k（n / c）1-1 / k）为边界，并且边界在最坏的情况下。我们展示了权衡在无线网络路由和VLSI布局设计中的应用和扩展。我们还提出了一种在在线设置中具有拉伸因子约束的负载均衡路由算法，其中路由请求是一个接一个地发送的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号