Time and space sliced non-blocking network switching fabric

Details Time and space sliced non-blocking network switching fabric Time and space sliced non-blocking network switching fabric

1998-12-16

2003-07-08

Vanderpuye, Ken (Department: 2661)

Multiplex communications

Pathfinding or routing

Store and forward

C370S395710, C370S412000, C370S413000

Reexamination Certificate

active

06590900

ABSTRACT:

TECHNICAL FIELD
This invention is directed to an expandable data switching fabric using a shared memory architecture. Data is commutated with respect to both space and time to facilitate input and output of multiple high speed switched data streams without data loss.
BACKGROUND
Considerable attention has been devoted to the study of interconnection networks. See, for example, T. Feng., “A Survey of Interconnection Networks”, IEEE Computer, December 1991, pp. 12-27. Several network topologies have been proposed for designing parallel computers and computer communication networks.
A static interconnection network is characterized by point-to-point links which connect various nodes based upon a given structure. Common examples of static interconnection network topologies include bus, ring, mesh, crossbar, tree, hypercube and hypercycle topologies. Many static interconnection networks are multi-stage networks having no central or shared memory for storing the data which passes through the network. Additionally, most static interconnection networks have statically allocated resources for switching data through the network.
Typically, data is passed through a prior art static interconnection network by time-dividing the data path into a number of discrete sub-paths, with each sub-path being used during a specific, corresponding time slice. See, for example, U.S. Pat. Nos. 3,956,593; 4,005,272; and, 4,038,497. By contrast, the present invention passes data by dynamically allocating the network's data switching resources and by time-dividing the data such that the entire data path can be used during all time slices.
Another prior art approach uses a shared memory architecture. Typically, a content-addressable central, shared memory is used, but without commutation. See, for example, U.S. Pat. No. 5,513,134. Prior art techniques for commutation of switched data have also been devised, as exemplified by U.S. Pat. No. 5,168,492. However, the '492 patent uses a rotator to commutate the data, whereas the present invention employs a barrel shifter and commutates the data with respect to both space and time.
SUMMARY OF INVENTION
In accordance with the preferred embodiment, the invention provides a method of switching n data streams for input and output of the data streams by an n input, n output data store without data loss. This is accomplished by dividing the data store into n separate storage arrays and dividing each of the data streams into n equal-sized pieces. Then, during each one of n separate time units, one of the data stream pieces is written into a corresponding one of the storage arrays; or, one of the data stream pieces is read from a corresponding one of the storage arrays.
Preferably, for each data stream, during each time unit i, where 1≦i≦n, an i
th
data stream piece is written into an i
th
one of the storage arrays, or an i
th
piece is read from an i
th
storage array. During each j
th
time unit, where 1≦j≦n, one data stream piece P
ij
is written into an i
th
storage array, or one piece P
ij
is read from an i
th
storage array.
Advantageously, before the writing or reading step, each data stream is shifted in log
2
n separate stages, with each shifting stage respectively comprising shifting each one of the data streams by:
2
(log
2
n)
−1
bits in the first shifting stage;
2
(log
2
n)
−2
bits in the second shifting stage; . . . ; and,
1 bit in the n
th
shifting stage.
The invention further provides apparatus for switching n data streams for input and output of the data streams without data loss. The apparatus incorporates an n input, n output data store subdivided into n separate storage arrays; means for dividing each data stream into n equal-sized pieces and for writing each piece into a corresponding one of the storage arrays during each one of n separate time units; and, means for reading each written piece from the respective storage arrays during each one of another n separate time units and for combining the read pieces to reform a corresponding one of the data streams.
The means for dividing the data streams and for writing the pieces, and the means for reading the written pieces and for combining the read pieces, may each comprise a shifting means for shifting each data stream in log
2
n separate stages, with each shifting stage respectively comprising shifting each one of the data streams by:
2
(log
2
n)
−1
bits in the first shifting stage;
2
(log
2
n)
−2
bits in the second shifting stage; . . . ; and,
1 bit in the n
th
shifting stage.


REFERENCES:
patent: 3956593 (1976-05-01), Collins et al.
patent: 4005272 (1977-01-01), Collins et al.
patent: 4038497 (1977-07-01), Collins et al.
patent: 5168492 (1992-12-01), Beshai et al.
patent: 5513134 (1996-04-01), Cooperman et al.
patent: 6111880 (2000-08-01), Rusu et al.
patent: 6233245 (2001-05-01), Chapman et al.
patent: 6243382 (2001-06-01), O'Neill et al.
T. Feng, “A Survey of Interconnection Networks”, IEEE Computer, Dec. 1981, pp. 12-27.

Affiliated with

Also associated with

Rating

Time and space sliced non-blocking network switching fabric does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Time and space sliced non-blocking network switching fabric, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time and space sliced non-blocking network switching fabric will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3100817