The KR-BenesNetwork: AControl-Optimal Rearrangeable Permutation Network

Title: The KR-BenesNetwork: AControl-Optimal Rearrangeable Permutation Network

Research Question: Can we design a more efficient rearrangeable network for routing permutations, especially those with locality properties?

Methodology: The researchers proposed a novel rearrangeable network called the KR-BenesNetwork, which is based on another network called the BenesNetwork. The BenesNetwork has been used for decades in applications like circuit switching and packet routing. The KR-BenesNetwork, however, is control-optimal, meaning it has the lowest control complexity for every input permutation. This network is designed to exploit locality properties of permutations, known as K-boundedness, and is derived by making some small modifications to the BenesNetwork.

Results: The KR-BenesNetwork has a depth of 2 logK + 2 stages and a control complexity of O(NlogK). It is superior to the BenesNetwork from a hardware point of view for K ≤ N/√8 and has a lower control complexity when K ≤ N/√2. The researchers also showed that any optimal network for rearrangeably routing K-bounded permutations must have a depth of at least 2 logK + 1. They provided arguments for conjecturing that the optimal network, in fact, has 2 logK + 2 stages, making the KR-BenesNetwork optimal. Finally, the researchers used the KR-BenesNetwork to derive a permutation-specific control-optimal network for routing arbitrary permutations. Its control complexity is superior to the BenesNetwork in most cases and is bounded by the BenesNetwork in the worst case.

Implications: The KR-BenesNetwork is a significant improvement over the BenesNetwork in terms of control and hardware complexity. It is particularly beneficial for routing permutations with locality properties, which are common in many applications. This could lead to more efficient networking systems and better performance in various fields, such as telecommunications, internet routers, and optical switching.

Link to Article: https://arxiv.org/abs/0309006v1 Authors: arXiv ID: 0309006v1