US5440549A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Broadband multi-channel switch with multicasting capability
Assignee: Washington University in St. Louis
•
Filing: 1993-04-22
•
Granted: 1995-08-08
•
Expires: 2013-04-22
Abstract
Abstract A multi-channel, multicasting switch for an ATM network utilizes a particular nonblocking condition of the Flip Network, which is exploited to realize a multi-channel switching architecture that supports an arbitrary number of channel groups. Using a single Flip Network recursively, the resulting architecture becomes efficient in the sense that the crosspoint complexity is O(N log 2 N) for N inputs. The number of times the Flip Network is used recursively is a function of the number of channel groups only. The architecture is internally nonblocking and bufferless. Distinguishing features are the abilities to provide multicasting, super-rate switching (i.e., rates that exceed the capacity of a single channel are accommodated), multi-rate switching (i.e., bit pipes of different rates are supported simultaneously), multiple performance requirements (i.e., services with different performance requirements are treated accordingly), and fairness (i.e., cells originating from different input channels and/or destined for different output channels are treated fairly). In multi-channel switching, cells belonging to a single session can traverse over multiple channels and the architecture maintains cells in order by assigning a specific Gray code to each data cell in each group.
Inventors
- 👤 Paul S. Min
- 👤 Hossein Saidi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 23:01
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/10; H04L49/104; H04L49/105; H04L49/106; H04L49/15; H04L49/1553; H04L49/20; H04L49/201; H04L49/203; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5678; H04L2012/5681
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
112 words
A non-blocking switch for an ATM network having: a plurality of inputs for connection to a plurality of inputs channels over which a plurality of data cells arrive in a sequence; a plurality of outputs over which said data cells are routed to a plurality of output channels; said plurality of output channels being grouped into a plurality of channel groups; and means for processing said data cells from said inputs to at least one of said channel groups, said processing means including means for maintaining the sequence of said data cells as they are processed to thereby ensure their sequence is the same as they leave said switch through said outputs.
Claim 2
Dependent Claim
112 words
A non-blocking switch for an ATM network having: a plurality of inputs for connection to a plurality of inputs channels over which a plurality of data cells arrive in a sequence; a plurality of outputs over which said data cells are routed to a plurality of output channels; said plurality of output channels being grouped into a plurality of channel groups; and means for processing said data cells from said inputs to at least one of said channel groups, said processing means including means for maintaining the sequence of said data cells as they are processed to thereby ensure their sequence is the same as they leave said switch through said outputs.
Claim 3
Dependent Claim
40 words
The switch of claim 1 wherein said sequence maintaining means includes means for assigning each data cell an output in its corresponding channel group, if an output is available, and means for storing said data cells into said channel groups.
Claim 4
Dependent Claim
14 words
The switch of claim 2 wherein said processing means comprises at least one NBGN.
Claim 5
Dependent Claim
14 words
The switch of claim 3 wherein said processing means comprises a plurality of NBNG's.
Claim 6
Dependent Claim
34 words
The switch of claim 3 wherein said sequence maintaining means further comprises means for recycling said data cells through said NBNG to thereby sort said data cells into a greater number of channel groups.
Claim 7
Dependent Claim
51 words
The switch of claim 5 wherein said sorting means has means for sorting said data cells into two channel groups so that said data cells are sorted into 2 r channel groups by being recycled through said NBNG, where r equals the number of cycles required to separated said channel groups.
Claim 8
Dependent Claim
34 words
The switch of claim 6 wherein each of said NBNGs has an output and further comprising a buffer at each NBNG output to separate in time each cycle of data cells through said NBNG.
Claim 9
Dependent Claim
52 words
The switch of claim 7 wherein the number of switch inputs equals a factor C times the number of input channels, where C equals a positive integer, and further comprising a buffer at the input of each NBNG and means for delivering the output of said output buffer to said switch inputs.
Claim 10
Dependent Claim
20 words
The switch of claim 2 wherein said assigning means includes means for assigning said outputs in a Gray code order.
Claim 11
Dependent Claim
32 words
The switch of claim 1 wherein said sequence maintaining means includes means for ordering the data cells within each time period according to their input channel and according to their time period.
Claim 12
Dependent Claim
26 words
The switch of claim 10 wherein said processing means includes means for maintaining said data cell ordering as said data cells are processed through said switch.
Claim 13
Dependent Claim
28 words
The switch of claim 1 further comprising means for multicasting at least a selected one of said input channels to a selected plurality of said output channel groups.
Claim 14
Dependent Claim
26 words
The switch of claim 12 wherein said multicasting means includes a second means for maintaining the sequence of said data cells as they are processed therethrough.
Claim 15
Dependent Claim
15 words
The switch of claim 13 wherein said multicasting means includes means for recycling data cells.
Claim 16
Dependent Claim
30 words
The switch of claim 13 wherein said multicasting means includes an NBGN, said NBNG having two groups of inputs, one of said input groups being reserved for recycled data cells.
Claim 17
Dependent Claim
33 words
The switch of claim 15 wherein said second sequence maintaining means includes means for ordering the data cells within each time period according to their input channel and according to their time period.
Claim 18
Dependent Claim
37 words
The switch of claim 16 wherein said second sequence maintaining means includes means for ordering the data cells appearing at said recycled data cell input group before the other of said group of inputs to said NBGN.
Claim 19
Dependent Claim
37 words
The switch of claim 17 wherein said multicasting means includes means for sorting the data cells into a plurality of services classes, said service classes determining the priority for processing of said data cells through said switch.
Claim 20
Dependent Claim
18 words
The switch of claim 18 wherein said sorting means includes means for recycling data cells through an NBGN.
Claim 21
Dependent Claim
33 words
In a non-blocking multi-channel switch for an ATM network, the improvement comprising an NBGN and means for successively recycling all data cells through said NBGN to sort said data cells into multiple groups.
Claim 22
Dependent Claim
33 words
In a non-blocking multi-channel switch for an ATM network, the improvement comprising an NBGN and means for successively recycling all data cells through said NBGN to sort said data cells into multiple groups.
Claim 23
Dependent Claim
13 words
The switch of claim 20 wherein said switch comprises a single IC chip.
Claim 24
Dependent Claim
29 words
In a multi-channel switch for an ATM network, the improvement comprising a plurality of NBGN's connected in cascade for sorting all data cells into a plurality of channel groups.
Claim 25
Dependent Claim
29 words
In a multi-channel switch for an ATM network, the improvement comprising a plurality of NBGN's connected in cascade for sorting all data cells into a plurality of channel groups.
Claim 26
Dependent Claim
13 words
The switch of claim 22 wherein said switch comprises a single IC chip.
Claim 27
Dependent Claim
88 words
A multi-channel packet switch for an ATM network for switching data cells between a plurality of switch inputs and a plurality of switch outputs, said switch comprising a multicast phase having means for copying said data cells and a routing phase connected to an output of said multicast phase for routing said data cells to selected ones of said switch outputs, each of said multicast phase and said routing phase having means for maintaining said data cells in the same sequence as they are processed through said switch.
Claim 28
Dependent Claim
88 words
A multi-channel packet switch for an ATM network for switching data cells between a plurality of switch inputs and a plurality of switch outputs, said switch comprising a multicast phase having means for copying said data cells and a routing phase connected to an output of said multicast phase for routing said data cells to selected ones of said switch outputs, each of said multicast phase and said routing phase having means for maintaining said data cells in the same sequence as they are processed through said switch.
Claim 29
Dependent Claim
21 words
The switch of claim 24 wherein each of said multicast phase and said routing phase have means for recycling data cells.
Claim 30
Dependent Claim
48 words
The switch of claim 25 wherein each of said sequence maintaining means including means for ordering said data cells with respect to the physical location of the switch inputs over which they appear, and means for maintaining said ordering as said data cells are processed through said switch.
Claim 31
Dependent Claim
25 words
The switch of claim 26 wherein each of said multicase phase and said routing phase further comprise means for multi-channel switching of said data cells.
Claim 32
Independent Claim
102 words
A method for implementing multicasting in a packet switch for an ATM network, said packet switch including a switch fabric having a plurality of inputs and a plurality of outputs, said switch fabric including means for routing a plurality of data cells from said inputs to said outputs, the method comprising the steps of: determining which data cells are to be multicast to a plurality of destinations; comparing the number of copies of data cells required with the capacity of a copy network; and recycling all data cells through said switch fabric which require copies in excess of said copy network capacity.
Claim 33
Independent Claim
102 words
A method for implementing multicasting in a packet switch for an ATM network, said packet switch including a switch fabric having a plurality of inputs and a plurality of outputs, said switch fabric including means for routing a plurality of data cells from said inputs to said outputs, the method comprising the steps of: determining which data cells are to be multicast to a plurality of destinations; comparing the number of copies of data cells required with the capacity of a copy network; and recycling all data cells through said switch fabric which require copies in excess of said copy network capacity.
Claim 34
Dependent Claim
51 words
The method of claim 28 wherein the recycling step includes the steps of: recycling said data cells whose number of requested copies exceeds the remaining capacity of the copy network remaining at the time of recycling; and continuing the comparison of the other data cells with the remaining copy network capacity.
Claim 35
Dependent Claim
26 words
The method of claim 29 further comprising the steps of: maintaining said data cells in time ordered sequence as they are routed through said switch fabric.
Claim 36
Dependent Claim
50 words
The method of claim 30 wherein the step of maintaining data cell sequence further comprises the steps of: ordering said data cells with respect to the physical location of the switch inputs over which they appear; and maintaining said ordering as said data cells are processed through said switch fabric.
Claim 37
Independent Claim
76 words
A method for sorting data cells in a non-blocking, multi-channel ATM switch for routing to one of up to 2 K output channel groups, said switch for having up to 2 K groups of output channels, the method comprising the steps of: sorting said data cells K times, K being a positive integer greater than 1, each sort dividing said data cells into two groups; and routing said sorted data cells to said output channel groups.
Claim 38
Independent Claim
76 words
A method for sorting data cells in a non-blocking, multi-channel ATM switch for routing to one of up to 2 K output channel groups, said switch for having up to 2 K groups of output channels, the method comprising the steps of: sorting said data cells K times, K being a positive integer greater than 1, each sort dividing said data cells into two groups; and routing said sorted data cells to said output channel groups.
Claim 39
Dependent Claim
26 words
The method of claim 32 further comprising the steps of: maintaining said data cells in time ordered sequence as they are sorted and routed through switch.
Claim 40
Dependent Claim
26 words
The method of claim 33 wherein the sorting step further comprises sorting said data cells with the same sorting means for each of said K times.
Claim 41
Dependent Claim
36 words
The method of claim 34 wherein the step of sequence maintaining further comprises the step of ordering said data cells with respect to a physical location of the switch inputs over which said data cells appear.
References Cited (Backward Citations)
US4813038A
Cited
US4893304A
Cited
US4899335A
Cited
US4896934A
Cited
US5005167A
Cited
US5148428A
Cited
US5034946A
Cited
US5119368A
Cited
US5103444A
Cited
US5172371A
Cited
US5220664A
Cited
US5216668A
Cited
US5305311A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-07 | 1999-02-06 | 1999-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-07 | 2003-02-06 | 2003-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-07 | 2007-02-06 | 2007-08-08 | $7700.00 | Window Closed / Lapsed |