TWO-DIMENSIONAL PIPELINED SCHEDULING TECHNIQUE

• US 20090323695A1
• Filed: 08/31/2009
• Published: 12/31/2009
• Est. Priority Date: 10/02/2000
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: KAMIYA, Satoshi, OZAKI, Hirokazu
• Granted Patent: US 8,005,092 B2
• Time in Patent Office: Days
• 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 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-9. -9. (canceled)