一种基于路由网络代数的路由振荡检测算法

• 作 者: 赵会群 孙晶 高远
• 机 构: 北方工业大学信息工程学院(北京)
• 出 处: 第十届全国容错计算机学术会议
• 发表日期: 2003年期
• 关键词: 路由网络代数 路由振荡检测 检测算法 相互关系 线性时间 网络元素 算法比较 检测方法 仿真工具 对应关系 相关性 仲裁 验证 基础

基于路由网络代数(Routing network algebra简称RNA)提出了一种新的路由振荡检测方法.通过建立路由振荡与路由网络"活锁"的对应关系,把路由振荡检测归结为检测网络元素的相关性.在此基础上,一种线性时间的路由振荡检测算法被提出.与著名的Arbiter路由仲裁计划提出的路由振荡检测算法比较,文中提出的算法不是np-hard问题.为了展示提出方法的正确性,利用仿真工具SSFNET验证了"活锁"与路由振荡的相互关系.