Self-routing control mechanism over multistage interconnection networks of concentrators Number:7,065,073 from the United States Patent and Trademark Office (PTO) owispatent

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