Packet scheduling device

Details Packet scheduling device Packet scheduling device

2000-08-15

2004-06-22

Vanderpuye, Kenneth (Department: 2661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395420

Reexamination Certificate

active

06754215

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a packet scheduling device for conducting the scheduling of packet data, and more particularly to, a packet scheduling device for conducting efficiently the scheduling of variable-length packet data with multiple priority classes.
BACKGROUND OF THE INVENTION
Conventionally, in packet data networks, a variety of service classes are defined according to the kind of traffic, thereby the effective use of resources and the efficient data transfer in the network are achieved. For example, in the Internet service by Internet protocol (IP) there is less need to guarantee its quality of Service (QOS) such as network delay, but in general phone-call service there is need to guarantee the real-time performance. So, the optimum data transfer service of service class according to the kind of traffic is offered, thereby the optimum distribution of resource in the network is achieved.
The service class is defined as a priority class, for example, constant bit rate (CBR), real-time-variable bit rate (rt-VRB) or available bit rate (ABR). CBR is a service optimum to a traffic that requires the real-time performance to guarantee a constant bandwidth always. rt-VRB is a service suitable to a traffic that requires the real-time performance like CBR and the data transfer rate varies. ABR is a service for computer data transmission that does not require the real-time performance but no data loss in the network is allowed.
Users set in advance the priority class to each data flow. Each packet data is, in the packet data network, subject to the data transfer based on requirements such as QOS etc. concerning data discard rate or in-network delay defined according to the each set priority class.
To adapt to such traffic with a variety of priority classes, a packet scheduling device is placed at the post-stage of a packet switch or in the line. The packet scheduling device is provided with a buffer for each priority class, and outputs packet data of each priority class based on a minimum guarantee bandwidth set previously. The packet scheduling in selecting packet data to be output from the buffer provided for each priority class is generally performed by weighted round robin (WRR).
In recent years, the Internet traffic due to the popularization of the Internet increases, therefore it is required to conduct the priority control by packet scheduling to a packet of transmission control protocol/Internet protocol (TCP/IP) used in the Internet. A variety of packet scheduling devices to conduct such priority control have been suggested.
FIG. 1
is a block diagram showing the composition of a conventional packet scheduling device suggested. This packet scheduling device guarantees the bandwidth of each priority class in asynchronous transfer mode (ATM) cell transfer service. In
FIG. 1
, an ATM cell to the packet scheduling device is input to a queue selection part
11
. The ATM cell input is in advance provided with an identifier to indicate the priority class to the header. The queue selection part
11
refers to the header, selects any one of first to M-th queues
12
1
to
12
M
provided for each priority class to buffer multiple ATM cells, stores the input ATM cell
10
therein.
From each of the first to M-th queues
12
1
to
12
M
, queue length notification signal
13
to indicate the number of ATM cell accumulated is input to an output class selection part
14
and a reset control part
15
. Also, first to M-th weight counters
16
1
to
16
M
are provided for the first to M-th queues
12
1
to
12
M
, respectively, and a weight value corresponding to a bandwidth required to the priority class is in advance set to each of the weight counters. From each of the first to M-th weight counters
16
1
to
16
M
, a weight count value
17
as the count result is input to the output class selection part
14
and the reset control part
15
.
The class selection part
14
monitors the queue length notification signal
13
from each queue and the weight count value
17
from each weight counter, selects a queue to output cell by the WRR scheduling while referring to priority that the priority class assigned to each queue is further classified into high-priority class or low-priority class. The class selection part
14
sends output allowance signal to the selected queue. The reset control part
15
also monitors the queue length notification signal
13
from each queue and the weight count value
17
from each weight counter, sends reset instruction signal
19
to each of the first to M-th weight counters
16
1
to
16
M
when the product of the queue length Qi and weight count value Wi of priority class i becomes “0” in all priority classes.
The queue receiving the output allowance signal
18
sent from the class selection part
14
reads its first-accumulated cell of ATM cells stored in the queue, sends it to a cell output part
20
. The cell output part
20
outputs the cell to a post-stage device (not shown).
FIG. 2
is a flow chart showing schematically the WRR scheduling processing conducted by this packet scheduling device. In
FIG. 2
, first, the weight count values set for the respective queues of the first to M-th weight counters
16
1
to
16
M
are reset, and a predetermined weight count value for each weight counter is set (step S
30
). Then, provided that f(i) is the product of queue length Qi and weight count value of each queue, it is judged, in all queues, whether f(i) is “0” or not (step S
31
). If in all queues f(i) is “0” (step S
31
:N), i.e. if the queue length Qi to indicate whether there exists a cell accumulated in the queue is “0”, then returns to step S
30
.
On the other hand, if there exists any cell in any queue and therefore the weight count value Wi is not “0” (step S
31
:Y), then it is judged whether there exists a queue whose priority is classified into high-priority class in priority class with f(i) not “0”, or not (step S
32
). If there exists a queue whose priority class is classified into high-priority class in priority class with f(i) not “0” (step S
32
:Y), then an output class is selected from the judged priority class by WRR (step S
33
), and the weight count value Wi of the weight counter corresponding to this queue is subtracted by “1” (step S
34
), then returns to step S
31
.
If there exists no queue whose priority class is classified into high-priority class in priority class with f(i) not “0” (step S
32
:N), then an output class is selected from the judged low-priority class by WRR (step S
35
), and the weight count value Wi of the weight counter corresponding to this queue is subtracted by “1” (step S
34
), then returns to step S
31
.
Then, the similar selection processing from step S
31
to step S
34
is repeated, when f(i) becomes “0” in all queues at step S
31
, the weight count values are reset and are initialized into a predetermined weight value.
Such a method for packet scheduling device is disclosed in, e.g., Japanese patent application laid-open No. 11-68770 (1999) titled “An ATM switch scheduling method”. By the application of this method, an ATM cell can be output at a bandwidth guaranteed to each priority class according to a weight count value set to each priority class. Also, an ATM cell with high-priority class can be output preferentially without waiting for other ATM cell with low-priority class to be output. Therefore, the delay degradation of traffic in a priority class that requires its real-time performance can be avoided.
Also, Japanese patent application laid-open No. 10-84383 (1998) discloses a packet scheduling device that, as a scheduling key for storing scheduling information to indicate a flow target to be scheduled, one for a packet queue transmittable and one for a packet queue not transmittable are provided separately, and the transmission from the packet queue transmittable is allowed. Thereby, it can be avoided that a same flow continues to be selected until the corresponding counter to each queue becomes unable to make any decrement or a packet queue becomes empty.
However, in the metho

Affiliated with

Also associated with

Rating

Packet scheduling device does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Packet scheduling device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet scheduling device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3329102