Implementing Priority Queues
Frequently models will require the implementation of priority queueing systems, in which different types of packets are accorded precedence over others while waiting to be forwarded to another module. In some cases, packets may be classified into a discrete set of priority levels. For example, a system might support just two priorities, high and low. In other cases, a continuous range of priorities may be needed. This might occur, for example, in a system which gives higher priority to queued packets the longer they have been in existence.
In either case, priority schemes create an ordering of packets in the queue. The continuous priority range model is used within subqueues, because a discrete priority classification can be regarded as a special case of the continuous system. However, the collection of subqueues within the queue can also be used as a mechanism to represent discrete priorities. This is done by creating one subqueue per priority level, and inserting packets into the correct subqueue based upon their priorities. When a packet is removed from the queue, the subqueues are scanned in priority order until a non-empty subqueue is found; this guarantees that the highest priority packet available is always removed first. This technique is illustrated by the following code fragments.
Figure 175: Using Subqueues to Implement Discrete Priorities
/* Insert an arriving packet into the appropriate subqueue. */
/* The "get_prio()" function returns the priority, which */
/* may be derived from a packet field, or from the packet's */
/* "priority" attribute, and is an integer between 0 and */
/* NUM_PRIOS - 1, where NUM_PRIOS is the number of priority */
/* levels (and also of subqueues). 0 is the highest priority. */
prio = get_prio (pk_ptr);
op_subq_pk_insert (prio, pk_ptr, OPC_QPOS_TAIL);
/* Extract the packet with the highest priority, that is, */
/* the packet at the head of the lowest-numbered subqueue */
/* that contains packets. As before, NUM_PRIOS is the */
/* number of priority levels and subqueues. */
pk_ptr = OPC_NIL;
for (i = 0; i < NUM_PRIOS; i++)
{
if (op_subq_empty (i) == OPC_FALSE)
{
pk_ptr = op_subq_pk_remove (i, OPC_QPOS_HEAD);
break;
}
}
if (pk_ptr != OPC_NIL)
op_pk_send (pk_ptr, OUT_STRM);
Within individual subqueues, the abstract subqueue position index constant OPC_QPOS_PRIO provides a convenient method for inserting or extracting packets while respecting priority ordering. For this purpose, the priority of a packet is specified by its “priority” attribute, which can be set with the Kernel Procedure op_pk_priority_set(). If the OPC_QPOS_PRIO constant is passed as the packet position to the Kernel Procedure op_subq_pk_insert(), the packet of interest will be inserted ahead of all packets of lower priority and behind all packets of higher or equal priority. Similarly, if this constant is passed to op_subq_pk_access() or op_subq_pk_remove(), these procedures will operate on the highest priority packet present in the subqueue. See Chapter 21 “Subqueue Package” on page 1 for more information.
A simple priority queueing process model called pc_prio (passive concentrating priority queue) is included with Modeler as part of the standard models library. This process model operates only on one subqueue, using the “priority” attribute of packets to order them. It can be employed in its default form for many priority queueing applications, or modified as desired, and serves as a basic example of a priority queue implementation.