Implement WF2Q+ in dummynet.

1 files changed, 1135 insertions, 316 deletions

diff --git a/sys/netinet/ip_dummynet.c b/sys/netinet/ip_dummynet.c
index 5f8c091..830d9bf 100644
--- a/sys/netinet/ip_dummynet.c
+++ b/sys/netinet/ip_dummynet.c
@@ -36,6 +36,7 @@
  *
  * Most important Changes:
  *
+ * 000601: WF2Q+ support
  * 000106: large rewrite, use heaps to handle very many pipes.
  * 980513:	initial release
  *
@@ -70,9 +71,8 @@
 #endif
 
 /*
- * we keep a private variable for the simulation time, but probably
- * it would be better to use the already existing one "softticks"
- * (in sys/kern/kern_timer.c)
+ * We keep a private variable for the simulation time, but we could
+ * probably use an existing one ("softticks" in sys/kern/kern_timer.c)
  */
 static dn_key curr_time = 0 ; /* current simulation time */
 
@@ -80,16 +80,29 @@ static int dn_hash_size = 64 ;	/* default hash size */
 
 /* statistics on number of queue searches and search steps */
 static int searches, search_steps ;
-static int pipe_expire = 1 ;   /* expire queue if empty */
+static int pipe_expire = 0 ;   /* expire queue if empty */
+static int dn_max_ratio = 16 ; /* max queues/buckets ratio */
 
-static struct dn_heap ready_heap, extract_heap ;
+static int red_lookup_depth = 256;	/* RED - default lookup table depth */
+static int red_avg_pkt_size = 512;      /* RED - default medium packet size */
+static int red_max_pkt_size = 1500;     /* RED - default max packet size */
+
+/*
+ * ready_heap contains all dn_flow_queue's scheduled for action
+ * at a given time.
+ * wfq_ready_heap contains the schedulable pipe.
+ * Extract_heap contains pipes because it is there that packets
+ * in the delay line are held.
+ */
+static struct dn_heap ready_heap, extract_heap, wfq_ready_heap ;
 static int heap_init(struct dn_heap *h, int size) ;
 static int heap_insert (struct dn_heap *h, dn_key key1, void *p);
-static void heap_extract(struct dn_heap *h);
+static void heap_extract(struct dn_heap *h, void *obj);
 static void transmit_event(struct dn_pipe *pipe);
 static void ready_event(struct dn_flow_queue *q);
 
 static struct dn_pipe *all_pipes = NULL ;	/* list of all pipes */
+static struct dn_flow_set *all_flow_sets = NULL ;/* list of all flow_sets */
 
 #ifdef SYSCTL_NODE
 SYSCTL_NODE(_net_inet_ip, OID_AUTO, dummynet,
@@ -108,13 +121,24 @@ SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, search_steps,
 	    CTLFLAG_RD, &search_steps, 0, "Number of queue search steps");
 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, expire,
 	    CTLFLAG_RW, &pipe_expire, 0, "Expire queue if empty");
+SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, max_chain_len,
+	    CTLFLAG_RW, &dn_max_ratio, 0, 
+	"Max ratio between dynamic queues and buckets");
+SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_lookup_depth,
+	CTLFLAG_RD, &red_lookup_depth, 0, "Depth of RED lookup table");
+SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_avg_pkt_size,
+	CTLFLAG_RD, &red_avg_pkt_size, 0, "RED Medium packet size");
+SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_max_pkt_size,
+	CTLFLAG_RD, &red_max_pkt_size, 0, "RED Max packet size");
 #endif
 
+static int config_pipe(struct dn_pipe *p);
 static int ip_dn_ctl(struct sockopt *sopt);
 
 static void rt_unref(struct rtentry *);
 static void dummynet(void *);
 static void dummynet_flush(void);
+void dummynet_drain(void);
 
 /*
  * ip_fw_chain is used when deleting a pipe, because ipfw rules can
@@ -139,7 +163,7 @@ rt_unref(struct rtentry *rt)
  * Some macros help finding parent/children so we can optimize them.
  *
  * heap_init() is called to expand the heap when needed.
- * Increment size in blocks of 256 entries (which make one 4KB page)
+ * Increment size in blocks of 16 entries.
  * XXX failure to allocate a new element is a pretty bad failure
  * as we basically stall a whole queue forever!!
  * Returns 1 on error, 0 on success
@@ -147,9 +171,9 @@ rt_unref(struct rtentry *rt)
 #define HEAP_FATHER(x) ( ( (x) - 1 ) / 2 )
 #define HEAP_LEFT(x) ( 2*(x) + 1 )
 #define HEAP_IS_LEFT(x) ( (x) & 1 )
-#define HEAP_RIGHT(x) ( 2*(x) + 1 )
+#define HEAP_RIGHT(x) ( 2*(x) + 2 )
 #define	HEAP_SWAP(a, b, buffer) { buffer = a ; a = b ; b = buffer ; }
-#define HEAP_INCREMENT	255
+#define HEAP_INCREMENT	15
 
 static int
 heap_init(struct dn_heap *h, int new_size)
@@ -182,7 +206,13 @@ heap_init(struct dn_heap *h, int new_size)
  * already in place, and key is the position where to start the
  * bubble-up.
  * Returns 1 on failure (cannot allocate new heap entry)
+ *
+ * If offset > 0 the position (index, int) of the element in the heap is
+ * also stored in the element itself at the given offset in bytes.
  */
+#define SET_OFFSET(heap, node) \
+    if (heap->offset > 0) \
+	    *((int *)((char *)(heap->p[node].object) + heap->offset)) = node ;
 static int
 heap_insert(struct dn_heap *h, dn_key key1, void *p)
 {   
@@ -205,30 +235,39 @@ heap_insert(struct dn_heap *h, dn_key key1, void *p)
 
 	if (DN_KEY_LT( h->p[father].key, h->p[son].key ) )
 	    break ; /* found right position */ 
-	/* son smaller than father, swap and try again */
+	/* son smaller than father, swap and repeat */
 	HEAP_SWAP(h->p[son], h->p[father], tmp) ;
+	SET_OFFSET(h, son);
 	son = father ;
     }
+    SET_OFFSET(h, son);
     return 0 ;
 }
 
 /*
- * remove top element from heap
+ * remove top element from heap, or obj if obj != NULL
  */
 static void
-heap_extract(struct dn_heap *h)
+heap_extract(struct dn_heap *h, void *obj)
 {  
     int child, father, max = h->elements - 1 ;
+
     if (max < 0)
 	return ;
-
-    /* move up smallest child */
-    father = 0 ;
+    father = 0 ; /* default: move up smallest child */
+    if (obj != NULL) { /* extract specific element, index is at offset */
+	if (h->offset <= 0) {
+	    printf("*** extract from middle not supported!!!\n");
+	    return ; /* or maybe panic... */
+	}
+	father = *((int *)((char *)obj + h->offset)) ;
+    }
     child = HEAP_LEFT(father) ;		/* left child */
     while (child <= max) {		/* valid entry */
 	if (child != max && DN_KEY_LT(h->p[child+1].key, h->p[child].key) )
 	    child = child+1 ;		/* take right child, otherwise left */
 	h->p[father] = h->p[child] ;
+	SET_OFFSET(h, father);
 	father = child ;
 	child = HEAP_LEFT(child) ;   /* left child for next loop */
     }   
@@ -243,37 +282,88 @@ heap_extract(struct dn_heap *h)
 }           
 
 /*
+ * change object position and update references
+ */
+static void
+heap_move(struct dn_heap *h, dn_key new_key, void *object)
+{
+    int temp;
+    int i ;
+    int max = h->elements-1 ;
+    struct dn_heap_entry buf ;
+
+    if (h->offset <= 0)
+	panic("cannot move items on this heap");
+
+    i = *((int *)((char *)object + h->offset));
+    if (DN_KEY_LT(new_key, h->p[i].key) ) { /* must move up */
+	h->p[i].key = new_key ;
+	for (; i>0 && DN_KEY_LT(new_key, h->p[(temp = HEAP_FATHER(i))].key) ;
+		 i = temp ) { /* bubble up */
+	    HEAP_SWAP(h->p[i], h->p[temp], buf) ;
+	    SET_OFFSET(h, i);
+	}
+    } else {		/* must move down */
+	h->p[i].key = new_key ;
+	while ( (temp = HEAP_LEFT(i)) <= max ) { /* found left child */
+	    if ((temp != max) && DN_KEY_GT(h->p[temp].key, h->p[temp+1].key))
+		temp++ ; /* select child with min key */
+	    if (DN_KEY_GT(new_key, h->p[temp].key)) { /* go down */
+		HEAP_SWAP(h->p[i], h->p[temp], buf) ;
+		SET_OFFSET(h, i);
+	    } else
+		break ;
+	    i = temp ;
+	}
+    }
+    SET_OFFSET(h, i);
+}
+
+
+
+/*
  * heapify() will reorganize data inside an array to maintain the
  * heap property. It is needed when we delete a bunch of entries.
  */
 static void
 heapify(struct dn_heap *h)
 {
-    int father, i ;
-    struct dn_heap_entry tmp ;
+    int i ;
 
-    for (i = h->elements - 1 ; i > 0 ; i-- ) {
-	father = HEAP_FATHER(i) ;
-	if ( DN_KEY_LT(h->p[i].key, h->p[father].key) )
-	    HEAP_SWAP(h->p[father], h->p[i], tmp) ;
+    for (i = 0 ; i < h->elements ; i++ )
+	heap_insert(h, i , NULL) ;
     }
+
+/*
+ * cleanup the heap and free data structure
+ */
+static void
+heap_free(struct dn_heap *h)
+{
+    if (h->size >0 )
+	free(h->p, M_IPFW);
+    h->elements = h->size = 0 ;
 }
+
 /*
  * --- end of heap management functions ---
  */
 
 /*
- * Scheduler functions -- transmit_event(), ready_event()
+ * Scheduler functions:
  *
  * transmit_event() is called when the delay-line needs to enter
  * the scheduler, either because of existing pkts getting ready,
  * or new packets entering the queue. The event handled is the delivery
  * time of the packet.
  *
- * ready_event() does something similar with flow queues, and the
+ * ready_event() does something similar with fixed-rate queues, and the
  * event handled is the finish time of the head pkt.
  *
- * In both cases, we make sure that the data structures are consistent
+ * wfq_ready_event() does something similar with WFQ queues, and the
+ * event handled is the start time of the head pkt.
+ *
+ * In all cases, we make sure that the data structures are consistent
  * before passing pkts out, because this might trigger recursive
  * invocations of the procedures.
  */
@@ -282,12 +372,12 @@ transmit_event(struct dn_pipe *pipe)
 {
     struct dn_pkt *pkt ;
 
-    while ( (pkt = pipe->p.head) && DN_KEY_LEQ(pkt->output_time, curr_time) ) {
+    while ( (pkt = pipe->head) && DN_KEY_LEQ(pkt->output_time, curr_time) ) {
 	/*
 	 * first unlink, then call procedures, since ip_input() can invoke
 	 * ip_output() and viceversa, thus causing nested calls
 	 */
-	pipe->p.head = DN_NEXT(pkt) ;
+	pipe->head = DN_NEXT(pkt) ;
 
 	/*
 	 * The actual mbuf is preceded by a struct dn_pkt, resembling an mbuf
@@ -336,7 +426,7 @@ transmit_event(struct dn_pipe *pipe)
 	FREE(pkt, M_IPFW);
     }
     /* if there are leftover packets, put into the heap for next event */
-    if ( (pkt = pipe->p.head) )
+    if ( (pkt = pipe->head) )
          heap_insert(&extract_heap, pkt->output_time, pipe ) ;
     /* XXX should check errors on heap_insert, by draining the
      * whole pipe p and hoping in the future we are more successful
@@ -344,6 +434,37 @@ transmit_event(struct dn_pipe *pipe)
 }
 
 /*
+ * the following macro computes how many ticks we have to wait
+ * before being able to transmit a packet. The credit is taken from
+ * either a pipe (WF2Q) or a flow_queue (per-flow queueing)
+ */
+#define SET_TICKS(pkt, q, p)	\
+    (pkt->dn_m->m_pkthdr.len*8*hz - (q)->numbytes + p->bandwidth - 1 ) / \
+	    p->bandwidth ;
+
+/*
+ * extract pkt from queue, compute output time (could be now)
+ * and put into delay line (p_queue)
+ */
+static void
+move_pkt(struct dn_pkt *pkt, struct dn_flow_queue *q,
+	struct dn_pipe *p, int len)
+{
+    q->head = DN_NEXT(pkt) ;
+    q->len-- ;
+    q->len_bytes -= len ;
+
+    pkt->output_time = curr_time + p->delay ;
+
+    if (p->head == NULL)
+	p->head = pkt;
+    else
+	DN_NEXT(p->tail) = pkt;
+    p->tail = pkt;
+    DN_NEXT(p->tail) = NULL;
+}
+
+/*
  * ready_event() is invoked every time the queue must enter the
  * scheduler, either because the first packet arrives, or because
  * a previously scheduled event fired.
@@ -354,53 +475,152 @@ static void
 ready_event(struct dn_flow_queue *q)
 {
     struct dn_pkt *pkt;
-    struct dn_pipe *p = q->p ;
-    int p_was_empty = (p->p.head == NULL) ;
+    struct dn_pipe *p = q->fs->pipe ;
+    int p_was_empty ;
+
+    if (p == NULL) {
+	printf("ready_event- pipe is gone\n");
+	return ;
+    }
+    p_was_empty = (p->head == NULL) ;
 
-    while ( (pkt = q->r.head) != NULL ) {
-	int len = pkt->dn_m->m_pkthdr.len;
-	int len_scaled = p->bandwidth ? len*8*hz : 0 ;
 	/*
-	 * bandwidth==0 (no limit) means we can drain as many pkts as
-	 * needed from the queue. Setting len_scaled = 0 does the job.
+     * schedule fixed-rate queues linked to this pipe:
+     * Account for the bw accumulated since last scheduling, then
+     * drain as many pkts as allowed by q->numbytes and move to
+     * the delay line (in p) computing output time.
+     * bandwidth==0 (no limit) means we can drain the whole queue,
+     * setting len_scaled = 0 does the job.
 	 */
+    q->numbytes += ( curr_time - q->sched_time ) * p->bandwidth;
+    while ( (pkt = q->head) != NULL ) {
+	int len = pkt->dn_m->m_pkthdr.len;
+	int len_scaled = p->bandwidth ? len*8*hz : 0 ;
 	if (len_scaled > q->numbytes )
 	    break ;
-	/*
-	 * extract pkt from queue, compute output time (could be now)
-	 * and put into delay line (p_queue)
-	 */
 	q->numbytes -= len_scaled ;
-	q->r.head = DN_NEXT(pkt) ;
-	q->len-- ;
-	q->len_bytes -= len ;
-
-	pkt->output_time = curr_time + p->delay ;
-
-	if (p->p.head == NULL)
-	    p->p.head = pkt;
-	else
-            DN_NEXT(p->p.tail) = pkt;
-        p->p.tail = pkt;
-        DN_NEXT(p->p.tail) = NULL;
+	move_pkt(pkt, q, p, len);
     }
     /*
      * If we have more packets queued, schedule next ready event
      * (can only occur when bandwidth != 0, otherwise we would have
      * flushed the whole queue in the previous loop).
-     * To this purpose compute how many ticks to go for the next
-     * event, accounting for packet size and residual credit. This means
-     * we compute the finish time of the packet.
+     * To this purpose we record the current time and compute how many
+     * ticks to go for the finish time of the packet.
      */
-    if ( (pkt = q->r.head) != NULL ) { /* this implies bandwidth != 0 */
-	dn_key t ;
-	t = (pkt->dn_m->m_pkthdr.len*8*hz - q->numbytes + p->bandwidth - 1 ) /
-		p->bandwidth ;
-	q->numbytes += t * p->bandwidth ;
+    if ( (pkt = q->head) != NULL ) { /* this implies bandwidth != 0 */
+	dn_key t = SET_TICKS(pkt, q, p); /* ticks i have to wait */
+	q->sched_time = curr_time ;
 	heap_insert(&ready_heap, curr_time + t, (void *)q );
 	/* XXX should check errors on heap_insert, and drain the whole
 	 * queue on error hoping next time we are luckier.
 	 */
+    } else	/* RED needs to know when the queue becomes empty */
+	q->q_time = curr_time;
+    /*
+     * If the delay line was empty call transmit_event(p) now.
+     * Otherwise, the scheduler will take care of it.
+     */
+    if (p_was_empty)
+	transmit_event(p);
+}
+
+/*
+ * Called when we can transmit packets on WF2Q queues. Take pkts out of
+ * the queues at their start time, and enqueue into the delay line.
+ * Packets are drained until p->numbytes < 0. As long as
+ * len_scaled >= p->numbytes, the packet goes into the delay line
+ * with a deadline p->delay. For the last packet, if p->numbytes<0,
+ * there is an additional delay.
+ */
+static void
+ready_event_wfq(struct dn_pipe *p)
+{
+    int p_was_empty = (p->head == NULL) ;
+    struct dn_heap *sch = &(p->scheduler_heap);
+    struct dn_heap *blh = &(p->backlogged_heap);
+
+    if (p->if_name[0] == 0) /* tx clock is simulated */
+	p->numbytes += ( curr_time - p->sched_time ) * p->bandwidth;
+    else { /* tx clock is for real, the ifq must be empty or this is a NOP */
+	if (p->ifp && p->ifp->if_snd.ifq_head != NULL)
+	    return ;
+	else {
+	    DEB(printf("pipe %d ready from %s --\n",
+		p->pipe_nr, p->if_name);)
+	}
+    }
+
+
+    while ( sch->elements && p->numbytes >= 0 ) {
+	struct dn_heap *neh ;
+	u_int64_t normalized_service ;
+	struct dn_flow_queue *q = sch->p[0].object ;
+	struct dn_pkt *pkt = q->head;  
+	struct dn_flow_set *fs = q->fs;   
+	u_int64_t len = pkt->dn_m->m_pkthdr.len;
+	int len_scaled = p->bandwidth ? len*8*hz : 0 ;
+
+	heap_extract(sch, NULL); /* remove queue from heap */
+	p->numbytes -= len_scaled ;
+	move_pkt(pkt, q, p, len);
+	    
+	/* XXX should we do this at the end of the service ? */
+	/* evaluate normalized service */
+	normalized_service = (len<<MY_M)/p->sum ;
+	if (q->len == 0) { /* session not backlogged any more*/
+	    heap_extract(blh, q); /* remove queue from backlogged heap */
+	    p->sum -= fs->weight;
+	    fs->backlogged-- ;
+	} else { /* session backlogged again: update values */
+	    q->S = q->F ; /* update start time */
+	    len = (q->head)->dn_m->m_pkthdr.len;
+	    q->F += (len<<MY_M)/(u_int64_t) fs->weight ;
+	    /* update queue position in backlogged_heap */
+	    heap_move(blh, q->S, q);
+	}
+	/* update virtual time */
+	p->V += normalized_service ;
+	if (blh->elements > 0)
+	    p->V = MAX64 ( p->V, blh->p[0].key );
+	DEB(printf("-- %d backlogged, V is %d\n",
+		blh->elements, (int)(p->V >> MY_M) ); )
+
+	/* move from not_eligible_heap to scheduler_heap */
+	neh = &(p->not_eligible_heap) ;
+	while (neh->elements > 0 && DN_KEY_LEQ(neh->p[0].key, p->V) ) {
+	    struct dn_flow_queue *temp = neh->p[0].object ;
+	    heap_extract(neh, NULL);
+	    heap_insert(sch, temp->F, temp);
+	}
+
+	if (q->len) {/* need to reschedule queue */
+	    if ( DN_KEY_LEQ(q->S, p->V) )
+		heap_insert(sch, q->F, q); /* schedule following packet */
+	    else
+		heap_insert(neh, q->S, q); /* queue in not_eligible_heap */
+	}
+	if (p->if_name[0] != '\0') {/* tx clock is from a real thing */
+	    p->numbytes = -1 ; /* mark not ready for I/O */
+	    break ;
+	}
+    }
+    /*
+     * If we are getting clocks from dummynet (not a real interface) and
+     * If we are under credit, schedule the next ready event.
+     * Also fix the delivery time of the last packet.
+     */
+    if (p->if_name[0]==0 && p->numbytes < 0) { /* this implies bandwidth >0 */
+	dn_key t=0 ; /* number of ticks i have to wait */
+
+	if (p->bandwidth > 0)
+	    t = ( p->bandwidth -1 - p->numbytes) / p->bandwidth ;
+	p->tail->output_time += t ;
+	p->sched_time = curr_time ;
+	heap_insert(&wfq_ready_heap, curr_time + t, (void *)p);
+	/* XXX should check errors on heap_insert, and drain the whole
+	 * queue on error hoping next time we are luckier.
+	 */
     }
     /*
      * If the delay line was empty call transmit_event(p) now.
@@ -411,7 +631,7 @@ ready_event(struct dn_flow_queue *q)
 }
 
 /*
- * this is called once per tick, or HZ times per second. It is used to
+ * This is called once per tick, or HZ times per second. It is used to
  * increment the current tick counter and schedule expired events.
  */
 static void
@@ -420,62 +640,152 @@ dummynet(void * __unused unused)
     void *p ; /* generic parameter to handler */
     struct dn_heap *h ;
     int s ;
+    struct dn_heap *heaps[3];
+    int i;
 
+    heaps[0] = &ready_heap ;		/* fixed-rate queues */
+    heaps[1] = &wfq_ready_heap ;	/* wfq queues */
+    heaps[2] = &extract_heap ;		/* delay line */
     s = splnet(); /* avoid network interrupts... */
     curr_time++ ;
-    h = &ready_heap ;
+    for (i=0; i < 3 ; i++) {
+	h = heaps[i];
     while (h->elements > 0 && DN_KEY_LEQ(h->p[0].key, curr_time) ) {
-	/*
-	 * XXX if the event is late, we should probably credit the queue
-	 * by q->p->bandwidth * (delta_ticks). On the other hand, i dont
-	 * think this can ever occur with this code (i.e. curr_time will
-	 * still be incremented by one at each tick. Things might be
-	 * different if we were using the counter from the high priority
-	 * timer.
-	 */
-	if (h->p[0].key != curr_time)
-	    printf("-- dummynet: warning, event is %d ticks late\n",
-		curr_time - h->p[0].key);
-        p = h->p[0].object ;
-        heap_extract(h); /* need to extract before processing */
+	    DDB(if (h->p[0].key > curr_time)
+		printf("-- dummynet: warning, heap %d is %d ticks late\n",
+		    i, (int)(curr_time - h->p[0].key));)
+	    p = h->p[0].object ; /* store a copy before heap_extract */
+	    heap_extract(h, NULL); /* need to extract before processing */
+	    if (i == 0)
         ready_event(p) ;
-    }
-    h = &extract_heap ;
-    while (h->elements > 0 && DN_KEY_LEQ(h->p[0].key, curr_time) ) {
-	if (h->p[0].key != curr_time)	/* XXX same as above */
-	    printf("-- dummynet: warning, event is %d ticks late\n",
-		curr_time - h->p[0].key);
-        p = h->p[0].object ;
-        heap_extract(&extract_heap);
+	    else if (i == 1) {
+		struct dn_pipe *pipe = p;
+		if (pipe->if_name[0] != '\0')
+		    printf("*** bad ready_event_wfq for pipe %s\n",
+			pipe->if_name);
+		else
+		    ready_event_wfq(p) ;
+	    } else
         transmit_event(p);
     }
+    }
     splx(s);
     timeout(dummynet, NULL, 1);
 }
  
 /*
- * Given a pipe and a pkt in last_pkt, find a matching queue
+ * called by an interface when tx_rdy occurs.
+ */
+int
+if_tx_rdy(struct ifnet *ifp)
+{
+    struct dn_pipe *p;
+
+    for (p = all_pipes; p ; p = p->next )
+	if (p->ifp == ifp)
+	    break ;
+    if (p == NULL) {
+	char buf[32];
+	sprintf(buf, "%s%d",ifp->if_name, ifp->if_unit);
+	for (p = all_pipes; p ; p = p->next )
+	    if (!strcmp(p->if_name, buf) ) {
+		p->ifp = ifp ;
+		DEB(printf("++ tx rdy from %s (now found)\n", buf);)
+		break ;
+	    }
+    }
+    if (p != NULL) {
+	DEB(printf("++ tx rdy from %s%d - qlen %d\n", ifp->if_name,
+		ifp->if_unit, ifp->if_snd.ifq_len);)
+	p->numbytes = 0 ; /* mark ready for I/O */
+	ready_event_wfq(p);
+    }
+}
+
+/*
+ * Unconditionally expire empty queues in case of shortage.
+ * Returns the number of queues freed.
+ */
+static int
+expire_queues(struct dn_flow_set *fs)
+{
+    struct dn_flow_queue *q, *prev ;
+    int i, initial_elements = fs->rq_elements ;
+
+    if (fs->last_expired == time_second)
+	return 0 ;
+    fs->last_expired = time_second ;
+    for (i = 0 ; i <= fs->rq_size ; i++) /* last one is overflow */
+	for (prev=NULL, q = fs->rq[i] ; q != NULL ; )
+	    if (q->head != NULL) {
+  		prev = q ;
+  	        q = q->next ;
+  	    } else { /* entry is idle, expire it */
+		struct dn_flow_queue *old_q = q ;
+
+		if (prev != NULL)
+		    prev->next = q = q->next ;
+		else
+		    fs->rq[i] = q = q->next ;
+		fs->rq_elements-- ;
+		free(old_q, M_IPFW);
+	    }
+    return initial_elements - fs->rq_elements ;
+}
+
+/*
+ * If room, create a new queue and put at head of slot i;
+ * otherwise, create or use the default queue.
+ */
+static struct dn_flow_queue *
+create_queue(struct dn_flow_set *fs, int i)
+{
+    struct dn_flow_queue *q ;
+
+    if (fs->rq_elements > fs->rq_size * dn_max_ratio &&
+	    expire_queues(fs) == 0) {
+	/*
+	 * No way to get room, use or create overflow queue.
+	 */
+	i = fs->rq_size ;
+	if ( fs->rq[i] != NULL )
+	    return fs->rq[i] ;
+    }
+    q = malloc(sizeof(*q), M_IPFW, M_DONTWAIT) ;
+    if (q == NULL) {
+	printf("sorry, cannot allocate queue for new flow\n");
+	return NULL ;
+    }
+    bzero(q, sizeof(*q) );     /* needed */
+    q->fs = fs ;
+    q->hash_slot = i ;
+    q->next = fs->rq[i] ;
+    q->S = q->F = fs->pipe->V ;		/* set virtual times */
+    fs->rq[i] = q ;
+    fs->rq_elements++ ;
+    return q ;
+}
+
+/*
+ * Given a flow_set and a pkt in last_pkt, find a matching queue
  * after appropriate masking. The queue is moved to front
  * so that further searches take less time.
- * XXX if the queue is longer than some threshold should consider
- * purging old unused entries. They will get in the way every time
- * we have a new flow.
  */
 static struct dn_flow_queue *
-find_queue(struct dn_pipe *pipe)
+find_queue(struct dn_flow_set *fs)
 {
     int i = 0 ; /* we need i and q for new allocations */
     struct dn_flow_queue *q, *prev;
 
-    if ( !(pipe->flags & DN_HAVE_FLOW_MASK) )
-	q = pipe->rq[0] ;
+    if ( !(fs->flags_fs & DN_HAVE_FLOW_MASK) )
+	q = fs->rq[0] ;
     else {
 	/* first, do the masking */
-	last_pkt.dst_ip &= pipe->flow_mask.dst_ip ;
-	last_pkt.src_ip &= pipe->flow_mask.src_ip ;
-	last_pkt.dst_port &= pipe->flow_mask.dst_port ;
-	last_pkt.src_port &= pipe->flow_mask.src_port ;
-	last_pkt.proto &= pipe->flow_mask.proto ;
+	last_pkt.dst_ip &= fs->flow_mask.dst_ip ;
+	last_pkt.src_ip &= fs->flow_mask.src_ip ;
+	last_pkt.dst_port &= fs->flow_mask.dst_port ;
+	last_pkt.src_port &= fs->flow_mask.src_port ;
+	last_pkt.proto &= fs->flow_mask.proto ;
 	last_pkt.flags = 0 ; /* we don't care about this one */
 	/* then, hash function */
 	i = ( (last_pkt.dst_ip) & 0xffff ) ^
@@ -484,22 +794,22 @@ find_queue(struct dn_pipe *pipe)
 	    ( (last_pkt.src_ip >> 16 ) & 0xffff ) ^
 	    (last_pkt.dst_port << 1) ^ (last_pkt.src_port) ^
 	    (last_pkt.proto );
-	i = i % pipe->rq_size ;
+	i = i % fs->rq_size ;
 	/* finally, scan the current list for a match */
 	searches++ ;
-	for (prev=NULL, q = pipe->rq[i] ; q ; ) {
+	for (prev=NULL, q = fs->rq[i] ; q ; ) {
 	    search_steps++;
 	    if (bcmp(&last_pkt, &(q->id), sizeof(q->id) ) == 0)
 		break ; /* found */
-	    else if (pipe_expire && q->r.head == NULL) {
+	    else if (pipe_expire && q->head == NULL) {
 		/* entry is idle, expire it */
 		struct dn_flow_queue *old_q = q ;
 
 		if (prev != NULL)
 		    prev->next = q = q->next ;
 		else
-		    pipe->rq[i] = q = q->next ;
-		pipe->rq_elements-- ;
+		    fs->rq[i] = q = q->next ;
+		fs->rq_elements-- ;
 		free(old_q, M_IPFW);
 		continue ;
 	    }
@@ -508,83 +818,198 @@ find_queue(struct dn_pipe *pipe)
 	}
 	if (q && prev != NULL) { /* found and not in front */
 	    prev->next = q->next ;
-	    q->next = pipe->rq[i] ;
-	    pipe->rq[i] = q ;
+	    q->next = fs->rq[i] ;
+	    fs->rq[i] = q ;
 	}
     }
     if (q == NULL) { /* no match, need to allocate a new entry */
-	q = malloc(sizeof(*q), M_IPFW, M_DONTWAIT) ;
-	if (q == NULL) {
-	    printf("sorry, cannot allocate new flow\n");
-	    return NULL ;
-	}
-	bzero(q, sizeof(*q) );	/* needed */
+	q = create_queue(fs, i);
+	if (q != NULL)
 	q->id = last_pkt ;
-	q->p = pipe ;
-	q->hash_slot = i ;
-	q->next = pipe->rq[i] ;
-	pipe->rq[i] = q ;
-	pipe->rq_elements++ ;
-	DEB(printf("++ new queue (%d) for 0x%08x/0x%04x -> 0x%08x/0x%04x\n",
-		pipe->rq_elements,
-		last_pkt.src_ip, last_pkt.src_port,
-		last_pkt.dst_ip, last_pkt.dst_port); )
     }
     return q ;
 }
 
+static int
+red_drops(struct dn_flow_set *fs, struct dn_flow_queue *q, int len)
+{
+    /*
+     * RED algorithm
+     * 
+     * RED calculates the average queue size (avg) using a low-pass filter
+     * with an exponential weighted (w_q) moving average:
+     * 	avg  <-  (1-w_q) * avg + w_q * q_size
+     * where q_size is the queue length (measured in bytes or * packets).
+     * 
+     * If q_size == 0, we compute the idle time for the link, and set
+     *	avg = (1 - w_q)^(idle/s)
+     * where s is the time needed for transmitting a medium-sized packet.
+     * 
+     * Now, if avg < min_th the packet is enqueued.
+     * If avg > max_th the packet is dropped. Otherwise, the packet is
+     * dropped with probability P function of avg.
+     * 
+     */
+
+    int64_t p_b = 0;
+    /* queue in bytes or packets ? */
+    u_int q_size = (fs->flags_fs & DN_QSIZE_IS_BYTES) ? q->len_bytes : q->len;
+
+    DEB(printf("\n%d q: %2u ", (int) curr_time, q_size);)
+
+    /* average queue size estimation */
+    if (q_size != 0) {
+	/*
+	 * queue is not empty, avg <- avg + (q_size - avg) * w_q
+	 */
+	int diff = SCALE(q_size) - q->avg;
+	int64_t v = SCALE_MUL((int64_t) diff, (int64_t) fs->w_q);
+
+	q->avg += (int) v;
+    } else {
+	/*
+	 * queue is empty, find for how long the queue has been
+	 * empty and use a lookup table for computing
+	 * (1 - * w_q)^(idle_time/s) where s is the time to send a
+	 * (small) packet.
+	 * XXX check wraps...
+	 */
+	if (q->avg) {
+	    u_int t = (curr_time - q->q_time) / fs->lookup_step;
+
+	    q->avg = (t < fs->lookup_depth) ?
+		    SCALE_MUL(q->avg, fs->w_q_lookup[t]) : 0;
+	}
+    }
+    DEB(printf("avg: %u ", SCALE_VAL(q->avg));)
+
+    /* should i drop ? */
+
+    if (q->avg < fs->min_th) {
+	q->count = -1;
+	return 0; /* accept packet ; */
+    }
+    if (q->avg >= fs->max_th) { /* average queue >=  max threshold */
+	if (fs->flags_fs & DN_IS_GENTLE_RED) {
+	    /*
+	     * According to Gentle-RED, if avg is greater than max_th the
+	     * packet is dropped with a probability
+	     *	p_b = c_3 * avg - c_4
+	     * where c_3 = (1 - max_p) / max_th, and c_4 = 1 - 2 * max_p
+	     */
+	    p_b = SCALE_MUL((int64_t) fs->c_3, (int64_t) q->avg) - fs->c_4;
+	} else {
+	    q->count = -1;
+	    printf("- drop");
+	    return 1 ;
+	}
+    } else if (q->avg > fs->min_th) {
+	/*
+	 * we compute p_b using the linear dropping function p_b = c_1 *
+	 * avg - c_2, where c_1 = max_p / (max_th - min_th), and c_2 =
+	 * max_p * min_th / (max_th - min_th)
+	 */
+	p_b = SCALE_MUL((int64_t) fs->c_1, (int64_t) q->avg) - fs->c_2;
+    }
+    if (fs->flags_fs & DN_QSIZE_IS_BYTES)
+	p_b = (p_b * len) / fs->max_pkt_size;
+    if (++q->count == 0)
+	q->random = random() & 0xffff;
+    else {
+	/*
+	 * q->count counts packets arrived since last drop, so a greater
+	 * value of q->count means a greater packet drop probability.
+	 */
+	if (SCALE_MUL(p_b, SCALE((int64_t) q->count)) > q->random) {
+	    q->count = 0;
+	    DEB(printf("- red drop");)
+	    /* after a drop we calculate a new random value */
+	    q->random = random() & 0xffff;
+	    return 1;    /* drop */
+	}
+    }
+    /* end of RED algorithm */
+    return 0 ; /* accept */
+}
+
+static __inline
+struct dn_flow_set *
+locate_flowset(int pipe_nr, struct ip_fw_chain *rule)
+{
+    struct dn_flow_set *fs = NULL ;
+
+    if ( (rule->rule->fw_flg & IP_FW_F_COMMAND) == IP_FW_F_QUEUE )
+	for (fs=all_flow_sets; fs && fs->fs_nr != pipe_nr; fs=fs->next)
+	    ;
+    else {
+	struct dn_pipe *p1;
+	for (p1 = all_pipes; p1 && p1->pipe_nr != pipe_nr; p1 = p1->next)
+	    ;
+	if (p1 != NULL)
+	    fs = &(p1->fs) ;
+    }
+    if (fs != NULL)
+	rule->rule->pipe_ptr = fs ; /* record for the future */
+    return fs ;
+}
+
 /*
- * dummynet hook for packets.
+ * dummynet hook for packets. Below 'pipe' is a pipe or a queue
+ * depending on whether WF2Q or fixed bw is used.
  */
 int
-dummynet_io(int pipe_nr, int dir,
+dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
 	struct mbuf *m, struct ifnet *ifp, struct route *ro,
 	struct sockaddr_in *dst,
 	struct ip_fw_chain *rule, int flags)
 {
     struct dn_pkt *pkt;
-    struct dn_pipe *p;
-    int len = m->m_pkthdr.len ;
+    struct dn_flow_set *fs;
+    struct dn_pipe *pipe ;
+    u_int64_t len = m->m_pkthdr.len ;
     struct dn_flow_queue *q = NULL ;
     int s ;
 
-    s = splimp();
-    /* XXX check the spl protection. It might be unnecessary since we
-     * run this at splnet() already.
-     */
-
-    DEB(printf("-- last_pkt dst 0x%08x/0x%04x src 0x%08x/0x%04x\n",
-	last_pkt.dst_ip, last_pkt.dst_port,
-	last_pkt.src_ip, last_pkt.src_port);)
+    s = splimp(); /* XXX might be unnecessary, we are already at splnet() */
 
     pipe_nr &= 0xffff ;
-    /*
-     * locate pipe. First time is expensive, next have direct access.
-     */
-    if ( (p = rule->rule->pipe_ptr) == NULL ) {
-	for (p = all_pipes; p && p->pipe_nr != pipe_nr; p = p->next)
+    if ( (fs = rule->rule->pipe_ptr) == NULL ) {
+	fs = locate_flowset(pipe_nr, rule);
+	if (fs == NULL)
+	    goto dropit ;	/* this queue/pipe does not exist! */
+    }
+    pipe = fs->pipe ;
+    if (pipe == NULL) { /* must be a queue, try find a matching pipe */
+	for (pipe = all_pipes; pipe && pipe->pipe_nr != fs->parent_nr;
+		 pipe = pipe->next)
 	    ;
-	if (p == NULL)
-	    goto dropit ;	/* this pipe does not exist! */
-	rule->rule->pipe_ptr = p ; /* record pipe ptr for the future	*/
+	if (pipe != NULL)
+	    fs->pipe = pipe ;
+	else {
+	    printf("No pipe %d for queue %d, drop pkt\n",
+		fs->parent_nr, fs->fs_nr);
+	    goto dropit ;
     }
-    q = find_queue(p);
-    /*
-     * update statistics, then do various check on reasons to drop pkt
-     */
+    }
+    q = find_queue(fs);
     if ( q == NULL )
 	goto dropit ;		/* cannot allocate queue		*/
+    /*
+     * update statistics, then check reasons to drop pkt
+     */
     q->tot_bytes += len ;
     q->tot_pkts++ ;
-    if ( p->plr && random() < p->plr )
+    if ( fs->plr && random() < fs->plr )
 	goto dropit ;		/* random pkt drop			*/
-    if ( p->queue_size && q->len >= p->queue_size)
-	goto dropit ;		/* queue count overflow			*/
-    if ( p->queue_size_bytes && len + q->len_bytes > p->queue_size_bytes)
+    if ( fs->flags_fs & DN_QSIZE_IS_BYTES) {
+    	if (q->len_bytes > fs->qsize)
 	goto dropit ;		/* queue size overflow			*/
-    /*
-     * can implement RED drops here if needed.
-     */
+    } else {
+	if (q->len >= fs->qsize)
+	    goto dropit ;	/* queue count overflow			*/
+    }
+    if ( fs->flags_fs & DN_IS_RED && red_drops(fs, q, len) )
+	goto dropit ;
 
     pkt = (struct dn_pkt *)malloc(sizeof (*pkt), M_IPFW, M_NOWAIT) ;
     if ( pkt == NULL )
@@ -602,33 +1027,70 @@ dummynet_io(int pipe_nr, int dir,
     if (dir == DN_TO_IP_OUT) {
 	/*
 	 * We need to copy *ro because for ICMP pkts (and maybe others)
-	 * the caller passed a pointer into the stack; and, dst might
-	 * also be a pointer into *ro so it needs to be updated.
+	 * the caller passed a pointer into the stack; dst might also be
+	 * a pointer into *ro so it needs to be updated.
 	 */
 	pkt->ro = *ro;
 	if (ro->ro_rt)
-	    ro->ro_rt->rt_refcnt++ ; /* XXX */
+	    ro->ro_rt->rt_refcnt++ ;
 	if (dst == (struct sockaddr_in *)&ro->ro_dst) /* dst points into ro */
 	    dst = (struct sockaddr_in *)&(pkt->ro.ro_dst) ;
 
 	pkt->dn_dst = dst;
 	pkt->flags = flags ;
     }
-    if (q->r.head == NULL)
-	q->r.head = pkt;
+    if (q->head == NULL)
+	q->head = pkt;
     else
-	DN_NEXT(q->r.tail) = pkt;
-    q->r.tail = pkt;
+	DN_NEXT(q->tail) = pkt;
+    q->tail = pkt;
     q->len++;
     q->len_bytes += len ;
 
+    if ( q->head != pkt )	/* flow was not idle, we are done */
+	goto done;
     /*
-     * If queue was empty (this is first pkt) then call ready_event()
-     * now to make the pkt go out at the right time. Otherwise we are done,
-     * as there must be a ready event already scheduled.
+     * The flow was previously idle, so we need to schedule it.
      */
-    if (q->r.head == pkt) /* r_queue was empty */
+    if ( (rule->rule->fw_flg & IP_FW_F_COMMAND) == IP_FW_F_PIPE ) {
+	/* fixed-rate queue: just insert into the ready_heap. */
+	dn_key t = 0 ;
+	if (pipe->bandwidth) 
+	    t = SET_TICKS(pkt, q, pipe);
+	q->sched_time = curr_time ;
+	if (t == 0)	/* must process it now */
 	ready_event( q );
+	else
+	    heap_insert(&ready_heap, curr_time + t , q );
+    } else {
+	/*
+	 * WF2Q: compute start time and put into backlogged list. Then
+	 * look at eligibility -- if not eligibile, it means that
+	 * there is some other flow already scheduled for the same pipe.
+	 * If eligible, AND the pipe is idle, then call ready_event_wfq().
+	 */
+	q->S = MAX64(q->F, pipe->V ) ;
+	q->F = q->S + ( len<<MY_M )/(u_int64_t) fs->weight;
+
+	heap_insert(&(pipe->backlogged_heap), q->S, q);
+	pipe->sum += fs->weight ;	/* new session backlogged */
+	fs->backlogged++ ;
+	if (DN_KEY_GT(q->S, pipe->V) ) { /* not eligible */
+	    DDB(printf("== not eligible, size %d\n", (int)len);)
+	    heap_insert(&(pipe->not_eligible_heap), q->S, q);
+	} else {
+	    heap_insert(&(pipe->scheduler_heap), q->F, q);
+	    if (pipe->numbytes >= 0) { /* pipe is idle */
+		if (pipe->scheduler_heap.elements != 1)
+		    printf("*** OUCH! pipe should have been idle!\n");
+		DEB(printf("Waking up pipe %d at %d\n",
+			pipe->pipe_nr, (int)(q->F >> MY_M)); )
+		pipe->sched_time = curr_time ;
+		ready_event_wfq(pipe);
+	    }
+	}
+    }
+done:
     splx(s);
     return 0;
 
@@ -641,7 +1103,7 @@ dropit:
 }
 
 /*
- * below, the rt_unref is only needed when (pkt->dn_dir == DN_TO_IP_OUT)
+ * Below, the rt_unref is only needed when (pkt->dn_dir == DN_TO_IP_OUT)
  * Doing this would probably save us the initial bzero of dn_pkt
  */
 #define DN_FREE_PKT(pkt)	{		\
@@ -650,25 +1112,60 @@ dropit:
 	m_freem(n->dn_m);			\
 	pkt = DN_NEXT(n) ;			\
 	free(n, M_IPFW) ;	}
+
 /*
- * dispose all packets queued on a pipe
+ * Dispose all packets and flow_queues on a flow_set.
+ * If all=1, also remove red lookup table and other storage,
+ * including the descriptor itself.
+ * For the one in dn_pipe MUST also cleanup ready_heap...
  */
 static void
-purge_pipe(struct dn_pipe *pipe)
+purge_flow_set(struct dn_flow_set *fs, int all)
 {
     struct dn_pkt *pkt ;
     struct dn_flow_queue *q, *qn ;
     int i ;
 
-    for (i = 0 ; i < pipe->rq_size ; i++ )
-	for (q = pipe->rq[i] ; q ; q = qn ) {
-	    for (pkt = q->r.head ; pkt ; )
+    for (i = 0 ; i <= fs->rq_size ; i++ ) {
+	for (q = fs->rq[i] ; q ; q = qn ) {
+	    for (pkt = q->head ; pkt ; )
 		DN_FREE_PKT(pkt) ;
 	    qn = q->next ;
 	    free(q, M_IPFW);
 	}
-    for (pkt = pipe->p.head ; pkt ; )
+	fs->rq[i] = NULL ;
+    }
+    fs->rq_elements = 0 ;
+    if (all) {
+	/* RED - free lookup table */
+	if (fs->w_q_lookup)
+	    free(fs->w_q_lookup, M_IPFW);
+	if (fs->rq)
+	    free(fs->rq, M_IPFW);
+	/* if this fs is not part of a pipe, free it */
+	if (fs->pipe && fs != &(fs->pipe->fs) )
+	    free(fs, M_IPFW);
+    }
+}
+
+/*
+ * Dispose all packets queued on a pipe (not a flow_set).
+ * Also free all resources associated to a pipe, which is about
+ * to be deleted.
+ */
+static void
+purge_pipe(struct dn_pipe *pipe)
+{
+    struct dn_pkt *pkt ;
+
+    purge_flow_set( &(pipe->fs), 1 );
+
+    for (pkt = pipe->head ; pkt ; )
 	DN_FREE_PKT(pkt) ;
+
+    heap_free( &(pipe->scheduler_heap) );
+    heap_free( &(pipe->not_eligible_heap) );
+    heap_free( &(pipe->backlogged_heap) );
 }
 
 /*
@@ -680,6 +1177,7 @@ dummynet_flush()
 {
     struct dn_pipe *curr_p, *p ;
     struct ip_fw_chain *chain ;
+    struct dn_flow_set *fs, *curr_fs;
     int s ;
 
     s = splnet() ;
@@ -690,27 +1188,45 @@ dummynet_flush()
     /* prevent future matches... */
     p = all_pipes ;
     all_pipes = NULL ; 
+    fs = all_flow_sets ;
+    all_flow_sets = NULL ;
     /* and free heaps so we don't have unwanted events */
-    if (ready_heap.size >0 )
-	free(ready_heap.p, M_IPFW);
-    ready_heap.elements = ready_heap.size = 0 ;
-    if (extract_heap.size >0 )
-	free(extract_heap.p, M_IPFW);
-    extract_heap.elements = extract_heap.size = 0 ;
+    heap_free(&ready_heap);
+    heap_free(&wfq_ready_heap);
+    heap_free(&extract_heap);
     splx(s) ;
     /*
      * Now purge all queued pkts and delete all pipes
      */
+    /* scan and purge all flow_sets. */
+    for ( ; fs ; ) {
+	curr_fs = fs ;
+	fs = fs->next ;
+	purge_flow_set(curr_fs, 1);
+    }
     for ( ; p ; ) {
 	purge_pipe(p);
 	curr_p = p ;
 	p = p->next ;	
-	free(curr_p->rq, M_IPFW);
 	free(curr_p, M_IPFW);
     }
 }
 
+
 extern struct ip_fw_chain *ip_fw_default_rule ;
+static void
+dn_rule_delete_fs(struct dn_flow_set *fs, void *r)
+{
+    int i ;
+    struct dn_flow_queue *q ;
+    struct dn_pkt *pkt ;
+
+    for (i = 0 ; i <= fs->rq_size ; i++) /* last one is ovflow */
+	for (q = fs->rq[i] ; q ; q = q->next )
+	    for (pkt = q->head ; pkt ; pkt = DN_NEXT(pkt) )
+		if (pkt->hdr.mh_data == r)
+		    pkt->hdr.mh_data = (void *)ip_fw_default_rule ;
+}
 /*
  * when a firewall rule is deleted, scan all queues and remove the flow-id
  * from packets matching this rule.
@@ -719,148 +1235,180 @@ void
 dn_rule_delete(void *r)
 {
     struct dn_pipe *p ;
-    struct dn_flow_queue *q ;
     struct dn_pkt *pkt ;
-    int i ;
+    struct dn_flow_set *fs ;
 
+    /*
+     * If the rule references a queue (dn_flow_set), then scan
+     * the flow set, otherwise scan pipes. Should do either, but doing
+     * both does not harm.
+     */
+    for ( fs = all_flow_sets ; fs ; fs = fs->next )
+	dn_rule_delete_fs(fs, r);
     for ( p = all_pipes ; p ; p = p->next ) {
-	for (i = 0 ; i < p->rq_size ; i++)
-	    for (q = p->rq[i] ; q ; q = q->next )
-		for (pkt = q->r.head ; pkt ; pkt = DN_NEXT(pkt) )
-		    if (pkt->hdr.mh_data == r)
-			pkt->hdr.mh_data = (void *)ip_fw_default_rule ;
-	for (pkt = p->p.head ; pkt ; pkt = DN_NEXT(pkt) )
+	fs = &(p->fs) ;
+	dn_rule_delete_fs(fs, r);
+	for (pkt = p->head ; pkt ; pkt = DN_NEXT(pkt) )
 	    if (pkt->hdr.mh_data == r)
 		pkt->hdr.mh_data = (void *)ip_fw_default_rule ;
     }
 }
 
 /*
- * handler for the various dummynet socket options
- * (get, flush, config, del)
+ * setup RED parameters
  */
 static int
-ip_dn_ctl(struct sockopt *sopt)
+config_red(struct dn_flow_set *p, struct dn_flow_set * x) 
 {
-    int error = 0 ;
-    size_t size ;
-    char *buf, *bp ; /* bp is the "copy-pointer" */
-    struct dn_pipe *p, tmp_pipe ;
+    int i;
+
+    x->w_q = p->w_q;
+    x->min_th = SCALE(p->min_th);
+    x->max_th = SCALE(p->max_th);
+    x->max_p = p->max_p;
+
+    x->c_1 = p->max_p / (p->max_th - p->min_th);
+    x->c_2 = SCALE_MUL(x->c_1, SCALE(p->min_th));
+    if (x->flags_fs & DN_IS_GENTLE_RED) {
+	x->c_3 = (SCALE(1) - p->max_p) / p->max_th;
+	x->c_4 = (SCALE(1) - 2 * p->max_p);
+    }
 
-    struct dn_pipe *x, *a, *b ;
+    /* if the lookup table already exist, free and create it again */
+    if (x->w_q_lookup)
+	free(x->w_q_lookup, M_IPFW);
+    if (red_lookup_depth == 0) {
+	printf("\nnet.inet.ip.dummynet.red_lookup_depth must be > 0");
+	free(x, M_IPFW);
+	return EINVAL;
+    }
+    x->lookup_depth = red_lookup_depth;
+    x->w_q_lookup = (u_int *) malloc(x->lookup_depth * sizeof(int),
+	    M_IPFW, M_DONTWAIT);
+    if (x->w_q_lookup == NULL) {
+	printf("sorry, cannot allocate red lookup table\n");
+	free(x, M_IPFW);
+	return ENOSPC;
+    }
 
-    /* Disallow sets in really-really secure mode. */
-    if (sopt->sopt_dir == SOPT_SET && securelevel >= 3)
-	return (EPERM);
+    /* fill the lookup table with (1 - w_q)^x */
+    x->lookup_step = p->lookup_step ;
+    x->lookup_weight = p->lookup_weight ;
+    x->w_q_lookup[0] = SCALE(1) - x->w_q;
+    for (i = 1; i < x->lookup_depth; i++)
+	x->w_q_lookup[i] = SCALE_MUL(x->w_q_lookup[i - 1], x->lookup_weight);
+    if (red_avg_pkt_size < 1)
+	red_avg_pkt_size = 512 ;
+    x->avg_pkt_size = red_avg_pkt_size ;
+    if (red_max_pkt_size < 1)
+	red_max_pkt_size = 1500 ;
+    x->max_pkt_size = red_max_pkt_size ;
+    return 0 ;
+}
 
-    switch (sopt->sopt_name) {
-    default :
-	panic("ip_dn_ctl -- unknown option");
+static int
+alloc_hash(struct dn_flow_set *x, struct dn_flow_set *pfs)
+{
+    if (x->flags_fs & DN_HAVE_FLOW_MASK) {     /* allocate some slots */
+	int l = pfs->rq_size;
+
+	if (l == 0)
+	    l = dn_hash_size;
+	if (l < 4)
+	    l = 4;
+	else if (l > 1024)
+	    l = 1024;
+	x->rq_size = l;
+    } else                  /* one is enough for null mask */
+	x->rq_size = 1;
+    x->rq = malloc((1 + x->rq_size) * sizeof(struct dn_flow_queue *),
+	    M_IPFW, M_DONTWAIT);
+    if (x->rq == NULL) {
+	printf("sorry, cannot allocate queue\n");
+	return ENOSPC;
+    }
+    bzero(x->rq, (1+x->rq_size) * sizeof(struct dn_flow_queue *));
+    x->rq_elements = 0;
+    return 0 ;
+}
 
-    case IP_DUMMYNET_GET :
-	for (p = all_pipes, size = 0 ; p ; p = p->next )
-	    size += sizeof( *p ) +
-		p->rq_elements * sizeof(struct dn_flow_queue);
-	buf = malloc(size, M_TEMP, M_WAITOK);
-	if (buf == 0) {
-	    error = ENOBUFS ;
-	    break ;
+static void
+set_fs_parms(struct dn_flow_set *x, struct dn_flow_set *src)
+{
+    x->flags_fs = src->flags_fs;
+    x->qsize = src->qsize;
+    x->plr = src->plr;
+    x->flow_mask = src->flow_mask;
+    if (x->flags_fs & DN_QSIZE_IS_BYTES) {
+	if (x->qsize > 1024*1024)
+	    x->qsize = 1024*1024 ;
+    } else {
+	if (x->qsize == 0)
+	    x->qsize = 50 ;
+	if (x->qsize > 100)
+	    x->qsize = 50 ;
+    }
+    /* configuring RED */
+    if ( x->flags_fs & DN_IS_RED )
+	config_red(src, x) ;    /* XXX should check errors */
 	}
-	for (p = all_pipes, bp = buf ; p ; p = p->next ) {
-	    int i ;
-	    struct dn_pipe *pipe_bp = (struct dn_pipe *)bp ;
-	    struct dn_flow_queue *q;
 
 	    /*
-	     * copy the pipe descriptor into *bp, convert delay back to ms,
-	     * then copy the queue descriptor(s) one at a time.
+ * setup pipe or queue parameters.
 	     */
-	    bcopy(p, bp, sizeof( *p ) );
-	    pipe_bp->delay = (pipe_bp->delay * 1000) / hz ;
-	    bp += sizeof( *p ) ;
-	    for (i = 0 ; i < p->rq_size ; i++)
-		for (q = p->rq[i] ; q ; q = q->next, bp += sizeof(*q) )
-		    bcopy(q, bp, sizeof( *q ) );
-	}
-	error = sooptcopyout(sopt, buf, size);
-	FREE(buf, M_TEMP);
-	break ;
 
-    case IP_DUMMYNET_FLUSH :
-	dummynet_flush() ;
-	break ;
+static int 
+config_pipe(struct dn_pipe *p)
+{
+    int s ;
+    struct dn_flow_set *pfs = &(p->fs);
 
-    case IP_DUMMYNET_CONFIGURE :
-	p = &tmp_pipe ;
-	error = sooptcopyin(sopt, p, sizeof *p, sizeof *p);
-	if (error)
-	    break ;
 	/*
 	 * The config program passes parameters as follows:
-	 * bandwidth = bits/second (0 means no limits);
-	 * delay = millisec.,   must be translated into ticks.
-	 * queue_size = slots (0 means no limit)
-	 * queue_size_bytes = bytes (0 means no limit)
-	 *	  only one can be set, must be bound-checked
+     * bw = bits/second (0 means no limits),
+     * delay = ms, must be translated into ticks.
+     * qsize = slots/bytes
 	 */
 	p->delay = ( p->delay * hz ) / 1000 ;
-	if (p->queue_size == 0 && p->queue_size_bytes == 0)
-	    p->queue_size = 50 ;
-	if (p->queue_size != 0 )	/* buffers are prevailing */
-	    p->queue_size_bytes = 0 ;
-	if (p->queue_size > 100)
-	    p->queue_size = 50 ;
-	if (p->queue_size_bytes > 1024*1024)
-	    p->queue_size_bytes = 1024*1024 ;
+    /* We need either a pipe number or a flow_set number */
+    if (p->pipe_nr == 0 && pfs->fs_nr == 0)
+	return EINVAL ;
+    if (p->pipe_nr != 0 && pfs->fs_nr != 0)
+	return EINVAL ;
+    if (p->pipe_nr != 0) { /* this is a pipe */
+	struct dn_pipe *x, *a, *b;
+	/* locate pipe */
 	for (a = NULL , b = all_pipes ; b && b->pipe_nr < p->pipe_nr ;
 		 a = b , b = b->next) ;
-	if (b && b->pipe_nr == p->pipe_nr) {
-	    b->bandwidth = p->bandwidth ;
-	    b->delay = p->delay ;
-	    b->queue_size = p->queue_size ;
-	    b->queue_size_bytes = p->queue_size_bytes ;
-	    b->plr = p->plr ;
-	    b->flow_mask = p->flow_mask ;
-	    b->flags = p->flags ;
-	} else { /* completely new pipe */
-	    int s ;
+
+	if (b == NULL || b->pipe_nr != p->pipe_nr) { /* new pipe */
 	    x = malloc(sizeof(struct dn_pipe), M_IPFW, M_DONTWAIT) ;
 	    if (x == NULL) {
 		printf("ip_dummynet.c: no memory for new pipe\n");
-		error = ENOSPC ;
-		break ;
+		return ENOSPC;
 	    }
-	    bzero(x, sizeof(*x) );
+	    bzero(x, sizeof(struct dn_pipe));
+	    x->pipe_nr = p->pipe_nr;
+	    x->fs.pipe = x ;
+	    x->backlogged_heap.size = x->backlogged_heap.elements = 0 ;
+	    x->backlogged_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos);
+	} else
+	    x = b;
+
 	    x->bandwidth = p->bandwidth ;
+	x->numbytes = 0; /* just in case... */
+	bcopy(p->if_name, x->if_name, sizeof(p->if_name) );
+	x->ifp = NULL ; /* reset interface ptr */
 	    x->delay = p->delay ;
-	    x->pipe_nr = p->pipe_nr ;
-	    x->queue_size = p->queue_size ;
-	    x->queue_size_bytes = p->queue_size_bytes ;
-	    x->plr = p->plr ;
-	    x->flow_mask = p->flow_mask ;
-	    x->flags = p->flags ;
-	    if (x->flags & DN_HAVE_FLOW_MASK) {/* allocate some slots */
-		int l = p->rq_size ;
-		if (l == 0)
-		    l = dn_hash_size ;
-		if (l < 4)
-		    l = 4 ;
-		else if (l > 1024)
-		    l = 1024 ;
-		x->rq_size = l ;
-	    } else /* one is enough for null mask */
-		x->rq_size = 1 ;
-	    x->rq = malloc(x->rq_size * sizeof(struct dn_flow_queue *),
-		    M_IPFW, M_DONTWAIT) ;
-	    if (x->rq == NULL ) {
-		printf("sorry, cannot allocate queue\n");
+	set_fs_parms(&(x->fs), pfs);
+
+
+	if ( x->fs.rq == NULL ) { /* a new pipe */
+	    s = alloc_hash(&(x->fs), pfs) ;
+	    if (s) {
 		free(x, M_IPFW);
-		error = ENOSPC ;
-		break ;
+		return s ;
 	    }
-	    bzero(x->rq, x->rq_size * sizeof(struct dn_flow_queue *) );
-	    x->rq_elements = 0 ;
-
 	    s = splnet() ;
 	    x->next = b ;
 	    if (a == NULL)
@@ -869,68 +1417,332 @@ ip_dn_ctl(struct sockopt *sopt)
 		a->next = x ;
 	    splx(s);
 	}
-	break ;
+    } else { /* config queue */
+	struct dn_flow_set *x, *a, *b ;
 
-    case IP_DUMMYNET_DEL :
-	p = &tmp_pipe ;
-	error = sooptcopyin(sopt, p, sizeof *p, sizeof *p);
-	if (error)
-	    break ;
-
-	for (a = NULL , b = all_pipes ; b && b->pipe_nr < p->pipe_nr ;
+	/* locate flow_set */
+	for (a=NULL, b=all_flow_sets ; b && b->fs_nr < pfs->fs_nr ;
 		 a = b , b = b->next) ;
-	if (b && b->pipe_nr == p->pipe_nr) {	/* found pipe */
-	    int s ;
-	    struct ip_fw_chain *chain ;
 
-	    s = splnet() ;
-	    chain = ip_fw_chain.lh_first;
+	if (b == NULL || b->fs_nr != pfs->fs_nr) { /* new  */
+	    if (pfs->parent_nr == 0)	/* need link to a pipe */
+		return EINVAL ;
+	    x = malloc(sizeof(struct dn_flow_set), M_IPFW, M_DONTWAIT);
+	    if (x == NULL) {
+		printf("ip_dummynet.c: no memory for new flow_set\n");
+		return ENOSPC;
+	    }
+	    bzero(x, sizeof(struct dn_flow_set));
+	    x->fs_nr = pfs->fs_nr;
+	    x->parent_nr = pfs->parent_nr;
+	    x->weight = pfs->weight ;
+	    if (x->weight == 0)
+		x->weight = 1 ;
+	    else if (x->weight > 100)
+		x->weight = 100 ;
+	} else {
+	    /* Change parent pipe not allowed; must delete and recreate */
+	    if (pfs->parent_nr != 0 && b->parent_nr != pfs->parent_nr)
+		return EINVAL ;
+	    x = b;
+	}
+	set_fs_parms(x, pfs);
 
+	if ( x->rq == NULL ) { /* a new flow_set */
+	    s = alloc_hash(x, pfs) ;
+	    if (s) {
+		free(x, M_IPFW);
+		return s ;
+	    }
+	    s = splnet() ;
+	    x->next = b;
 	    if (a == NULL)
-		all_pipes = b->next ;
+		all_flow_sets = x;
 	    else
-		a->next = b->next ;
+		a->next = x;
+	    splx(s);
+	}
+    }
+    return 0 ;
+}
+
 	    /*
-	     * remove references to this pipe from the ip_fw rules.
+ * Helper function to remove from a heap queues which are linked to
+ * a flow_set about to be deleted.
 	     */
-	    for (; chain; chain = chain->chain.le_next)
-		if (chain->rule->pipe_ptr == b)
-		    chain->rule->pipe_ptr = NULL ;
-	    /* remove all references to b from heaps */
-	    if (ready_heap.elements > 0) {
-		struct dn_heap *h = &ready_heap ;
+static void
+fs_remove_from_heap(struct dn_heap *h, struct dn_flow_set *fs)
+{
 		int i = 0, found = 0 ;
-		while ( i < h->elements ) {
-		    if (((struct dn_flow_queue *)(h->p[i].object))->p == b) {
-			/* found one */
+    for (; i < h->elements ;)
+	if ( ((struct dn_flow_queue *)h->p[i].object)->fs == fs) {
 			h->elements-- ;
 			h->p[i] = h->p[h->elements] ;
 			found++ ;
 		    } else
 			i++ ;
-		}
 		if (found)
 		    heapify(h);
 	    }
-	    if (extract_heap.elements > 0) {
-		struct dn_heap *h = &extract_heap ;
-		int i = 0, found = 0 ;
-		while ( i < h->elements ) {
-		    if (h->p[i].object == b) { /* found one */
+
+/*
+ * helper function to remove a pipe from a heap (can be there at most once)
+ */
+static void
+pipe_remove_from_heap(struct dn_heap *h, struct dn_pipe *p)
+{
+    if (h->elements > 0) {
+	int i = 0 ;
+	for (i=0; i < h->elements ; i++ ) {
+	    if (h->p[i].object == p) { /* found it */
 			h->elements-- ;
 			h->p[i] = h->p[h->elements] ;
-			found++ ;
-		    } else
-			i++ ;
-		}
-		if (found)
 		    heapify(h);
+		break ;
+	    }
+	}
+    }
 	    }
+
+/*
+ * drain all queues. Called in case of severe mbuf shortage.
+ */
+void
+dummynet_drain()
+{
+    struct dn_flow_set *fs;
+    struct dn_pipe *p;
+    struct dn_pkt *pkt;
+
+    heap_free(&ready_heap);
+    heap_free(&wfq_ready_heap);
+    heap_free(&extract_heap);
+    /* remove all references to this pipe from flow_sets */
+    for (fs = all_flow_sets; fs; fs= fs->next )
+	purge_flow_set(fs, 0);
+
+    for (p = all_pipes; p; p= p->next ) {
+	purge_flow_set(&(p->fs), 0);
+	for (pkt = p->head ; pkt ; )
+	    DN_FREE_PKT(pkt) ;
+	p->head = p->tail = NULL ;
+    }
+}
+
+/*
+ * Fully delete a pipe or a queue, cleaning up associated info.
+ */
+static int 
+delete_pipe(struct dn_pipe *p)
+{
+    int s ;
+    struct ip_fw_chain *chain ;
+
+    if (p->pipe_nr == 0 && p->fs.fs_nr == 0)
+	return EINVAL ;
+    if (p->pipe_nr != 0 && p->fs.fs_nr != 0)
+	return EINVAL ;
+    if (p->pipe_nr != 0) { /* this is an old-style pipe */
+	struct dn_pipe *a, *b;
+	struct dn_flow_set *fs;
+
+	/* locate pipe */
+	for (a = NULL , b = all_pipes ; b && b->pipe_nr < p->pipe_nr ;
+		 a = b , b = b->next) ;
+	if (b && b->pipe_nr != p->pipe_nr)
+	    return EINVAL ; /* not found */
+
+	s = splnet() ;
+
+	/* unlink from list of pipes */
+	if (a == NULL)
+	    all_pipes = b->next ;
+	else
+	    a->next = b->next ;
+	/* remove references to this pipe from the ip_fw rules. */
+	for (chain = ip_fw_chain.lh_first ; chain; chain = chain->chain.le_next)
+	    if (chain->rule->pipe_ptr == &(b->fs))
+		chain->rule->pipe_ptr = NULL ;
+
+	/* remove all references to this pipe from flow_sets */
+	for (fs = all_flow_sets; fs; fs= fs->next )
+	    if (fs->pipe == b) {
+		printf("++ ref to pipe %d from fs %d\n",
+			p->pipe_nr, fs->fs_nr);
+		fs->pipe = NULL ;
+		purge_flow_set(fs, 0);
+	    }
+	fs_remove_from_heap(&ready_heap, &(b->fs));
+	purge_pipe(b);	/* remove all data associated to this pipe */
+	/* remove reference to here from extract_heap and wfq_ready_heap */
+	pipe_remove_from_heap(&extract_heap, b);
+	pipe_remove_from_heap(&wfq_ready_heap, b);
 	    splx(s);
-	    purge_pipe(b);	/* remove pkts from here */
-	    free(b->rq, M_IPFW);
 	    free(b, M_IPFW);
+    } else { /* this is a dummynet queue (dn_flow_set) */
+	struct dn_flow_set *a, *b;
+
+	/* locate set */
+	for (a = NULL, b = all_flow_sets ; b && b->fs_nr < p->fs.fs_nr ;
+		 a = b , b = b->next) ;
+	if (b && b->fs_nr != p->fs.fs_nr)
+	    return EINVAL ; /* not found */
+
+	s = splnet() ;
+	if (a == NULL)
+	    all_flow_sets = b->next ;
+	else
+	    a->next = b->next ;
+	/* remove references to this flow_set from the ip_fw rules. */
+	for (chain = ip_fw_chain.lh_first; chain; chain = chain->chain.le_next)
+	    if (chain->rule->pipe_ptr == b)
+		chain->rule->pipe_ptr = NULL ;
+
+	if (b->pipe != NULL) {
+	    /* Update total weight on parent pipe and cleanup parent heaps */
+	    b->pipe->sum -= b->weight * b->backlogged ;
+	    fs_remove_from_heap(&(b->pipe->backlogged_heap), b);
+	    fs_remove_from_heap(&(b->pipe->not_eligible_heap), b);
+	    fs_remove_from_heap(&(b->pipe->scheduler_heap), b);
+	}
+	purge_flow_set(b, 1);
+	splx(s);
+    }
+    return 0 ;
+	}
+
+/*
+ * helper function used to copy data from kernel in DUMMYNET_GET
+ */
+static char *
+dn_copy_set(struct dn_flow_set *set, char *bp)
+{
+    int i, copied = 0 ;
+    struct dn_flow_queue *q, *qp = (struct dn_flow_queue *)bp;
+
+    for (i = 0 ; i <= set->rq_size ; i++)
+	for (q = set->rq[i] ; q ; q = q->next, qp++ ) {
+	    if (q->hash_slot != i)
+		printf("++ at %d: wrong slot (have %d, "
+		    "should be %d)\n", copied, q->hash_slot, i);
+	    if (q->fs != set)
+		printf("++ at %d: wrong fs ptr (have %p, should be %p)\n",
+			i, q->fs, set);
+	    copied++ ;
+	    bcopy(q, qp, sizeof( *q ) );
+	    /* cleanup pointers */
+	    qp->next = NULL ;
+	    qp->head = qp->tail = NULL ;
+	    qp->fs = NULL ;
 	}
+    if (copied != set->rq_elements)
+	printf("++ wrong count, have %d should be %d\n",
+	    copied, set->rq_elements);
+    return (char *)qp ;
+}
+
+static int
+dummynet_get(struct sockopt *sopt)
+{
+    char *buf, *bp ; /* bp is the "copy-pointer" */
+    size_t size ;
+    struct dn_flow_set *set ;
+    struct dn_pipe *p ;
+    int s, error=0 ;
+
+    s = splnet() ; /* to avoid thing change while we work! */
+    /*
+     * compute size of data structures: list of pipes and flow_sets.
+     */
+    for (p = all_pipes, size = 0 ; p ; p = p->next )
+	size += sizeof( *p ) +
+	    p->fs.rq_elements * sizeof(struct dn_flow_queue);
+    for (set = all_flow_sets ; set ; set = set->next )
+	size += sizeof ( *set ) +
+	    set->rq_elements * sizeof(struct dn_flow_queue);
+    buf = malloc(size, M_TEMP, M_DONTWAIT);
+    if (buf == 0) {
+	splx(s);
+	return ENOBUFS ;
+    }
+    for (p = all_pipes, bp = buf ; p ; p = p->next ) {
+	struct dn_pipe *pipe_bp = (struct dn_pipe *)bp ;
+
+	/*
+	 * copy pipe descriptor into *bp, convert delay back to ms,
+	 * then copy the flow_set descriptor(s) one at a time.
+	 * After each flow_set, copy the queue descriptor it owns.
+	 */
+	bcopy(p, bp, sizeof( *p ) );
+	pipe_bp->delay = (pipe_bp->delay * 1000) / hz ;
+	pipe_bp->fs.flags_fs |= DN_IS_PIPE ;
+	/* cleanup pointers */
+	pipe_bp->next = NULL ;
+	pipe_bp->head = pipe_bp->tail = NULL ;
+	pipe_bp->fs.next = NULL ;
+	pipe_bp->fs.pipe = NULL ;
+	pipe_bp->fs.rq = NULL ;
+
+	bp += sizeof( *p ) ;
+	bp = dn_copy_set( &(p->fs), bp );
+    }
+    for (set = all_flow_sets ; set ; set = set->next ) {
+	struct dn_flow_set *fs_bp = (struct dn_flow_set *)bp ;
+	bcopy(set, bp, sizeof( *set ) );
+	fs_bp->flags_fs |= DN_IS_QUEUE ;
+	fs_bp->next = NULL ;
+	fs_bp->pipe = NULL ;
+	fs_bp->rq = NULL ;
+	bp += sizeof( *set ) ;
+	bp = dn_copy_set( set, bp );
+    }
+    splx(s);
+    error = sooptcopyout(sopt, buf, size);
+    FREE(buf, M_TEMP);
+    return error ;
+}
+
+/*
+ * Handler for the various dummynet socket options (get, flush, config, del)
+ */
+static int
+ip_dn_ctl(struct sockopt *sopt)
+{
+    int error = 0 ;
+    struct dn_pipe *p, tmp_pipe;
+
+    /* Disallow sets in really-really secure mode. */
+    if (sopt->sopt_dir == SOPT_SET && securelevel >= 3)
+	return (EPERM);
+
+    switch (sopt->sopt_name) {
+    default :
+	printf("ip_dn_ctl -- unknown option %d", sopt->sopt_name);
+	return EINVAL ;
+
+    case IP_DUMMYNET_GET :
+	error = dummynet_get(sopt);
+	break ;
+
+    case IP_DUMMYNET_FLUSH :
+	dummynet_flush() ;
+	break ;
+
+    case IP_DUMMYNET_CONFIGURE :
+	p = &tmp_pipe ;
+	error = sooptcopyin(sopt, p, sizeof *p, sizeof *p);
+	if (error)
+	    break ;
+	error = config_pipe(p);
+	break ;
+
+    case IP_DUMMYNET_DEL :	/* remove a pipe or queue */
+	p = &tmp_pipe ;
+	error = sooptcopyin(sopt, p, sizeof *p, sizeof *p);
+	if (error)
+	    break ;
+
+	error = delete_pipe(p);
 	break ;
     }
     return error ;
@@ -939,10 +1751,17 @@ ip_dn_ctl(struct sockopt *sopt)
 static void
 ip_dn_init(void)
 {
-    printf("DUMMYNET initialized (000106)\n");
+    printf("DUMMYNET initialized (000608)\n");
     all_pipes = NULL ;
+    all_flow_sets = NULL ;
     ready_heap.size = ready_heap.elements = 0 ;
+    ready_heap.offset = 0 ;
+
+    wfq_ready_heap.size = wfq_ready_heap.elements = 0 ;
+    wfq_ready_heap.offset = 0 ;
+
     extract_heap.size = extract_heap.elements = 0 ;
+    extract_heap.offset = 0 ;
     ip_dn_ctl_ptr = ip_dn_ctl;
     timeout(dummynet, NULL, 1);
 }