一种基于代数方法的路由振荡检测算法研究  

A Study of Algorithm for Testing Route Oscillation Based on Algebraic Method

作　　者：赵会群[1] 孙晶[1] 

机构地区：[1]北方工业大学信息工程学院,北京100041

出　　处：《计算机学报》2007年第10期1763-1769,共7页Chinese Journal of Computers

基　　金：国家自然科学基金(60473032);国家"八六三"高技术研究发展计划项目基金(2006AA09Z139);北京市自然科学基金(4062012)资助.~~

摘　　要：基于路由网络代数(Routing Network Algebra,RNA)提出了一种新的路由振荡检测方法.通过建立路由系统的路由网络代数模型,把路由分析转化为代数演算;通过引入路由网络元素线性相关性概念,证明了路由振荡的充分必要条件是网络元素线性相关.在此基础上,提出了O(H×L+N2)时间级的路由振荡检测算法.为了支持文中提出的算法,设计实现了一个路由振荡检测程序,通过对多个真实的路由表检测,进一步说明了上述算法的可行性.Based on the RNA（Route network algebra） a new method for testing route oscillation is proposed. By modeling a route system in RNA expression it translates route analysis work into algebraic deduction. By introducing concept of linear relation of network elements it proves that route oscillation if and only if network elements have linear relativity. Following the ideal an O（HXL-bN2） time algorithm for testing route oscillation is proposed. To support the new ideal an experiment is design with proposed algorithm, which work on real route table of AS, its feasibility had been further demonstrated.

关 键 词：路由振荡 路由网络代数 协议测试 边界网关协议 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]