Subject: Re: [manet] Need for DPD header (SMF document discussion)

From: "Jeff Weston" <[email-masked]>
Date: Thu, 12 Apr 2007 09:48:01 -0400

> From: "Charles E. Perkins" <[email-masked]>
> Subject: Re: [manet] Need for DPD header (SMF document discussion)
> To: "ext Henderson, Thomas R" <[email-masked]>
> Cc: [email-masked]
> Message-ID: <[email-masked]>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> 
> 
> Hello Tom,
> 
> ext Henderson, Thomas R wrote:
> >
> >> We just proved otherwise -- that a good hash function completely
> >> disambiguates based on IP header alone.  There is no need to
> >> include payload data.
> >>     
> >
> > It would be nice to see some data regarding how heavyweight 
> the hashing
> > is for the classes of devices under consideration.  Is that 
> posted in a
> > previous list message or presentation?  I agree that if it is
> > inexpensive, a hash on the packet would be preferable to 
> the tagger ID
> > solution.
> I am in the process of finding out what inexpensive hash functions
> are sufficiently effective for the job.  So far, we have found
> that SHA-1 can completely disambiguate packets that are
> different only in the ip_id field, storing only 32 bits of the hash
> result (e.g., not 160 bits).  To me, that means SHA-1 is
> "too good", and we can make do with less.

Maybe I'm just misunderstanding something, but it seems to me as if you're saying "hashing is good enough as long as the IP_ID field
is changed, so we don't need the DPD option header".  But the DPD option header only applies to IPv6, which doesn't have an IP_ID
field in the first place, so the point is moot, no?  (not to mention, that the IP_ID field is not incremented on all systems -- many
Linux 2.4 kernels always set it to zero for UDP packets, IIRC)

> I'll also try to get a count of the instruction cycles needed.
> 
> > However, I do not see why you would need (or want) to hash just the
> > header; the hash output will be larger than or commensurate 
> with storing
> > the header fields themselves.  Plus, I have been told that many
> > multicast sources do not have distinguishing IP ID fields.
> >   
> I don't claim that we should avoid including the payload.  
> Exactly what 
> needs
> to be hashed is a matter for further clarification.  My 
> statement was really
> targeted towards making the case that hashing is good and 
> cheap.  If we
> can get away with hashing only 512 bits of data, that would 
> be nice, but
> it is not a showstopper if we need to use more.
> 
> And, again, for cases where hashing does not disambiguate,
> then we can use the DPD option.  This would, of course, be
> fine as a backup strategy.

I don't think hashing is as reliable as you think it is.  Here are a few potential problems I see with your solution (which, as I
understand it, is simply "compare hash to an arbitrary number of previously stored hashes, and add the DPD option header if there's
a conflict"):

1) In a heterogeneous MANET, where different devices have different memory and CPU capabilities, you may have nodes that are capable
of storing only a very small subset of the hashes stored by other nodes.  If these nodes source any data, then it is possible that
they may not notice a hash conflict while the forwarding nodes do, dropping the packet...
2) Multicast packets may be received out-of-order, which could cause problems if a conflicting hash has just been thrown out by the
source node, but not on some forwarding nodes (so they drop the packet).
3) Similarly, if any node sources multicast packets such that they have a TTL/max hop count that does not allow propogation
throughout the entire MANET, then the source node will undoubtedly throw old hashes out faster than some of its forwarders...
4) The same problem will happen if a MANET fragments, and comes back together some time later.

These are potential problems with IPv6 no matter how good your hashing is (even if your hash is "store the entire packet"), since
plain vanilla IPv6 packets with identical payloads are indistinguishable, AFAIK.  As previously mentioned, these aren't uncommon,
with video, VOIP "hello" packets, etc.

Honestly, I just don't see the need to bring in the complications of hashing ... it creates more problems than it solves, IMHO...
Creating a potentially unreliable multicast network in favor of saving a few bytes on the air just doesn't seem right to me.

-Jeff Weston

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

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 12 Apr 2007 08:58:24 -0700

Hello Jeff,

> understand it, is simply "compare hash to an arbitrary number of previously stored hashes, and add the DPD option header if there's
You seem to characterize conflicting hash results as a frequent
occurrence, which does not in any way match our experiemental
results.  Besides, any IPv4 source which is equipped to put in the
DPD option will much more easily be equipped for correctly
manipulating the ip_id field, which almost completely invalidates
most of your arguments as far as I can tell.  But even for IPv6 ...

> they may not notice a hash conflict while the forwarding nodes do, dropping the packet...
How does the DPD option enable nodes to have more slots for
for storing data about past packets?
> source node, but not on some forwarding nodes (so they drop the packet).
Do you mean the source of the multicast packet?  If so, I guess your point
is that the source node may not have a "complete" record of previous hashes,
nd other nodes may have more complete records for that source.

I find this to be very, very unlikely, because:
1. A certain number of hash results would be mandated for
    memory
2. They don't have to be more than 32 bits long, probably less.
3. Anyway hash collisions seem to be rare, and you are proposing
    something that would happen even more rarely.

I did not get a consistent answer to my previous questions about
multiple taggers vs. increased congestion because of the effect
of _disabling_ duplicate suppression.

> throughout the entire MANET, then the source node will undoubtedly throw old hashes out faster than some of its forwarders...
This seems to be effectively the same scenario as before -- except
that using limited TTL seems already to indicate that the source is
happy if transmissions are limited, so probably throwing out a few
more is even less of a problem (in the very rare subset of the very
rare case).
> 4) The same problem will happen if a MANET fragments, and comes back together some time later.
Do you mean that the DPD option is solving problems that arise
because of manet fragmentation/rejoining?  I'm very surprised
to hear this.
> with video, VOIP "hello" packets, etc.
Do you mean the DPD option is a mechanism for disambiguating
otherwise undistinguishable packets?  Then we are in perfect
agreement, as I have already stated in several previous messages
to this mailing list.  My claim is that this is a very small proportion
of total broadcasts, and that the DPD option will most often be
used in just these cases.
> Creating a potentially unreliable multicast network in favor of saving a few bytes on the air just doesn't seem right to me
>   
Saving bytes over the air can dramatically increase the lifetime of
many networks.  Nobody seems to be talking about creating
an unreliable multicast network, least of all me.

Regards,
Charlie P.

---

From: "Templin, Fred L" <[email-masked]>
Date: Thu, 12 Apr 2007 09:05:55 -0700

Charlie,

> most of your arguments as far as I can tell.  But even for IPv6 ...

I disagree; it is up to the sending host to choose its ip_id
in such a way that two packets that may be alive in the network
at the same time would not have the same ip_id value. But, there
are many factors that may weigh in as to the exact strategy a
host chooses for setting ip_id and it is unrealistic to require
hosts to abandon those other considerations solely for providing
a unique identifier for DPD.

Fred
[email-masked]

---

From: "Jeff Weston" <[email-masked]>
Date: Thu, 12 Apr 2007 13:54:42 -0400

Hi Charlie,

> > 1) In a heterogeneous MANET, where different devices have different 
> > memory and CPU capabilities, you may have nodes that are capable of 
> > storing only a very small subset of the hashes stored by 
> other nodes.  If these nodes source any data, then it is 
> possible that they may not notice a hash conflict while the 
> forwarding nodes do, dropping the packet...
> >   

It doesn't allow more slots, but it doesn't need them either.  Multicast source nodes only need to know the last used sequence
number for each destination address.  Therefore, this particular situation would never arise with use of the DPD option (unless a
node were storing the entire DPD sequence number space, which doesn't make much sense from a design standpoint anyways).

> > These are potential problems with IPv6 no matter how good 
> your hashing 
> > is (even if your hash is "store the entire packet"), since plain 
> > vanilla IPv6 packets with identical payloads are 
> indistinguishable, AFAIK.  As previously mentioned, these 
> aren't uncommon, with video, VOIP "hello" packets, etc.
> >   
> agreement, as I have already stated in several previous 
> messages to this mailing list.  My claim is that this is a 
> very small proportion of total broadcasts, 

That depends greatly on the application(s) being used in the MANET, IMHO.

-Jeff