Controlled latency with dynamically limited queue depth...

Details Controlled latency with dynamically limited queue depth... Controlled latency with dynamically limited queue depth...

2000-05-11

2004-05-18

Nguyen, Chau (Department: 2666)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S428000

Reexamination Certificate

active

06738386

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to queuing techniques. More particularly, it relates to an efficient and reliable technique and apparatus for queuing high priority data for processing (e.g., for transmission) without risk of high latency due to prior queued lower priority data.
2. Background of Related Art
Queues are generally used by communications systems as a sort of holding bin for data packets after they are prepared for transmission, but before they are actually processed for transmission.
For instance,
FIG. 6
shows the relevant portion of an exemplary transmission system including one or more software queues
120
-
124
containing data packets for transmission.
In particular, as shown in
FIG. 6
, the software queues
120
-
124
contain data of varying degrees of priority for transmission. For instance, data packets corresponding to a lower priority data transmission may relate, e.g., to the uploading of a web page, while a higher priority data transmission may relate, e.g., to a video or audio transmission. The particular priority levels assigned to various data packets may be determined by the particular application.
A priority queuing scheme
610
typically includes the relevant algorithms and/or arbitration rules to determine a fair ordering of data packets for transmission by the transmission system in a hardware portion of the transmission system. Generally speaking, a higher priority data packet will typically be pulled from the high priority queue
124
more frequently than will be lower priority data packets from a lower priority queue
120
, so as to conform to desired latency requirements. Latency requirements relate to the maximum delays which will be incurred by any particular data packet, e.g., from the time it is placed on the relevant software queue
120
-
124
until the time that it finally gets pulled from a hardware queue
650
for appropriate encoding and transmission, e.g., by an RF front end.
A typical priority queuing routine in the priority queue module
610
will look at the contents of the various software priority queues
120
-
124
, and determine which packet should be next added to the hardware transmit queue
650
. Typical priority queuing routine considers, e.g., which packets are available, fairness, priority, throughput, transmit latency, and many other factors when deciding which data packet should be queued next into the hardware queue
650
.
However, most priority queuing schemes do not work well when higher priority queues are temporarily empty. For instance, if there are only low priority packets available in the lowest priority queue
120
and no data packets available in the highest priority queue
124
, then the priority queuing routine in the priority queue module
610
will fill the hardware transmit queue
650
with only low priority data. This may occur over a period of time, filling up the hardware queue
650
with only low priority packets, which must be cleared (i.e., transmitted) before the hardware queue
650
can accept any additional data packets for transmission. Although it is usually desirable to keep the hardware queue
650
as full as possible to optimize throughput, once a higher priority packet finally becomes available, the high priority packet will be placed onto the end of the hardware transmit queue
650
, and may even have to wait for placement on the hardware queue
650
, causing significant latency delays.
The typical conventional hardware transmit queue cannot easily be reordered, e.g., by software. This is because software reordering might create a race condition between the hardware and the software accessing the same hardware transmit queue
650
. Moreover, hardware reordering of a hardware transmit queue
650
would be costly to implement, and/or result in a slower operation of the hardware transmit queue
650
. Thus, the higher priority data packet, once reappearing in the higher priority software queue
124
, will be forced to experience a significant latency. This significant latency would include time it would take to transmit all low priority packets already in the hardware transmit queue
650
at the time that the higher priority data packet gets queued into the hardware transmit queue
650
. Moreover, in such situations, the significant latency time for the higher priority data packet may risk violation of latency constraints on the higher priority data packet.
The hardware transmit queue
650
could be made statically smaller to shorten the latency time through the hardware transmit queue
650
, but this would tend to decrease the throughput of the transmission system.
Accordingly, there is a need for an efficient and reliable queuing technique and apparatus which provides sufficient and reliable servicing of high priority data at all times without necessarily causing a sacrifice in throughput.
SUMMARY OF THE INVENTION
In accordance with the principles of the present invention, a data packet queue comprises a priority queuing module adapted to submit to a data queue data packets in accordance with a priority of the data packets. A priority history module is adapted to monitor a history of priority levels of data packets submitted to the data queue. A depth of the hardware data queue is adaptively limited based on the monitored history of the priority levels of data packets.
A method of balancing latency with throughput in a data packet queue in accordance with another aspect of the present invention comprises determining a priority level history with respect to past submissions to the data packet queue. A depth of the data packet queue is adaptively adjusted based on the determined priority level history.


REFERENCES:
patent: 6141323 (2000-10-01), Rusu et al.
patent: 6175554 (2001-01-01), Jang et al.
patent: 6466579 (2002-10-01), Scott et al.
patent: 6535484 (2003-03-01), Hughes et al.

Affiliated with

Also associated with

Rating

Controlled latency with dynamically limited queue depth... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Controlled latency with dynamically limited queue depth..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Controlled latency with dynamically limited queue depth... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3194909