Self-routing permutation networks based on de Bruijn digraphs

Details Self-routing permutation networks based on de Bruijn digraphs Self-routing permutation networks based on de Bruijn digraphs

2000-08-01

2004-04-13

Olms, Douglas (Department: 2661)

Multiplex communications

Pathfinding or routing

Through a circuit switch

C370S369000, C370S380000

Reexamination Certificate

active

06721311

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The field of invention relates to self-routing permutation networks that are scalable and exhibit optimal control and cross-point complexity.
2. Statement of the Problem
In switching networks, inputs and outputs are connected via paths. Different connections utilize different paths. Early switching networks used in telephone switching systems were space-division switching networks where inputs and outputs were connected by physical paths via arrays of relays which acted as cross-points. Switching networks have since greatly evolved, both physically and also in their context. Currently, efficient and low cost switching networks are crucial not only for telecommunication networks, but also for parallel computing where processors and memory modules are connected via fast and efficient switching networks.
With the advance in digital optics, much work on photonic switching architectures have taken place. There are many benefits that can be derived from the use of optics in switching networks. In particular, optical switching networks can provide higher bandwidths, faster connections, and large numbers of connections per optical link (via wavelength division multiplexing—WDM). Optical switching networks also utilize less power than their electronic counterparts. In addition, optical signals are not subject to noise that can corrupt high-frequency signals, allowing optical signals to be more densely packed.
Switching networks can be divided into two groups: fully connected non-blocking networks, and fully connected but blocking networks. Non-blocking switching networks can be further classified into three categories: rearrangeable non-blocking networks, wide-sense non-blocking networks, and strictly non-blocking networks.
A network is classified as rearrangeable if any idle input may be connected to any idle output provided that existing connections are allowed to be rearranged. A strictly non-blocking network on the other hand is always able to connect any idle input to any idle output without interfering with the existing connections. Wide-sense non-blocking network achieves strictly non-blocking property with the help of an algorithm.
In parallel computing, non-blocking networks (also known as permutation networks) can provide the right balance between the processing power of the processing units and the communication bandwidth between them. Collisions are practically non-existent if parallel algorithms are crafted such that data with distinct outputs are produced from the inputs on every cycle. Processing units that are connected to this non-blocking network can be connected quickly to any other processing units in exactly one-network hop, regardless of the physical topology that the processing units (or group of processing units) are emulating.
Crossbar switches, Clos networks and Benes networks are well-known permutation networks. See C. Clos, “A Study of Non-blocking Switching Networks,”
Bell System Technical Journal
, 32, pp. 406-424, 1953 and V. E. Benes, “Permutation Groups, Complexes, and Rearrangeable Multistage Connecting Networks,”
Bell System Technical Journal
, 43, pp. 1619-1640, 1964. The (N×N) crossbar switches have N
2
cross-points and a constant control complexity. The (N×N) 3-stage Clos network has the O(N
{fraction (3/2)}
) cross-point and control complexities. The Benes network, based on (d×d) crossbar switches, has the O(N log
d
N) cross-point and control complexities.
In telecommunications, Broadband Integrated Services Digital Network (B-ISDN), based on Asynchronous Transfer Mode (ATM), is expected to be the fabric of future communication networks. For building large ATM switches, non-blocking Clos network is one of the most popular general architecture used. One of the main reasons that contributes to its popularity is its expandable architecture. A large Clos network can be built by interconnecting small switching modules in a regular pattern. However, the control complexity for the Clos network is high. Some of the hardware controllers for the Clos network have the complexity comparable to that of the switching fabric itself.
Rearrangeable non-blocking networks such as the Benes network uses minimal switching elements with O(N log N) hardware complexity for a network of size N, but require expensive control algorithms to rearrange the switching elements in an attempt to maintain the non-blocking property. The looping algorithm which rearranges switches in the Benes network operates with O(N log N) complexity.
The crossbar switch is an example of a wide-sense non-blocking network. With the aid of a simple control algorithm, crossbar switches can be non-blocking. However, the hardware requirement for crossbar switches is expensive—N
2
cross-points (N×N) crossbar switch.
Strictly non-blocking switching networks such as the 3-stage Clos network requires less hardware (O(N
{fraction (3/2)}
) cross-points) compared to crossbar switches, especially for large N. However, similar to the Benes network, a non-trivial control algorithm is needed to determine the non-blocking routes in the Clos network.
A need exists for a new class of self-routing, packet switched permutation networks. A need exists for a class of rearrangeable non-blocking networks having topologies with minimal hardware cost and optimal control algorithms.
SUMMARY OF INVENTION
The permutation networks of the present invention based on de Bruijn digraphs (i.e., referred to as nD-dBPN where nD=the number n of dimensions D and dBPN is an acronym for “de Bruijn Permutation Network”) solves these needs. The 2D-dBPN de Bruijn digraph has a cross-point complexity comparable to that of the 3-stage Clos network (i.e., O(N log
d
N) but without the complex control algorithm required by the Clos networks). A new class of networks is now set forth exhibiting constant control complexity (wide sense non-blocking) having a constant control complexity (self-routing). The cost in terms of the cross-points used for the new network is an optimal O(N log N). This new self-routing non-blocking network uses fast algorithms to control in the Terabit bandwidth while providing for cost-effective switching.
In addition to having a superior cross-point complexity and a constant control complexity, the new non-blocking network of the present invention also possesses other favorable design properties. The new network also has expandable (i.e., scalable) architecture, i.e., the network can be built by interconnecting smaller non-blocking networks (e.g., small crossbars).


REFERENCES:
patent: 4495615 (1985-01-01), Wilcke
patent: 5134690 (1992-07-01), Samatham
patent: 5218676 (1993-06-01), Ben-Ayed et al.
patent: 5491705 (1996-02-01), Pradhan et al.
patent: 6018523 (2000-01-01), Even
Samsudin and Lee, nD-dBPN: New Self-Routing Permutation Networks Based On the de Bruijn Digraphs, Thesis, Aug. 27, 1998, 8 pages.
Clos, A Study of Non-Blocking Switching Networks, The Bell System Technical Journal, vol. XXXII, Mar. 1953, pp. 126-144.
Goke and Lipovski, Banvan Networks for Partitioning Multiprocessor Systems, The Proceedings of the First Annual Symposium on Computer Architecture, 1973, pp. 100-107.
Benes, Permutation Groups, Complexes, and Rearangeable Connecting Networks, Bell System Technical Journal, 43, No. 4, 1964, pp. 1619-1640.
Sivarajan and Ramaswami, Multiphop Lightwave Networks Based on de Bruijn Graphs, IBM Research Division, 1991, pp. 1001-1011.
Banerjee, Jain, Shah, Regular Multihop Logical Topologies for Lightwave Networks, IEEE, 1999, http://www.comsoc.org/pubs/surveys/1q99issue/banerjee.html, (24 pages).

Affiliated with

Also associated with

Rating

Self-routing permutation networks based on de Bruijn digraphs does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Self-routing permutation networks based on de Bruijn digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-routing permutation networks based on de Bruijn digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3272049