Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-12-01
2002-06-18
Ton, Dang (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395420
Reexamination Certificate
active
06408006
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method of allocating buffers in a fast packet switched network, such as an ATM network or frame relay network, offering different QoS (Quality of Service) classes.
BACKGROUND OF THE INVENTION
The intention of QoS in a communication system, for example, one which is frame relay or ATM based for the purposes of discussion, is to allow the system to offer a differentiated service for applications with differing performance requirements, particularly in the areas of any information loss or delay which could occur during transfer. An example of two disparate applications which might simultaneously use QoS would be real time packet voice, and bulk electronic mail transfer. To achieve the goal of supporting multiple services, such communication networks and the switches that provide these services may need to add service categories with defined performance objectives for each quality of service.
Focusing on a switch, bridge, router etc. which is implementing QoS for packet (or cell) based communications, the architecture of such a node must be capable of buffering incoming packets. After or during packet processing, the transmit frame or cell scheduling algorithm creates the various service categories by determining the relative order with which the packets of multiple QoS levels should be transmitted. By virtue of the ordering of transmissions, a resulting delay can be incurred, particularly for lower performance service classes which may be large depending on the amount of higher priority traffic present at any given time. Packets which are delayed too long are considered stale and usually are dropped rather than delivered late. To limit the delay encountered by given packets or cells, and also limit the memory resources used by the switch, each QoS level is normally provided with either a buffering resource limit (memory), an aging limit (time) or both.
As examples of possible aging and resource implementations, enforcing aging could be done by recording the time when a packet arrived at the node and comparing it to the time when the packet is at the front of the transmission queue. In
FIG. 1
, packets A . . . G are placed in queues
1
,
2
,
3
of relating to different classes of service and having respectively highest, intermediate, and lowest priority. The enqueued packets are passed by the scheduler
5
into the interface
5
in a manner known per se. Packet D might need to wait for packets A-C to be transmitted first, depending on the scheduling algorithm applied. If the aging limit has expired by the time D is determined the next to be sent by the scheduling algorithm, D is discarded. For buffering resource limits, in
FIG. 1
packet G is dropped immediately from the lowest priority QoS level since there is already packets D-F buffered and adding G would exceed the buffer limit. One could increase the buffer limit to allow packet G, but only at the cost of increased memory demands.
The problem presented is how to optimally allocate memory to a priority level. For certain periods of time, there may not be any higher priority traffic and all packets admitted inside the buffer limit to a lower priority level will be able to be transmitted within the aging limit. In
FIG. 2
, packets A-C will all be transmitted within the aging limit.
For other periods of time, there may be large amounts of priority traffic, where lower priority traffic will not have the opportunity to be transmitted without exceeding aging or buffering limits. Focusing only on the lowest priority queue in
FIG. 3
, packet K will be dropped as expected due to buffering limits. However packets G-J will also eventually be dropped since they will not meet aging limits after packets A-F are transmitted first. Thus packets G-J are buffered despite having no chance of being transmitted.
Therefore, under congestion scenarios there will be node buffering resources uselessly allocated for lower priority class use. If the node has many different priorities per transmission interface and numerous transmission interfaces, the potential waste of buffer resources could become extremely significant.
An object of the invention is to reduce the amount of waste buffering under QoS transmission.
SUMMARY OF THE INVENTION
Accordingly the present invention provides a method of allocating buffers in a packet switched communication system offering different classes of service, each class of service being associated with a QoS queue, comprising the steps of computing the optimal buffering when a new packet for a particular QoS class arrives, setting the buffer limit for the queue associated with said particular class in accordance with said determination, and handling said new packet according to said set buffer limit.
Typically, the newly arrived packet is accepted into the queue or discarded according to the newly set queue size.
If the buffer limit is already set at the appropriate value, of course no change to the limit is actually required in order to set it to the desired value.
The buffering allocation for QoS in accordance with the invention is preferably performed by taking into account the timestamp of the frame or cell at the head of a given QoS queue, the transmission line speed, and the aging limit configured for the QoS class. As each newly processed frame or cell is placed into a particular QoS transmission queue, the optimal buffering at that point in time is determined and used to set the buffer limit for the queue, which in turn is used to determine how the new frame or cell is handled.
It is important to note that the invention is not dependent on the priority scheduling algorithm and can be applied to any QoS level. It is not computationally intensive, has low variable storage requirements and can be implemented in a real time system.
The term packet will be used herein to denote both frame and cell based systems.
The invention also provides a packet switched communication system offering different classes of service, each class of service being associated with a QoS queue, comprising means for determining the optimal buffering when a new packet for a particular QoS class arrives, means for setting the buffer limit for the queue associated with said particular class in accordance with said determination, and means for handling said new packet according to said newly set buffer limit.
REFERENCES:
patent: 6115390 (2000-09-01), Chuah
patent: 6167445 (2000-12-01), Gai et al.
patent: 6226277 (2001-05-01), Chuah
(Marks & Clerk)
Alcatel Canada Inc.
Ton Dang
LandOfFree
Adaptive buffering allocation under multiple quality of service does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive buffering allocation under multiple quality of service, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive buffering allocation under multiple quality of service will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2916979