• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Spare capacity allocation: Model, analysis and algorithm.
【24h】

Spare capacity allocation: Model, analysis and algorithm.

机译：备用容量分配：模型，分析和算法。

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

摘要

Network survivability technique is a countermeasure to the vulnerability of communication networks in the face of failures and malicious attacks. With the expansion of network capacity and increasing concentration of services in backbone networks, reducing response time and improving cost efficiency to provide survivable network services become increasingly important.; In this dissertation, I study a critical component of network survivability technique, i.e. spare capacity allocation (SCA) problem on mesh networks. The SCA problem is to decide how much spare capacity should be reserved on links and where to pre-plan backup paths to protect traffic from a set of failures.; I formulate the SCA problem using a novel matrix-based network flow model. I provide bounds on the network redundancy of this NP-complete optimization problem. I develop an approximation algorithm called successive survivable routing (SSR). Compared with other algorithms in numerical results, SSR achieves a very good trade-off between near-optimality and computational speed. Moreover, the matrix model and SSR algorithm are extended to the cases of different path restoration schemes, arbitrary failure scenarios, and objectives with non-linear link costs.; Another contribution of this dissertation is to extend the above model to topology layout and spare capacity design in multi-layer networks. To make an upper layer network resilient from a set of lower layer failures, I use a matrix-based layout model to find an optimal topology. Such solution is then used in the matrix-based SCA formulations and the SSR algorithm for multi-layer networks is developed. Applications in fault-tolerant virtual private network (VPN) design are provided.; I also propose two alternative SCA algorithms. One is to randomly scale the path sets for the branch and bound algorithm and the other is a simulated annealing algorithm. Both of them take longer execution time than SSR but also find near optimal solutions.; In short, I give a two-pronged attack to SCA problem—a matrix-based model to disclose the problem structure, and a routing-based algorithm to find near-optimal solutions. These results are further extended to multi-layer survivability problems with important applications.
机译：网络生存能力技术是面对故障和恶意攻击时通信网络脆弱性的对策。随着网络容量的扩展和骨干网络中服务的日益集中，减少响应时间并提高成本效率以提供可生存的网络服务变得越来越重要。在本文中，我研究了网络生存能力技术的关键组成部分，即网状网络上的备用容量分配（SCA）问题。 SCA问题是决定应在链路上保留多少备用容量，以及在何处预先计划备份路径以保护流量免受一系列故障的影响。我使用基于矩阵的新型网络流量模型来制定SCA问题。我提供了这个NP完全优化问题的网络冗余范围。我开发了一种称为连续生存路由（SSR）的近似算法。与其他算法相比，SSR在接近最优性和计算速度之间取得了很好的折衷。此外，矩阵模型和SSR算法可扩展到具有不同路径恢复方案，任意故障场景和具有非线性链接成本的目标的情况。本文的另一个贡献是将上述模型扩展到多层网络中的拓扑布局和备用容量设计。为了使上层网络能够抵抗一系列下层故障，我使用基于矩阵的布局模型来找到最佳拓扑。然后，将这种解决方案用于基于矩阵的SCA公式中，并开发了用于多层网络的SSR算法。提供了在容错虚拟专用网（VPN）设计中的应用程序。我还提出了两种替代SCA算法。一种是随机缩放分支定界算法的路径集，另一种是模拟退火算法。它们都比SSR花费更长的执行时间，但也找到了接近最优的解决方案。简而言之，我对SCA问题进行了两方面的攻击：一种基于矩阵的模型来揭示问题的结构，而另一种是基于路由的算法来寻找近乎最优的解决方案。这些结果进一步扩展到具有重要应用程序的多层生存性问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号