Scheduling the dispatch of cells in multistage switches

• US 20020061020A1
• Filed: 05/08/2001
• Published: 05/23/2002
• Est. Priority Date: 11/20/2000
• Status: Active Grant

• Current Assignee: Polytechnic University (New York University)
• Original Assignee: Polytechnic University (New York University)
• Inventors: Chao, Hung-Hsiang Jonathan, Oki, Eiji
• Granted Patent: US 7,173,931 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/1569 Clos switching fabrics
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A multiple phase cell dispatch scheme, in which each phase uses a simple and fair (e.g., round robin) arbitration methods, is described. VOQs of an input module and outgoing links of the input module are matched in a first phase. An outgoing link of an input module is matched with an outgoing link of a central module in a second phase. The arbiters become desynchronized under stable conditions which contributes to the switch'"'"'s high throughput characteristic. Using this dispatch scheme, a scalable multiple-stage switch able to operate at high throughput, without needing to resort to speeding up the switching fabric and without needing to use buffers in the second stage, is possible. The cost of speed-up and the cell out-of-sequence problems that may occur when buffers are used in the second stage are therefore avoided.

Claims

1. A method for use in a multi-stage switch including

a plurality of central modules, and

a plurality of input modules, each including virtual output queues and outgoing links coupled with each of the plurality of central modules, for scheduling the dispatch of cells stored in the virtual output queues, the method comprising:

a) matching a non-empty virtual output queue of an input module with an outgoing link in the input module; and

b) matching the outgoing link with an outgoing link of one of the central modules,

wherein high switch throughput can be achieved without speedup of the central modules.

2. The method of claim 1 wherein the act of matching a non-empty virtual output queue of an input module with an outgoing link in the input module includes:

i) broadcasting a request for the non-empty virtual output queue to an arbiter for each of the outgoing links of the input module;

ii) selecting, with the arbiter of each of the outgoing links of the input module, a non-empty virtual output queue that broadcast a request;

iii) sending a grant to an arbiter for the selected non-empty virtual output queue; and

iv) selecting, with the arbiter of the selected non-empty virtual output queue, an outgoing link from among the one or more outgoing links that sent a grant.

3. The method of claim 2 wherein the act of matching a non-empty virtual output queue of an input module with an outgoing link in the input module occurs within one cell time slot.

4. The method of claim 2 wherein the act of selecting, with the arbiter of each of the outgoing links of the input module, a non-empty virtual output queue that broadcast a request, is done in accordance with a round robin discipline.

5. The method of claim 2 wherein the act of selecting, with the arbiter of each of the outgoing links of the input module, a non-empty virtual output queue that broadcast a request, is done in based on the location of a pointer updated in accordance with a round robin discipline through each of the virtual output queues of the input module.

6. The method of claim 5 wherein the pointer moves through groups of virtual output queues, before moving through virtual output queues within each group.

7. The method of claim 2 wherein the acts of i) broadcasting a request for the non-empty virtual output queue to an arbiter for each of the outgoing links of the input module;

ii) selecting, with the arbiter of each of the outgoing links of the input module, a non-empty virtual output queue that broadcast a request;

iii) sending a grant to an arbiter for the selected non-empty virtual output queue; and

iv) selecting, with the arbiter of the selected non-empty virtual output queue, an outgoing link from among the one or more outgoing links that sent a grant,

are performed at least twice within one cell time slot.

8. The method of claim 1 wherein the act of matching the outgoing link of the input module with an outgoing link of one of the central modules includes:

i) broadcasting a request for the outgoing link of the input module to an arbiter for each of the outgoing links of the central modules that lead towards an output port associated with the virtual output queue matched with the outgoing link of the input module;

ii) selecting with the arbiter of each of the outgoing links of the central modules, an outgoing link of an input module that broadcast a request; and

iii) sending a grant to the selected outgoing link of the input module.

9. The method of claim 8 wherein the act of selecting with the arbiter of each of the outgoing links of the central module, an outgoing link of the input module that broadcast a request, is done based on a round robin discipline.

10. The method of claim 8 wherein the act of selecting, with the arbiter of each of the outgoing links of the central module, an outgoing link of the input module that broadcast a request, is done in based on the location of a pointer updated in accordance with a round robin discipline through each of the outgoing links of each of the input modules.

11. A method for use in a multi-stage switch including

a plurality of central modules, and

a plurality of input modules, each including virtual output queues and outgoing links coupled with each of the plurality of central modules,

for matching a non-empty virtual output queue of an input module with an outgoing link in the input module, the method comprising:

a) broadcasting a request for the non-empty virtual output queue to an arbiter for each of the outgoing links of the input module;

b) selecting, with the arbiter of each of the outgoing links of the input module, a non-empty virtual output queue that broadcast a request;

c) sending a grant to an arbiter for the selected non-empty virtual output queue; and

d) selecting, with the arbiter of the selected non-empty virtual output queue, an outgoing link from among the one or more outgoing links that sent a grant.

12. The method of claim 11 wherein the act of matching a non-empty virtual output queue of an input module with an outgoing link in the input module occurs within one cell time slot.

13. The method of claim 11 wherein the act of selecting, with the arbiter of each of the outgoing links of the input module, a non-empty virtual output queue that broadcast a request, is done in accordance with a round robin discipline.

14. The method of claim 11 wherein the act of selecting, with the arbiter of each of the outgoing links of the input module, a non-empty virtual output queue that broadcast a request, is done in based on the location of a pointer updated in accordance with a round robin discipline through each of the virtual output queues of the input module.

15. The method of claim 14 wherein the pointer moves through groups of virtual output queues, before moving through virtual output queues within each group.

16. The method of claim 11 wherein the acts of

a) broadcasting a request for the non-empty virtual output queue to an arbiter for each of the outgoing links of the input module;

b) selecting, with the arbiter of each of the outgoing links of the input module, a non-empty virtual output queue that broadcast a request;

c) sending a grant to an arbiter for the selected non-empty virtual output queue; and

d) selecting, with the arbiter of the selected non-empty virtual output queue, an outgoing link from among the one or more outgoing links that sent a grant,

are performed at least twice within one cell time slot.

18. The combination of claim 17 wherein the means for matching a non-empty virtual output queue of an input module with an outgoing link in the input module include:

i) means for broadcasting a request for the non-empty virtual output queue to an arbiter for each of the outgoing links of the input module;

ii) for each of the outgoing links of the input module, an arbiter for selecting a non-empty virtual output queue that broadcast a request;

iii) means for sending a grant to an arbiter for the selected non-empty virtual output queue; and

iv) for the selected non-empty virtual output queue, an arbiter for selecting an outgoing link from among the one or more outgoing links that sent a grant.

19. The combination of claim 18 wherein the means for matching a non-empty virtual output queue of an input module with an outgoing link in the input module performs the match within one cell time slot.

20. The combination of claim 18 wherein the arbiter of each,of the outgoing links of the input module for selecting a non-empty virtual output queue that broadcast a request, includes a pointer updated in accordance with a round robin discipline.

21. The combination of claim 20 wherein the pointer moves through groups of virtual output queues, before moving through virtual output queues within each group.

22. The combination of claim 17 wherein the means for matching a non-empty virtual output queue of the input module with an outgoing link in the input module performs multiple matching iterations within one cell time slot.

23. The combination of claim 17 wherein the means for matching the outgoing link with an outgoing link of one of the central modules include:

i) means for broadcasting a request for the outgoing link of the input module to an arbiter for each of the outgoing links of the central modules that lead towards an output port associated with the virtual output queue matched with the outgoing link of the input module;

ii) for each of the outgoing links of the central module, an arbiter for selecting an outgoing link of the input module that broadcast a request; and

iii) means for sending a grant to the selected outgoing link of the input module.

24. The combination of claim 23 wherein the arbiter of each of the outgoing links of the central module for selecting an outgoing link that broadcast a request, includes a pointer updated based on a round robin discipline.

25. The combination of claim 17 wherein there are:

k input modules, each having n input ports, n×

k virtual output queues, and m outgoing links.

26. The combination of claim 25 wherein, n×

k virtual output queues of each input module are grouped into k groups of n virtual output queues.

28. The input module of claim 27 wherein the means for matching a non-empty virtual output queue of an input module with an outgoing link in the input module performs such matching within one cell time slot.

29. The input module of claim 27 wherein the arbiter of each of the outgoing links of the input module for selecting a non-empty virtual output queue that broadcast a request, is pointer updated in accordance with a round robin discipline.

30. The input module of claim 29 wherein the pointer moves through groups of virtual output queues, before moving through virtual output queues within each group.

31. The input module of claim 27 wherein means for matching a non-empty virtual output queue of an input module with an outgoing link in the input module repeats such matching within one cell time slot.

32. The input module of claim 27 wherein there are k input modules, each having n input ports, n×

k virtual output queues, and m outgoing links.

33. The input module of claim 32 wherein the n x k virtual output queues of each input module are grouped into k groups of n virtual output queues.

17. A combination for use in a multi-stage switch, the combination comprising:

a) a plurality of central modules, each including outgoing links towards output modules including a plurality of output ports;

b) a plurality of input modules, each including

i) virtual output queues, and

ii) outgoing links coupled with each of the plurality of central modules; and

c) means for matching a non-empty virtual output queue of the input module with an outgoing link in the input module; and

d) means for matching the outgoing link of the input module with an outgoing link of one of the central modules,

wherein high switch throughput can be achieved without speedup of the central modules

27. An input module for use a multi-stage switch including a plurality of central modules, the input module comprising:

a) virtual output queues;

b) outgoing links coupled with each of the plurality of central modules; and

c) means for matching a non-empty virtual output queue of an input module with an outgoing link in the input module, the means for matching including

i) means for broadcasting a request for the non-empty virtual output queue to an arbiter for each of the outgoing links of the input module,

ii) for each of the outgoing links of the input module, an arbiter for selecting a non-empty virtual output queue that broadcast a request,

iii) means for sending a grant to an arbiter for the selected non-empty virtual output queue, and

iv) for the selected non-empty virtual output queue, an arbiter for selecting an outgoing link from among the one or more outgoing links that sent a grant.

34. A machine readable medium having stored thereon information comprising:

a) a sequence of virtual output queue identifiers, each having an associated indicator indicating whether or not a request was received from the associated virtual output queue;

b) a first pointer pointing to one of the sequence of virtual output queue identifiers;

c) a sequence of outgoing link identifiers, each having an associated indicator indicating whether or not a grant was received from an associated outgoing link; and

d) a second pointer pointing to one of the sequence of outgoing link identifiers.