Two-dimensional pipelined scheduling technique
First Claim
1. A method performed by a switching system, the method comprising:
- receiving, by a switch scheduler of the switching system, a first set of packet forwarding requests identifying input port/output port combinations for each of a number of packets;
identifying, by the switch scheduler, a first service pattern in a matrix of scheduling modules for scheduling packet forwarding for a first future time slot, where the first service pattern provides for scheduling of packets designating groups of input port/output port combinations that do not conflict with each other;
determining, by the switch scheduler, for the groups of input port/output port combinations in the first service pattern, the input port/output port combinations for which packet forwarding requests are received;
scheduling, by the switch scheduler, packet forwarding for the determined input port/output port combinations for which packet forwarding requests are received;
updating, by the switch scheduler, reservation information associated with the groups of input port/output port combinations in the first service pattern to reflect the scheduling; and
transferring, by the switch scheduler, the updated reservation information to scheduling modules in a second service pattern in the matrix of scheduling modules for scheduling packet forwarding for a second future time slot, where the second service pattern provides for scheduling of packets designating additional groups of input port/output port combinations that do not conflict with each other.
0 Assignments
0 Petitions
Accused Products
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 modulo 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.
28 Citations
20 Claims
-
1. A method performed by a switching system, the method comprising:
-
receiving, by a switch scheduler of the switching system, a first set of packet forwarding requests identifying input port/output port combinations for each of a number of packets; identifying, by the switch scheduler, a first service pattern in a matrix of scheduling modules for scheduling packet forwarding for a first future time slot, where the first service pattern provides for scheduling of packets designating groups of input port/output port combinations that do not conflict with each other; determining, by the switch scheduler, for the groups of input port/output port combinations in the first service pattern, the input port/output port combinations for which packet forwarding requests are received; scheduling, by the switch scheduler, packet forwarding for the determined input port/output port combinations for which packet forwarding requests are received; updating, by the switch scheduler, reservation information associated with the groups of input port/output port combinations in the first service pattern to reflect the scheduling; and transferring, by the switch scheduler, the updated reservation information to scheduling modules in a second service pattern in the matrix of scheduling modules for scheduling packet forwarding for a second future time slot, where the second service pattern provides for scheduling of packets designating additional groups of input port/output port combinations that do not conflict with each other. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A device, comprising:
-
a plurality of input ports to receive packets; a plurality of output ports to output packets; and a switch scheduler that includes a plurality of scheduling modules, each of the plurality of scheduling modules to schedule packet forwarding connections from a corresponding one or more of the plurality of input ports to a corresponding one or more of the plurality of output ports, where the switch scheduler is to; receive a first set of packet forwarding requests identifying input port/output port combinations for each of a number of the received packets, schedule packet forwarding operations in a first future time slot for groups of input port/output port combinations in a first service pattern, where the first service pattern designates groups of input port/output port combinations that do not conflict with each other and where the scheduling is based on the received first set of packet forwarding requests, update reservation information associated with the groups of input port/output port combinations in the first service pattern to reflect the scheduling, and transfer the updated reservation information to scheduling modules in a second service pattern, where the second service pattern is to schedule packets designating additional groups of input port/output port combinations that do not conflict with each other. - View Dependent Claims (9, 10, 11, 12)
-
-
13. A method performed by a switching system, the method comprising:
-
receiving, by the switching system, at scheduling modules in a switch scheduler of the switching system, a group of packet forwarding requests designating packets to be forwarded, where each of the packet forwarding requests identifies an input port/output port combination associated with a packet to be forwarded; receiving, at a first group of scheduling modules in a first service pattern, prior reservation information relating to prior scheduled forwarding operations associated with the scheduling modules in the first service pattern, where the first service pattern is to schedule packets designating groups of input port/output port combinations that do not conflict with each other; and scheduling, by the switching system, packet forwarding operations for the input port/output port combinations in the first service pattern based on the prior reservation information and the received packet forwarding requests. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification