首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Overlay Networks with Linear Capacity Constraints
【24h】

Overlay Networks with Linear Capacity Constraints

机译:具有线性容量约束的覆盖网络

获取原文
获取原文并翻译 | 示例

摘要

Overlay networks are virtual networks residing overthe IP network, consequently, overlay links may share hiddenl ower-level bottlenecks. Previous work have assumed an independent overlay model: a graph with independent link capacities.We introduce a model of overlays which incorporates correlated link capacities and linear capacity constraints (LCC) to formulate hidden shared bottlenecks; we refer to these as LCC-overlays. We define metrics to qualitatively measure overlay quality in terms of its accuracy (in representing the true network topology) and efficiency (i.e., performance). Through analysis and simulations,we show that LCC-overlay is perfectly accurate and hence enjoys much higher efficiency than the inaccurate independent overlay. We discover that even a highly restricted LCC class u00026;#8212; node basedLCCu00026;#8212; yields near-optimal accuracy and significantly higher efficiency. We study two network flow problems in the context of LCC-graphs: Widest-Path and Maximum-Flow. Weprove that Widest-Path with LCC is NP-complete. We formulate Maximum-Flow with LCC as a linear program, and propose an efficient distributed algorithm to solve it. Based on the LCCmodel, we further study the problem of optimizing delay while still maintaining optimal or near-optimal bandwidth. We also outline a distributed algorithm to efficiently construct an overlay with node-based LCC.
机译:覆盖网络是驻留在IP网络上的虚拟网络,因此,覆盖链接可能会共享隐藏的下层瓶颈。先前的工作假设了一个独立的覆盖模型:一个具有独立链接容量的图。我们介绍了一个覆盖模型,该模型结合了相关的链接容量和线性容量约束(LCC)来表达隐藏的共享瓶颈;我们将其称为LCC叠加。我们定义了度量标准,以根据其准确性(代表真实的网络拓扑)和效率(即性能)来定性地测量覆盖质量。通过分析和仿真,我们显示LCC叠加是非常准确的,因此比不准确的独立叠加具有更高的效率。我们发现,即使是严格限制的LCC类u00026;#8212;基于节点的LCCu00026;#8212;产生接近最佳的精度和明显更高的效率。我们在LCC图的背景下研究了两个网络流量问题:最宽路径和最大流量。我们证明带有LCC的最宽路径是NP完整的。我们以LCC作为线性程序制定了最大流量,并提出了一种有效的分布式算法来解决它。基于LCC模型,我们进一步研究了优化延迟同时仍保持最佳或接近最佳带宽的问题。我们还将概述一种分布式算法,以有效地构建基于节点的LCC的覆盖。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号