US6661788B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multicast scheduling for a network device
Assignee: Dominari Holdings Inc
•
Filing: 1999-05-14
•
Granted: 2003-12-09
•
Expires: 2019-05-14
Abstract
Abstract A method and apparatus are provided for scheduling multicast data in an input-queued network device. According to one aspect of the present invention, deterministic and bounded delay for high priority multicast cells is guaranteed by the multicast scheduler. The scheduler receives a transmit request associated with each of a plurality of input ports. The transmit request identifies output ports to which pending multicast cells are ready to be transmitted, if any. Then, for each of multiple classes of service, the scheduler performs a single scheduling iteration. The single scheduling iteration includes a grant phase, an accept phase, and an update phase. During the grant phase, the scheduler grants one or more of the input ports access to the fabric by issuing grants based upon the transmit requests and a priority indicator that identifies an input port that is given scheduling priority for the scheduling iteration. During the accept phase, on behalf of each of the input ports, the scheduler accepts all grants corresponding to the input port. Finally, during the update phase, the scheduler updates the priority indicator for use in a subsequent scheduling cycle.
Inventors
- 👤 Richard L. Angle
- 👤 Shantigram V. Jagannath
- 👤 Geoffrey B. Ladwig
- 👤 Nanying Yin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 08:57
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/30; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L12/1881; H04L47/00; H04L47/10; H04L47/15; H04L47/24; H04L47/2416; H04L47/50; H04L47/62; H04L47/6205; H04L49/20; H04L49/201; H04L49/25; H04L49/253; H04L49/254
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
232 words
A network device comprising: a plurality of line cards, each line card including an input port and an output port; a fabric coupled to the plurality of line cards, the fabric allowing the simultaneous transfer of data among the plurality of input ports and output ports; and a fabric configuration manager coupled to the fabric and the plurality of line cards, the fabric configuration manager configured to receive one or more transmit requests from the input ports, each of the transmit requests identifying one of the input ports having a pending multicast cell that is ready to be transmitted to one or more output ports; search the output ports identified by each of the transmit request to find output ports that are available for grant, the search beginning with one of the input ports identified by a priority indicator; accept grants of output ports that were found to be available for grant by the searching; configure the fabric to form connections between input ports and output ports, each input port being connected to those output ports for which grants were accepted; and increment the priority indicator to identify a next input port that has a pending transmit request if grants have been accepted for all of the output ports identified by the transmit request, or if one of the output ports identified by the transmit request is asserting a back pressure signal.
Claim 2
Dependent Claim
232 words
A network device comprising: a plurality of line cards, each line card including an input port and an output port; a fabric coupled to the plurality of line cards, the fabric allowing the simultaneous transfer of data among the plurality of input ports and output ports; and a fabric configuration manager coupled to the fabric and the plurality of line cards, the fabric configuration manager configured to receive one or more transmit requests from the input ports, each of the transmit requests identifying one of the input ports having a pending multicast cell that is ready to be transmitted to one or more output ports; search the output ports identified by each of the transmit request to find output ports that are available for grant, the search beginning with one of the input ports identified by a priority indicator; accept grants of output ports that were found to be available for grant by the searching; configure the fabric to form connections between input ports and output ports, each input port being connected to those output ports for which grants were accepted; and increment the priority indicator to identify a next input port that has a pending transmit request if grants have been accepted for all of the output ports identified by the transmit request, or if one of the output ports identified by the transmit request is asserting a back pressure signal.
Claim 3
Dependent Claim
15 words
The network device of claim 1 , wherein the fabric further comprises a switched backplane.
Claim 4
Dependent Claim
32 words
The network device of claim 1 , wherein the back pressure signal is asserted by the one of the output ports to protect the output port from excess data from the fabric.
Claim 5
Dependent Claim
38 words
The network device of claim 1 , wherein the priority indicator further comprises a circular counter having N states, and wherein the priority indicator is incremented by rotating to the next input port in a round robin fashion.
Claim 6
Dependent Claim
51 words
The network device of claim 1 , wherein the fabric configuration manager is further configured to perform a plurality of schedulings, each scheduling being for one of a plurality of classes of service, each scheduling being performed in decreasing order of the relative priorities of the plurality of classes of service.
Claim 7
Dependent Claim
19 words
The network device of claim 5 , wherein a separate priority indicator is maintained for each class of service.
Claim 8
Dependent Claim
77 words
The network device of claim 1 , wherein a request vector is assembled for each of the output ports, the request vector having a cell availability indication corresponding to each of the input ports, wherein the fabric configuration manager is further configured to scan the request vector associated with each of the output ports to issue a grant for a first available cell, the scan beginning with one of the input ports identified by the priority indicator.
Claim 9
Independent Claim
135 words
A method of scheduling multicast data for transfer across a fabric of a network device, the method comprising: receiving a transmit request from an input port identified by a priority indicator, the transmit request identifying one or more output ports to which a pending multicast cell is ready to be transmitted; searching the output ports identified by the transmit request for output ports that are available for grant; accepting grants of output ports that were found to be available for grant by the searching; and incrementing the priority indicator to identify a next input port that has a pending transmit request if grants have been accepted for all of the output ports identified by the transmit request, or if one of the output ports identified by the transmit request is asserting a back pressure signal.
Claim 10
Independent Claim
135 words
A method of scheduling multicast data for transfer across a fabric of a network device, the method comprising: receiving a transmit request from an input port identified by a priority indicator, the transmit request identifying one or more output ports to which a pending multicast cell is ready to be transmitted; searching the output ports identified by the transmit request for output ports that are available for grant; accepting grants of output ports that were found to be available for grant by the searching; and incrementing the priority indicator to identify a next input port that has a pending transmit request if grants have been accepted for all of the output ports identified by the transmit request, or if one of the output ports identified by the transmit request is asserting a back pressure signal.
Claim 11
Dependent Claim
31 words
The method of claim 8 , wherein the back pressure signal is asserted by the one of the output ports to protect the output port from excess data from the fabric.
Claim 12
Dependent Claim
40 words
The method of claim 8 , wherein the priority indicator further comprises a circular counter having N states, and wherein incrementing the priority indicator further comprises rotating the priority indicator to the next input port in a round robin fashion.
Claim 13
Dependent Claim
37 words
The method of claim 8 , wherein the method is for a plurality of classes of service, each class of service being scheduled in decreasing order of the relative priorities of the plurality of classes of service.
Claim 14
Dependent Claim
18 words
The method of claim 11 , wherein a separate priority indicator is maintained for each class of service.
Claim 15
Dependent Claim
70 words
The method of claim 8 , further comprising: assembling a request vector for each of the output ports, the request vector having a cell availability indication corresponding to each of the input ports; and scanning the request vector associated with each of the output ports beginning with one of the input ports identified by the priority indicator; and issuing a grant for a first available cell found by the scanning.
Claim 16
Dependent Claim
244 words
A network device comprising: a plurality of input ports; a plurality of output ports; a fabric coupled to the plurality of input ports and the plurality of output ports, the fabric to selectively couple any of the plurality of input ports to any of the plurality of output ports; and a fabric configuration manager coupled to the fabric and the plurality of line cards, the fabric configuration manager including means for receiving one or more transmit requests from the input ports, each of the transmit requests identifying one of the input ports having a pending multicast cell that is ready to be transmitted to one or more output ports; means for searching the output ports identified by each of the transmit request to find output ports that are available for grant, the search beginning with one of the input ports identified by a priority indicator; means for accepting grants of output ports that were found to be available for grant by the searching; and means for configuring the fabric to couple each of the plurality of input ports to each of the plurality of output ports for which grants were accepted; and means for incrementing the priority indicator to identify a next input port that has a pending transmit request if grants have been accepted for all of the output ports identified by the transmit request, or if one of the output ports identified by the transmit request is asserting a back pressure signal.
Claim 17
Dependent Claim
244 words
A network device comprising: a plurality of input ports; a plurality of output ports; a fabric coupled to the plurality of input ports and the plurality of output ports, the fabric to selectively couple any of the plurality of input ports to any of the plurality of output ports; and a fabric configuration manager coupled to the fabric and the plurality of line cards, the fabric configuration manager including means for receiving one or more transmit requests from the input ports, each of the transmit requests identifying one of the input ports having a pending multicast cell that is ready to be transmitted to one or more output ports; means for searching the output ports identified by each of the transmit request to find output ports that are available for grant, the search beginning with one of the input ports identified by a priority indicator; means for accepting grants of output ports that were found to be available for grant by the searching; and means for configuring the fabric to couple each of the plurality of input ports to each of the plurality of output ports for which grants were accepted; and means for incrementing the priority indicator to identify a next input port that has a pending transmit request if grants have been accepted for all of the output ports identified by the transmit request, or if one of the output ports identified by the transmit request is asserting a back pressure signal.
Claim 18
Dependent Claim
15 words
The network device of claim 14 , wherein the fabric further comprises a switched backplane.
Claim 19
Dependent Claim
32 words
The network device of claim 14 , wherein the back pressure signal is asserted by the one of the output ports to protect the output port from excess data from the fabric.
Claim 20
Dependent Claim
44 words
The network device of claim 14 , wherein the priority indicator further comprises a circular counter having N states, and wherein means for incrementing the priority indicator includes means for rotating the priority indicator to the next input port in a round robin fashion.
Claim 21
Dependent Claim
50 words
The network device of claim 14 , wherein the fabric configuration manager further means for performing a plurality of schedulings, each scheduling being for one of a plurality of classes of service, each scheduling being performed in decreasing order of the relative priorities of the plurality of classes of service.
Claim 22
Dependent Claim
19 words
The network device of claim 18 , wherein a separate priority indicator is maintained for each class of service.
Claim 23
Dependent Claim
77 words
The network device of claim 14 , further comprising: means for assembling a request vector for each of the output ports, the request vector having a cell availability indication corresponding to each of the input ports; and means for scanning the request vector associated with each of the output ports beginning with one of the input ports identified by the priority indicator; and means for issuing a grant for a first available cell found by the scanning.
Claim 24
Independent Claim
183 words
A method of scheduling multicast data for transfer across a fabric of a network device, the method comprising: receiving one or more transmit requests from the input ports, each of the transmit requests identifying one of the input ports having a pending multicast cell that is ready to be transmitted to one or more output ports; searching the output ports identified by each of the transmit request to find output ports that are available for grant, the search beginning with one of the input ports identified by a priority indicator; accepting grants of output ports that were found to be available for grant by the searching; and configuring the fabric to couple each of the plurality of input ports to each of the plurality of output ports for which grants were accepted; and incrementing the priority indicator to identify a next input port that has a pending transmit request if grants have been accepted for all of the output ports identified by the transmit request, or if one of the output ports identified by the transmit request is asserting a back pressure signal.
Claim 25
Independent Claim
183 words
A method of scheduling multicast data for transfer across a fabric of a network device, the method comprising: receiving one or more transmit requests from the input ports, each of the transmit requests identifying one of the input ports having a pending multicast cell that is ready to be transmitted to one or more output ports; searching the output ports identified by each of the transmit request to find output ports that are available for grant, the search beginning with one of the input ports identified by a priority indicator; accepting grants of output ports that were found to be available for grant by the searching; and configuring the fabric to couple each of the plurality of input ports to each of the plurality of output ports for which grants were accepted; and incrementing the priority indicator to identify a next input port that has a pending transmit request if grants have been accepted for all of the output ports identified by the transmit request, or if one of the output ports identified by the transmit request is asserting a back pressure signal.
Claim 26
Dependent Claim
31 words
The method of claim 21 , wherein the back pressure signal is asserted by the one of the output ports to protect the output port from excess data from the fabric.
Claim 27
Dependent Claim
40 words
The method of claim 21 , wherein the priority indicator further comprises a circular counter having N states, and wherein incrementing the priority indicator further comprises rotating the priority indicator to the next input port in a round robin fashion.
Claim 28
Dependent Claim
37 words
The method of claim 21 , wherein the method is for a plurality of classes of service, each class of service being scheduled in decreasing order of the relative priorities of the plurality of classes of service.
Claim 29
Dependent Claim
18 words
The method of claim 24 , wherein a separate priority indicator is maintained for each class of service.
Claim 30
Dependent Claim
70 words
The method of claim 21 , further comprising: assembling a request vector for each of the output ports, the request vector having a cell availability indication corresponding to each of the input ports; and scanning the request vector associated with each of the output ports beginning with one of the input ports identified by the priority indicator; and issuing a grant for a first available cell found by the scanning.
References Cited (Backward Citations)
US5267235A
Cited
US5493566A
Cited
US6157967A
Cited
US5742606A
Cited
US5577035A
Cited
EP0687091A2
Cited
US5500858A
Cited
US5724351A
Cited
US5978359A
Cited
US6141346A
Cited
US6295295B1
Cited
EP0785697A2
Cited
US6212182B1
Cited
US5875190A
Cited
US5923644A
Cited
US5835491A
Cited
US6188690B1
Cited
US6201789B1
Cited
US6259698B1
Cited
US6104700A
Cited
US6324165B1
Cited
US6201792B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-12-08 | 2007-06-09 | 2007-12-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-12-08 | 2011-06-09 | 2011-12-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-12-08 | 2015-06-09 | 2015-12-09 | $7700.00 | Window Closed / Lapsed |