EP0785697A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Multistage network having multicast routing congestion feedback
Assignee: AT&T Inc
•
Filing: 1997-01-07
•
Granted: —
•
Expires: 2017-01-07
Abstract
Abstract Multicasting of an ingress cell received at one of a plurality of input ports is provided through a multistage network to a plurality of output ports. The received ingress cell at a first input port includes a data payload and information identifying one or more routing queues to which a single copy of the data payload is to be outputted. A backpressure queue assignment is identified for the first ingress cell, the backpressure queue assignment identifying a backpressure indicator indicative of the congestion level at at least one routing queue of a subsequent stage. Using the backpressure indicator, it is determined if the first ingress cell is to be outputted from one or more of the routing queues. Thereafter, the first ingress cell is outputted from one or more of the routing queues when the congestion level is below or equal to a first threshold.
Inventors
- 👤 Fabio Massimo Chiussi
- 👤 Vijay Pochampalli Kumar
- 👤 Joseph George Kneuer
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 21:15
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/15; H04L49/1553; H04L49/20; H04L49/201; H04L49/203; H04L49/30; H04L49/3081; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5635; H04L2012/5638; H04L2012/5646; H04L2012/5652; H04L2012/5678; H04L2012/5679; H04L2012/5681; H04L2012/5682
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
187 words
Apparatus for multicasting an ingress cell received at one of a plurality of input ports, connectable through a multistage network, to a plurality of output ports, comprising: (a) means for receiving a first ingress cell at a first input port of a first stage, the ingress cell including a data payload and information identifying one or more routing queues to which a single copy of the data payload is to be outputted; (b) means for storing the data payload in memory; (c) one or more routing queues, at least one for each of the output ports; (d) means for identifying a backpressure queue assignment for the first ingress cell, the backpressure queue assignment identifying a backpressure indicator indicative of the congestion level for at least one routing queue of a subsequent stage; (e) means for determining, using the backpressure indicator, if the first ingress cell is to be outputted from one or more routing queues of the first stage; and (f) means for outputting the first ingress cell from the one or more routing queues when the congestion level is below or equal to a first threshold.
Claim 2
Dependent Claim
20 words
The apparatus of claim 1 including a plurality of routing queues, at least one for each of the output ports.
Claim 3
Dependent Claim
32 words
The apparatus of claim 1 wherein the first ingress cell is maintained in at least one of the one or more routing queues when the congestion level is above the first threshold.
Claim 4
Dependent Claim
32 words
The apparatus of claim 1 wherein the backpressure queue assignment is determined from a bit map identifying one or more output ports to which the first ingress cell is to be outputted.
Claim 5
Dependent Claim
49 words
The apparatus of claim 1 wherein a subsequent ingress cell identified as belonging to a connection which is the same as a connection associated with a first ingress cell connection is stored in the same routing queue, a bit map being included as part of the first ingress cell.
Claim 6
Dependent Claim
59 words
The apparatus of claim 5 wherein the backpressure queue assignment corresponds to a particular routing queue, and the ingress cell is counted as being in the particular routing queue until the stored data payload has been delivered to all of the output ports for the cell as determined from a bit map included as part of the ingress cell.
Claim 7
Dependent Claim
31 words
The apparatus of claim 5 wherein the backpressure indicator indicates when the congestion level is above the first threshold for any of a multiplicity of routing queues in a subsequent stage.
Claim 8
Dependent Claim
19 words
The apparatus of claim 5 wherein the first ingress cell and the subsequent cell utilize different backpressure queue assignments.
Claim 9
Dependent Claim
20 words
The apparatus of claim 8 wherein the different backpressure queues are assigned in a round-robin manner over all backpressure queues.
Claim 10
Dependent Claim
23 words
The apparatus of claim 8 wherein the backpressure queue assignments can identify any of the one or more routing queues for that cell.
Claim 11
Dependent Claim
19 words
The apparatus of claim 8 wherein the backpressure queue assignments can identify one or more of the output ports.
Claim 12
Dependent Claim
24 words
The apparatus of claim 8 wherein the different backpressure queue assignments are made randomly from a plurality of the one or more routing queues.
Claim 13
Dependent Claim
21 words
The apparatus of claim 8 wherein the different backpressure queue numbers are assigned randomly from a plurality of the output ports.
Claim 14
Dependent Claim
25 words
The apparatus of claim 8 wherein said all backpressure queue assignments identify the one or more routing queues of a subsequent stage of said network.
Claim 15
Dependent Claim
13 words
The apparatus of claim 1 wherein the first threshold has a predefined value.
Claim 16
Dependent Claim
25 words
The apparatus of claim 1 wherein the first threshold is a function of other than the one or more routing queues of the subsequent stage.
Claim 17
Dependent Claim
30 words
The apparatus of claim 1 wherein the first threshold is a function of the total number of cells stored in the buffer space in the subsequent stage of said network.
Claim 18
Dependent Claim
45 words
The apparatus of claim 17 wherein a cell that is outputted to more than one routing queue in the subsequent stage of said network is counted only once in the computation of the total number of cells stored in the buffer space in that stage.
Claim 19
Dependent Claim
111 words
The apparatus of claim 1 further comprising: (a) a plurality of routing queues corresponding to each of the output ports; (b) means for assigning each ingress cell, using header data included in the ingress cell, to one of the plurality of routing queues corresponding to each output port; (c) a plurality of backpressure indicators each indicating the congestion level of one of a plurality of routing queues in the subsequent stage of said network; and (d) means for outputting the first ingress cell from each routing queue when the congestion level of a corresponding routing queue in the subsequent stage of said network is below or equal to a second threshold.
Claim 20
Dependent Claim
37 words
The apparatus of claim 19 wherein the first ingress cell is maintained in the routing queue when the congestion level of a corresponding routing queue in the subsequent stage of said network is above the second threshold.
Claim 21
Dependent Claim
30 words
The apparatus of claim 19 wherein the second threshold is a function of the total number of cells stored in the buffer space in the subsequent stage of said network.
Claim 22
Dependent Claim
45 words
The apparatus of claim 21 wherein a cell that is outputted to more than one routing queue in the subsequent stage of said network is counted only once in the computation of the total number of cells stored in the buffer space in that stage.
Claim 23
Dependent Claim
42 words
The apparatus of claim 19 wherein the second threshold is a function of the total number of cells linked in a plurality of routing queues in the subsequent stage of said network identified by the header data included in the ingress cell.
Claim 24
Dependent Claim
20 words
The apparatus of claim 19 wherein each backpressure indicator indicates the total congestion level of a plurality of routing queues.
Claim 25
Independent Claim
170 words
A method of multicasting an ingress cell received at one of a plurality of input ports, connectable through a self-routing multistage network, to a plurality of output ports, said method comprising the steps of (a) receiving a first ingress cell at a first input port of a first stage, the ingress cell including a data payload and information identifying a routing queue to which a single copy of the data payload is to be outputted, (b) storing the data payload in said routing queue, (c) identifying a backpressure queue assignment for the first ingress cell, the backpressure queue assignment identifying a backpressure queue containing a congestion value indicative of the congestion level for the routing queue of a subsequent stage, (d) determining, using the congestion value stored in the backpressure queue, if the first ingress cell is to be outputted from the one or more routing queues, and (e) outputting the first ingress cell from the routing queue when the congestion value is below or equal to a first threshold.
Claim 26
Dependent Claim
32 words
The method of claim 25 wherein the first ingress cell is maintained in at least one of the one or more routing queues when the congestion level is above the first threshold.
Claim 27
Dependent Claim
32 words
The method of claim 25 wherein the backpressure queue assignment is determined from a bit map identifying one or more output ports to which the first ingress cell is to be outputted.
Claim 28
Dependent Claim
49 words
The method of claim 25 wherein a subsequent ingress cell identified as belonging to a connection which is the same as a connection associated with a first ingress cell connection is stored in the same routing queue, a bit map being included as part of the first ingress cell.
Claim 29
Dependent Claim
59 words
The method of claim 25 wherein the backpressure queue assignment corresponds to a particular routing queue, and the ingress cell is counted as being in the particular routing queue until the stored data payload has been delivered to all of the output ports for the cell as determined from a bit map included as part of the ingress cell.
Claim 30
Dependent Claim
31 words
The method of claim 25 wherein the backpressure indicator indicates when the congestion level is above the first threshold for any of a multiplicity of routing queues in a subsequent stage.
Claim 31
Dependent Claim
19 words
The method of claim 25 wherein the first ingress cell and the subsequent cell utilize different backpressure queue assignments.
Claim 32
Dependent Claim
20 words
The method of claim 31 wherein the different backpressure queues are assigned in a round-robin manner over all backpressure queues.
Claim 33
Dependent Claim
23 words
The method of claim 31 wherein the backpressure queue assignments can identify any of the one or more routing queues for that cell.
Claim 34
Dependent Claim
19 words
The method of claim 31 wherein the backpressure queue assignments can identify one or more of the output ports.
Claim 35
Dependent Claim
24 words
The method of claim 31 wherein the different backpressure queue assignments are made randomly from a plurality of the one or more routing queues.
Claim 36
Dependent Claim
21 words
The method of claim 31 wherein the different backpressure queue assignments are made randomly from a plurality of the output ports.
Claim 37
Dependent Claim
25 words
The method of claim 31 wherein said all backpressure queue assignments identify the one or more routing queues of a subsequent stage of said network.
Claim 38
Dependent Claim
13 words
The method of claim 25 wherein the first threshold has a predefined value.
Claim 39
Dependent Claim
25 words
The method of claim 25 wherein the first threshold is a function of other than the one or more routing queues of the subsequent stage.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.