Internet域间路由稳定性研究

论文题目: Internet域间路由稳定性研究

论文类型: 博士论文

论文专业: 计算机科学与技术

作者: 朱珂

导师: 卢锡城

关键词: 计算机网络,边界网关协议,策略,路由振荡,收敛延迟,路径增长,安全多方计算仿真

文献来源: 国防科学技术大学

发表年度: 2005

论文摘要: BGP协议是Internet域间路由协议的事实标准。BGP协议允许自治系统(Autonomous System, AS)管理员制定任意复杂的管理策略，每个自治系统都可以根据路由策略独立决定如何选择使用来自其他自治系统的路由信息，以实现各自的商业目标。由于当前的Internet正逐步演化为具有商业意义的公共电信基础设施，因此BGP协议也日益凸现其重要作用与意义。 作为Internet控制平面的核心协议，BGP协议直接影响域间路由的稳定性和效率。本文致力于BGP策略配置带来的域内路由振荡、慢收敛、路径增长以及域间路由振荡等域间路由稳定性问题的研究，取得了以下的研究成果： 1．解决了BGP域内路由震荡问题。多出口鉴别(Multi-Exit-Discriminator, MED)是BGP路由的一个非负整数属性值，当比较两个来自同一个自治系统AS的路由信息时，MED值小的优先。由于来自不同AS的路由信息其MED值不具有可比性，因此在路由比较过程中会造成某些路由信息不可见，从而导致BGP域内路由震荡。本文利用D-SPP模型分析域内路由震荡的深层数学原理，并基于该原理分析已有的解决算法，发行其中的不足，并据此提出了基于消除秩函数时变性的改进算法，更高效的解决了域内路由振荡问题。 2．加快BGP收敛速度。当网络拓扑或自治系统策略发生变化时，运行BGP的路由器经常需要很长一段时间来完成收敛过程。由于收敛延迟将直接导致报文转发延迟甚至丢失，对于当前Internet的高性能服务和QoS需求，加快BGP收敛速度将起到至关重要的作用。本文通过大规模仿真，并充分利用已有的研究结果，深入研究容易引起收敛延迟的特定网络拓扑结构，提出了基于对比度阀值的加快收敛速度算法，该算法以“确认不可达自治系统结点，怀疑变化自治系统的路径信息，优先考虑通过稳定自治系统到达目的地的路径”为原则，极大的减小了BGP收敛时间，同时克服了已有算法不可增量实现的缺陷。 3．控制BGP路径增长。对等关系是网络服务供应商改善系统性能的一个重要而高效的方法，这种关系除了可以提供冗余性，还可以支持自治系统灵活的选择报文传输的出口。但是，出于商业目的，这种灵活性经常被供应商用以实现自私的“hot potato”路由。研究表明，这种路由策略是造成路径增长的主要原因。为了限制这种自私行为，需要在对等体间设定价格机制。本文首先分析了简单的连续型价格机制存在的问题，进一步提出了离散型门限价格机制，该机制可以完全消除连续型价格机制所引发的全局效益损失，同时诱导对等体双方部分的放弃“hot potato”路由，在一定程度上控制了路径增长现象。 4．实现动态发现BGP域间路由震荡的算法，并为管理员提供解决震荡的工具。基于策略的路由选择过程使BGP协议不再是严格意义上的距离矢量协议，也不再具有距离矢量协议的收敛性，自治系统各自为政的策略配置方式会导致全局策略冲突，引起永久性的路由振荡。针对该问题，Griffin利用稳定路径问题(Stable Path Problem, SPP)模型形式化的

论文目录:

目录

图目录

表目录

摘要

ABSTRACT

第一章 绪论

1.1 问题的提出

1.1.1 边界网关协议 BGP

1.1.2 研究背景与意义

1.1.3 研究目标

1.1.4 研究内容

1.1.5 研究方法与技术路线

1.2 本文的工作

1.3 论文的结构

第二章 国内外相关研究现状

2.1 路由震荡

2.1.1 传统方法

2.1.2 最新方法

2.1.3 Internet逻辑连接属性

2.2 收敛延迟

2.2.1 Labovitz的实验结果

2.2.2 Griffin的实验结果及建议

2.3 路径增长

2.4 本章小结

第三章 BGP域内路由稳定性研究

3.1 BGP域内路由振荡

3.1.1 路由选择过程

3.1.2 BGP路由反射器

3.1.3 BGP联邦

3.1.4 反射器路由振荡

3.1.5 联邦路由振荡

3.2 动态稳定路径问题模型

3.2.1 动态稳定路径问题模型

3.2.2 动态稳定路径问题的竞争有向图和竞争轮

3.2.3 动态稳定路径问题的可解性分析

3.2.4 消除竞争有向图环路方法

3.3 消除秩函数时变性算法

3.3.1 算法思想

3.3.2 算法伪码实现

3.3.3 模拟试验

3.4 相关工作比较

3.5 本章小结

第四章 BGP收敛延迟研究

4.1 收敛延迟

4.1.1 全互联拓扑结构下的网络故障

4.1.2 多备份路径拓扑结构下的网络故障

4.1.3 网络重路由

4.2 对比度阀值算法

4.2.1 结点亮度和路径对比度

4.2.2 对比度阀值算法

4.2.3 算法分析

4.2.4 算法比较

4.3 可多点部署的对比度阀值算法

4.3.1 信息分析

4.3.2 可多点部署的对比度阀值算法

4.3.3 算法比较

4.4 本章小结

第五章 基于价格机制的 BGP路径增长控制

5.1 路径增长

5.2 一种简单的价格机制

5.2.1 “Hot potato”路由

5.2.2 连续型简单价格机制

5.3 离散型门限价格机制

5.3.1 离散型门限价格机制

5.3.2 与简单价格机制的比较

5.4 本章小结

第六章 基于安全多方计算的 BGP策略冲突检测算法

6.1 振荡问题的形式化分析

6.1.1 BGP抽象模型

6.1.2 状态转换图与 BGP系统的可解性

6.2 安全路径矢量协议

6.2.1 竞争有向图

6.2.2 安全路径矢量协议 SPVP

6.3 基于安全多方计算的策略冲突检测算法

6.3.1 安全多方计算

6.3.2 基于安全多方计算的策略冲突检测算法

6.4 本章小结

第七章 结束语

7.1 研究工作总结

7.2 本文的主要贡献

7.3 下一步的工作

致谢

攻读博士期间发表的论文

参考文献

发布时间: 2006-09-22

参考文献

• [1].域间路由系统独立监控技术[D]. 王禹.解放军信息工程大学2014
• [2].域间路由系统安全监测关键技术[D]. 郭毅.解放军信息工程大学2012
• [3].域间路由系统自组织特性及关键问题研究[D]. 赵金晶.国防科学技术大学2007
• [4].可信域间路由系统关键技术的研究[D]. 刘志辉.北京邮电大学2011
• [5].互联网域间路由系统生存性研究[D]. 刘宇靖.国防科学技术大学2013
• [6].分级域间路由系统及其关键技术[D]. 王娜.解放军信息工程大学2008
• [7].安全域间路由协议关键技术的研究[D]. 赵宸.北京邮电大学2013
• [8].域间路由生存性关键技术研究[D]. 李春秀.北京邮电大学2015
• [9].面向域间路由控制的信任机制研究[D]. 夏怒.东南大学2016
• [10].互联网域间路由安全监测技术研究[D]. 刘欣.国防科学技术大学2008

相关论文

• [1].计算机网络中的多播路由算法[D]. 刘莹.西安电子科技大学2000
• [2].IP网络带宽测量的模型与算法的研究[D]. 刘湘辉.国防科学技术大学2005
• [3].Web服务发现若干关键技术研究[D]. 胡建强.国防科学技术大学2005
• [4].P2P流媒体内容分发关键技术研究[D]. 刘亚杰.国防科学技术大学2005
• [5].一种新型路由器体系结构及其实现技术研究[D]. 王宝生.国防科学技术大学2005
• [6].路由协议并行处理技术研究[D]. 张晓哲.国防科学技术大学2005
• [7].Internet域间路由稳定性研究[D]. 王洪君.东北大学2006
• [8].基于BGP的域间流量工程研究[D]. 王大东.东北大学2006
• [9].计算机网络中的路由与性能优化[D]. 齐小刚.西安电子科技大学2005
• [10].自治域路由快速收敛、竞争策略和流量特性建模[D]. 李磊.北京交通大学2008

标签：计算机网络论文;  边界网关协议论文;  策略论文;  路由振荡论文;  收敛延迟论文;  路径增长论文;  安全多方计算仿真论文;