Bug 772 - AODV is unable to correctly buffer packets waiting for route reply
AODV is unable to correctly buffer packets waiting for route reply
Status: RESOLVED FIXED
Product: ns-3
Classification: Unclassified
Component: routing
ns-3-dev
All All
: P2 critical
Assigned To: Pavel Boyko
:
Depends on:
Blocks: 777
  Show dependency treegraph
 
Reported: 2009-12-10 06:01 EST by Pavel Boyko
Modified: 2010-03-01 02:04 EST (History)
3 users (show)

See Also:


Attachments
proposed fix (19.65 KB, application/octet-stream)
2010-01-13 05:56 EST, Pavel Boyko
Details
fix (21.52 KB, application/octet-stream)
2010-02-24 06:51 EST, Pavel Boyko
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Pavel Boyko 2009-12-10 06:01:09 EST
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.
Comment 1 Tom Henderson 2009-12-11 01:37:35 EST
(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?
Comment 2 Pavel Boyko 2009-12-11 01:42:00 EST
  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.
Comment 3 Tom Henderson 2009-12-11 02:34:40 EST
(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.
Comment 4 Pavel Boyko 2009-12-11 03:35:45 EST
(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?
Comment 5 Tom Henderson 2010-01-06 00:30:25 EST
(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.
Comment 6 Pavel Boyko 2010-01-13 05:55:40 EST
  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).
Comment 7 Pavel Boyko 2010-01-13 05:56:23 EST
Created attachment 722 [details]
proposed fix
Comment 8 Tom Henderson 2010-01-14 00:51:18 EST
(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;
    }
Comment 9 Pavel Boyko 2010-01-14 01:06:41 EST
  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?
Comment 10 Pavel Boyko 2010-02-21 07:46:28 EST
  Tom,

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

  Pavel
Comment 11 Tom Henderson 2010-02-21 11:56:10 EST
(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.
Comment 12 Pavel Boyko 2010-02-24 06:51:32 EST
Created attachment 770 [details]
fix
Comment 13 Pavel Boyko 2010-02-24 06:53:52 EST
  Tom,
 
  please review this (I hope the final one) patch.
Comment 14 Tom Henderson 2010-02-25 02:03:44 EST
(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.
Comment 15 Pavel Boyko 2010-03-01 02:04:58 EST
(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.