Subject: [aqm] [NS-2 implementation of AQMs]

From: Nicolas KUHN <[email-masked]>
Date: Fri, 21 Feb 2014 12:16:49 +0100

Dear all, 

We have a question regarding the NS-2 implementations of RED, CoDel, PIE and others AQMs. Especially, we believe that the way buffer-overflows are managed is not the same for each AQM scheme.

In "Multimedia-unfriendly TCP Congestion Control and Home Gateway Queue Management" (L. Stewart et al.) details that :
"PS: The queue is packet (slot) based, and the maximum queue length is specified as an integer number of packets:
if (NumPktsInQ ≥ PktQueueLength)
      drop incoming packet"

However: 
1- In droptail.cc: if((q_->length() + 1) >= qlim_) buffer overflow is detected
2- In RED/PIE/CoDel/etc.: if((q_->length() >= qlim_) buffer overflow is detected

In the case of RED/PIE, when there are buffer overflows, the incoming packet may not be dropped. As a result, the incoming packet needs to be stored before the other packet is selected for drop: if((q_->length() >= qlim_) should be avoided - and if((q_->length() + 1) >= qlim_) preferred. 

In the case of CoDel, when there are buffer overflows, the incoming packets are dropped. if((q_->length() >= qlim_) is a good solution.

Anyway, the authors of "Multimedia-unfriendly TCP Congestion Control and Home Gateway Queue Management" (L. Stewart et al.) illustrate the impact of this setting that should be carefully discussed. This point is of interest while comparing the performance of various AQM schemes with NS-2. 

We believe that AQMs that need information about incoming packets before tail-dropping them MUST detect buffer over flow when if((q_->length() + 1) >= qlim_).
Any thoughts? 

Kind regards, 

Amadou B. Bagayoko & Nicolas Kuhn

---

From: "Ilpo Järvinen" <[email-masked]>
Date: Fri, 21 Feb 2014 14:10:31 +0200 (EET)

On Fri, 21 Feb 2014, Nicolas KUHN wrote:

> We have a question regarding the NS-2 implementations of RED, CoDel, PIE 
> and others AQMs. Especially, we believe that the way buffer-overflows 
> are managed is not the same for each AQM scheme.
> 
> In "Multimedia-unfriendly TCP Congestion Control and Home Gateway Queue 
> Management" (L. Stewart et al.) details that :
> "PS: The queue is packet (slot) based, and the maximum queue length is 
> specified as an integer number of packets:
> In the case of RED/PIE, when there are buffer overflows, the incoming 
> packet may not be dropped. As a result, the incoming packet needs to be 
> stored before the other packet is selected for drop: if((q_->length() >= 
> qlim_) should be avoided - and if((q_->length() + 1) >= qlim_) preferred. 
> 
> In the case of CoDel, when there are buffer overflows, the incoming 
> packets are dropped. if((q_->length() >= qlim_) is a good solution.
> 
> Anyway, the authors of "Multimedia-unfriendly TCP Congestion Control and 
> Home Gateway Queue Management" (L. Stewart et al.) illustrate the impact 
> of this setting that should be carefully discussed. This point is of 
> interest while comparing the performance of various AQM schemes with 
> NS-2. 
> 
> We believe that AQMs that need information about incoming packets before 
> tail-dropping them MUST detect buffer over flow when if((q_->length() + 
> 1) >= qlim_).
> Any thoughts? 

While doing some tests with RED using ns2 in the past, I noticed this same 
difference. I patched ns2 RED to get equal behavior (patch attached but it
probably breaks some of the ns2 tests which is why I didn't consider 
trying to upstream it).

-- 
 i.

[PATCH 1/1] Change size to match fifo behavior

---
 queue/red.cc |    4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/queue/red.cc b/queue/red.cc
index 5a9c292..be3e4db 100644
--- a/queue/red.cc
+++ b/queue/red.cc
@@ -686,6 +686,8 @@ void REDQueue::enque(Packet* pkt)
 	int droptype = DTYPE_NONE;
 	int qlen = qib_ ? q_->byteLength() : q_->length();
 	int qlim = qib_ ? (qlim_ * edp_.mean_pktsize) : qlim_;
+	/* To make buffer equal to FIFO behavior */
+	int qlenafter = qlen + (qib_ ? ch->size() : 1);
 
 	curq_ = qlen;	// helps to trace queue during arrival, if enabled
 
@@ -712,7 +714,7 @@ void REDQueue::enque(Packet* pkt)
 		edv_.v_prob = 0.0;
 		edv_.old = 0;		
 	}
-	if (qlen >= qlim) {
+	if (qlenafter >= qlim) {
 		// see if we've exceeded the queue size
 		droptype = DTYPE_FORCED;
 	}
-- 
1.7.9.5

---

From: Naeem Khademi <[email-masked]>
Date: Fri, 21 Feb 2014 15:52:33 +0100

Nicolas,

Good catch although I tend to think that the impact of this would be
more visible on FIFO/DropTail queues; with an AQM presumably set at a
low threshold this impact will probably be less profound (although
depending on too many other factors, such as the load, multiplexing
level, BDP, etc).

Naeem

On Fri, Feb 21, 2014 at 1:10 PM, Ilpo Järvinen
<[email-masked]> wrote:
> _______________________________________________
> aqm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/aqm
>

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 21 Feb 2014 15:02:29 -0500

In message <CAEjQQ5UpuO=[email-masked]>
 
> depending on too many other factors, such as the load, multiplexing

In real routers, at least large routers, the queue limit is measured
in bytes, not packets.  In many interfaces the queue limit is also
setable in msec rather than have the user/admin figure out how many
bytes that should be at a given speed and have the user/admin set
different values on interfaces of different speed.  OTOH a lot of big
router configs are machine generated by the SP.

In small routers and particularly hosts used as routers the queue
limit is often expressed in packets but IMHO that is bad since a queue
full of TCP ACKs is a lot less than a queue with the same number of
full MSS TCP packets.

Curtis