Subject: Re: [Manet-dt] Re: [manet] Need for DPD header (SMF document discussion) - ValidReason for Tagger ID

From: "Jeff Weston" <[email-masked]>
Date: Thu, 3 May 2007 10:09:42 -0400

> From: "Charles E. Perkins" <[email-masked]>
> Subject: Re: [Manet-dt] Re: [manet] Need for DPD header (SMF document
> 	discussion) - ValidReason for Tagger ID

> To summarize, I prefer if we
> make hashing "good enough", and then use
> the DPD header for the rare cases where
> the hash function fails to distinguish different
> flooded packets.

Charlie,

I am curious as to how you are going to determine whether the hash funtion fails or not, given that different forwarder nodes will
often have a different hash history than the sender...  Even if you assume that all nodes are equal and store the same amount of
history information, there are numerous reasons that nodes may have a different hash history.  Assuming a sort of FIFO queue of
hashes, if there is a packet collision (extremely common in standard 802.11 multicast), then some forwarding nodes will have one
older hash than the sender node.  If some (but not all) packets have a low TTL, this can produce the same effect to a much larger
degree.  The problem becomes more pronounced if you decide to conserve memory and not keep separate queues for each
source/destination tuple.

I still contend that exactly duplicate IPv6 packets are not all that uncommon, depending on your application (video, anything that
uses keepalives).  It's even more common if you do not hash the entire packet, as many XML-formatted messages may be the same for
the first number of bytes, for instance.

I can really forsee hashing causing many applications to fail in a MANET.  All it takes is the right data rate and the right
keepalive rate.  If they happen to match up to "one keepalive almost every time we roll through our history", the application will
fail at random.

-Jeff Weston

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 03 May 2007 13:40:48 -0700

Hello Jeff,

ext Jeff Weston wrote:
> often have a different hash history than the sender...
Each flooded packet has to be compared against other flooded packets
from the same sender.  I think this much is common to most approaches,
but of course we could design something different.
>   Even if you assume that all nodes are equal and store the same amount of
All that matters is that the source ensures that every packet
hashes to a different value.  If the packet does not already
produce a different hash, then the source "SHOULD" add
a DPD header (or something).
> the first number of bytes, for instance.
Well, if they are exactly duplicate, how can you tell if they are
duplicated (and needing to be suppressed) vs. duplicated (and
not needing to be suppressed)?
> keepalive rate.  If they happen to match up to "one keepalive almost every time we roll through our history", the application will
Do you still think so, given my responses above?

Regards,
Charlie P.

---

From: "Jeff Weston" <[email-masked]>
Date: Thu, 3 May 2007 22:27:33 -0400

Charlie,

Comments inline.

> -----Original Message-----
> From: Charles E. Perkins [mailto:[email-masked]] 
> Sent: Thursday, May 03, 2007 4:41 PM
> To: ext Jeff Weston
> Cc: [email-masked]
> Subject: Re: [Manet-dt] Re: [manet] Need for DPD header (SMF 
> document discussion) - ValidReason for Tagger ID
> 
> Hello Jeff,
> 
> ext Jeff Weston wrote:
> >
> >   
> >> make hashing "good enough", and then use the DPD header 
> for the rare 
> >> cases where the hash function fails to distinguish 
> different flooded 
> >> packets.
> >>     
> >
> > Charlie,
> >
> > I am curious as to how you are going to determine whether the hash 
> > funtion fails or not, given that different forwarder nodes 
> will often have a different hash history than the sender...
> Each flooded packet has to be compared against other flooded 
> packets from the same sender.  I think this much is common to 
> most approaches, but of course we could design something different.
> >   Even if you assume that all nodes are equal and store the same 
> > amount of history information, there are numerous reasons 
> that nodes 
> > may have a different hash history.  Assuming a sort of FIFO 
> queue of 
> > hashes, if there is a packet collision (extremely common in 
> standard 
> > 802.11 multicast), then some forwarding nodes will have one 
> older hash 
> > than the sender node.  If some (but not all) packets have a 
> low TTL, this can produce the same effect to a much larger 
> degree.  The problem becomes more pronounced if you decide to 
> conserve memory and not keep separate queues for each 
> produce a different hash, then the source "SHOULD" add a DPD 
> header (or something).

Right.  But my point is that this is not a trivial thing to when forwarding
nodes have different histories.  While the source/tagger may not see a new
packet as having a conflicting hash, that doesn't automatically imply that
the forwarders will also see no conflicting hash.  Since they will have a
different history of hashes to compare against, they may well drop packets
as duplicates, when they are, in fact, not duplicates.

> > I still contend that exactly duplicate IPv6 packets are not 
> all that 
> > uncommon, depending on your application (video, anything that uses 
> > keepalives).  It's even more common if you do not hash the 
> entire packet, as many XML-formatted messages may be the same 
> for the first number of bytes, for instance.
> >   
> Well, if they are exactly duplicate, how can you tell if they 
> are duplicated (and needing to be suppressed) vs. duplicated 
> (and not needing to be suppressed)?

With the DPD option, you mark them with a new header.  A node can mark the
packets that it sources, as well as those packets flooded into the MANET by
a gateway/"tagger"...  This is relatively trivial, and NRL's SMF code
already does this.

This isn't as easy to do with hashing, because you are not marking each
packet, but instead, comparing its hash to a limited, non-predictable
history of hashes.  The problem is again that this history does not match
the history at all forwarded nodes, so some forwarders may (incorrectly)
drop the packet as being a duplicate.  I do not see a way to avoid this
problem.

> > I can really forsee hashing causing many applications to fail in a 
> > MANET.  All it takes is the right data rate and the right keepalive 
> > rate.  If they happen to match up to "one keepalive almost 
> every time we roll through our history", the application will 
> fail at random.
> >   

Yes.

-Jeff

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 04 May 2007 14:15:07 -0700

Hello Jeff,

Continuing the discussion...

ext Jeff Weston wrote:
>
>  ... my point is that this is not a trivial thing to when forwarding
The source would be in charge of disambiguating packets.
For sources that do not obey, the taggers can put in DPD headers
if there is danger of a problem.  For heavy flows, clearly the
intended receiver is not worried about energy and so it won't
bother anyone much if there is more overhead.  For energy
constrained systems, it is much more of a bother and so the
DPD header should be avoided if it is not needed -- which
would be most of the time I reckon.

> a gateway/"tagger"...  This is relatively trivial, and NRL's SMF code
Yes, the source should do this for packets that would otherwise
be identical.  This is a subcase of the point about having the
same hash result (rare except for identical packets, but possible).

My point was that the taggers cannot disambiguate identical
packets (!).  Isn't this obvious?  In the scenario of unfortunate
applications that insist in emitting identical packets for IPv6
without any RTP or other nice wrapper, if the source does not
put in the distinguishing data at the network layer, the taggers
are likely to pessimistically assume they have to tag all
identical packets.

Ick.
> drop the packet as being a duplicate.  I do not see a way to avoid this
(?) But the source can do the tagging when needed.  Why doesn't
this solve the problem, for the case you mention when the hash does
not disambiguate?
>>> MANET.  
Now, do you still think so??

Regards,
Charlie P.

---

From: "Jeff Weston" <[email-masked]>
Date: Mon, 7 May 2007 09:27:30 -0400

Comments inline. 

> Sent: Friday, May 04, 2007 5:15 PM
> To: ext Jeff Weston
> Cc: [email-masked]
> > nodes have different histories.  While the source/tagger 
> may not see a 
> > new packet as having a conflicting hash, that doesn't automatically 
> > imply that the forwarders will also see no conflicting hash.  Since 
> > they will have a different history of hashes to compare 
> against, they 
> > may well drop packets as duplicates, when they are, in 
> fact, not duplicates.
> >   

Precisely, and my whole point was that with hashing, there is an inherent problem, in which duplicate-hashed packets will sometimes
be dropped due to forwarders having a different history than the source/tagger.  Do you agree?

> For sources that do not obey, the taggers can put in DPD 
> headers if there is danger of a problem.  For heavy flows, 
> clearly the intended receiver is not worried about energy and 
> so it won't bother anyone much if there is more overhead.  
> For energy constrained systems, it is much more of a bother 
> and so the DPD header should be avoided if it is not needed 
> -- which would be most of the time I reckon.

Are you suggesting that the tagger/source keep track of the data rate it's sending, and add the DPD option if the data rate is too
large?  That sounds much more complicated than necessary to me...

> >> duplicated (and needing to be suppressed) vs. duplicated (and not 
> >> needing to be suppressed)?
> >>     
> >
> > With the DPD option, you mark them with a new header.  A 
> node can mark 
> > the packets that it sources, as well as those packets 
> flooded into the 
> > MANET by a gateway/"tagger"...  This is relatively trivial, 
> and NRL's 
> > SMF code already does this.
> >   
> Yes, the source should do this for packets that would 
> otherwise be identical.  This is a subcase of the point about 
> having the same hash result (rare except for identical 
> packets, but possible).
> 
> packets (!).  Isn't this obvious?  In the scenario of 
> unfortunate applications that insist in emitting identical 
> packets for IPv6 without any RTP or other nice wrapper, if 

I thought the point of this whole debate was to save a few bytes on the air ... Why are we forcing applications running on a MANET
to use a wrapper, or to timestamp their keepalives, thereby negating any energy savings in the first place?

> the source does not put in the distinguishing data at the 
> network layer, the taggers are likely to pessimistically 
> assume they have to tag all identical packets.
> 
> Ick.
> > This isn't as easy to do with hashing, because you are not marking 
> > each packet, but instead, comparing its hash to a limited, 
> > non-predictable history of hashes.  The problem is again that this 
> > history does not match the history at all forwarded nodes, so some 
> > forwarders may (incorrectly) drop the packet as being a 
> duplicate.  I 
> > do not see a way to avoid this problem.
> >   
> (?) But the source can do the tagging when needed.  Why 
> doesn't this solve the problem, for the case you mention when 
> the hash does not disambiguate?

My whole point is that the source doesn't always know when tagging is needed!  Different forwarders will have different hash
histories, period (due to various reasons previously mentioned).  Do you agree?  So unless all forwarders are feeding back
information on their histories to the source somehow, the source has absolutely no way of knowing when tagging is definitely
unnecessary, correct?

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 07 May 2007 08:05:38 -0700

Hello Jeff,

 From your answers, it seems that there is still
something I am not making clear, even though
it seems clear bordering on obvious to me.

To restate:

- Source is in charge of making packets
   distinguishable by way of a hash function.
- Every node suppressing duplicates uses the
   same hash function.  Thus, if the source
   ensures that packets are distinguished, no
   other node (regardless of history) will have
   a problem with this.
- For sources that do not obey this, a very
   very rare problem exists for packets that
   are not exact duplicates.  These sources
   are MANET-unaware sources, otherwise
   they would do the right thing.
- To solve the problem when the source does
   not distinguish, it has been proposed to use
  "taggers" (hashing or not).
- I believe you have claimed that some IPv6
   packet streams in your experience produce
   multiple identical packets that are not supposed
   to be considered duplicates -- and, hence not
   suppressed.
- To distinguish these packets, the proposal is
   to tag _every_ IPv6 flooded packet _ever_
   sent in the ad hoc network?  Externally
   sourced or not?

This is a very severe and onerous requirement to
solve a problem I have never seen and only the
word of the tagger proponents to support its
existence.

It would be a burden for _every_ ad hoc
network ever built from this specification.

Continuing...

- In order to distinguish such packets, hashing
   would require insertion of a header.  We can
   discuss more about this header, but before
   doing so I think it should be clear that this is
   only to solve a problem that is almost
   astronomically rare, and only for IPv6 packets.

- For this astronomically rare problem, for
   MANET-unaware sources that do not
   already make the packets distinct, I agree
   that taggers could put in a header.

- As an even rarer occurrence within the
   already rare problem, it is possible that
   for multiple MANET-unaware sources,
   taggers might fail to have enough history
   to ensure unique hash results for every
   instance of "duplicated but different"
   packets that are somehow not supposed
   to be suppressed.

That is the context in which I see our
current discussion is being carried out.
There must be some part of the bedrock
context that you do not agree with, otherwise
the conclusion seems inescapable that we
should use hashing.  Can you point out
where our assumptions are diverging?

Given the above, I have made some
answers inline below.

> be dropped due to forwarders having a different history than the source/tagger.  Do you agree?

You must be referring to the case where the source does not actually
do what it is supposed to do.  Right?
> large?  That sounds much more complicated than necessary to me...
It is no more complicated than any other rate-controlled
operation.
> to use a wrapper, or to timestamp their keepalives, thereby negating any energy savings in the first place?
First, these are not applications running purely on the MANET,
or else they would already have the DPD header inserted from
the source and no tagger would ever have any work to do.
Unless I misunderstand you, this is only for cases where a
data stream is coming from outside the MANET and the external
source does not know it is running a MANET application.

> My whole point is that the source doesn't always know when tagging is needed! 

No, the source would _always_ know exactly when
the packets have to be distinguished.  It is sourcing them!
It knows that any node checking for duplicates will use
exactly the same hash function and so will get the same
answer per packet.

>  Different forwarders will have different hash
> histories, period (due to various reasons previously mentioned).  Do you agree?
I agree that for external, MANET-unaware hosts that are using
specific kinds of applications that I have never ever seen, a
problem could exist for a kind of data stream that I have
never ever seen.

>   So unless all forwarders are feeding back
No.  The source would always emit packets that can
easily be distinguished.  Unless it were external and
MANET-unaware.

Regards,
Charlie P.

---

From: "Jeff Weston" <[email-masked]>
Date: Mon, 7 May 2007 12:03:37 -0400

>    other node (regardless of history) will have

This is the part where I'm having the problem.  I guess I'm thinking about this from an implementation perspective...

-In order for a source to ensure that the packets are distinguishable via a hash, it must store a history of hashes to compare
against.
-In order for the program to work for any length of time, the source must have some sort of limited queue of hashes, as it cannot
store an infinite number of them.
-Therefore, the source cannot ensure that a given packet will not have a hash conflict with ANY packet it has sent; the source can
only ensure that there will be no conflict with any hash within its limited history.
-Thus, whether the source's limited history matches up with (or at least includes all of) its forwarders' limited history, IS
important.

I had assumed this would most likely be implemented as a memory-based FIFO queue (always store X hashes from each source), which
would introduce a problem in which forwarders (having a similarly limited history) would have a history of hashes (from not
receiving some packets due to collisions, limited TTL packets, etc.) that the source had already purged from memory, and was
therefore unable to compare against.  This was the issue I was trying to get you to see (particularly since duplicate IPv6 packets
are not uncommon with some applications).

I suppose it's possible that you could have a sort of time-based FIFO queue (store all hashes for the last X seconds from each
source), rather than a simple memory-based FIFO.  This would effectively avoid the history mismatch problem (assuming all nodes
agree on the number of seconds), but it forces you to keep more state (e.g. a timestamp w/ each hash), and would likely lead to high
memory usage with fast data flows.

-Jeff

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 07 May 2007 09:25:17 -0700

Hello Jeff,

> This is the part where I'm having the problem.  I guess I'm thinking about this from an implementation perspective...
That is also how I am thinking about the problem.
> -In order for a source to ensure that the packets are distinguishable via a hash, it must store a history of hashes to compare
Check.
> store an infinite number of them.
Check.

> only ensure that there will be no conflict with any hash within its limited history.
Check.
> -Thus, whether the source's limited history matches up with (or at least includes all of) its forwarders' limited history, IS
Check.
> therefore unable to compare against.
If the source produces enough packets to swamp its queue,
within the time during which we want to consider packets to
be live in the network, then the source can add the new
header.
>   This was the issue I was trying to get you to see (particularly since duplicate IPv6 packets
This is the issue that has been explained to me repeatedly
and over and over again, iteratively, and etc.  :-)
> memory usage with fast data flows.
I think this tradeoff can be made without a huge expense,
and that we can compare the energy utilization of the
two schemes.  All schemes proposed so far are per
source, right?  Regarding the timestamp, I can design a
scheme for that using only a few bits.  There is no need
to store a full microsecond-accurate timestamp per entry.
Plus, the timestamp would not be needed at all for well
behaved sources.  Maybe the DPD header should
include a bit describing whether the source is well
behaved (meaning, MANET-aware and rate-limiting).
For such sources, bookkeeping would be minimized.

Regards,
Charlie P.

PS (trivia contest): What is the only word in the
      English language with three consecutive pairs
      of double letters?