路由网络代数

Routing Network Algebra

基于基本网络代数 (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.