Packet transfer control apparatus and scheduling method therefor

Claim 2

A packet transfer control apparatus provided with at least one scheduler which controls the transfer by weighting the order of transfer for the head packets in the queues in the order from the packet having the earliest scheduled transfer finish time for packets stored in a plurality of queues to which are allocated reserved bandwidths individually determined in advance and, at the same time, allocating the resources (bandwidths) to all of the active queues in which packets to be transferred are stored, wherein the scheduler is provided with: a clustering means for dividing the head packets in the queues into clusters in accordance with the ratio between the packet length of the head packet in each queue and the reserved bandwidth (hereinafter referred to as the scheduled resource occupation time), a cluster managing means for holding the packets having the earliest scheduled transfer finish times among the packets in a cluster for all clusters as the first order packets, an inside-cluster selecting means for selecting the packet having the earliest scheduled transfer finish time for the cluster as the first order packet when a packet is deleted or added inside the cluster, and an inter-cluster selecting means for selecting the packet having the earliest scheduled transfer finish time as the top priority transfer packet from among the first order packets inside the clusters.

Claim 3

A packet transfer control apparatus as set forth in claim 2, wherein: said scheduler is provided with a reserved bandwidth use ratio computing means for computing the ratio (hereinafter referred to as the reserved bandwidth use ratio) of a cumulative value of the reserved bandwidths for the active queues with respect to the resources (bandwidths) and said inter-cluster selecting means is structured to calculate the scheduled transfer finish time based on the transfer start reference time of each first order packet, the scheduled resource occupation time, and the reserved bandwidth use ratio.

Claim 4

A packet transfer control apparatus as set forth in claim 2 or 3, wherein: said inside-cluster selecting means is structured to sort the packets in a cluster in the order from the earliest scheduled transfer finish time and said cluster managing means may be constituted so as to hold the packets sorted in the order from the earliest scheduled transfer finish time for every cluster.

Claim 5

A packet transfer control apparatus as set forth in claim 2 or 3, wherein: said inside-cluster selecting means is structured to perform the selection by switching between processing for selecting only the first order packet having the earliest scheduled transfer finish time from the packets in a cluster and processing for sorting them in the order from the one having the earliest scheduled transfer finish time, perform the processing for sorting in the order from the one having the earliest scheduled transfer finish time when the transfer time of a packet in transmission is more than a predetermined time, and perform the processing for selecting only the first order packet having the earliest scheduled transfer finish time when the transfer time of the packet in transmission is not more than a predetermined time.

Claim 6

A packet transfer control apparatus as set forth in any one of claims 2, 3, and 5, wherein the inside-cluster selecting means is constituted so as to select the packet having the earliest scheduled transfer finish time based on only said transfer start reference time of each packet in the cluster or said transfer start reference time and said scheduled resource occupation time.

Claim 7

A packet transfer control apparatus as set forth in claim 4 or 5, wherein said inside-cluster selecting means is constituted so as to sort the packets in the cluster in the order from the one having the earliest scheduled transfer finish time based on only said transfer start reference time of each packet in the cluster or said transfer start reference time and said scheduled resource occupation time.

Claim 8

A packet transfer control apparatus as set forth in any one of claims 2 to 7, wherein said clustering means is constituted so as to divide the head packets in the queues into clusters by discriminating the type of the application packet having traffic characteristics for which the scheduled resource occupation time is specified.

Claim 9

A packet transfer control apparatus as set forth in any one of claims 2 to 8, wherein: provision is made of a plurality of schedulers which perform different processing for allocation of the resources of the entire transmission system for packets stored in multi-queues differing for all clusters in accordance with the class of the quality of service, each scheduler is provided with a means for selecting the packet having the earliest scheduled transfer finish time from among the head packets for every multi-queue, and provision is made of a scheduler for selecting the packet having the earliest scheduled transfer finish time from among packets selected by the schedulers corresponding to the multi-queues.

Claim 10

A packet transfer control apparatus as set forth in claim 9, wherein at least one scheduler among said schedulers corresponding to the multi-queues is provided with a means for allocating bandwidths of a fixed rate to queues in the corresponding multi-queues and selecting the packet having the earliest scheduled transfer finish time.

Claim 11

A packet transfer scheduling method which transfers packets by weighting the order of transfer for head packets of queues in the order from the packet having the earliest scheduled transfer finish time for packets stored in a plurality of queues to which are allocated at least reserved bandwidths individually determined in advance and, at the same time, allocating resources (bandwidths) to all of the active queues in which packets to be transferred are stored, comprising: a step of dividing the head packets of the queues into clusters in accordance with scheduled resource occupation times of the head packets in the queues, a step of selecting the packet having the earliest scheduled transfer finish time for a cluster as a first order packet when a packet is deleted or added to packets in the cluster and holding this selected packet, and a step of selecting the packet having the earliest scheduled transfer finish time from among the first order packets in the clusters as a top priority transfer packet.

Claim 12

A packet transfer scheduling method as set forth in claim 11, further comprising a step of computing a reserved bandwidth use ratio of active queues and a step of calculating a scheduled transfer finish time during the selection among clusters based on the transfer start reference time of the first order packet, the scheduled resource occupation time, and the reserved bandwidth use ratio.

Claim 13

A packet transfer scheduling method as set forth in claim 11 or 12, further comprising, when achieving the selection in the clusters, a step of sorting the packets in a cluster in the order from the earliest scheduled transfer finish time and holding the sorted packets.

Claim 14

A packet transfer scheduling method as set forth in claim 11 or 12, further comprising, when achieving the selection in the clusters, a step of performing processing for sorting in the order from the packet having the earliest scheduled transfer finish time when the transfer time of a packet in transmission is more than a predetermined time and performing processing for selecting only the first order packet having the earliest scheduled transfer finish time when the transfer time of the packet in transmission is not more than a predetermined time.

Claim 15

A packet transfer scheduling method as set forth in claim 11, 12, or 14, further comprising, when achieving the selection in the clusters, a step of selecting the packet having the earliest scheduled transfer finish time based on only the transfer start reference time of each packet in the cluster or the transfer start reference time and the scheduled resource occupation time.

Claim 16

A packet transfer scheduling method as set forth in claim 13 or 14, further comprising, when achieving the selection in the clusters, a step of sorting the packets in the cluster in the order from the one having the earliest scheduled transfer finish time based on only the transfer start reference time of each packet in the cluster or the transfer start reference time and the scheduled resource occupation time.

Claim 17

A packet transfer scheduling method as set forth in any one of claims 11 to 16, further comprising, when achieving the selection in the clusters, a step of dividing the head packets of queues into clusters by discriminating the type of the application packet having traffic characteristics for which the scheduled resource occupation time is specified.