Search

The existence of parallel node-disjoint paths between any pair of nodes is a desirable property of interconnection networks, because such paths allow tolerance to node and/or link failures along some of the paths, without causing disconnection. Additionally, node-disjoint paths support high-throughput communication via the concurrent transmission of parts of a message. We characterize maximum-sized families of parallel paths between any two nodes of alternating group networks. More specifically, we establish that in a given alternating group network AN, there exist n−1 parallel paths (the maximum possible, given the node degree of n−1) between any pair of nodes. Furthermore, we demonstrate that these parallel paths are optimal or near-optimal, in the sense of their lengths exceeding the internode distance by no more than four. We also show that the wide diameter of AN is at most one unit greater than the known lower bound D+1, where D is the network diameter. [ABSTRACT FROM AUTHOR]

Abstract-An optical transpose interconnection system (OTIS) network with n[sup2] nodes is a two-level swapped architecture built of n of an n-nodes basis network that constitute its clusters. A simple rule for intercluster connectivity (node j in cluster i connected to node i in cluster j, for all i ≠ j) leads to regularity, modularity, packageability, fault tolerance, and algorithmic efficiency of the resulting networks. We prove that an OTIS (swapped) network with a connected basis network posses maximal fault tolerance, regardless of whether its basis network is maximally fault tolerant. We also show how the corresponding maximal number of node-disjoint paths between two nodes of a swapped network can be algorithmically, constructed in a manner that is independent of the existence and construction of node-disjoint paths within its basis network. Our results complement previous studies that show swapped networks inheriting some desirable properties (e.g., Hamiltonicity) from their basis networks. Here, we show that the swapped connectivity actually introduces a desirable property that may not exist in the basis network. Furthermore, our general result about maximal connectivity and the corresponding node-disjoint path construction for swapped networks replace a number of proofs and constructions in the literature for specific basis networks and obviate the need for proving maximal fault tolerance and dealing with node-disjoint path constructions for many other basis networks of potential practical interest. Additionally, we use our parallel path constructions to establish that the fault diameter and wide diameter of an OTIS network is no more than 4 units greater than its diameter. [ABSTRACT FROM AUTHOR]