Subject: Re: [Int-area] Review: draft-ietf-intarea-ipv4-id-update-00

From: Bob Briscoe <[email-masked]>
Date: Wed, 05 May 2010 15:34:11 +0100

Joe,

At 19:46 28/04/2010, Joe Touch wrote:
>Hi, Bob,
>
>Cutting things down for brevity:
>
>Bob Briscoe wrote:
>...
> >> >> as you note, it requires
> >> >> state, particularly on a per IP-pair/protocol basis.
> >> >
> >> > If the cache doesn't store a packet count, it stores a timeout per
> >> > IP-pair/protocol anyway.
> >>
> >> It may store a timeout for each pending reassembly, but does not need to
> >> keep state once reassembly has been completed. Your suggestion of using
> >> N would require retention of that state even after reassembly.
> >
> > You seem to be implying one state per cached fragment. I'm talking about
> > one counter per IP-pair/protocol triple.
>
>You can use a counter only if you know that IDs are used in a sequence
>within a src/dst addr and protocol (which we can't know, since it isn't
>required);, if not, then you need to remember every successfully
>reassembled datagram's ID.

[BB] Does your term 'sequence' mean 'sequence in numerical order'? If 
so, I disagree.

For instance, OpenBSD uses a pseudo-random number generator to 
generate IP IDs. But the algorithm is designed not to repeat for a 
deterministic number of packets (otherwise it would be useless for reassembly).

IP ID sequences jump around so that they comply whenever a security 
policy requires a host to send unpredictable IP IDs. Otherwise it can 
be exploited to port scan another host on behalf of an attacker, 
without the attacker ever communicating with the scanned host (the 
idleScan attack).
<http://nmap.org/book/idlescan.html>

Plenty of pseudo-random number generators can jump around a 16-bit 
number space for a known number of packets without repeating: 
<http://en.wikipedia.org/wiki/Pseudorandom_number_generator#Periodicity>
For instance, the original algo used in OpenBSD went through the 
whole 2^16 number space before repeating. The OpenBSD algo has since 
been updated as vulnerabilities were found:
<http://www.packetstormsecurity.org/papers/attack/OpenBSD_DNS_Cache_Poisoning_and_Multiple_OS_Predictable_IP_ID_Vulnerability.pdf>
but it still guarantees a known minimum periodicity.

The OpenBSD algo is particularly important, because many OSs (e.g. 
MacOS X) now use it for IP ID generation.

A more trivial example is the IP IDs you see from most little-endian 
Windows machines. Viewed from a big-endian (Internet) point of view, 
they increment by 256 each packet 
<http://nmap.org/book/osdetect-methods.html#osdetect-ti>. When viewed 
on the wire, the IDs make jumps through the number space, but they 
are still guaranteed to only repeat after 2^16 packets.

> >> >> Given that, my preference is to stay with the current suggestion that
> >> >> the numbers not be reused over the expected reordering interval at the
> >> >> sender side, and leave it at that.
> >> >
> >> > I don't think Fernando's earlier question was answered fully: From the
> >> > sender's perspective what is the expected reordering interval?
> >>
> >> Expected reordering is a receiver perspective. The sender cannot know
> >> this in IP; we do not have (nor, AFAICT, can we add) a bidirectional
> >> protocol to determine this.
> >
> > The I-D says:
> > "
> >    o  >> Sources emitting non-atomic IPv4 packets SHOULD NOT repeat ID
> >       field values within a given source IP, destination IP, and
> >       protocol tuple over the period that fragment reordering would
> >       affect reassembly.
> > "
> >
> > As you say, the source doesn't know "the period that reordering would
> > affect reassembly". So this rule tells the source it musn't repeat the
> > ID within a period that it doesn't know.
> > I'm not saying we need a bidirectional protocol so the source can know
> > this period. I'm saying it cannot know, so we must not write the rule as
> > if it can.
>
>The rule is:
>
>         sources make a bet.
>
>         sources pay the price for making the bet wrong.

[BB] BTW, both src & dst pay the price of misassociation - they want 
to communicate but cannot.

>It doesn't say how sources know how to make the bet; on this we agree.
>Right now, the bet is blind based on how fast it wants to transmit. I'm
>saying that "if the source has some better idea of expected reordering -
>which it can get only out of band, it can use that to recycle IDs for
>fragmentation".
>
>Would that be a better way of saying it?

[BB] If you start from the premise that you want to constrain 
fragmentation based on time-related concepts (packet rate and 
lifetime) I certainly agree that this is the best way you can say it 
(altho I assume this isn't the wording you are proposing for the doc).

But I don't believe we should start from that time-related premise, 
for two reasons:
- it's not the way IP implementations have been written
- it leads us to set impractical rules for these implementations (blind bets)

This is why I say that the I-D should state the following:
Rule 1: the source does not repeat an IP ID within N packets (rather 
than a certain time).
Rule 2: the receiver can then know not to hold a cached fragment 
after (say) N/2 packets have arrived within the relevant 3-tuple (by 
assuming packet loss is not more than 50%).

I know that earlier you said:
>Using any other N would be a new requirement that would be impossible to
>impose.

[BB] ...Yes a new req, but No, not impossible - IMHO more possible 
than the new requirement in the I-D.

For the src, limiting N will be more feasible than imposing packet 
lifetimes, because it's what all source implementations (except buggy 
ones) actually do. Whereas AFAIK no src implementation does anything 
about repeating the ID within *any* period of time (whether packet 
lifetime or re-ordering duration), even tho RFC791 says they should 
do the former.

Whether we take your approach or mine, we both change the rules for 
src & dst. So neither of us can claim existing implementations will 
comply already. So I suggest we should at least add rule changes that 
will work (without needing bets or out of band channels).

The whole reason we have a problem is because RFC791 introduced time 
into the constraints. But it was inappropriate, and no-one used it. 
The I-D tries to correct that by shortening the length of that time. 
I think the solution is to remove time altogether. When in a hole, 
stop digging.

>FWIW, we could have done this much better, as follows (all arithmetic
>modulo 4):
>
>Consider 4 regions of ID (00*, 01*, 10*, 11*)

Are these mod 4 or mod 2^16?

>fragtop points to the highest ID region you're currently reassembling
>
>fragnew is the ID of the incoming first fragment (MF=1, offset=0)
>
>if fragnew > fragtop
>         fragtop = fragnew
>         flush(fragnew+1)  /* drop all fragments one region higher */
>
>
>This could use the ID to determine when the receiver can flush old
>fragments based on when it sees new IDs. I can't make it work with only
>2 regions, though - it needs 3 AFAICT (and 4 is easier to implement).
>
>However, it assumes that:
>
>         - with a src/dst/proto,
>         IDs in region X are exhausted before region X+1 is used

I assume this is a thought experiment... but surely we cannot take 
this further as it would require mandating that IP ID generation in 
the majority of operating systems including Windows & MacOS X (see 
earlier) must change to comply with this new definition of what is 
right in IPv4.

>         - a counter (fragtop) is maintained for each src/adr/proto tuple
>         currently reassembling
>
>         - the above is done at the speed of fragments arriving
>
>Although this is interesting academically, it also opens an opportunity
>for a DOS attack, i.e., with a single fragment I can flush your reassy
>cache, so I don't see it flying even IF it were feasible to require.

Perhaps the point behind my proposal has been missed: To be robust, 
reassembly code should count how many packets have arrived 
*irrespective* of the values in the IP ID of those packets. I'm sure 
this doesn't make it invulnerable to all DoS attacks, but at least it 
makes it invulnerable to blind DoS attacks using particular IP ID values.

>----
>
>The upshot is that I think the doc should focus on:
>
>         a) the ID having no meaning when the packet is atomic

Certainly.

>         b) sources avoiding sending non-atomic packets

Certainly

>         (perhaps focusing on "sources that want to run over 10 Mbps"?)

I hope I have explained why times and rates don't need to be and 
shouldn't be relevant.

>         c) sources that do want to fragment and do run over 10 Mbps
>         are taking a risk that they may ultimately pay for,
>         so the onus is on them to figure out what is safe
>         (even if that means out of band means)

I hope I have given an approach that would just work, without 
creating any difficult dilemmas for hosts.

Cheers

Bob

PS: In cutting down the thread earlier, the second of my two points 
has been lost without resolution. (I don't believe we should say "the 
ID MUST be ignored except for reassembly".)
I'll re-post it once we've resolved this first point.
And I still have to post my full review of the text once we've 
resolved these 2 conceptual points.

>Joe

________________________________________________________________
Bob Briscoe,                                BT Innovate & Design

---

From: Joe Touch <[email-masked]>
Date: Wed, 05 May 2010 08:46:46 -0700

Bob,

Popping this up a level, you conclude with:

> *irrespective* of the values in the IP ID of those packets.

When do you stop counting? I've been presuming you see a src/dst/prot/ID
repeat, but the ID might not repeat as needed to avoid incorrect
fragmentation:

	a) you can't distinguish between valid repeats and duplicates
	spaced out due to other network effects, so you could guess
	very low
	
	b) you may need to keep a LOT of IDs to know when they repeat
		- if you just pick one, and the next time it comes
		it's lost, you guess high and could reassemble
		incorrectly

		- if you just pick one, and the source randomizes over
		all destinations, it might repeat other IDs to you
		before it repeats the one you're tracking

This is why I assumed you were keeping a copy of all the IDs, or assumed
they came in sequence. If you do neither, it creates problems. However,
it's not feasible to do either.

So I understand the *desire* to use some externally observable event to
determine when the reassembly interval at the receiver, but I don't see
how it's feasible at all.

Joe

-----------------------------

> Are these mod 4 or mod 2^16?

I was presuming we were looking at the high-order bits.

> I assume this is a thought experiment... but surely we cannot take this
> further as it would require mandating that IP ID generation in the
> majority of operating systems including Windows & MacOS X (see earlier)
> must change to comply with this new definition of what is right in IPv4.

Right - but, AFAICT, that's not more of an imposition than what you're
suggesting.

If we change the rules for how IP IDs are interpreted (or not), we can
as easily (or not) change the rules for how they are generated.

However, I put it forth as a reason why *neither* is useful.

---

---

From: Bob Briscoe <[email-masked]>
Date: Mon, 24 May 2010 20:00:07 +0100

Joe,

inline...

>                 it's lost, you guess high and could reassemble

[BB] I've been trying to unpick your questions without success. This 
says to me that you might be thinking I'm proposing something 
different to what I am, so I've tried to lay it out clearly below.

If you don't understand my text below either, I think it would be 
best if we talked offline, then come back to the list to summarise 
our discussion.

>                 before it repeats the one you're tracking

[BB] The receiving behaviour I'm proposing will not work if the 
source is randomising over all destinations. However, this is not how 
RFC791 said the source should do it. So I'm assuming we cannot cater 
for noncompliant implementations (quoting back your own words earlier 
in this thread).

I admit there are a lot of source implementations that have contained 
this particular non-compliance for a very long time, so we (the w-g) 
may want to make an exception for them. But my working assumption for 
this conversation is that we cannot cater for non-compliant sources, 
even if the receiver cannot tell it is talking to a broken source.

>how it's feasible at all.

[BB] Here's the way I'm thinking a receiver could do fragment caching 
& reassembly. Apologies in advance for all the bugs there are bound 
to be in the pointer syntax of my pseudocode, but I hope it's good 
enough to 'get it'.

The receiver maintains two different indexes into its fragment 
reassembly cache:
1/ fragMatchTable (per src-dst-dscp) hash table to look up IPv4 ID 
and return an array containing a pair of pointers for each fragment 
cached against that ID
   i) a pointer to the fragment itself
   ii) a pointer to the fragment's entry in fragCountTable
2/ fragCountTable (per src-dst-dscp) doubly linked list of pointers 
to all the outstanding cached fragments in arrival order 
(irrespective of their ID). Each entry in the list is a structure 
that contains:
- pointers to the fragments that arrived before & after ('next' & 'previous')
- a pointer to the entry in fragMatchTable for the fragment cached at 
that position
- a count 'count' of how many distinct IDs arrived between the 
previous fragment in the list and this one

In addition to this linked list, fragCountTable contains
- pointers to the oldest & newest entries in the list
- a count ('totalCount') of how many distinct IDs arrived between the 
oldest fragment and the latest arrival

Whenever a fragment (or whole packet) arrives, if there are cached 
fragments stored against its src-dst-dscp, the receiver runs the 
following pseudocode to garbage-collect fragments that arrived more 
than N packets ago:

while (totalCount > N) {   /* N is max count of distinct IDs allowed */
     /* garbageCollect along the linked list from oldest entry */
     *nextOldestFrag = oldestFrag->next    /* temp pointer to next oldest */
     garbage(oldestFrag)       /* Remove oldest fragment from both tables */
     totalCount -= nextOldestFrag->count   /*Reduce totalCount accordingly*/
     oldestFrag = nextOldestFrag           /* update oldest frag pointer  */
}

Having done the above garbage collection, only fragments that arrived 
less than N packets ago will be in the cache, so it can 
lookupFragMatchTable(ID), knowing that if it finds a match it will be 
sufficiently fresh to be used.

*frag = lookupFragMatchTable(ID)
if (*frag == NULL) {       /* no frag cached against this ID */
     totalCount++
     newestFrag->count++

     /* Code not shown for adding a new entry in the cache ...
      */

} else {                   /* a frag is already cached against this ID */

/* Code not shown for matching the ID with existing fragment(s).
  * Whenever a fragment is reassembled, the cached fragment is removed
  * from both tables and the entries either side in the doubly linked list
  * are updated to heal over the gap and to add the removed 'count' to the
  * 'count' in the next position.
  */

}

more...

[BB] [snip]

>Right - but, AFAICT, that's not more of an imposition than what you're

[BB] Mine is not an imposition. That's my point.

Your thought experiment:
Requires changing the sender and the receiver, so neither will work 
with legacy.

My rough idea:
Source unchanged. Legacy receivers continue to work with risk of 
misassociation as today. But a receiver can be updated to be sure it 
will never misassociate.

...except with a non-compliant source, whether broken, buggy or 
malicious - but no-one can assure correct association in these cases.

>However, I put it forth as a reason why *neither* is useful.

Am I deluded or am I helping?

Bob

---

From: Joe Touch <[email-masked]>
Date: Mon, 24 May 2010 12:53:32 -0700

Hi, Bob,

Bob Briscoe wrote:
> says to me that you might be thinking I'm proposing something different
> to what I am, so I've tried to lay it out clearly below.
> 
> If you don't understand my text below either, I think it would be best
> if we talked offline, then come back to the list to summarise our
> discussion.
> 
> 
> [BB] The receiving behaviour I'm proposing will not work if the source
> is randomising over all destinations. However, this is not how RFC791
> said the source should do it. So I'm assuming we cannot cater for
> noncompliant implementations (quoting back your own words earlier in
> this thread).

RFC791 says that the ID must be unique per src/dst/proto:

---
                                ... The originating protocol module of
    an internet datagram sets the identification field to a value that
    must be unique for that source-destination pair and protocol for the
    time the datagram will be active in the internet system. ...

---

The problem is that we don't know anything else for sure.

> this particular non-compliance for a very long time, so we (the w-g) may
> want to make an exception for them. But my working assumption for this
> conversation is that we cannot cater for non-compliant sources, even if
> the receiver cannot tell it is talking to a broken source.

All sources that go over 6.4 Mbps for 1500 byte MTUs are noncompliant by
reusing the IDs. Excepting sensors, PDAs, and cellphones, that's most of
the other devices on the Internet AFAICT.

However, that's not the real issue -- see below.

> [BB] Here's the way I'm thinking a receiver could do fragment caching &
> reassembly. Apologies in advance for all the bugs there are bound to be
> in the pointer syntax of my pseudocode, but I hope it's good enough to
> 'get it'.
> 
> 1/ fragMatchTable (per src-dst-dscp) hash table to look up IPv4 ID and
> return an array containing a pair of pointers for each fragment cached
> against that ID
> 2/ fragCountTable (per src-dst-dscp) doubly linked list of pointers to
> all the outstanding cached fragments in arrival order (irrespective of
> their ID). Each entry in the list is a structure that contains:
> - a count 'count' of how many distinct IDs arrived between the previous
> fragment in the list and this one

How do you keep that information without keeping a list of those IDs?

(and it needs such a list for each src/dst/proto triple -- this is where
I think the state blows up)

Keep in mind, you need to keep ALL the IDs - not just those you're
reassembling (they might not be fragmented). And you need to keep them
even after they're reassembled too.

> following pseudocode to garbage-collect fragments that arrived more than
> N packets ago:
> 
> Requires changing the sender and the receiver, so neither will work with
> legacy.
> 
> My rough idea:

See above. I think I have pointed out the specific place where the state
in yours is untenable.

Joe

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 25 May 2010 10:00:16 +0100

Joe,

See 3 responsees inline marked '[BB2]'...

>The problem is that we don't know anything else for sure.

[BB2] Well, we don't even *know* this. This is all that has been 
standardised, but we know it's not what exists.

 From all the research done to look at packet streams and identify 
which OS is generating the ID sequence, I believe we can ascertain 
that even the randomised ones guarantee not to repeat within a 
certain number of packets (see links provided earlier in thread).

> > in the pointer syntax of my pseudocode, but I hope it's good enough to

[BB2] BTW, my brain farted below:
s/src-dst-dscp
  /src-dst-proto/

>even after they're reassembled too.

[BB2] Nope. See the second part of the pseudocode below (the if-else 
block). You only need to store one count variable for each frag in 
the cache. And you only update two counts as each fragment is added 
to or removed from the cache.

Bob

---

From: Joe Touch <[email-masked]>
Date: Tue, 25 May 2010 07:04:39 -0700

Hi, Bob (et al.),

Trimming things down so others can follow.

I still think this assumes properties about ID generation and needs to
keep prohibitive state. See below.

Joe

...
> From all the research done to look at packet streams and identify which
> OS is generating the ID sequence, I believe we can ascertain that even
> the randomised ones guarantee not to repeat within a certain number of
> packets (see links provided earlier in thread).

Random ones ought not have a regular period, or they're not random.
Seeing any single repetition does not ensure a regular period.

And NATs don't necessarily rewrite the ID (as they ought to be required
to). Which means you're not always seeing a single OS when you look at
packets from a single source IP address.

> block). You only need to store one count variable for each frag in the
> cache. And you only update two counts as each fragment is added to or
> removed from the cache.

This assumes:
	
	a) all the packets from the src/dst/proto are fragmented
	b) the period of an ID repeating is constant

(a) isn't generally true; many apps (esp. interactive ones) generate
small packets at the end of every transaction

(b) is another assumption on how IDs are generated

Your algorithm, AFAICT, looks at only ONE ID per src/dst/proto, and
*hopes* that's the one it sees repeat - before others repeat. I can't
figure out if you keep that info for every src/dst/proto, or only for
the ones for which you've seen fragments? or only *while* you're
reassembling?

If all this is for fragments only, then if that one is skipped over by a
non-fragment, you lose. If the repeat period is shorter for other IDs
than for the one you keep, you lose.

However, even keeping ONE ID per srd/dst/proto is prohibitive - you need
to keep this even if you're not fragmenting.

>> than

How does it detect when it fails?  I.e., how do you set the initial values?

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 25 May 2010 21:46:10 +0100

Joe,

>Seeing any single repetition does not ensure a regular period.

[BB3] They are pseudorandom not random. It seems you didn't follow 
the links I sent.

Basically all the variants of pseudorandom ID generators were 
intended to hide the OS, but they have all been proved not to, 
because they all also comply with the more important property (for ID 
generation) that they don't repeat for a guaranteed number of 
packets. So we've been left with a bunch of pseudorandom generator 
implementations that don't really hide anything but also still don't 
repeat for N packets. So there's still some hope.

It was when I found this out, that I started to think how we could build on it.

>packets from a single source IP address.

[BB3] That's true.

But if the NAT doesn't re-write as it ought, probably nothing will 
work. If your rule (source must not repeat within duration of 
reordering context) were the law, AND all sources were keeping to it 
AND they somehow knew the reordering duration, BUT NATs did not 
re-write,... then the NAT could be breaking your law: repeating 
within the reordering context.

So non-compliant NATs break both our proposals. Hence best to rule 
non-compliant NATs out of scope.

>         a) all the packets from the src/dst/proto are fragmented

[BB3] No. This may be a misconception from assuming my variable name 
'frag' only applies to fragments, not to whole packets. The increment 
of 'count' is at each distinct ID, whether fragment or packet.

>         b) the period of an ID repeating is constant

[BB3] Certainly I believe the repetition period of all known ID 
generation algos is constant. But the constraint I need is slightly 
weaker; that it must not repeat within less than N packets.

That's the constraint I believe we should document for the source (as 
I've said many times). Because it documents what all sources already 
comply with (AFAIK), even the pseudo-random ones

(...but not non-compliant NATs & tunnels that don't re-write the ID - 
which we have to rule out of scope IMO).

>small packets at the end of every transaction

[BB3] Agree, but I wasn't making this assumption in the first place 
(see above), so it's fine.

>(b) is another assumption on how IDs are generated

[BB3] I believe it's the only true assumption we have, which is why I 
put all the links in the earlier posting to studies collecting and 
analysing all the ID generation algos seen on the Internet.

The reason I take so long sometimes between postings is because I'm 
actually researching my responses. I'm not just spouting email froth here.

(Actually, initially my proposal was mostly intuitive, but I've 
started fighting for it a bit more seriously now. Having done a bit 
of background digging, I think there might be something to it. 
However, I admit this area is a tough one to find any path through 
the overgrowth of non-compliant implementations).

>*hopes* that's the one it sees repeat - before others repeat.

[BB3] I don't understand. This doesn't seem to be anything like what 
I'm talking about. Might you have made a mental jump that assumes I'm 
proposing something I'm not?

Perhaps I can clarify?... IDs are only handled in fragMatchTable. The 
receiver holds all the cached IDs in fragMatchTable. It looks up the 
ID of each packet that arrives in that hashtable. Nothing surprising 
so far, it's just how you might expect a reassembly cache to work.

The other table (fragCountTable) doesn't have anything to do with 
IDs. It just holds a count of how many distinct IDs have arrived 
(determined by lookups in the other table), in order to trigger 
garbage collection of those cache entries that have been 'counted 
out' by N more recent arrivals.

[[[
Ah! Perhaps my earlier words misled you (altho the pseudocode should 
have made it clear),...?
When I said "the receiver counts how many distinct IDs have arrived 
since the last cached fragment", I didn't mean it fully checks each 
arriving ID is distinct from *all* the IDs that ever arrived since 
the oldest one in the cache. I mean it checks whether the arriving ID 
(whether packet or frag) matches any frag still held in the cache, 
and if it doesn't match anything, it counts it as a distinct new ID.

Strictly, this assumption isn't true (but it's safe) if the arriving 
packet/fragment is a duplicate that arrives after the first copy has 
been reassembled and removed from the cache.  If the receiver counts 
each duplicate ID as a distinct ID, the count of distinct IDs will 
rise too quickly. This just means some older cached fragments might 
be thrown out as garbage when they could have been used (which is the 
safe way round).
]]]

>I can't

[BB3] Only for src-dst-protos for which the receiver still has 
fragments cached. Sorry, I didn't say that, but I meant it.

But to be clear, once fragments are in the cache, it still counts 
whole packets as distinct IDs arriving too.

>non-fragment, you lose.

[BB3] As above: for mixtures of frags & whole packets, as long as 
there are some frags still cached.

>If the repeat period is shorter for other IDs

[BB3] See above. I don't recognise this idea about keeping ONE ID?

>to keep this even if you're not fragmenting.

[BB3] See above - if no fragments are cached for a src-dst-proto, no 
need for any of this.

>How does it detect when it fails?  I.e., how do you set the initial values?

[BB3] I think I understand the second question...

When the first frag arrives for a src-dst-proto that currently has 
none cached, the receiver creates the tables, and in fragCountTable 
it sets count & totalCount to 0, because no distinct IDs have yet 
arrived since this one.

The first question doesn't seem to be the same, but I don't 
understand what you mean by "it" or "fails". Perhaps you mean a cache 
miss? If so, see the pseudocode: the arriving packet/fragment counts 
as a new distinct ID. And if it's a fragment, it's cached and new 
entries are added for it in both tables.

> >> >  * 'count' in the next position.

[BB3] Boy, this is painful. I guess it would have been quicker if I 
had written & published code, but I'm trying not to get distracted 
from my day job, which isn't about fragmentation.

Bob

---

From: Joe Touch <[email-masked]>
Date: Tue, 25 May 2010 14:11:35 -0700

Hi, Bob,

See below. Overall, your algorithm

- adds work for non-fragmented packets as currently generated
- proposes a new requirement for ID generation
- generates false negatives for NAT'd packet streams

IMO, this is out of scope for this draft; you're proposing something
new. I don't think it's necessary to deprecate the use of the ID in
non-fragments, nor to relax the requirement that IDs can be reused over
an expected reordering interval (the latter of which is already a
network design parameter, so doesn't change anything).

Joe

Bob Briscoe wrote:
> [BB3] They are pseudorandom not random. It seems you didn't follow the
> links I sent.
>
> Basically all the variants of pseudorandom ID generators were intended
> to hide the OS, but they have all been proved not to, because they all
> also comply with the more important property (for ID generation) that
> they don't repeat for a guaranteed number of packets. So we've been left
> with a bunch of pseudorandom generator implementations that don't really
> hide anything but also still don't repeat for N packets. So there's
> still some hope.

You're missing my points on this issue:

- the ID is not required to be pseudorandom
	and I don't agree that adding that requirement is useful

- even pseudorandom generators that are guaranteed not to repeat for N
packets don't *always* repeat exactly every M packets for M>=N
	just because you measure a period doesn't mean that is
	the known period of the generator

> It was when I found this out, that I started to think how we could build

You're doing 'blue sky' analysis here. When it works, it's useful.
Consider when your assumptions fail - error in period measurement, etc.
- that's the case we're working with.

> But if the NAT doesn't re-write as it ought, probably nothing will work.
>
> If your rule (source must not repeat within duration of reordering
> context) were the law, AND all sources were keeping to it AND they
> somehow knew the reordering duration, BUT NATs did not re-write,... then
> the NAT could be breaking your law: repeating within the reordering
> context.
> 

They're not out of scope; they're out there. So what can we say about
repeated IDs when we see them? IMO, nothing, as a result.

Unless you believe NAT'd packets are magically labeled as such, and you
can avoid them in your algorithm.

This is why I'm proposing NOT to attempt to infer anything from the
observed IDs, and why I consider it the *sender's* responsibility to
figure out what to do (that way, when the sender doesn't, we correctly
blame a nonconformant sender). Note that NATs that don't rewrite IDs are
already violating the ID rule, and will continue to under my assumptions.

Under yours, your mechanism will silently do the wrong thing.

> 'frag' only applies to fragments, not to whole packets. The increment of
> 'count' is at each distinct ID, whether fragment or packet.

Yes, but you will only ever see a repeat of an ID that was in a fragment
 - notably the one you select (arbitrarily) to hold.

Pseudorandom generators that avoid repeating every N do not GUARANTEE
repeats ever M for M>=N. So you might end up with a repeating ID that
isn't the one you're holding, and that could cause reassembly errors
that you will not detect.

> weaker; that it must not repeat within less than N packets.

Right now, the ID must not repeat for the reuse interval. We have no
requirement at all on the algorithm used, and even when a single node's
algorithm is correct, running them through a NAT scrambles the
algorithms together, which taints your measurements exactly as I'm
concerned about above.

> comply with (AFAIK), even the pseudo-random ones

I'd like input from the group on this. IMO, this draft should deprecate
the use of the ID when fragmentation doesn't exist. I don't think it's
tenable to require any particular algorithm for ID generation.

> [BB3] Agree, but I wasn't making this assumption in the first place (see
> above), so it's fine.
> 
> 
> actually researching my responses. I'm not just spouting email froth here.>
> 
> (Actually, initially my proposal was mostly intuitive, but I've started
> fighting for it a bit more seriously now. Having done a bit of
> background digging, I think there might be something to it. However, I
> admit this area is a tough one to find any path through the overgrowth
> of non-compliant implementations).

I think if you want to write a draft proposing a new requirement for ID
generation, that's your decision, but IMO it's out of scope for this doc.

> [BB3] I don't understand. This doesn't seem to be anything like what I'm
> talking about. Might you have made a mental jump that assumes I'm
> receiver holds all the cached IDs in fragMatchTable. It looks up the ID
> of each packet that arrives in that hashtable. Nothing surprising so
> far, it's just how you might expect a reassembly cache to work.

It is surprising - I don't need to lookup non-fragments in a frag cache
right now, but if you don't you might never see the ID repeat.

> The other table (fragCountTable) doesn't have anything to do with IDs.
> It just holds a count of how many distinct IDs have arrived (determined
> by lookups in the other table), in order to trigger garbage collection
> of those cache entries that have been 'counted out' by N more recent
> arrivals.

You cannot say "distinct" here without actually keeping the IDs around.

> arriving ID is distinct from *all* the IDs that ever arrived since the
> oldest one in the cache. I mean it checks whether the arriving ID
> (whether packet or frag) matches any frag still held in the cache, and
> if it doesn't match anything, it counts it as a distinct new ID.
> 
> each duplicate ID as a distinct ID, the count of distinct IDs will rise
> too quickly. This just means some older cached fragments might be thrown
> out as garbage when they could have been used (which is the safe way
> round).
> ]]]
> 
> 
>> I can't
> [BB3] Only for src-dst-protos for which the receiver still has fragments
> cached. Sorry, I didn't say that, but I meant it.
> 
> But to be clear, once fragments are in the cache, it still counts whole
> packets as distinct IDs arriving too.
> 
> 
> [BB3] As above: for mixtures of frags & whole packets, as long as there
> are some frags still cached.
> 
> When the first frag arrives for a src-dst-proto that currently has none
> cached, the receiver creates the tables, and in fragCountTable it sets
> count & totalCount to 0, because no distinct IDs have yet arrived since
> this one.
> 
> The first question doesn't seem to be the same, but I don't understand
> what you mean by "it" or "fails". Perhaps you mean a cache miss? If so,
> see the pseudocode: the arriving packet/fragment counts as a new
> distinct ID. And if it's a fragment, it's cached and new entries are
> added for it in both tables.
> 
> 
> [BB3] Boy, this is painful. I guess it would have been quicker if I had
> written & published code, but I'm trying not to get distracted from my
> day job, which isn't about fragmentation.
> 
> 
> Bob
> 
>

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 26 May 2010 18:40:28 +0100

Joe,

>- adds work for non-fragmented packets as currently generated
True, but only if mixed with fragmented packets in the same 
src-dst-proto (rare).

>- proposes a new requirement for ID generation
True: Because I believe all hosts would already comply.

>- generates false negatives for NAT'd packet streams
True, but only if the NAT is non-compliant, and no worse than 
existing false negatives from the same NATs.

- additionally, I put a new requirement on the receiver, but 
unaltered legacy receivers will continue to be OK in all cases where 
they happen to be OK today.

Now, let's write a similar critique of your proposal...

- proposes a new rate-limit requirement that *no* src impl currently meets
   - adds an implied reqt for an e2e reordering-interval protocol
   - legacy src-dst pairs without such a protocol at both ends will 
continue to work OK in all cases where they happen to be OK today.
- generates false negatives for packet streams from non-compliant 
NATs, but no worse than existing false negatives from the same NATs.

>new.

So is the I-D.

>I don't think it's necessary to deprecate the use of the ID in
>non-fragments,

This is a different point. I agree on this.

>nor to relax the requirement that IDs can be reused over

I will re-repeat a question both Fernando & I asked, that has still 
not been answered. For expected reordering context/interval, please give:
i) a definition,
ii) an exaample value and
iii) an explanation of how a source should estimate it

>         and I don't agree that adding that requirement is useful

I'll say again, I'm proposing a src must not repeat an ID within less 
than N packets per src-dst-proto. I've never said anything about a 
requirement to do anything pseudorandom. You can meet my requirement 
by just incrementing the ID by 1 for each new packet.

I have to have the patience of a saint to not just walk away from 
this conversation. I'm trying to help.

>         the known period of the generator

I don't need a known period. I'm solely proposing
A SRC MUST NOT REPEAT AN ID WITHIN LESS THAN N PACKETS PER SRC-DST-PROTO.

In case it's not clear, the capitals mean I'm shouting, which I have 
to do when I have already said something twice and it's still being 
heard completely differently to how I'm saying it.

>- that's the case we're working with.

I'm not asking anyone to measure any period. The minimum repetition 
period is a deterministic property of the algorithm the developer 
chooses to do ID generation. It's known, not measured.

>can avoid them in your algorithm.

YOU CAN'T AVOID THEM IN YOURS EITHER.

>observed IDs,

I'M NOT INFERRING ANYTHING FROM THE OBSERVED IDs

>and why I consider it the *sender's* responsibility to
>blame a nonconformant sender).

Same with my proposal (as you know, I have put a requirement on the 
sender too).

>Note that NATs that don't rewrite IDs are

Your mechanism will also silently do the wrong thing with such a NAT.

>  - notably the one you select (arbitrarily) to hold.

I DON'T SELECT ANY ID TO HOLD.

>that you will not detect.

I DON'T SELECT ANY ID TO HOLD.

>Right now, the ID must not repeat for the reuse interval.

To be clear, this is what you are proposing, not a rule that exists right now.

>We have no

And it taints yours. It taints anyone's.

>tenable to require any particular algorithm for ID generation.

I AM NOT REQUIRING AN ID GENERATION ALGO.

I'M PROPOSING A MINIMAL CONSTRAINT ON THE ALGO. *ALL* EXISTING ALGOS 
MEET THIS CONSTRAINT AFAIK, and all the possible algos you could ever 
want to invent meet it too.

> > background digging, I think there might be something to it.
>

Understood. But I'm not going to do that.

I am continuing on this thread because I am concerned that your I-D 
places an unworkable new requirement on source implementations.

>right now, but if you don't you might never see the ID repeat.

Looking up an unfrag packet is only necessary when frags are mixed in 
the same src-dst-proto. Yes, this is extra work, but you seem to be 
making more of this weakness than it warrants. Fragmentation is rare 
these days. Unfrag packets mixed with fragments within a 
src-dst-proto are relatively rare. This is a pimple on a spot.

>You cannot say "distinct" here without actually keeping the IDs around.

Did you read the next 2 paras below?

Bob

---

From: Joe Touch <[email-masked]>
Date: Wed, 26 May 2010 11:43:31 -0700

Hi, Bob (et al.),

Trying to summarize (I'll refer to "the current draft" and "Bob's
algorithm" so we can refer to things without relative context of who
writes the email).

Joe

------------------------

- the current draft focuses on changes to "atomic" packets
	(i.e., those not already fragmented and with DF=1)
	for those packets:
	- deprecates all uses of the ID by receivers or
	intermediates
	- sender can put any value in since it is ignored

- the current ID relaxes the requirement on sender's repeating IDs
	- currently they MUST NOT repeat IDs for 2*MSL
	(which most ignore, but it's still there - so any host that
	doesn't do this is already non-compliant and already
	potentially generates reassy errors- that's not new)

	- indicates that reuse can occur so long as it won't
	interfere with reordering
		i.e., it *relaxes* the current 2*MSL reuse
		interval; this doesn't ADD a requirement so
		much as RELAX it

		it does not specify how to determine that
		value. there is no way for the sender to
		do that anyway; it's a design parameter, IMO

** if this issue is contentious, let's leave the value at 2*MSL **

I wanted to relax it. Bob is showing a *possible* way to detect the
interval at the receiver, given some assumptions, but that's not
directly useful to the sender anyway.

Addressing the key outstanding question:

- Bob repeated Fernando's question:
> ...For expected reordering context/interval, please give:
> i) a definition,

There has been such a definition since draft-touch-02 at least:

If useful, I can revise the presentation to make it clear that
"reordering interval" is defined as the "period over which reordering
can occur", i.e., the longest period between fragments of the same
datagram as seen at the reciever"

> ii) an exaample value and

2*MSL, if we can't converge on something better

> iii) an explanation of how a source should estimate it

I would suggest that the source could estimate it using RTT, i.e., some
fraction or multiple of RTT seems a reasonable estimate.

----

Bob's algorithm tries to have the receiver adjust the reassembly cache
to avoid misassociation automatically - regardless of how fast the
sender wraps IDs.

IMO, that's simply impossible. If the sender wraps faster than fragments
get interleaved, there is *NO WAY* for the receiver to detect it at all.

There are some blue-sky approaches, one of which Bob outlines, that try
to detect this *WHEN THE SENDER IS ALREADY DOING THE RIGHT THING*, i.e.,
not repeating IDs over the reordering period.

I can't see what the point of that algorithm is, then.

----

Addressing some of Bob's recent claims, even though (as noted just
above), I don't see the utility of the algorithm:

- the current draft allows new sources to not set the ID for atomic packets
	- it makes NO additional requirements for any currently
	deployed sources

	(Bob's does - those sources MUST comply with his algorithm
	properties; although many current sources do, we don't
	have a way to determine this exhaustively)

- Bob's suggestion tries to compute the reuse interval
	- not clear why this is useful; the sender is the
	one who determines what that reuse is

Some clarifications (all quoted text is from your recent response):

- Bob's algorithm detects when an ID repeats

	There's a new algorithm (Bob's pseudocode)
	that measures that period at the receiver.

> I'M NOT INFERRING ANYTHING FROM THE OBSERVED IDs

	If you don't need that measuring, why do you
	need the pseudocode you provided (which
	refers to observed IDs)?

> I DON'T SELECT ANY ID TO HOLD.

	- it had better hold an ID somewhere
	or it can't ever know it's seen it twice

	you hold it in the fragment you're reassembling, at least

	- the number of packets SENT between ID reuse
	would be what I have called the ID generator 'period'

> A SRC MUST NOT REPEAT AN ID WITHIN LESS THAN N PACKETS PER SRC-DST-PROTO.

	Let's say you pick an ID, and see it repeat in K packets,
	given the source is using, as you require, an algorithm
	that doesn't repeat for N packets.

		- you can't know that K=N
		packets could be reordered, and in that case
		K could be larger or smaller
		K can also vary if the alg isn't strictly periodic,
		(with a single fixed repeating interval for all
		IDs), or if IDs go through a NAT

		- if you pick K when it's larger than N, and if you
		use that to govern reassembly, you can end up
		causing errors

		NB: this is a case where a new recommendation could
		cause incorrect behavior; it's not possible to know
		that receiver behavior not erroneous

	- Bob's algorithm measures periodicity at the receiver
		NB: due to reordering, the period measured
		at the receiver is NOT the same as that at the
		sender - it can/will be longer or shorter

> want to invent meet it too.

	How about one that creates IDs across all destinations, not just
	a single dest? (actually, many such implementations do this)
		in this case, any ID you want to see repeat might
		or might not repeat on the sender generator's period,
		it might repeat on some multiple of that

		this is yet another way in which the receiver measure
		of this period is likely to be incorrect

- Bob's algorithm MUST check the IDs of non-fragmented packets
	- checking that ID is a computational expense
	not incurred by the current draft or by current implementations

-----------------------------------