基于空闲容量分配的路由算法研究

摘要

通信网络技术的蓬勃发展和数字技术的全面采用，推动着向下一代宽带综合网络的发展。目前通信网络已成为现代信息社会最重要的基础设施。主干网络达到了每秒几十个吉比特的速度，带宽瓶颈已得到了很大的缓解，已有能力提供综合业务，即不仅仅限于数据，还包括语音、视频等的传送。在这样一种高速、多业务的网络中出现任何故障都会造成巨大的影响和损失，因此，当前对于网络生存性的研究较之传统网络更加迫切。网络良好的生存性关乎两个重要的方面：生存性策略的实施和空闲容量的分配。正是基于此，本文将针对空闲容量分配问题进行研究。 本文首先介绍空闲容量分配(SCA，SpareCapacityAllocation)的研究现状及意义；比较全面地介绍网络生存性概念和生存性技术;给出故障的恢复过程，为不同的恢复方法进行分类，对预留和动态分配资源做简单分析；分析讨论路由保护方法的故障关联，并解决陷阱拓扑问题。然后，介绍几种比较成熟的SCA算法并给出分别适用于单链路故障和任意故障的SCA模型。最后提出连续可存活路由(SSR，SuccessiveSurvivableRouting)算法，针对链路失效情况，对SSR算法和其它算法进行仿真并对性能进行比较。结果表明：SSR算法是一种能很好解决空闲容量分配问题的近似算法，可以获得近似最优的冗余度和快速的计算时间。

目录

文摘

英文文摘

论文说明：缩略语

声明

第一章绪论

1.1空闲容量分配的研究现状及意义

1.2本文主要工作

1.3论文组织结构

第二章网络生存性技术

2.1生存性概念

2.2生存性技术

2.3故障的恢复过程

2.3.1故障的分类

2.3.2故障检测、故障定位和故障通知

2.3.3故障恢复策略-保护和恢复

2.4预留和动态分配资源

2.5路由保护方法的故障关联

2.6本章小结

第三章空闲容量分配算法的分析

3.1问题描述

3.2网络设计问题

3.3算法复杂度

3.3.1算法复杂度

3.3.2多项式界问题

3.3.3 NPC问题

3.4算法介绍

3.4.1 BB算法

3.4.2 SA算法

3.4.3 GA算法

3.4.4 TS算法

3.4.5 SPI算法

3.5小结

第四章SCA模型

4.1 SCA模型的分类

4.2适用于单链路故障的SCA模型

4.2.1相关术语(符号)定义

4.2.2公式描述

4.2.3空闲预备矩阵

4.3适用于任意故障的SCA模型

4.3.1相关术语(符号)定义

4.3.2公式描述

第五章SSR算法研究

5.1 SSR算法的理论基础

5.2 SSR算法流程

5.3寻找备份路径

5.4空闲预备矩阵的同步

5.4.1更新G的两种方式

5.4.2讨论分析

5.5结论

第六章针对链路失效的SSR算法仿真及其比较

6.1概述

6.2仿真系统介绍

6.2.1 MATLAB的优点

6.2.2 MATLAB的缺点

6.3实验设计和仿真结果

6.3.1网络负载实验

6.3.2拓扑结构对冗余度的影响

6.4 SSR与RAFT的性能比较

6.5分析和结论

6.6本章小结

第七章结论

7.1论文总结

7.2今后的研究方向

致谢

参考文献

攻读硕士期间发表和录用的论文