Efficient Shortest-Path-Tree Computation in Network Routing Based on Pulse-Coupled Neural Networks
Efficient Shortest-Path-Tree Computation in Network Routing Based on Pulse-Coupled Neural Networks
复制标题
基于脉冲耦合神经网络的网络路由中高效最短路径树计算
DOI：
10.1109/tsmcb.2012.2221695
复制
发表时间：
2013-06-01
影响因子：
11.8
通讯作者：
Yang, Simon X.
中科院分区：
文献类型：
--
作者：
Qu, Hong;Yi, Zhang;Yang, Simon X.
最短路径树（SPT）计算是使用链路状态路由协议的路由器的关键问题，例如最常用的开放最短路径优先和中间系统到中间系统。每当链路状态发生变化时，每个路由器都需要重新计算一个以自身为根的新SPT。大多数商业路由器通过删除当前SPT并在开始时使用静态算法（例如Dijkstra算法）构建新SPT来进行此计算。整个SPT的这种重新计算是低效的，这可能消耗相当大量的CPU时间并导致网络中的时间延迟。近年来，人们提出了一些利用更新后的SPT中的信息进行动态更新的方法。然而，这些动态算法仍然存在许多局限性。本文提出了一种新的脉冲耦合神经网络（M-PCNNs）模型用于SPT计算。它是严格证明，该模型是能够解决一些优化问题，如SPT。针对大规模问题，提出了一种基于M-PCNN的SPT静态算法。此外，一个动态的算法，利用以前计算的SPT的结构，这显着提高了算法的效率。仿真结果证明了该方法的有效性和高效性。
Shortest path tree (SPT) computation is a critical issue for routers using link-state routing protocols, such as the most commonly used open shortest path first and intermediate system to intermediate system. Each router needs to recompute a new SPT rooted from itself whenever a change happens in the link state. Most commercial routers do this computation by deleting the current SPT and building a new one using static algorithms such as the Dijkstra algorithm at the beginning. Such recomputation of an entire SPT is inefficient, which may consume a considerable amount of CPU time and result in a time delay in the network. Some dynamic updating methods using the information in the updated SPT have been proposed in recent years. However, there are still many limitations in those dynamic algorithms. In this paper, a new modified model of pulse-coupled neural networks (M-PCNNs) is proposed for the SPT computation. It is rigorously proved that the proposed model is capable of solving some optimization problems, such as the SPT. A static algorithm is proposed based on the M-PCNNs to compute the SPT efficiently for large-scale problems. In addition, a dynamic algorithm that makes use of the structure of the previously computed SPT is proposed, which significantly improves the efficiency of the algorithm. Simulation results demonstrate the effective and efficient performance of the proposed approach.