Fair queue servicing using dynamic weights (DWFQ)

Details Fair queue servicing using dynamic weights (DWFQ) Fair queue servicing using dynamic weights (DWFQ)

1998-09-08

2001-11-13

Jung, Min (Department: 2663)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S412000

Reexamination Certificate

active

06317416

ABSTRACT:

This invention relates to the field of telecommunications, and more particularly to a method of fair queue servicing in asynchronous data networks, such as Asynchronous Transfer Mode (ATM) networks or more generally any packet switched network that supports more than one class of service.
The use of ATM by a continually increasing number of applications is driving a requirement to increase the number of service classes and to allow more flexibility in the service offerings. To support the application requirements, the ATM Forum is adding new service categories in new releases of ATM specifications. Furthermore, network providers are looking for the flexibility of defining multiple service classes for a given service category. The service classes are differentiated by their Quality-Of-Service requirements (QoS). The QoS requirements are configurable in accordance with a bi-dimensional matrix describing loss and delay. The delay jitter is another factor which needs to be bounded for some service classes.
Previously, three service categories were supported on an ATM network element, namely constant bit rate (CBR), variable bit rate (VBR) and unspecified bit rate (UBR). The CBR service is the only service that guarantees a bound on delay. It is used for time sensitive data, such as voice and video.
These various services can be supported by traditional exhaustive round-robin queuing among two priority queues. However, this simple technique cannot be used when the number of queues increases beyond two, because of the high potential of starvation for lower priority queues. Furthermore, the exhaustive round robin can only guarantee bounds on delay and delay variation for the highest priority queue. The support of multiple service class in an ATM switching product or multiplexer requires a minimum of one queue per class.
A queue scheduling algorithm, Weighted Fair Queuing (WFQ), has been recently proposed in the literature (see S. Golestani, A self-clocked Fair Queuing scheme for broadband applications. INFOCOM 1994. June 1994).
This scheduling scheme allows any number queues (service classes) to be serviced, while providing fair and work conserving access to bandwidth. One of the key features of WFQ is that the CDV (Cell Delay Variation) is bounded for any service class, as long as it is given a minimum weight.
This proposed scheme can be implemented in ATM products, However, it has not been determined how to set the servicing weights efficiently to take into account the dynamically changing bandwidth requirement of each service class (connection addition/removal, ABR flow control, Early packet Discard).
An object of the invention is to provide a framework that ensures that the weights are set appropriately to guarantee the desired Quality of Service and modified in real-time to ensure that the dynamic allocation of bandwidth across the classes is optimized.
According to the present invention there is provided a method of fair queue servicing at a queuing point in a multi-service class packet switched network, wherein incoming packets are received in buffers and outgoing packets are scheduled by a weighted fair queue scheduler characterized in that real-time information of buffer usage along with the minimum bandwidth requirement is used to dynamically modify the weights of the weighted fair queue scheduler.
Preferably the minimum bandwidth requirement is extracted during connection admission control.
The method is particularly suitable for use in ATM networks.
The DWFQ (Dynamic Weighted Fair Queuing) can be implemented at any queuing point which arbitrates servicing between n queues (n≧2).
The invention also provides a fair queue servicing arrangement in a multi-service class packet switched network, comprising a weighted fair queuing controller, and buffer means for receiving incoming packets in queues, characterized in that further comprises means for monitoring buffer usage for each queue, means for determining the bandwidth requirements of each class of service, and a service weights manager for dynamically modifying the weights of said weighted fair queuing controller means in response to said buffer usage and bandwidth requirements.
Preferably, the means for monitoring buffer usage a queue growth monitor which performs real-time estimation of the queue growth in said buffer means.


REFERENCES:
patent: 5179557 (1993-01-01), Kudo
patent: 5231633 (1993-07-01), Hluchyj et al.
patent: 5335224 (1994-08-01), Cole et al.
patent: 5432790 (1995-07-01), Hluchyj et al.
patent: 5463620 (1995-10-01), Sriram
patent: 5517495 (1996-05-01), Lund et al.
patent: 5623668 (1997-04-01), Nieuwenhuizen
Golestani; “A self-Clocked Fair Queueing Scheme for Broadband Applications”; IEEE 1994 pp. 636-646.

Affiliated with

Also associated with

Rating

Fair queue servicing using dynamic weights (DWFQ) does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fair queue servicing using dynamic weights (DWFQ), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair queue servicing using dynamic weights (DWFQ) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2570445