Subject: Re: [multipathtcp] Review of draft-scharf-mptcp-mctcp

From: Costin Raiciu <[email-masked]>
Date: Thu, 22 Jul 2010 16:23:33 +0100

Hi,

Comments inline.

> We have to carefully separate what is an inherent limitation of a
> protocol, and what is a problem of a specific buffer management
> implementation. The corresponding sections seem to assume fixed and very
> small buffer sizes.

No. Those are very simple examples that can be understood easily. We can't show 
an example with a 1000 packet receive buffer, but the same problems apply.

> In this case, MPTCP will IMHO run into problems
> whatever encoding is used: Reassembly is difficult without additional
> memory.

No. In the example we gave, implicit data ACKs perform much worse than explicit data ACKs. It's not a case that everything is gray.

> Also, a stack might need additional memory to store the
> information received in MPTCP's options. All this is highly
> implementation-specific, and some of the assumptions in the design
> document do not apply to MCTCP. To me, the only conclusion out of the
> design document is that a MPTCP receiver will need a dynamic memory
> management (dynamic receive buffer tuning). Modern TCP stacks do this
> anyway. 

Dynamic receive buffer tuning is just an optimization to save memory in the
cases where a connection needs less than the max memory allowed. It allows the stack
to progressively allocate more memory. 
Linux tcp_rmem sysctl allows you to set three bounds: min (this is what you start off with), average, and max.
Dynamic memory management will resize the buffer within these bounds, trying hard not to trigger flow control
while using as little memory as possible.

But there is always an upper bound, no matter how you dynamically manage the memory. If the BDP is large/growing
the kernel will keep allocating memory until it hits some predefined max. Then, it will allocate no more. 
However, the receive buffer will not be increased to store more data for a slow app. It just tracks the BDP, plus some constant
number of segments to allow efficient copying from kernel space to user space.. 

As far as I understand, there are two control loops:
- one deciding what to do with segments when they arrive - each segment is checked to see if it is "in-window" before being accepted. 
If it is out of window it is dropped. See net/ipv4/tcp_input.c for details of how this is done.
- one loop deciding how big the receive buffer should be - this uses estimates of BDP; this is done in linux in tcp_rcv_space_adjust. This is called whenever data
is copied to userspace (c.f.  2.6.28 kernel).

> The design document claims (p. 8): "In fact, due to the implementation
> of dynamic receive buffer sizing in modern operating systems, the
> receive window often tracks only just above the level actually
> required. It is likely that receive window problems can occur in such
> operating systems even when flow control should not kick in."
> 
> Could you give an example that supports this claim, given that this
> seems to be such a crucial issue for the a protocol design discussion?
> Is this problem occuring in practice in the MPTCP Linux kernel
> implementation?

Sebastien Barre did run into many issues wth receive buffers while implementing the code. In particular, he's just found out that not having a shared buffer pool can easily lead to deadlocks.
He can tell you more himself.

> 
> Note that, to the best of my knowledge, many current operating systems
> announce rather large receive windows (>64K). If they use dynamic memory
> management, they can increase the receive window on a subflow as long as
> the OS has some free memory. In this case, IMHO none of the deadlock
> situations described in the design document can occur. But, again,
> please correct me if I am wrong.

As I said, there is always an upper bound on the amount of allocated memory to a TCP connection.
Otherwise, one connection can eat the memory of the entire system. That's not wise resource usage.

> * Design principle 2 is only necessary if the passive opener would
> trigger any multipath actions, which is not necessarily true. In case of
> MCTCP, the active opener has to trigger the change to multi-connection
> mode, i. e., there is no problem if the MPCAP option in the SYN/ACK gets
> lost. In that case, the passive opener just observes that this
> connection never enters multi-connection mode, but I don't see any
> problems with this.

Ok. The design principle assumes you start the multipath mode. In your case, the active opener 
will discover this only later, when it wants to use multipath. But the principle still holds: if you want to 
do multipath, the first non syn packets must confirm multipath is enabled. I think we are in agreement. 

> 
> * Design principle 3 is apparently also wrong. If desired, I can explain
> why.

Why?

> 
> 
>> Some detailed comments about your proposal:
>> 
>> You said your solution is a hybrid between payload and 
>> options encoding, but I fail to see the big difference to 
>> pure payload encoding. Any payload encoding MUST use options 
>> on SYN packets to negotiate multipath TCP capability. Our 
>> unfinished payload draft does this too. This is also what 
>> your solution uses. Am I missing something?
> 
> As far as I can tell, the key difference seems to be that MCTCP does not
> change the encoding format for single path transfer, i. e., it is
> backward compatible for all middleboxes until one really wants to use
> multiple paths. Apart from that, there are numerous details that MCTCP
> solves in a different way, due to different design objectives.
> 
> MCTCP has been developed independently from your unpublished payload
> draft. I assume that there are both similarities and differences. MCTCP
> is by far not the only way how to realize payload encoding, and it would
> really be worth discussing other design alternatives. Also, note that
> the MCTCP draft explicitly lists some drawbacks of the design, and it is
> possible to address some of them by alternative approaches.
> 
>> Besides the encoding, one major difference between the 
>> current spec and your solution is that your solution has 
>> explicitly two phases:
>> Phase 1 - connection is single path, with regular payload 
>> encoding Phase 2 - connection is multipath, with TLV chunked encoding.
>> There is a phase shift from 1 to 2 when multiple subflows are 
>> needed, and from 2 to 1 sometimes (not clear when).
> 
> Basically, the fall back from multi-connection mode to single-connection
> mode is only needed when there are content-modifying middleboxes, or
> middleboxes that entirely block TLV transport.
> 
>> - Your design choice brings up a good question: do we want to 
>> try and look as much as regular TCP when in single path mode? 
>> This might make sense for compatibility reasons, and to reduce costs.
> 
> Agreed.
> 
>> Our options design can specify an infinite DSN mapping in the 
>> SYN to tell the receiver it should use subflow data sequence 
>> numbers for connection level reordering. Also, when an 
>> infinite mapping is in place, data ACKs are not needed, and 
>> the sender just uses subflow ACKs to free its send buffers. 
>> This phase of the options draft is very close to phase 1 of 
>> your algorithm.
> 
> True. I was not aware of your idea of infinite mappings when designing
> MCTCP, but it is indeed similar.
> 
>> Our current spec uses this phase as a fallback to regular TCP 
>> when things go bad - mainly to deal with middleboxes that 
>> strip options on data segments and with middleboxes that 
>> change the payload.
>> However, we have not specified a way to return to the regular 
>> multipath phase from this one. It is not difficult to do so: 
>> we could use techniques such as: send a new finite DSN 
>> mapping and a new segment, and wait for the data ACK  before 
>> proceeding. Receiving the data ACK tells you the receiver 
>> know about the mode switch, 
> 
> I have thought about that solution, too. My current understanding is
> that a fallback to infinite mapping is not robustly possible, but I
> might be wrong.
> 
> The fundamental problem is that the usage of both infinite and finite
> DSN mappings results in contradicting mappings for the sequence number
> space. The sender must know that the receiver has received the updated
> mapping, and the receiver must know that the sender is actually applying
> it. If a middlebox on all paths starts to strip options, there is IMHO
> no way how sender and receiver can both know what mapping is indeed used
> (example: what happens in your example if the data ACK gets lost?). But,
> as I said, I might have missed some workaround.

Fallback scenarios for options based TCP are described in the draft. They cover middleboxes 
that drop options on data.

> 
> Please specify a way how to return to the regular phase, so that we can
> check whether it is robust, or whether you risk to corrupt the
> application bytestream by applying the wrong mapping (which is IMHO even
> worse than closing the connection).

We can do what you propose: pause data on the existing "infinite" subflow, open a new one, put a finite DSN there. Close the
existing one. From there on you are in multipath mode.

> 
>> - One of your design goals is to allow user-mode 
>> implementations, with minimal support from the kernel. This 
>> is obviously a good thing for the adoption point of view, but 
>> I don't think we can get away with so few changes to the 
>> stack. In particular, besides signalling on SYNs, the OS must 
>> manage a shared memory pool for the whole connection - 
>> otherwise you can easily get deadlocks.
> 
> There are two different ways how to implement MCTCP, as explained in the
> draft:
> 
> It is either a new shim layer inside the OS, mostly on top of individual
> connections. Then, it is basically operating on socket level. Or it is
> realized in the user space, as an own library (such as glibc), in
> combination with some small patches of the TCP stack to deal with the
> TCP options and with coupled congestion control. To me, this is the more
> interesting variant as long as multipath transport is not universially
> supported in the Internet.
> 
> In the latter case, the MCTCP library has an own memory management
> anyway, which is probably the shared memory pool that you refer to. For
> a kernel solution, I would personally decouple the memory management of
> MCTCP from the receive buffer of an individual TCP connection.
> But this
> is left to an implementation, and I am not familiar with all OS
> constraints. Note that in case of Linux (the only TCP implementation
> that I know in detail), there is no fixed receive buffer. Memory is
> dynamically allocated for each incoming packet, and there is no real
> reservation of buffer capacity. Thus, the OS already uses a shared
> memory pool for all TCP connections today.

On packet reception in Linux a check is made to see if the socket has enough memory to store the segment.
In particular sk_mem_schedule in net/core/sock.c will fail if the socket memory usage is above the max.

> 
> Memory management in a modern OS is a highly complex issue, and IMHO
> hardly relates to the assumptions of receive buffers in RFC 793. But
> maybe an OS expert has to speak up here.

I think you are right, but the optimizations are done around the spec and not against it. Again, the OS will try
to get away with the least bufffering possible; it will keep increasing until it hits some max bound. After that flow control
kicks in.

> 
>> The alternative is to 
>> allocate, for each subflow, the memory needed for the entire 
>> connection. In that way, we could avoid deadlocks; this 
>> memory is, at best, linear in the number of subflows. With 
>> the user space solution memory usage would be at least 
>> quadratic in the numbe of subflows.
>> Besides  inneficiency, this requires that the receive buffers 
>> of existing connections can be altered at runtime from 
>> user-space. Is that possible with current OSes?
> 
> I cannot follow this argument. I don't think that one would implement
> MCTCP with very large buffers per subflow.
> 
> BTW, in case of Linux, there are socket options and sysctls that allow
> to modify the "receive buffer size" from user space. AFAIK they mostly
> affect the receive window announced to the sender, and only indirectly
> the kernel memory management. These settings are applied in runtime,
> AFAIK. But, again, this is a topic for OS experts.
> 
>> - You propose to use a data NACK to allow the connection to 
>> recover from pro-active acking middleboxes that fail to 
>> deliver the data. That should work. However, it means the 
>> sender must use timers to delete this data. How big are these 
>> timers? Probably you wouldn't want to delete data before a 
>> timeout would occur (presumably this would be used by the 
>> receiver to detect missing data). For 3g connections with 
>> rtts well into 1s, timeouts can be a lot more than that. You 
>> really don't want to buffer all of your sent data for a few 
>> seconds at the sender.
> 
> A timeout is one solution. Alternatively, the sender could estimate the
> worst-case BDP and store some few multiples of that. For a HSPA
> connection with (optimistically) 10 Mbit/s and 200ms RTT, the BDP is 250
> KB. Caching for 3s would require less than 1 MB of memory. IMHO, current
> smartphones, netbooks, etc. have at least 1GB of memory. Memory is not
> that scarce... Is there really an issue?

200ms is true when there is no data transfer. At least in london, the rtt goes up to
1s when you are transferring data with TCP. That's because operators don't like packet 
loss. 

> But, as I pointed out in the draft, I am still not convinced that data
> ACKs would actually solve a relevant problem:

I strongly disagree. The data ACKs are needed if this whole thing will ever work.

> - If the data ACKs are sent frequently, they result in a lot of
> overhead. If they are sent more seldomly, the buffer requirement at the
> sender will be rather large, too.
> 
> To return the question: How frequently do you recommend to send data
> ACKs?

If overhead is a problem , sending the data ACK a few times per RTT should be enough
to help the sender clear its buffer. Say once every two or four full segments? If you do it once every two segments, 
the overhead is 10B/3KB  or 6KB sent. That is negligible

Cheers,
Costin

---

From: "SCHARF, Michael" <[email-masked]>
Date: Thu, 22 Jul 2010 21:17:20 +0200

Costin, 

> > implementation. The corresponding sections seem to assume fixed and 
> > very small buffer sizes.
> 
> No. Those are very simple examples that can be understood 
> easily. We can't show an example with a 1000 packet receive 
> buffer, but the same problems apply.

in section 2.2.1, the example uses two receive buffers, with a size of
two packets, respectively.

I totally agree that for such small buffers various problems occur with
multipath transport. The simple conclusion is: Don't use multipath in
that case.

My suggestion would be to enable multipath transport only if the TCP
receiver has a committed receive buffer size of (say) at least 256 KB,
and if the receiver announces a receive window of at least 128 KB to the
sender (on each subflow). This gives us quite some headroom to deal with
(hypothetical) payload ACKs somewhere stuck in the TCP receive buffer,
different RTTs, etc.

Why does the problems then still apply? The document only contains
generic statements for the case of larger buffers, and it is hard to
discuss claims about potential problems that are not described.

> > A timeout is one solution. Alternatively, the sender could estimate 
> > the worst-case BDP and store some few multiples of that. For a HSPA 
> > connection with (optimistically) 10 Mbit/s and 200ms RTT, 
> the BDP is 
> > 250 KB. Caching for 3s would require less than 1 MB of 
> memory. IMHO, 
> > current smartphones, netbooks, etc. have at least 1GB of memory. 
> > Memory is not that scarce... Is there really an issue?
> 
> 200ms is true when there is no data transfer. At least in 
> london, the rtt goes up to 1s when you are transferring data 
> with TCP. That's because operators don't like packet loss. 

Well, then let's cache say 5 MB if a networking stack is connected to
one of those networks that have pro-acking middleboxes.

This is still seems to be quite doable, and there is still no apparent
need for data ACKs.

Michael