Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-11-25
2001-05-08
An, Meng-Al T. (Department: 2154)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S414000, C370S429000, C370S237000, C370S235000, C709S200000, C709S241000, C709S232000, C709S234000
Reexamination Certificate
active
06229813
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to digital systems wherein processed items are temporarily stored in queues, typically having limited capacity, pending further processing and more particularly to a method and mechanism for controlling queue size in such systems by selectively assigning multiple control variables such as pointers to each of the queues.
BACKGROUND
In many digital systems, such as communications networks, user data and control traffic contend for processing time slots either within a system architecture or-at a system to system interface. In order to provide some control to the handling of such traffic it is common to generate one or more queues, typically in the form of first in first out (FIFO) buffers, wherein the traffic is separated in accordance with given traffic parameters and some form of arbitration is used to establish the order in which the queues are processed. Arbitration schemes such as round robin, exhaustive round robin or weighted round robin are commonly used.
In certain implementations, packets or cells, including both user data and control data are placed in queues for subsequent processing. If, however, the data packets or cells contain considerable information the data is placed in data buffers and the address assigned to each item in the data buffers is placed in the queues. Frequently, the items in the queues must be further processed either within the system or by an associated system having a separate processor.
The mechanisms for generating queues in software are generally well known. Typically, such queues are implemented as either an array such as a circular array or a linked list. Generally, queues make use of either an enqueue pointer or an index to identify where pointers to items or the items should be inserted into or added to the queue. Further, either a dequeue pointer or index to identify where pointers to items should be removed from the queue are provided. Optionally, a counter may be implemented that indicates the number of items or pointers to items currently stored on the queue.
Generally, the queues are of fixed size and before additional items may be added the queue size is checked to determine if there is room to insert another item. This is typically done by checking the optional counter described above or by calculating the difference between the enqueue pointer and the dequeue pointer.
A problem arises when there are multiple queues to be serviced and as discussed above, the items need to be processed by the system for some time after they have been removed from the queue. For a variety of reasons, i.e. division of responsibilities between processors for performance, access to memory systems in a multitask environment, interrupt handler, relatively complex algorithms for determining which queue to service next, etc., it is often desirable to have one task choose the next queue to remove an item from, remove the item and then pass it on to another processor, task, or procedure for subsequent processing.
Because the items are still being processed by the system after removal from the queue, the queue could be empty but a large number of items are still being consumed by the system. In order to prevent this situation from occurring, current implementations generally try to limit the rate at which items are removed from the queue so that items are dequeued at approximately the same rate at which they are subsequently processed.
This creates a difficult balance to achieve in practice and usually requires elaborate feedback mechanisms to instruct the processor responsible for dequeuing to either speed up or slow down.
A specific application requiring a mechanism for controlling queue size in a multiprocessor system relates to Newbridge Networks Corporation's Carrier Scale Internetworking (CSI) implementation. Carrier Scale Internetworking introduces the concept of Realms wherein a network is divided into virtual service networks which may encompass bridged or routed virtual private networks (VPN) or public internet connectivity. Through CSI a service provider can offer virtual private network services to individual customers. The service provider is also able to offer a differentiated class of service (CoS) through the CSI architecture. The Internetworking Service Card (ISC) within the CSI architecture provides, amongst other things, the class of service functionality. Currently, there are three classes of service offered, namely a control class for control traffic and standard and premium classes of service for user data traffic.
The ISC includes a multiprocessor environment wherein a first processor examines information packet headers and organizes the packets into separate queues according to the aforementioned criteria. The queues are serviced in accordance with an arbitration scheme and the items serviced from the queues are further processed in a second processor. As discussed previously, the task of controlling queue size in a multiprocessor environment presents a significant problem.
Accordingly, there is a requirement for an improved mechanism for controlling the queue length or queue size in a multi task processor system or a multiprocessor system in which items removed from queues continue to use up system resources during subsequent processing.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a mechanism by which the simple queue length comparisons which are done as part of the enqueing process, can be extended to effectively control the consumption of system resources in situations where items are removed from a queue and then continue to be processed by the system.
The present invention, therefore, relates to an environment in which: items or pointers to items are placed on queues; each queue cannot grow beyond some predetermined length which may or may not vary in response to the availability of resources in the system; items removed from the queues are subject to further processing either by one or more processors or by other tasks or procedures running on the same processor; and the items which have been removed from the queue and passed onto another processor/task/procedure continue to consume resources and hence need to be taken into consideration when calculating the current queue size to decide if additional items can be added to the queue.
The present invention involves the introduction of an additional control variable to each queue, this variable can be implemented as either a virtual dequeue pointer/index or a virtual queue length counter. When items are placed on the queue the queue size is checked. This is accomplished either by checking the size of the virtual queue length counter or by calculating the difference between the enqueue pointer and the virtual dequeue pointer. If too many items are present on the queue then an item is returned to the system free pool. This item may be either the item that was to be enqueued or one of the items already present on the queue depending on the desired behaviour of the system.
When items are dequeued, the dequeue pointer is used to identify the item to remove and the dequeue pointer is updated accordingly upon removal of an item. The queue length counter is also decremented if it is present. However, the virtual dequeue pointer or the virtual queue length counter is not modified at this time. The item is then passed onto another processor for further processing. When this further processing is completed the item is no longer being consumed by the system. The processor responsible for freeing the item updates the virtual dequeue pointer or decrements the virtual queue length counter.
Hence, when enqueuing occurs the queue length calculation includes not only the items that are still physically present on the queue but also includes items that have been removed from the queue but are still being consumed elsewhere in the system. This ensures that relatively slow processing of items removed from a particular queue cannot consume all the items in the system. The resource consumption is checked at the time item
Buchko Steven W.
Neville Wade
(Marks & Clerk)
Alcatel Canada Inc.
An Meng-Al T.
Lin Wen-Tai
LandOfFree
Pointer system for queue size control in a multi-task... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pointer system for queue size control in a multi-task..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pointer system for queue size control in a multi-task... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2486383