Browse Prior Art Database

Priority Bypass Algorithm

IP.com Disclosure Number: IPCOM000105857D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 83K

Publishing Venue

IBM

Related People

Goldberg, SH: AUTHOR [+2]

Abstract

An algorithm is disclosed to efficiently remove messages from multiple priority queues giving precedence based on message priority and age on queue while insuring fair distribution across queues. Said algorithm guarantees all messages will be removed from the queue without requiring the use of timers or additional cleanup routines.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Priority Bypass Algorithm

      An algorithm is disclosed to efficiently remove messages from
multiple priority queues giving precedence based on message priority
and age on queue while insuring fair distribution across queues.
Said algorithm guarantees all messages will be removed from the queue
without requiring the use of timers or additional cleanup routines.

      The Figure shows the environment of messages, queues and
servers.  Each message has a designated priority.  Each queue may
contain multiple messages of any priority.  Each server removes
messages from a queue and processes them.  A server may serve one or
more queues.  A queue may be served by one or more servers.  Queues
and servers may be added or removed dynamically.  The number of
priorities supported is not critical to the priority bypass
algorithm.  This algorithm is only interesting when, for some period
of time, messages arrive faster than the servers can handle them.

      The priority bypass algorithm manages these priority queues
using the following criteria, specified in order of importance:

1.  Allows processing of the highest priority message first.

2.  Provides a fair distribution across different queues for messages
    of the same priority.

3.  Provides an aging factor that prevents a permanent lock out of
    lower priority messages by a continuous stream of higher priority
    messages.

      The priority bypass algorithm requires the use of an adjustment
amount applied to modify the priority of certain messages when they
are bypassed.  Priorities are adjusted when bypassed vertically or
horizontally.  A message is bypassed vertically when another message
is inserted directly in front of it on the same queue.  A message is
bypassed horizontally when it is the first message in a queue and it
is eligible to be dequeued but is passed over in favor of a message
from another queue.  There is a vertical adjustment value (V) for
each queue and a horizontal adjustment value (H) for each server.
The adjustment amount will be determined dynamically and will need to
be some fractional unit of the difference between two priorities.  A
new value is calculated when queues...