Packet switch device and scheduling control method

• US 6,920,145 B2
• Filed: 01/12/2001
• Issued: 07/19/2005
• Est. Priority Date: 01/12/2000
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Tomonaga, Hiroshi, Kawarai, Kenichi, Matsuoka, Naoki
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/759,181
• Publication Number:
  US 20010007562A1
• Time in Patent Office: 1,649 Days
• Field of Search: 370/389, 370/412, 370/414, 370/415
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/503 Policing
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance
• CPC Class Codes: H04L 49/608 ATM switches adapted to switch variable length packets, e.g. IP packets

Abstract

A packet switch device having a plurality of input buffers; a packet switch; a plurality of schedulers, having a pipeline scheduling process module wherein a plurality of time units corresponding to the number of output lines is spent in scheduled sending process of the fixed length packets from the input buffer, and wherein the scheduled sending process is executed in a number of processes, in parallel, the number of processes corresponding to the number of the input lines, having a sending status management module wherein sending status of the fixed length packets which constitute one frame is managed for each of the input lines, and provided corresponding to any of the output lines; and at least one result notification module for notifying the input buffer of result information from the scheduled sending process performed by each of the plurality of schedulers. Further, in the scheduled sending process executed in a number of processes, in parallel, the device does not select the input line sending the fixed length packets corresponding to the same frame, and, after determining a selection, the device maintains the selection of the same input line until the completion of sending the fixed length packets corresponding to the same frame.

Claims

1. A packet switch device having a plurality of input lines, a plurality of output lines and a switching unit and where a frame of data received on an input line of the plurality of input lines is stored as one or more fixed length packets in an input buffer corresponding to the input line, where a plurality of input buffers are provided corresponding to the plurality of input lines, each input buffer of the plurality having a buffer memory that is logically divided into queues corresponding to the plurality of output lines, the buffer memory for temporarily storing the fixed length packets, and the switching unit switching the fixed length packets read from the buffer memory to the plurality of output lines, the packet switch device comprising:

a plurality of schedulers corresponding to the plurality of output lines; and

at least one result notification module for notifying the input buffers of the results of a scheduling process performed by each scheduler,

wherein each scheduler, comprising;

a scheduling process module in which a scheduling process is executed in a number of parallel processes corresponding to the number of the input lines, the scheduling process for scheduling the sending of the fixed length packets from each input buffer to the switching unit,

a sending status management module which manages a sending status of the fixed length packets constituting one frame for each of the input lines, and

a request management module for managing requested transfer information being information about the fixed length packets stored in the input buffer for each of the input lines;

wherein, after the scheduling process schedules an input line for sending of a fixed length packet from its corresponding input buffer, the scheduling process continuously schedules the input line until the sending of the fixed length packets constituting the same frame is completed,

wherein each scheduling process module executes the scheduling process in a number of parallel processes corresponding to the number of the input lines, and the input line scheduled by a scheduler for setting the fixed length packets constituting the same frame is not scheduled by another scheduler, and

wherein each scheduling process module decides which input line and corresponding input buffer will send the fixed length packets on the basis of the requested transfer information from the request management module, information on which input line is not currently scheduled, and the sending status managed by the sending status management module.

2. The packet switch device of claim 1, further comprising:

a transmission medium serially connecting the plurality of schedulers and providing undetermined information which is the information on which input line is not currently scheduled; and

a further transmission medium connecting the plurality of schedulers with one another for sending status information inputted into the sending status management module.

3. The packer switch device of claim 1, wherein the result notification module comprising:

a control unit for monitoring whether or not the input buffer is sending the fixed length packets that constitute one frame based on the result information from the scheduled sending process; and

a discarding process unit for discarding the result information for an input buffer, wherein

when notifying the result information for each of the plurality of schedulers to the plurality of input buffers, when the control unit monitoring the result information determines the result information is inputted from a different scheduler when the input buffer has already received result information for sending the fixed length packets that constitute a frame from another scheduler, the control unit instructs the discarding process unit to discard the results information from the different scheduler.

4. The packet switch device of claim 1, further comprising:

a unit for continuously expanding and connecting the plurality of schedulers and the result notification modules as the plurality of output lines increases in a manner where the plurality of schedulers corresponds with the plurality of output lines.

5. The packet switch device of claim 1, wherein

a plurality of fixed length packets constituting a frame include a first packet constituting a beginning of the frame and second packets constituting remaining packets of the plurality of fixed length packets constituting the frame, and the packet switch device further comprising:

a unit provided at a front stage of the input buffers for adding a frame end identifier to a second packet when the second packet is also a last packet of the plurality of fixed length packets constituting the frame.

6. The packet switch device of claim 1, wherein the scheduling process module manages, according to a QoS class, the requested transfer information sent from the input buffers, and the scheduling process performs the scheduling process for sending the fixed length packets with respect to the QoS class selected based on the result, of both QoS bandwidth control and QoS priority control in the output lines.

7. The packet switch device of claim 1, wherein each of the schedulers further comprising:

a load observation module for counting a number of occurrences of requested transfer information inputted from the input buffers within a predetermined time; and

an observation result reflecting module for instructing a timing to notify the observation result to the scheduling process module, the timing being shifted by a unit of time for each of the input buffers;

wherein the input buffer corresponding to the input line is selected according to a proportion of the number of occurrences of the requested transfer information that is observed.

8. A scheduling control method for scheduling the switching of frames of data from a plurality of input lines to a plurality of output lines where each frame of data arriving on an input line is converted to at least one fixed length packet prior to switching, comprising the steps of:

receiving requests to switch fixed length packets from input lines to output lines where the request includes information of a number of the fixed length packets constituting the frame of data, and an output destination;

executing the scheduling process as a number of processes executed in parallel, the number of parallel processes corresponding to the number of the input lines, and where the scheduling process has scheduled an input line with the number of fixed length packets constituting the frame of data to the output destination, the input line remains scheduled until a last fixed length packet constituting the frame of data is sent;

controlling the scheduling process where an input line currently sending fixed length packets constituting the frame of data to be switched to the output destination will not be scheduled in another scheduling process until the last fixed length packet constituting the frame of data is scheduled; and

managing a sending status of the fixed length packets constituting one frame for each of the input lines,

wherein each scheduling process decides which input line will send the fixed length packets on the basis of the request information, information on which input line is not currently scheduled, and the sending status.

9. The scheduling control method of claim 8, wherein

the scheduling process is executed in a plurality of time units corresponding to a number of the output lines, and is a pipeline process with the number of parallel processes corresponding to a number of the input lines.

10. The scheduling control method of claim 8, further comprising steps of:

receiving QoS information with the receiving requests to switch fixed length packets from input lines to output lines, for each QoS class, and

performing the scheduling process with respect to a QoS class selected based on the results of both QoS bandwidth control and QoS priority control of the output lines.

11. The scheduling control method of claim 8, further comprising steps of:

counting a number of occurrences of receiving requests to switch fixed length packets within a predetermined time;

instructing timing to reflect the counted result to the scheduling process, the timing being shifted by a unit of time for each of the input buffers; and

selecting the input buffer according to a proportion of the number of occurrences of requests to switch fixed length packets that is counted.