基于三维矩阵重构争论有向图的域间路由振荡检测算法

边界网关协议(Border G atew ay P rotoco l,BGP)是当前In ternet域间路由协议的事实标准,基于策略的路由选择过程使它不再是严格意义上的距离矢量协议,也不再具有距离矢量协议的收敛性.V aradhan指出,自治系统各自为政的策略配置方式会导致全局策略冲突,引起永久性的路由振荡.针对该问题,G riffin利用稳定路径问题(S tab le Path P rob lem,SPP)模型形式化的抽象出BGP协议行为,并以此为基础提出了一种分布式的策略冲突检测算法,尽管该算法完全避免了传统方法的缺陷,但仍然存在泄漏策略信息和对BGP协议改动太大以及浪费网络资源的问题.本文提出了一种基于安全多方计算的检测路由策略冲突的方法,用于在怀疑BGP路由发生振荡时,动态的检测系统中是否存在策略冲突.该方法采纳了G riffin的理论基础,同时由于巧妙的运用了安全多方计算协议,可以完全解决G riffin算法的问题,具有很好的实用性.

An Approach to Seeking BGP Policy Confliction Based on Reconstructing Dispute Diagraph with Three-dimensional Matrix

The Border Gateway Protocol,BGP,is currently the only inter-domain routing protocol employed on the Internet.BGP is a path-vector protocol that allows each Autonomous System to override distance-based metrics with policy-based metrics when choosing best routes.Varadhan has shown that it is possible for a group of Autonomous Systems to independently define BGP policies that together lead to BGP protocol oscillations that never converge on a stable routing.Based on analyzing BGP with Stable Path Problem (SPP) model,Griffin proposed an efficient algorism that can find the policy confliction.But this algorithm faces several impediments.In this paper we present a new method which inherits Griffin′s merits and eliminates his impediments at the same time.With secure multi-party computation,our algorithm can work well and has significant practical value.