A method of batching conflict routings in shuffle-exchange networks

作者：Zhang Yi Hao^*; Shen Yue Hong; Dong Min; Jiang Yi Min

来源：Theoretical Computer Science, 2014, 522: 24-33.

DOI：10.1016/j.tcs.2013.12.003

• Covering function
• Eigenfunction
• Least no-conflict routing grouping
• Maximal no-conflict routing group
• Shuffle-exchange network

In order to resolve the problem of separating conflict routings in shuffle-exchange networks, we define the concepts of the maximal no-conflict routing group and the least no-conflict routing grouping (LNCRG), as well as an associated eigenfunction and covering function. Based on these concepts, we propose a theoretical and practical method of computing the LNCRG using Boolean algebra. In addition, an algorithm for approximately computing the LNCRG is put forward to improve the efficiency of batching routings. Our theoretical analysis and experiments show that the time efficiency and accuracy of the algorithm are excellent. The proposed method provides strong support for the batching of routing policies in large-scale information exchanges.

• 出版日期2014-2-20
• 单位中国人民解放军陆军工程大学