A Novel Protection Routing Scheme in Recursive Match Networks

Abstract

The recursive match networks (RMNs) represent an important family of communication networks characterized by their regularity and high fault tolerance, including the logic graph of the data center network BCube, the interconnection networks bijective connection (BC) networks, and even potentially other future networks. Protection routing is a key technology to enhance the reliability of communication networks, where dual completely independent spanning trees (dual-CISTs) have garnered significant attention as they suffice to configure a protection routing. In this paper, we propose a novel concept of dual protection routing spanning trees (dual-PRSTs) and demonstrate their application for protection routing construction in RMNs. Compared with dual-CISTs, dual-PRSTs provide more relaxed conditions, allowing for link intersections, internal vertex intersections, and vertices each serving as an inner-vertex in both trees, which are not permitted in dual-CISTs. We show that the research results in this paper are directly applicable to BCube, the BC networks, and other networks that fall within the definition of RMNs. Furthermore, it is proven that as long as a communication network contains dual-PRSTs, they can be utilized to configure a protection routing in it, although the protection routing scheme is conducted in RMNs. Empirical evaluations demonstrate that the protection routing based on dual-PRSTs is not only effective with competitive performance, but also generally outperforms that built with dual-CISTs in terms of path length metrics.