路由网络代数  

Routing Network Algebra

作　　者：赵会群[1,2] 孙晶[1] 王国仁[3] 高远[3] 

机构地区：[1]北方工业大学信息工程学院 [2]东北大学信息工程学院沈阳100061 [3]东北大学信息工程学院

出　　处：《计算机学报》2004年第7期888-896,共9页Chinese Journal of Computers

基　　金：国家自然科学基金资助 (Internet域间路由稳定性和可管理性的研究( 60 2 73 0 78) );北京市教委科研基金资助 (KM2 0 0 3 10 0 0 90 2 6);北方工业大学北京市现场总线重点实验室开放课题资助

摘　　要：基于基本网络代数 (BasicNetworkAlgebra ,BNA)和LOTOS/E LOTOS ,该文提出一种适合于分析Inter net路由系统行为的代数系统 .该代数系统称为路由网络代数 (RoutingNetworkAlgebra,RNA) ,它结合了BNA中的并行、串行运算以及LOTOS中的同步并行运算 ,并在此基础提出更适合于描述Internet路由系统行为的选择运算“ ”、协同并行“ ”以及路由网络常量 ,如m×n(路由转发 )、∧ m(分支 )、∨ m(合并 )、⊥ m(下沉 )和┬ m(亚元 ) .通过分析由上述代数运算和路由网络常量构成的路由网络代数模型 ,可以分析路由系统中死锁 (deadlock)和活锁(alivelock)等行为 .为了检验路由网络代数的有效性 ,完成了BGP路由稳定性的实验分析工作 .Based on the BNA (basic network algebra) and LOTOS/E-LOTOS a new algebra framework for description and analysis of behavior of Internet routing system is proposed. The new algebra system called Routing Network Algebra (RNA in short) combines parallel and sequential operation from BNA and synchronous parallel operation from LOTOS into RNA. In order to describe the properties of Internet routing system some new operations called selection operation and collaborative parallel operation and some constants such as translation, split, merge, sink, dummy source are also employed. By analyzing the algebra model that comprise of operations and constants the behaviors of routing system such as deadlock and alive lock can be found. In order to verify the efficiency of the RNA, an experiment for analyzing the stability of routing system of BGP (Border Gateway Protocol) has been completed.

关 键 词：网络代数 LOTOS 路由网络代数 路由稳定性 边界网关协议 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]