Bug 2819

(In reply to Tom Henderson from comment #0)
> I found two issues with FqCoDel:
> 1) the packet filters will assert if a packet of the specified type is not
> found; however, these filters are meant to be chained and should not assert
> if a packet does not match one of them

This is the currently implemented behavior. Qdiscs can call QueueDisc::Classify, which iterates over all of the filters (by calling the non virtual PacketFilter::Classify) until one that is able to classify the packet is found (i.e., does not return PF_NO_MATCH). PacketFilter::Classify first invokes the virtual PacketFilter::CheckProtocol, that checks whether the filter can classify a packet of the given type (see, e.g., Ipv4PacketFilter::CheckProtocol). If so, it invokes the virtual PacketFilter::DoClassify; otherwise, return PF_NO_MATCH, so that the next filter can be tested.

The assert you found in FqCoDelIpv{4,6}PacketFilter::DoClassify is just to make sure that the packet is not null.

> 2) the queue disc drops any packet not matching a filter.  I think any such
> packets should perhaps go to a different flow queue (e.g. ARP).

This is the behavior of fq-codel in Linux (didn't check again, but I am almost sure). Please keep in mind that, at the moment, only IPv4 and IPv6 send packets to the traffic control in ns-3. ARP packets do not go through the traffic control.

(In reply to Stefano Avallone from comment #1)
> The assert you found in FqCoDelIpv{4,6}PacketFilter::DoClassify is just to
> make sure that the packet is not null.

To be more precise: the assert should be always true, because FqCoDelIpv4PacketFilter::DoClassify is only invoked by PacketFilter::Classify if Ipv4PacketFilter::CheckProtocol returns true, i.e., DynamicCast<Ipv4QueueDiscItem> (item) != 0. So, the assert is just to check that everything goes as expected.

> 
> > 2) the queue disc drops any packet not matching a filter.  I think any such
> > packets should perhaps go to a different flow queue (e.g. ARP).
> 
> This is the behavior of fq-codel in Linux (didn't check again, but I am
> almost sure). Please keep in mind that, at the moment, only IPv4 and IPv6
> send packets to the traffic control in ns-3. ARP packets do not go through
> the traffic control.

Would you consider to route ARP through traffic control?  This is probably the root of the problem that I observed.  

In particular, I am working on a device type that requires flow control (Stop/Wake) to work accurately, and it was disruptive to have ARP packets escape the flow control and arrive during a Stop state.

So I modified ArpL3Protocol to send the packets through the tc subsystem; e.g.

-  cache->GetDevice ()->Send (packet, toMac, PROT_NUMBER);
+  cache->GetInterface ()->GetTrafficControl ()->Send (cache->GetDevice (),
+    Create<ArpQueueDiscItem> (packet, toMac, PROT_NUMBER));

but I later discovered when trying to use fq-codel with this that no packets got through due to lack of ARP support.

> Would you consider to route ARP through traffic control?  This is probably
> the root of the problem that I observed.  

I think we need to route ARP through traffic control. This is what Linux does. Indeed, ARP packets are sent through arp_xmit, which, after invoking the netfilter hooks, calls arp_xmit_finish, which passes the packet to dev_queue_xmit, which is the function that eventually enqueues the packet in the queue disc installed on the outgoing device.

I had a look at fq-codel and discovered that actually packet filtering is not accurately implemented in ns-3. I will have a more detailed look at it in the next days and come up with a patch to review.

I have prepared a few patches to address this bug. You can have a look at https://github.com/stavallo/ns-3-dev-git/commits/tc-next. 

1) traffic-control: Add a Hash method to QueueDiscItem

Computing a hash of the 5-tuple is not really a tc packet filter. Rather, it is a function which computes a value based on the packet type. So, I added a Hash method to the Ipv{4,6}QueueDiscItem class by copying the code in FqCodelIpv{4,6}PacketFilter. Since QueueDiscItem subclasses keep header and payload separate, it is easy to access all the header fields.

2) traffic-control: FqCoDel computes a hash function if no filters are installed

This implements the correct behavior for FQ-CoDel: if no tc packet filter is installed, compute a hash function on the packet (by calling the Hash method of the appropriate QueueDiscItem subclass). Otherwise, call the tc packet filter(s) and drop the packet if no filter is able to classify it.

3) internet: ARP packets pass through the traffic control layer

ARP packets need to pass through tc (as in Linux). So, I added an ArpQueueDiscItem class similar to Ipv{4,6}QueueDiscItem, having a Hash method that computes a value based on the four addresses and the packet type (as in Linux). ArpL3Protocol::SendArp* encapsulate the ARP header and packet in an ArpQueueDiscItem object and pass it to tc.

I checked that all the tests pass.

A couple of things while I am on it (which affect the changes I have to make to the documentation):

- FqCodelIpv{4,6}PacketFilter classes are now useless. Can I just remove them and note in the documentation (and in CHANGES.html) how to configure FqCoDel now?

- the fq-codel test lives in test/ns3-tc because it depends on the internet module. However, I can get rid of such dependency (by using a TestQueueDiscItem and a TestPacketFilter, if needed) and move it to traffic-control/test. What do you think?

(In reply to Stefano Avallone from comment #5)
> I have prepared a few patches to address this bug. You can have a look at
> https://github.com/stavallo/ns-3-dev-git/commits/tc-next. 
> 
> 1) traffic-control: Add a Hash method to QueueDiscItem
> 
> Computing a hash of the 5-tuple is not really a tc packet filter. Rather, it
> is a function which computes a value based on the packet type. So, I added a
> Hash method to the Ipv{4,6}QueueDiscItem class by copying the code in
> FqCodelIpv{4,6}PacketFilter. Since QueueDiscItem subclasses keep header and
> payload separate, it is easy to access all the header fields.
> 
> 2) traffic-control: FqCoDel computes a hash function if no filters are
> installed
> 
> This implements the correct behavior for FQ-CoDel: if no tc packet filter is
> installed, compute a hash function on the packet (by calling the Hash method
> of the appropriate QueueDiscItem subclass). Otherwise, call the tc packet
> filter(s) and drop the packet if no filter is able to classify it.
> 
> 3) internet: ARP packets pass through the traffic control layer
> 
> ARP packets need to pass through tc (as in Linux). So, I added an
> ArpQueueDiscItem class similar to Ipv{4,6}QueueDiscItem, having a Hash
> method that computes a value based on the four addresses and the packet type
> (as in Linux). ArpL3Protocol::SendArp* encapsulate the ARP header and packet
> in an ArpQueueDiscItem object and pass it to tc.
> 
> I checked that all the tests pass.

I only had a couple of minor comments; please review and decide on them, then finalize.

> 
> A couple of things while I am on it (which affect the changes I have to make
> to the documentation):
> 
> - FqCodelIpv{4,6}PacketFilter classes are now useless. Can I just remove
> them and note in the documentation (and in CHANGES.html) how to configure
> FqCoDel now?

We typically use the NS_DEPRECATED feature for a release cycle or two and then remove them.  Is that applicable?  (i.e. will the old usage of these classes still result in correct behavior, or not?).

If correct behavior no longer is supported with the old classes, I would then remove them and outline the change in CHANGES.html.

> 
> - the fq-codel test lives in test/ns3-tc because it depends on the internet
> module. However, I can get rid of such dependency (by using a
> TestQueueDiscItem and a TestPacketFilter, if needed) and move it to
> traffic-control/test. What do you think?

I am neutral on this point; probably lean towards keeping as is because > 99.99 (how many nines?)% of usage will actually involve passing IP traffic through it.

(In reply to Tom Henderson from comment #6)
> I only had a couple of minor comments; please review and decide on them,
> then finalize.

Done. 

> We typically use the NS_DEPRECATED feature for a release cycle or two and
> then remove them.  Is that applicable?  (i.e. will the old usage of these
> classes still result in correct behavior, or not?).
> 
> If correct behavior no longer is supported with the old classes, I would
> then remove them and outline the change in CHANGES.html.

To my knowledge, the NS_DEPRECATED macro is applicable to functions, not to classes. So, I opted for removing the FqCoDel filters and documenting in CHANGES.html that the previous behavior is simply obtained by not configuring any packet filter.
 
> I am neutral on this point; probably lean towards keeping as is because >
> 99.99 (how many nines?)% of usage will actually involve passing IP traffic
> through it.

Agreed.

I just pushed the revised patch with changesets from 13580 to 13583.

Thanks for reviewing the patch!