1. Field of the Invention
The present invention relates to a packet transmission apparatus for transmitting packets using a plurality of queues and relates to a method therefor.
2. Description of the Related Art
This type of packet transmission apparatus has various forms, such as routers, switches, or boards that perform those main functions. WFQ (Weighted Fair Queuing) is most generally used as a scheduling method in this type of packet transmission apparatus. According to WFQ, band control is carried out for each priority class. In this method, queues corresponding to the number of priority classes are prepared, packets are transmitted according to a weight that has been set for each priority class. Thereby band assurance is offered.
In WFQ, when a packet arrives, a priority class is determined from the header of the packet. The packet is queued in a queue corresponding to the priority. A time stamp is given to the first packet of each queue. The packet having the smallest time stamp value (the oldest packet in the queue) is selected as the packet to be transmitted.
Therefore, (1) if the number of queues is n, then the calculation of O (log n) is required to determine a minimum value. Further, (2) even in the case where the number of packets is so small that processing according to priority is not needed, processing-overheads are large because a classification is made based on priority with respect to queues.
Accordingly, in order to realize higher-speed processing, Japanese Unexamined Patent Publication No. Hei-10-13463 discloses the following technique. A preferential flag is kept on with respect to a preferential packet both in a non-congestion state and in a congestion state. In the congestion state (i.e., in the state where a queue length has reached a threshold), the preferential flag extracts the on-packet so as to again queue it at a special queue corresponding to congestion, and preferentially transmits the packet queuing at the special queue corresponding to congestion.
As a result, FIFO (First In First Out) is realized in the non-congestion state. Therefore higher processing speed is achieved than is possible with WFQ.
However, if this technique is applied, the following disadvantages will arise.
(1) The classification by priority of packets that have arrived is regularly needed. Additionally, there is a need to operate preferential flags on the basis of the results of the classification. Therefore, time loss because of the classification is unavoidable even in the non-congestion state.
(2) Further, in the congestion state, since there is a need to extract flags that are in an ON-state with reference to the preferential flag of each packet and carry out re-queuing (i.e., replacement of a large amount of packets), a processing burden enormously increases. Additionally, in the congestion state in which the space for queues is almost full, if such burdened processing as above is carried out in addition to the processing of the packets that have arrived, there might arise a fear that the arriving packets cannot be processed in time, and therefore a malfunction, such as packet loss, is invited.