步长有限制的双环网络的最优路由算法  

An Optimal Routing Algorithm for Double Loop Networks with Restricted Steps

作　　者：陈协彬[1] 

机构地区：[1]漳州师范学院数学系,漳州363000

出　　处：《计算机学报》2004年第5期596-603,共8页Chinese Journal of Computers

基　　金：福建省自然科学基金 (F0 0 0 18)资助

摘　　要：双环网络G(n ;h) (n是结点数 ,1和h是步长 )是重要的互联网络结构 .目前人们已提出了几种最优路由算法 ,其时间复杂性至少为O(n) .该文考虑步长h有限制的双环网络G(n ;h)的最优路由问题 ,证明了当h满足某个不等式时 ,可得到G(n ;h)的直径显公式和常数时间的最优路由算法 ,确切地说 ,至多只要 6次算术运算或比较即可确定源结点 0到任一个目标结点的最短路 .这些结果可应用于 6 6族紧优和 30族几乎紧优双环网络的无限族 ,使得对于 5 n 30 0的每个n (n =99和 187除外 ) ,都有G(n ;h)含于上述某个无限族中 .Double loop networks (DLN, for simplicity) G(n; h), where n is the number of its nodes and 1 and h are its steps, are important interconnection networks. Some optimal routing algorithms for G(n; h) have been proposed, their time complexity is at least O(n). In this paper, DLN with restricted steps are considered. It is proved that if the step h satisfies a certain inequality, then the formula for its diameter is given, and the constant time optimal routing is obtained, precisely, at most 6 arithmetic operations or comparisons are needed to determine a shortest path from the origin 0 to any destination node. The results can be applied to 66 infinite families of tight optimal DLN and 30 infinite families of nearly tight optimal DLN, such that for every n, 5n300, except n=99 and 187, there is G(n; h) contained in above some family.

关 键 词：双环网络 步长 最优路由算法 互联网络结构 最短路 

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