Scheduling apparatus and scheduling method

• US 5,920,568 A
• Filed: 01/29/1997
• Issued: 07/06/1999
• Est. Priority Date: 06/17/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Kurita, Toshihiko, Iida, Ichiro
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US08/790,443
• Time in Patent Office: 888 Days
• Field of Search: 370/414, 370/416-418, 370/395, 370/468, 370/229, 370/335, 370/351, 370/428, 370/429, 370/411, 370/412
• US Class Current: 370/412
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6235 Variable service order

Abstract

A scheduling apparatus and a scheduling method are capable of reading data elements from a plurality of queues in such a form that past hysteresis reflects therein. The scheduling apparatus comprises a queue hysteresis table for storing a value e_-- count obtained subtracting the number of data elements (packets in a router) actually fetched out of the queue, from the number of times with which this queue becomes a processing target with respect to each queue. The apparatus also comprises a scheduling unit for cyclically designating each queue as a processing target, adding "1" to e_-- count, corresponding to that queue, in the queue hysteresis table if no data elements exist in the queue designated as the processing target, consecutively fetching, from the processing target queue, the data elements the number of which corresponds to a value of e_-- count corresponding to the queue if the data elements exist in the processing target queue, and decrementing the value of e_-- count by the number of fetched data elements.

Claims

1. A scheduling apparatus for fetching data elements from a plurality of queues for storing inputted data elements, comprising:

storing means for storing read-out number data defined as data for determining an upper limit of the number of the data elements that are read extra from the queue with respect to each of the plurality of queues;

designating means for cyclically designating one of the plurality of queues as a processing target;

judging means for judging whether or not the queue designated by said designating means is stored with the data elements;

adding means for adding "1" to the read-out number data, corresponding to the queue designated by said designating means, in said storing means when said judging means judges that the queue is not stored with the data elements; and

data element fetching means for fetching a data element from the queue designated by said designating means when said judging means judges that the queue is stored with the data elements, judging whether or not the read-out number data corresponding to this queue is above 1, and, when the read-out number data is over 1, fetching from the queue the data elements an upper limit number of which is the read-out number data, and further subtracting the number of the fetched data elements from the read-out number data corresponding to that queue.

2. A scheduling apparatus according to claim 1, wherein said adding means adds "1" to the read-out number data as far as the read-out number data takes a value less than a predetermined value.

3. A scheduling apparatus according to claim 1, further comprising:

counting means for counting the number of queues stored with no data elements when said designating means designates a predetermined queue as a processing target; and

controlling means for controlling said data element fetching means so that a sum of the numbers of data elements fetched extract from the respective queues till the predetermined queue is again designated by said designating means, does not exceed a count value by said counting means.

4. A scheduling apparatus according to claim 1, wherein said storing means further stores an empty count number used for determining an initial value for the read-out number data with respect to each queue,

said adding means adds "1" respectively to the empty count number and the read-out number data, corresponding to the queue designated by said designating means, in said storing means, and

said scheduling apparatus further comprises setting means for setting a value of the corresponding empty count number in each piece of read-out number data within said storing means with a predetermined period and setting "0" in each of the empty count numbers.

5. A scheduling apparatus for fetching data elements from a plurality of queues for storing inputted data elements, comprising:

storing means for storing size data with respect to each of the plurality of queues;

designating means for cyclically designating one of the plurality of queues as a processing target;

adding means for adding a specified value to the size data, corresponding to that queue, in said storing means if the queue designated by said designating means is not stored in its head with the data element having a size under the size data, corresponding to the queue, in said storing means; and

data element fetching means for, if the queue designated by said designating means is stored in its head with the data element having the size under the size data corresponding to that queue, fetching the same data element, and repeating a process of subtracting a size of the fetched data element from the size data corresponding to that queue till the data elements having the size under the size data come to non-existence in the head of that queue.

6. A scheduling apparatus according to claim 5, wherein said adding means adds the specified value to the size data as far as the size data takes a value less than a predetermined value.

7. A scheduling apparatus according to claim 5, further comprising:

controlling means for controlling said data element fetching means so that a sum of sizes of the data elements fetched after one piece of data element from one queue does not exceed a predetermined value.

8. A scheduling apparatus according to claim 5, wherein said storing means stores second size data used for determining an initial value for the size data with respect to each queue,

said adding means adds a specified value respectively to the second size data and the size data, corresponding to the queue designated by said designating means, in said storing means, and

said scheduling apparatus further comprises setting means for setting a value of the corresponding second size data in each piece of size data within said storing means with a predetermined period and setting "0" in each piece of the second size data.

9. A scheduling method of fetching data elements from a plurality of queues for storing inputted data elements, comprising:

a step of cyclically designating one of the plurality of queues as a processing target;

a step of adding "1" to read-out number data corresponding to that queue if the relevant queue is not stored with the data elements with respect to each queue designated as the processing target;

a step of fetching a data element from the relevant queue if this queue is stored with the data elements;

a step of judging whether or not the read-out number data of the relevant queue is over "1";

a step of further fetching, from the relevant queue, the read-out number data an upper limit number of which is the read-out number data; and

a step of subtracting the number of the fetched data elements from the read-out number data.

10. A scheduling method of fetching data elements from a plurality of queues for storing inputted data elements, comprising:

a step of cyclically designating one of the plurality of queues as a processing target;

a step of adding a specified value to size data corresponding to the relevant queue if the head of this queue is not stored with the data elements having a size under size data corresponding to that queue with respect to each queue designated as the processing target;

a step of fetching, if the data element having the size under the size data corresponding to the relevant queue is stored in the head of that queue, this piece of data element; and

a step of repeating a process of subtracting a size of the fetched data element from the size data corresponding to the relevant queue till the data element having the size under the size data comes to non-existence in the head of the relevant queue.