Stage specific dilation in multi-stage interconnection networks

Details Stage specific dilation in multi-stage interconnection networks Stage specific dilation in multi-stage interconnection networks

1999-12-20

2004-04-20

Nguyen, Hanh (Department: 2662)

Multiplex communications

Pathfinding or routing

Through a circuit switch

C370S400000, C370S419000, C370S389000

Reexamination Certificate

active

06724758

ABSTRACT:

BACKGROUND
Interconnection networks are commonly used in many different applications, such as connection of internal lines in very large-scale integration (VLSI) circuits, wide area computer networks, backplane lines, system area networks, telephone switches, internal networks for asynchronous transfer mode (ATM) switches, processor/memory interconnects, interconnection networks for multicomputers, distributed shared memory mulitprocessors, clusters of workstations, local area networks, metropolitan area networks, and networks for industrial applications, as noted in page 1 of the book entitled “Interconnection Networks An Engineering Approach” by Jose Duato, Sudhakar Yalamanchili and Lionel Ni, published by IEEE Computer Society Press, Los Alamitos, Calif. 1997, which book is incorporated by reference herein in its entirety.
Examples of ATM switches are described in, for example, U.S. Pat. Nos. 5,898,688, 5,898,687, 5,734,656, 5,726,985, 5,668,812, and 5,610,921 each of which is incorporated by reference herein in its entirety. Moreover, the following three books: (1) by A. S. Acampora, entitled “An Introduction to Broadband Networks” published by Plenum Press, in 1994, (2) by R. Perlman, entitled “Interconnections: Bridges and Routers” published by Addison-Wesley, in 1992, and (3) by P. E. Green, entitled “Network Interconnection and Protocol Conversion” published by IEEE Press, in 1988 are each incorporated by reference herein in their entirety.
One group of interconnection networks, known as “multistage interconnection networks” (MINs) connect input ports of a network to output ports through a number of stages of switches, where each switch is a crossbar network. The crossbar network is normally configured by a central controller that establishes a path from an input port to an output port. However, in asynchronous multiprocessors, centralized control and permutation routing are infeasible, and a routing algorithm is used to establish a path across the multiple stages, as noted in the above-described book at pages 19-20.
Also as noted in the above-described book at page 19, although many MINs have an equal number of input and output ports, “[t]hese networks can also be configured with the number of inputs greater than the number of outputs (concentrators) and vice versa (expanders).” One example of such an MIN uses crossbar routing switches having an equal number of inputs and outputs, although the number of logically equivalent outputs in each direction can be greater than one, as described in an article entitled “Multipath Fault Tolerance in Multistage Interconnection Networks” by Fred Chong, Eran Egozy, Andre DeHon and Thomas Knight, Jr., MIT Transit Project, Transit Note #48, 1991-1993, available from the Internet at http://www.ai.mit.edu/projects/transit/tn48/tn48.html, which article is incorporated by reference herein in its entirety. As illustrated in an unlabeled figure (the figure on page 3) in the just-described article, “[a] multipath MIN [is] constructed from 4×2 (inputs×radix) dilation-2 crossbars and 2×2 dilation-1 crossbars. Each of the 16 endpoints has two inputs and outputs for fault tolerance. Similarly, the routers each have two outputs in each of their two logical output directions. As a result, there are many paths between each pair of network endpoints.”
Note that the MIN of the just-described article appears to be limited to fault tolerance, because the article states (under the heading “Routing” on page 4) “[o]ur fault tolerance results described below are independent of the details of routing and fault identification. That is, routing can be circuit-switched or packet-switched using any number of routing strategies. The fault tolerance results only depend on network topology and the routers' ability to use their redundant connection in each logical direction to avoid faults.” Note also that the just-described MIN was implemented using “[a]n RN1 routing component [that] can be configured to act as a single 8-input, radix 4, dilation 2 routing component or as a pair of independent 4-input, radix-4, dilation 1 routing components.”
The above-described article states (under the heading “Dilated Non-Interwired Network” on page 4) that “dilated networks . . . connect all outputs in a given logical direction to the same physical routing component in the subsequent stage of the network. The topology is thus identical to the corresponding non-dilated bidelta network. . . . Such networks gain performance by having multiple paths.” Moreover, the article states (under the heading “Discussion” on page 16) “[a]lthough we have concentrated upon the fault tolerance of multipath networks, these networks also perform well under unbalanced loading. Intuitively, the effects of hot-spots are very similar to component failures.”
See also the following articles each of which is incorporated by reference herein in its entirety: (1) Clyde P. Kruskal and Marc Snir, “The Performance of Multistage Interconnection Networks for Multiprocessors” published in
IEEE Transactions on Computers
, C-32(12):1091-1098, December 1983; (2) Clyde P. Kruskal and Marc Snir, “A Unified Theory of Interconnection Network Structure” published in
Theoretical Computer Science
, pages 75-94, 1986; (3) Robert Grondalski, “A VLSI Chip Set for Massively Parallel Architecture” published in
IEEE International Solid-State Circuits Conference
, pages 198-199, 1987; and (4) K. Y. Eng et al., “A Growable Packet (ATM) Switch Architecture: Design Principles and Applications” published in
IEEE Transactions on Communications
, vol. 40, No. 2, Feb. 1992, pp. 423-430.
SUMMARY
In accordance with the invention, an apparatus and method increase the data rate(s) in one or more portions (also called “later portions”) of a communications network, while maintaining a normal data rate in one or more other portions (also called “earlier portions”) that supply traffic to the just-described later portion(s). Depending on the implementation, a later portion that is being speeded up can include an intermediate stage or the final stage of a multistage interconnection network (MIN), or can include two or more such stages (also called “later stages”). Therefore, speed up in only a portion of a MIN is implemented depending on location of the portion relative to input ports of the MIN. The just-described MIN is preferably of the connection-less type (e.g. packet-switched or cell-switched), although connection-oriented MINs (e.g. circuit-switched) can also be differentially speeded-up.
Stage specific speed-up of a MIN reduces (or even avoids) traffic contention that otherwise occurs when a disproportionate amount of traffic temporarily travels to a common destination. At the same time, stage specific speed-up reduces costs that are otherwise incurred when all portions of a MIN are speeded up. Therefore, a network that is speeded up in only a later portion (also referred to as “differentially-speeded-up network”; e.g. having a normal speed initial stage and a speeded-up final stage) has the advantage of reducing traffic contention, while being less expensive than a network that is speeded-up in all portions.
In one embodiment, stage-specific speed up (wherein only later portions are speeded up) is used in a MIN that has at least two stages: an earlier stage to supply traffic (regardless of destination) to a later stage, wherein the later stage converges the traffic based on destination. Speed-up of a later portion of a MIN can be implemented by clocking a line faster in one or more output ports of a stage, as compared to an input port of the same stage. Alternatively, the speed-up can be implemented by providing one or more additional lines in a stage's output ports (so an output port has lines greater in number than lines in an input port of the same stage). Note that the just-described additional lines carry different traffic, as opposed to multiple lines in a fault tolerant MIN that are used in a redundant manner to carry the

Affiliated with

Also associated with

Rating

Stage specific dilation in multi-stage interconnection networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Stage specific dilation in multi-stage interconnection networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stage specific dilation in multi-stage interconnection networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3225440