本发明公开了一种面向Benes网络的低复杂度避障路由方法及装置，对于Benes网络，通过对故障单元判定子网连接优先级；根据输入‑输出端口连接情况，构建输入层输入端口、输出层输出端口、子网连接优先级的关联关系；根据关联关系确定输入层、输出层开关状态；根据开关状态更新子网中的输入‑输出端口连接情况；当输入‑输出端口连接情况达到中间级，则确定中间级开关单元状态并结束流程；否则，将次边缘级作为最新的边缘级，重新进行故障单元分析。面向开关单元设计不理想、配套控制电路及电封装不连通情况，该低复杂度避障路由方法可实现任意规模Benes网络结构、任意端口配置情况下的低阻塞率路由，实现开关单元资源利用最优化。
1.一种面向Benes网络的低复杂度避障路由方法，Benes网络是由一组开关单元构成的阵列，多个阵列依次嵌套，各阵列均包括输入层、输出层，以及输入层和输出层之间的两个子网，各阵列的输入层分别与该阵列的两个子网的输入端连接，各阵列的输出层分别与该阵列的两个子网的输出端连接，各输入层、各输出层及各子网分别包括多个成阵列排列的多个开关单元，各开关单元均为2*2输入‑输出开关单元，当前层阵列的各子网分别嵌套有一个下一层阵列，对于各阵列，该阵列的输入层作为该阵列的边缘级输入层，该阵列的输出层作为该阵列的边缘级输出层，其特征在于，所述方法包括如下步骤：由嵌套的外层向中心方向，对各阵列，依次执行如下操作，直至达到嵌套最内部的中间级阵列：
步骤S1，对所述阵列进行故障单元分析，根据分析结果，判定两个所述子网的连接优先级；
步骤S2，根据输入层的输入端口与输出层输出端口的连接关系以及两个所述子网的连接优先级，构建输入层的输入端口、输出层的输出端口，以及两个所述子网的连接优先级的关联关系；
步骤S3，根据关联关系，确定作为边缘级的输入层中各开关单元的开关状态和作为边缘级的输出层中各开关单元的开关状态，所述开关状态为交叉状态或平行状态；
步骤S4，根据作为边缘级的输入层的开关状态和作为边缘级的输出层的开关状态，进行两个所述子网的路径更新，以更新两个所述子网中的输入‑输出端口的连接关系；
步骤S5，判断输入‑输出端口连接情况是否达到中间级，若达到，则确定中间级开关单元状态并结束流程；若未达，则将次边缘级作为最新的边缘级，并分析此时的输入‑输出端口连接情况，返回步骤S1。
2.根据权利要求1所述的一种面向Benes网络的低复杂度避障路由方法，其特征在于：
确定所述阵列中，子网故障单元的数量以及边缘级故障单元的数量，其中所述子网故障单元包括对应子网中处于故障的开关单元，所述边缘级故障单元包括所述阵列中输入层包括的处于故障的开关单元以及所述阵列中输出层包括的处于故障的开关单元；
根据所述阵列中，子网故障单元的数量和边缘级故障单元的数量，判定两个所述子网的连接优先级；
其中，子网故障单元少的子网，优先级更高；当子网故障单元数相同时，边缘级故障单元少的子网，优先级更高；当子网故障单元数及边缘级故障单元数均相同时，默认或随机指定一个优先级更高的子网。
3.根据权利要求1所述的一种面向Benes网络的低复杂度避障路由方法，其特征在于：
所述开关单元包括上、下输入端口，和上、下输出端口，所述两个子网分别为A、B子网，所述步骤S2具体包括：
根据输入层的输入端口与输出层输出端口的连接关系，将输入层开关单元的输入端口与输出层开关单元的输出端口建立00、01、10、11的输入‑输出关联关系，其中第一位的0或1对应输入层开关单元的上输入端口或下输入端口，第二位的0或1对应输出层开关单元的上输出端口或下输出端口；
根据两个所述子网的优先级，通过输入‑输出关联关系，建立A、B、AB、BA的优先级关联关系，A表示该输入‑输出关联关系通过A子网连接，B表示该输入‑输出关联关系通过B子网连接，AB表示一个输入层开关单元的两个输入端口和一个输出层开关单元的两个输出端口完全对应，此时输入‑输出关联关系先通过优先级更高的A子网连接，而后通过B子网连接，BA则相反。
4.根据权利要求1所述的一种面向Benes网络的低复杂度避障路由方法，其特征在于：
所述步骤S2中，建立开关单元表，用于记录输入层输入端口、输出层输出端口，以及子网连接优先级的关联关系，其中行表示输入层开关单元，列表示输出层开关单元，在寻找下一填写的开关单元过程中，首先判断当前输入层开关单元是否有对应端口需填写；然后判断当前输出层开关单元是否有对应端口需填写；若此开关单元对应的行和列均无需要填写的端口，则按端口输入顺序选择下一要填写的开关单元。
5.根据权利要求3所述的一种面向Benes网络的低复杂度避障路由方法，其特征在于：
所述关联关系中00+A，01+A，10+B，11+B，10+AB，11+AB，00+BA，01+BA对应输入层开关单元平行状态，10+A，11+A，00+B，01+B，00+AB，01+AB，10+BA，11+BA对应输入层开关单元交叉状态；
其中00+A，10+A，01+B，11+B，01+AB，11+AB，00+BA，10+BA对应输出层开关单元平行状态；01+A，11+A，00+B，10+B，00+AB，10+AB，01+BA，11+BA对应输出层开关单元交叉状态。
6.一种面向Benes网络的低复杂度避障路由装置，包括Benes网络、故障单元分析模块、开关单元表填写模块、开关状态确定模块和子网路径更新模块，Benes网络是由一组开关单元构成的阵列，多个阵列依次嵌套，各阵列均包括输入层、输出层，以及输入层、和输出层之间的两个子网，各阵列的输入层分别与该阵列的两个子网的输入端连接，各阵列的输出层分别与该阵列的两个子网的输出端连接，各输入层、各输出层及各子网分别包括多个成阵列排列的多个开关单元，各开关单元均为2*2输入‑输出开关单元，当前层阵列的各子网分别嵌套有一个下一层阵列，对于各阵列，该阵列的输入层作为该阵列的边缘级输入层，该阵列的输出层作为该阵列的边缘级输出层，其特征在于：由嵌套的外层向中心方向，对各阵列，依次循环调用如下模块，直至达到嵌套最内部的中间级阵列：
所述故障单元分析模块，对所述阵列进行故障单元分析，根据分析结果，判定两个所述子网的连接优先级；
所述开关单元表填写模块，根据输入层的输入端口与输出层输出端口连接关系以及两个所述子网的连接优先级，构建输入层的输入端口、输出层的输出端口，以及两个所述子网的连接优先级的关联关系；
所述开关状态确定模块，根据关联关系，确定作为边缘级的输入层中各开关单元的开关状态和作为边缘级的输出层中各开关单元的开关状态，所述开关状态为交叉状态或平行状态；
所述子网路径更新模块，根据作为边缘级的输入层的开关状态和作为边缘级的输出层的开关状态，进行两个所述子网的路径更新，以更新两个所述子网中的输入‑输出端口的连接关系；子网路径更新模块根据开关状态，进行子网路径更新，更新子网中的输入‑输出端口连接情况，以确定后续内部开关单元状态；若输入‑输出端口连接情况达到中间级，则确定中间级开关单元状态；若未达，则将次边缘级作为最新的边缘级，并分析此时的输入‑输出端口连接情况，返回故障单元分析模块。
7.根据权利要求6所述的一种面向Benes网络的低复杂度避障路由装置，其特征在于：
所述开关单元包括上、下输入端口，和上、下输出端口，所述两个子网分别为A、B子网，所述开关单元表填写模块，通过构建开关单元表，建立输入层的输入端口与输出层输出端口的连接关系，以及两个所述子网的连接优先级，其中开关单元表的行表示输入层单元开关，列表示输出层单元开关，开关单元表包括输入‑输出端口表和子网连接情况表。
8.根据权利要求7所述的一种面向Benes网络的低复杂度避障路由装置，其特征在于：
所述输入‑输出端口表，根据输入层的输入端口与输出层输出端口的连接关系，将输入层开关单元的输入端口与输出层开关单元的输出端口建立00、01、10、11的输入‑输出关联关系，并在输入‑输出端口表的行列交叉处进行填写，其中第一位的0或1对应输入层开关单元的上输入端口或下输入端口，第二位的0或1对应输出层开关单元的上输出端口或下输出端口。
9.根据权利要求8所述的一种面向Benes网络的低复杂度避障路由装置，其特征在于：
所述子网连接情况表，根据两个所述子网的优先级和输入‑输出关联关系，在行列交叉处填写相应的优先级关联关系A、B、AB、BA，A表示该输入‑输出关联关系通过A子网连接，B表示该输入‑输出关联关系通过B子网连接，AB表示一个输入层开关单元的两个输入端口和一个输出层开关单元的两个输出端口完全对应，此时输入‑输出关联关系先通过优先级更高的A子网连接，而后通过B子网连接，BA则相反。
10.根据权利要求9所述的一种面向Benes网络的低复杂度避障路由装置，其特征在于：
所述开关单元构成的阵列为交叉开关矩阵，所述开关状态确定模块根据开关单元表，确定交叉开关矩阵的交叉/平行状态，所述关联关系中00+A，01+A，10+B，11+B，10+AB，11+AB，00+BA，01+BA对应输入层开关单元平行状态，10+A，11+A，00+B，01+B，00+AB，01+AB，10+BA，11+BA对应输入层开关单元交叉状态；其中00+A，10+A，01+B，11+B，01+AB，11+AB，00+BA，10+BA对应输出层开关单元平行状态；01+A，11+A，00+B，10+B，00+AB，10+AB，01+BA，11+BA对应输出层开关单元交叉状态。
一种面向Benes网络的低复杂度避障路由方法及装置
技术领域
[0001] 本发明涉及网络交换领域，尤其是涉及一种面向Benes网络的低复杂度避障路由方法及装置。
背景技术
[0002] 网络交换机是一种用于电/光信号转发的网络设备，可以为任意两个接入的网络交换节点提供通路。网络交换架构分为受限阻塞型、重排无阻塞型和严格无阻塞型架构，三者所使用的开关单元数目包括级数是递增的。其中Benes网络属于重排无阻塞型架构，即当有新的输入‑输出端口连接建立时，所有路径需重新规划、开关单元状态经过重新规划后可以满足全部连接需求。相较于严格无阻塞型网络架构，Benes网络的规模更小、路由时经过的级数更少。得益于Benes网络架构带来的器件低损耗、小尺寸，其在光交换网络结构中得到了广泛应用，但是此网络架构下的路径切换算法较为复杂，因此需要重点关注。
[0003] 鉴于此，来自贝尔实验室的D. C. Opferman等人提出了环路路由算法（Looping Alogorithm），此路由算法的基本思路是先确定边缘级的开关状态，再依次确定内部次级的开关状态，直至中间级。但是此算法是基于假设某开关单元状态前提的，如果假设错误就需要回溯改正，算法复杂度极高。在此基础上，A. Karimi等人提出了输入输出路由算法（Input and Output Routing Algorithm），此算法解决了冲突回溯问题，但是其仅能工作在满配置情况，即所有输入、输出端口均使用的情况下算法才可正常工作，缺少了灵活性和多场景情况下的可用性。A. Chakrabarty等人提出的分离路由算法（Division Routing Algorithm）采用填写开关单元表的方案可实现任意端口配置情况下的路径选择，但是其在特殊的路径选择情况下仍会面临冲突回溯问题。
[0004] 除此之外，上述路由算法方案均未考虑网络单元存在故障的情况，而实际应用中由于开关单元设计不理想、配套控制电路及电封装不连通情况将会导致路由方案的阻塞率上升，极大影响网络交换性能。
发明内容
[0005] 为解决现有技术的不足，本发明提供的一种面向Benes网络的低复杂度避障路由方法及装置，能够部署在任意规模的Benes网络中，针对不同的端口配置情况均无需执行冲突回溯，大幅降低了算法复杂度，针对各种问题带来的个别开关单元损坏或性能不理想情况，能够有效降低路由方案的阻塞率，提升了网络交换的性能和稳定性，本发明采用如下的技术方案：
[0006] 一种面向Benes网络的低复杂度避障路由方法，Benes网络是由一组开关单元构成的阵列，多个阵列依次嵌套，各阵列均包括输入层、输出层，以及输入层和输出层之间的两个子网，各阵列输入层分别与该阵列的两个子网的输入端连接，各阵列的输出层分别与该阵列的两个子网的输出端连接，各输入层、各输出层及各子网分别包括多个成阵列排列的多个开关单元，各开关单元均为2*2输入‑输出开关单元，当前层阵列的各子网分别嵌套有一个下一层阵列，对于各阵列，该阵列的输入层作为该阵列的边缘级输入层，该阵列的输出层作为该阵列的边缘级输出层，所述方法包括如下步骤：
[0007] 由嵌套的外层向中心方向，对各阵列，依次执行如下操作，直至达到嵌套最内部的中间级阵列：
[0008] 步骤S1，对所述阵列进行故障单元分析，根据分析结果，判定两个所述子网的连接优先级；
[0009] 步骤S2，根据输入层的输入端口与输出层输出端口的连接关系以及两个所述子网的连接优先级，构建输入层的输入端口、输出层的输出端，以及两个所述子网的连接优先级的关联关系；
[0010] 步骤S3，根据关联关系，确定作为边缘级的输入层中各开关单元的开关状态和作为边缘级的输出层中各开关单元的开关状态，所述开关状态为交叉状态或平行状态；
[0011] 步骤S4，根据作为边缘级的输入层的开关状态和作为边缘级的输出层的开关状态，进行两个所述子网的路径更新，以更新两个所述子网中的输入‑输出端口的连接关系，以确定后续内部开关单元状态；
[0012] 步骤S5，判断输入‑输出端口连接情况是否达到中间级，若达到，则确定中间级开关单元状态并结束流程；若未达，则将次边缘级作为最新的边缘级，并分析此时的输入‑输出端口连接情况，返回步骤S1。从Benes网络看，最初的边缘级是输入层和输出层，次边缘级是子网的边缘级，即子网左右两列开关单元，边缘级是从两侧向中间层层递进，每一层都通过该层输入端和输出端及其对应的子网优先级避开故障多的子网，从而替身了网络交换的性能和稳定性。
[0013] 进一步地，所述步骤S1具体包括：
[0014] 确定所述阵列中，子网故障单元的数量以及边缘级故障单元的数量，其中所述子网故障单元包括对应子网中处于故障的开关单元，所述边缘级故障单元包括所述阵列中输入层包括的处于故障的开关单元以及所述阵列中输出层包括的处于故障的开关单元；根据所述阵列中，子网故障单元的数量和边缘级故障单元的数量，判定两个所述子网的连接优先级，作为子网连接情况表填写的优先级，其中，子网故障单元少的子网，优先级更高；当子网故障单元数相同时，边缘级故障单元少的子网，优先级更高；当子网故障单元数及边缘级故障单元数均相同时，默认或随机指定一个优先级更高的子网。
[0015] 进一步地，所述开关单元包括上、下输入端口，和上、下输出端口，所述两个子网分别为A、B子网，所述步骤S2具体包括：
[0016] 根据输入层的输入端口与输出层输出端口的连接关系，将输入层开关单元的输入端口与输出层开关单元的输出端口建立00、01、10、11的输入‑输出关联关系，其中第一位的0或1对应输入层开关单元的上输入端口或下输入端口，第二位的0或1对应输出层开关单元的上输出端口或下输出端口；根据两个所述子网优先级，通过输入‑输出关联关系，建立A、B、AB、BA的优先级关联关系，A表示该输入‑输出关联关系通过A子网连接，B表示该输入‑输出关联关系通过B子网连接，AB表示一个输入层开关单元的两个输入端口和一个输出层开关单元的两个输出端口完全对应，此时输入‑输出关联关系先通过优先级更高的A子网连接，而后通过B子网连接，BA则相反。在开关单元表填写过程中，通过设计新型的填写方案避免了路径冲突回溯问题，降低了算法复杂度。
[0017] 进一步地，所述步骤S2中，建立开关单元表，用于记录输入层输入端口、输出层输出端口，以及子网连接优先级的关联关系，其中行表示输入层开关单元，列表示输出层开关单元，在寻找下一填写的开关单元过程中，首先判断当前输入层开关单元是否有对应端口需填写；然后判断当前输出层开关单元是否有对应端口需填写；若此开关单元对应的行和列均无需要填写的端口，则按端口输入顺序选择下一要填写的开关单元。
[0018] 进一步地，所述关联关系中00+A，01+A，10+B，11+B，10+AB，11+AB，00+BA，01+BA对应输入层开关单元平行状态，10+A，11+A，00+B，01+B，00+AB，01+AB，10+BA，11+BA对应输入层开关单元交叉状态；其中00+A，10+A，01+B，11+B，01+AB，11+AB，00+BA，10+BA对应输出层开关单元平行状态；01+A，11+A，00+B，10+B，00+AB，10+AB，01+BA，11+BA对应输出层开关单元交叉状态。
[0019] 一种面向Benes网络的低复杂度避障路由装置，包括Benes网络、故障单元分析模块、开关单元表填写模块、开关状态确定模块和子网路径更新模块，Benes网络是由一组开关单元构成的阵列，多个阵列依次嵌套，各阵列均包括输入层、输出层，以及输入层、和输出层之间的两个子网，各阵列的输入层分别与该阵列的两个子网的输入端连接，各阵列的输出层分别与该阵列的两个子网的输出端连接，各输入层、各输出层及各子网分别包括多个成阵列排列的多个开关单元，各开关单元均为2*2输入‑输出开关单元，当前层阵列的各子网分别嵌套有一个下一层阵列，对于各阵列，该阵列的输入层作为该阵列的边缘级输入层，该阵列的输出层作为该阵列的边缘级输出层；
[0020] 由嵌套的外层向中心方向，对各阵列，依次循环调用如下模块，直至达到嵌套最内部的中间级阵列：
[0021] 所述故障单元分析模块，对所述阵列进行故障单元分析，根据分析结果，判定两个所述子网的连接优先级；
[0022] 所述开关单元表填写模块，根据输入层的输入端口与输出层的输出端口连接关系以及两个所述子网的连接优先级，构建输入层的输入端口、输出层的输出端，以及两个所述子网的连接优先级的关联关系；
[0023] 所述开关状态确定模块，根据关联关系，确定作为边缘级的输入层中各开关单元的开关状态和作为边缘级的输出层中各开关单元的开关状态，所述开关状态为交叉状态或平行状态；
[0024] 所述子网路径更新模块，根据作为边缘级的输入层的开关状态和作为边缘级的输出层的开关状态，进行两个所述子网的路径更新，以更新两个所述子网中的输入‑输出端口的连接关系，以确定后续内部开关单元状态。
[0025] 进一步地，所述开关单元包括上、下输入端口，和上、下输出端口，所述两个子网分别为A、B子网，所述开关单元表填写模块，通过构建开关单元表，建立输入层的输入端口与输出层的输出端口的连接关系，以及两个所述子网的连接优先级，其中开关单元表的行表示输入层单元开关，列表示输出层单元开关，开关单元表包括输入‑输出端口表和子网连接情况表。
[0026] 进一步地，所述输入‑输出端口表，根据输入层的输入端口与输出层的输出端口的连接关系，将输入层开关单元的输入端口与输出层开关单元的输出端口建立00、01、10、11的输入‑输出关联关系，并在输入‑输出端口表的行列交叉处进行填写，其中第一位的0或1对应输入层开关单元的上输入端口或下输入端口，第二位的0或1对应输出层开关单元的上输出端口或下输出端口。
[0027] 进一步地，所述子网连接情况表，根据两个所述子网的优先级和输入‑输出关联关系，在行列交叉处填写相应的优先级关联关系A、B、AB、BA，A表示该输入‑输出关联关系通过A子网连接，B表示该输入‑输出关联关系通过B子网连接，AB表示一个输入层开关单元的两个输入端口和一个输出层开关单元的两个输出端口完全对应，此时输入‑输出关联关系先通过优先级更高的A子网连接，而后通过B子网连接，BA则相反。
[0028] 进一步地，所述开关单元构成的阵列为交叉开关矩阵，所述开关状态确定模块根据开关单元表，确定交叉开关矩阵的交叉/平行状态，所述关联关系中00+A，01+A，10+B，11+B，10+AB，11+AB，00+BA，01+BA对应输入层开关单元平行状态，10+A，11+A，00+B，01+B，00+AB，01+AB，10+BA，11+BA对应输入层开关单元交叉状态；其中00+A，10+A，01+B，11+B，01+AB，11+AB，00+BA，10+BA对应输出层开关单元平行状态；01+A，11+A，00+B，10+B，00+AB，10+AB，
01+BA，11+BA对应输出层开关单元交叉状态。
[0029] 本发明的优势和有益效果在于：
[0030] 本发明的一种面向Benes网络的低复杂度避障路由方法及装置，基于分离路由算法，通过设计新型的开关单元填写方案，解决了分离路由算法面临的冲突回溯问题，大幅降低了路由算法复杂度；针对开关单元故障问题，通过子网故障单元分析模块判定子网连接优先级，可有效避免损坏或性能不理想的开关单元、降低路由方案阻塞率，提升了网络交换的性能和稳定性。
附图说明
[0031] 图1是本发明实施例中避障路由方法的流程图。
[0032] 图2是本发明实施例中16x16 Benes网络阵列图。
[0033] 图3是本发明实施例中16x16情况下开关单元表。
[0034] 图4是本发明实施例中避障路由装置的结构图。
[0035] 图5是本发明实施例中16x16 Benes网络输入‑输出端口连接情况与故障单元位置图。
[0036] 图6是本发明实施例中非避障路由算法下路由图。
[0037] 图7是本发明实施例中开关单元输入‑输出端口表。
[0038] 图8是本发明实施例中开关单元子网连接情况表。
[0039] 图9是本发明实施例中边缘级开关单元状态图。
[0040] 图10是本发明实施例中避障路由算法下路由图。
具体实施方式
[0041] 以下结合附图对本发明的具体实施方式进行详细说明。应当理解的是，此处所描述的具体实施方式仅用于说明和解释本发明，并不用于限制本发明。
[0042] 如图1所示，一种面向Benes网络的低复杂度避障路由方法，Benes网络是由一组开关单元构成的阵列，如图2所示，多个阵列依次嵌套，各阵列均包括输入层、输出层，以及输入层和输出层之间的A、B两个子网，各阵列的输入层分别与该阵列的两个子网的输入端连接，各阵列的输出层分别与该阵列的两个子网络的输出端连接，各输入层、各输出层及各子网分别包括多个成阵列排列的多个开关单元，各开关单元均为2*2输入‑输出开关单元，当前层阵列的各子网分别嵌套有一个下一层阵列，对于各阵列，该阵列的输入层作为该阵列的边缘级输入层，该阵列的输出层作为该阵列的边缘级输出层，A、B两个子网通过边缘级（含输入层和输出层）开关单元状态确定，方法包括如下步骤：
[0043] 步骤S1，对所述阵列进行故障单元分析，根据分析结果，判定两个所述子网的连接优先级；
[0044] 确定所述阵列中，子网故障单元的数量以及边缘级故障单元的数量，其中所述子网故障单元包括对应子网中处于故障的开关单元，所述边缘级故障单元包括所述阵列中输入层包括的处于故障的开关单元以及所述阵列中输出层包括的处于故障的开关单元；根据所述阵列中，子网故障单元的数量和边缘级故障单元的数量，判定两个所述子网的连接优先级，作为子网连接情况表填写的优先级，其中，子网故障单元少的子网，优先级更高；当子网故障单元数相同时，边缘级故障单元少的子网，优先级更高；当子网故障单元数及边缘级故障单元数均相同时，默认或随机指定一个优先级更高的子网。
[0045] 具体地，根据子网故障单元统计和子网边缘级故障单元统计情况，来判定下一步骤中子网络连接情况表填写优先级。其中，故障单元较少的子网在填写子网络连接情况表时，优先级更高，当子网中故障单元相同时，边缘级故障单元较少的子网，在填写子网络连接情况表时优先级更高。若二者均相同，则默认A子网优先级高于B子网。
[0046] 步骤S2，根据输入层的输入端口与输出层输出端口的连接关系以及两个所述子网的连接优先级，构建输入层的输入端口、输出层的输出端，以及两个所述子网的连接优先级的关联关系；
[0047] 开关单元包括上、下输入端口，和上、下输出端口，两个子网分别为A、B子网，根据输入‑输出端口连接情况，将输入层开关单元的输入端口与输出层开关单元的输出端口建立00、01、10、11的输入‑输出关联关系，其中第一位的0或1对应输入层开关单元的上输入端口或下输入端口，第二位的0或1对应输出层开关单元的上输出端口或下输出端口；根据子网优先级，通过输入‑输出关联关系，建立A、B、AB、BA的优先级关联关系，A表示该输入‑输出关联关系通过A子网连接，B表示该输入‑输出关联关系通过B子网连接，AB表示一个输入层开关单元的两个输入端口和一个输出层开关单元的两个输出端口完全对应，此时输入‑输出关联关系先通过优先级更高的A子网连接，而后通过B子网连接，BA则相反。
[0048] 建立开关单元表，用于记录输入层输入端口、输出层输出端，以及子网连接优先级的关联关系，其中行表示输入层单元开关，列表示输出层单元开关，在寻找下一填写的开关单元过程中，首先判断当前输入层开关单元是否有对应端口需填写；然后判断当前输出层开关单元是否有对应端口需填写；若此开关单元对应的行和列均无需要填写的端口，则按端口输入顺序选择下一要填写的开关单元。
[0049] 具体地，根据输入‑输出端口连接情况分别填写边缘级开关单元输入‑输出端口表和子网连接情况表，如图3所示的16x16情况下填写的开关单元表，所填写的表格位置表明了输入、输出层开关单元的连接情况。如图2所示每个开关单元包含两个输入端口和两个输出端口，分别连接A、B两个子网，根据输入输出端口为开关单元的上端口或下端口，分别在如图3所示的输入‑输出端口表填写00、01、10、11。其中第一位的0或1对应输入层开关单元的输入端口的上端口或下端口，第二位的0或1对应输出层开关单元的输出端口的上端口或下端口。同理，根据步骤S1中的子网优先级情况，在如图3所示的子网连接情况表填写A、B、AB、BA，需注意，由于边缘级开关单元的输入、输出，分别连接A、B两个子网，因此，子网连接情况表中每一行每一列均不存在两个A或两个B的情况，其中若一个输入层开关单元的两个端口和一个输出层开关单元的两个端口对应则会出现AB或BA元素，AB表示子网连接情况表中某个方格对应的输入、输出开关之间，先选用了优先级更高的子网A，由于输入、输出开关均有两个端口，且另个端口分别连接A、B两个子网，因此，之后同样的开关单元只能选择子网B，BA则反之。需注意，在寻找下一要填写的开关单元过程中，首先判断当前输入层开关单元是否有对应端口需填写（即图3中的一行）；然后判断当前输出层开关单元是否有对应端口需填写（即图3中的一列）；若此开关单元对应的行和列均无需要填写的端口，则按端口输入顺序选择下一要填写的开关单元。
[0050] 步骤S3，根据关联关系，确定作为边缘级的输入层中各开关单元的开关状态和作为边缘级的输出层中各开关单元的开关状态，所述开关状态为交叉状态或平行状态；
[0051] 开关状态包括交叉/平行（Cross/bar）状态，其中00+A，01+A，10+B，11+B，10+AB，11+AB，00+BA，01+BA对应输入层开关单元平行状态，10+A，11+A，00+B，01+B，00+AB，01+AB，10+BA，11+BA对应输入层开关单元交叉状态；其中00+A，10+A，01+B，11+B，01+AB，11+AB，00+BA，10+BA对应输出层开关单元平行状态；01+A，11+A，00+B，10+B，00+AB，10+AB，01+BA，11+BA对应输出层开关单元交叉状态。
[0052] 具体地，根据上一步骤中得到的边缘级开关单元输入‑输出端口表和子网连接情况表，确定边缘级开关单元状态。其中00+A，01+A，10+B，11+B，10+AB，11+AB，00+BA，01+BA对应输入层开关单元Bar状态，其中，对于输入层开关单元只考虑输入端口，即第一位的0或1，及后面选取的子网络，例如：第一位为0时，对应子网络为A，第一位为1时，后面子网络对应B，此外，涉及AB、BA的状态，例如：11+AB，由于子网连接情况表的数据采用覆盖的方式进行填写，A状态被B状态覆盖了，因此此处的11+AB状态相当于11+B，BA状态的情况也类似；10+A，11+A，00+B，01+B，00+AB，01+AB，10+BA，11+BA对应输入层开关单元Cross状态；其中00+A，10+A，01+B，11+B，01+AB，11+AB，00+BA，10+BA对应输出层开关单元Bar状态；01+A，11+A，00+B，10+B，00+AB，10+AB，01+BA，11+BA对应输出层开关单元Cross状态。
[0053] bar状态是指横向输入连接到纵向输出，纵向输入连到横向输出；cross状态是指横向输人连接到横向输出，纵向输人连接到纵向输出。
[0054] 步骤S4，根据作为边缘级的输入层的开关状态和作为边缘级的输出层的开关状态，进行两个所述子网的路径更新，以更新两个所述子网中的输入‑输出端口的连接关系，以确定后续内部开关单元状态；
[0055] 具体地，根据输入‑输出端口连接情况，及步骤S3得到的边缘级开关单元状态，更新子网路径情况，即子网中的输入‑输出端口连接情况。
[0056] 步骤S5，判断输入‑输出端口连接情况是否达到中间级，若达到，则确定中间级开关单元状态并结束流程；若未达，则将次边缘级作为最新的边缘级，并分析此时的输入‑输出端口连接情况，返回步骤S1。
[0057] 如图4所示，一种面向Benes网络的低复杂度避障路由装置，包括Benes网络、故障单元分析模块、开关单元表填写模块、开关状态确定模块和子网路径更新模块，Benes网络是由一组开关单元构成的阵列，包括输入层、输出层，以及输入、输出层之间的两个子网，输入层分别与两个子网的输入端连接，输出层分别与两个子网的输出端连接；开关单元包括上、下输入端口，和上、下输出端口，所述两个子网分别为A、B子网；开关单元构成的阵列为交叉开关矩阵。
[0058] 所述故障单元分析模块，用于判定子网连接优先级。
[0059] 所述开关单元表填写模块，根据输入‑输出端口连接情况和子网连接优先级，构建输入层输入端口、输出层输出端，以及子网连接优先级的关联关系；开关单元表填写模块，通过构建开关单元表，建立输入层输入端口、输出层输出端，以及子网连接优先级的关联关系，其中开关单元表的行表示输入层单元开关，列表示输出层单元开关，开关单元表包括输入‑输出端口表和子网连接情况表。输入‑输出端口表，根据输入‑输出端口连接情况，在行列交叉处填写相应的输入‑输出关联关系00、01、10、11，其中第一位的0或1对应输入层开关单元的上输入端口或下输入端口，第二位的0或1对应输出层开关单元的上输出端口或下输出端口。网连接情况表，根据子网优先级和输入‑输出关联关系，在行列交叉处填写相应的优先级关联关系A、B、AB、BA，A表示该输入‑输出关联关系通过A子网连接，B表示该输入‑输出关联关系通过B子网连接，AB表示一个输入层开关单元的两个输入端口和一个输出层开关单元的两个输出端口完全对应，此时输入‑输出关联关系先通过优先级更高的A子网连接，而后通过B子网连接，BA则相反。
[0060] 所述开关状态确定模块，根据关联关系，确定作为边缘级的输入层、输出层开关状态；开关状态确定模块根据开关单元表，确定交叉开关矩阵的交叉/平行状态，其中00+A，01+A，10+B，11+B，10+AB，11+AB，00+BA，01+BA对应输入层开关单元平行状态，10+A，11+A，00+B，01+B，00+AB，01+AB，10+BA，11+BA对应输入层开关单元交叉状态；其中00+A，10+A，01+B，11+B，01+AB，11+AB，00+BA，10+BA对应输出层开关单元平行状态；01+A，11+A，00+B，10+B，00+AB，10+AB，01+BA，11+BA对应输出层开关单元交叉状态。
[0061] 所述子网路径更新模块，根据开关状态，进行子网路径更新，更新子网中的输入‑输出端口连接情况，以确定后续内部开关单元状态；若输入‑输出端口连接情况达到中间级，则确定中间级开关单元状态；若未达，则将次边缘级作为最新的边缘级，并分析此时的输入‑输出端口连接情况，返回故障单元分析模块。
[0062] 在本发明实施例中，提供一种面向16x16 Benes网络非满配置、存在特定故障情况下的实施方案，如图5所示，标记了故障单元位置与非满配置情况下的输入‑输出端口连接情况（(0,3),(2,14),(3,1),(13,5)）。当未部署故障单元分析模块时，即采用非避障路由算法时得到的路由如图6所示，由于路由路径上存在两个故障单元，极大影响了网络交换的性能和稳定性。
[0063] 当采用本发明的低复杂度避障路由方法时，首先分析子网故障单元数与子网边缘级故障单元数来确定子网连接优先级。如图5所示，在确定边缘级开关状态时，A、B子网中的故障单元数相同，由于A子网对应边缘级故障单元数多，因此填写开关单元表时B子网优先级高于A子网。根据边缘级开关单元表填写方案得到的开关单元输入‑输出端口表和子网连接情况表，分别如图7、图8所示，表中相应行、列填充元素表明使用了对应位置的边缘级（输入、输出层）开关单元。在此之后，可根据输入‑输出端口表和子网连接情况表的元素填写情况得到如图9所示的边缘级（第一级与第七级）开关单元状态，其中0表示开关单元未使用、1表示开关单元为Bar状态、2表示开关单元为Cross状态。根据输入‑输出端口情况和边缘级开关状态，得到次边缘级（第二级和第六级）的输入‑输出端口情况。由于此时输入‑输出端口连接情况尚未达中间级（第四级），因此需要将次边缘级视为边缘级并针对不同子网络重复上述步骤，最终本发明的避障路由方法得到的路由图如图10所示，得到的路由方案可以避免所标记的故障单元，解决了此前路由方案面临的阻塞问题，提升了网络交换的性能和稳定性。
[0064] 以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的范围。
