Subject: Re: [manet] Need for DPD header (SMF document discussion) - Valid Reason for Tagger ID

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

The tagger id is needed to differentiate between taggers, in the event
that the source itself (or other ensure-ably unique path element) has
not tagged the packet. Since IPv6 requires a new option to carry the
IPID, the new option optionally includes the tagger id.

The tagger id disambiguates the ID space of different taggers.

Ian

On 4/13/07, Teco Boot <[email-masked]> wrote:
>
> 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
>
> > -----Original Message-----
> > From: Ian Chakeres [mailto:[email-masked]]
> > Sent: vrijdag 13 april 2007 10:08
> > To: Charles E. Perkins
> > Cc: manet
> > Subject: Re: [manet] Need for DPD header (SMF document discussion)
> >
> > 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
> >
> > On 4/12/07, Charles E. Perkins <[email-masked]> wrote:
> > >
> > > Hello Ian,
> > >
> > > ext Ian Chakeres wrote:
> > >
> > > > 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.
> > >
> > > 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.
> > >
> > >
> >
> > _______________________________________________
> > manet mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/manet
>
>

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

---

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

Hello Ian,

> The tagger id disambiguates the ID space of different taggers.
It is for the case of IPv6 that I am proposing we use a hash
function and relegate the use of the new option for only those
rare cases where the hash function does not properly distinguish
two different packets.

I've been doing some more testing with hash functions, and
even MD5 seems to work very, very well for this purpose,
even if one only retains 64 bits of the hash result.  Keeping
smaller hash results should help with reducing memory
requirements.

But we could keep the DPD option for IPv6 for the once
in a billion times [or even more rare!] occurrence of hash
duplication.

As another point of discussion, if a tagger encounters two
exactly identical packets, shouldn't it anyway assume that
they are duplicates and only forward one of them?  What
if two different taggers encounter the same packet?
Doesn't the tagging introduce a false difference between
the packets?

Regards,
Charlie P.

---

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

I believe your main problem with using a sequence number in the DPD
option is the consisten overhead of the option. Is that correct
Charlie?

Charlie do you have any suggestion on how we might uniformly compare
the overhead of the option (more bits, small memory, small CPU) vs.
the overhead of hashing (higher CPU, larger memory requirements, some
complexity in adding DPD sometimes, some more bits sometimes)?

Other comments inline.

> smaller hash results should help with reducing memory

Would you agree that using a sequence number could be more efficient
in terms of reducing memory requirements and CPU requirements?

> in a billion times [or even more rare!] occurrence of hash

I think for certain applications, duplicate IP packets will be
generated often. I do not want or think these should applications to
stop working when SMF DPD is used.

> Doesn't the tagging introduce a false difference between

If there are two taggers, yes they will introduce a difference
versions of the same packet - effectively creating two different
packets with different DPD options. I do not see an alternative to
stop disseminations of otherwise identical packets. If the tagger id
is not used, we can have lots of packet loss if two taggers sequence
numbers get synchronized. I believe this is much worse.

If you know of an alternative way to solve this problem, please let me know.

Ian

---

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

Hello Ian,

> option is the consisten overhead of the option. Is that correct
Yes, that is definitely my concern.
> complexity in adding DPD sometimes, some more bits sometimes)?
We can measure the energy expenditure for typical cases.
Each bit transmitted will take a certain amount of energy.
I am sure you can write the equations, and then we need to
determine the parameters:
- # of instruction cycles for hashing
- energy per bit transmitted
- energy per instruction cycle
- size of typical DPD option
- number of bytes of input data to be hashed
  (in blocks, perhaps).

I believe the number of instructions for hashing can be
made typically small enough so that the energy budget
is far smaller than for the radio transmission.

The memory requirement can be an issue, but if each hash
result is only 64 bits or 32 bits, and if we are not keeping
thousands of results around, I do not find it at all
persuasive.  Every time I turn around, prices for memory
are dropping.  Pretty soon a gigabyte of processor
memory will cost the same as your lunch.  It's already
drastically cheap for disk.

Regards,
Charlie P.

---

From: Teco Boot <[email-masked]>
Date: Fri, 27 Apr 2007 17:00:25 +0200

Small comment:
If memory is really cheap and memory lookups can be performed faster than
hash calculations, the DPD code could use packet header lookup instead of
hash lookup. Functionality is the same. Both mechanisms rely on unique
packet headers (say 1st 64 bytes or defined fields). That is what should be
specified in the standard. Which method is used for verifying duplicates is
an implementation issue.
Regards, Teco

> From: Charles E. Perkins [mailto:[email-masked]]
> Sent: vrijdag 27 april 2007 16:33
> To: ext Ian Chakeres
> Cc: manet
> Subject: Re: [manet] Need for DPD header (SMF document discussion) -
> ValidReason for Tagger ID
> 
> 
> Hello Ian,
> 
> ext Ian Chakeres wrote:

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 27 Apr 2007 08:58:02 -0700

Hello Teco,

ext Teco Boot wrote:
> hash lookup. Functionality is the same.
Check.
> Both mechanisms rely on unique
> packet headers (say 1st 64 bytes or defined fields).
The defined fields could include some amount of payload.
>  That is what should be
I think for IPv6 has also to specify which hash function
to use.  For IPv4 I am hoping we do not need a hash
function or any DPD header.

Regards,
Charlie P.