Pipelined maximal-sized matching cell dispatch scheduling

Abstract

A Pipelined-based Maximal-sized Matching (PMM) scheduling approach for input-buffered switches relaxes the timing constraint for arbitration with a maximal matching scheme. In the PMM approach, arbitration may operate in a pipelined manner. Each subscheduler is allowed to take more than one time slot for its matching. Every time slot, one of them provides the matching result. The subscheduler can adopt a pre-existing efficient maximal matching algorithm such as iSLIP and DRRM. PMM maximizes the efficiency of the adopted arbitration scheme by allowing sufficient time for a number of iterations. PMM preserves 100% throughput under uniform traffic and fairness for best-effort traffic.

1. For use with a switch having a first number of input ports, a second number of output ports, each of the input ports having the second number of virtual output queues, and a third number of subschedulers, each of the third number of subschedulers being able to arbitrate matching to each of the second number of output ports, 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; 
 b) for each of the subschedulers, maintaining a second indicator F(i,j,k) for indicating whether the subscheduler is available or reserved; and 
 c) for each of the subschedulers, performing a matching operation, if it has been reserved, to match a cell buffered at a virtual output queue with its corresponding output port,
 wherein each of the subschedulers requires more than one cell time slot to generate a match from its matching operation, and 
 wherein the subschedulers can collectively generate a match result for each output port in each cell time slot. 
 
 
     
     
       2. The method of  claim 1  wherein each of the subschedulers requires the third number of cell time slots to generate a match from its matching operation. 
     
     
       3. The method of  claim 1  wherein each of the subschedulers require no more than the third number of cell time slots to generate a match results from its matching operation. 
     
     
       4. The method of  claim 1  wherein fairness for best-effort traffic is maintained. 
     
     
       5. The method of  claim 1  wherein the matching operation is a matching operation selected from a group of matching operations consisting of (A) Dual Round-Robin Matching, and (B) iterative-SLIP. 
     
     
       6. The method of  claim 1  further comprising:
 d) if a cell buffered at a virtual output queue has been successfully matched with its corresponding output port, informing the virtual output queue. 
 
     
     
       7. The method of  claim 6  further comprising:
 e) 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. 
 
     
     
       8. The method of  claim 7  wherein the head of line cell is dispatched in a next cell time slot. 
     
     
       9. The method of  claim 1  further comprising:
 e) if a cell buffered at a virtual output queue has been successfully matched with its corresponding output port, then dispatching its head of line cell. 
 
     
     
       10. The method of  claim 9  wherein the head of line cell is dispatched in a next cell time slot. 
     
     
       11. 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,
 wherein the count is incremented upon learning that a new cell has arrived at the virtual output queue. 
 
     
     
       12. The method of  claim 11  wherein the count is decremented when an available subscheduler is reserved for considering a head of line cell at a corresponding virtual output queue. 
     
     
       13. The method of  claim 1  wherein the second indicator, for each of the subschedulers, is set to indicate that the associated subscheduler 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  wherein the second indicator, for each of the subschedulers, is set to indicate that the associated subscheduler is available if the associated subscheduler matches a cell buffered at a virtual output queue with its corresponding output port. 
     
     
       15. The method of  claim 1  wherein the second indicator is set to indicate that a k th  subscheduler is reserved if the first indicator indicates that a corresponding virtual output queue is storing a cell awaiting dispatch arbitration,
 wherein k is set to the current cell time slot modulo the third number. 
 
     
     
       16. For use with a switch including a first number of output ports, a second number of input ports, and the first number of virtual output queues associated with each of the second number of input ports, a dispatch scheduler comprising:
 a) a third number of subschedulers; 
 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; and 
 c) a second indicator, for each of the subschedulers, indicating whether the subscheduler is available or reserved,
 wherein each of the subschedulers 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, 
 wherein each of the subschedulers requires more than one cell time slot to generate a match from its matching operation, and 
 wherein the subschedulers can collectively generate a match result for each output port in each cell time slot. 
 
 
     
     
       17. The dispatch scheduler of  claim 16  wherein each of the subschedulers requires the third number of cell time slots to generate a match from its matching operation. 
     
     
       18. The dispatch scheduler of  claim 16  wherein each of the subschedulers require no more than the third number of cell time slots to generate a match results from its matching operation. 
     
     
       19. The dispatch scheduler of  claim 16  wherein fairness for best-effort traffic is maintained. 
     
     
       20. The dispatch scheduler of  claim 16  wherein the matching operation is a matching operation selected from a group of matching operations consisting of (A) Dual Round-Robin Matching, and (B) iterative-SLIP. 
     
     
       21. 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. 
     
     
       22. 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. 
     
     
       23. The dispatch scheduler of  claim 22  wherein the head of line cell is dispatched in a next cell time slot. 
     
     
       24. 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,
 wherein the count is incremented upon learning that a new cell has arrived at the virtual output queue. 
 
     
     
       25. The dispatch scheduler of  claim 24  wherein the count is decremented when an available subscheduler is reserved for considering a head of line cell at a corresponding virtual output queue. 
     
     
       26. The dispatch scheduler of  claim 16  wherein the second indicator, for each of the subschedulers, is set to indicate that the associated subscheduler is reserved if the first indicator indicates that a corresponding virtual output queue is storing a cell awaiting dispatch arbitration. 
     
     
       27. The dispatch scheduler of  claim 16  wherein the second indicator, for each of the subschedulers, is set to indicate that the associated subscheduler is available if the associated subscheduler matches a cell buffered at a virtual output queue with its corresponding output port. 
     
     
       28. The dispatch scheduler of  claim 16  wherein the second indicator is set to indicate that a k th  subscheduler is reserved if the first indicator indicates that a corresponding virtual output queue is storing a cell awaiting dispatch,
 wherein k is set to the current cell time slot modulo the third number. 
 
     
     
       29. For use with a switch having a first number of input ports, a second number of output ports, each of the input ports having the second number of virtual output queues, and a third number of subschedulers, each of the third number of subschedulers being able to arbitrate matching to each of the second number of output ports, a method for scheduling the dispatch of cells or packets stored in the virtual output queues, the method comprising for each of the subschedulers, performing a matching operation, if it has been reserved, to match a cell buffered at a virtual output queue with its corresponding output port,
 wherein each of the subschedulers requires more than one cell time slot to generate a match from its matching operation, 
 wherein the subschedulers can collectively generate a match result for each output port in each cell time slot, and 
 fairness is maintained for best-effort traffic. 
 
     
     
       30. The method of  claim 29  wherein each of the subschedulers requires the third number of cell time slots to generate a match from its matching operation. 
     
     
       31. The method of  claim 29  wherein each of the subschedulers require no more than the third number of cell time slots to generate a match results from its matching operation. 
     
     
       32. The method of  claim 29  wherein the matching operation is a matching operation selected from a group of matching operations consisting of (A) Dual Round-Robin Matching, and (B) iterative-SLIP. 
     
     
       33. A method for scheduling the dispatch of cells stored in an output queue of a switch, the method comprising:
 maintaining a first indicator for indicating whether the output queue is storing a cell awaiting dispatch arbitration;   maintaining a second indicator for indicating whether a subscheduler is available or reserved; and   performing a matching operation to match a cell buffered at the output queue with a corresponding output port if, based on the first indicator the output queue is storing the cell awaiting dispatch arbitration and if, based on the second indicator, the subscheduler has been reserved,   wherein the subscheduler requires more than one cell time slot to generate a match from the matching operation, and wherein the subscheduler collectively generates a match result in each cell time slot for the output port.   
     
     
       34. The method of claim 33, wherein the subscheduler requires a number of cell time slots equal to a total number of subschedulers to generate the match from the matching operation. 
     
     
       35. The method of claim 33, wherein the subscheduler requires no more than a number of cell time slots equal to a total number of subschedulers to generate the match results from the matching operation. 
     
     
       36. The method of claim 33, wherein fairness for best-effort traffic is maintained. 
     
     
       37. The method of claim 33, wherein the matching operation comprises at least one of the following: a Dual Round-Robin Matching operation and an iterative-SLIP operation. 
     
     
       38. The method of claim 33, further comprising, if the cell buffered at the output queue has been successfully matched with the corresponding output port, informing the output queue. 
     
     
       39. The method of claim 38 further comprising, if the output queue has been informed that it has been successfully matched with the corresponding output port, dispatching a head of line cell. 
     
     
       40. The method of claim 39, wherein the head of line cell is dispatched in a next cell time slot. 
     
     
       41. The method of claim 33, further comprising, if the cell buffered at the output queue has been successfully matched with the corresponding output port, dispatching a head of line cell. 
     
     
       42. The method of claim 41, wherein the head of line cell is dispatched in a next cell time slot. 
     
     
       43. The method of claim 33, wherein the first indicator for indicating whether the 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 output queue. 
     
     
       44. The method of claim 43, wherein the count is decremented when the subscheduler is reserved for considering a head of line cell at the corresponding output queue. 
     
     
       45. The method of claim 33, wherein the second indicator is set to indicate that the subscheduler is reserved if the first indicator indicates that the corresponding output queue is storing a cell awaiting dispatch arbitration. 
     
     
       46. The method of claim 33, wherein the second indicator is set to indicate that the subscheduler is available if the associated subscheduler matches a cell buffered at the output queue with the corresponding output port. 
     
     
       47. The method of claim 33 further comprising a plurality of subschedulers that define an order, wherein each of the subschedulers have a respective position in the order, and wherein the second indicator is set to indicate the subscheduler at the respective position is reserved if the first indicator indicates that the corresponding output queue is storing a cell awaiting dispatch arbitration, wherein the respective position is set to the current cell time slot modulo a total number of the plurality of subschedulers. 
     
     
       48. A dispatch scheduler for use with a switch, the dispatch scheduler comprising:
 a) a subscheduler;   b) a first indicator module having a first indicator, associated with an output queue, for indicating whether the output queue is storing a cell awaiting dispatch arbitration; and   c) a second indicator module having a second indicator for indicating whether the subscheduler is available or reserved,   wherein the subscheduler is configured to perform a matching operation to match a cell buffered at the output queue with a corresponding output port if, based on the first indicator the output queue is storing the cell awaiting dispatch arbitration and if, based on the second indicator, the subscheduler has been reserved, wherein the subscheduler requires more than one cell time slot to generate a match from the matching operation, and wherein the subscheduler collectively generates a match result in each cell time slot for the output port.   
     
     
       49. The dispatch scheduler of claim 48, wherein the subscheduler requires a number of cell time slots equal to a total number of subschedulers to generate the match from the matching operation. 
     
     
       50. The dispatch scheduler of claim 48, wherein the subscheduler requires no more than a number of cell time slots equal to a total number of subschedulers to generate the match results from the matching operation. 
     
     
       51. The dispatch scheduler of claim 48, wherein fairness for best-effort traffic is maintained. 
     
     
       52. The dispatch scheduler of claim 48, wherein the matching operation comprises at least one of the following: a Dual Round-Robin Matching operation and an iterative-SLIP operation. 
     
     
       53. The dispatch scheduler of claim 48, wherein if a cell buffered at the output queue has been successfully matched with the corresponding output port, the output queue is so informed. 
     
     
       54. The dispatch scheduler of claim 48, wherein if a cell buffered at the output queue has been successfully matched with the corresponding output port, a head of line cell is dispatched. 
     
     
       55. The dispatch scheduler of claim 54, wherein the head of line cell is dispatched in a next cell time slot. 
     
     
       56. The dispatch scheduler of claim 48, wherein the first indicator is a count, and wherein the count is incremented upon learning that a new cell has arrived at the output queue. 
     
     
       57. The dispatch scheduler of claim 56, wherein the count is decremented when the subscheduler is reserved for considering a head of line cell at the corresponding output queue. 
     
     
       58. The dispatch scheduler of claim 48, wherein the second indicator is set to indicate that the subscheduler is reserved if the first indicator indicates that the corresponding output queue is storing a cell awaiting dispatch arbitration. 
     
     
       59. The dispatch scheduler of claim 48, wherein the second indicator is set to indicate that the subscheduler is available if the subscheduler matches a cell buffered at the output queue with the corresponding output port. 
     
     
       60. The dispatch scheduler of claim 48 further comprising a plurality of subschedulers that define an order, wherein each of the subschedulers have a respective position in the order, and wherein the second indicator is set to indicate the subscheduler at the respective position is reserved if the first indicator indicates that the corresponding output queue is storing a cell awaiting dispatch arbitration, wherein the respective position is set to the current cell time slot modulo a total number of the plurality of subschedulers.