[ns] Some more thoughts about the idle_-flag in the diffserv RED-queueimplementation

[Thilo Wagner <wagner@panasonic.de>]

After I wrote the last message regarding the bug I made the changes I
suggested in the mail and got some quite acceptable results. The changes
can be found at the end of this mail. But I also had a look at the
sourcecode of red.cc and found out, that they don't drop packets if a
queue was idle before, so they can set idle_ to 0 at the beginning of
enqueue without having to care that the packet might get dropped later. 
Here's a part of red.cc: 

void REDQueue::enque(Packet* pkt)
{
  ..
  ..
        if (idle_) {
		// A packet that arrives to an idle queue will never
		//  be dropped.
		double now = Scheduler::instance().clock();
		/* To account for the period when the queue was empty. */
		idle_ = 0;
		m = int(edp_.ptc * (now - idletime_));
	}
  ..
  ..

	if (qavg >= edp_.th_min && qlen > 1) {
          // decide if packet gets dropped
        } else {
          // packet doesn't get dropped
        }
 ..
 ..
}

So packets never get dropped when qlen is 1 so it can't happen that the
idle_ flag is set to 0 but the queue is empty. 

I had a look at [Sally Floyd, Van Jacobsen, "Random Early Detection
Gateways for Congestion Avoidance", IEEE/ACM Transactions on Networking,
August 1993] but I couldn't find that behaviour described in there so
maybe it's an improvement made after the paper was written.

To add this behavoiur to dsredq.cc would be no problem for rio_d and
probably also MRED-mode but I'm not sure what to do with the rio_c
MRED-mode because there I can't make a test on virtual_queuelength > 1
before dropping a packet as I also have to pay attention to the virtual
queues with lower drop prec's. 

Any comments are welcome!

Best regards, 
Thilo 

---- changes to dsred.cc ----

the call to updareREDStateVar at the end of dsREDQueue::enque (added by
xuanc, 12/03/01) 
must be removed again

---- changes to dsredq.h ----

class redQueue {
 public:
  ..
  ..
++  //sets idle_ to 0
++  void redQueue::updateIdleFlag(int prec);
  ..
}

---- changes to dsredq.cc ----

++ // void updateIdleFlag(int)
++ //    Called by enque() to set idle_ to 0 if a packet was enqueued
successfully
++ void redQueue::updateIdleFlag(int prec) {
++   if (mredMode == rio_c) { 
++     for (int i = prec; i < numPrec; i++) qParam_[i].idle_ = 0;
++   } else if (mredMode == rio_d) { 
++    qParam_[prec].idle_ = 0; 
++   } else {
++    qParam_[0].idle_ = 0;
++   } 
++ }

// void enque(Packet *pkt, int prec, int ecn)
//    Enques a packet associated with one of the precedence levels of
the
//    physical queue.
int redQueue::enque(Packet *pkt, int prec, int ecn) {
  int m = 0;
  double now, u;
  double pa,pb;
  
  if (q_->length() > (qlim-1))
    return PKT_DROPPED;
  
  now = Scheduler::instance().clock();
  
  //now determining the avg for that queue
  if (mredMode == dropTail) {
    if (q_->length() >= qParam_[0].edp_.th_min) {
      return PKT_DROPPED;
    } else {
      q_->enque(pkt);
      return PKT_ENQUEUED;		
    }
  } else if (mredMode == rio_c) {
    for (int i = prec; i < numPrec; i++) {	
      m = 0;
      if (qParam_[i].idle_) {
!! 	// qParam_[i].idle_ = 0;
	m = int(qParam_[i].edp_.ptc * (now - qParam_[i].idletime_));
      }
      calcAvg(i, m+1); 
    }
  } else if (mredMode == rio_d) {
    if (qParam_[prec].idle_) {
!!    // qParam_[prec].idle_ = 0;
      m = int(qParam_[prec].edp_.ptc * (now - qParam_[prec].idletime_));
    }	
    calcAvg(prec, m+1);
  } else { //wred
    if (qParam_[0].idle_) {
!!    // qParam_[0].idle_ = 0;
      m = int(qParam_[0].edp_.ptc * (now - qParam_[0].idletime_));
    }	
    calcAvg(0, m+1);
  }
  
  // enqueu packet if we are using ecn
  if (ecn) {
    q_->enque(pkt);	
    
    //virtually, this new packet is queued in one of the multiple
queues,
    //thus increasing the length of that virtual queue
    qParam_[prec].qlen++;
  }
  
  //if the avg is greater than the min threshold,
  //there can be only two cases.....
  if (qParam_[prec].edv_.v_ave > qParam_[prec].edp_.th_min) {
    //either the avg is less than the max threshold
    if (qParam_[prec].edv_.v_ave <= qParam_[prec].edp_.th_max) {
      //in which case determine the probabilty for dropping the packet,
      
      qParam_[prec].edv_.count++;
      qParam_[prec].edv_.v_prob = (1/qParam_[prec].edp_.max_p_inv) *
	(qParam_[prec].edv_.v_ave-qParam_[prec].edp_.th_min) /
	(qParam_[prec].edp_.th_max-qParam_[prec].edp_.th_min);
      
      pb = qParam_[prec].edv_.v_prob;
      pa = pb/(1.0 - qParam_[prec].edv_.count*pb);
      //now determining whether to drop the packet or not
      u = Random::uniform(0.0, 1.0);
      
      //drop it
      if (u <= pa) {	
!!     if (ecn) {
!!      updateIdleFlag(prec); // set idle_ to 0
!!      return PKT_MARKED;
!!     } else 	return PKT_EDROPPED;
      }
    } else { //if avg queue is greater than max. threshold
      qParam_[prec].edv_.count = 0;
!!    if (ecn) {
!!     updateIdleFlag(prec); // set idle_ to 0
!!     return PKT_MARKED;
!!    } else return PKT_DROPPED;
    }
  }
  qParam_[prec].edv_.count = -1;
  
  // if ecn is on, then the packet has already been enqueued
!!  if(ecn) {
!!   updateIdleFlag(prec); // set idle_ to 0
!!   return PKT_ENQUEUED;
!!  }
  
  //if the packet survives the above conditions it
  //is finally queued in the underlying queue
  q_->enque(pkt);
  
  //virtually, this new packet is queued in one of the multiple queues,
  //thus increasing the length of that virtual queue
  qParam_[prec].qlen++;
++  updateIdleFlag(prec); // set idle_ to 0 
 
  return PKT_ENQUEUED;
}