A Class of Odd-Radix Chordal Ring Networks

A Class of Odd-Radix Chordal Ring Networks

Abstract

An n-node network, with its nodes numbered from – ⎣n/2⎦ to ⎡n/2⎤ – 1, is a chordal ring with chord lengths 1 = s0 < s1 < . . . < sk–1 < n/2 when an arbitrary node j (– ⎣n/2⎦ ≤ j < ⎡n/2⎤) is connected to each of the 2k nodes j ± si mod n (0 ≤ i < k) via an undirected link, where “mod” represents (nearly) symmetric residues in [– ⎣n/2⎦, ⎡n/2⎤ – 1]. We study a class of chordal rings in which the chord length si is a power of an odd “radix” r, that is, si = r i, for r = 2a + 1 ≥ 3. We show that this class of chordal rings, with their nodes indexed by radix-r integers using the symmetric digit set [–a, a], are easy to analyze and offer a number of advantages in terms of static network parameters and dynamic performance for many application contexts. In particular, these networks allow a very simple optimal (shortest-path) routing algorithm that generates balanced traffic. We then briefly discuss fault tolerance properties of our networks and point out a number of variations and extensions to the basic structure.

References