单向链路邻接发现和路径生成的研究

RESEARCH ON NEIGHBOR DISCOVERY AND PATH GENERATION FOR UNIDIRECTIONAL LINKS

单向链路和不对称应用需求的出现使得传统的网络路由算法和协议不再适用．隧道封装和路由修改是解决近期双向连通网络添加单向链路所面临问题的常用方法，但仍无法适合完全单向链路网络的远期目标．文中首先给出网络和路由的定义和表示；再提出基于有界扩散的邻接发现算法，并证明某一回路穿越特定链路次数的上界；然后提出基于邻接矩阵的路径生成算法。

With the emergence of unidirectional links and asymmetric applications requirements, traditional routing algorithms and protocols for bi\|directional and symmetric links are facing some severe challenges. Tunnel encapsulation and route modification are two common solutions to the short\|term scenario where some unidirectional links are added into the connected bi\|directional networks, but they also fail to meet the long\|term scenario where only unidirectional links are available. Following the definition of graph topology and network routing, a bounded neighbor discovery algorithm is proposed, and the upper bound on trips of any loop crossing one specified links is proved. A path generation algorithm based on the neighbor/path matrix is also presented and validated by some examples.