Subject: [manet] FW: Intended status of produced IDs

From: Teco Boot <[email-masked]>
Date: Fri, 06 Apr 2007 00:18:14 +0200

Hi,

During the IETF-68 MANET WG meeting, I heard the target for the current I-D
MANET protocols is Experimental.

The drafts itself mention Standards Track (OLSRv2 mentions nothing).

Are there minutes of the meeting published?

Can the chair provide the target for the drafts?

Teco

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

---

From: Emmanuel Baccelli <[email-masked]>
Date: Fri, 06 Apr 2007 00:53:28 +0200

Hi Teco,
SMF is targeted as experimental. OLSRv2 and DYMO are targeted as 
standards track.
Emmanuel

Teco Boot a écrit :
> Hi,
> 
>  
> 
> During the IETF-68 MANET WG meeting, I heard the target for the current 
> I-D MANET protocols is Experimental.
> 
> ------------------------------------------------------------------------
>

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 06 Apr 2007 10:41:57 +0200

> SMF is targeted as experimental. OLSRv2 and DYMO are targeted as 

Why two standards track documents?  Why can't it be just one protocol?

Alex

______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
______________________________________________________________________

---

From: Teco Boot <[email-masked]>
Date: Fri, 06 Apr 2007 11:21:33 +0200

Thanks for clarification.
Be aware getting a standards track RFC approved could be hard. It needs
consensus in the WG. And would alternative Experimental protocols (3561,
3626, 3684, 4728) get obsolete?
My personal idea on SMF, the DPD part is ready for standards track; it fills
in something missing and it can be reused for unicast traffic also, for
protecting a network for melting down due to routing loops. Unsynchronized
routing table updates introduce routing loops, a problem when using
proactive protocols.
Teco

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 06 Apr 2007 09:27:56 -0700

Hello Alex,

Your short question hides several Ph.Ds worth of answers.

In fact, there can be one protocol, but it is far from trivial
to do it.  First, you must allow some routes to be proactively
maintained, and which ones are to be reactively maintained.
Then, you must ask yourself to design a mechanism by which
proactively maintained routes do not disturb uninvolved nodes.

Once you have answered these difficult questions, you
can progress to answering the impossible question:
- How are policies set to determine which routes are
  proactively maintained and which are reactive.

My opinion is that this is a very subtle matter and should
be controlled by application requirements, and by service
availabilities.

Alternatively, you could take the sledge hammer approach
and just invalidate either OLSR or DYMO (or both :-).

On the positive side, I am very much in favor of making a
single protocol.  I think we are a few months away from being
able to initiate that effort.

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Sun, 08 Apr 2007 13:26:28 -0700

Hello folks,

The SMF document mentions hashing as a tool for
identifying separate  network-layer broadcasts.
We decided to test out the efficiency of various hash
functions for this purpose.  An  ideal hash function
would provide two different values for two different
IP headers, so that different broadcasts could be
disambiguated by a simple test.

If a hash function has this property, then there would be
little need for a separate IPv4 protocol element to make
the distinction between various broadcast packets.

We have found out that well known hash functions such
as SHA-1 already have the desired property.  If one
takes the source IP address of an IP header, and adjoins
to it the ip_id field (16 bits), and uses this as input for SHA-1,
then the 160-bit resulting values have 0.0000000% overlap
over the range of all 65,536 ip_id values.  We can probably
do with less than 160-bit values, to minimize storage
requirements.

For this reason, I am in favor of specifying (at least for
most IPv4 systems) that the sender should be able to use
different ip_id values for each successive broadcast packet,
and that receivers should be able to run a hash function to
obtain a unique identification for each received multicast
(e.g., broadcast) packet.   This also goes along with the
philosophy of absolutely minimizing bytes over the air
when a small amount of extra processing can be done
instead.

For IPv6, the situation is different and there is a need to
specify another network-layer extension header, as has
already been done in SMF (or else specify the use of the
fragmentation header in a certain way).  I am not sure
when the "tagger" function would ever be needed, given
the availability of the fragmentation header.  If the problem
is that packets from the Internet are destined for nodes in
an ad hoc network, how will the tagger distinguish between
duplicate packets and distinct new multicasts?  What
happens nowadays when a multicast router gets a
duplicate packet?  Presumably, broadcast packets will
not emerge from the Internet for injection into a manet;
we might even prohibit such a thing from happening.

What is the likelihood that there would be reluctance to
standardize the newly specified DPD header as an
IPv6 extension header?  If there is any reluctance, this
would translate into further delays for SMF, and would
swing the balance towards using the fragment header
instead.

Regards,
Charlie P.

---

From: "Ian Chakeres" <[email-masked]>
Date: Mon, 9 Apr 2007 17:21:43 +0530

Comments inline.

<snip>

> we might even prohibit such a thing from happening.

The tagger id is useful when the source does not include the DPD
option, another box (tagger) is responsible for adding the DPD IPv6
option, and the tagger cannot be sure that it is the only tagger.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 09 Apr 2007 09:06:23 -0700

Hello Ian,

I must be missing something, please excuse my Monday
morning density...

> option, and the tagger cannot be sure that it is the only tagger.
If the purpose of the option is to disambiguate multicast
packets, why does it matter?  No matter which node performs
the disambiguation, it only needs to be done once...(?)  In fact,
shouldn't we specify that the DPD option should appear
AT MOST once in a packet?

Furthermore, I would strongly suggest that the DPD option
_only_  be used when a hash function would otherwise give
the same result as it did for another recent packet from the
same source.  In other words, even for IPv6 we should rely
on hashing for 99.999% of the cases and specify the use of
the DPD option for only the rarity of a duplicated hash result.

Then we have to decide on which hash function to use.
More on that later :-)  The main point for now is to agree
that SMF should make some such specification, and relegate
the DPD option to only very rare use.

Regards,
Charlie P.

---

From: "Ian Chakeres" <[email-masked]>
Date: Tue, 10 Apr 2007 14:19:27 +0530

Comments inline.

> AT MOST once in a packet?

The purpose is to uniquely identify the packet. If a node other than
the source inserts the option, and there might be multiple taggers,
then the tagger id must be included.

I agree the DPD option should appear at most once.

Imagine there a manet with multiple points of attachment. If the
source did not include the option field, then these attachment points
should tag the packets. If each attachment points includes on the ID,
the DPD matching might overlap. If this occurs various bad things
happen. To avoid this situation the tagger id, disambiguates who
performed the tagging operation.

> the DPD option for only the rarity of a duplicated hash result.

I believe the problem is that the tagger (sometimes not the source)
cannot determine which packets are duplicates and which are not
(unless they contain an ID). If you have a simple method for taggers
to determine whether the ID is needed or not, I would be interested in
hearing about it.

Also (this has been discussed before) hash operations can be heavy
weight for weak devices.

For these reasons, I do not think hashing should be the normal
operation. Instead tagging packets with good sequence numbers should
be the default operation.

Note that hashing (without including a unique ID) can result in
several false collisions for video data, since video data can produce
identical packets often. Joe has mentioned this a few times in the
past. I believe he might have even presented some data long ago.

---

From: "Velt, R. \(Ronald\) in 't" <[email-masked]>
Date: Tue, 10 Apr 2007 14:41:29 +0200

Hi,

> -----Original Message-----
> From: Emmanuel Baccelli [mailto:[email-masked]] 
> Sent: vrijdag 6 april 2007 0:53
> To: [email-masked]
> Subject: Re: [manet] FW: Intended status of produced IDs
> 
> Hi Teco,
> SMF is targeted as experimental. OLSRv2 and DYMO are targeted 
> as standards track.

However, draft-ietf-manet-smf-04 says (as noted by Teco): "Intended status: Standards Track". Is this a glitch?

Ronald

> Emmanuel
> 
> Teco Boot a écrit :
> > Hi,
> > 
> >  
> > 
> > During the IETF-68 MANET WG meeting, I heard the target for the 
> > current I-D MANET protocols is Experimental.
> > 

This e-mail and its contents are subject to the DISCLAIMER at http://www.tno.nl/disclaimer/email.html

---

From: "Charles E. Perkins" <[email-masked]>
Date: Tue, 10 Apr 2007 08:33:08 -0700

Hello Ian,

> then the tagger id must be included.
Do you mean to imply that the tagger becomes the source IP
address for the packet?  If the source IP address stays the same,
then why does the identity of the tagger matter?

> performed the tagging operation.
Now I am even more confused.  If two different taggers
add two different options to the same broadcast/multicast
packet, how can a manet node tell they are the same packet
after all, and (to fulfill the whole point of the exercise)
suppress duplicates?

> to determine whether the ID is needed or not, I would be interested in
My method is simple:
1  Run a hash function on the packet.
2. Compare to previous packets
3. If there is a match, add the option.
4. Otherwise, do not.

What's needed here is agreement on which hash function to use.
It looks like we can devise a perfect hash, at least until the ip_id
field rolls over.  By that time, the previous packet that might have
collided in hash space will be a distant forgotten memory of the
manet.
> Also (this has been discussed before) hash operations can be heavy
I strongly disagree with this claim.  To my understanding, it is
practically always the other way around.  Adding bytes over the
air is typically more energy intensive than additional computation.
 
I'm not talking about full-blown zillion-bit privacy here.  Some
hash functions that work are much lighter weight.

> be the default operation.
I strongly disagree with this.  I would like to see any documentation
to the effect that this saves energy.

If there is a rare system for which it is true, then those few devices
could add the option.  For most devices, the option SHOULD NOT
be used...
> past. I believe he might have even presented some data long ago.
We just proved otherwise -- that a good hash function completely
disambiguates based on IP header alone.  There is no need to
include payload data.

Regards,
Charlie P.

---

From: Evelyn Stephen <[email-masked]>
Date: Tue, 10 Apr 2007 10:13:09 -0700 (PDT)

i like to unsubscribe
  
"Velt, R. (Ronald) in 't" <[email-masked]> wrote:
  Hi,

Ronald

 
---------------------------------
Finding fabulous fares is fun.
Let Yahoo! FareChase search your favorite travel sites to find flight and hotel bargains.

---

From: "Velt, R. \(Ronald\) in 't" <[email-masked]>
Date: Tue, 10 Apr 2007 22:00:48 +0200

Hello Charles,

Very probably, I am several orders of magnitude denser any given day of
the week than you may have been on Monday morning, but...

> From: Charles E. Perkins [mailto:[email-masked]] 
> Sent: dinsdag 10 april 2007 17:33
> To: ext Ian Chakeres
> Cc: [email-masked]
> Subject: Re: [manet] Need for DPD header (SMF document discussion)
> 
> 
> Hello Ian,
> 
> ext Ian Chakeres wrote:
> >
> address for the packet?  If the source IP address stays the 
> same, then why does the identity of the tagger matter?
> 
> Now I am even more confused.  If two different taggers add 
> two different options to the same broadcast/multicast packet, 
> how can a manet node tell they are the same packet after all, 
> and (to fulfill the whole point of the exercise) suppress duplicates?
> 

I just read the relevant portion of the SMF draft. Can I test my
understanding by "explaining" this to you? My interpretation is that the
'tagger ID' helps in the case where multicast packets from a single
source _outside_ the manet can somehow follow different paths to
different gateways ('points of attachment'), where they are to be
injected _into_ the manet. At this point, these packets would be tagged.
Since this would happen only once per packet, there is never more than
one DPD option per packet. However, each 'tagger' takes its packet
identifiers from its own independent number space. Therefore, without
the 'tagger ID', Murphy will ensure that sometimes two 'taggers' will
add an equal packet ID on two packets, that in actuality are different,
but have the same source address and multicast destination address.
Thus, 'false duplicates' would be created. Within the manet, these would
be indistinguishable for DPD, leading to incorrect discarding. [SMF
authors, please correct...]

> _only_  be 
> >> used when a hash function would otherwise give the same 
> result as it 
> >> did for another recent packet from the same source.  In 
> other words, 
> >> even for IPv6 we should rely on hashing for 99.999% of the 
> cases and 
> >> specify the use of the DPD option for only the rarity of a 
> duplicated 
> >> hash result.
> >
> It looks like we can devise a perfect hash, at least until 
> the ip_id field rolls over.  By that time, the previous 
> packet that might have collided in hash space will be a 
> distant forgotten memory of the manet.
> >
> I strongly disagree with this claim.  To my understanding, it 
> is practically always the other way around.  Adding bytes 
> over the air is typically more energy intensive than 
> additional computation.
>  
> I'm not talking about full-blown zillion-bit privacy here.  
> Some hash functions that work are much lighter weight.
> 
> >
> I strongly disagree with this.  I would like to see any 
> documentation to the effect that this saves energy.
> 
> If there is a rare system for which it is true, then those 
> few devices could add the option.  For most devices, the 
> option SHOULD NOT be used...
> >
> We just proved otherwise -- that a good hash function 
> completely disambiguates based on IP header alone.  There is 
> no need to include payload data.

Now I am _really_ in dense mode. How would this ever work for a
'vanilla' IPv6 header? Which header fields would distinguish subsequent
packets coming from the same source, sent to the same multicast group?
Payload length? Could easily be the same, if packets belong to a bulk
transfer and full MTU is exploited. Hop count? Not necessarily
different. Flow label???? What am I missing here?

Best regards,
Ronald

---

From: "Charles E. Perkins" <[email-masked]>
Date: Tue, 10 Apr 2007 15:25:22 -0700

Hello Ronald,

ext Velt, R. (Ronald) in 't wrote:
> My interpretation is that the
This is also my understanding.
> but have the same source address and multicast destination address.
Well, maybe, but only if the taggers are operating independently of each 
other.
But, as noted in an earlier e-mail, it has the effect also of disabling 
duplicate
suppression for packets that ought to be the same.  I wonder which is the
more frequent effect.
> be indistinguishable for DPD, leading to incorrect discarding.
>   
So for this case, tagger-ID enables nodes to avoid incorrect discarding,
whereas for the other case tagger-ID disables duplicate suppression, unless
the taggers are cooperating with each other.  But then we don't need 
tagger-ID.
I'm not sure which is worse.  Losing some broadcasts because of
collision in DPD option space would resemble the effects of unreliable
broadcast over the wireless medium.  Propagating unwanted duplicates
would congest the network.  It surely depends on which bad thing
happens more often.  I wonder if there has been a study of this effect.

> 'vanilla' IPv6 header?

You are right.  I was forgetting about the this case when I said that
payload was not needed.  But I already agreed that the DPD option
would be useful for cases where the hash function did not uniquely
identify different broadcasts.

Regards,
Charlie P.

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Tue, 10 Apr 2007 22:26:14 -0700

Hi Charlie, Ian, 

> Sent: Tuesday, April 10, 2007 8:33 AM
> To: ext Ian Chakeres
> Cc: [email-masked]

My understanding is that the DPD would need to be extended to
consistently use the same tagger, if multiple gateways were tagging.
That is, if there are two gateways A and B tagging the same packet and
injecting it into SMF, the DPD would need to pick packets from one of
these gateways and discard packets from the other, for a given
source/destination pair, to suppress unwanted duplicates.  I think this
is explained in section 5.2.1 of the current draft.

> disambiguates based on IP header alone.  There is no need to

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.  

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.

Regards,
Tom

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 11 Apr 2007 14:18:18 -0700

Hello Tom,

> inexpensive, a hash on the packet would be preferable to the tagger ID
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.

I'll also try to get a count of the instruction cycles needed.

> 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.

Regards,
Charlie P.

---

From: David Young <[email-masked]>
Date: Wed, 11 Apr 2007 18:28:36 -0500

> inexpensive, a hash on the packet would be preferable to the tagger ID

Ian, Tom, and Charlie,

I cannot tell whether or not you each mean the same thing when you say
a hash is "heavyweight."  I took Ian to mean system resources such as
CPU and bus/memory bandwidth---that is, a heavyweight hash reduces total
system performance.  Charlie is concerned with how fast the device draws
down its battery.  I am concerned with the total system performance,
and I will say a bit about that.

I expect that some MANET routers will be portable devices containing an
ARM CPU with a modest data cache size.  Let us say the cache size is 8kB.
If you are forwarding 1kB multicast packets, and the CPU hashes each
packet payload for the purpose of duplicate detection, then the rate of
cache turnover as you compute the hash function over every byte of every
packet is potentially very high (up to 1/8th of your cache per packet).
The danger is that the operating system and applications (MP3 player,
telephone, photo/movie display, web browser) slow tremendously as they
get kicked out of the cache by multicast traffic.

[Contrast that with the usual unicast forwarding case: provided that the
 NIC has verified the IP checksum (not too unusual, these days), the CPU
 need only read the IP header of any packet to make a forwarding decision,
 so the cache impact is small.]

Incidentally, some ARM "systems on a chip" have coprocessors for CRC32.
Will comparison of CRC32s suffice to detect duplicates?

Dave

-- 
David Young             OJC Technologies
[email-masked]      Urbana, IL * (217) 278-3933

---

From: "Ian Chakeres" <[email-masked]>
Date: Thu, 12 Apr 2007 17:43:12 +0530

David,

The current SMF document describes a simple DPD procedure that is very
lightweight in terms of CPU, state, energy, etc. I think it should be
preferred over other DPD mechanisms, e.g. hashing.

Ian

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 12 Apr 2007 09:23:37 -0700

Hello David,

As you point out, minimizing system impact for
DPD is not a simple, one-dimensional problem.
The new option would require fewer instruction
cycles, but more radio transmission power.
If the processing time is faster than the time it
takes to send data over the air, then I am
wondering how the cache problem you describe
would affect performance.  Sending a byte over
the air at 1 Mb/sec would take 10 microseconds,
and a lot of processors can do numerous
instructions in that amount of time.  This means
that sending extra bytes could be a losing
strategy time-wise, even separate from the
energy considerations.

It seems to me that the very systems that would
have limited cache space would be the ones most
likely to benefit from energy conservation by way
of packet size reduction.

Moreover, I believe this imbalance will only
increase in the future. We can expect to see more
years of reduced feature size in chips, and thus
reduced energy expenditure for processing.  We
will always have to have a certain amount of energy
to push radio waves over the air, and can only hope
for more efficiency in the circuitry for transmission
and reception.

I do not know yet whether CRC32 will suffice for
the purpose of good hashing.  Most likely, we will
have a choice between almost perfect hashing
that is relatively expensive in processing (but still
far less energy expensive than radio transmission)
vs. pretty darned good hashing that is a lot less
expensive in processing requirement.

We need more data.  But I would not have brought
it up in the first place except for my understanding
that a bit over the air can be literally millions of times
more expensive than a processor cycle, in terms of
energy cost.  From this perspective, throwing in
another 32-bit field needs a lot of justification before
it can be accepted by designers of, say, sensor
networks.

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 12 Apr 2007 09:28:31 -0700

Hello Ian,

> preferred over other DPD mechanisms, e.g. hashing.

I don't think so.  I reckon the DPD mechanism will be
more expensive in terms of energy and, sometimes,
time required for processing.  In fact, in most cases,
the energy imbalance might be drastically worse for
more bytes over the air.  The CPU state requirement
could be relatively small -- e.g, 24 bits per recent
packet.  This is a matter to be settled, but I do not see
it as a large burden, even for systems saving dozens of
recent hash results.

Regards,
Charlie P.

---

From: "Ian Chakeres" <[email-masked]>
Date: Fri, 13 Apr 2007 13:37:31 +0530

Let me simply respond regarding IPv4 packets.

A - DPD based on IPID

There is no additional packet overhead (when the source inserts a
sequence number into the IPID field as specified in the SMF document).
On the DPD detection side, a node need only keep a sequence number and
window (for a particular tuple). I believe this is extremely light
weight.

B - Hashing

For comparison, hashing would require a unique ID in the packets - so
no additional overhead here. On the DPD detection side, nodes need to
perform the hash, for every packet including duplicates. They must
also maintain the previous hashes for comparison. Finally the hash &
past hashes need to be compared to detect duplicates.

I think procedure B is much heavier weight in terms of state, CPU, etc
than procedure A. If you disagree please explain.

Ian

---

From: Teco Boot <[email-masked]>
Date: Fri, 13 Apr 2007 11:07:04 +0200

On hashing; this introduces a new requirement: sent packets shall be unique.
This requirement could be hard to fulfill, for example there could be
keep-alive packets without sequence numbers or other unique field and there
could be retransmits of the same packet. Many IETF protocols behave this
way, so why asking upper layer applications to do otherwise?

Question on IPv4 / IPID and the tagger functionality: I don't understand
when using IPv6 there is a valid reason to use the tagger option and when
using IPv4 / IPID lack of the tagger option is acceptable. I think we need a
better analysis why and when the tagger is needed and we could look for
alternative solutions.

Teco
 
> From: Ian Chakeres [mailto:[email-masked]]
> Sent: vrijdag 13 april 2007 10:08
> To: Charles E. Perkins
> Cc: manet

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 25 Apr 2007 10:41:36 -0700

Hello Ian,

ext Ian Chakeres wrote:
> window (for a particular tuple). I believe this is extremely light weight.
For IPv4, I am very happy to use the IP_ID field without any
additional hashing, along with the source IP address.  Do we
have agreement this is O.K.?

With this agreement, then we would only specify hashing
for use with IPv6.  I only mentioned IPv4 because I was
under the impression that some people did not think the IP_ID
field was sufficient for the task.

Regards,
Charlie P.

---

From: "Joe Macker" <[email-masked]>
Date: Thu, 26 Apr 2007 12:20:20 -0400

While we collected previous data with a variety of hash algorithms a few
years ago and looked at high rate multicast traffic flows like video,etc we
were not convinced it was the right general approach. At the time, we tried
to examine a 32 bit hash result that was also a fast algorithm for
per-packet processing use.  I think we are also interested in regathering
specific data included processing/delay tradeoffs.  Certainly the text of
SMF allows for hashing approaches but SHOULDs the implementation of DPD for
IPv6.  I think this is still correct and allows for implementable
experimentation. Your IPv4 results are encouraging to hear about.

FYI, there reamin IPv6 applications that can produce very common looking
header/data portions. It may be more frequent with video streaming etc.
I've seen this with IPv6/UDP vlc streams.  IN this case its not
one-in-a-billion without additional assistance.

-Joe
>Sent: Wednesday, April 11, 2007 5:18 PM
>To: ext Henderson, Thomas R
>Cc: [email-masked]
>>> 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.
>
>> 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.
>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 26 Apr 2007 11:31:51 -0700

Hello Joe,

First, let me be clear about what I am proposing.

I am _not_ arguing against having a DPD header as an
optional protocol element.  It is even O.K. with me to
require all ad hoc nodes to implement the DPD option.

What I want, is for nodes to _typically_ rely on the
hash function to disambiguate different multicast
packets.  If the hash function does not work, then
the DPD header SHOULD be inserted into the
packet by the source.

This requires that we specify the hash function so
that the source will know whether or not the recipients
can disambiguate based on the hash function.

For IPv4, the sense of the recent discussion seems to
be that we do not need DPD header or hash functions
at all, because the IP_ID field will disambiguate.  This
seems like the best possible solution to me.

For IPv6, it matters, and I am by now pretty confident
that the hash function will work at least 99.9999%
of the time if not 99.99999999% of the time.  For
the times when it works, we save energy and maybe
even time (depending on the transmission rate).  For
the time when hashing does not work, we would
have the DPD header.

If you have datasets that MD5 cannot disambiguate,
I'd love to see them.  As far as I can tell, even
changing one single bit causes the hash results to be
different.  One has to search long and hard to find
two input strings that have the same results, or
else be an expert cryptographer with insights about
recent publications showing the weakness of MD5
against determined adversaries.

Regards,
Charlie P.

---

From: "Joe Macker" <[email-masked]>
Date: Thu, 26 Apr 2007 17:07:11 -0400

I think I understand you.  I think there is more to it than that and there
are several issues. Let me try to outline my issues.  I am very much a fan
of keeping the specification flexible to allow hashing experimentation.
Hopefully the folling clarifies some issues.  I think we agree IPv4 approach
is good enough for now so this is also about IPv6

(1) Ambiguity of hash results
 - I think we agree given a good data set this can be made very improbable.
No argument.
 - Changing 1 bit is very good for a good hash algorithm.  No argument. Hash
algorithms should be well-balanced. 
 - However, if we sample part or all of the packet (these may fast flows,
video) there is a chance an application may produce a same in parts or
possible completely the same packet (UDP IPv6 without RTP in vlc video
stream for example).
 - Is this disallowed for an application ever to do this?  I know the hybrid
approach (3) deals with this.

(2) Heterogeneity of Flows at Forwarder and History Management
 - SMF is forwarding multiple flows possible from the same source or
heterogeneous sources.  These flows can arrive at orders of magnitude
different rates (e.g., Video vs. chat).
 - a present SMF DPD tuple-based bitmap "sliding window implementation" is
pretty efficient straightforward engineering approach to handle this, deals
with out of order packets properly, and will not swamp out a slower flows
due to queue history management problems by one source-receiver flow
dominating the DPD queue. 
 - This is the same code as IPv4 code so its not like something different is
done.
 - With the monolithic hashing approach for all packets will it be a
homogeneous FIFO for all packets,etc.? Timeout per packet?
 - Or will we use a hash for the flow and a hash for the DPD.
 - I am open to discussion on this. 

(3) The Hybrid Approach to detect (1) and only add DPD in .00000001% of time
;-) as you put it is allowed but I am still concerned about (2).

Please don't get me wrong I agree hashing approaches are relatively fast and
feel they adding great value to IP flow analysis tools,etc.  I know it can
run fast so that is not my engineering concern and perhaps the older SMF
text needs updating in that regard. It feel managing the tuple-based DPD
histories is important in a heterogeneous environment. It can be harder to
test and check this.

-Joe

>Sent: Thursday, April 26, 2007 2:32 PM
>To: ext Joe Macker
>Cc: 'ext Henderson, Thomas R'; [email-masked]
>I am _not_ arguing against having a DPD header as an optional 
>protocol element.  It is even O.K. with me to require all ad 
>hoc nodes to implement the DPD option.
>
>What I want, is for nodes to _typically_ rely on the hash 
>function to disambiguate different multicast packets.  If the 
>hash function does not work, then the DPD header SHOULD be 
>inserted into the packet by the source.
>
>This requires that we specify the hash function so that the 
>source will know whether or not the recipients can 
>disambiguate based on the hash function.
>
>For IPv4, the sense of the recent discussion seems to be that 
>we do not need DPD header or hash functions at all, because 
>the IP_ID field will disambiguate.  This seems like the best 
>possible solution to me.
>
>For IPv6, it matters, and I am by now pretty confident that 
>the hash function will work at least 99.9999% of the time if 
>not 99.99999999% of the time.  For the times when it works, we 
>save energy and maybe even time (depending on the transmission 
>rate).  For the time when hashing does not work, we would have 
>the DPD header.
>
>If you have datasets that MD5 cannot disambiguate, I'd love to 
>see them.  As far as I can tell, even changing one single bit 
>causes the hash results to be different.  One has to search 
>long and hard to find two input strings that have the same 
>results, or else be an expert cryptographer with insights 
>about recent publications showing the weakness of MD5 against 
>determined adversaries.
>
>Regards,
>Charlie P.
>
>
>ext Joe Macker wrote:
>> While we collected previous data with a variety of hash algorithms a 
>> few years ago and looked at high rate multicast traffic flows like 
>> video,etc we were not convinced it was the right general 
>approach. At 
>> the time, we tried to examine a 32 bit hash result that was also a 
>> fast algorithm for per-packet processing use.  I think we are also 
>> interested in regathering specific data included processing/delay 
>> tradeoffs.  Certainly the text of SMF allows for hashing approaches 
>> but SHOULDs the implementation of DPD for IPv6.  I think 
>this is still 
>> correct and allows for implementable experimentation. Your 
>IPv4 results are encouraging to hear about.
>>
>> FYI, there reamin IPv6 applications that can produce very common 
>> looking header/data portions. It may be more frequent with 
>video streaming etc.
>>> 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.
>>>
>>> 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.
>>>
>>> Regards,
>>> Charlie P.
>>>
>>>
>>>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 26 Apr 2007 17:22:00 -0700

Hello Joe,

I don't understand a couple of things that you said:

>  - I think we agree given a good data set this can be made very improbable.
I'm saying, given practically any two different data sets, the
has results will differ. 
> algorithms should be well-balanced.
This, I did not understand...
> possible completely the same packet (UDP IPv6 without RTP in vlc video
For any such scenario, the DPD header could be applied.

> approach (3) deals with this.
I did not understand the questoin, unfortunately.  I do not
think that the application would insert the DPD header, or
calculate the hash.
> dominating the DPD queue.
If you wanted to specify that, after a certain high rate
of packet sourcing, a node SHOULD begin to insert
DPD options, that would be fine with me.  For sensor
nodes, I don't see this happening very often.
> homogeneous FIFO for all packets,etc.? Timeout per packet?
I was thinking about a single list of hash results for single
packets, but if you believe there should be multiple lists
we could work on that...(?)
>  - Or will we use a hash for the flow and a hash for the DPD.
I did not understand this...
> ;-) as you put it is allowed but I am still concerned about (2).
(2) basically means too many packets will cause the loss of hash
results for packets that are still actively being forwarded, if I
understand correctly.
> feel they adding great value to IP flow analysis tools,etc.
But we are discussing DPD, not flow analysis...(?)

Sorry if I am missing something obvious!

Regards,
Charlie P.

---

From: Teco Boot <[email-masked]>
Date: Fri, 27 Apr 2007 10:26:18 +0200

Hi Joe, Charlie,

I still don't feel comfortable with IPv4 IP header DPD testing.
RFC791 needs an update for enforcing unique headers specifying a node SHOULD
use IP Identification, even if the don't fragment bit is set.

I monitored some traffic on my XP laptop, sending multicast looks OK. But
for unicast, I received multiple copies of exactly the same IP header
(checksum is same for all packets), for different sessions. I think it is
not that difficult to find traffic with identical first 64 bytes for
different packets. For example, I received TCP ACK frames with ID set on
zeros. In combination with packet loss, the duplicate packet is needed by
TCP. In theory, the problem is the same with reliable multicast and there
could be systems out there having the problem.

I mentioned earlier DPD would be a nice mechanism for dampening ping-ponged
packets during a routing loop. And providing support for fragmentation
should not be that difficult.

I still think IPv4 and IPv6 specific drafts for DPD would be helpful. The
drafts would describe the mechanism for unicast and multicast. SMF DPD text
can be used as a start and SMF could reference to the 2 drafts. The DPD
drafts would become Standards Track RFCs. And the IPv4 RFC would update
RFC791.

Regards, Teco

> Sent: vrijdag 27 april 2007 2:22
> To: ext Joe Macker
> Cc: [email-masked]

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 27 Apr 2007 07:21:59 -0700

Hello Teco,

> use IP Identification, even if the don't fragment bit is set.
I think this means that any method for suppressing duplicates specified
in the [manet] working group should be slated for a standards-track
document.  I agree with this.
> drafts would become Standards Track RFCs. And the IPv4 RFC would update
But any standards track document for duplicate suppression could
be interpreted as updating RFC 791.  Getting support for a new
IP option for IPv4 is going to be monstrously difficult.  We tried
this many years ago for Mobile IP and it was already too difficult.
Requiring a new protocol (i.e., not a new option) for this would
be almost humorously difficult.  Where would the DPD option go?
And why would we imagine it to be easier for source nodes to
implement than the IP_ID management (which is trivial)?  If the
DPD option is only for gateways, then there is still the difficulty
to enable IPv4 nodes receiving the packet correctly.

I think the situation for IPv6 is a lot better, but from a technical
standpoint still tilted mostly towards avoiding requiring the
transmission of extra header bytes.

By the way, having multiple tagger IDs is a detrimental factor
that could affect header compression designs.

Regards,
Charlie P.

---

From: "Joe Macker" <[email-masked]>
Date: Fri, 27 Apr 2007 10:55:07 -0400

I want to make it clear that for IPv4 multicast the SMF prototype
implementation can override the ID field to properly sequence it?  The
present prototype code support deterministic ID field updating for source
multicast traffic.  The use of ID fields is known to not be uniformly
implemented across OSes and it is well known there are problems. So even if
one chose to do hashing for IPv4 this is important and you might want to use
it.  Other IETF groups like ROHC have described this as well.  Why you may
have interest we don't mess with unicast in SMF so that may warrant a
separate discussion.  We've contemplated writing a separate DPD IPv4
document that would provide a more robust method, but I am fan of leaving
this out for the EXP SMF submission and gaining more experience.

If there is interest in generalizing DPD for unicast as well we should have
a separate thread since that is a new topic.

>From: Teco Boot [mailto:[email-masked]] 
>Sent: Friday, April 27, 2007 4:26 AM
>To: 'Charles E. Perkins'; 'ext Joe Macker'
>Cc: [email-masked]
>Subject: RE: [manet] Need for DPD header (SMF document discussion)
>
>Hi Joe, Charlie,
>
>RFC791 needs an update for enforcing unique headers specifying 
>a node SHOULD use IP Identification, even if the don't 
>fragment bit is set.
>
>I monitored some traffic on my XP laptop, sending multicast 
>looks OK. But for unicast, I received multiple copies of 
>exactly the same IP header (checksum is same for all packets), 
>for different sessions. I think it is not that difficult to 
>find traffic with identical first 64 bytes for different 
>packets. For example, I received TCP ACK frames with ID set on 
>zeros. In combination with packet loss, the duplicate packet 
>is needed by TCP. In theory, the problem is the same with 
>reliable multicast and there could be systems out there having 
>the problem.
>
>I mentioned earlier DPD would be a nice mechanism for 
>dampening ping-ponged packets during a routing loop. And 
>providing support for fragmentation should not be that difficult.
>
>I still think IPv4 and IPv6 specific drafts for DPD would be 
>helpful. The drafts would describe the mechanism for unicast 
>and multicast. SMF DPD text can be used as a start and SMF 
>could reference to the 2 drafts. The DPD drafts would become 
>Standards Track RFCs. And the IPv4 RFC would update RFC791.
>
>Regards, Teco
>
>
>> I'm saying, given practically any two different data sets, the has 
>> results will differ.
>> >  - Changing 1 bit is very good for a good hash algorithm.  
>No argument.
>> Hash
>> > video) there is a chance an application may produce a same 
>in parts 
>> > or possible completely the same packet (UDP IPv6 without 
>RTP in vlc 
>> > video stream for example).
>> >
>> >  - Is this disallowed for an application ever to do this?  I know 
>> > the
>> hybrid
>think that 
>> the application would insert the DPD header, or calculate the hash.
>> > heterogeneous sources.  These flows can arrive at orders of 
>> > magnitude different rates (e.g., Video vs. chat).
>> >  - a present SMF DPD tuple-based bitmap "sliding window 
>implementation"
>> is
>> > pretty efficient straightforward engineering approach to handle 
>> > this,
>> deals
>> If you wanted to specify that, after a certain high rate of packet 
>> sourcing, a node SHOULD begin to insert DPD options, that would be 
>> fine with me.  For sensor nodes, I don't see this happening very 
>> often.
>> I was thinking about a single list of hash results for 
>single packets, 
>> but if you believe there should be multiple lists we could work on 
>> that...(?)
>> > (3) The Hybrid Approach to detect (1) and only add DPD in 
>.00000001% 
>> > of
>> time
>> > Please don't get me wrong I agree hashing approaches are 
>relatively 
>> > fast
>> and

---

From: Teco Boot <[email-masked]>
Date: Fri, 27 Apr 2007 16:53:21 +0200

Hi Charlie,

I do not propose a new IPv4 header option. I propose better specification of
usage of the Identification field. It would be a smooth update / upgrade. It
could take a long term migration. Nodes that do not fill in the Id field as
required by DPD would have their packets dropped in the MANET. I doubt if
this is a large problem, nowadays there is no "connected" MANET which means
no connectivity at all.

For IPv6 headers, there is nothing available for making packets unique. So
we need the DPD option. Doable, but IMHO more difficult than IPv4. For
example, we could introduce a trigger start sending packets with the DPD
option on the source.

With DPD option, header compression algorithm is somewhat more complex. But
I don't see big problems. And it should not add BW requirements, assuming
sequenced Ids and an extension on some RFCs implemented.

First focus on finishing SMF as experimental and then start the real DPD
stuff going as STD?

Regards, Teco

> Sent: vrijdag 27 april 2007 16:22
> To: ext Teco Boot
> Cc: [email-masked]

---

From: "Joe Macker" <[email-masked]>
Date: Fri, 27 Apr 2007 11:09:48 -0400

>Sent: Thursday, April 26, 2007 8:22 PM
>To: ext Joe Macker
>Cc: [email-masked]

Right we agree assuming certain conditions: length of sample set and quality
and length of hash result.
We agree this is feasible with different data sets.

>>  - Changing 1 bit is very good for a good hash algorithm.  No 
>> argument. Hash algorithms should be well-balanced.
>>   
We agree. You said changing even 1 bit produced a different hash. Of course
that is true as a property of a good hash algorithm.

>in parts or 
>>  - Is this disallowed for an application ever to do this?  I 
>know the 
>> hybrid approach (3) deals with this.
>>   
We are saying the same thing here. 

>> implementation" is pretty efficient straightforward engineering 
>> approach to handle this, deals with out of order packets 
>properly, and 
>> will not swamp out a slower flows due to queue history management 
>> problems by one source-receiver flow dominating the DPD queue.
>>   
>If you wanted to specify that, after a certain high rate of 
>packet sourcing, a node SHOULD begin to insert DPD options, 
>that would be fine with me.  For sensor nodes, I don't see 
>this happening very often.

I think we both I understand and I am just less convinced until I see an
implementation experimented with lots of heterogeneous flows.

>>  - This is the same code as IPv4 code so its not like something 
>> different is done.
>packets, but if you believe there should be multiple lists we 
>could work on that...(?)

Right that is my point. I am less convinced a single list is good.  You
realize we are keeping very little state on individual packets (1 bit) and
can implement a sliding window per tuple?

>I did not understand this...

Same as above just pointing out potential for multiple lists...but I don't
see an advantage over tuple-based.

>(2) basically means too many packets will cause the loss of 
>hash results for packets that are still actively being 
>forwarded, if I understand correctly.

Yes, that is a concern.  Remember this is about envisioning a larger set of
heterogeneous forwarders and how stale entries  will be purged,etc.  We
borrowed some of your previous thoughts here on how to control purging the
data.  Each node is potentially handling very different data sets at
different rates and potentially varying sources/destination.  I think we
need to further experiment with issues in this regard in maanging the DPD.

>> Please don't get me wrong I agree hashing approaches are relatively 
>> fast and feel they adding great value to IP flow analysis tools,etc.

---

From: "Templin, Fred L" <[email-masked]>
Date: Fri, 27 Apr 2007 08:53:41 -0700

Teco,

> usage of the Identification field.

Although I agree that the network cannot currently rely on
the ip_id field to contribute uniqueness information for DPD,
the setting of ip_id is an end-to-end consideration between
the source and destination(s). So, it would be unreasonable
to mandate a specific behavior that a source host must use
(e.g., monotonically-increasing) strictly for the purpose
of being friendly to network middleboxes.

Fred
[email-masked]

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 27 Apr 2007 09:12:38 -0700

Hello Joe,

Thanks for the clarifications.

> and length of hash result.

My claim was specific to 64 bits of MD5 hash result.
Under those conditions, I think that practically any two
inputs will produce different hash results, regardless of
length or "quality" -- as long as they are actually
different.
> implementation experimented with lots of heterogeneous flows.

Actually, in this case I think relying on experimentation would
be unwise.  If you have some flow datasets you'd like to try,
I'd be happy to run them through and get the results.  However,
relying on empirical data using real traffic would be problematic
for two reasons:
- we already agree that the failure condition would be quite rare
- it would be very very difficult to debug in practice.

I think it is better to abstractly characterize the kind of data that
the hash function has to distinguish, and then run a few billion
test cases.

Do you have an abstract characterization of the kinds of data
you'd like to see handled properly by the hash function?

> can implement a sliding window per tuple?

More on this later...  I am wondering about it.
However, I do understand what you are saying.
>
>
> Each node is potentially handling very different data sets at

Having multiple queues of hash results is doable, but
I'm not yet persuaded that we have to go to the trouble
of actually doing it.  I think it would be better to just
require the extra DPD header for such high-volume
flows.  In this case, putting the functionality at the
gateway makes sense to me.  It seems more likely
to me that any such problem would arise as a result
of multiple downloads into the ad hoc network from
multiple points of connectivity to the Internet.
Maybe the jungle crews are watching several
different TV shows :-)

Regards,
Charlie P.

---

From: "Joe Macker" <[email-masked]>
Date: Fri, 27 Apr 2007 12:54:23 -0400

>Sent: Friday, April 27, 2007 12:13 PM
>To: ext Joe Macker
>Cc: [email-masked]
>> Right we agree assuming certain conditions: length of sample set and 
>> quality and length of hash result.
>>
>>   
>
>length or "quality" -- as long as they are actually different.
Agreed.
>> I think we both I understand and I am just less convinced 
>until I see 
>> an implementation experimented with lots of heterogeneous flows.
>>   
>
>Actually, in this case I think relying on experimentation 
>would be unwise.  If you have some flow datasets you'd like to 
>try, I'd be happy to run them through and get the results.  
>However, relying on empirical data using real traffic would be 
>problematic for two reasons:
>I think it is better to abstractly characterize the kind of 
>data that the hash function has to distinguish, and then run a 
>few billion test cases.
>

I am talking about the heterogeneity of flows and DPD purging and state
maintenance.
Some fast flows some slow flows from the samce source to different
destinations.
Lets say multicast video-over-IP and multicast chat (with keep alives,etc).

Also in the forwarding the handling of set of heterogeneous flows and
purging of old DPD data. Are you planning on maintaining additional timing
state per DPD entry, etc or just use some large FIFO list.  All these issues
are important.
----------------------------------------
Let me try to summarize you thoughts so we can move.  I think we can agree
there is a more to learn.

IPv4 approach presently is fine or you hope so as do I. It certainly has
been working in a mobile emulation testbed for many years now. For IPv6 you
are not against a DPD header to add some header variability "on demand" but
you are of the opinion that a hash list is your preferred method for the
majority of cases.

-Joe

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 27 Apr 2007 12:34:47 -0700

Hello Joe,

To put it briefly,

> you are of the opinion that a hash list is your preferred method for the

Yes.

Regards,
Charlie P.

PS. If it is the preferred method for _only me_ , and no one else on the 
mailing
       list wants to emphasize energy cost over the other 
considerations, then
       I am happy to give up the discussion!