I'm currently working on redesigning the ifqueue model from my 4-year
experience with ALTQ.
The new model tries to remove FIFO-queue assumptions from the BSD
network code and drivers in order to accommodate various packet
scheduler and queue management mechanisms.

A brief summary of the design is attached below.  The full text of the
(still incomplete) design note is available from
http://www.csl.sony.co.jp/~kjc/software/altq-new-design.txt

The new model is already implemneted in the KAME development tree, and
working code is available for FreeBSD-2.2.8/3.5/4.1, NetBSD-1.4.2 and
OpenBSD-2.7 as a KAME snap kit.
http://www.kame.net/

I'd like to hear comments and suggestions.
(the copy of this message is sent to freebsd-net@freebsd.org,
tech-net@netbsd.org, and tech@openbsd.org)

-Kenjiro


Notes on the new ALTQ implementation

    The BSD systems need better output queueing abstraction to support
packet scheduling (e.g., CBQ) or active queue management (e.g., RED).
To introduce a new model, we need to convert the existing code to be
conformant to the new model.  But the problem is that there are too
many drivers to convert all at once.

    This is a proposal that allows incremental transition to the
new model.  (If we are going to modify the existing drivers, we need
to get it right.)
The model is designed for ALTQ but it is general enough for other
implementations so that we can make the driver conversion once and
for all.

The new model removes direct references to the fields
within ifp->if_snd, and defines the following macros to manipulate
ifp->if_snd:
	IFQ_ENQUEUE(ifq, m, err)
	IFQ_DEQUEUE(ifq, m)
	IFQ_POLL(ifq, m)
	IFQ_PURGE(ifq)
	IFQ_IS_EMPTY(ifq)
The new model also enforces some rules regarding how to use these
macros.

Another requirement for a driver is to work under rate-limiting.
 - IFQ_DEQUEUE() could return NULL even when IFQ_IS_EMPTY() is FALSE
   under rate-limiting.  a driver should always check if (m == NULL).
 - a driver is supposed to call if_start from the tx complete interrupt
   under late-limiting (in order to trigger the next dequeue).

For most drivers, it is a simple task of replacing old-style lines by
the corresponding new-style lines, and usually just a few lines need
to be modified.  But some drivers need more than that.
The old-style drivers still work with the original FIFO queue but
they cannot take advantage of new queueing disciplines.