Scheduling the dispatch of cells in non-empty virtual output queues of multistage switches using a pipelined hierarchical arbitration scheme

• US 7,046,661 B2
• Filed: 07/23/2001
• Issued: 05/16/2006
• Est. Priority Date: 11/20/2000
• Status: Expired

• Current Assignee: Polytechnic University (New York University)
• Original Assignee: Polytechnic University (New York University)
• Inventors: Rojas-Cessa, Roberto, Chao, Hung-Hsiang Jonathan, Oki, Eiji
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): HAILE, FEBEN
• Application Number:
  US09/911,038
• Publication Number:
  US 20030021266A1
• Time in Patent Office: 1,758 Days
• Field of Search: 370/386, 370/388, 370/395.4, 370/395.7, 370/395.71, 370/412, 370/417, 370/429
• US Class Current: 370/388
• 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/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/1553 Interconnection of ATM switching modules, e.g. ATM switching fabrics
• CPC Class Codes: H04L 49/1569 Clos switching fabrics
• CPC Class Codes: H04L 49/3045 Virtual queuing
• 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 pipeline-based matching scheduling approach for input-buffered switches relaxes the timing constraint for arbitration with matching schemes, such as CRRD and CMSD. In the new approach, arbitration may operate in a pipelined manner. Each sub-scheduler is allowed to take more than one time slot for its matching. Every time slot, one of them provides a matching result(s). The sub-scheduler can use a matching scheme such as CRRD and CMSD.

Claims

1. For use with a multi-stage switch having

a first number, k×

n, of output ports,

a plurality of central modules, each having outgoing links, and

a second number of input modules, each including k groups of n virtual output queues and outgoing links coupled with each of the plurality of central modules, and

a third number of sub-schedulers, each of the third number of sub-schedulers being able to arbitrate matching an input port with an outgoing link of one of the plurality of central modules via an outgoing link of the input module including the input port,

a method for scheduling the dispatch of cells stored in the virtual output queues, the method comprising for each of the sub-schedulers, performing a matching operation, if it has been reserved, to match a cell buffered at a virtual output queue with an outgoing link of one of the plurality of central modules, wherein the matching operation includes;

a) matching a non-empty virtual output queue of an input module with an outgoing link in the input module, wherein the outgoing link has an associated master arbitration operation for selecting one of the k groups of n virtual output queues; and

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

wherein each of the sub-schedulers requires more than one cell time slot to generate a match from its matching operation, and

wherein the sub-schedulers can collectively generate a match result in each cell time slot.

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) sending, on behalf of each non-empty virtual output queue, a request to slave arbiters, each of the slave arbiters being associated with one of each of the outgoing links of the input module, and each of the slave arbiters being associated with the group of virtual output queues to which the non-empty virtual output queue belongs;

ii) sending, on behalf of each group of virtual output queues to which a non-empty virtual output queue belongs, a request to master arbiters, each of the master arbiters being associated with one of each of the outgoing links of the input module;

iii) selecting, with each of the master arbiters, a virtual output queue group having at least one non-empty virtual output queue, from among one or more virtual output queue groups that sent a request;

iv) selecting, with each of the slave arbiters, a non-empty virtual output queue, belonging to its associated group, from among one or more virtual output queues that sent a request; and

v) selecting, with the arbiter of the each of the selected non-empty virtual output queues of each of the selected virtual output queue groups, an outgoing link from among the one or more candidate outgoing links, each of the one or more candidate outgoing links being associated with a master arbiter that selected the virtual output queue group and a slave arbiter that selected the non-empty virtual output queue.

3. The method of claim 2 wherein an act of selecting, with a master arbiter, a virtual output queue group having at least one non-empty virtual output queue, is done in accordance with a round robin discipline.

4. The method of claim 2 wherein an act of selecting, with a slave arbiter, a non-empty virtual output queue, belonging to its associated group, is done in accordance with a round robin discipline.

5. The method of claim 2 wherein the act of selecting, with the arbiter of the each of the selected non-empty virtual output queues of each of the selected virtual output queue groups, an outgoing link from among the one or more candidate outgoing links, is done in accordance with a round robin discipline.

6. The method of claim 2 wherein the acts of

i) sending, on behalf of each non-empty virtual output queue, a request to slave arbiters, each of the slave arbiters being associated with one of each of the outgoing links of the input module, and each of the slave arbiters being associated with the group of virtual output queues to which the non-empty virtual output queue belongs;

ii) sending, on behalf of each group of virtual output queues to which a non-empty virtual output queue belongs, a request to master arbiters, each of the master arbiters being associated with one of each of the outgoing links of the input module;

iii) selecting, with each of the master arbiters, a virtual output queue group having at least one non-empty virtual output queue, from among one or more virtual output queue groups that sent a request;

iv) selecting, with each of the slave arbiters, a non-empty virtual output queue, belonging to its associated group, from among one or more virtual output queues that sent a request; and

v) selecting, with the arbiter of the each of the selected non-empty virtual output queues of each of the selected virtual output queue groups, an outgoing link from among the one or more candidate outgoing links, each of the one or more candidate outgoing links being associated with a master arbiter that selected the virtual output queue group and a slave arbiter that selected the non-empty virtual output queue,

are performed at least twice within the third number of cell time slots.

7. 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) sending a request for the outgoing link of the input module to an arbiter for each of the outgoing links of the central modules that leads towards an output port associated with the virtual output queue matched with the outgoing link of the input module; and

ii) selecting with the arbiter of each of the outgoing links of the central modules, an outgoing link of an input module from among those that sent a request.

8. The method of claim 7 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.

9. The method of claim 1 further comprising:

c) if a cell buffered at a virtual output queue has been successfully matched with its corresponding output port, informing the virtual output queue.

10. The method of claim 9 further comprising:

d) for each of the virtual output queues, if the virtual output queue has been informed that it has been successfully matched with its corresponding output port, then dispatching its head of line cell.

11. The method of claim 1 wherein each of the virtual output queues is associated with a first count for indicating whether the virtual output queue is storing a cell awaiting dispatch, wherein a first count is incremented upon learning that a new cell has arrived at its associated virtual output queue.

12. The method of claim 11 wherein the count is decremented when an available sub-scheduler is reserved for considering a head of line cell at a corresponding virtual output queue.

13. The method of claim 1 further comprising:

c) for each of the sub-schedulers, maintaining a second indicator for each of the virtual output queues, for indicating whether the sub-scheduler is available or reserved,

wherein the second indicator, for each of the sub-schedulers, is set to indicate that the associated sub-scheduler is reserved if the first indicator indicates that a corresponding virtual output queue is storing a cell awaiting dispatch arbitration.

14. The method of claim 1 further comprising:

c) for each of the sub-schedulers, maintaining a second indicator for each of the virtual output queues, for indicating whether the sub-scheduler is available or reserved,

wherein the second indicator, for each of the sub-schedulers, is set to indicate that the associated sub-scheduler is available if the associated sub-scheduler matches a cell buffered at a virtual output queue with its corresponding output port.

15. The method of claim 1 further comprising:

c) for each of the sub-schedulers, maintaining a second indicator for each of the virtual output queues, for indicating whether the sub-scheduler is available or reserved,

wherein the second indicator is set to indicate that a p^th sub-scheduler is reserved if the first indicator indicates that a corresponding virtual output queue is storing a cell awaiting dispatch arbitration,

wherein p is set to the current cell time slot modulo the third number.

16. For use with a multi-stage switch including

a plurality of central modules, each including outgoing links towards output modules, the output modules collectively including a first number, k×

n, of output ports;

a second number of input modules, each including

k groups of n virtual output queues, and

outgoing links coupled with each of the plurality of central modules;

a dispatch scheduler comprising;

a) a third number of sub-schedulers; and

b) a first indicator, associated with each of the virtual output queues, for indicating whether the virtual output queue is storing a cell awaiting dispatch arbitration,

wherein each of the sub-schedulers is adapted to perform a matching operation, if it has been reserved, to match a cell buffered at a virtual output queue with its corresponding output port, and includes;

i) master arbiters, each of the master arbiters being associated with one of the outgoing links of the input module, for selecting a group of virtual output queues from among those associated with a received request,

ii) groups of slave arbiters, each group of slave arbiters being associated with one of the k groups of n virtual output queues, for selecting a virtual output queue from among those submitting a request, and

iii) virtual output queue arbiters, each virtual output queue arbiter being associated with one of the virtual output queues, for selecting an outgoing link of the input module from among those submitting a grant

wherein each of the sub-schedulers requires more than one cell time slot to generate a match from its matching operation, and

wherein the sub-schedulers can collectively generate a match result in each cell time slot.

17. The dispatch scheduler of claim 16 wherein each of the sub-schedulers require no more than the third number of cell time slots to generate a match result from its matching operation.

18. The dispatch scheduler of claim 16 wherein if a cell buffered at a virtual output queue has been successfully matched with its corresponding output port, the virtual output queue is so informed.

19. The dispatch scheduler of claim 16 wherein if a cell buffered at a virtual output queue has been successfully matched with its corresponding output port, its head of line cell is dispatched.

20. The dispatch scheduler of claim 16 wherein the first indicator, for each of the virtual output queues, for indicating whether the virtual output queue is storing a cell awaiting dispatch arbitration, is a count, and

wherein the count is incremented upon learning that a new cell has arrived at the virtual output queue.

21. The dispatch scheduler of claim 20 wherein the count is decremented when an available sub-scheduler is reserved for considering a head of line cell at a corresponding virtual output queue.

22. The dispatch scheduler of claim 16 further comprising:

c) a second indicator for each of the virtual output queues and for each of the sub-schedulers, indicating whether the sub-scheduler is available or reserved,

wherein the second indicator, for each of the sub-schedulers, is set to indicate that the associated sub-scheduler is reserved if the first indicator indicates that a corresponding virtual output queue is storing a cell awaiting dispatch arbitration.

23. The dispatch scheduler of claim 16 further comprising:

c) a second indicator for each of the virtual output queues and for each of the sub-schedulers, indicating whether the sub-scheduler is available or reserved,

wherein the second indicator, for each of the sub-schedulers, is set to indicate that the associated sub-scheduler is available if the associated sub-scheduler matches a cell buffered at a virtual output queue with its corresponding output port.

24. The dispatch scheduler of claim 16 further comprising:

c) a second indicator for each of the virtual output queues and for each of the sub-schedulers, indicating whether the sub-scheduler is available or reserved,

wherein the second indicator is set to indicate that a p^th sub-scheduler is reserved if the first indicator indicates that a corresponding virtual output queue is storing a cell awaiting dispatch, and

wherein p is set to the current cell time slot modulo the third number.

25. The dispatch scheduler of claim 16 wherein the means for matching a non-empty virtual output queue of an input module with an outgoing link in the input module further include:

iv) means for sending, on behalf of each non-empty virtual output queue, a request to slave arbiters, each of the slave arbiters being associated with one of the outgoing links of the input module, and each of the slave arbiters being associated with one of the groups of virtual output queues; and

v) means for sending, on behalf of each of the groups of virtual output queues to which a non-empty virtual output queue belongs, a request to master arbiters, each of the master arbiters being associated with one of the outgoing links of the input module.

26. The dispatch scheduler of claim 16 wherein each of the master arbiters operates in accordance with a round robin discipline.

27. The dispatch scheduler of claim 26 wherein each of the master arbiters operates independent of the others.

28. The dispatch scheduler of claim 16 wherein each of the slave arbiters operates in accordance with a round robin discipline.

29. The dispatch scheduler of claim 28 wherein each of the slave arbiters operates independent of the others.

30. The dispatch scheduler of claim 16 wherein each of the virtual output queue arbiters operates in accordance with a round robin discipline.

31. The dispatch scheduler of claim 30 wherein each of the virtual output queue arbiters operates independent of the others.

32. The dispatch scheduler of claim 16 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 the third number of cell time slots.

33. The dispatch scheduler of claim 16 wherein the means for matching the outgoing link with an outgoing link of one of the central modules include:

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

ii) for each of the outgoing links of the central module, an arbiter for selecting an outgoing link of the input module from among those that sent a request.

34. The dispatch scheduler of claim 16 wherein there are:

k input modules, each having n input ports, k groups of n virtual output queues, and m outgoing links.