Subject: [multipathtcp] Options vs payload & offload

From: <[email-masked]>
Date: Mon, 26 Jul 2010 13:58:09 +0100

one of the issues that came up on Saturday as being very important is that the MPTCP should support offload.

I was wondering if this issue has any impact on our Options vs Payload discussion - ie which should be used for signalling (after the initial MPTCP-capability indication).
Or is offload an orthogonal issue, which can be done equally well (or with equal difficulty) whether options or payload is chosen?

thanks
phil

---

From: Joe Touch <[email-masked]>
Date: Mon, 26 Jul 2010 08:03:42 -0700

> Or is offload an orthogonal issue, which can be done equally well (or with equal difficulty) whether options or payload is chosen?

Some offload engines put the TCP data and headers in different places, 
so this COULD impact whether those engines can easily support payload 
location of opition data.

Joe

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 28 Jul 2010 09:41:58 +0200

> Or is offload an orthogonal issue, which can be done equally well (or with equal difficulty) whether options or payload is chosen?

As I understand it, this offloading is often done using a simple but fast RISC CPU, so in theory the NIC could be programmed to perform any operation that can be performed sufficiently efficiently.

In that regard, there is an issue with putting singaling in the data stream. I got two conflicting pieces of information out of yesterday's session: the information (always?) follows the TCP header, and it's like SSL, having its own framing that may or may not coincide with TCP segmentation.

The former, where the MPTCP signaling always follows the TCP header, _should_ be workable if vendors are prepared to add multipath offloading to their NICs. The latter, I am going to speculate without having talked to these vendors, would be quite hard. Even if the implementation is easy it's doubtful that MPTCP offloading is added before MPTCP is wildly successful, but if it's very hard, because basically another pass through the data stream must be made to find the MPTCP signaling because it doesn't always sit in the same place in the packet, then I'm very sure the NIC vendors are going to take a pass until their customers start insisting en masse that this is implemented. (Apart from the extra work this also requires additional state.)

However, there is one thing that makes the SSL-like framing interesting: this might allow for the possibility to implement MPTCP in user space, the same way SSL is implemented in user space. So if someone has a proposal in this direction, with perhaps some limited modification to the kernel TCP stack that makes it possible to move past holes in the TCP seqnum space (without this it's not really going to work I don't think) then I think we should listen to that.

But barring such a proposal, I think it makes more sense to go with options. We know this is likely to perform well, while with the payload approach this is questionable at best. As to the issue of lack of option space, two things:

1. this is nature's way of forcing us to leave some space in the packet for data and not use it all up for overhead

2. unless I'm very much mistaken, there have been past proposals for extending the option space. This is going to be painful but at least this way we share the pain, if we want to do something just for MPTCP it's that much harder to get middlebox implementers to support this, compared to the situation where this is presented as a more general next step for TCP

About MPTCP and offloading in general. Offloading works by the TCP stack generating a jumboframe with one IP header, one TCP header and a very large data segment. The NIC hacks the data into smaller pieces, puts copies of the IP and TCP headers in front of each piece, adjusts the minimum number of fields that it can get away with adjusting (mostly the sequence number) and then sends out the whole thing as a series of packets. I believe that TCP options are copied into each of the resulting packets. So the only way MPTCP can work with offloading is if the MPTCP options can be identical in multiple packets. So that means something like having a second sequence number in a TCP option won't work. However, this should be easily (?) fixable by encoding the second sequence number as an offset towards the regular seqnum field rather than a regular integer.

---

From: Andrew Yourtchenko <[email-masked]>
Date: Wed, 28 Jul 2010 09:53:47 +0200

>> Or is offload an orthogonal issue, which can be done equally well (or with equal difficulty) whether options or payload is chosen?
[snip]

> However, there is one thing that makes the SSL-like framing interesting: this might allow for the possibility to implement MPTCP in user space, the same way SSL is implemented in user space. So if…

Jana (in CC) has a proposal for exactly that, I believe. If I
paraphrase correctly (Jana please fix me if I am wrong): the API
involves punting the segments we send the SACK for, to the userland;
and also allowing the userland to know when those chunks of sequence
space reappear in the "TCP proper" bytestream.

thanks,
andrew

---

From: "SCHARF, Michael" <[email-masked]>
Date: Wed, 28 Jul 2010 10:19:50 +0200

> In that regard, there is an issue with putting singaling in 
> the data stream. I got two conflicting pieces of information 
> out of yesterday's session: the information (always?) follows 
> the TCP header, and it's like SSL, having its own framing 
> that may or may not coincide with TCP segmentation.

The proposal of MCTCP is to do exactly the same like TLS/SSL. There is a
separate framing on top of the bytestream.

For efficiency reasons, it is helpful if the TLV header always start at
the first byte of a packet, and I this should usually be true on a
packet-based stack, unless Nagle messes up the segmentation.

I think that there are offloading solutions for SSL/TLS. Complete
offload support for payload encoding would be very similar like SSL/TLS
offloading.

> However, there is one thing that makes the SSL-like framing 
> interesting: this might allow for the possibility to 
> implement MPTCP in user space, the same way SSL is 
> implemented in user space. So if someone has a proposal in 
> this direction, with perhaps some limited modification to the 
> kernel TCP stack that makes it possible to move past holes in 
> the TCP seqnum space (without this it's not really going to 
> work I don't think) then I think we should listen to that.

As I mentioned before, I have running code for implementing MCTCP in the
user space, as it is specified in the draft. With some additional
support from the kernel, we could do further tricks, e. g., for data
ACKs.

Yet, anyway, for a user-space solution we do need a library similar to
SSL in the user space. Apps that are aware of MPTCP can be compiled
against that library. For legacy apps, we might need some hooks in the
standard library of the OS that provides the socket API, which is a
little bit more tricky, but it seems to be doable.

And it offers a possible deployment path for a initial version of MPTCP
with much less impact on the kernel. I agree that for 10G stuff, this
solution may not be good enough. But at the moment Sebastian seems to be
struggling with the complexity of the protocol if it is completely
implemented in the kernel. I think we should really discuss deployment
paths that start with simple steps. They could be doable for option
encoding, too, but I've not seen any discussion how we could do it.

> But barring such a proposal, I think it makes more sense to 
> go with options. We know this is likely to perform well, 
> while with the payload approach this is questionable at best. 

I don't know what you refer to with "performs well".

If it is about implementation overhead, SSL/TLS shows that payload
encoding is doable.

If it is about head-of-line blocking issues, there are several solutions
on the table how to mitigate this
(separate flow, allow to disable data ACKs in environment where
performance really matters, etc.).

> As to the issue of lack of option space, two things:
> 
> 1. this is nature's way of forcing us to leave some space in 
> the packet for data and not use it all up for overhead

I am not sure if I understand this reason. Could you please explain it?
 
> 2. unless I'm very much mistaken, there have been past 
> proposals for extending the option space. This is going to be 
> painful but at least this way we share the pain, if we want 
> to do something just for MPTCP it's that much harder to get 
> middlebox implementers to support this, compared to the 
> situation where this is presented as a more general next step for TCP

Well, of course MPTCP's options could be one way to foster larger TCP
option space at some time in future. But then, let's be very clear that
this is the intention of the design choice.

AFAIK, all proposals for longer options had some severe backward
compatibility issues. Also, note that MCTCP only needs 6 byte in SYNs. 

> About MPTCP and offloading in general. Offloading works by 
> the TCP stack generating a jumboframe with one IP header, one 
> TCP header and a very large data segment. The NIC hacks the 
> data into smaller pieces, puts copies of the IP and TCP 
> headers in front of each piece, adjusts the minimum number of 
> fields that it can get away with adjusting (mostly the 
> sequence number) and then sends out the whole thing as a 
> series of packets. I believe that TCP options are copied into 
> each of the resulting packets. So the only way MPTCP can work 
> with offloading is if the MPTCP options can be identical in 
> multiple packets. So that means something like having a 
> second sequence number in a TCP option won't work. However, 
> this should be easily (?) fixable by encoding the second 
> sequence number as an offset towards the regular seqnum field 
> rather than a regular integer.

IMHO in this case the option is present in every packet. With TLV
encoding in 10G environments, there is one header every 64K (or,
whatever the maximum chunk size of payload encoding is).

I am no offloading expert, but there where some claims yesterday that it
would be much better if the option was only in the first segment of a
sequence number mapping range, because reassembly offloading on existing
cards will stop once it hits an unknown option. 

Note that putting the options in every packet adds some overhead (which
is small), but IMHO one also has to process every option in the
receiver, as it could contain another sequence number space mapping, and
I imagine that this results in cost.

But it would really help if someone familiar with offloading could
provide technical details on this.

Michael

---

From: Costin Raiciu <[email-masked]>
Date: Wed, 28 Jul 2010 10:39:36 +0200

Hi,

Regarding Michael's comparison of TLS chunking  and Multipath chunking, I think there is a fundamental difference between the two. TLS framing is roughly independent of the stack, and just uses it as a way to send a reliable bytestream. For MPTCP, the framing MUST be aligned with the segments on the wire, otherwise it just doesn't work.  For example, say my framing is (DATA_CHUNK,length=3000, blob). The kernel MUST NOT split this across two subflows! This is fundamentally different to TLS.

The big question for a userland mptcp is who puts the TLV encoding in. 

Solution 1. If it's the userland library, then the kernel MUST be aware of chunking, to only send full TLV chunks on any subflow. Otherwise,as I've said, if it splits different TLV chunks across different paths the re-ordering doesn't work. Considering that chunks have varying sizes (because app data has varying sizes) its unclear to me how the kernel can be forced to respect TLV boundaries without knowing what these are. So it seems that solution 2 is unavoidable.

Solution 2. The kernel inserts the TLV headers itself. There are two problems with this. First, as was pointed out, payload segmentation offload doesn't work with current cards. 
Second, on packet reception, the kernel has to parse the TLV stream, removing the TLV headers before passing data to the app. This has a big performance impact compared 
to today's stacks, that don't touch the payload at all: they just play with the control information. Seb's code does the same: it does not touch the payload. 

To summarize, it seems that a simple userland library to support multipath is not really possible. The kernel has to change quite a bit to support multipath. If we do the changes, we might as well get the performance too.

Cheers,
Costin

---

From: Joe Touch <[email-masked]>
Date: Wed, 28 Jul 2010 01:53:23 -0700

On 7/28/2010 12:41 AM, Iljitsch van Beijnum wrote:
> On 26 jul 2010, at 14:58,<[email-masked]>  <[email-masked]>  wrote:
...
> As I understand it, this offloading is often done using a simple but
> fast RISC CPU, so in theory the NIC could be programmed to perform any
> operation that can be performed sufficiently efficiently.
>
> In that regard, there is an issue with putting singaling in the data
> stream. I got two conflicting pieces of information out of yesterday's
> session: the information (always?) follows the TCP header, and it's like
> SSL, having its own framing that may or may not coincide with TCP
> segmentation.

Yes, we seemed to get two conflicting answers at first, but I think I 
now understand that the framing does NOT match the TCP segment boundaries.

> The former, where the MPTCP signaling always follows the TCP header,
> _should_ be workable if vendors are prepared to add multipath offloading
> to their NICs. The latter, I am going to speculate without having talked
> to these vendors, would be quite hard.

My view is that the offload engine is very likely going to NEED to run 
multiple levels of reassembly buffers:

	----> buf-1a -
                       \
	----> buf-1b --> buf-1 ----> user socket
                       /
	----> buf-1c -

AFAICT, for offloading, buf-1a, 1b, and 1c need to be on the NIC. Buf-1 
can share the space of the user socket (i.e., direct DMA of the final 
data), but only once already handled in the individual TCP streams.

IMO, this means that offloading is fine, but will definitely require 
larger buffers and more processing. I can't see how that isn't required 
in general anyway - even if all meta-info is in the option space. There 
may be some lower processing requirements, but otherwise it's just as 
much space and complexity AFAICT.

Joe

---

From: "SCHARF, Michael" <[email-masked]>
Date: Wed, 28 Jul 2010 11:37:12 +0200

Costin,

please read my draft. The protocol that I propose does not work in the
way you assume it to work.

As I mentioned before, there will be a live demo with running MCTCP code
next week, and I would have offered a live demo in the workshop on
Saturday, too, if I had given a timeslot for talking about my MCTCP
implementation.

I am very willing to discuss efficiency, overhead, etc. of a user-space
vs. kernel-space solution, and draft-scharf-mptcp-mctcp contains a
section that explains possible downsides of a user space solution (e.
g., scheduling granularity). I am not at all claiming that this is the
best solution, but it has some interesting properties, too.

> Regarding Michael's comparison of TLS chunking  and Multipath 
> chunking, I think there is a fundamental difference between 
> the two. TLS framing is roughly independent of the stack, and 
> just uses it as a way to send a reliable bytestream. For 
> MPTCP, the framing MUST be aligned with the segments on the 
> wire, otherwise it just doesn't work.

MCTCP only requires a reliable bytestream, like TLS. If the framing is
not alined, reassembly at the sender and parsing may be more complex.
True. Why should this not work?

Note that, even with option encoding, complex operations will also be
needed if the boundary of a sequence number mapping in a TCP option lies
within a TCP segment.

For example, say my 
> framing is (DATA_CHUNK,length=3000, blob). The kernel MUST 
> NOT split this across two subflows! This is fundamentally 
> different to TLS.

True. MCTCP does not do such spliting. So, what is the point?

> Solution 1. If it's the userland library, then the kernel 
> MUST be aware of chunking, to only send full TLV chunks on 
> any subflow. Otherwise,as I've said, if it splits different 
> TLV chunks across different paths the re-ordering doesn't 
> work. Considering that chunks have varying sizes (because app 
> data has varying sizes) its unclear to me how the kernel can 
> be forced to respect TLV boundaries without knowing what 
> these are. So it seems that solution 2 is unavoidable.

No. If the user land library does all TLV handling, the kernel just sees
a byte stream on each subflow. Like in TLS. Scheduling is done in the
user land.

That is all described in draft--scharf-mptcp-mctcp.

> Solution 2. The kernel inserts the TLV headers itself. There 
> are two problems with this. First, as was pointed out, 
> payload segmentation offload doesn't work with current cards. 
> Second, on packet reception, the kernel has to parse the TLV 
> stream, removing the TLV headers before passing data to the 
> app. This has a big performance impact compared to today's 
> stacks, that don't touch the payload at all: they just play 
> with the control information. Seb's code does the same: it 
> does not touch the payload. 

Payload encoding does have to touch the payload neither. It just has to
prepend a TLV header. In case of a kernel-level MCTCP implementation,
the most simple thing would be to send the TLV header in a first
segment, and do offloading of the chunk for the rest (remember: this can
be 64K in the current spec, and we may even increase this for 10G).

If the byte stream is received that way, parsing is very simple, too.

Of course, in some cases resegmentation may occur, and then the
reassembly overhead increases. But this applies to option encoding, too.

> To summarize, it seems that a simple userland library to 
> support multipath is not really possible. The kernel has to 
> change quite a bit to support multipath. If we do the 
> changes, we might as well get the performance too.

You can see such an "impossible" library in live next week in the
Euroview 2010 workshop. As I mentioned before, It uses a stable Linux
kernel patch with about 800 lines of code.

I can show the code to everyone who has doubts.

Michael

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 28 Jul 2010 11:40:44 +0200

On 28 jul 2010, at 10:39, Costin Raiciu wrote:

> If it's the userland library, then the kernel MUST be aware of chunking, to only send full TLV chunks on any subflow. Otherwise,as I've said, if it splits different TLV chunks across different paths the re-ordering doesn't work.

I don't think it's _that_ bad. The problem with the data frames stradling TCP segments would be that data will have to be transmitted unnecessarily. If we assume that most retransmissions are going to happen on the original subflow, that's almost a non-issue. However, if retransmissions are often going to be on a different subflow, this could get annoying. So how bad this is depends on the retransmission policy and real-world circumstances.

> Considering that chunks have varying sizes (because app data has varying sizes) its unclear to me how the kernel can be forced to respect TLV boundaries without knowing what these are.

Right. This would work much better over DCCP than over TCP.

> to today's stacks, that don't touch the payload at all:

That's just semantics. Effectively, this would just be an extension to the TCP header. The problem that I worry about in this case though, is all the middleboxes that look at the data, and may even perform resegmentation.

> To summarize, it seems that a simple userland library to support multipath is not really possible. The kernel has to change quite a bit to support multipath. If we do the changes, we might as well…

No, I think this can work. Although the TCP reliability means that if you lose packets the subflow is stuck until those packets are retransmitted. A rather blunt solution to this (other than modifying the kernel to allow skipping data in TCP or using DCCP rather than TCP) would be to set up a pool of backup subflows that remain idle until a currently used subflow gets stuck. The stuck subflow is then terminated and packets are (re)transmitted over a fresh one.

Michael: SSL offloading is concerned about the crypto, not so much on the pure data flow performance. I doubt SSL framing, even without any crypto, is going to be as fast as native TCP the same way I doubt SCTP will perform as well as TCP.

Richard: we don't have to worry about reordering, because to the NIC the different subflows will look like different sessions. One way to be compatible with existing offloading NICs could be to include the MPTCP options only once every few segments (if the NIC can at least do the vectored I/O you describe in the sending direction).

About the data ACK: why not have two versions of this, a cumulative and a non-cumulative version.

---

From: Joe Touch <[email-masked]>
Date: Wed, 28 Jul 2010 02:42:31 -0700

Hi, all,

Based on yesterday's discussion, and some discussion afterwards (esp. w/ 
Marcelo), here is my view:

1) there are, as noted, different types of meta-information, each of 
which needs to decide independently where it belongs

2) IMO, this acts a LOT like multi-layer TCP:

     as per the arch doc:
	c = connection = E2E single bytestream
	s = subflow = individual TCP connection seen on the Internet

     then the packets *effectively* look like this:

         +----------+-----------+----------+-----------+---------------+
	| s-TCPhdr | s-TCPopts | c-TCPhdr | c-TCPopts | ...payload... |
         +----------+-----------+----------+-----------+---------------+

Note - some of the c- metainfo is already contained in the s-options, 
i.e., the c-header port pair is basically the connection ID in the 
s-option. As a result, the c- header info is:

	connection ACKs (from the c-header)
	connection options (from the c-header)

All of this is currently c- metainfo.

Obviously, s- signals should go in s- headers.

Right now, the s- metainfo (hdr/opt) are the only TCP headers, and the 
c- metainfo are the ones we're embedding in the data plane in TLV 
encoding. The alternative, to assume that the c- metainfo are 
segment-aligned, does not seem feasible due to rewriting NATs, etc.

The question is really about the c- signals. It seems like most ought to 
go in the c- header location - i.e., in the data plane. However, the 
reality is that these signals are NOT all needed reliably.

So, in some sense, there ought to be separate channels

	TCP subflows for the subflowdata

	UDP channels for the connection signals

UDP because the connection signals are NOT needed reliably or in order - 
as with most TCP signaling. So putting it inside a TCP subflow ends up 
creating a blocking problem.

3) the conclusion is that all of the c- header and options info need to 
be in the s-options space

	that's the only UDP-like, unordered, unreliable place to put it

So this is really about the fact that the c- metainfo NEEDS to be in an 
unordered, unreliable stream, and that the alternatives are:
	
	a separate UDP channel (which won't work through some NATs)

	piggybacking on the s- metainfo

I.e., the c- metainfo IS c-level, but is placed at the s-level ONLY 
because of this reason.

Joe

---

From: Robert Watson <[email-masked]>
Date: Wed, 28 Jul 2010 11:03:47 +0100 (BST)

On Wed, 28 Jul 2010, Iljitsch van Beijnum wrote:

> As I understand it, this offloading is often done using a simple but fast 
> RISC CPU, so in theory the NIC could be programmed to perform any operation 
> that can be performed sufficiently efficiently.

I think this point shouldn't be oversold: there are fundamental execution 
environment differences between your general-purpose OS of choice and the NIC 
offload environment.  A critical one is information availability: if you are 
using TCP multipath and using multiple NICs, individual NICs see only the 
information sent out of them.  For simple offload techniques such as TSO on a 
single flow, they are currently stateless, as any information required (MSS) 
can be passed down with each packet quite efficiently.  Sometimes, additional 
information to simplify silicon is passed down: for example, several cards I'm 
aware of expect the OS to pass down an offset to TCP payload data so that the 
silicon doesn't have to perform TCP option parsing on transmit.

Consider the proposal under discussion to add CRC verification in order to 
detect badly behaved middle nodes.  These resemble, in some ways, the existing 
offload of ethernet, IP, and TCP checksums, and it's likely similarly 
desirable to offload them.

To recap, checksum offload helps because:

(1) On cache-weak architectures, checksums are computationally expensive, and 
offload provides both asynchrony and parallelism not otherwise afforded by the 
host CPU.

(2) On cache-strong architectures, payload data lines are processed by the NIC 
anyway, so cache misses on the payload can be avoided in the host OS network 
transmit path, which is normally significantly asynchronous (perhaps even on 
another core) from the original data send (where the data might or might not 
still be in the cache).

The information availability problem might arise if the data to CRC isn't 
well-aligned with packets being exposed to the NIC.  How will the NIC geneate 
the checksum to put in header, and how will it validate the checksum it 
receives if only some of the data covered by the checksum is present?  You 
could imagine a (very carefully thought out) use of intermediate CRC-32 
results that pass around the current data offset relative to the block so that 
the right CRC constant table locations are used, and in which the host OS is 
responsible for combining the intermediate results.

Hence my question during the workshop on Saturday: how well-handled will 
middle nodes that don't transform data, but do resegment data?  These nodes 
exist in moderate quantity, and in some ways are quite desirable -- despite 
the appearance of doing "more" work (resegmenting), they're likely making 
efficient use of the resources they have (offload, but also memory) during 
processing.  A typical application might be a firewall running an automata 
over the TCP data stream in order to detect bad things, FYI.

Today, this is no problem, as the receiving node will get valid TCP checksums 
generated by offload on the middle node; however, if resegmentation causes 
higher-level MP-TCP CRCs to be misaligned with respect to payload data 
delivered in segments, you may not be able to offload CRC-32 verification on 
the receiving MP-TCP end node.  This in turn might lead to a massive cache 
miss rate in inbound network processing for the receiving network stack, as it 
pulls in all packet cache lines prematurely in order to validate the CRC-32 
that hardware couldn't help with.

One thing I find quite appealing about the proposed userland variant on MP-TCP 
is that it would keep unoffloaded CRC-32 cache misses in the application, 
which is far more likely to be looking at the bytes in the payload shortly 
anyway, whereas most of the time the kernel input path would never take cache 
misses on payload data, it would just pass it by reference.

Which is to say: before cards support MP-TCP offload, any new CRC-32 
generation and validation has to involve a significant host CPU performance 
overhead.  This may be mitigated by moving it as close to access to that data 
as possible.  However, in the 3-5 year time range, if MP-TCP is successful, 
then elements of it could be offloaded, but only if they are designed in such 
a way as to allow that.  I don't think it's sufficient to say "anything we can 
do in the host CPU, we can do on the network card", because that may imply 
either moving significant amount of additional information that you might 
otherwise not, or worse, synchronous communication.

Robert

---

From: Costin Raiciu <[email-masked]>
Date: Wed, 28 Jul 2010 12:14:17 +0200

Michael,

Point taken. I had a different mental model about how the library would work. What you are saying is that the library effectively opens a few tcp connections with some special options in the SYN exchange, 
and schedules data on top. This should work, I agree.

With this solution, I am bit concerned about the performance of the overall connection when a subflow has bad performance and times out repeatedly. Ideally, you would like this not to affect the other subflow.
 
Say subflow A was sending some data chunk, and it timed out halfway through: only half of this data is acknowledged. Now, you need to send this
on the other subflows. The kernel can't do this when it times out on the subflow, even if it knew this is a multipath connection: it would also need to respect the TLV boundaries when moving data across, or insert new 
TLV boundaries. So the app must detect the failure and quickly move data across.

I see two possible solutions. Either the kernel notifies the app on each timeout (this means more kernel changes), or the app has much coarser timeouts to move data across. The second will work correctly, but will end
up getting very poor performance. How does your current code do this? Have you tested it with one subflow having repeated timeouts?

Another concern is packet-level delay. If your library effectively assigns data to subflows without knowing the current spare congestion window and RTT on that subflow, it could be that the choice is bad
and that data has to wait for a long time to be transmitted by the subflow. This will translate in much higher end-to-end packet-level delay, and the need to use much larger reordering buffers.
Sebastien has had a lot of trouble getting this to work correctly even in the kernel, just because what seems now like a good placement could turn out to be bad in the near future. Even with "perfect" 
RTT/cwnd information in the kernel it is difficult to get this right. Hence, he will now try to avoid assigning segments to subflows until the subflows can put the segments on the wire.

As a general note, I am fully convinced it is possible to correctly do payload encoding of MPTCP. However, I am also convinced it will be much more difficult (if not impossible) to get good performance out of this.  
Costin

---

From: "SCHARF, Michael" <[email-masked]>
Date: Wed, 28 Jul 2010 12:24:44 +0200

> > If it's the userland library, then the kernel MUST be aware 
> of chunking, to only send full TLV chunks on any subflow. 
> Otherwise,as I've said, if it splits different TLV chunks 
> across different paths the re-ordering doesn't work.
> 
> I don't think it's _that_ bad. The problem with the data 
> frames stradling TCP segments would be that data will have to 
> be transmitted unnecessarily. If we assume that most 
> retransmissions are going to happen on the original subflow, 
> that's almost a non-issue. However, if retransmissions are 
> often going to be on a different subflow, this could get 
> annoying. So how bad this is depends on the retransmission 
> policy and real-world circumstances.

True. Note that this issue is described in draft-scharf-mptcp-mctcp.

A user-land MCTCP implementation requires more time to retransmit a
missing piece of data on another subflow than a kernel-level
implementation.

If I correctly understand Sebastian's talk, the MPTCP kernel
implementation also tries to avoid this rescheduling due to the involved
cost.

> No, I think this can work. Although the TCP reliability means 
> that if you lose packets the subflow is stuck until those 
> packets are retransmitted. A rather blunt solution to this 
> (other than modifying the kernel to allow skipping data in 
> TCP or using DCCP rather than TCP) would be to set up a pool 
> of backup subflows that remain idle until a currently used 
> subflow gets stuck. The stuck subflow is then terminated and 
> packets are (re)transmitted over a fresh one.

Good point.
 
> Michael: SSL offloading is concerned about the crypto, not so 
> much on the pure data flow performance. I doubt SSL framing, 
> even without any crypto, is going to be as fast as native TCP 
> the same way I doubt SCTP will perform as well as TCP.

True, offloading motivation is different.

As a side note: AFAIK, the current payload encoding spec requires
checksums in the options for every sequence mapping to detect
content-length changing middleboxes.

Jana told me that, unlike described in my current spec, MCTCP actually
only requires a simple checksum covering the TLV header to detect all
content-length modifying middleboxes, which is way simpler.

I wonder if someone has ever thought about the complexity of calculating
the checksums in the MPTCP spec, without special offloading support for
MPTCP. And if there is any middlebox detection algorithm for options not
requiring such checksums.

Michael

---

From: "Ford, Alan" <[email-masked]>
Date: Wed, 28 Jul 2010 11:45:39 +0100

Michael, all,

> content-length modifying middleboxes, which is way simpler.

That is true.

> requiring such checksums.

The checksum of full data is probably relatively expensive (although I
have no numbers about this) and so we should still think about other
options that can achieve almost the same benefit. One suggestion that
arrived by email yesterday (and I was going to mention in the session
tomorrow) is that we could copy the first n bytes (4 being an obvious
number) of the start of the payload referred to by the DSN_MAP into the
DSN_MAP option itself, to ensure we are still in sync.

The last n bytes may be better, as that allows an error to be detected
before the start of the next data covered by the next DSN_MAP, however.
We could also checksum the last n bytes as another option, which may be
slightly more reliable.

Cheers,
Alan

---

From: "SCHARF, Michael" <[email-masked]>
Date: Wed, 28 Jul 2010 12:54:49 +0200

> With this solution, I am bit concerned about the performance 
> of the overall connection when a subflow has bad performance 
> and times out repeatedly. Ideally, you would like this not to 
> affect the other subflow.
>  
> Say subflow A was sending some data chunk, and it timed out 
> halfway through: only half of this data is acknowledged. Now, 
> you need to send this on the other subflows. The kernel can't 
> do this when it times out on the subflow, even if it knew 
> this is a multipath connection: it would also need to respect 
> the TLV boundaries when moving data across, or insert new TLV 
> boundaries. So the app must detect the failure and quickly 
> move data across.

True. Note the library can detect this as the local sequence number does
not move forward. It takes some time to detect this, because the library
must query this information from the kernel. Or it must receive a
connection-level SACK/NACK from the receiver, which may arrive faster if
the RTT is really small. But once the stall is detected, a user-land
solution can easily recover.

But, agreed, a difference between a user-space MCTCP implementation and
a kernel-level implementation of the current MPTCP protocol spec is that
a user-space solution cannot effectively retransmit few packets on
another subflow. I don't think that we frequently need this.

> I see two possible solutions. Either the kernel notifies the 
> app on each timeout (this means more kernel changes), or the 
> app has much coarser timeouts to move data across. The second 
> will work correctly, but will end up getting very poor 
> performance. How does your current code do this? Have you 
> tested it with one subflow having repeated timeouts?

The current implementation periodically queries the local sequence
numbers with a configurable time granularity (less than one second). Of
cource, retransmissions are limited by that time granularity.

> Another concern is packet-level delay. If your library 
> effectively assigns data to subflows without knowing the 
> current spare congestion window and RTT on that subflow, it 
> could be that the choice is bad and that data has to wait for 
> a long time to be transmitted by the subflow. This will 
> translate in much higher end-to-end packet-level delay, and 
> the need to use much larger reordering buffers.

The libary _roughly_ knows congestion windows and RTT, but not
necessarily the current value when data is scheduled.

And, true, there are cases where the decision on out-dated data will be
suboptimal. A user-land implementation comes at some cost, but it is
better than nothing.

> As a general note, I am fully convinced it is possible to 
> correctly do payload encoding of MPTCP. However, I am also 
> convinced it will be much more difficult (if not impossible) 
> to get good performance out of this.  

I agree that on lossy links the per-packet delay of a user-land MCTCP
implementation may not always be optimal, and be outperformed by MPTCP.
But, concerning throughput, it will efficiently do resource pooling. I
will try to provide throughput and per-packet delay values for MCTCP in
a future meeting, if this would somehow help.

But, again, a general comment: Please read my draft. I have been very
clear that MCTCP's design is optimized of transfer for large files
(>>1MB), where the individual packet delays do not matter that much, but
bandwidth aggregation reduces the overall completion time. If the key
optimization goal is doing VoIP over multiple paths, with minimal
per-packet delays, we might need indeed another protocol.

Michael

---

From: Olivier Bonaventure <[email-masked]>
Date: Wed, 28 Jul 2010 15:45:01 +0200

Michael,

> another subflow. I don't think that we frequently need this.

Last year, Jerry Chu reported some interesting measurements

http://www.ietf.org/proceedings/75/slides/tcpm-1.pdf

"TCP retransmit rate: 0.8% - 2.4%
measured at Google's frontend servers"

retransmissions are unfortunately not a very rare event.

Olivier

-- 
http://inl.info.ucl.ac.be , UCLouvain, Belgium

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 28 Jul 2010 17:04:20 +0200

On 28 jul 2010, at 12:03, Robert Watson wrote:

> Which is to say: before cards support MP-TCP offload, any new CRC-32 generation and validation has to involve a significant host CPU performance overhead.

I haven't been keeping up with the list, so maybe there are good reasons for all of this.

However, it seems to me that doing CRCs means MPTCP will be much, much slower than regular TCP in all but a few corner cases. That can't be our intended result.

On 28 jul 2010, at 12:21, Scheffenegger, Richard wrote:

> I haven't found the exact values of the chunk sizes used therein, but
> they are in the MB range... Thus MPTCP should allow chunks of that size,
> to run efficiently (making use of TSO / LRO) over existing HW.

That doesn't make much sense. This means that if there is a bit error in that multi-MB chunk you have to resend the whole thing. Which also means that you must buffer multiple of these chunks until they're ACKed. And the data is delivered to the app in a very bursty fashion.

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 28 Jul 2010 16:18:50 +0100

Hi Iljitsch,

Again, the sub-flows are supposed to be reliable transport. If we don't
trust the sub-flow transport for error free services, fixing this at the
MPTCP layer is the wrong place [IMHO]. (That needs to be addressed in
the TCP layer, see anumita's I-D for potential ideas :) Or FEC WG, ... 

For the scope of MPTCP, the assumption that the sub-flows are delivering
error free data should be kept, and no CRC-32C should be introduced at
that level (for all the reasons mentioned).

Sending multiple MB-sized chunks via different sub-flows in parallel
(both link level and CPU affinity) makes much sense from my point of
view, as it reduced CPU involvement as much as possible - actually it
"only" has to throttle the NIC's sending rate by not giving it too large
parts of a chunk; further on the receiving side, RSS and LRO can be used
at high efficiency (at the cost of buffer space, I agree - which is
plenty nowadays. If not, you can still reduce chunk size (MPTCP
negotiated option btwn TX / RX?).

Or did I miss something?

Thanks!

Richard

> -----Original Message-----
> From: Iljitsch van Beijnum [mailto:[email-masked]] 
> Sent: Mittwoch, 28. Juli 2010 17:04
> To: Robert Watson
> Cc: [email-masked]
> Subject: Re: [multipathtcp] Options vs payload & offload
> 
> > Which is to say: before cards support MP-TCP offload, any 
> new CRC-32 generation and validation has to involve a 
> significant host CPU performance overhead.
> 
> However, it seems to me that doing CRCs means MPTCP will be 
> much, much slower than regular TCP in all but a few corner 
> cases. That can't be our intended result.
> 
> 
> > they are in the MB range... Thus MPTCP should allow chunks of that 
> > size, to run efficiently (making use of TSO / LRO) over existing HW.
> 
> That doesn't make much sense. This means that if there is a 
> bit error in that multi-MB chunk you have to resend the whole 
> thing. Which also means that you must buffer multiple of 
> these chunks until they're ACKed. And the data is delivered 
> to the app in a very bursty fashion.
> 
> _______________________________________________
> multipathtcp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/multipathtcp
>

---

From: "SCHARF, Michael" <[email-masked]>
Date: Wed, 28 Jul 2010 17:26:03 +0200

> > But, agreed, a difference between a user-space MCTCP implementation 
> > and a kernel-level implementation of the current MPTCP 
> protocol spec 
> > is that a user-space solution cannot effectively retransmit few 
> > packets on another subflow. I don't think that we 
> frequently need this.
> 

Yes, of course. But from that we can still recover by retransmissions
within the subflow if it is active.

Retransmissions on another flow are only really _needed_ if the original
subflow is stalled or fails. My point was that this is scenario should
happen much more seldomly, unless paths are really dynamic. Of course,
in particular in combination with heterogeneous RTTs, there are cases in
which a retransmission on another subflow is actually better and reduces
packet delays - this is obvious.

Michael

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 28 Jul 2010 17:30:49 +0200

On 28 jul 2010, at 17:18, Scheffenegger, Richard wrote:

> Again, the sub-flows are supposed to be reliable transport.

No. Reliability means that you get stuck for retransmissions when data is lost. This makes the reliability of MPTCP the product of the reliability of the subflows, i.e., much smaller than the reliability of a single flow, such as 90%*90%=81%. If you can move retransmissions to another subflow on the other hand, you make the reliability the inverse of the products of the inverse of the reliability, such as 100%-((100%-90%)*(100%-90%))=99%.

> error free data should be kept,

This assuption was never there, so we can't keep it.

> view,

If you want to send many megabytes of data reliably over parallel flows, why not simply do this in your application over multiple TCP flows?

---

From: Olivier Bonaventure <[email-masked]>
Date: Wed, 28 Jul 2010 17:48:22 +0200

Alan,
> options that can achieve almost the same benefit. 

My main concern is that using a CRC on each chunk corresponding to a
DNS_MAP option forces the sender (and the receiver) to compute a CRC for
each chunk. This implies touching the data on the CPU of both the sender
and the receiver as the NICs do not support this CRC and will likely not
support it for some time.

Although there are middleboxes that change the payload of TCP segments
to replace ASCII-encoded IP addresses, the fraction of the TCP
connections that are affected by such middleboxes is probably very very
small. Forcing MPTCP to CRC all segments to discover such seldom events
look overkill to me.

> One suggestion that

The reason why I suggested this is that MPTCP does not need to check
that the data has been correctly transmitted without errors. MPTCP only
needs to detect that a bytestream has expanded or shrunk.

A middlebox that changes bytes in the bytestream would not break the
operation of MPTCP ( it could break the operation of the application
running above, but an application running over regular TCP would have
the same problem). MPTCP is only concerned if the middlebox changes the
bytestream and inserts additional bytes (and thus changes the sequence
numbering) or removes some bytes (and thus changes the sequence numbering).

There are several possible ways to have a lightweight DSN_MAP option
that is able to detect middleboxes that change the sequence numbering.

- a first solution that I proposed yesterday to Alan is to place inside
the DNS_MAP option the byte of the payload that is mapped by the DSN_MAP
option

                      1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +---------------+---------------+------------------------------+
      | Kind=DSN_MAP  |    Length     |     Data Sequence Number ... :
      +---------------+---------------+------------------------------+
      : ... ( (length-12) octets )    | Data-level Length (2 octets) |
      +-------------------------------+------------------------------+
      |              Subflow Sequence Number (4 octets)              |
      +--------------------------------------------------------------+
      |  Mapped byte  |
      +---------------+

This reduces the size of the DSN_MAP option and from an implementation
viewpoint, extracting this byte from the payload is much simpler and
faster than computing a CRC over the entire mapped region.

A drawback of this approach is that since a single byte is included in
the option, there is no guarantee that the receiver will detect
immediately the change in the sequence numbering.

- a second solution mentionned by Alan is to map the n bytes (say 4
bytes) that precede the mapped byte. Using the last n bytes allows the
receiver to detect a problem in the previous segment.

                1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +---------------+---------------+------------------------------+
      | Kind=DSN_MAP  |    Length     |     Data Sequence Number ... :
      +---------------+---------------+------------------------------+
      : ... ( (length-12) octets )    | Data-level Length (2 octets) |
      +-------------------------------+------------------------------+
      |              Subflow Sequence Number (4 octets)              |
      +--------------------------------------------------------------+
      |  		Last four bytes of bytestream		     |
      +--------------------------------------------------------------+

Putting 32 bits increases the size of the option and also the
probability of quickly detecting middleboxes that change sequence numbers.

A corner case that we need to consider is the first DSN_MAP option that
is sent on a connection. Since no byte has been sent, the sender cannot
refer to these bytes in the DNS_MAP option.

- a third solution is to use a checksum over the last N bytes of the
bytestream and place the computed checksum inside the option. This
increases the probability of detecting middleboxes, but also the cost on
the sender and the receiver sides.

           1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +---------------+---------------+------------------------------+
      | Kind=DSN_MAP  |    Length     |     Data Sequence Number ... :
      +---------------+---------------+------------------------------+
      : ... ( (length-12) octets )    | Data-level Length (2 octets) |
      +-------------------------------+------------------------------+
      |              Subflow Sequence Number (4 octets)              |
      +--------------------------------------------------------------+
      |     Checksum of the last n bytes of bytestream		     |
      +--------------------------------------------------------------+

A last point that I would like to mention is that AFAIK, such
middleboxes only exist in IPv4 today. It might be useful to consider
that when an MPTCP connection is running over IPv6, it does not need to
detect middleboxes that change the bytestream. If we allow the DNS_MAP
to have a variable length, the DNS_MAP option could include 0 bytes of
the bytestream when used over IPv6

Best regards,

Olivier

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 28 Jul 2010 17:01:19 +0100

Hi Iljitsch,

> Sent: Mittwoch, 28. Juli 2010 17:31
> To: Scheffenegger, Richard
> Cc: Robert Watson; [email-masked]
> No. Reliability means that you get stuck for retransmissions 
> when data is lost. This makes the reliability of MPTCP the 
> product of the reliability of the subflows, i.e., much 
> smaller than the reliability of a single flow, such as 
> 90%*90%=81%. If you can move retransmissions to another 
> subflow on the other hand, you make the reliability the 
> inverse of the products of the inverse of the reliability, 
> such as 100%-((100%-90%)*(100%-90%))=99%.

I refer to reliability when it comes to payload errors; Perhaps
resiliency would have been a better word.

In any case, my point was, that no CRC-32C (or CRC64, or FEC) will be
required on the MPTCP layer.

Stability and timeliness are the concerns you just seem to describe,
which are orthogonal.

> 
> > For the scope of MPTCP, the assumption that the sub-flows are 
> > delivering error free data should be kept,
> 

Well, MPTCP runs over a sub-flow protocol which looks alike TCP on the
sub-flow level. In order to "look-alike" TCP on a sub-flow level as much
as possible, in order to don't break current gear, wouldn't it make
sense to not only look-alike TCP, but *be* TCP (including segment CRC
checks, sub-flow individual retransmissions (ACK/SACK) ). The only
adjustment will be the effective TCP congestion control scheme - which
doesn't change the signaling (so on the wire, it'll still look like TCP,
right?). 

> If you want to send many megabytes of data reliably over 
> parallel flows, why not simply do this in your application 
> over multiple TCP flows?

App-specific implementations do exist, and do work reasonably welll
within their scope. 

However, breaking the semantics of TCP will definitely break MPTCP when
running over certain middleboxes I'm concerned about in the area which
is relevant the most from my point of view (firewalls, AV, proxys in
commercial private networks) - whenever the "usual" TCP semantics are
broken, it's asking for problems.
And I would think, that in the commercial, private networks, such
devices are *MUCH* more common than in the public internet - to the
point that any TCP semantic violations will lead to sub-flows getting
forcefully broken all the time. And also to the point, that very few
sessions are actually NOT crossing such a device...

I don't know if one of the devices tested by Yoshifumi Nishida was
actually some kind of stateful, inspecting firewall as you'd typically
find between an intranet and a DMZ. 

Let's discuss this over dinner.

Rgds,
   Richard

---

From: Robert Watson <[email-masked]>
Date: Wed, 28 Jul 2010 17:33:22 +0100 (BST)

On Wed, 28 Jul 2010, Iljitsch van Beijnum wrote:

>> overhead.
> However, it seems to me that doing CRCs means MPTCP will be much, much 
> slower than regular TCP in all but a few corner cases. That can't be our 
> intended result.

While I agree with the point your making, I think it is useful to observe that 
hardware vendors have been dropping CRC offload support into their NICs for a 
bit anyway.  In fact, I believe Intel just added it to their product line to 
support SCTP checksum offload.  So as long as we can make the CRC accessible 
to offload acceleration, I'm not sure it's such a big deal in practice 
(especially if it can be made optional for loopback and other "exempt" 
situations).

NB: many loopback TCP implementations now exploit the same mechanism provided 
for hardware offload to avoid regular TCP checksums generation, verification, 
or both, over loopback interfaces.

Robert

---

From: Robert Watson <[email-masked]>
Date: Wed, 28 Jul 2010 17:43:33 +0100 (BST)

On Wed, 28 Jul 2010, Scheffenegger, Richard wrote:

> running over certain middleboxes I'm concerned about in the area which is 
> relevant the most from my point of view (firewalls, AV, proxys in commercial 
> private networks) - whenever the "usual" TCP semantics are broken, it's 
> asking for problems. And I would think, that in the commercial, private 
> networks, such devices are *MUCH* more common than in the public internet - 
> to the point that any TCP semantic violations will lead to sub-flows getting 

My (opiniated) view is that the only argument for MP-TCP over, say, multipath 
SCTP, is the practical adoption path: we can get it over the Internet (and the 
commerical private networks you mention) as-is today.  This suggests (to me) 
that wherever possible, MP-TCP must make pragmatic design choices that 
maximize the success of getting it into deployment despite standards bodies, 
OS vendors, NIC vendors, network operators, and especially nefarious middle 
nodes.  Any design choice supported by "they will have to change the middle 
boxes" loses. :-)

Robert

---

From: Mark Handley <[email-masked]>
Date: Wed, 28 Jul 2010 17:47:44 +0100

Just to add an extra data point:

Our goal was to fall back to regular TCP behaviour in the presence of
middleboxes that change the payload length.  The advantage of a
checksum is that you don't pass any changed data up to the app if the
checksum fails.  You then fallback to regular TCP behaviour, and the
middlebox gets to play again doing whatever it was it was trying to
do.

Checksums are very robust for this role, and protect against a whole
set of possible confusions that can happen for middleboxes.  For
example, two consecutive segments on a subflow using options encoding
could actually be quite a way apart in the data flow, but could
trigger a false rewriting by a middlebox.  Similarly, with payload
encoding, the TLV header itself or the concatenation of the TLV and
payload could trigger a false rewriting by a middlebox.  It doesn't
really matter if we use payload or options encoding, we really can't
trust any rewriting behaviour by a middlebox when we're using multiple
paths.  Checksums will catch all of this, not just length changes.
And they'll trigger fallback to regular TCP behaviour safely without
passing potentially bad data to the application.

I've spent a lot of time thinking about alternatives to checksums.  My
conclusion is that checksums are the only robust way to do this.  The
performance penalty is probably negligible for a great deal of wide
area traffic, simply because most applications are not limited by
this.  For those where there is a non-negligible performance penalty,
I would expect one of several options to apply:

 - disable MP-TCP.
 - disable MP-TCP for any app that is likely to be rewritten (hint:
there aren't many).
 - disable checksums for any app that is unlikely to be rewritten
 - deploy a NIC that supports MP-TCP TSO once they become available.

All of this is really only an issue on busy servers.

For datacenter deployment, I would expect the OS to configure
checksums off by default for all traffic to local destinations.  So
this wouldn't be an issue there.

To summarise:  checksums are only an issue for a relatively small
number of very busy wide-area servers running relatively few
applications, and we can live with MP-TCP being disabled for those
servers until the next generation of smart NICs come along.

 - Mark

---

From: "Ford, Alan" <[email-masked]>
Date: Wed, 28 Jul 2010 18:25:20 +0100

Checksums of the data are undoubtedly the only way to reliably ensure that data is not changed.

However, whether this is really what we want depends to some extent on what the impact we are trying to protect against is, and what the boxes do. I'm not sure we need them.

We don't want to stop boxes doing these changes to the payloads, we just lost alignment in MPTCP if they change length. The corner case you say when two neighbouring segments of data on a subflow trigger a change over the boundary is the main non-length-changing case.

To take the idea of copying payload bytes as suggested by Olivier and me, this would protect against middleboxes that shorten or lengthen the data with a change. We can use this to discard the data and fallback, or (for further study) may even be able to learn the subflow sequence number adjustment and carry on.

The problem is a false hit on data spanning a boundary. The last 4 bytes would catch this if the change occurred over the boundary, however it would not catch it if it is only on data that is in the later segment (but triggered due to data at the end of the earlier segment). This is a very specific corner case and one that I'm not convinced would actually cause any problems. If we cared, we could protect against it by having the first 2 bytes and last 2 bytes of each segment in the DSN_MAP (or the XOR of the first and last 4 bytes, or something like that), and that would work.

Are there any cases where copying bytes would be worse than checksums?

Alan

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Mark Handley
> Sent: 28 July 2010 17:48
> To: [email-masked]
> Cc: Ford, Alan; [email-masked]; SCHARF, Michael
> Subject: Re: [multipathtcp] Kernel changes need for payload encoding
>

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 28 Jul 2010 19:44:32 +0200

> servers until the next generation of smart NICs come along.

Special cases requiring different behavior invariably turn out problematic.

One approach to checksumming would be to carry a second copy of the checksum, which the middlebox won't know about and thus will not update when it mangles the packet. On the receiving side checking whether the TCP checksum and the MPTCP checksum are the same is basically free (there is a tiny bit of overhead if the session is NATed but not enough to worry about). On the sender side, the second checksum is also free if the first is computed in software. In the offloading case today's NIC won't know to make a copy of the checksum so offloading would have to be disabled until NICs know how to insert a second copy of the checksum.

I guess it would be possible to only do the second checksum for the first n packets and if nothing bad happens to those packets (and other sessions in the past have also been ok) disable the checksum for increased performance.

---

From: Robert Watson <[email-masked]>
Date: Wed, 28 Jul 2010 18:47:20 +0100 (BST)

> - deploy a NIC that supports MP-TCP TSO once they become available.

Checksums generate work at both send and receive endpoints (and, I guess, 
active middle nodes), so we need to make sure that any checksum integration 
can be offloaded at both endpoints.

For the benefit of the ignorant such as myself: is the middle node problem of 
deciding whether it has "complete" visibility into MP-TCP any harder than the 
problem of deciding if it has complete visibility into regular TCP?  How 
should an MP-TCP-aware middle node, perhaps even as simple as an in-NIC 
NAT/firewall/etc, behave in the presence of these CRCs, etc?

Robert

---

From: Mark Handley <[email-masked]>
Date: Wed, 28 Jul 2010 18:59:21 +0100

> One approach to checksumming would be to carry a second copy of the checksum, which the middlebox won't know about and thus will not update when it mangles the packet. On the receiving side checkin…

My assumption is that doing a CRC32 is also pretty much free on modern
hardware if you're doing the TCP checksum in software.  The real cost
is getting the data into the CPU cache.  Crunching a checksum or even
two checksums costs you very little.  Need to verify this is true
though.

One nice thing about not reusing the TCP checksum (which included the
pseudoheader) is we can checksum multiple segments at once, which
means we should still be able to use TSO to mitigate interrupts/DMA
transfers.

So it's not clear to me that we would want to reuse the TCP checksum,
even if NATs didn't confuse the issue.

 - Mark

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 28 Jul 2010 20:10:40 +0200

On 28 jul 2010, at 19:59, Mark Handley wrote:

> is getting the data into the CPU cache.

Hm, for a desktop CPU that's probably true but don't forget we also want to run MPTCP on much less capable devices.

I don't think it makes sense to use a CRC32 unless we need the extra strength.

You're also making a big assumption that the regular TCP checksum and the new CRC can be done in the same loop, or in loops so close together that the whole segment is still in the cache.

> means we should still be able to use TSO to mitigate interrupts/DMA

I don't understand.

Note that AFAIK a CRC can't be computed in any way other than front to back, while a one's complement checksum can be modified incrementally or be created by checksumming the checksums of different parts of the data that together make up the entire thing.

> even if NATs didn't confuse the issue.

As I wrote, NAT confusion is minimal as there is a fixed offset between the original TCP checksum and the one after NATing, so once we know this value we can just cache it and apply it to the copy of the checksum and get the same value as the first checksum updated by the NAT.

---

From: "Biswas, Anumita" <[email-masked]>
Date: Wed, 28 Jul 2010 11:19:16 -0700

> Sent: Wednesday, July 28, 2010 11:11 AM
> To: Mark Handley
> Cc: [email-masked]; SCHARF,Michael; 
> [email-masked]
> Subject: Re: [multipathtcp] Checksumming and offloading
> 
> 
> Hm, for a desktop CPU that's probably true but don't forget 
> we also want to run MPTCP on much less capable devices.
> 
If the bit error rates are higher than 10^-4 , we do need a stronger TCP
checksum - especially at jumboframe sizes.
http://tools.ietf.org/id/draft-anumita-tcpm-stronger-checksum-00.txt

> 
> You're also making a big assumption that the regular TCP 
> checksum and the new CRC can be done in the same loop, or in 
> loops so close together that the whole segment is still in the cache.
> 
> Note that AFAIK a CRC can't be computed in any way other than 
> front to back, while a one's complement checksum can be 
> modified incrementally or be created by checksumming the 
> checksums of different parts of the data that together make 
> up the entire thing.
> 
> As I wrote, NAT confusion is minimal as there is a fixed 
> offset between the original TCP checksum and the one after 
> NATing, so once we know this value we can just cache it and 
> apply it to the copy of the checksum and get the same value 
> as the first checksum updated by the NAT.
>

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 28 Jul 2010 20:25:21 +0200

> checksum

That's one flipped bit in 10000, which means that almost half of your packets will have a bit error.

Packets already have a CRC32 in them, it's just at the link layer rather than the transport layer.

Wired networks (which are the only ones with jumboframes) have BERs of 10^-10 or better.

If a stronger checksum is required in the general case it should be built into TCP proper, not just multipath TCP.

---

From: Robert Watson <[email-masked]>
Date: Wed, 28 Jul 2010 19:29:59 +0100 (BST)

On Wed, 28 Jul 2010, Mark Handley wrote:

> hardware if you're doing the TCP checksum in software.  The real cost is 
> getting the data into the CPU cache.  Crunching a checksum or even two 
> checksums costs you very little.  Need to verify this is true though.
>
> pseudoheader) is we can checksum multiple segments at once, which means we 
> should still be able to use TSO to mitigate interrupts/DMA transfers.
>
> So it's not clear to me that we would want to reuse the TCP checksum, even 
> if NATs didn't confuse the issue.

The CRC-32 checksum is only "free" for cache-rich systems if the data was in 
the cache anyway at the point of generation or validation.  There are a few 
processing points when that's true:

- certainly when the data is generated or processed in userspace

- perhaps if/when the data is copied into/out of the kernel (this may not
   happen sendfile(2), for example, may never bring in the data cache lines)

- certainly when the data is checksummed by the ethernet hardware for frame
   receipt/transmit

This is one of the reasons why hardware checksum offload for TCP is so helpful 
even on modern hardware: TCP checksum calculation depends on having selected a 
segmentation strategy, and normally for steady-state transmitting streams, 
that strategy is only selected very late in the above sequence: at the point 
where we're processing an ACK and know what's up with the remote window.  But 
that point is not one of the ones in the above list, so the payload data lines 
may well not be in the cache.

By offloading, we eliminate cache misses during segmentation (and perhaps 
segmentation itself with TSO) and shift that to the card which will have the 
bytes in-hand anyway.  This is because contemporary kernels do a very good job 
at avoiding data copying, working mostly with data by reference for 
high-volume streams.  If CRC generation / validation can't happen at one of 
the in-cache points above, or in hardare, then it should be very measurable 
because it will fault in all the cache lines at significant cost.  The 
userspace MP-TCP implementation might be able to do it "at generation" or "at 
receipt", which is an interesting option, but doesn't apply to zero-copy send, 
where the data may normally never enter any general-purpose CPU's cache.

On low-cache/cacheless systems, especially embedded ARM-style processors, 
instructions are definitely not free, so I'd guess you could measure not only 
the performance hit, but also additional power-use.  That's just a hand-wave, 
and would be good to verify through measurement as well.

Robert

---

From: Robert Watson <[email-masked]>
Date: Wed, 28 Jul 2010 20:16:05 +0100 (BST)

> processing points when that's true:

Just to clarify this point slightly, I mean that the data is conveniently 

> - certainly when the data is generated or processed in userspace

The general-purpose core doing the generation or processing.

>  happen sendfile(2), for example, may never bring in the data cache lines)

The core doing the copying into or out of the kernel.

> - certainly when the data is checksummed by the ethernet hardware for frame

The offload engine in the ethernet device, be it hard silicon, perhaps a MIPS 
core (or many MIPS cores) embedded in the ASIC, or something else.

Robert

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 28 Jul 2010 23:58:19 +0100

Hi Robert,

> From: Robert Watson [mailto:[email-masked]] 
> Sent: Mittwoch, 28. Juli 2010 18:33
> To: Iljitsch van Beijnum
> While I agree with the point your making, I think it is 
> useful to observe that hardware vendors have been dropping 
> CRC offload support into their NICs for a bit anyway.  In 
> fact, I believe Intel just added it to their product line to 
> support SCTP checksum offload.  So as long as we can make the 
> CRC accessible to offload acceleration, I'm not sure it's 
> such a big deal in practice (especially if it can be made 
> optional for loopback and other "exempt" 
> situations).
> 
> NB: many loopback TCP implementations now exploit the same 
> mechanism provided for hardware offload to avoid regular TCP 
> checksums generation, verification, or both, over loopback interfaces.
> 
> Robert
> 

Let me comment a bit on the CRC offloading part.

A) [personal opinion] it's not necessary to run payload protection of
data with MPTCP. That should be a function of the transport protocol (be
it TCP, SCTP, DCCP, ...)

B) CRC offloading in hardware does work - but only on a per-segment
basis. I don't know a TOE / NIC, that will keep state of CRC for 1) only
payload and 2) across multiple frames. Albeit the latter one could
probably be addressed by a pre-load of the CRC field with some non-zero
number.

C) Intel did add SCTP CRC32C - but again, that will cover the entire
transport segment, and the CRC will be placed at a fixed position in the
resulting stream of segments. Not in the options or data part.

Due to A) I would like to come back as to why this should be necessary
in the first place.

If a middlebox really chooses to do something strange with the payload,
MPTCP fails - however, MPTCP should fail safely, reverting back to
standard TCP and recovering the missing DATA... (even if it is then
still munched; but some X-Header added or removed wouldn't break, say, a
HTTP session over TCP, while they would over MPTCP.

Signalling like PUSH and MPTCP Options can be used for marking the begin
and and of a MPTCP sub-flow chunk (to detect the munching in the MPTCP
subflow. That would further alleviate the question of having TLVs in the
data stream - even though MPTCP subflows failing due to middleboxed not
knowing what to do with TLVs should again fail savely back to standard
TCP.

Having that said, I uphold my position, that not fiddling with the
semantics of TCP at the subflow level is key in making MPTCP performant
(using current generation hardware) and compliant (with middleboxes that
don't care about funny options, but the payload; ie. Stateful firewalls
with AV capabilities. That reminds me that this is a security concern
(evil data could be smuggled in by spreading it via small chunks over
many different subflows, so that it's not detectable by current
Firewalls).

Regards,
   Richard

---

From: "Pat Thaler" <[email-masked]>
Date: Wed, 28 Jul 2010 16:02:52 -0700

The argument for using the Castagnoli polynomial as suggested by the ID, draft-anumita-tcpm-stronger-checksum-00.txt, is misguided. 

It assumes that the choice of polynomial should be based on the Hamming distance of the polynomial. 

If bit errors were random independent events, this would be true. In that case, the probability of n errored bits in a message would be approximately BER^n, where BER is the bit error ratio. Each increased bit of Hamming distance dramatically reduces the probability of an error larger than the Hamming distance occurring. 

However, bit errors are not random independent events. As a matter of fact, the worse the physical channel, the more we apply techniques at the physical layer to improve performance over that channel such as signal processing (e.g. forward error correction, digital signal processing) and error correction algorithms. The signal processing reduces the number of errors by correcting for the problems of the channel but since the recovered bits are used for the processing of the later bits, when an error occurs it often produces a burst of errors. The error correction algorithms correct when single or small numbers of bit errors occur but when too many errors occur the wrong correction may be applied with the result containing multiple errors. 

Therefore, Hamming distance shouldn't be the measure used to chose between polynomials.

Secondly, the Castignoli polynomial has a factor of x+1. This is a way to increase Hamming distance. If you have a degree n-1 polynomial that has a Hamming distance of m where m is an even number and you multiply that polynomial by x+1, the resulting degree n polynomial will have a Hamming distance of m+1 because the x+1 factor detects all cases with an odd number of bit errors (i.e. it is a parity check). Again if single bit errors were independent random events, this might be a good thing, but in real use it can decrease error detection because of a hidden cost.

The factor x+1 means that the polynomial will detect all odd bit errors at the cost of doubling error escapes for even numbers of bit errors. If one uses a degree 32 primitive polynomial like the Ethernet CRC, the error detection for errors over the Hamming distance will be 1 - 2^-32 regardless of whether the number of errors was odd or even. When you use a degree polynomial, the error detection is 100% for odd numbers of bit errors at the cost of reducing error detection for even numbers of bit errors to 1 - 2^-16. 

Because of the encodings used, some physical layers are more likely to produce bit errors in pairs. Also, some physical layers detect all packets with odd numbers of bit errors (e.g. the 8B/10B code used in Fibre Channel and Ethernet) and cause a packet discard. Some error detection mechanisms that operate while data is in memory or going over busses inside equipment also favor detection of odd numbers of bit errors. 

Therefore, it is unwise to use a higher layer error detection that favors detection of odd numbers of bit errors while weakening detection of even numbers of bit errors.

---

From: "Robert N. M. Watson" <[email-masked]>
Date: Thu, 29 Jul 2010 00:15:29 +0100

> many different subflows, so that it's not detectable by current

Sounds like we agree pretty much entirely.

I wonder if it would make sense to think a bit more about how MP-TCP-aware middle nodes, especially ones acting to filter multiple ingress/egresses for a site, might behave. In historic TCP land, the usual choice has been between getting a bit in the way but not too much (packet filter-oriented approach, perhaps with transforms, pattern matching, etc), and terminating the TCP connection and building a new one onto the end host (traditional proxy-oriented firewall approach), which causes reassembly, buffering, etc, to take place, but tolerates more complex transforms more easily. Do we see that same split continuing with MP-TCP, and if so, how do we anticipate firewalls interacting? Might they have policy regarding the use of redundant paths?

To what extent can they/should they/must they preserve scheduling selected by the original transmitter? I suppose for packet filters, we take a low-overhead "don't mess with it" approach, perhaps made a fair amount more difficult because of the need to track the different flows, etc, and for proxies, we assume that we continue to have to effectively terminate the connection, which might confuse applications that think that connections (and hence subflow) properties are end-to-end...

Robert

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 29 Jul 2010 00:15:04 +0100

> Sent: Mittwoch, 28. Juli 2010 20:11
> To: Mark Handley

Note that if you want to run a CRC over a large dataset, your hamming
distance will suffer. Ie. TCP Checksum is known to provide not enough
hamming distance when segments exceed standard MTUs (1500 bytes), to
cover burst bit errors. However, multi layer CRC (CRC32 in Ethernet, TCP
Checksum) extend that somewhat.

Having that said, I still don't see a pressing need of having CRCs in
MPTCP.

> loops so close together that the whole segment is still in the cache.

Checksum / Ethernet CRC32 is offloaded typically. CPU cache will never
see any data here.

> > means we should still be able to use TSO to mitigate interrupts/DMA 

Note that CRC / Checksum in a TSO will not be done in software. Asking
for an additional CRC will kill performance, as that will have to be
done by the CPU (currently). With whole-chunk CRCs, the liklihood of
having to process that on the receiving end is even larger.

> as the first checksum updated by the NAT.

If CRC-32C or CRC64 are really seen as critical in the design, only the
payload (plus TLVs, which are part of the payload) should be covered.

And as Joe Touch explained to me, that (payload CRC) should be done
using TCP Auth, with a NULL Key and a new hashing algorithm (ie. CRC-32C
or CRC64), so that we don't reinvent the wheel here...

Having that said (I start sounding like Cato the elder...), I still need
to understand the design requirement for the need of a CRC per segment
or per chunk.

Richard

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 29 Jul 2010 00:51:37 +0100

If we need protection against payload shrink/expansion this, I think copying the start/end/boundary bytes would be much less impactful, as that's a localized operation in a single segment, which has to be constructed by the CPU anyhow for the most part. 

Note, however, that detection of that may be delayed by chunk bytes - what at the time of detection might already have been delivered to the app (and freed on the sender). Not doing so would cause a potential latency burden (and addressing this with smaller chunks would, in turn, result in much worse performance, potentially lower than std tcp...)

Thus the question is, what shall be done in that case?

As we don't want to prevent middleboxes from meddling with MPTCP for lawful purposes (ie. Prevention of JOIN which may circumvent a firewall), and also some meddling of the payload by middleboxes is of some merit (wifi providers run their business model on that :) ), just making sure that the bytes don't shift should suffice.

And I think that could be done by the boundary/start bytes getting copied (it would also detect repagaging, and fail if that happens, btw), in the same starting seg carrying the MPTCP options (of chunk size, DATA_SEG, ...)

BTW: Some middleboxes might not appear to do repackaging, but do chance Sequence numbers - thus a implicit mapping of DATA_SEG to the first payload byte might be better, than a explicit DATA_SEG to sub-flow SEG mapping...

Regards,
   Richard

> From: Ford, Alan [mailto:[email-masked]] 
> Sent: Mittwoch, 28. Juli 2010 19:25
> To: Mark Handley; [email-masked]
> Cc: [email-masked]; SCHARF,Michael
> Checksums of the data are undoubtedly the only way to 
> reliably ensure that data is not changed.
> 
> However, whether this is really what we want depends to some 
> extent on what the impact we are trying to protect against 
> is, and what the boxes do. I'm not sure we need them.
> 
> We don't want to stop boxes doing these changes to the 
> payloads, we just lost alignment in MPTCP if they change 
> length. The corner case you say when two neighbouring 
> segments of data on a subflow trigger a change over the 
> boundary is the main non-length-changing case.
> 
> To take the idea of copying payload bytes as suggested by 
> Olivier and me, this would protect against middleboxes that 
> shorten or lengthen the data with a change. We can use this 
> to discard the data and fallback, or (for further study) may 
> even be able to learn the subflow sequence number adjustment 
> and carry on.
> 
> The problem is a false hit on data spanning a boundary. The 
> last 4 bytes would catch this if the change occurred over the 
> boundary, however it would not catch it if it is only on data 
> that is in the later segment (but triggered due to data at 
> the end of the earlier segment). This is a very specific 
> corner case and one that I'm not convinced would actually 
> cause any problems. If we cared, we could protect against it 
> by having the first 2 bytes and last 2 bytes of each segment 
> in the DSN_MAP (or the XOR of the first and last 4 bytes, or 
> something like that), and that would work.
> 
> > From: [email-masked] [mailto:[email-masked]] On 
> > Behalf Of Mark Handley
> > Sent: 28 July 2010 17:48
> > >>> Jana told me that, unlike described in my current spec, MCTCP 
> > >>> actually only requires a simple checksum covering the 
> TLV header 
> > >>> to detect all content-length modifying middleboxes, 
> which is way simpler.
> > >>
> > >> That is true.
> > >>
> > >>> the checksums in the MPTCP spec, without special offloading 
> > >>> support
> > >> for
> > >>> MPTCP. And if there is any middlebox detection algorithm for 
> > >>> options
> > >> not
> > >> The checksum of full data is probably relatively expensive 
> > >> (although I have no numbers about this) and so we should still 
> > >> think about other options that can achieve almost the 
> same benefit.
> > >
> > >
> > > DNS_MAP option forces the sender (and the receiver) to 
> compute a CRC 
> > > for each chunk. This implies touching the data on the CPU of both 
> > > the sender and the receiver as the NICs do not support 
> this CRC and 
> > > will likely not support it for some time.
> > >
> > > Although there are middleboxes that change the payload of TCP 
> > > segments to replace ASCII-encoded IP addresses, the 
> fraction of the 
> > > TCP connections that are affected by such middleboxes is probably 
> > > very very small. Forcing MPTCP to CRC all segments to 
> discover such 
> > > seldom events look overkill to me.
> > >
> > >> One suggestion that
> > >> number) of the start of the payload referred to by the 
> DSN_MAP into 
> > >> the DSN_MAP option itself, to ensure we are still in sync.
> > >>
> > >> The last n bytes may be better, as that allows an error to be 
> > >> detected before the start of the next data covered by 
> the next DSN_MAP, however.
> > >> We could also checksum the last n bytes as another option, which 
> > >> may be slightly more reliable.
> > >
> > > that the data has been correctly transmitted without 
> errors. MPTCP 
> > > only needs to detect that a bytestream has expanded or shrunk.
> > >
> > > running above, but an application running over regular TCP would 
> > > have the same problem). MPTCP is only concerned if the middlebox 
> > > changes the bytestream and inserts additional bytes (and thus 
> > > changes the sequence
> > > - a first solution that I proposed yesterday to Alan is to place 
> > > inside the DNS_MAP option the byte of the payload that is 
> mapped by 
> > > the DSN_MAP option
> > >
> > >                      1                   2                   3
> > >       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 
> 6 7 8 9 0 
> > > 1
> > >      
> > >      : ... ( (length-12) octets )    | Data-level Length 
> (2 octets) 
> > > |
> > >      
> > >      |              Subflow Sequence Number (4 octets)    
>           
> > > |
> > >      
> > > This reduces the size of the DSN_MAP option and from an 
> > > implementation viewpoint, extracting this byte from the 
> payload is 
> > > much simpler and faster than computing a CRC over the 
> entire mapped region.
> > >
> > > A drawback of this approach is that since a single byte 
> is included 
> > > in the option, there is no guarantee that the receiver 
> will detect 
> > > bytes) that precede the mapped byte. Using the last n 
> bytes allows 
> > > the receiver to detect a problem in the previous segment.
> > >
> > >                1                   2                   3
> > >       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 
> 6 7 8 9 0 
> > > 1
> > >      
> > >      : ... ( (length-12) octets )    | Data-level Length 
> (2 octets) 
> > > |
> > >      
> > >      |              Subflow Sequence Number (4 octets)    
>           
> > > |
> > >      
> > >      |                 Last four bytes of bytestream      
>           
> > > |
> > >      
> > > A corner case that we need to consider is the first 
> DSN_MAP option 
> > > that is sent on a connection. Since no byte has been sent, the 
> > > sender cannot refer to these bytes in the DNS_MAP option.
> > >
> > >
> > > increases the probability of detecting middleboxes, but also the 
> > > cost on the sender and the receiver sides.
> > >
> > >           1                   2                   3
> > >       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 
> 6 7 8 9 0 
> > > 1
> > >      
> > >      : ... ( (length-12) octets )    | Data-level Length 
> (2 octets) 
> > > |
> > >      
> > >      |              Subflow Sequence Number (4 octets)    
>           
> > > |
> > >      
> > >      |     Checksum of the last n bytes of bytestream     
>           
> > > |
> > >      
> > > that when an MPTCP connection is running over IPv6, it 
> does not need 
> > > to detect middleboxes that change the bytestream. If we allow the 
> > > DNS_MAP to have a variable length, the DNS_MAP option 
> could include 
> > > 0 bytes of the bytestream when used over IPv6
> > >
> > > Best regards,
> > >
> > >
> > > Olivier
> > >
> > > --

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 29 Jul 2010 08:57:49 +0200

On 29 jul 2010, at 1:51, Scheffenegger, Richard wrote:

> If we need protection against payload shrink/expansion this, I think copying the start/end/boundary bytes would be much less impactful

Looking at the start end bytes to detect length changes is pretty useless. What if the middlebox changes this:

http://www.google.com/?q=hamming%20distance

into:

http://www.bing.com/?q=hamming%20distance

Last and first bytes are still the same.

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 29 Jul 2010 10:37:49 +0100

Hi Iljitsch,

Not true; the detection would still work, but very likely too late:

> |http://www.google.com/?q=hamming%20distance|something
  |0123456789901234567890123456789012345678901|012345678
  |chunk 0, length 42                         |chunk 1, length 9

> into:
> 
> |http://www.bing.com/?q=hamming%20distanceso|mething
  |chunk 0, length 42                         |chunk 1, length 9
(end-of-line blocking if no further data comes)

Same End-of-Line Blocking would happen without and chunk 1 - chunk 0 can
not be delivered if the content shrinks - as the chunk length no longer
is full; after the MPTCP waited too long, it would probably fail that
session at that point...

In the case of data expansion, chunk 0 may be delivered partially, with
some expanded data being overwritten from a different chunk, received
via a different sub-flow.

Again, as the example simplifies, there are some valid use cases, where
in-stream modifications are desirable. Addressing that need in MPTCP may
be better, instead of defining a data integrity check of the payload
within MPTCP layer.

Regards,
   Richard

> Sent: Donnerstag, 29. Juli 2010 08:58
> Cc: Ford, Alan; Mark Handley; 
> [email-masked]; [email-masked]; 
> SCHARF, Michael
> > If we need protection against payload shrink/expansion 
> this, I think 
> > copying the start/end/boundary bytes would be much less impactful
> 
> Looking at the start end bytes to detect length changes is 
> pretty useless. What if the middlebox changes this:
>

---

From: Mark Handley <[email-masked]>
Date: Thu, 29 Jul 2010 11:03:29 +0100

> be better, instead of defining a data integrity check of the payload

Our goal has never been to ban in-stream modification.  Our goal is to
detect in-stream modification and when it happens to fall back to
single-path TCP so the in-stream modification can be done correctly by
a non-MP-aware middlebox.

For MP-aware middleboxes, we'd simply expect them to fix the checksum
and not change the length.

It's an interesting question what a MP-aware middlebox would do if it
needed to change the length.  With the current protocol, it can't do
that unless it sees all paths and can fix up the DSN mapping on all
paths.

 - Mark

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 29 Jul 2010 13:25:36 +0200

> distance will suffer.

AFAIK, the hamming distance for a CRC32 is the same for messages between 376 and 11454 bytes in size. (Does anyone know how to calculate hamming distances for common checksums and/or a list of these, I've been looking for this info but can't seem to find it.)

> Ie. TCP Checksum is known to provide not enough
> cover burst bit errors.

Ok. But how is that a multipath TCP problem?

> Checksum / Ethernet CRC32 is offloaded typically. CPU cache will never

Note that the ethernet CRC is calculated in hardware on all ethernet NICs. This is easy because CRCs are easy to calculate in hardware and having the FCS field at the end of the ethernet frame makes all of this very straightforward. The location of the internet checksum in the header of a segment makes hardware offloading much harder because a separate pass through the data is now necessary. I'm pretty sure the same problem makes doing a CRC that is stored in a header also highly problematic to offload. And CRCs are notoriously expensive to calculate in software, we REALLY don't want that to happen.

> Note that CRC / Checksum in a TSO will not be done in software.

Plenty of systems don't have hardware offloading capabilities in their network interfaces. We're not just talking about servers and desktop computers.

> using TCP Auth

That reuses Joe's favorite TCP option, but it doesn't solve the issue that such a CRC can't be calculated as the data is passed through the pipeline. It's also rather strange to calculate a second CRC32 while almost all packets already have a layer 2 FCS that is also a CRC32.

I would be more interested into moving towards a stronger checksum, maybe a CRC64, for layer 2 when jumboframes are used.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 29 Jul 2010 13:37:28 +0200

> Not true; the detection would still work, but very likely too late:

Are you saying that checking last and first bytes detects the problem? Or that looking at the length detects the problem? In the former case I disagree in the latter case I agree.

> 
> there are some valid use cases, where
> in-stream modifications are desirable.

Huh?

---

From: "Ford, Alan" <[email-masked]>
Date: Thu, 29 Jul 2010 12:44:21 +0100

Iljitsch,

> Are you saying that checking last and first bytes detects the problem?
Or
> that looking at the length detects the problem? In the former case I
disagree
> in the latter case I agree.

The example showed how a combination of first+last bytes and length can
detect the loss of sync between mapping and data.

> > in-stream modifications are desirable.

We do not want to stop middleboxes modifying payloads. If an application
wants to ensure a middlebox does not alter it, it will use TLS (for
example).

However, some enterprises deploy such middleboxes to protect against
viruses or other content they determine undesirable. Such boxes will
always exist and if we fail to work at all with such boxes we are not
helping MPTCP's deployment (currently on checksum failure we will drop
back to regular TCP. However, optimisations may be feasible.)

Regards,
Alan

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 29 Jul 2010 14:08:19 +0200

> detect the loss of sync between mapping and data.

How do the first and last bytes come into this? The length should be sufficient.

> helping MPTCP's deployment

There is a fine line between choosing not to fight something and actively accommodating it.

Who was I having the discussion with about whether the DF bit is mutable in transit again? Turns out that the flags in the IP header, which include the DF bit, _are_ mutable in transit according to IPsec rules, but the data certainly isn't.

I would love to make the system's battery explode when a content modifying middlebox is encountered but the problem is that this leaves the user out in the cold. Questions:

1. Do we care enough to determine whether all subflows are equally affected by the content lenght changing so we can keep MPTCP running if that's the case?

2. In the case where one or more subflows are affected and one or more aren't, which ones do we kill?

3. We now killed a subflow with outstanding data, do we signal this back to the sender or do we let regular retransmissions take care of this?

4. Is it safe to try and set up additional subflows after this?

---

From: "Ford, Alan" <[email-masked]>
Date: Thu, 29 Jul 2010 13:20:21 +0100

Iljitsch,

> How do the first and last bytes come into this? The length should be

The data is a continuous stream, without the bytes (or a checksum) you
don't know that the data length has changed, unless it has become
shorter and there it no more data to be sent. Richard's example showed
this clearly:

  into:

The length of the first chunk is 42 in both cases, but contains
different data because the data has been adjusted. The use of first +
last bytes can be used to detect this.

> There is a fine line between choosing not to fight something and
actively
> accommodating it.

Indeed, but we should always be mindful of ensuring deployment is easy
in most cases.

> Who was I having the discussion with about whether the DF bit is
mutable in
> transit again? Turns out that the flags in the IP header, which
include the
> DF bit, _are_ mutable in transit according to IPsec rules, but the
data
> certainly isn't.
> 
> I would love to make the system's battery explode when a content
modifying
> middlebox is encountered but the problem is that this leaves the user
out in
> the cold. 

...and MPTCP blocked from the very start, so that's a non-option.

> Questions:
> 
> 1. Do we care enough to determine whether all subflows are equally
affected
> by the content lenght changing so we can keep MPTCP running if that's
the
> case?

I don't really understand what you mean here; do you mean if one loses
two bytes, one gains two bytes, and thus the DSN mappings re-sync
themselves? If so, I think not.

> aren't, which ones do we kill?

The ones that are affected. If there is only one subflow left, the
current idea is to fall back to single-path TCP and stop using MPTCP.

> 3. We now killed a subflow with outstanding data, do we signal this
back to
> the sender or do we let regular retransmissions take care of this?

We propose the use of a "fallback" option when we fall back to
single-path TCP (attached to a RST), to signal the failure back to the
sender, thus allowing the sender to rapidly retransmit the affected
data. Regular retransmissions would also cope, but it is less optimal.

> 4. Is it safe to try and set up additional subflows after this?

We suggest not, and stick to regular single-path TCP.

Regards,
Alan

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 29 Jul 2010 14:34:33 +0200

> shorter and there it no more data to be sent.

What I imagine is having "this segment is 1000 bytes long" in an option. If it then turns out the segment is 999 or 1001 bytes, a content modifying middlebox has been mangling our packet.

>> 1. Do we care enough to determine whether all subflows are equally affected
>> by the content lenght changing so we can keep MPTCP running if that's the case?

> I don't really understand what you mean here;

I was thinking about detecting changes in packets from different subflows. However, a content mangling middlebox wouldn't modify ALL packets so this is not possible.

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 29 Jul 2010 13:33:36 +0100

Hi Mark,

> From: Mark Handley [mailto:[email-masked]] 
> 
> Our goal has never been to ban in-stream modification.  Our 
> goal is to detect in-stream modification and when it happens 
> to fall back to single-path TCP so the in-stream modification 
> can be done correctly by a non-MP-aware middlebox.

That was my understanding too.

> For MP-aware middleboxes, we'd simply expect them to fix the 
> checksum and not change the length.

That'll be a hard problem; Take for example a HTTP/MPTCP session, where
a middlebox chooses to redirect you from http://www.google.com to
http://www.my_fancy_hotel_login_page.com, and the HTTP doesn't carry any
extensions which you can really drop...

Unless there is a mechanism to adjust for added and removed bytes in a
chunk, that use case can not be covered.

But I like the Idea from Alan about a simple negotiation of MPTCP
capabilities. Certain MPTCP features need to be mandatory (ie. Support
of the MPTCP negotiation during session setup), but other stuff, such as
adjusting the DATA_SEQ numbering could be optional (and negotiated ie.
By a bitfield).

Supposed that negotiation goes through the middlebox which wants to
meddle the payload, it can actually do that, as long as only the
receiver is capable of doing this (I'm thinking about a forward
signaling of these adjustments only, with the receiver returning signals
to the sender as if that adjustment on the way never happened. Thus the
sender would be middlebox agnostic for that - allowing a simple MPTCP
stack run against more complete MPTCP stack receiver, with the middlebox
"splitting" some of the initial signalling...) 

> It's an interesting question what a MP-aware middlebox would 
> do if it needed to change the length.  With the current 
> protocol, it can't do that unless it sees all paths and can 
> fix up the DSN mapping on all paths.
> 
>  - Mark
> 

My idea was:

Have a MPTCP option at the beginning of the chunk, giving the chunk
length, chunk seq;
Have a  MPTCP option carrying a few number of bytes of the chunks
beginning.

When a middlebox fiddles with the contents of one segment (potentially
splitting this into two, or even changing segmentation), if can add an
optional MPTCP header, carrying a signed int to say by how many bytes
that chunk's size is altered (I'm thinking about 16 bits, signed;
multiple adjustments could be spread over multiple segments. Assumption
is, that we are not using MSS >32k, otherwise a middlebox can not cut
out entire segments anymore... ;) Probably not too hard an limit). Note
that the middlebox will have to be stateful when chunks are meddled
around, in case part of the content is repeated.

Have a  MPTCP option, carrying some bytes right before the end of the
chunk.

The MPTCP receiver would, in the sequence of the chunks (indicated by
DATA_SEQ first, and subflow SEQ second), adjust it's reported SEQ
numbers (adding of a 2nd counter, which is inc/dec by the adjust stuff
from the middlebox). It would report back the SEQ number after adding
the delta...

That was, back-signalling of the (modified) sequence numbers would be
transparent to the sender.

It's a bit more involved on the receiver though, if there are still
chunks outstanding, that are lower in sequence than the DATA_SEQ number
after which the adjustment was signalled; however, once all preceding
chunks are at the receiver, that data can be discarded (and only delta
needs to be checked). 

Apart from these implementation details, only an ADJUST signal would be
needed to catch MPTCP compliant, payload-meddling middleboxes. The
start/end byte carrying would fetch non-MPTCP payload meddling
middleboxes (resulting in a revert to simple TCP, ideally, and the
resending of the last chunk. Delivery of a chunk to the app may only be
allowed once the chunk has been fully received though - depending on the
data volume, the sender may choose an appropriate chunk-size.

Further, the two begin / end databyte options would also serve as a
"super-segment" indicator, which may allow for streamlined
offload-processing further down the road (as a NIC could choose to
deliver only fully reassembled chunks upstream; for simple nics,
breaking the in-sequence processing just one segment ahead of chunk-end
should not impose too much of a drawback, especially if chunk sizes of
>>64k are used.

Is that vaguely coherent?

Thanks,
   Richard

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 29 Jul 2010 13:39:27 +0100

Hi Ilijtsch,

> Sent: Donnerstag, 29. Juli 2010 13:26
> Cc: Mark Handley; [email-masked]; SCHARF,Michael; 
> >> I don't think it makes sense to use a CRC32 unless we need 
> the extra 
> >> strength.
> 
> AFAIK, the hamming distance for a CRC32 is the same for 
> messages between 376 and 11454 bytes in size. (Does anyone 
> know how to calculate hamming distances for common checksums 
> and/or a list of these, I've been looking for this info but 
> can't seem to find it.)

For up to 32bit, an exhaustive search was performed; computing power
limitations at the time didn't allow for doing this with 48 / 64 bit
CRCs. (I think it would be cool to run these higly optimized search
algos now against 64bit CRCs.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.2899&rep=re
p1&type=pdf )

[...]
 
> I would be more interested into moving towards a stronger 
> checksum, maybe a CRC64, for layer 2 when jumboframes are used.
>

Or an even better CRC-64 which may be found by above referenced search
methods.

Fully agree, when it's valuable to have integrity checking.

But MPTCP shouldn't have that capability IMHO.

Richard

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 29 Jul 2010 13:52:01 +0100

> We propose the use of a "fallback" option when we fall back 
> to single-path TCP (attached to a RST), to signal the failure 
> back to the sender, thus allowing the sender to rapidly 
> retransmit the affected data. Regular retransmissions would 
> also cope, but it is less optimal.
> 

Thanks Alan.

Note the subtle timing change that brings with it: the receiver can not
let go of any chunk, unless that chunk is fully received
(retransmissions of a part of a chunk via a different subflow are
allowed, though).

You can only successfully detect a meddling middlebox at the end of a
chunk (or when the last segment is received but doesn't match the
expected signature (= n bytes) ).

For latency sensitive apps, sender and receiver might want to actively
opt-out of that checking scheme, to enable instant  delivery of any
in-sequence DSN as soon as received. I would keep that to an MPTCP
specific API, though, and for legacy uses (TCP standard API) rather have
each chunk buffered by the receiver until full reception.

Note that there exist corner-cases with agnotic middleboxes, where a
part of a chunk is resent over a different subflow, that can end up
scambling data. However, that rat-hole should only be marked (security
implications), but left for future revisions to be solved, if this is
found to be a major issue.

Richard

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 29 Jul 2010 13:59:28 +0100

> Sent: Donnerstag, 29. Juli 2010 14:35
> To: Ford, Alan
> Cc: multipathtcp List
> >> How do the first and last bytes come into this? The length 
> should be 
> >> sufficient.
> 
> What I imagine is having "this segment is 1000 bytes long" in 
> an option. If it then turns out the segment is 999 or 1001 
> bytes, a content modifying middlebox has been mangling our packet.

What to do with segments that don't carry such an option; ie the middle
box expaning by 10 bytes the payload, but segments in such a way, that
the original segment (w/ option) stays at 1000 bytes payload...

Only a missing option in the next segment would reveal that.

Having that said, I object against over-using options. Any time a
current NIC / TOE encounters something unexpected, it's cry for help by
the software stack ;)

Rare options are key, imho, to deliver high performance.

Options are also key to deal with infrequent events
(JOIN/DROP/ADJUST,begin/end chunk data, DSN), but shouldn't be in every
sub-flow segment.
 
> >> affected by the content lenght changing so we can keep 
> MPTCP running if that's the case?
> 
> I was thinking about detecting changes in packets from 
> different subflows. However, a content mangling middlebox 
> wouldn't modify ALL packets so this is not possible.
> 

I think for uncooperating middleboxes, the begin/end data mirror
suffices - mostly. 

For cooperating, they could intercept JOINs, insert ADJUSTs, etc... 

Regards,
   Richard