[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[ns] Re: Some more thoughts about the idle_-flag in the diffserv RED-queueimplementation
Thanks so much for contributing the fix. I have patch them in and you will
see the changes in tomorrow's daily snapshot. Thanks.
Cheers,
-chen
On Tue, 4 Dec 2001, Thilo Wagner wrote:
> 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;
> }
>
--
Xuan Chen
USC/ISI