Subject: Re: [multipathtcp] Options vs payload & offload

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 28 Jul 2010 10:14:34 +0100

From: Iljitsch van Beijnum <iljitsch at muada.com>

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

I've read some NIC specs which do TSO and RSS; also, Andrew McGregor and
I did look into the LRO code running in Linux (under the premise, that
much of what will eventually be offloaded to hardware, typically follows
some implementation already in widespread use).

Some observations:

TSO is much less of an issue - the sender can create a bunch of send
descriptors (heads & data), which are subsequently processed by hw
without further intervention. Thus there is little overhead in having an
Option only when it's really necessary, vs. having a single header which
is replicated over *all* the data chunk segments. (Data chunk = the
consecutive data sent via a single subflow in a single "IO").

However, on the receive side, the LRO code will "bail out" and stop
reassembly, when any option other than Timestamps are received, the
sequence space is non-contingous (lost / reordered packet) - or the max
IP packet size is exceeded.

Therefore, a design constraint imposed much more by the typical subflow
receiver than the sender is to have any TCP option only when it's really
necessary; Having any MPTCP option in all the headers of a chunk will
probably break performance in a lot of LRO implementations.

Further, I do like Tim Sheppard's idea of having only half-duplex
sub-flows; this should allow for implementation optimizations.

Last, again speaking about the DATA_ACK option (which may be subject to
head-of-line blocking if sent as payload).

Worst case such auch an DATA_ACK would be to carry also Timestamp (10)
and some SACK (2+n*8) information.

In the past there was done some research on the loss of efficiency when
having SACK with Timestamps (limiting n to 3, instead of the originally
possible 4), and that showed negleglible impact in performance
(goodput/efficiency) when moving from 4 to 3; It was further noted, that
the highest gains with SACK come from having the 1st field, with the 2nd
field adding some additional resiliency when ACKs get lost on the return
path.

Qualitatively, there should be an exponential drop in the gains by
having 1 more SACK field (ie. 80/16/3/1 %) - thus limiting the number of
SACK fields when DATA_ACK and Timestamps are carried in the same segment
to only 2 fields should still allow the most SACK benefits.

One question I have - raised by Lars actually - wouldn't it make sense
to allow multipath DATA_SACK options as well?

Lars mentioned some recent research, where Wifi power down is used (and
hotspots queuing/storing data packets) to conserve mobile device power.

Using a DATA_SACK option, retransmission of DATA over different paths
should be more efficient (as only the missing data needs to be sent).
The selection of which sub-flow to use (and which should be possible to
be signalled by the receiver) should also be there to allow some policy
for subflow selection other than relative bandwidth between them.

Question to the group: Should such a signalling go into the first
version of the specs, or deferred to a later version in order to get an
initial MPTCP out faster?

Richard Scheffenegger

---

From: Costin Raiciu <[email-masked]>
Date: Wed, 28 Jul 2010 11:51:51 +0200

Hi,

> probably break performance in a lot of LRO implementations.

I had a very interesting chat with Ilpa Jarvinen and Aki Nyrthinen yesterday about this. Aki was saying that what we might end up doing is inserting the longer mapping in a single segment, without TSO, and send the rest of the segments covered by the mapping using TSO (say 15KB). LRO will only bail out on the first segment with the mapping; it will work fine for the rest of the segments. 

> and some SACK (2+n*8) information.

I would also like to add than when SACK is present, Data ACK will typically not be included. The draft says that Data ACK must only be sent when it
moves forward. When SACK is present we already have a gap, which means normally that the data ACK is stuck. Hence, there is no need to send it.

> to allow multipath DATA_SACK options as well?

I think we can use the subflow ACKs to infer data SACKs. 

Basically, the sender keeps a scoreboard of
segments, with their Data level seqno and subflow level seqno. When the segment is acked at subflow level, we can treat this information as a data SACK. 

Thanks,
Costin

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 28 Jul 2010 11:21:37 +0100

> -----Original Message-----
> From: Costin Raiciu [mailto:[email-masked]] 
> Sent: Mittwoch, 28. Juli 2010 11:52
> To: Scheffenegger, Richard
> Cc: multipathtcp
> Subject: Re: [multipathtcp] Options vs payload & offload
> 
> Hi,
> 
> > sequence space is non-contingous (lost / reordered packet) - or the 
> > max IP packet size is exceeded.
> > 
> > Therefore, a design constraint imposed much more by the typical 
> > subflow receiver than the sender is to have any TCP option 
> only when 
> > it's really necessary; Having any MPTCP option in all the 
> headers of a 
> > chunk will probably break performance in a lot of LRO 
> implementations.
> 
> I had a very interesting chat with Ilpa Jarvinen and Aki 
> Nyrthinen yesterday about this. Aki was saying that what we 
> might end up doing is inserting the longer mapping in a 
> single segment, without TSO, and send the rest of the 
> segments covered by the mapping using TSO (say 15KB). LRO 
> will only bail out on the first segment with the mapping; it 
> will work fine for the rest of the segments. 

Exactly; one word about the chunk sizes though: We do have a protocol
running in our boxes, which basically does MPTCP (we call it ICS); it's
designed for bulk data transfers at high bandwidth over long latencies.
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.

> > Last, again speaking about the DATA_ACK option (which may 
> be subject 
> > to head-of-line blocking if sent as payload).
> > 
> I would also like to add than when SACK is present, Data ACK 
> will typically not be included. The draft says that Data ACK 
> must only be sent when it moves forward. When SACK is present 
> we already have a gap, which means normally that the data ACK 
> is stuck. Hence, there is no need to send it.

But you may have made forward progress on DATA in an independent
subflow, and that subflow is no longer available (ie. Got teared down
for some reason in mid-transfer, or deliberate by sender or
receiver...). 

As ACKs are typically not elegible for LRO anyway, and sent at a much
lower pace when LRO is used than every 2nd subflow packet, it might be a
good idea to have a DATA_ACK and a DATA_SACK (covering the first hole;
actually, the idea could be to just indicate the *end* of the first hole
(or the size of that first hole, to make encoding / option size
smaller).

> 
> > 
> > In the past there was done some research on the loss of efficiency 
> > when having SACK with Timestamps (limiting n to 3, instead of the 
> > originally possible 4), and that showed negleglible impact in 
> > performance
> > (goodput/efficiency) when moving from 4 to 3; It was further noted, 
> > that the highest gains with SACK come from having the 1st 
> field, with 
> > the 2nd field adding some additional resiliency when ACKs 
> get lost on 
> > the return path.
> > 
> > having 1 more SACK field (ie. 80/16/3/1 %) - thus limiting 
> the number 
> > of SACK fields when DATA_ACK and Timestamps are carried in the same 
> > segment to only 2 fields should still allow the most SACK benefits.
> > 
> Basically, the sender keeps a scoreboard of segments, with 
> their Data level seqno and subflow level seqno. When the 
> segment is acked at subflow level, we can treat this 
> information as a data SACK. 
> 

Ah, correct... Ok, forget about the SACK hole idea; ;)

---

From: Yoshifumi Nishida <[email-masked]>
Date: Wed, 28 Jul 2010 06:07:30 -0700

Hi

2010/7/28 Costin Raiciu <[email-masked]>

> I would also like to add than when SACK is present, Data ACK will typically
> not be included. The draft says that Data ACK must only be sent when it
> moves forward. When SACK is present we already have a gap, which means
> normally that the data ACK is stuck. Hence, there is no need to send it.
>
> I just would like to make sure one thing.
In case that multiple data blocks are missed, data seq should be advanced
everytime the retransmission of the first SACK block arrive. Don't we need
to send DATA ACK in this case?

--
Yoshifumi Nishida
[email-masked]

---

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

Hi
,
> In case that multiple data blocks are missed, data seq should be advanced everytime the retransmission of the first SACK block arrive. Don't we need to send DATA ACK in this case? 

Yes, we do need to send the Data ACK in that case, because it moves forward. 

Richard brought up another point: there can be other paths that could advance the Data ACK, while a subflow has experienced loss and is including SACK blocks in the acks. In this case,
the Data ACKs will be transmitted on the "working" subflow anyways, so the question is whether we also want to send them over the subflow with SACK blocks. I would be inclined to say no,
but I admin I haven't thought this through properly.

Costin

---

From: "Ilpo Järvinen" <[email-masked]>
Date: Wed, 28 Jul 2010 16:24:00 +0300 (EEST)

On Wed, 28 Jul 2010, Costin Raiciu wrote:

> Richard brought up another point: there can be other paths that could 
> advance the Data ACK, while a subflow has experienced loss and is 
> including SACK blocks in the acks. In this case, the Data ACKs will be 
> transmitted on the "working" subflow anyways, so the question is whether 
> we also want to send them over the subflow with SACK blocks. I would be 
> inclined to say no, but I admin I haven't thought this through properly.

But what if that's the only path you got available (at that point of time) 
for some reason? Or all paths hit a loss event at the same time? No 
guarantee you'll have "working" flow.

-- 
 i.

---

From: Costin Raiciu <[email-masked]>
Date: Wed, 28 Jul 2010 15:34:48 +0200

> guarantee you'll have "working" flow.

Sure, that can happen but I expect it to be rare. As long as in the common case we don't kick out (too many) SACK blocks, this should work well enough.

As a general strategy when we run out of options, I think it is possible to  carefully create one or a few extra ACKs per RTT (or just turn off delayed acks). 
We could use the option space of these ACKs to extend the option space available for signaling. 

I haven't really thought this through, but it seems this might work as long as existing stacks implement and use appropriate byte counting.

Cheers,
Costin

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 28 Jul 2010 14:38:09 +0100

> Sent: Mittwoch, 28. Juli 2010 15:18
> To: Yoshifumi Nishida
> Cc: multipathtcp

> > > Worst case such auch an DATA_ACK would be to carry also Timestamp 
> > > (10) and some SACK (2+n*8) information.
> > 
> > I would also like to add than when SACK is present, Data ACK will 
> > typically not be included. The draft says that Data ACK 
> > In case that multiple data blocks are missed, data seq 
> should be advanced everytime the retransmission of the first 
> SACK block arrive. Don't we need to send DATA ACK in this case? 
> 
> Richard brought up another point: there can be other paths 
> that could advance the Data ACK, while a subflow has 
> experienced loss and is including SACK blocks in the acks. In 
> this case, the Data ACKs will be transmitted on the "working" 
> subflow anyways, so the question is whether we also want to 
> send them over the subflow with SACK blocks. I would be 

Well, as mentioned, cutting SACK short when a DATA_ACK also has to be
present shouldn't 
Have much impact on the sub-flows. (And Costins argument about the
sub-flow ACK/SACK effectively serve as DATA_SACK might actually be
another nail in the coffin of user-space implementations - at least
those will not be as effective (packet conservation) as kernel
implementations, which could still deliver DATA covered in
non-contingeous sub-flows, and only request the missing DATA; actually
it'll be the server who lacks the info (when the receiver is implemented
in userspace) which DATA is still outstanding (some might have been
covered by SACK in a subflow, but never delivered by the kernel to the
userspace MPTCP implementation. How does the server know to resent only
the missing DATA up to the sub-flow sacked point, or the point ACKed by
a different sub-flow...

(DATA_ACK_REQ option giving the length of data missing for the MPTCP
layer until it's first next DATA?) 

Further, if a subflow fails, the DATA_ACKs should still be delivered
relyable, right?

So, may there be cases (a sub-flow enters loss recovery or stalls for a
(ACK-)timeout period) where it make sense to sent back DATA_ACK over all
sub-flows nearly at the same time (also as a kind of probe for recently
quiet sub-flows)?

But Costin is right, a number of differenc scenarios (ACK loss, sub-flow
data loss, reordering between subflows (different back-channel latency)
need to be defined and investigated to come up with a viable answer
there...

Regards,
   Richard

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 28 Jul 2010 14:44:12 +0100

Costin, 

> Sent: Mittwoch, 28. Juli 2010 15:35
> To: Ilpo Järvinen
> Cc: multipathtcp

[...]
> 
> As a general strategy when we run out of options, I think it 
> is possible to  carefully create one or a few extra ACKs per 
> RTT (or just turn off delayed acks). 
> I haven't really thought this through, but it seems this 
> might work as long as existing stacks implement and use 
> appropriate byte counting.
> 
> Cheers,
> Costin
> 

ABC is primarly on the sender side, to not overshoot the cwnd to fast; the additional ACKs might not advance anything with each sub-flow (and there might not even be any data for that subflow). But defining, that a MPTCP sender MUST implement ABC (most do anyway, afaik) could be put in the draft, and we can work on the assumption that multiple ACKs per sub-flow don't break anything at the sub-flow level. ;)

---

From: Yoshifumi Nishida <[email-masked]>
Date: Wed, 28 Jul 2010 07:17:48 -0700

Hi,

> typically not be included. The draft says that Data ACK must only be sent
> when it
> advance the Data ACK, while a subflow has experienced loss and is including
> SACK blocks in the acks. In this case,
> the Data ACKs will be transmitted on the "working" subflow anyways, so the
> question is whether we also want to send them over the subflow with SACK
> blocks. I would be inclined to say no,
> well, if we want to send DATA ACK on other working flows, I think it might
look like dupacks when no data is coming from the peer of the flow. I'm not
sure how bad and how rare it is, but might need to think.
--
Yoshifumi Nishida
[email-masked]

---

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

________________________________

	From: Yoshifumi Nishida [mailto:[email-masked]] 
	Sent: Mittwoch, 28. Juli 2010 16:18
	To: Costin Raiciu
	Cc: multipathtcp
	Subject: Re: [multipathtcp] Options vs payload & offload

	Hi,

	well, if we want to send DATA ACK on other working flows, I
think it might look like dupacks when no data is coming from the peer of
the flow. I'm not sure how bad and how rare it is, but might need to
think. 
	--
	Yoshifumi Nishida
	[email-masked]

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

As the DATA is supposed to be sent about reliable transport sub-flows, I
would call in question a flow retransmission scheme based on triple
DATA_ACK. (note that sub-flows would still use triple ACK / SACKs for
their retransmissions).

A NACK based retransmission scheme might be actually the better way to
trigger retransmission of DATA via the same, or a different sub-flow...
(Signalling of which flow to use could be implicit, by the sender
choosing that path, over which the NACK was received (first; NACKs may
need a small unique ID, then sending out the same NACK over multiple
sub-flows at the same time would not be an issue if one of them is
delayed...)

Regards,
   Richard