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

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.

1. For use with a A method for scheduling the dispatch of cells or packets in a multi-stage switch, the multi-stage switch having
 a plurality of central modules, each having outgoing links, and
 a plurality of input modules, each including 
 a first number of input ports, each of the input ports having a second number of 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 or packets stored in the virtual output queues, the method comprising: 
 a) for each of the virtual output queues, maintaining a first indicator for indicating whether the virtual output queue is storing a cell awaiting dispatch arbitration; and 
 b) 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 via an outgoing link of the input module, wherein the matching operation includes:
 i) for an input module, matching a non-empty virtual output queue with an outgoing link of the input module, and 
 ii) matching the outgoing link of the input module with an outgoing link of the associated central module, 
 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 with an outgoing link of the input module includes
 A) broadcasting a request for the non-empty virtual output queue to an arbiter of the sub-scheduler for each of the outgoing links of the input module; 
 B) selecting, with the arbiter, of the sub-scheduler, 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, of the sub-scheduler, for the selected non-empty virtual output queue; and 
 D) selecting, with the arbiter, of the sub-scheduler, of the selected non-empty virtual output queue, an outgoing link of the input module from among the one or more outgoing links that sent a grant. 
 
     
     
       3. The method of  claim 2  wherein the act of selecting, with the arbiter, of the sub-scheduler, 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. 
     
     
       4. The method of  claim 3  wherein the round robin discipline moves through groups of virtual output queues, before moving through virtual output queues within each group. 
     
     
       5. The method of  claim 2  wherein each of the acts of following is performed at least twice within the third number of cell time slots: 
 A) broadcasting a request for the non-empty virtual output queue to an arbiter of the sub-scheduler for each of the outgoing links of the input module; 
 B) selecting, with the arbiter of the sub-scheduler 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 of the sub-scheduler for the selected non-empty virtual output queue; and 
 D) selecting, with the arbiter of the sub-scheduler 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 the third number of cell time slots. 
     
     
       6. The method of  claim 1  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. 
     
     
       7. 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. 
 
     
     
       8. The method of  claim 7  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. 
 
     
     
       9. The method of  claim 1  wherein the first indicator, for each of the virtual output queues, for indicating whether the virtual output queue is storing a cell awaiting dispatch, is a count, and
 wherein the count is incremented upon learning that a new cell has arrived at the virtual output queue. 
 
     
     
       10. The method of  claim 9  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. 
     
     
       11. 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. 
 
 
     
     
       12. 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. 
 
 
     
     
       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 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. 
 
 
     
     
       14. For A dispatch scheduler 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 of output ports, 
 a plurality of input modules, each including virtual output queues and outgoing links coupled with each of the plurality of central modules, the input modules collectively including a second number of input ports, 
 
       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) for an input module, means for matching a non-empty virtual output queue with an outgoing link of the input module, and 
 ii) means for matching the outgoing link of the input module with an outgoing link of the associated central module, 
 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. 
 
 
     
     
       15. The dispatch scheduler of  claim 14  wherein the means for matching a non-empty virtual output queue with an outgoing link of the input module include includes: 
 A) 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; 
 B) for each of the outgoing links of the input module, an arbiter for selecting a non-empty virtual output queue that broadcast a request; 
 C) means for sending a grant to an arbiter for the selected non-empty virtual output queue; and 
 D) for the selected non-empty virtual output queue, an arbiter for selecting an outgoing link of the input module from among the one or more outgoing links of the input module that sent a grant. 
 
     
     
       16. The dispatch scheduler of  claim 14  wherein each of the sub-schedulers require requires no more than the third number of cell time slots to generate a match result from its matching operation. 
     
     
       17. The dispatch scheduler of  claim 14  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. 
     
     
       18. The dispatch scheduler of  claim 14  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. 
     
     
       19. The dispatch scheduler of  claim 14  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. 
 
     
     
       20. The dispatch scheduler of  claim 19  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. 
     
     
       21. The dispatch scheduler of  claim 14  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. 
 
 
     
     
       22. The dispatch scheduler of  claim 14  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. 
 
 
     
     
       23. The dispatch scheduler of  claim 14  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. 
 
 
     
     
       24. The dispatch scheduler of  claim 14  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, operates in accordance with a round robin discipline. 
     
     
       25. The dispatch scheduler of  claim 24  wherein the round robin discipline moves through groups of virtual output queues, before moving through virtual output queues within each group. 
     
     
       26. The dispatch scheduler of  claim 14  wherein the means for matching a non-empty virtual output queue with an outgoing link of the input module performs multiple iterations of matching a non-empty virtual output queue with an outgoing link of the input module within the third number of cell time slots. 
     
     
       27. A method for scheduling the dispatch of cells or packets stored in a virtual output queue of a multi-stage switch, the method comprising:
 maintaining a first indicator for indicating whether the virtual output queue is storing a cell awaiting dispatch arbitration; and   performing a matching operation using a sub-scheduler to match a cell buffered at the virtual output queue with an outgoing link of a central module via an outgoing link of an input module, wherein the matching operation comprises:
 matching a non-empty virtual output queue with the outgoing link of the input module, and 
 matching the outgoing link of the input module with the outgoing link of the associated central module, wherein the sub-scheduler requires more than one cell time slot to generate a match from the matching operation, and wherein the sub-scheduler collectively generates a match result in each cell time slot.  
   
     
     
       28. The method of claim 27, wherein matching a non-empty virtual output queue with an outgoing link of the input module comprises:
 broadcasting a request for the non-empty virtual output queue to an arbiter of the sub-scheduler for the outgoing links of the input module;   selecting, with the arbiter, of the sub-scheduler, the non-empty virtual output queue that broadcasts a request;   sending a grant to an arbiter, of the sub-scheduler, for the selected non-empty virtual output queue; and   selecting, with the arbiter, of the sub-scheduler, of the selected non-empty virtual output queue, the outgoing link of the input.    
     
     
       29. The method of claim 28, wherein selecting, with the arbiter, of the sub-scheduler, the non-empty virtual output queue that broadcasts a request is done using a round robin discipline.  
     
     
       30. The method of claim 29, wherein the round robin discipline moves through groups of virtual output queues, before moving through virtual output queues within each group.  
     
     
       31. The method of claim 28, wherein broadcasting a request for the non-empty virtual output queue; selecting the non-empty virtual output queue that broadcasts a request; sending a grant to an arbiter of the sub-scheduler; and selecting the outgoing link are performed at least twice within the cell time slots.  
     
     
       32. The method of claim 27, wherein the sub-scheduler requires no more than the number of cell time slots to generate a match result from its matching operation.  
     
     
       33. The method of claim 27 further comprising if a cell buffered at a virtual output queue has been successfully matched with the corresponding output port, informing the virtual output queue.  
     
     
       34. The method of claim 33 further comprising if the virtual output queue has been informed that it has been successfully matched with the corresponding output port, dispatching its head of line cell.  
     
     
       35. The method of claim 27, wherein the first indicator is a count, and wherein the count is incremented upon learning that a new cell has arrived at the virtual output queue.  
     
     
       36. The method of claim 35, wherein the count is decremented when the sub-scheduler is reserved for considering a head of line cell at the corresponding virtual output queue.  
     
     
       37. The method of claim 27, further comprising maintaining a second indicator for the virtual output queue, for indicating whether the sub-scheduler is available or reserved, wherein the second indicator is set to indicate that the associated sub-scheduler is reserved if the first indicator indicates that the corresponding virtual output queue is storing a cell awaiting dispatch arbitration.  
     
     
       38. The method of claim 27 further comprising maintaining a second indicator for the virtual output queue, for indicating whether the sub-scheduler is available or reserved, wherein the second indicator is set to indicate that the associated sub-scheduler is available if the associated sub-scheduler matches a cell buffered at the virtual output queue with the corresponding output port.  
     
     
       39. The method of claim 27 further comprising maintaining a second indicator for the virtual output queues, for indicating whether the sub-scheduler is available or reserved, wherein the second indicator is set to indicate that a sub-scheduler is reserved if the first indicator indicates that the corresponding virtual output queue is storing a cell awaiting dispatch and wherein the sub-scheduler is selected from a plurality of sub-schedulers based on the current cell time slot modulo the total number of sub-schedulers.  
     
     
       40. A dispatch scheduler for use with a multi-stage switch, the dispatch scheduler comprising:
 a sub-scheduler; and   a first indicator, associated with a virtual output queue, for indicating whether the virtual output queue is storing a cell awaiting dispatch arbitration, wherein the sub-scheduler is configured to perform a matching operation to match a cell buffered at the virtual output queue with an output port, and comprises:
 means for matching a non-empty virtual output queue with an outgoing link of an input module, and 
 means for matching the outgoing link of the input module with an outgoing link of an associated central module, wherein the sub-scheduler requires more than one cell time slot to generate a match from the matching operation, and wherein the sub-scheduler collectively generates a match result in each cell time slot.  
   
     
     
       41. The dispatch scheduler of claim 40 wherein the means for matching a non-empty virtual output queue with an outgoing link of the input module comprises 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; an arbiter for selecting the non-empty virtual output queue that broadcast a request; means for sending a grant the an arbiter for the selected non-empty virtual output queue; and for the selected non-empty virtual output queue, an arbiter for selecting an outgoing link of the input module.  
     
     
       42. The dispatch scheduler of claim 40, wherein each of the sub-schedulers require no more than the number of cell time slots to generate a match result from its matching operation.  
     
     
       43. The dispatch scheduler of claim 40, wherein if a cell buffered at the virtual output queue has been successfully matched with the corresponding output port, the virtual output queue is informed.  
     
     
       44. The dispatch scheduler of claim 40, wherein if a cell buffered at the virtual output queue has been successfully matched with the corresponding output port, a head of line cell is dispatched.  
     
     
       45. The dispatch scheduler of claim 40, wherein the first indicator is a count, and wherein the count is incremented upon learning that a new cell has arrived at the virtual output queue.  
     
     
       46. The dispatch scheduler of claim 45, wherein the count is decremented when the sub-scheduler is reserved for considering the head of line cell at the corresponding virtual output queue.  
     
     
       47. The dispatch scheduler of claim 40, further comprising a second indicator indicating whether the sub-scheduler is available or reserved, wherein the second indicator is set to indicate that the associated sub-scheduler is reserved if the first indicator indicates that the corresponding virtual output queue is storing a cell awaiting dispatch arbitration.  
     
     
       48. The dispatch scheduler of claim 40 further comprising a second indicator indicating whether the sub-scheduler is available or reserved, wherein the second indicator is set to indicate that the associated sub-scheduler is available if the associated sub-scheduler matches a cell buffered at the virtual output queue with the corresponding output port.  
     
     
       49. The dispatch scheduler of claim 40 further comprising a second indicator indicating whether the sub-scheduler is available or reserved, wherein the second indicator is set to indicate that a p.sup.th sub-scheduler is reserved if the first indicator indicates that the corresponding virtual output queue is storing a cell awaiting dispatch, and wherein p is set to the current cell time slot modulo the number of sub-schedulers.  
     
     
       50. The dispatch scheduler of claim 40, wherein the arbiter for selecting the non-empty virtual output queue that broadcasts a request operates using a round robin discipline.  
     
     
       51. The dispatch scheduler of claim 50, wherein the round robin discipline moves through groups of virtual output queues, before moving through virtual output queues within each group.  
     
     
       52. The dispatch scheduler of claim 40, wherein the means for matching the non-empty virtual output queue with an outgoing link of the input module performs multiple iterations of matching the non-empty virtual output queue with an outgoing link of the input module within the cell time slots.  
     
     
       53. A multi-stage switch with a computer-readable storage medium having computer-readable instructions for scheduling the dispatch of cells or packets stored in a virtual output queue of the multi-stage switch stored therein, the computer-readable comprising instructions for:
 maintaining a first indicator for indicating whether the virtual output queue is storing a cell awaiting dispatch arbitration; and   performing a matching operation using a sub-scheduler if the sub-scheduler has been reserved, to match a cell buffered at the virtual output queue with an outgoing link of a central module via an outgoing link of an input module, wherein the matching operation comprises:
 matching a non-empty virtual output queue with the outgoing link of the input module, and 
 matching the outgoing link of the input module with an outgoing link of the associated central module, wherein the sub-scheduler requires more than one cell time slot to generate a match from the matching operation, and wherein the sub-scheduler collectively generates a match result in each cell time slot.