Self-routing control mechanism over multistage interconnection networks of concentrators Number:7,065,073 from the United States Patent and Trademark Office (PTO) owispatent Application of the technique of statistical line grouping to banyan-type networks to practically alleviate the problems of output contention, traffic fluctuation, burstiness, and so forth without incurring additional preprocessing and buffering on the input traffic by introducing alternate-routing ingredient to the unique-routing banyan-type network, but does not complicate the switching control too much through alternate routing. The concentrator composed of interconnected routing cells is employed to fill in each of the dilated nodes of the banyan-type network to give a hybrid network. An extremely simple self-routing control mechanism over the hybrid network which is the natural melting of the self-routing control inside the concentrators and the self-routing control over the banyan-type network is presented.<H interconnection, concentrators, Self, routing, co, 7065073.html, Patent, pto, 7065073

Title: Self-routing control mechanism over multistage interconnection networks of concentrators

Abstract: Application of the technique of statistical line grouping to banyan-type networks to practically alleviate the problems of output contention, traffic fluctuation, burstiness, and so forth without incurring additional preprocessing and buffering on the input traffic by introducing alternate-routing ingredient to the unique-routing banyan-type network, but does not complicate the switching control too much through alternate routing. The concentrator composed of interconnected routing cells is employed to fill in each of the dilated nodes of the banyan-type network to give a hybrid network. An extremely simple self-routing control mechanism over the hybrid network which is the natural melting of the self-routing control inside the concentrators and the self-routing control over the banyan-type network is presented.

Patent Number: 7,065,073 Issued on 06/20/2006 to Li

Inventors: Li; Shuo-Yen Robert (Hong Kong, HK)
Assignee: Industrial Technology Research Institute (Hsinchu, TW)

Appl. No.: 882328

Filed: June 15, 2001

Current U.S. Class: 370/369 ; 370/395.2; 709/244

Current International Class: H04Q 11/00 (20060101)

Field of Search: 370/390,411,388,380,395.41,369,360,375,389,395.32,395.2 709/238-244

References Cited [Referenced By]

U.S. Patent Documents


4523273	June 1985	Adams et al.
4623996	November 1986	McMillen
4852091	July 1989	Li
4899334	February 1990	Shimizu
4905225	February 1990	Francois et al.
4945534	July 1990	Driscoll et al.
4955017	September 1990	Eng et al.
4970507	November 1990	Cooperman et al.
5123011	June 1992	Hein et al.
5148428	September 1992	Lee
5166926	November 1992	Cisneros et al.
5184346	February 1993	Kozaki et al.
5216668	June 1993	Zhang
5299317	March 1994	Chen et al.
5303383	April 1994	Neches et al.
5353283	October 1994	Tsuchiya
5367518	November 1994	Newman
5367520	November 1994	Cordell
5369635	November 1994	Gandini et al.
5371495	December 1994	Sturges et al.
5396231	March 1995	Hein
5426733	June 1995	Masui
5450074	September 1995	Yoshifuji
5451936	September 1995	Yang et al.
5471628	November 1995	Phillips et al.
5483541	January 1996	Linsky
5500858	March 1996	McKeown
5506840	April 1996	Pauwels et al.
5517495	May 1996	Lund et al.
5541914	July 1996	Krishnamoorthy et al.
5566179	October 1996	Kobayashi et al.
5568477	October 1996	Galand et al.
5583861	December 1996	Holden
5600630	February 1997	Takano et al.
5602844	February 1997	Lyles
5623698	April 1997	Stephenson et al.
5671222	September 1997	Chen et al.
5689505	November 1997	Chiussi et al.
5689506	November 1997	Chiussi et al.
5724349	March 1998	Cloonan et al.
5724351	March 1998	Chao et al.
5768270	June 1998	Ha-Duong
5802052	September 1998	Venkataraman
5809021	September 1998	Diaz et al.
5841775	November 1998	Huang
5852407	December 1998	Ishii et al.
5859846	January 1999	Kim et al.
5896371	April 1999	Kobayashi et al.
5940389	August 1999	Yang et al.
5949778	September 1999	Abu-Amara et al.
5963554	October 1999	Song
5987028	November 1999	Yang et al.
6052373	April 2000	Lau
6058112	May 2000	Kerstein et al.
6067298	May 2000	Shinohara
6081512	June 2000	Muller et al.
6157643	December 2000	Ma
6160806	December 2000	Cantwell et al.
6215786	April 2001	Larson et al.
6219349	April 2001	Kobayashi et al.
6259699	July 2001	Opalka et al.
6307854	October 2001	Webb
6335930	January 2002	Lee
6370155	April 2002	Cantwell et al.
6400708	June 2002	Bartholomew et al.
6427037	July 2002	Okayama
6473827	October 2002	McMillen et al.
6493347	December 2002	Sindhu et al.
6501757	December 2002	Kamaraj et al.
6553031	April 2003	Nakamura et al.
6556725	April 2003	Kondo et al.
6563819	May 2003	Park
6563837	May 2003	Krishna et al.
6600741	July 2003	Chrin et al.
6611519	August 2003	Howe
6621828	September 2003	Field et al.
6628651	September 2003	Ryan et al.
6647017	November 2003	Heiman
6657998	December 2003	Li
6714562	March 2004	Calvignac et al.
6721324	April 2004	Shinohara
6735203	May 2004	Heiman
6747971	June 2004	Hughes et al.
6757281	June 2004	Irish
6757282	June 2004	Ofek
6798777	September 2004	Ferguson et al.
6829237	December 2004	Carson et al.
6834038	December 2004	Zelig et al.
6850524	February 2005	Troxel et al.
2002/0018475	February 2002	Ofek et al.
2002/0031124	March 2002	Li
2002/0176526	November 2002	Mejia

Other References

Szymanski, "Design Principles for Pratical Self-Routing Nonblocking Switching Networks with O(NLogN) Bit-Complexity", IEEE, May 17, 1997, pp. 1057-1069. cited by examiner .
Szymanski, "Randomized Routing of Virtual Connections in Essentially Nonblocking Log N-Depth Networks", IEEE, Feb. 15, 1994, pp. 2521-2531. cited by examiner .
"Access and Alignment of Data in an Array Processor", by Lawrie, IEEE Trans. on Computers, vol. c-24, No. 12, Dec., 1975 pp. 1145-1155. cited by other .
"The Knockout Switch: A Simple, Modular Architecture for High-Performance Packet Switching", by Yeh et. al, IEEE Journal on Selected Comm, vol. SAC-5, No. 8, Oct. 1987, pp. 274-282. cited by other .
"Optimal, Multi-Stage Interconnection by Divide-and-Conquer Networks", by Li, Proc. of Second IASTED Conf, Dec. 1998, pp. 318-323. cited by other.

Primary Examiner: Pezzlo; John
Attorney, Agent or Firm: Akin Gump Strauss Hauer & Feld, LLP

Parent Case Text

CROSS-REFERENCE TO RELATED APPLICATION

This application is a non-provisional application of provisional application Ser. No. 60/212,333 filed Jun. 16, 2000.

Claims

What is claimed is:

1. A method for self-routing a packet through a b2.sup.n.times.b2.sup.n switching network comprising configuring the switching network with (a) 2.sup.n output groups, each of the output groups having a distinct binary address in the form of b.sub.1b.sub.2 . . . b.sub.n with b indistinguishable output ports, and (b) k super-stages of concentrators wherein each of the concentrators is a 2b.times.2b partial sorting network of interconnected routing cells and b of its 2b output ports are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, the network being characterized by the guide .gamma.(1), .gamma.(2), . . . , .gamma.(k), where y is a mapping from the set {1, 2, . . . , k}to the set {1, 2, . . . n}, and wherein the packet is either a real data packet destined for the output group at the binary destination address d.sub.1d.sub.2 . . . d.sub.n, or an idle packet having no pre-determined destination, generating a routing tag 1d.sub..gamma.(1)d.sub..gamma.(2) . . . d.sub..gamma.(k) for the real data packet with reference to the guide of the network and the destination address of the packet, and routing the real data packet through the network by using 1d.sub..gamma.(j) in the routing tag in the j-th super-stage concentrator, 1.ltoreq.j.ltoreq.k, to select between the 0-output group or the 1-output group of the j-th super-stage concentrator to emit the real data packet.

2. A method for self-routing a packet through a b2.sup.n.times.b2.sup.n switching network, the network: including 2.sup.n output groups, each of the output groups having a distinct binary address in the form of b.sub.1b.sub.2 . . . b.sub.n with b indistinguishable output ports, and k super-stages of concentrators wherein each of the concentrators is a 2b.times.2b partial sorting network of interconnected routing cells and b of its 2b output ports are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group; and being characterized by the guide .gamma.(1), .gamma.(2), . . . , .gamma.(k), where y is a mapping from the set {1, 2, . . . , k}to the set {1, 2, . . . , n}, and wherein the packet is either a real data packet destined for the output group at the binary destination address d.sub.1d.sub.2 . . . d.sub.n, or an idle packet having no pre-determined destination, the method comprising generating the routing tag 1d.sub..gamma.(1)d.sub..gamma.(2) . . . d.sub..gamma.(k) for the real data packet with reference to the guide of the network and the destination address of the packet, and routing the real data packet through the network by using 1d.gamma.(j) in the routing tag in the j-th super-stage concentrator, 1.ltoreq.j.ltoreq.k, to select between the 0-output group or the 1-output group of the j-th super-stage concentrator to emit the real data packet.

3. A method for self-routing a plurality of real data packets through a b2.sup.n.times.b2.sup.n switching network, the switching network being characterized by the guide .gamma.(1), .gamma.(2), . . . , .gamma.(k) where y is a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, and having (a) b2.sup.n external input ports, (b) 2.sup.n output groups, each of the output groups having a distinct binary address in the form of b.sub.1b.sub.2 . . . , b.sub.n with b indistinguishable output ports, and (c) k super-stages of 2b-to-b concentrators wherein each of the concentrators is a 2b.times.2b partial sorting network of interconnected routing cells where each of the routing cells is a sorting cell associated with the partial order "10 (`0-bound`)00 (`idle`)11 (`1-bound`)", b of the 2b output ports of each of the concentrators are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, and extra circuitry arranged at the output end of each of the concentrators wherein the extra circuitry is composed of 2b parallel 1.times.1 switching elements, one at each of the output ports of the concentrator, and each of the real data packets arriving at a distinct external input port determining an active input port and destined for an output group at the binary destination address d.sub.1d.sub.2 . . . d.sub.n, the method comprising generating an idle packet as a stream of `0` bits at each of the non-active external input ports, generating a routing tag 1d.sub..gamma.(1)d.sub..gamma.(2) . . . d.sub..gamma.(k) for each of the real data packets with reference to the guide of the network and the destination address of the packet, generating a routing tag which is a string of k+1 `0` bits for each of the idle packets, routing the real data packets and the idle packets through the network by sorting the packets by the 2b-to-b concentrators of the network, wherein the sorting at each of the concentrators includes the sorting at each of the sorting cells of the concentrator such that the sorting is with respect to the associated partial order and is based upon the leading two bits, which are either `10` or `11` for a real data packet, or `00` for an idle packet, of the routing tag of each of the two packets arrived at each of the sorting cells, and processing the routing tag of each of the packets by the extra circuitry at the output end of the concentrator before the said each of the packets exits from the j-th super-stage concentrator by removing the second leading bit from the routing tag or rotating the second leading bit to the end of the routing tag such that the leading two bits of the routing tag of each of the packets at each of the j-th super-stage concentrators, 1.ltoreq.j.ltoreq.k, are always `1d.sub..gamma.(j)` or `00`.

4. The method as recited in claim 3 wherein the real data packets are classified into 2.sup.r priority classes, r.gtoreq.1, wherein each of the priority classes is coded in an r-bit string p.sub.1p.sub.r, and the generating of a routing tag for each of the real data packets includes generating 1d.sub..gamma.(1)p.sub.1 . . . p.sub.rd.sub..gamma.(2) . . . d.sub..gamma.(k) as the routing tag.

5. The method as recited in claim 3 wherein the generating of a routing tag for each of the idle packets includes generating a string of k+r+1 `0` bits as the routing tag.

6. The method as recited in claim 3 wherein each of the priority classes is coded in an r-bit string p.sub.1 . . . p.sub.r, the generating of a routing tag for each of the real data packets includes generating 1d.sub..gamma.(1)p.sub.1 . . . p.sub.rd.sub..gamma.(2) . . . d.sub..gamma.(k) as the routing tag, the sorting at each of the sorting cells of the concentrator based upon the two leading bits of the routing tag includes using the priority code p.sub.1 . . . p.sub.r as the tiebreaker, and processing the routing tag includes generating the routing tag such that the leading r+2 bits of the routing tag of each of the real data packets at each of the j-th super-stage concentrators, 1.ltoreq.j.ltoreq.k, is `1d.sub..gamma.(j)p.sub.1 . . . p.sub.r`.

7. The method as recited in claim 3 wherein the real data packets are classified into 2.sup.r priority classes r.gtoreq.1, wherein each of the priority classes is coded in an r-bit string p.sub.1 . . . p.sub.r, the generating of a routing tag for each of the real data packets includes generating 1d.sub..gamma.(1)p.sub.1 . . . p.sub.rd.sub..gamma.(2) . . . d.sub..gamma.(k) as the routing tag, the generating of a routing tag for each of the idle packets includes generating a string of k+r+1 `0` bits as the routing tag, the sorting at each of the sorting cells of the concentrator based upon the two leading bits of the routing tag includes using the priority code p.sub.1 . . . p.sub.r as the tiebreaker, and processing the routing tag includes removing the second leading bit from the routing tag or rotating the second leading bit to the end of the routing tag, and rotating the r-bit priority code p.sub.1 . . . p.sub.r to the position behind the next bit originally following the priority code in the routing tag such that the leading r+2 bits of the routing tag of each of the packets at each of the j-th super-stage concentrators, 1.ltoreq.j.ltoreq.k, are always `1d.sub..gamma.(j)p.sub.1 . . . p.sub.r` or `00 . . . 0`.

8. The method as recited in claim 3 wherein the routing of packets includes changing the leading two bits of the routing tag of a misrouted packet into the new value "01" at the output end of a 2b-to-b concentrator at a super-stage upon output contention, and using the new value throughout the remaining stages, and the sorting at each of the sorting cells of each of the concentrator is with respect to the partial order "10 (`0-bound`)0x (`idle` or `misrouted`)11 (`1-bound`)".

9. The method as recited in claim 3 wherein the routing of the real data packets includes blocking misrouted packets at the output end of each of the 2b-to-b concentrators upon output contention.

10. The method as recited in claim 9 wherein the blocking of the misrouted packets includes turning each of the misrouted packets into a string of `0` bits as an idle packet.

11. A system for self-routing a packet comprising a b2.sup.n.times.b2.sup.n switching network, the switching network having (a) 2.sup.n output groups, each of the output groups having a distinct binary address in the form of b.sub.1b.sub.2 . . . b.sub.n with b indistinguishable output ports, and (b) k super-stages of concentrators wherein each of the concentrators is a 2b.times.2b partial sorting network of interconnected routing cells and b of its 2b output ports are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, the network being characterized by the guide .gamma.(1), .gamma.(2), . . . , .gamma.(k), where .gamma. is a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, and wherein the packet is either a real data packet destined for the output group at the binary destination address d.sub.1d.sub.2 . . . d.sub.n, or an idle packet having no pre-determined destination, routing tag circuitry for generating a routing tag 1d.sub..gamma.(1)d.sub..gamma.(2) . . . d.sub..gamma.(k) for the real data packet with reference to the guide of the network and the destination address of the packet, and routing control circuitry for routing the real data packet through the network by using 1d.sub..gamma.(j) in the routing tag in the j-th super-stage concentrator, 1.ltoreq.j.ltoreq.k, to select between the 0-output group or the 1-output group of the j-th super-stage concentrator to emit the real data packet.

12. A system for self-routing a plurality of real data packets comprising a b2.sup.n.times.b2.sup.n switching network having a plurality of 2b-to-b concentrators interconnected into a k-stage bit-permuting network characterized by guide .gamma.(1), .gamma.(2), . . . , .gamma.(k) where .gamma. is a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, and having (a) b2.sup.n external input ports, (b) 2.sup.n output groups, each of the output groups having a distinct binary address in the form of b.sub.1b.sub.2 . . . b.sub.n with b indistinguishable output ports, and (c) k super-stages of 2b-to-b concentrators wherein each of the concentrators is a 2b.times.2b partial sorting network of interconnected routing cells where each of the routing cells is a sorting cell associated with the partial order "10 (`0-bound`)<00 (`idle`)<11 (`1-bound`)", b of the 2b output ports of each of the concentrators are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, and extra circuitry arranged at the output end of each of the concentrators wherein the extra circuitry is composed of 2b parallel 1.times.1 switching elements, one at each of the output ports of the concentrator, and wherein each of the real data packets arrives at a distinct external input port and is destined for an output group at the binary destination address d.sub.1d.sub.2 . . . d.sub.n, idle-packet-generating circuitry, coupled to the external input ports, for generating an idle packet as a stream of `0` bits at each of the external input ports of the switching network if no real data packet arrived at that external input port, routing tag circuitry, coupled to the external input ports, for generating a routing tag 1d.sub..gamma.(1)d.sub..gamma.(2) . . . d.sub..gamma.(k) for each of the real data packets with reference to the guide of the network and the destination address of the packet, or generating a routing tag which is a string of k+1 `0` bits for each of the idle packets, routing control circuitry, coupled to the concentrators, for routing the real data packets and the idle packets through the network by sorting the packets by the 2b-to-b concentrators of the network, wherein the sorting at each of the concentrators includes the sorting at each of the sorting cells of the concentrator where the sorting is with respect to the associated partial order and is based upon the leading two bits, which are either `10` or `11` for a real data packet, or `00` for an idle packet, of the routing tag of each of the two packets arrived at the cell, and extra circuitry at the output end of the j-th super-stage concentrator, 1.ltoreq.j.ltoreq.k, for processing the routing tag of each of the packets before the said each of the packets exits from the j-th super-stage concentrator by removing the second leading bit from the routing tag or rotating the second leading bit to the end of the routing tag such that the leading two bits of the routing tag of each of the packets at each of the j-th super-stage concentrators, 1.ltoreq.j.ltoreq.k, are always `1d.sub..gamma.(j)` or `00`.

13. The system as recited in claim 12 wherein the real data packets are classified into 2.sup.r priority classes, r.gtoreq.1, wherein each of the priority classes is coded in an r-bit string p.sub.1 . . . p.sub.r, and the routing tag circuitry for each of the real data packets includes means for generating 1d.sub..gamma.(1)p.sub.1 . . . p.sub.rd.sub..gamma.(2) . . . d.sub..gamma.(k) as the routing tag.

14. The system as recited in claim 12 wherein the idle-packet-generating circuitry includes means for generating a string of k+r+1 `0` bits as the routing tag.

15. The system as recited in claim 12 wherein each of the priority classes is coded in an r-bit string p.sub.1 . . . p.sub.r, the routing tag circuitry for each of the real data packets includes means for generating 1d.sub..gamma.(1)p.sub.1 . . . p.sub.rd.sub..gamma.(2) . . . d.sub..gamma.(k) as the routing tag, the routing control circuitry includes means using the priority code p.sub.1 . . . p.sub.r as the tiebreaker, and the extra circuitry includes means for generating the routing tag such that the leading r+2 bits of the routing tag of each of the real data packets at each of the j-th super-stage concentrators, 1.ltoreq.j.ltoreq.k, is `1d.sub..gamma.(j)p.sub.1 . . . p.sub.r`.

16. The system as recited in claim 12 wherein the real data packets are classified into 2.sup.r priority classes, r.gtoreq.1, wherein each of the priority classes is coded in an r-bit string p.sub.1 . . . p.sub.r, the routing tag circuitry generates 1d.sub..gamma.(1)p.sub.1 . . . p.sub.rd.sub..gamma.(2) . . . d.sub..gamma.(k) as the routing tag for each of the real data packets, and a string of k+r+1 `0` bits as the routing tag for each of the idle packets, the routing control circuitry includes means for sorting the two arriving packets based upon the two leading bits of the routing tags of the two packets using the ensuing priority code p.sub.1 . . . p.sub.r as the tiebreaker, and the extra circuitry at the output end of the concentrator processes the routing tag of each of the packets before the said each of the packets exits from the j-th super-stage concentrator by removing the second leading bit from the routing tag or rotating the second leading bit to the end of the routing tag, and rotating the r-bit priority code p.sub.1 . . . p.sub.r to the position behind the next bit originally following the priority code in the routing tag such that the leading r+2 bits of the routing tag of each of the packets at each of the j-th super-stage concentrators, 1.ltoreq.j.ltoreq.k, are always `1d.sub..gamma.(j)p.sub.1 . . . p.sub.r` or `00 . . . 0`.

17. The system as recited in claim 12 wherein the switch includes delay elements in the 2b-to-b concentrator for maintaining the synchronization of the packets across the stage.

18. The system as recited in claim 12 wherein the extra circuitry at the output end of each of the 2b-to-b concentrators changes the leading two bits of the routing tag of a misrouted packet into the new value "01" at a super-stage upon output contention, and the new value is used throughout the remaining stages, and each of the sorting cells of each of the concentrators is associated with the partial order "10 (`0-bound`)0x (`idle` or `misrouted`)11 (`1-bound`)".

19. The system as recited in claim 18 wherein the switch includes annihilators of misrouted packets at the output end of each of the 2b-to-b concentrators.

Description

BACKGROUND OF THE DISCLOSURE

1. Field of the Invention

This invention relates generally to broadband switching and, more particularly, to the design of the sub-microsecond switching and control over a massive broadband switching network.

2. Description of the Background Art

As telecommunication systems have evolved, the demand for bandwidth has been ever increasing in both transmission and switching. Advances in fiber optics afford ample transmission capacity, while switching--the technology that puts transmission capacity to flexible use--has not kept pace. Because the scale of a switching fabric is subject to various constraints (e.g., electronic or physical), a large switch is often constructed from the networking of smaller ones. Thus, for example, the public switched telephone network is an interconnection of numerous switch offices; likewise, the core of the modern digital switching system is typically a multi-stage network of smaller switches. Most important, in this modern era of broadband communications, countless primitive switching units inside a single chip are integrated into a large switch. Massive integration of switching components has been a fertile area of research and exploratory development efforts.

The results of such efforts are generally ad hoc in nature, without rigorous underpinnings; such underpinnings, when uncovered, lead to general elucidating principles and, accordingly, more efficient implementations of switching networks follow naturally from the principles. In this way, known but specific industrial designs and/or commercial applications are understood as merely special cases of a broad array of cases. From another viewpoint, sporadic findings in the literature translate into instances of different special cases of the general principles.

By way of a heuristic example of the benefit of uncovering foundational principles, a switching network at a microscopic level is first considered to illustrate the foregoing observations. It is known in the art that efficacious control over a packet switching network composed of nodes is effected whenever the switching decision at each node is determined only by information carried in each local input data packet to the node; such a control mechanism is called "self-routing". The concept of"self-routing" was initially disclosed by D. H. Lawrie in an article entitled "Access and alignment of data in an array processor," as published in IEEE Trans. Comp., vol. 24, pp. 1145 1155, 1975. Lawrie postulated the following in-band control mechanism for a specific banyan-type network (called the Omega network) composed of a cascade of stages wherein each stage is further composed of a number of two-input/two-output switching cells: upon entering the network, a data packet composed of a sequence of bits is prepended with its binary destination address in the form d.sub.1d.sub.2 . . . d.sub.n. The bit d.sub.j indicates the preference between the only two outputs of a stage-j switching cell and is consumed by the stage-j switching control. Thus, the switching state of a cell is determined by just this leading bit of each of the two input packets. The existing self-route mechanism used in this particular banyan-type network considered by Lawrie is ad hoc, that is, determination of the routing tag of a packet is one of trial-and-error. The main reason behind the trial-and-error procedure is that Lawrie has not had the benefit of a fundamental theoretical approach to determine the routing tag for self-routing, as covered in the sequel by the inventive subject matter in accordance with the present invention. The theoretical underpinnings are founded upon the concept of "guide of a bit-permuting network", which is a sequence of numbers, whereby the guide ensures that the routing tag for any given bit-permuting network can be determined once the guide of that network is computed. As will be shown, the guide of the networks studied by Lawrie happens to be a special case wherein the guide is the monotonically increasing 1, 2, . . . , n. The destination address can no longer be used as the routing tag for any other banyan-type network whose guide is not monotonically increasing. For this reason, those banyan-type networks whose routing tag "seems not related" to the destination address have not been widely studied. But, ironically, those widely studied networks, including the Omega network studied by Lawrie, are actually the most anti-optimal ones with regard to the layout complexity under the popular "2-layer Manhattan model with reserved layers" among a huge family of equivalent networks.

The issues of equivalence among networks and optimization of layout complexity brings up a second example highlighting the shortcomings of the past methods. If all those widely studied networks are not optimal, then what networks are optimal and can used to replace the widely studied ones or how to construct such optimal networks in a systematic way need to be explored. The present invention addresses these problems.

All banyan-type networks are equivalent in a weak sense, but in some applications only equivalent networks in a stronger sense can be deployed in replacement of each. A related example of the shortcomings of the existing art is the lack of a systematic way for the adaptation of one network into an equivalent of another in strong senses.

A fourth motivating example, which considers a switching network at a macroscopic level, relates to the properties of a switching network itself. The component complexity of an N.times.N nonblocking network is at least N.sup.2/4 (Here the definition of a nonblocking network requires the network to be unique-routing to begin with, because otherwise there are different senses for a network to be "nonblocking".) The quadratic order in this bound indicates the intrinsically high complexity in the nonblocking property of the network. So instead of applying a nonblocking network in switch design, the focus is on uncovering simple networks that preserves "conditionally nonblocking properties" of switches and thereby construct large conditionally nonblocking switches out of small ones in an economical way. Recursive applications of such construction then leads to conditionally nonblocking switches of indefinitely large sizes. Such theoretical recursive property then allows the physical construction of switching fabric at a throughput level much higher than that of existing routers/switches by the contemporary ASIC technology. In the literature, there are individual instances of certain conditionally nonblocking switches constructed by switching networks, such as the one disclosed by A. Huang and S. Knauer in an article entitled "Starlite: a wideband digital switch," as published in Proceedings of Globecom '84, Atlanta, pp. 121 125, 1984. However, these instances of conditionally nonblocking property are not preserved by simple network and hence do not enjoy the advantage of recursive construction.

Banyan-type networks as recursive applications of 2-stage interconnection or, at least, equivalent to such recursive applications, In contrast with 3-stage alternate-routing switching that is popular in telephony, 2-stage switching network is more compact in nature and thereby facilitates the VLSI implementation of massive recursive application. More importantly, the unique-routing nature of 2-stage switching is more compatible with sub-microsecond control inside a broadband switching chip. A fifth example of deficiency of the existing art is in the systematic method of physical implementation of recursive 2-stage interconnection that takes advantage of today's technologies in making switching fabrics at a much higher level of throughput than all largest existent routers.

The critical problem with 2-stage switching is blocking, and one way to alleviate the blocking problem is by "statistical line grouping", which replaces every interconnection line in the network by a bundle of lines and, at the same time, dilates the size of every node proportionally. A critical issue in applying the method of statistical line grouping lies in the choice of the switch to fill the role of a dilated node. The selected switch does not have to be a nonblocking switch but needs some partial nonblocking property that is articulated in the present invention (Partial nonblocking property is more economically achievable than the full nonblocking property of a switch.) Meanwhile, the control over the selected switch must also be compatible with sub-microsecond control inside a broadband switching chip. Ideally, there should be a self-routing mechanism inside the selected switch that can be smoothly blended with the self-routing mechanism over the banyan-type network. A final example highlighting the shortcomings of the past methods is the lack of a clearly superior candidate for this selected switch. The present invention proposes "concentrator" as a perfect candidate. When multicast switching is involved, then a "multicast concentrator" replaces the concentrator.

SUMMARY OF THE INVENTION

The shortcomings of the prior art, as well as other limitations and deficiencies, are obviated in accordance with the present invention by applying algebraic principles to the physical realization of a large switching fabric based upon contemporary technologies.

In accordance with a broad method aspect of the present invention, a method for self-routing a packet through a b2.sup.n.times.b2.sup.n switching network includes: (a) configuring the switching network with (i) 2.sup.n output groups, each of the output groups having a distinct binary address in the form of b.sub.1b.sub.2 . . . b.sub.n with b indistinguishable output ports, and (ii) k super-stages of concentrators wherein each of the concentrators is a 2b.times.2b partial sorting network of interconnected routing cells and b of its 2b output ports are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, the network being characterized by guide .gamma.(1), .gamma.(2), . . . , .gamma.(k), where .gamma. is a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, and wherein the packet is either a real data packet destined for the output group at the binary destination address d.sub.1d.sub.2 . . . d.sub.n, or an idle packet having no pre-determined destination, (b) generating a routing tag 1d.sub..gamma.(1)d.sub..gamma.(2) . . . d.sub..gamma.(k) for the real data packet with reference to the guide of the network and the destination address of the packet; and (c) routing the real data packet through the network by using 1d.sub..gamma.(j) in the routing tag in the j-th super-stage concentrator, 1.ltoreq.j.ltoreq.k, to select between the 0-output group or the 1-output group of the j-th super-stage concentrator to emit the real data packet.

In accordance with a broad system aspect of the present invention, a system for self-routing a packet includes: (a) a b2.sup.n.times.b2.sup.n switching network, the switching network having (i) 2.sup.n output groups, each of the output groups having a distinct binary address in the form of b.sub.1b.sub.2 . . . b.sub.n with b indistinguishable output ports, and (ii) k super-stages of concentrators wherein each of the concentrators is a 2b.times.2b partial sorting network of interconnected routing cells and b of its 2b output ports are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, the network being characterized by the guide .gamma.(1), .gamma.(2), . . . , .gamma.(k), where .gamma. is a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, and wherein the packet is either a real data packet destined for the output group at the binary destination address d.sub.1d.sub.2 . . . d.sub.n, or an idle packet having no pre-determined destination; (b) routing tag circuitry for generating a routing tag 1d.sub..gamma.(1)d.sub..gamma.(2) . . . d.sub..gamma.(k) for the real data packet with reference to the guide of the network and the destination address of the packet; and (c) routing control circuitry for routing the real data packet through the network by using 1d.sub..gamma.(j) in the routing tag in the j-th super-stage concentrator 1.ltoreq.j.ltoreq.k, to select one between the 0-output group or the 1-output group of the j-th super-stage concentrator to emit the real data packet.

BRIEF DESCRIPTION OF THE DRAWING

The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which:

FIGS. 1A 1H depict eight of the twenty-seven connection states of a 2.times.3 circuit element;

FIGS. 2A B depict the "bar state" and the "cross state" connection states of a switching cell;

FIGS. 2C F depict the four connection states of an expander cell;

FIG. 3A depicts an exemplary interconnection network with three nodes;

FIG. 3B depicts the interconnection network of FIG. 3A wherein the nodes of the network are filled with switching cells to constitute a switch;

FIG. 4 depicts a route through an interconnection network;

FIG. 5A depicts an exemplary routable interconnection network;

FIG. 5B depicts an exemplary switching network wherein the nodes of the network of FIG. 5A are filled with switches, including switching cells and distributors;

FIG. 6A depicts a generic M.times.N k-stage interconnection network illustrating the layout of such a network;

FIG. 6B depicts an exemplary 5.times.4 2-stage interconnection network conforming to the layout of FIG. 6A;

FIG. 6C depicts one illustrative manner of prescribing an external input/output order on a multi-stage network;

FIG. 6D depicts one illustrative manner of splitting the prescribed external input/output order for purposes of linking one multi-stage network to another multi-stage network;

FIG. 6E depicts the results of the product of two 16.times.16 exchanges in one order;

FIG. 6F depicts the results of the product of the same two exchanges in FIG. 6E but in reverse order;

FIG. 7 depicts a 16.times.16 4-stage network as an example of a 2.sup.n.times.2.sup.n multi-stage network where n=4;

FIG. 8 depicts an exemplary plain 2-stage interconnection network with parameters m=2 and n=8;

FIG. 9 depicts the linear addressing scheme on an exemplary 2-stage interconnection network;

FIG. 10 depicts the vector addressing scheme on the same exemplary 2-stage interconnection network as in FIG. 9;

FIG. 11A depicts the manner in which a data signal progresses through a generic 2-stage interconnection network with an output exchange;

FIG. 11B depicts the manner in which a data signal progresses through a generic 2-stage interconnection network with an input exchange;

FIG. 12 depicts an exemplary 2-stage interconnection with an output exchange for a 3.times.5 2-stage interconnection network;

FIG. 13 depicts an exemplary 2-stage interconnection with an input exchange for a 3.times.5 2-stage interconnection network;

FIG. 14 depicts the manner in which "basic building block" networks of 2.times.2, 3.times.3, and 5.times.5 are used in an exemplary recursive 2-stage construction;

FIG. 15 depicts the manner of mapping the recursive 2-stage construction exemplified by FIG. 14 into a binary tree diagram;

FIGS. 16 19 depict the manner of building a recursive 2-stage interconnection with an input exchange from cells;

FIG. 20 depicts the binary tree associated with the recursive construction depicted in FIGS. 16 19;

FIG. 21A depicts a (3 2 1) permutation on an 8.times.8 exchange;

FIG. 21B depicts a (1 2 3) permutation on an 8.times.8 exchange;

FIG. 21C depicts a (3 1) permutation on an 8.times.8 exchange;

FIG. 21D depicts a combined (1 4)(2 3) permutation on an 8.times.8 exchange;

FIG. 22 depicts a network expressed as [id:(4 3 2 1):(1 4 2 3):(3 4):id].sub.4;

FIG. 23 depicts a network expressed as [:(3 2 1):(3 2 1):].sub.3;

FIG. 24 depicts a network expressed