US7023840B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiserver scheduling system and method for a fast switching element
Assignee: Alcatel Lucent SAS
•
Filing: 2002-01-28
•
Granted: 2006-04-04
•
Expires: 2022-01-28
Abstract
Abstract A scheduling system and methodology for use in a network switch element having multiserver, multiple-arbiter architecture. Ingress ports and egress ports coupled to the cross-connect fabric of the network element are provided with multiple ingress and egress arbiters, respectively, for effectuating an iterative arbitration strategy such as RGA or RG. Arbiter architectures include singe-arbiter-per-port; single-arbiter-per-server; multiple-arbiters-per-port; and multiple-arbiters-per-server arrangements, wherein the arbiters can be implemented using RRA, BTA, Flexible Ring, or any other arbiter technology. Depending on the iteration strategy, ingress arbiter architecture and egress arbiter architecture, a variety of iterative, multiserver-capable scheduling algorithms can be obtained, which scheduling algorithms can also be implemented in QoS-aware network nodes.
Inventors
- 👤 Prasad N. Golla
- 👤 Gerard Damm
- 👤 John Blanton
- 👤 Mei Yang
- 👤 Dominique Verchere
- 👤 Hakki Candan Cankaya
- 👤 Yijun Xiong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 15:12
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/25; H04L49/253; H04L49/254; H04L49/10; H04L49/101; H04L49/20; H04L49/205; H04L49/30; H04L49/3045; H04L49/50; H04L49/505; H04L49/508
Claims Analysis
Total Claims: 62
Claim 1
Independent Claim
198 words
A network element having a switching apparatus for switching information between a plurality of ingress ports and a plurality of egress ports via a cross-connect matrix disposed therebetween, comprising: a plurality of ingress servers associated with each of said ingress ports, said ingress servers operating to serve a plurality of virtual output queues (VOQs) supported by a corresponding ingress port; a plurality of egress servers associated with each of said egress ports, each of said egress servers operating to serve outgoing traffic supported by a corresponding egress port; at least one ingress arbiter associated with each of said ingress ports and at least one egress arbiter associated with each of said egress ports, said at least one ingress arbiter and egress arbiter for effectuating a particular type of arbitration; and a scheduler operating to configure said cross-connect matrix for transporting a plurality of transmission units from at least one of said ingress ports to at least one of said egress ports during each time slot associated with said cross-connect matrix, wherein said scheduler effectuates a particular scheduling mechanism based at least in part upon an ingress arbiter architecture, an egress arbiter architecture and a predetermined arbitration iteration strategy.
Claim 2
Dependent Claim
198 words
A network element having a switching apparatus for switching information between a plurality of ingress ports and a plurality of egress ports via a cross-connect matrix disposed therebetween, comprising: a plurality of ingress servers associated with each of said ingress ports, said ingress servers operating to serve a plurality of virtual output queues (VOQs) supported by a corresponding ingress port; a plurality of egress servers associated with each of said egress ports, each of said egress servers operating to serve outgoing traffic supported by a corresponding egress port; at least one ingress arbiter associated with each of said ingress ports and at least one egress arbiter associated with each of said egress ports, said at least one ingress arbiter and egress arbiter for effectuating a particular type of arbitration; and a scheduler operating to configure said cross-connect matrix for transporting a plurality of transmission units from at least one of said ingress ports to at least one of said egress ports during each time slot associated with said cross-connect matrix, wherein said scheduler effectuates a particular scheduling mechanism based at least in part upon an ingress arbiter architecture, an egress arbiter architecture and a predetermined arbitration iteration strategy.
Claim 3
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said ingress arbiter architecture comprises a single arbiter per port arrangement.
Claim 4
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said ingress arbiter architecture comprises a multiple arbiters per port arrangement.
Claim 5
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said egress arbiter architecture comprises a single arbiter per port arrangement.
Claim 6
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said egress arbiter architecture comprises a multiple arbiters per port arrangement.
Claim 7
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said at least one ingress arbiter comprises a binary tree arbiter.
Claim 8
Dependent Claim
21 words
The network element as set forth in claim 6 , wherein said binary tree arbiter is a reverting binary tree arbiter.
Claim 9
Dependent Claim
21 words
The network element as set forth in claim 6 , wherein said binary tree arbiter is a non-reverting binary tree arbiter.
Claim 10
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said at least one ingress arbiter comprises a round robin arbiter.
Claim 11
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said at least one ingress arbiter comprises a flexible ring arbiter.
Claim 12
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said at least one egress arbiter comprises a binary tree arbiter.
Claim 13
Dependent Claim
21 words
The network element as set forth in claim 11 , wherein said binary tree arbiter is a reverting binary tree arbiter.
Claim 14
Dependent Claim
21 words
The network element as set forth in claim 11 , wherein said binary tree arbiter is a non-reverting binary tree arbiter.
Claim 15
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said at least one egress arbiter comprises a round robin arbiter.
Claim 16
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said at least one egress arbiter comprises a flexible ring arbiter.
Claim 17
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said predetermined arbitration iteration strategy includes a Request-Grant (RG) iteration strategy.
Claim 18
Dependent Claim
22 words
The network element as set forth in claim 1 , wherein said predetermined arbitration iteration strategy includes a Request-Grant-Accept (RGA) iteration strategy.
Claim 19
Dependent Claim
24 words
The network element as set forth in claim 1 , wherein requests associated with said VOQs are classified based on an internal priority condition.
Claim 20
Dependent Claim
19 words
The network element as set forth in claim 18 , wherein said internal priority condition includes an age alarm.
Claim 21
Dependent Claim
20 words
The network element as set forth in claim 18 , wherein said internal priority condition includes a “queue full” alarm.
Claim 22
Dependent Claim
30 words
The network element as set forth in claim 1 , wherein said VOQs are classified based on a predetermined number of levels of a Quality of Service (QoS)-related priority condition.
Claim 23
Dependent Claim
58 words
The network element as set forth in claim 21 , wherein each of said plurality of ingress servers and each of said plurality of egress servers are associated with a predetermined number of ingress arbiters and egress arbiters, respectively, said predetermined number of ingress and egress arbiters equaling said predetermined number of levels of said QoS-based priority condition.
Claim 24
Dependent Claim
58 words
The network element as set forth in claim 21 , wherein each of said plurality of ingress ports and each of said plurality of egress ports are associated with a predetermined number of ingress arbiters and egress arbiters, respectively, said predetermined number of ingress and egress arbiters equaling said predetermined number of levels of said QoS-based priority condition.
Claim 25
Dependent Claim
64 words
The network element as set forth in claim 1 , wherein each of said plurality of ingress servers is associated with a corresponding ingress arbiter and each of said plurality of egress servers is associated with a corresponding egress arbiter, said network element further including means to desynchronize initialization of said ingress arbiters and said egress arbiters at the beginning of each time slot.
Claim 26
Dependent Claim
179 words
A scheduling system for use in a network switching element having a cross-connect fabric disposed between a plurality of ingress ports and a plurality of egress ports, each of said ingress ports having a plurality of ingress servers and each of said egress ports having a plurality of egress servers, wherein each ingress port supports a plurality of virtual output queue groups (VOQ groups), each of said VOQ groups having sub-queues therein based on a Quality of Service (QoS) priority level, said scheduling system comprising: a first level (L1) scheduler partition operable to generate requests in accord with an arbitration iteration strategy used in computing matches between said ingress servers and said egress servers, said requests being organized based on said QoS priority level; and a second level (L2) scheduler partition operating, in response to said requests assembled by said first level scheduler partition, to generate a scheduling matrix at each slot time associated with said cross-connect fabric, said scheduling matrix identifying matches between at least a portion of said ingress servers and a portion of said egress servers.
Claim 27
Dependent Claim
179 words
A scheduling system for use in a network switching element having a cross-connect fabric disposed between a plurality of ingress ports and a plurality of egress ports, each of said ingress ports having a plurality of ingress servers and each of said egress ports having a plurality of egress servers, wherein each ingress port supports a plurality of virtual output queue groups (VOQ groups), each of said VOQ groups having sub-queues therein based on a Quality of Service (QoS) priority level, said scheduling system comprising: a first level (L1) scheduler partition operable to generate requests in accord with an arbitration iteration strategy used in computing matches between said ingress servers and said egress servers, said requests being organized based on said QoS priority level; and a second level (L2) scheduler partition operating, in response to said requests assembled by said first level scheduler partition, to generate a scheduling matrix at each slot time associated with said cross-connect fabric, said scheduling matrix identifying matches between at least a portion of said ingress servers and a portion of said egress servers.
Claim 28
Dependent Claim
29 words
The scheduling system as set forth in claim 25 , wherein said L1 scheduler partition includes a plurality of ingress arbiters, each corresponding to a particular QoS priority level.
Claim 29
Dependent Claim
28 words
The scheduling system as set forth in claim 26 , wherein each of said ingress servers per said ingress port is associated with said plurality of ingress arbiters.
Claim 30
Dependent Claim
24 words
The scheduling system as set forth in claim 26 , wherein each of said ingress ports is associated with said plurality of ingress arbiters.
Claim 31
Dependent Claim
20 words
The scheduling system as set forth in claim 26 , wherein said ingress arbiters are comprised of round robin arbiters.
Claim 32
Dependent Claim
20 words
The scheduling system as set forth in claim 26 , wherein said ingress arbiters are comprised of binary tree arbiters.
Claim 33
Dependent Claim
29 words
The scheduling system as set forth in claim 25 , wherein said L2 scheduler partition includes a plurality of egress arbiters, each corresponding to a particular QoS priority level.
Claim 34
Dependent Claim
28 words
The scheduling system as set forth in claim 31 , wherein each of said egress servers per said egress port is associated with said plurality of egress arbiters.
Claim 35
Dependent Claim
24 words
The scheduling system as set forth in claim 31 , wherein each of said egress ports is associated with said plurality of egress arbiters.
Claim 36
Dependent Claim
20 words
The scheduling system as set forth in claim 31 , wherein said egress arbiters are comprised of round robin arbiters.
Claim 37
Dependent Claim
20 words
The scheduling system as set forth in claim 31 , wherein said egress arbiters are comprised of binary tree arbiters.
Claim 38
Dependent Claim
28 words
The scheduling system as set forth in claim 25 , wherein said L 1 scheduler partition includes means for prioritizing said requests based on an internal subpriority condition.
Claim 39
Dependent Claim
19 words
The scheduling system as set forth in claim 36 , wherein said internal subpriority condition includes an age alarm.
Claim 40
Dependent Claim
20 words
The scheduling system as set forth in claim 36 , wherein said internal subpriority condition includes a “queue full” alarm.
Claim 41
Dependent Claim
21 words
The scheduling system as set forth in claim 25 , wherein said arbitration iteration strategy comprises a Request-Grant (RG) iteration strategy.
Claim 42
Dependent Claim
21 words
The scheduling system as set forth in claim 25 , wherein said arbitration iteration strategy comprises a Request-Grant-Accept (RGA) iteration strategy.
Claim 43
Dependent Claim
253 words
A scheduling methodology for use in a network switching element having a cross-connect fabric disposed between a plurality of ingress ports and a plurality of egress ports, each of said ingress ports having a plurality of ingress servers and each of said egress ports having a plurality of egress servers, wherein each ingress port supports a plurality of virtual output queues (VOQs), said scheduling methodology comprising the steps: for each matrix cycle associated with said cross-connect fabric, initializing a scheduling matrix and a request matrix, said request matrix for building requests associated with an arbitration iteration strategy used in computing matches between said ingress servers and egress servers; performing an arbitration iteration to obtain a current match matrix; updating said request matrix and said scheduling matrix based on said current match matrix; if all of said plurality of ingress servers associated with a particular ingress port are matched, removing requests, issued from said particular ingress port, from said request matrix; if all of said plurality of egress servers associated with a particular egress port are matched, removing requests, directed to said particular egress port, from said request matrix; resetting said current match matrix and performing next arbitration iteration using said updated request matrix; and upon encountering a particular stop condition, terminating further iterations and forwarding said updated scheduling matrix to a controller for configuring at least one connection path in said cross-connect fabric based on said updated scheduling matrix so as to effectuate transfer of transmission units between matched ingress and egress servers.
Claim 44
Dependent Claim
253 words
A scheduling methodology for use in a network switching element having a cross-connect fabric disposed between a plurality of ingress ports and a plurality of egress ports, each of said ingress ports having a plurality of ingress servers and each of said egress ports having a plurality of egress servers, wherein each ingress port supports a plurality of virtual output queues (VOQs), said scheduling methodology comprising the steps: for each matrix cycle associated with said cross-connect fabric, initializing a scheduling matrix and a request matrix, said request matrix for building requests associated with an arbitration iteration strategy used in computing matches between said ingress servers and egress servers; performing an arbitration iteration to obtain a current match matrix; updating said request matrix and said scheduling matrix based on said current match matrix; if all of said plurality of ingress servers associated with a particular ingress port are matched, removing requests, issued from said particular ingress port, from said request matrix; if all of said plurality of egress servers associated with a particular egress port are matched, removing requests, directed to said particular egress port, from said request matrix; resetting said current match matrix and performing next arbitration iteration using said updated request matrix; and upon encountering a particular stop condition, terminating further iterations and forwarding said updated scheduling matrix to a controller for configuring at least one connection path in said cross-connect fabric based on said updated scheduling matrix so as to effectuate transfer of transmission units between matched ingress and egress servers.
Claim 45
Dependent Claim
21 words
The scheduling methodology as set forth in claim 41 , wherein said arbitration iteration strategy comprises a Request-Grant (RG) iteration strategy.
Claim 46
Dependent Claim
21 words
The scheduling methodology as set forth in claim 41 , wherein said arbitration iteration strategy comprises a Request-Grant-Accept (RGA) iteration strategy.
Claim 47
Dependent Claim
28 words
The scheduling methodology as set forth in claim 41 , wherein said particular stop condition includes determining if no new matches were found in said next arbitration iteration.
Claim 48
Dependent Claim
26 words
The scheduling methodology as set forth in claim 41 , wherein said particular stop condition includes determining if said updated request matrix is a null matrix.
Claim 49
Dependent Claim
27 words
The scheduling methodology as set forth in claim 41 , wherein said particular stop condition includes determining if a predetermined maximum number of iterations has been reached.
Claim 50
Dependent Claim
24 words
The scheduling methodology as set forth in claim 41 , wherein said particular stop condition includes determining if an iteration timeout has been reached.
Claim 51
Dependent Claim
20 words
The scheduling methodology as set forth in claim 41 , wherein said requests are prioritized based an internal priority condition.
Claim 52
Dependent Claim
19 words
The scheduling methodology as set forth in claim 48 , wherein said internal priority condition includes an age alarm.
Claim 53
Dependent Claim
20 words
The scheduling methodology as set forth in claim 48 , wherein said internal priority condition includes a “queue full” alarm.
Claim 54
Dependent Claim
30 words
The scheduling methodology as set forth in claim 41 , wherein said requests are classified based on a predetermined number of levels of a Quality of Service (QoS)-related priority condition.
Claim 55
Dependent Claim
21 words
The scheduling methodology as set forth in claim 41 , wherein said transmission units include variable length Internet Protocol (IP) packets.
Claim 56
Dependent Claim
18 words
The scheduling methodology as set forth in claim 41 , wherein said transmission units include fixed length cells.
Claim 57
Dependent Claim
19 words
The scheduling methodology as set forth in claim 41 , wherein said transmission units include protocol data units (PDUs).
Claim 58
Dependent Claim
24 words
The scheduling methodology as set forth in claim 41 , wherein said arbitration iteration is performed in accord with a multiserver, iterative SLIP algorithm.
Claim 59
Dependent Claim
25 words
The scheduling methodology as set forth in claim 41 , wherein said arbitration iteration is performed in accord with a multiserver, iterative Ping Pong algorithm.
Claim 60
Dependent Claim
26 words
The scheduling methodology as set forth in claim 41 , wherein said arbitration iteration is performed in accord with a multiserver, iterative dual round robin algorithm.
Claim 61
Dependent Claim
27 words
The scheduling methodology as set forth in claim 41 , wherein said arbitration iteration is performed in accord with a multiserver, flexible ring dual round robin algorithm.
Claim 62
Dependent Claim
26 words
The scheduling methodology as set forth in claim 41 , wherein said arbitration iteration is performed in accord with a multiserver, prioritized dual round robin algorithm.
References Cited (Backward Citations)
US6865154B1
Cited
WO1999040754A1
Cited
US20010050916A1
Cited
WO2000038375A1
Cited
US6747971B1
Cited
US6848017B2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-04-03 | 2009-10-03 | 2010-04-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-04-03 | 2013-10-03 | 2014-04-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-04-03 | 2017-10-03 | 2018-04-04 | $7700.00 | Window Closed / Lapsed |