混洗交换网络中最小无冲突路由分组的生成方法  

Method of Computing Least No Conflict Routing Groupings in Shuffle-exchange Networks

作　　者：张以皓[1,2] 沈越泓[1] 潘林[2] 

机构地区：[1]解放军理工大学通信工程学院,南京210007 [2]解放军理工大学指挥信息系统学院,南京210016

出　　处：《计算机科学》2014年第2期191-196,共6页Computer Science

摘　　要：为了解决混洗交换网络中冲突路由的分组问题,定义了路由的无冲突极大组、最小无冲突分组、特征函数及覆盖函数等概念,并基于这些概念提出了应用布尔代数计算最小无冲突分组的理论和方法。同时,为提高冲突路由分组的效率,提出了计算最小无冲突分组的近似算法。理论分析和实验表明,近似算法不仅具有良好的时间性能,而且具有较高的准确度,它为在大规模信息交换中实施分批路由策略提供了强有力的支撑。In order to resolve the problem of how to separate conflict routings in shuffle-exchange networks, the con- cepts of the maximal no conflict routing group, the least no conflict routing groupings, eigenfunction and covering func- tion were defined. Based on these concepts, the theory and method of computing the least no conflict routing groupings by boolean algebra were proposed. In addition, an algorithm of approximately computing the least no conflict routing groupings was put forward to improve the efficiency of batch routing. Results of theoretical analysis and experiments show that the time efficiency and accuracy of the algorithm are excellent. It provides strong supports for carrying out batch routing policy in process of massive information exchange.

关 键 词：混洗交换网络 无冲突极大组 最小无冲突分组 特征函数 覆盖函数 

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