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

《混洗交换网络中最小无冲突路由分组的生成方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第2期计算机科学Vo1．41No．22014年2月ComputerScienceFeb2014混洗交换网络中最小无冲突路由分组的生成方法张以皓L沈越泓潘林。(解放军理工大学通信工程学院南京210007)(解放军理工大学指挥信息系统学院南京210016)。摘要为了解决混洗交换网络中冲突路由的分组问题，定义了路由的无冲突极大组、最小无冲突分组、特征函数及覆盖函数等概念，并基于这些概念提出了应用布尔代数计算最小无冲突分组的理论和方法。同时，为提高冲突路由分组的效率，提出了计算最小无冲突分组的近似算法。理论分析和实验表明，近似算法不仅具有良好的时

2、间性能，而且具有较高的准确度，它为在大规模信息交换中实施分批路由策略提供了强有力的支撑。关键词混洗交换网络，无冲突极大组，最小无冲突分组，特征函数，覆盖函数中图法分类号TP393文献标识码AMethodofComputingLeastNoConflictRoutingGroupingsinShuffle-exchangeNetworksZHANGYi-hao'。SHENYue-hongPANLin2(CollegeofCommunicationEngineering，PIAUniversityofScienceandTechnology，Nanj

3、ing210007，China)(CollegeofCommandInformationSystem，PLAUniversityofScienceandTechnology，Nanjing210016，China)AbstractInordertOresolvetheproblemofhowtoseparateconflictroutingsinshufle-exchangenetworks，thecon—ceptsofthemaximalnoconflictroutinggroup，theleastnoconflictroutinggroupi

4、ngs，eigenfunctionandcoveringfunc—tionweredefined．Basedontheseconcepts，thetheoryandmethodofcomputingtheleastnoconflictroutinggroupingsbybooleanalgebrawereproposed．Inaddition，analgorithmofapproximatelycomputingtheleastnoconflictroutinggroupingswasputforwardtoimprovetheefficienc

5、yofbatchrouting．Resultsoftheoreticalanalysisandexperimentsshowthatthetimeefficiencyandaccuracyofthealgorithmareexcellent．ItprovidesstrongsupportsforcarryingOutbatchroutingpolicyinprocessofmassiveinformationexchange．KeywordsShuffle-exchangenetwork，Maximalnoconflictroutinggroup

6、，Leastnoconflictroutinggroupings，Eigen—function，Coveringfunction线之间的任何一一对应都能确定一组无冲突的路由。目前，1引言只在规模级”(网络输入线数为2)不大于5的网络中找到了由于并行处理系统中信息共享与交换的需求，人们提出可行的路由算法，但其应用范围十分有限，文献[10—12]分别了混洗交换网络_1](Shuffle-exchangenetworks)、榕树网络[2]提出了一3，4，5时混洗交换网络中实现重排的算法；旁路是(Banyannetworks)和基线网络口](Baseli

7、nenetworks)等多种通过对两个相互冲突路由中的一个进行被动重新选路来解决类型的多级互连网络。其中，N×N(N个输入端和N个输路由冲突，虽然方法实现简单，但时间延迟不易控制，路由性出端，N一2)的混洗交换网络由于其结构的可扩展性及路由能不够稳定；丢弃方法是直接放弃部分冲突路由信号的传输，机制方面的优势而被广泛研究和应用l_4。]。混洗交换网络由由于存在信息损失，只能用于某些路由质量要求不高的场合，2×2的交换单元连接而成，每个交换单元通过“直通”与“交而且，为了控制信息损失，采用的网络结构比较复杂_1。。；分批叉”状态的选择实现交换功能。根

8、据交换单元间连接方式的方法是通过对输入信息分批来避免路由冲突，分批路由需要不同，混洗交换网络又可分为多种类型，其中，最简单也是最的网络级