Bug 772

(In reply to comment #0)
> RFC 3561 says that:
> 
>    Data packets waiting for a route (i.e., waiting for a RREP after a
>    RREQ has been sent) SHOULD be buffered.  The buffering SHOULD be
>    "first-in, first-out" (FIFO).
> 
> This behavior was implemented in our aodv model (see
> aodv::RoutingProtocol::SendPacketFromQueue and Send methods). Unfortunately it
> doesn't work correctly for locally originated packets. The reason is that
> RouteOutput() is spontaneously called from socket implementations _before_
> packet is fully assembled. E.g. UdpSocketImpl calls RouteOutput before UDP
> header is added, TcpSocketImpl and TcpL4Protocol do both (before and after TCP
> header is added).
> 
> I can't imagine simple way to solve this problem preserving current routing API
> and socket implementations. Should I break AODV RFC compatibility and do not
> buffer locally originated packets waiting RREP? Do you see any other solutions?
> Probably making routing API fully asynchronous (like RouteInput()) will help,
> but this will affect a lot of code.

Can you put a default on a loopback interface and make all local outbound packets go through RouteInput instead?

This problem must also be experienced by Linux-based MANET routers that locally originate packets-- how do they solve it and can we do the same?

  Hi, Tom,

> Can you put a default on a loopback interface and make all local outbound
> packets go through RouteInput instead?

  Do you propose to return looback from RouteOutput() when route is unknown and then find it from RouteInput()? Right? 

> This problem must also be experienced by Linux-based MANET routers that locally
> originate packets-- how do they solve it and can we do the same?

  Well, I'll try to figure this out.

(In reply to comment #2)
>   Hi, Tom,
> 
> > Can you put a default on a loopback interface and make all local outbound
> > packets go through RouteInput instead?
> 
>   Do you propose to return looback from RouteOutput() when route is unknown and
> then find it from RouteInput()? Right? 

Yes.

(In reply to comment #3)
> (In reply to comment #2)
> >   Do you propose to return looback from RouteOutput() when route is unknown and
> > then find it from RouteInput()? Right? 
> 
> Yes.

  Well, this looks like smart workaround, I'll try. The simplest way to implement this I see is to tag such packets as, say, "DeferredRouteRequest" in RouteOutput to be able easily distinguish them from duplicates in RouteInput. Is that acceptable?

(In reply to comment #4)
> (In reply to comment #3)
> > (In reply to comment #2)
> > >   Do you propose to return looback from RouteOutput() when route is unknown and
> > > then find it from RouteInput()? Right? 
> > 
> > Yes.
> 
>   Well, this looks like smart workaround, I'll try. The simplest way to
> implement this I see is to tag such packets as, say, "DeferredRouteRequest" in
> RouteOutput to be able easily distinguish them from duplicates in RouteInput.
> Is that acceptable?

Sorry for the delay in responding-- I missed your question earlier.  I would be fine with the tag you suggest.  Did you find out how this is handled in practice?  Real implementations do not have the luxury of packet tags so presumably they must be able to detect these locally originated packets and distinguish them from duplicates.

  Tom, 

> Sorry for the delay in responding-- I missed your question earlier.  I would be
> fine with the tag you suggest.  Did you find out how this is handled in
> practice?  Real implementations do not have the luxury of packet tags so
> presumably they must be able to detect these locally originated packets and
> distinguish them from duplicates.

  To my shame I didn't find any mention of 127.0.0.1 in AODV-UU sources and stop there. Now I see that looped back packets can be easily detected by incoming interface (lo). I have implemented this in the attached patch, it seems to fix this bug (but not 777 one) without use of tags. All reference traces in src/routing/aodv/test must be re-generated because of ID field in IP headers, I have checked that nothing else changed and new tests are Ok.

  Now I ask you to review that patch and decide whether it's worth to be pushed before 3.7 (I think so).

Created attachment 722 [details]
proposed fix

(In reply to comment #6)
>   Tom, 
> 
> > Sorry for the delay in responding-- I missed your question earlier.  I would be
> > fine with the tag you suggest.  Did you find out how this is handled in
> > practice?  Real implementations do not have the luxury of packet tags so
> > presumably they must be able to detect these locally originated packets and
> > distinguish them from duplicates.
> 
>   To my shame I didn't find any mention of 127.0.0.1 in AODV-UU sources and
> stop there. Now I see that looped back packets can be easily detected by
> incoming interface (lo). I have implemented this in the attached patch, it
> seems to fix this bug (but not 777 one) without use of tags. All reference
> traces in src/routing/aodv/test must be re-generated because of ID field in IP
> headers, I have checked that nothing else changed and new tests are Ok.
> 
>   Now I ask you to review that patch and decide whether it's worth to be pushed
> before 3.7 (I think so).

Pavel,
I read through this but did not step through the code.  It seems like there is no provision for recalculating checksums due to address changing in deferred route output if Node::ChecksumEnabled is true.  

Also, the code seems to assume that all packets received on the loopback are these deferred RouteOutput packets, but what if another process is sending packets to 127.0.0.1?  This code doesn't seem to check for that case:

  // Deferred route request
  if (idev == m_lo)
    {
      DeferredRouteOutput (p, header, ucb, ecb);
      return true;
    }

  Tom,

  thank you for comments, 

> I read through this but did not step through the code.  It seems like there is
> no provision for recalculating checksums due to address changing in deferred
> route output if Node::ChecksumEnabled is true. 

  Could you point me a copy-paste source? 
 
> Also, the code seems to assume that all packets received on the loopback are
> these deferred RouteOutput packets, but what if another process is sending
> packets to 127.0.0.1?  This code doesn't seem to check for that case:
> 
>   // Deferred route request
>   if (idev == m_lo)
>     {
>       DeferredRouteOutput (p, header, ucb, ecb);
>       return true;
>     }

  Right, it seems that dedicated tag is needed anyway. Should I locally deliver that ("another process is sending to 127.0.0.1") packets? By the way, I just realized that AODV doesn't use Ipv4::IsDestinationAddress() method in local delivery code -- do we need one more bug for that?

  Tom,

  please answer my questions above to help me fix this long-standing bug.

  Pavel

(In reply to comment #9)
>   Tom,
> 
>   thank you for comments, 
> 
> > I read through this but did not step through the code.  It seems like there is
> > no provision for recalculating checksums due to address changing in deferred
> > route output if Node::ChecksumEnabled is true. 
> 
>   Could you point me a copy-paste source? 

Sorry for missing this reply originally.

I looked into this and the checksum (if enabled) is only calculated at the time of serialization, so I think there is no real issue.

> 
> > Also, the code seems to assume that all packets received on the loopback are
> > these deferred RouteOutput packets, but what if another process is sending
> > packets to 127.0.0.1?  This code doesn't seem to check for that case:
> > 
> >   // Deferred route request
> >   if (idev == m_lo)
> >     {
> >       DeferredRouteOutput (p, header, ucb, ecb);
> >       return true;
> >     }
> 
>   Right, it seems that dedicated tag is needed anyway. Should I locally deliver
> that ("another process is sending to 127.0.0.1") packets? By the way, I just
> realized that AODV doesn't use Ipv4::IsDestinationAddress() method in local
> delivery code -- do we need one more bug for that?

I believe that you should be able to copy the approach in list routing (which uses IsDestinationAddress()).  Probably we should just make sure with a test case that packets sent to these local addresses are delivered successfully if AODV is the only protocol in use.

Created attachment 770 [details]
fix

  Tom,
 
  please review this (I hope the final one) patch.

(In reply to comment #13)
>   Tom,
> 
>   please review this (I hope the final one) patch.

some minor comments; thanks for adding test code.

+//-----------------------------------------------------------------------------
+/// Tag used by AODV implementation
+struct DeferredRouteOutputTag : public Tag
+{

I didn't understand why to prefer making this a struct instead of a class.  It has methods and a constructor, and all of our other Tags are classes (e.g. you could make oif private data).   

+  uint32_t iif = (oif ? m_ipv4->GetInterfaceForDevice (oif) : -1);
+  DeferredRouteOutputTag tag (iif);

I read this "iif" as "input interface" at first; I see that it probably means instead "IP interface".  Maybe rename to "interface"?


@@ -1316,24 +1395,23 @@
   QueueEntry queueEntry;   while (m_queue.Dequeue (dst, queueEntry))
     {
+      DeferredRouteOutputTag tag;
+      Ptr<Packet> p = ConstCast<Packet> (queueEntry.GetPacket ());
+      p->RemovePacketTag (tag);
+      if (tag.oif != -1 && tag.oif != m_ipv4->GetInterfaceForDevice (route->GetOutputDevice ()))

couldn't this check the return value of p->RemovePacketTag(tag) (i.e., it might be clearer to write 
if (p->RemovePacketTag (tag) && tag.oif != -1 &&...)

@@ -429,6 +484,18 @@
     }

   m_ipv4 = ipv4;
+  
+  // Create lo route. It is asserted that the only one interface up for now is loopback
+  NS_ASSERT (m_ipv4->GetNInterfaces () == 1 && m_ipv4->GetAddress (0, 0).GetLocal () == Ipv4Address ("127.0.0.1"));
+  m_lo = m_ipv4->GetNetDevice (0);
+  NS_ASSERT (m_lo != 0);

I wasn't sure whether you can assume that SetIpv4 is always called when there is exactly one interface, and it seems like you are not checking whether interface is up, as the comment implies.

(In reply to comment #14)
> I didn't understand why to prefer making this a struct instead of a class.

  There is no difference. 

> I read this "iif" as "input interface" at first; I see that it probably means
> instead "IP interface".  Maybe rename to "interface"?

  "i" is for "index" :)) 

> couldn't this check the return value of p->RemovePacketTag(tag) (i.e., it might be clearer to write 

  Done.

> I wasn't sure whether you can assume that SetIpv4 is always called when there
> is exactly one interface, and it seems like you are not checking whether
> interface is up, as the comment implies.

  Yes, this code is not bulletproof, but for now it works. I have pushed patch as is to be able to proceed with the next critical aodv bug. I can return to the "find loopback device" code later if you wish -- just open a dedicated bug.   

  Thank you for all help with this bug.