光RP(k)网络上Hypercube通信模式的波长指派算法  

A Wavelength Assignment Algorithm of Hypercube Communication on Optical RP(k) Networks

作　　者：刘方爱[1] 刘志勇[2] 乔香珍[3] 

机构地区：[1]山东师范大学计算机系,山东济南250014 [2]国家自然科学基金委员会,北京100085 [3]中国科学院计算技术研究所,北京100080

出　　处：《软件学报》2003年第3期575-581,共7页Journal of Software

基　　金：Supported by the National Natural Science Foundation of China under Grant No.69933020 (国家自然科学基金); the Natural Science Foundation of Shandong Province of China under Grant No.Y2002G03 (山东省自然科学基金)

摘　　要：波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2n个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,52n-5/3}个波长.而在环网络上,实现该通信模式需要复用N/3+N/12个波长,比已有算法需要复用N/3+N/4个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.Routing and channel assignment is a key topic in optical interconnection networks, and it is a primary way to get insight into the capacity of interconnection networks. Based on the optical RP(k) network, the wavelength assignment of realizing the Hypercube communication with N=2n nodes on the optical RP(k) network is discussed. By defining the reverse order of the Hypercube, an algorithm to embed the n-D Hypercube into the RP(k) network is designed, which needs at most max{2,52n-5/3} wavelengths. An algorithm to embed the n-D hypercube into the ring network is also proposed, with its congestion equal to N/3+N/12. This is a better improvement than the known results, which is equal to N/3+N/4. The two algorithms proposed in this paper are of great value in designing optical networks.

关 键 词：光RP(k)网络 Hypercube通信模式 波长指派算法 计算机互连网络 

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