论文部分内容阅读
目前,边界网关协议(BGP)是运行于Internet上的事实上的外部网关协议。在一个自治域内部,网络管理者可以获取路由器拓扑并对路由信息进行控制。而在自治域之间,Internet采用了一种分布式控制路由信息方式,每个自治系统通过边界网关协议与其他自治系统交换网络可达信息。边界网关协议的关键特征是允许网络管理者定义自己的路由策略,路由策略允许自治系统向邻居自治系统通告其全部或部分路由。域间路由的可预测性,是指大型ISP为了某种目的将不得不调整他们的网络以满足紧迫的服务质量(QoS)的限制,排除链路故障、路由器故障以及在网络中实施负载均衡,都会使网络中的通信载荷产生强烈变化,他们必须对调整后的网络的域间路由选择结果做出评估来避免致命的错误,包括路由故障检测,预测路由选择结果等等。域间路由预测的难点在于很难组织起满足以下三个要求的(跨)域路由:全球范围的可达性,实现经济目标的高配置性策略,能提供质量保证的机制。因此更好的了解路由层正在发生的事情是必不可少的。但是运行在大型动态网络上的外部BGP (eBGP)、内部BGP (iBGP)、内部网关协议IGP三者之间的相互作用非常复杂,人们并不能真正理解,现有的拓扑结构的模拟往往是用一个单独的路由器再现每个AS,AS对等体的设置是根据AS连通图的边缘,而没有考虑内部BGP和内部网关协议IGP的影响以及两个AS之间的多个出口点的影响。这样导致了虽然模拟的拓扑是依靠网络上的真实数据得到的,但是再现的路由选择结果和实际不符。本文以国家自然科学基金‘’Internet可扩展性与可管理性研究”为背景,在多个方面对影响域间路由选择结果的因素进行了详细的研究,并对现实网络进行了模拟。本文概括介绍了Internet域间拓扑结构和域间路由的研究现状,域间路由预测的必要性和本文要采用的研究方法。介绍了BGP常用属性和BGP的决策过程,分析了影响域间路由选择过程模型因素。详细分析了Internet自治系统拓扑模型和自治系统层次结构特点,着重阐述了顶层自治系统的结构特点和域间路由的路径特点。利用BGP路由表包含的路径信息,根据不同层次自治系统结构特点,推导出了各个自治系统所属的层次。分类介绍了自治系统之间存在的商业合同关系,综述了在路由策略、自治系统关系方面的研究现状,阐述了根据自治系统关系设置路由策略的一般性原则。提出了一种从多个BGP路由表推导AS关系的方法,根据Tier-1路由表AS PATH的结构特点,利用多个Tier-1路由表相互验证自治系统关系,再由其他属于不同层次自治系统的BGP路由表辅助验证。与同类算法相比算法中没有引入经验参数,结果对比表明算法推导结果具有极高的正确率。对ISP间的多出口点对路由预测问题的影响进行了研究,首先给出了自治系统对等关系模型,提出了一种路径属性变化的记载方法,并进一步给出了检测多对等点路由通告不一致的算法,并利用c-bgp模拟工具在一个模拟的ISP拓扑上实现了该算法,结果显示算法是可行的。其次又研究了多出口点时的次优路由问题,给出了一个带有路由反射器的最佳路由出口点的检查算法,并用c-bgp模拟器进行了仿真,结果显示模拟的拓扑中存在30%以上的次优路由。研究了域内路由协议对路由选择的影响,分别讨论了iBGP全网时MED属性和路由反射对路由选择的影响,并给出了基于MED属性和路由反射的路由预测方法。通过对域内、域间的拓扑建模仿真,结果显示域内的IGP、iBGP等域内路由协议影响域间路由的选择结果。现实网络的模拟模型是域间路由预测的基础,它直接影响域间路由的可预测性。本文对现实网络模拟方法进行了研究。提出了如何从公共的路由表数据推导出Internet的初始模型,由初始模型演变到现实网络模拟模型的建模方法。在对当前流行的模拟方法进行分析总结的基础上,对Per-prefix试探法进行了改进,模型演变过程中考虑AS之间商业关系的影响。通过模拟实验,再现了现实网络的域间拓扑结构,结果显示改进后的Per-prefix试探法对Akamai-Sample中观察路径的匹配数量有明显的提高。