Two-dimensional pipelined scheduling technique

Abstract

A scheduler allowing high-speed scheduling scalable with the number of input and output ports of a crosspoint switch and suppressed unfairness among inputs is disclosed. The scheduler includes an M×M matrix of scheduling modules, each of which schedules packet forwarding connections from a corresponding input group of input ports to selected ones of a corresponding output group of output ports based on reservation information. A diagonal module pattern is used to determine a set of M scheduling modules to avoid coming into collision with each other. Each determined scheduling module performs reservation of packet forwarding connections based on current reservation information and transfers updated reservation information in row and column directions of the M×M matrix.

1. A scheduler for scheduling packet forwarding connections from N input ports to selected ones of N output ports at each time slot in a crosspoint switch, wherein N is a positive integer, comprising:
 an M×M matrix of scheduling modules, each of which schedules packet forwarding connections from a corresponding input group of input ports to selected ones of a corresponding output group of output ports based on reservation information of combinations of corresponding input and output ports at each time slot, wherein the N input ports are equally divided into M input groups and the N output ports are equally divided into M output groups; and 
 a selector for selecting a sequential one of different module patterns covering the M×M matrix of scheduling modules, wherein each of the different module patterns determines a set of M scheduling modules to avoid coming into collision with each other and determines a sequence of transferring reservation information, 
 wherein a scheduling module determined by a selected module pattern performs reservation of packet forwarding connections based on current reservation information of combinations of corresponding input and output ports and transfers updated reservation information according to the sequence determined by the selected module pattern. 
 
     
     
       2. The scheduler according to  claim 1 , wherein each of the different module patterns is a diagonal service pattern in a predetermined diagonal module group. 
     
     
       3. A pipelined scheduling method for an N×N crosspoint switch for connecting N input ports to selected ones of N output ports at each time slot, comprising the steps of:
 a) storing N logical queues for each of the N input ports, corresponding to respective ones of the N output ports, wherein the N input ports are equally divided into M input groups and the N output ports are equally divided into M output groups; 
 b) storing packet forwarding requests in an M×M matrix of modules, each of which stores packet forwarding requests from a corresponding input group of input ports to selected ones of a corresponding output group of output ports; 
 c) selecting M module patterns covering the M×M matrix of modules, wherein each of the module patterns determines a different set of M modules to avoid coming into collision with each other; and 
 d) performing the following steps d.1) through d.3) in each of the M modules determined by each of the selected M module patterns at each time slot to perform pipelined scheduling:
 d.1) reserving combinations of corresponding input and output ports at a predetermined future time slot depending on the corresponding packet forwarding requests based on input port reservation information and output port reservation information, which are received from two previous-stage modules in row and column directions of the M×M matrix; 
 d.2) updating the input ports reservation information and the output port reservation information depending on which combinations are reserved; and 
 d.3) transferring updated input port reservation information and updated output port reservation information to two subsequent-stage modules in row and column directions of the M×M matrix. 
 
 
     
     
       4. The pipelined scheduling method according to  claim 3 , wherein the step d) is concurrently performed in M scheduling processes for different future time slots, wherein each of the M scheduling processes starts with a different one of the selected M module patterns. 
     
     
       5. The pipelined scheduling method according to  claim 3 , wherein each of the selected M module patterns is a diagonal service pattern in a predetermined diagonal module group. 
     
     
       6. A scheduler for an N×N crosspoint switch for connecting N input ports to selected ones of N output ports at each time slot, comprising:
 N logical queues for each of the N input ports, corresponding to respective ones of the N output ports, wherein the N input ports are equally divided into M input groups and the N output ports are equally divided into M output groups; 
 an M×M matrix of scheduling modules, each of which stores packet forwarding requests from a corresponding input group of input ports to selected ones of a corresponding output group of output ports and schedules corresponding packet forwarding connections based on corresponding packet forwarding requests, input port reservation information and output port reservation information; 
 a selector for selecting M module patterns covering the M×M matrix of scheduling modules, wherein each of the M module patterns determines a different set of M scheduling modules to avoid coming into collision with each other, 
 wherein each of the M scheduling modules determined by each of the selected module patterns performs, at each time slot, reservation of corresponding packet forwarding requests for a predetermined future time slot, updates the input port reservation information and the output port reservation information depending on the reservation, and transfers updated input port reservation information and updated output port reservation information to two subsequent-stage modules in row and column directions of the M×M matrix. 
 
     
     
       7. The scheduler according to  claim 6 , wherein the scheduling modules determined by the selected M module patterns concurrently perform M scheduling processes for different future time slots, wherein each of the M scheduling processes starts with a different one of the selected M module patterns. 
     
     
       8. A method for scheduling packet forwarding connections providing combinations of N input ports and N output ports of a crosspoint switch, comprising the steps of:
 grouping possible combinations of the N input ports and the N output ports into M×M groups, wherein the N input ports are equally divided into M groups and the N output ports are equally divided into M groups; 
 allocating a packet forwarding request from an input port to a desired output port to a corresponding one of the M×M groups; 
 sequentially selecting a predetermined set of M diagonal service patterns in the M×M groups; and 
 scheduling packet forwarding connections in pipelines according to a sequentially selected diagonal service pattern. 
 
     
     
       9. The method according to  claim 8 , wherein the packet forwarding connections are concurrently scheduled in M scheduling processes for different future time slots, wherein each of the M scheduling processes starts with a different one of the M diagonal service patterns.