Two-dimensional pipelined scheduling technique

• US 8,005,092 B2
• Filed: 08/31/2009
• Issued: 08/23/2011
• Est. Priority Date: 10/02/2000
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kamiya, Satoshi, Ozaki, Hirokazu
• Primary Examiner(s): Ahmed; Salman
• Application Number:
  US12/550,941
• Publication Number:
  US 20090323695A1
• Time in Patent Office: 722 Days
• Field of Search: 370/395.4, 370/458, 370386-389, 370/395.41, 370/395.42, 370/395.43, 370/422, 370/423, 370/428, 370/429, 370/455, 370/459, 370/461, 370412-418
• US Class Current: 370/395.4
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/1546 using pipelined operation
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3045 Virtual queuing
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04L 49/503 Policing
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools

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.

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.

2. The method of claim 1, where the matrix of scheduling modules comprises an M×

M matrix of scheduling modules for scheduling packet forwarding for a combination of N input ports and N output ports, where M is an integer and N is an integer divisible by M, and where each scheduling module in the matrix of scheduling modules schedules packet forwarding for a group of N/M input ports and N/M output ports.

3. The method of claim 1, where the second service pattern differs from the first service pattern.

4. The method of claim 1, further comprising:

receiving prior reservation information for the first future time slot relating to the groups of input port/output port combinations in the first service pattern; and

scheduling packet forwarding for the groups of input port/output port combinations in the first service pattern at the first future time slot based on the received packet forwarding requests and the received prior reservation information.

5. The method of claim 4, where the prior reservation information is received from scheduling modules in a diagonal service pattern.

6. The method of claim 4, where the prior reservation information includes:

a logical representation of the input port/output port combinations,

a first logical indication associated with a received packet forwarding request for a particular input port/output port combination, and

a second logical indication associated with a no receive packet forwarding request for the particular input port/output port combination.

7. The method of claim 6, where the first logical indication comprises a logical “

1” and

the second logical indication comprises a logical “

0”

.

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.

9. The device of claim 8, where the scheduling modules comprise an M×

M matrix of scheduling modules for scheduling packet forwarding for a combination of N input ports and N output ports, where M is an integer and N is an integer divisible by M, and where each scheduling module, of the M×

M matrix of scheduling modules, schedules packet forwarding for a group of N/M input ports and N/M output ports.

10. The device of claim 8, where the second service pattern differs from the first service pattern.

11. The device of claim 8, where the switch scheduler is further to:

receive prior reservation information for the first future time slot relating to the groups of input port/output port combinations in the first service pattern, and

schedule packet forwarding operations for the groups of input port/output port combinations in the first service pattern at the first future time slot based on the received packet forwarding requests and the received prior reservation information.

12. The device of claim 8, where the switch scheduler is further to:

receive the prior reservation information in a third service pattern.

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.

14. The method of claim 13, where the scheduling modules comprise an M×

M matrix of scheduling modules for scheduling packet forwarding for a combination of N input ports and N output ports, where M is an integer and N is an integer divisible by M, and where each of the scheduling modules schedules packet forwarding for a group of N/M input ports and N/M output ports.

15. The method of claim 13, further comprising:

updating reservation information, associated with the groups of input port/output port combinations in the first service pattern, based on the scheduling and the prior reservation information; and

transferring the updated reservation information to scheduling modules in a second service pattern, 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.

16. The method of claim 15, where the second service pattern differs from the first service pattern.

17. The method of claim 15, where the second service pattern includes scheduling modules that are disposed adjacent to the scheduling modules in the first service pattern.

18. The method of claim 13, where the prior reservation information is received from scheduling modules in a third service pattern.

19. The method of claim 13, where the prior reservation information includes:

a logical representation of the input port/output port combinations,

a first logical indication associated with a received packet forwarding request for a particular input port/output port combination, and

a second logical indication associated with a no receive packet forwarding request for the particular input port/output port combination.

20. The method of claim 19, where the first logical indication comprises a logical “

1” and

the second logical indication comprises a logical “

0”

.