作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2007, Vol. 33 ›› Issue (16): 80-82. doi: 10.3969/j.issn.1000-3428.2007.16.027

• 网络与通信 • 上一篇    下一篇

最小分布优先Clos网路由算法

段新明1,杨愚鲁1,孙莱印2,凌晓萍2   

  1. (1. 南开大学信息技术科学学院,天津 300071;2. 日本神奈川工科大学信息学部)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-08-20 发布日期:2007-08-20

Minimum Distribution Priority Algorithm for Clos Network

DUAN Xin-ming1, YANG Yu-lu1, SUN Lai-yin2, LING Xiao-ping2   

  1. (1. College of Information Technical Science, Nankai University, Tianjin 300071; 2. Department of Information Technical Science, Kanagawa Institute of Technology)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-08-20 Published:2007-08-20

摘要: 提出了一种新的Clos网无阻塞路由算法、最小分布优先算法,用该算法可以降低Clos路由算法的高时间复杂度。对于Clos网连接说明矩阵,提出并证明了矩阵中某一列的完全性问题是一个独立的问题,并据此提出了以最小分布优先的方式逐列计算Clos连接说明矩阵的策略,消除了产生在矩阵列之间的回溯以及列内元素之间的回溯,能够完全实现无阻塞路由,在最坏情况下的时间复杂度为O(N3/2),可以应用于Clos网路由控制。

关键词: Clos网, 路由算法, 时间复杂度

Abstract: This paper presents a new Clos network routing algorithm named MDP(minimum distribution priority) algorithm in order to reduce the high time complexity of original algorithm for Clos network. It illustrates that it is an independent problem whether a column in specification matrix is complete. As a result, it introduces a minimum distribution priority scheme handling Clos specification matrix column by column and eliminates backtracking among columns and backtracking among elements in the same column. The MDP algorithm ensures that non-blocking routing can be completely achieved and a low time complexity O(N3/2) can still be reached in the worst case. So the algorithm is readily applicable to the control of Clos network.

Key words: Clos network, routing algorithm, time complexity

中图分类号: