随着Internet的发展和网络服务商业化进程的加快,Internet的规模和复杂程度都在迅速增长。从管理的角度讲,Internet是由成千上万的自治系统(Autonomous System简称AS)组成,这些AS可能分别隶属于不同的Internet服务提供商(Internet Service Provider简称ISP),而不同的ISP可能重组成为新的ISP,从而形成动态的管理组织结构。自治系统之间通过公共网络访问点(Network Access Point简称NAP)和边界网关协议(Border Gateway Protocol简称BGP)来交换路由信息。BGP协议允许每个自治系统根据自己的策略选择、通告和接受路由,为路由选择提供了灵活机制。 然而相关研究表明,BGP路由策略在一定情况下能够产生冲突,会引起路由振荡,造成可达信息在路由表中重复更新,直接或间接地影响Internet的性能。因此,BGP路由稳定性问题研究对Internet的发展具有重要的现实意义。本文的主要目的是对BGP的路由策略冲突检测问题进行研究,给出多种路由策略冲突检测的方法,并实现一套路由策略冲突检测系统。 首先,论文对BGP协议进行了详细的分析,给出了一个BGP抽象模型,并在此模型的基础上结合BGP的输出策略原则,实现了BGP路由系统自治系统关系的推导,提出了基于自治系统关系的路由策略冲突检测算法。同时,论文结合路由网络代数的相关知识,把BGP路由系统的策略冲突检测转换为路由网络代数表达式的活锁检测,并最终实现了基于路由网络代数的路由策略冲突检测算法。此外,本文还结合图论相关知识,利用拓扑排序和逆拓扑排序的方法对路由策略冲突检测问题进行研究,并提出了基于拓扑排序的路由策略冲突检测算法。 同时,论文给出了相应实验结果。借助于SSFNet仿真工具,我们对存在策略冲突的BGP路由系统进行建模,并使用相应算法对所模拟的BGP系统进行检测,最终所得结果和预期数据基本一致。 理论研究和实验结果表明,基于自治系统关系、基于路由网路代数和基于拓扑排序的路由冲突检测算法能够检测出不同类型的策略冲突,路由策略冲突检测系统综合使用了以上三种算法,能够有效地发现BGP路由系统中是否存在策略冲突。