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

From: Bob Briscoe <[email-masked]>
Date: Tue, 13 Apr 2010 17:28:03 +0100

Joe,

I've just done a thoro review of 
draft-ietf-intarea-ipv4-id-update-00, but not yet typed up.

Broad summary: Yes! I support this general approach.

Most of my comments are editorial (see a following mail). But before 
I type up my review, I want to deal with two points that I think need 
tightening up technically:

A) Define semantics, not usage
==============================
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
6. Updates to the IPv4 ID Specification
...
    o  Use the ID field only for fragmentation...

6.1 IPv4 ID Used Only for Fragmentation
...
    o  >> The IPv4 ID field of MUST be ignored except for packet
       reassembly.
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

I hold to the rule that it's generally bad practice (and futile) to 
define what a protocol field should or should not be used for. That's 
like defining how the layer above should use my layer.

We ought to define the semantics of the field. Then we can explain 
why that implies it will be wrong to use it for the purposes you list.
B) How to constrain ID repetition
=================================
6.2. Avoiding IPv4 ID Repetition and Its Impacts
Keep all the good text about avoiding non-atomic packets, etc. But 
then if the source still has to use non-atomic packets for some 
reason, we get to here:
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
    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.

    It is impractical to assert "MUST NOT" here, because there is no
    strict enforcement on packet lifetime and because sources may not be
    able to determine the reordering period.
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

The inability to say "MUST NOT" hilites a fudge here. We are saying 
the source SHOULD NOT repeat IDs within a period that it doesn't 
naturally know. This is not much better than the packet lifetime rule 
we're trying to replace. Can I suggest a rather bold step as a way 
out of this?...

Shift the misassociation constraint to the reassembly function (at 
the dest), rather than constraining ID generation (at the source).

Ie. the source just sends packets as fast as it needs to, wrapping 
the ID as often as the packet rate requires. But we make the 
reassembly function responsible for tossing fragments from its cache 
before it risks misassociation.

A dest could only hope to take on this responsibility properly if 
each source was using the full ID space for each destination 
separately (which RFC791 says it is meant to do, but some don't).

[Perhaps this is too bold a change from RFC791. I believe you are 
trying to tread a thin line between documenting best practice and 
defining new best practice. But 'it would have been nice' if this was 
the way fragmentation had been constrained in the first place: 
effectively using self-clocking rather than arbitrary packet lifetimes.]

Bob

At 17:30 26/03/2010, [email-masked] wrote:
>         Title           : Updated Specification of the IPv4 ID Field
>         Author(s)       : J. Touch
>         Filename        : draft-ietf-intarea-ipv4-id-update-00.txt
>         Pages           : 15
>         Date            : 2010-03-26
>

________________________________________________________________
Bob Briscoe,                                BT Innovate & Design

---

From: Joe Touch <[email-masked]>
Date: Tue, 13 Apr 2010 13:03:56 -0700

Hi, Bob,

Thanks for the feedback, first.

Also, I had an off-line discussion with John Day just this AM, and he
suggested I also address why generally just spinning down the MSL
doesn't help much (even if we notch it down from 120 secs to 6 secs -
which is double what I can see with a 3G card in real use - the
host-host BW goes up from 6.4 Mbps to around 130 Mbps, which is still
far too low).

Comments on the two points you raise are inserted below. The first point
(A) is easy to address; the second (B) I'm not sure about (see below).

Thanks for the feedback, and let me know if you see a way out of (B).

And thanks for the other editorial feedback as well.

Joe

Bob Briscoe wrote:
> Joe,
> 
> I've just done a thoro review of draft-ietf-intarea-ipv4-id-update-00,
> but not yet typed up.
> 
> Most of my comments are editorial (see a following mail). But before I
> type up my review, I want to deal with two points that I think need
> We ought to define the semantics of the field. Then we can explain why
> that implies it will be wrong to use it for the purposes you list.

Absolutely. Easy to put in.

> Keep all the good text about avoiding non-atomic packets, etc. But then
> if the source still has to use non-atomic packets for some reason, we
> get to here:
> The inability to say "MUST NOT" hilites a fudge here. We are saying the
> source SHOULD NOT repeat IDs within a period that it doesn't naturally
> know. This is not much better than the packet lifetime rule we're trying
> to replace. Can I suggest a rather bold step as a way out of this?...
> 
> Shift the misassociation constraint to the reassembly function (at the
> dest), rather than constraining ID generation (at the source).
> 
> Ie. the source just sends packets as fast as it needs to, wrapping the
> ID as often as the packet rate requires. But we make the reassembly
> function responsible for tossing fragments from its cache before it
> risks misassociation.

That's having the source write checks the receiver is responsible for
cashing. Since IP is mostly unidirectional*, I'd like to remind the
source that it is they who cause the pain, so I'd like to keep the
SHOULD NOT here.

* ICMPs excepted, but we don't want to rely on those even further, as we
can for MTU discovery.

I'm not sure how to ask the receiver to do anything useful here. If it
tosses before potential misassociation, it could easily be tossing
fragments it needs to reassemble. The problem is that it can't know when
it's seeing wrapped fragments that it shouldn't reassemble vs. ones it
should.

So ultimately I don't know what to tell the receiver to safely do here.

> A dest could only hope to take on this responsibility properly if each
> source was using the full ID space for each destination separately
> (which RFC791 says it is meant to do, but some don't).
> 
> [Perhaps this is too bold a change from RFC791. I believe you are trying
> to tread a thin line between documenting best practice and defining new
> best practice. But 'it would have been nice' if this was the way
> fragmentation had been constrained in the first place: effectively using
> self-clocking rather than arbitrary packet lifetimes.]

The self-clocking aspect is what we recommend later, i.e., don't
fragment in the first place, but if you do then don't wrap over the
"expected" reordering on a path.

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 13 Apr 2010 23:35:21 +0100

Joe,

inline...

>And thanks for the other editorial feedback as well.

I'm juggling a number of things at once at the mo - editorial list 
may not be immediate.

more...

>Absolutely. Easy to put in.

It's never easy to define the subtleties of semantics well. 
Nonetheless, we can but try. This will involve changes scattered 
throughout the doc - I'll make sure I hilite them all in my list of 
editorial changes.

>source that it is they who cause the pain, so I'd like to keep the

It's not so straightforward as the checking analogy. The problem with 
unidirectional is that control and information aren't in the same place.

>I'm not sure how to ask the receiver to do anything useful here.

The best way I can explain is to try to describe how a reassembly 
implementation might be written to satisfy my proposed constraint.

1) dest counts how many distinct IDs have arrived from each separate 
source modulo 2^16;
2) dest stores a circular linked list of cached fragments in order of 
arrival, along with their arrival count (from bullet #1);
3) dest holds pointer into the circular list to the oldest entry, i
4) whenever an arriving fragment is about to be associated with one 
in the cache, if its count is j, then keep expiring the oldest entry 
from the cache, which increases i % 2^16 until (j < i - N) % 2^16. 
Where N = constant (TBD), which represents the size of the guard band 
between the newest IDs arriving and oldest IDs being cached for reassembly.

I think it's also robust to DoS (there's an invitation to be 
flamed!). However, as I said, this only works if all sources use the 
full ID space for each destination separately (which RFC791 says they 
are meant to do, but many don't).

It would even 'work' for random ID assignment, because the receiver 
could set N high enough to reduce the probability of getting a misassociation.

>If it
>fragments it needs to reassemble.

If the reordering context has got large enough due to hi-speeds, so 
that it is tossing frags it needs, then the procedure above 
prioritises correct association over keeping reassembly efficient. 
Instead you get more retransmissions. If there's a lot of highly 
delayed fragments at high speed, that's the behaviour you want; given 
you've only got a 16-bit ID field you can't want anything better.

>The problem is that it can't know when

Is it clearer now?

Bob

>"expected" reordering on a path.

I hope it's clearer what I meant by self-clock now, rather than using 
a timer. I meant it's based on circling round a known-size number 
space, rather than waiting an unknowable lifetime.

Cheers

Bob

---

From: Joe Touch <[email-masked]>
Date: Tue, 13 Apr 2010 16:48:36 -0700

Hi, Bob,

Overall, assuming that the ID space cycles in sequence is a new
requirement that I don't think is tenable; as you note, it requires
state, particularly on a per IP-pair/protocol basis.

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.

Any thoughts from others?

Joe

PS - FWIW, I think the semantics of the space are actually easy to
indicate, and are already indicated in the doc:

6.1. IPv4 ID Used Only for Fragmentation

   Although at least one document suggests the ID field has other uses,
   we assert here that the ID field is defined only for fragmentation
   and reassembly.

Was there something more specific we needed to actually state?

Joe

Bob Briscoe wrote:
> I'm juggling a number of things at once at the mo - editorial list may
> not be immediate.
> 
> more...
> 
>> Joe
>>
>> Bob Briscoe wrote:
>> > Joe,
>> >
> It's never easy to define the subtleties of semantics well. Nonetheless,
> we can but try. This will involve changes scattered throughout the doc -
> I'll make sure I hilite them all in my list of editorial changes.
> 
> 
> 4) whenever an arriving fragment is about to be associated with one in
> the cache, if its count is j, then keep expiring the oldest entry from
> the cache, which increases i % 2^16 until (j < i - N) % 2^16. Where N =
> constant (TBD), which represents the size of the guard band between the
> newest IDs arriving and oldest IDs being cached for reassembly.
> 
> I think it's also robust to DoS (there's an invitation to be flamed!).
> However, as I said, this only works if all sources use the full ID space
> for each destination separately (which RFC791 says they are meant to do,
> but many don't).
> 
> If the reordering context has got large enough due to hi-speeds, so that
> it is tossing frags it needs, then the procedure above prioritises
> correct association over keeping reassembly efficient. Instead you get
> more retransmissions. If there's a lot of highly delayed fragments at
> high speed, that's the behaviour you want; given you've only got a
> 16-bit ID field you can't want anything better.
> 
>> trying
> I hope it's clearer what I meant by self-clock now, rather than using a
> timer. I meant it's based on circling round a known-size number space,
> rather than waiting an unknowable lifetime.
> 
> Cheers
> 
> 
> Bob
> 
> 
> 
> 
> 
>

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 28 Apr 2010 08:29:52 +0100

Joe,

As warned off-list, I had to let this thread sleep for a while. I'm 
back now; see inline...

At 00:48 14/04/2010, Joe Touch wrote:
>requirement that I don't think is tenable;

The ID space doesn't have to be constrained to cycle in sequence. The 
semantic only has to be that an ID will not repeat for N packets 
within a src-dest-protocol triple, where N is to be defined. In the 
extreme N could be (2^16)-1. But if the receiver is having to count 
packets, it will have to allow for some packet losses. N=2^15 would 
allow for a very conservative sustained 50% packet loss.

BTW, FreeBSD's random ID assignment would have to be allowed for in 
the definition of the semantics.

>as you note, it requires

If the cache doesn't store a packet count, it stores a timeout per 
IP-pair/protocol anyway.

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

I'm not saying my idea to put the responsibility on the receiver is 
necessarily the answer. Perhaps there need to be requirements on both 
ends. But I am saying there's a genuine problem here (as your 
conversation with John Day showed)...

If you were coding a source, how would you answer these questions 
(that your draft requires the implementer to answer):
Q1. How long does the source expect the destination to cache 
fragments for reassembly after reordering?
A1: 4sec (say)

That implies a maximum packet rate of (2^16)/4 = 16,384pps
(~200Mbps for 1500B packets, but potentially slower for a smaller MTU)

Q2. How do I stop my source code being used for transfers to one v4 
dest IP that are collectively pulling more than 16,384pps through the 
ID space per protocol?
A2: I don't know: My code is independent of packet rate, which 
depends on the host it's used on at run-time, and the network path 
and the other host. OK, I could set a 4s timer and continually check 
the ID space hasn't wrapped. Then...

Q3. What do I do if it wraps before this timer expires? Limit the 
window? Turn off fragmentation and do PLPMTUD? But I had a reason for 
not doing that in the first place...

If we can't answer these questions, we must not tell implementers 
they MUST answer them. This is a real problem that we mustn't duck.

more...

>Was there something more specific we needed to actually state?

Here, I think we're talking at cross-purposes. "Use only for 
fragmentation" defines a use of the field, not the semantics of the field.

You already have a couple of bullets in S.7.1 that I would call the 
semantics of the field, but I would tighten them up as shown in {}:

    o  >> The IP ID is not defined if the packet (datagram) is atomic. IP
       packet sources MAY use any value as ID; all such values MUST BE
       ignored {and not changed} on examination at intermediate nodes and
       destinations.

    o  >> The IP ID of non-atomic packets MUST BE unique {per source-
       destination-protocol triple }
          {Your preferred approach: during the time the source expects
           reordered to arrive at the destination.}
          {My preferred approach: within a sequence of <N:TBA> packets.}

/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\[Then,

I don't believe we should say "the ID MUST be ignored except for reassembly".
This would be equivalent to RFC791 having said the TTL MUST only be 
used for loop detection, which would have precluded uses such as GTSM 
(RFC3682). We should avoid prohibiting safe innovation.

I would suggest instead:
    o  >> The ID MUST NOT be assumed unique by nodes that cannot or 
do not determine its uniqueness within the bounds defined in the 
previous bullet.

Then we can deprecate the three uses of the IP ID that you have 
identified, but on the grounds that they break this rule, rather than 
an (unnecessary) blanket ban on doing anything with the IP ID unless 
it is reassembly.

Bulleting each deprecated use from your paragraph:

    o Some hosts use this tag to validate
    received ICMPs, in which the ICMP payload - an IP packet prefix - is
    matched against a cache of recently transmitted IP headers {to check
    whether the received ICMP reflects a transmitted packet. This is not
    a valid use of the ID field, because the host cannot tell whether it
    may have wrapped the ID field since it sent the packet that caused
    the intermediate node to send the ICMP message. Further, if a NAT
    rewrites the IP ID (as it should for non-atomic packets), then the
    source cannot validate ICMP messages based on the IP ID of the
    original packet. Incidentally, this technique is vulnerable to
    spoofing of ICMPs from attackers on the data path.}

I prefer more precise wording like this rather than the text ending:
"and like ID reuse will cause problems at high packet rates"
If we want to persuade implementers not to do things, we need to give 
precise reasons.

    o A similar sort of matching can be used in tunnels, to enable
    ICMP relaying at the tunnel ingress, with similar challenges
    [<http://tools.ietf.org/html/rfc2003>RFC2003].
Again, rather than banning this, we need to say exactly what's wrong 
with it, and say how to do it properly instead.

    o The IP ID has been
    suggested as a way to detect and remove duplicate packets, e.g., at
    congested routers. {Although this has been noted 
[<http://tools.ietf.org/html/rfc1122>RFC1122], no current
    deployments are known. It is unlikely a router implementation would
    want to, or be able to, check the above uniqueness constraints for
    each IPv4 src-dest-protocol triple merely to remove duplicate packets,
    therefore this approach is also deprecated.}

HTH

Bob

> >> > to replace. Can I suggest a rather bold step as a way out of 
> this?...>> >

---

From: Joe Touch <[email-masked]>
Date: Wed, 28 Apr 2010 08:42:25 -0700

Hi, Bob, (et al.),

Bob Briscoe wrote:
> Joe,
> 
> As warned off-list, I had to let this thread sleep for a while. I'm back
> now; see inline...
> 
> semantic only has to be that an ID will not repeat for N packets within
> a src-dest-protocol triple, where N is to be defined. 

The current requirement is that the ID does not repeat unless used to
identify a new fragment and the old fragments are assumed gone.

Using any other N would be a new requirement that would be impossible to
impose.

> If the cache doesn't store a packet count, it stores a timeout per

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.

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

> conversation with John Day showed)...

IMO that conversation suggests additional explanation is useful - e.g.,
why decreasing the global MSL doesn't help (since currently known values
still inhibit throughput based on current sustained rates).

> If you were coding a source, how would you answer these questions (that
> your draft requires the implementer to answer):
> Q1. How long does the source expect the destination to cache fragments
> for reassembly after reordering?
> A1: 4sec (say)
> 

I would say that a receiver might have some expectation (based on past
successful reassembly, e.g., that 95% can be reassembled by holding
fragments 4 seconds, then that would mean it might decide to drop
incomplete reassemblies that persist longer.

If you have a high-level backchannel, the sender might be told that, but
we don't have that in IP (and I don't expect we want to/can add an ICMP
message for this purpose).

> Q2. How do I stop my source code being used for transfers to one v4 dest
> IP that are collectively pulling more than 16,384pps through the ID
> space per protocol?
> A2: I don't know: My code is independent of packet rate, which depends
> on the host it's used on at run-time, and the network path and the other
> host. OK, I could set a 4s timer and continually check the ID space
> hasn't wrapped. Then...

You set the DF and don't fragment them yourself. In that case, the ID
field is meaningless, and you can run as fast as you want.

When you fragment or allow downstream fragmentation, it's your
responsibility to figure out how not to reuse the IDs in ways that
defeat reassembly. If you have a backchannel, you can use it - e.g.,
from TCP getting hints about whether segments come out of order.

> not doing that in the first place...

You currently are supposed to do one of:
	- pace (limit the throughput)
	- disable fragmentation (and use PMTUD, PLPMTUD, or just
	send packets you know can't be fragmented, i.e., 64 bytes)

You can have all the reasons you want for not doing these, but the point
is that *implementations already ignorantly reuse the ID*, at their own
risk.

There's no way around that except to say:
	a) don't do it
	b) if you do it, here are the risks, and it's
	your responsibility to figure out how to mitigate them

That's what this doc does.

Joe

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 28 Apr 2010 18:27:38 +0100

Joe,

>Using any other N would be a new requirement that would be impossible to

I'm aware this would be new stuff, and therefore can't be applied in 
retrospect. The point I'm making is the same as John Day's: without 
addressing this, we're just denying there is an inherent problem with 
the existing way of doing this.

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

>protocol to determine this.

The I-D says:
"
"

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.

Or am I being thick and missing something?

>That's what this doc does.

I think I'm beginning to understand the writing style here. The 
constraint on the source seems to be sarcastic. It says "If you want 
to use fragmentation, here's an impossible rule you have to follow." 
I don't believe we should write RFCs like that.

Cheers

Bob

---

From: Joe Touch <[email-masked]>
Date: Wed, 28 Apr 2010 11:46:50 -0700

Hi, Bob,

Cutting things down for brevity:

Bob Briscoe wrote:
...
> 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.

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

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?

FWIW, we could have done this much better, as follows (all arithmetic
modulo 4):

Consider 4 regions of ID (00*, 01*, 10*, 11*)

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

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

----

The upshot is that I think the doc should focus on:

	a) the ID having no meaning when the packet is atomic

	b) sources avoiding sending non-atomic packets
	(perhaps focusing on "sources that want to run over 10 Mbps"?)

	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)

Joe