A new family of routing algorithms for the distributed maintenance of routing information in large networks and internets is introduced. This family is called link vector algorithms (LVA), and is based on the selective diffusion of link-state information based on the distributed computation of preferred paths, rather than on the flooding of complete link-state information based on the distributed computation of preferred paths, rather than on the flooding of complete link-state information to all routers. According to LVA, each router maintains a subset of the topology that corresponds to the links used by its neighbor routers in their preferred paths to known destinations. Based on that subset of topology information, the router derives its own preferred paths and communicates the corresponding link-state information to its neighbors. An update message contains a vector of updates; each such update specifies a link and its parameters. LVAs can be used for different types of routing. The correctness of LVA is verified for arbitrary types of routing when correct and deterministic algorithms are used to select preferred paths at each router. LVA is shown to have smaller complexity than link-state and distance-vector algorithms, and to have better average performance than the ideal topology-broadcast algorithm and the distributed Bellman-Ford algorithm.
引入了一种新的路由算法系列,用于在大型网络和Internet中分布式维护路由信息。该族称为链路矢量算法(LVA),它基于基于首选路径的分布式计算的链路状态信息的选择性扩散,而不是基于基于首选路径的分布式计算的完整链路状态信息的泛洪路径,而不是将完整的链接状态信息泛洪到所有路由器。根据LVA,每个路由器都维护拓扑的一个子集,该子集与其邻居路由器在通往已知目的地的首选路径中使用的链路相对应。基于该拓扑信息的子集,路由器得出自己的首选路径,并将相应的链路状态信息传递给其邻居。更新消息包含更新向量;每个此类更新都会指定一个链接及其参数。 LVA可以用于不同类型的路由。当使用正确的确定性算法在每个路由器上选择首选路径时,可针对任意类型的路由验证LVA的正确性。 LVA具有比链接状态和距离矢量算法更小的复杂性,并且比理想的拓扑广播算法和分布式Bellman-Ford算法具有更好的平均性能。 P>
Univ. of California, Santa Cruz;
86 Symposium. He has also been program committee member for numerous IFIP 6.5, ACM, and IEEE conferences on computer communication. He received the SRI International Exceptional-Achievement Award in 1985 for his work on multimedia communications, and again in 1989 for his work on adaptive routing algorithms.;
机译:基于链接状态向量的分布式可伸缩路由
机译:信息动态意识的路由软件开发:以基于未来链路延迟信息估计的改进链路状态路由的路由软件为例
机译:存在路由信息损坏时基于树的链接状态路由
机译:具有三个指标的基于链路状态QoS的路由的可扩展算法
机译:运动矢量路由协议:一种用于移动自组织网络的基于位置的路由协议。
机译:混合重力和路径选择模型用于评估大型路网中的矢量交通
机译:基于链路状态向量的分布式可扩展路由
机译:基于链路状态向量的分布式可扩展路由。