Subject: [Softwires] MAP draft 11 question on fragment ID space reduction

From: Andrew 👽 Yourtchenko <[email-masked]>
Date: Mon, 13 Oct 2014 20:00:48 +0200

[ resending the full mail including the softwire maillist, not just
the authors ]

Hello,

In http://www.ietf.org/rfcdiff?url2=draft-ietf-softwire-map-11

A change in "8.3.3. Sending IPv4 fragments to the outside" from
"SHOULD" to "MUST" jumped at me, which caused to think more about this
paragraph.

This paragraph says now:

"If two IPv4 host behind two different MAP CE's with the same IPv4
   address sends fragments to an IPv4 destination host outside the
   domain, those hosts may use the same IPv4 fragmentation identifier,
   resulting in incorrect reassembly of the fragments at the destination
   host.  Given that the IPv4 fragmentation identifier is a 16 bit
   field, it can be used similarly to port ranges.  A MAP CE MUST
   rewrite the IPv4 fragmentation identifier to be within its allocated
   port-set."

I'd argue that setting it to "MUST" tries to solve a corner case but
in return introduces a much worse behavior for the common case.

I'll use a slight hyperbole to illustrate the worst case of such an
impact for a common case.

First, implementation-wise: I assume the CPE would take the frag ID
and apply modN operation where N is the share ratio, and then shift
the frag ID into correct space.

Now, the hyperbole: take a share ratio of 64K. One CPE gets a
single TCP/UDP port, and a single fragment id to peruse.

And, from a host behind one of these CPEs you open a TCP session to
another host on IPv4. You start sending a file. Your TCP window grows
beyond a single segment, and you send 4 fragments - 2 per segment, and
because of the rewriting they all get the same IP ID. As a result the
destination can not reassemble the packets.

Note that this is a typical case - no collision, no two hosts opening
a session. It gets affected.

This is of course a hyperbole to show the problem.

The smaller share ratio makes the problem less acute, but even with
16-bit space and even some years ago [1] there were problems. So given
that the broadband speeds multiplied in the meantime, shrinking the ID
space will make the problem worse.

Since it looks like the fragment value does not affect the interoperability, I'd
request to put this back to "SHOULD" (arguably it even be relaxed to
"MAY", given the severity of the issue above), and let the
implementers themselves consider whether it is worth doing or not.

[1] https://tools.ietf.org/html/draft-mathis-frag-harmful-00

Thanks!

--a

p.s. a cosmetic nit: looks like the following sentence in section 5.2
has an extra "that":

"The Rule IPv6 prefix (which is part of the End-user IPv6 prefix) that
   is common among all CEs using the same Basic Mapping Rule within the
   MAP domain. "

---

From: Ole Troan <[email-masked]>
Date: Tue, 14 Oct 2014 12:01:39 +0200

[resending to list, cause mailman whinged about too many in cc]
Andrew,

thank you for the comment. let me top-post my reply.

the scenario we were concerned about was where a number of CPEs would share the same IPv4 address, and where many of them would communicate with the same destination. if there wasn't a way to coordinate the fragment id space used, there would be a chance of the remote destination incorrectly reassembling packets. where one fragment would come from CPE #1 and the other from CPE #2.

there is a tradeoff between that problem and the problem you identify, that is risking fragment collision within one single connection.

splitting the fragment id space so that there is only a single bit per CPE sounds like a corner case that should be disallowed. I don't know if we have the knowledge to be able to specify exactly how much of the fragment id space is safe to split up though.is it 4, 6, or 8 bits?

if changing back to SHOULD from the MUST would lead people to accept that we leave the exact recommendations for further study I would be happy to do that.

I have cc'ed Ted who brought this up initially in his AD review, and I've also included Joe Touch in case he has further insights.

cheers,
Ole

> On 13 Oct 2014, at 19:22 , Andrew 👽 Yourtchenko <[email-masked]> wrote:
> 
> in return introduces a much worse behavior for the common case, if I
> understand it correctly.
> 
> Now, the promised hyperbole: take a share ratio of 64K. One CPE gets a
> single port, and a single fragment id to peruse.
>

---

From: Ted Lemon <[email-masked]>
Date: Tue, 14 Oct 2014 08:32:35 -0500

> splitting the fragment id space so that there is only a single bit per CPE sounds like a corner case that should be disallowed. I don't know if we have the knowledge to be able to specify exactly h…

There's a lot to think about here.  The fragment ID translation algorithm probably needs to maintain a cache so that it doesn't accidentally overload fragment IDs.   The set of all outstanding fragments has the potential to be larger than the set of all ports in use, so there is definitely reason to be concerned about shrinking the fragment ID space.   However, shrinking the fragment ID space _does_ serve the useful purpose of isolating fragment ID collisions to the nodes that are supposed to be receiving the fragments.

It may be that the right thing to do is to note that this is a problem, make a recommendation, but essentially leave it as future research, since we really haven't analyzed the problem in enough depth to make an informed recommendation.

> if changing back to SHOULD from the MUST would lead people to accept that we leave the exact recommendations for further study I would be happy to do that.

So yes, this might be a good way to go.

---

From: "Rajiv Asati (rajiva)" <[email-masked]>
Date: Tue, 14 Oct 2014 14:51:02 +0000

It might be worth understanding why this problem is even worth
addressing/mentioning.

Is the possibility of 2 or more host devices (behind 2 or more MAP CE
routers) sharing the same IPv4 address would be "generating the fragmented
packets" towards the same destination around the same time, not close to
zero due to PMTUD etc.?

AFAIK, RFC6888 doesn¹t mention such a problem or requirement for CGN?

IMO, there shouldn¹t be any normative recommendation, if this problem is
mentioned.

-- 
Cheers,
Rajiv Asati
Distinguished Engineer, Cisco

-----Original Message-----
From: Ted Lemon <[email-masked]>
Date: Tuesday, October 14, 2014 at 9:32 AM
To: Ole Troan <[email-masked]>
Cc: Softwires-wg list <[email-masked]>
Subject: Re: [Softwires] MAP draft 11 question on fragment ID space
reduction

>> splitting the fragment id space so that there is only a single bit per
>>CPE sounds like a corner case that should be disallowed. I don't know if
>>we have the knowledge to be able to specify exactly how much of the
>>fragment id space is safe to split up though.is it 4, 6, or 8 bits?
>
>There's a lot to think about here.  The fragment ID translation algorithm
>probably needs to maintain a cache so that it doesn't accidentally
>overload fragment IDs.   The set of all outstanding fragments has the
>potential to be larger than the set of all ports in use, so there is
>definitely reason to be concerned about shrinking the fragment ID space.
> However, shrinking the fragment ID space _does_ serve the useful purpose
>of isolating fragment ID collisions to the nodes that are supposed to be
>receiving the fragments.
>
>It may be that the right thing to do is to note that this is a problem,
>make a recommendation, but essentially leave it as future research, since
>we really haven't analyzed the problem in enough depth to make an
>informed recommendation.
>
>> if changing back to SHOULD from the MUST would lead people to accept
>>that we leave the exact recommendations for further study I would be
>>happy to do that.
>
>_______________________________________________
>Softwires mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/softwires

---

From: Ted Lemon <[email-masked]>
Date: Tue, 14 Oct 2014 09:54:17 -0500

> It might be worth understanding why this problem is even worth

This was in the document, so I commented on it.   I don't know what the original motivation was for adding it.   I would be okay with simply removing the text if the authors and WG agree that it's not necessary.

---

From: Joe Touch <[email-masked]>
Date: Tue, 14 Oct 2014 10:39:52 -0700

On 10/14/2014 2:58 AM, Ole Troan wrote:
...
> splitting the fragment id space so that there is only a single bit 
> per CPE sounds like a corner case that should be disallowed. I don't
> know if we have the knowledge to be able to specify exactly how much
> of the fragment id space is safe to split up though.is it 4, 6, or 8
> bits?

As per RFC 6864, the IPv4 ID space is small and use of that space needs
to consider the number of current IP packets being reassembled, i.e.,
the reordering likely to occur.

It might be safe to use a space one bit larger than the amount of
reordering, but I'd prefer two.

So the key question is:

	- how much fragment reordering to you expect *within*
	a given IP address pair/transport tuple?

I don't know the answer to that, but log2(reordering) + 2 ought to be a
lower bound on the space that might overlap.

I.e., I doubt you should ever allow 1-2 bits. I would expect a minimum
of 4 bits but the appropriate answer depends on the reordering you're
trying to protect against.

NOTE: I would strongly encourage an encapsulation that includes its own
checksum to protect against incorrect reassembly (if that's not already
included; I haven't checked the draft).

Joe

---

From: Ole Troan <[email-masked]>
Date: Wed, 15 Oct 2014 15:27:47 +0200

Ted, et al,

there are good arguments going both ways, so apologies for my changing opinion here. ;-)

we could go with the hand-wavy, there is a problem here, we don't have a good solution:

        <t>If two IPv4 host behind two different MAP CE's with the
        same IPv4 address sends fragments to an IPv4 destination host
        outside the domain, those hosts may use the same IPv4
        fragmentation identifier, resulting in incorrect reassembly of
        the fragments at the destination host. Given that the IPv4
        fragmentation identifier is a 16 bit field, it could be used
        similarly to port ranges. A MAP CE could rewrite the IPv4
        fragmentation identifier to be within its allocated port-set,
        if the resulting fragment identifier space was large enough
        related to the rate fragments was sent. However, splitting the
        identifier space in this fashion would increase the
        probability of reassembly collision for all connections
        through the CPE. See also <xref target="RFC6864"/></t>

the alternatives are that we could say, since the problem of multiple CPEs with same IP address sending fragments to same destination required coordination that if the fragment id space was say 10 bits, then rewrite. or we could go even further and say that the CPE would have to throttle traffic to ensure that the id space didn't cycle within the reassembly timeout.
or we could drop the text altogether.

my preference would be the above proposed text. it has the problem description but it doesn't prescribe a solution.

any other opinion?

ps: whatever solution we have here should probably also apply to the other mechanisms. e.g. https://tools.ietf.org/html/draft-ietf-softwire-4rd-09#section-4.6.3

cheers,
Ole

> On 14 Oct 2014, at 15:32 , Ted Lemon <[email-masked]> wrote:
>

---

From: Rémi Després <[email-masked]>
Date: Thu, 16 Oct 2014 11:24:48 +0200

Hi, Ole,

FWIW, a look at https://tools.ietf.org/html/draft-ietf-softwire-4rd-09#section-4.6.3 might be helpful.

Cheers,
RD

---

From: Andrew 👽 Yourtchenko <[email-masked]>
Date: Thu, 16 Oct 2014 13:12:04 +0200

Hi Remi,

On 10/16/14, Rémi Després <[email-masked]> wrote:
> Hi, Ole,
>
> FWIW, a look at
> https://tools.ietf.org/html/draft-ietf-softwire-4rd-09#section-4.6.3 might
> be helpful.

This is exactly the problem. You replace the problem of a highly
visited destination (for whom the natural path is to deploy IPv6
anyway and bypass the whole transition mechanism?) having potential
for reassembly errors with a problem of N-fold increased fragment
collision probability on *all* streams, where N is your share ratio,
and which side of this tradeoff is worse is unclear to me - both are
bad in different ways.

Fortunately, since CGNs provide a higher sharing ratio of addresses
(and they can't possibly rewrite the IDs because they do not have a
deterministic algorithm), and are much more widely deployed than any
of the tech we are discussing, we should have already hit this problem
in real life many times over ? Any feedback on this ?

--a

>> the alternatives are that we could say, since the problem of multiple CPEs
>> with same IP address sending fragments to same destination required
>> coordination that if the fragment id space was say 10 bits, then rewrite.
>> or we could go even further and say that the CPE would have to throttle
>> traffic to ensure that the id space didn't cycle within the reassembly
>> timeout.
>> my preference would be the above proposed text. it has the problem
>> description but it doesn't prescribe a solution.
>>
>> any other opinion?
>>
>> ps: whatever solution we have here should probably also apply to the other
>> mechanisms. e.g.
>> https://tools.ietf.org/html/draft-ietf-softwire-4rd-09#section-4.6.3
>>
>> cheers,
>> Ole
>>
>>
>>

---

From: Ted Lemon <[email-masked]>
Date: Thu, 16 Oct 2014 07:44:28 -0500

> my preference would be the above proposed text. it has the problem description but it doesn't prescribe a solution.

WFM.