Subject: [multipathtcp] Host network stack thoughts from the implementors workshop (was: Re: Multipath TCP Implementors workshop, Saturday 24th July)

From: "Robert N. M. Watson" <[email-masked]>
Date: Sun, 25 Jul 2010 14:38:53 +0100

Dear all:

Following Sebastien's talk, there were a number of areas I hoped to seek some expansion / clarification, or had questions. This is a brain dump, but perhaps can provide some fodder for WG discussion at IETF this week:

- Could you expand on the extent of code change and the opportunity for code sharing and reuse in the Linux prototype: where was the most change needed, what sorts of new functions were added and why, where was the majority of development and testing time spent? Were there protocol design choices, that if eliminated, would have dramatically simplified the implementation or allowed greater reuse?

- Could you expand on buffering trade-offs, especially as relates to memory use, memory/data flow, implementation complexity, and obligations as relate to the specification -- "kernel memory" is expensive, especially in embedded mobile environments, and the apparent implications of copying and storing data many times are concerning. Could you specifically address the memory overhead as compared with regular TCP in various scenarios given the current implementation, and say a bit more about alternative implementations? (You talked a little about when to segment data and push it down to sub-flows, for example)

- Where do current prototypes diverge from the specification driven by complexity / feasibility concerns? Do you see resolving them through changes to the implementation, or changes to the protocol specification?

- Could you expand on the "join" issue and its comparison to listen sockets. Listen sockets are one of the most complex and error-prone parts of current TCP implementations; in retrospect the join problem should have been obvious to me, but as someone only taking a casual interest to date, it was a surprise, and one of the most worrying things I heard over the course of the day. If the goal is to look just like the on-the-wire SYN handshake, do you see things like syncache/syn cookies being used here? What does this mean in terms of book-keeping for getting new sub-flows hooked up to the logical connection they will belong to? Do you see reusing the current code paths for SYN-handling in TCP input?

- Could you say a bit more about your practical experience (and concerns) with the role of middle nodes, especially ones that don't change the "content" of the connection, but do make changes to segmentation, window advertisements, etc, especially in light of my points about edge node performance technologies (such as LRO, TSO) being used in middle nodes. Should the MP-TCP working group, as well as providing a protocol spec, be providing specific guidance to middle node implementors?

- How to use non-protocol policy sources to inform congestion control and scheduling decisions, such as affinity information in multicore/multi-queue environments, power management, out-of-band topology information, sysadmin policy, application policy, network policy, etc. It seemed that when these concerns were raised, part of the answer was "this might be a vendor problem", but I think that would miss the point: if the goal of MP-TCP is to allow applications to portably, transparently, and consistently get the benefit of multiple paths, then providing a notional framework that implementors can use and implement has value.

- Interactions between existing load balancing technologies such as ECMP and RSS: where multipath TCP is helped, and where it is hurt, and how to influence future iterations of those technologies so that they work better with MP-TCP. E.g., my proposal of a logical connection identifier option so that it can be used instead of sub-flow 5-tuples in NICs (which are, in practice, middle nodes).

- More generally: could you clarify the extent to which the current Linux prototype is a research platform vs. a tech transfer target -- very different things, and Sebastien's slides mentioning the goal of Linux kernel adoption seemed not to mention trade-offs driven by one side or the other?

I'm particularly concerned that the current Linux prototype considers "SMP optimizations" a footnote rather than a primary design concern: one of the central thrusts of the last decade of OS design has been adapting to the multicore world. MP-TCP has immediate implications for multiprocessor efficiency for a variety of reasons, not least due to interaction with multi-queue network cards. While this may not be an immediate worry on the smart phone end (one of the strongest perceived applications for MP-TCP), remember that at the other end of the Internet are piles of multiprocessor servers in data centres. If MP-TCP reduces their scalability by 30% for busy TCP environments, that's a huge adoption concern in terms of power use, number of Us, etc. We need measurements to understand these issues concretely (i.e., do they really exist?), and from what I heard, it sounds like the current Linux prototype is not yet sufficiently mature to explore this issue. The results of that investigation may drive protocol changes, so it's imperative that this be considered sooner rather than later.

Rather than sound all-negative, I do want to say that MP-TCP is a really interesting area that we (the FreeBSD community) would like to engage with. We have lots of immediate downstream consumers of our network stack who would benefit from access to a mature MP-TCP -- and a fair number of them will consider us the route by which they adopt the technology (if things go well). Taking existing network stack considerations into account will be critical: implementation complexity, modern hardware constraints (especially as relates to SMP), the reality of middle nodes, etc, are impacting MP-TCP design already, but some may need greater emphasis going forward.

Robert Watson
University of Cambridge
Computer Laboratory

---

From: Lars Eggert <[email-masked]>
Date: Sun, 25 Jul 2010 15:56:22 +0200

On 2010-7-25, at 15:38, Robert N. M. Watson wrote:
> I'm particularly concerned that the current Linux prototype considers "SMP optimizations" a footnote rather than a primary design concern: one of the central thrusts of the last decade of OS design has been adapting to the multicore world. MP-TCP has immediate implications for multiprocessor efficiency for a variety of reasons, not least due to interaction with multi-queue network cards. While this may not be an immediate worry on the smart phone end (one of the strongest perceived applications for MP-TCP), remember that at the other end of the Internet are piles of multiprocessor servers in data centres.

Smart phones are going multi-core in the very near future. So this is a concern there as well.

Lars

---

From: Sébastien Barré <[email-masked]>
Date: Mon, 26 Jul 2010 16:23:13 +0200

Dear Robert,

Thanks for the comments !
I'll try to answer inline:

Op 25-07-10 15:38, Robert N. M. Watson schreef:
> - Could you expand on the extent of code change and the opportunity for code sharing and reuse in the Linux prototype: where was the most change needed,
The thing that requires most changes is when TCP subflows deviate from 
regular TCP. Conceptually, MPTCP tries to be something located "above" 
TCP, hence using almost unmodified TCP implementation for each subflow. 
Where things become costly is when we need to hack the TCP 
implementation to make it useable for MPTCP subflows. In decreasing 
order of importance, I would sort such changes as follows :
*Shared receive window: as explained in the slides this is probably the 
most heavy change, although we can probably rearrange a bit the code to 
isolate MPTCP changes better. This single decision of using a shared 
receive window (and of course shared receive buffer) leads to the 
following changes:
->Receive buffer autotuning+window computation.
->Sanity checks at segment reception, if the segment is not in receive 
window, must be dropped. But that window has changed now.
->Since the rcvwnd is copied into the sndwnd of the sender, sndwnd 
semantics must also be changed. A set of (legacy) functions allow 
knowing the size of the sndwnd, the last seqnum of the sndwnd, whether 
next segment is allowed to go to the wire,etc. All this must be changed 
to use Data sequence numbers instead.
->storing of the shared value for sndwnd/rcvwnd: Currently I use the 
existing per-subflow variables as "local variables" used to compute the 
shared value for sndwnd/rcvwnd. That shared value is in turn stored in 
the mptcp control block.  That seemed a natural choice, but forces to 
change the functions that use those variables. An alternate choice would 
be to store a copy of the shared value in the local variables of each 
subflows, allowing to keep unmodifed the functions that use them. But 
then we need to add new variables, hence use more memory, and duplicate 
data. Thus both solutions have drawbacks.

*JOIN option implementation: One thing I do not like here is that I need 
to check the existence of that option in the main TCP entry point. I did 
not find any other option to implement this. The problem is that usually 
Linux kernel maintainers do not like when we modify those main entry 
points. The reason for needing to check it is that if the JOIN is there, 
we must even not try to do normal socket lookup, but instead go for a 
token-based MPTCP lookup. So if we see the join, we directly enter 
mptcp-specific code, that quite reproduces the steps of normal SYN 
reception. Maybe some code sharing is possible here, but with the 
requirement of making more general the regular TCP code for 
listening-side TCP establishment.

*tcp_recvmsg(): This is the TCP function that is almost always called 
when a read()/recv()/... syscall is executed. It has been __heavily__ 
modified, but I kept the logic of it, and the Van Jacobson trick of 
giving as much work as possible to the process instead of the kernel, is 
supported in MPTCP (implemented with the so-called prequeue in Linux).
When a segment arrives on any subflow, and its DSN is in order, we wake 
up the application. The adapted tcp_recvmsg then receives data from all 
subflows at once, iterating over them.

*tcp_sendmsg(): almost no changes here. Basically it now sends at most 
one segment, in order to give the opportunity for the scheduler to send 
next segment to another subflow. The function is now used for subflow 
sending, and the sendmsg() syscall is now directed to a mtcp_sendmsg() 
function (for scheduling), that in turn calls the almost unmodified 
tcp_sendmsg().

> what sorts of new functions were added and why,
I explained above changes necessary to regular TCP. Now of course we 
have a set of MPTCP new functions. They are divided in two files. One 
(mtcp.c) is mainly for scheduling and general MPTCP actions (state 
creation/suppression/new subflows). Basically that one is more about 
policy. The other one, mtcp_pm.c (pm stands for Path Manager), 
implements path management as defined in the proto draft. If we want to 
manage paths differently, we can just ignore that file and define 
another one with another path manager. Currently there is one alternate 
path manager, which is Shim6. Shim6 will probably be maintained as a 
separate patch in the future, in order to have one patch that exactly 
follows the ietf spec.
So, mtcp_pm.c implements JOIN reception, ADD_ADDR, token-related operations.
> where was the majority of development and testing time spent?
Up to now, much of the effort went to getting a good scheduler and 
buffer management at receive/sender side. Experience from this has been 
shown in the presentation. The main goal at the moment is to be able to 
fill all available paths in a range of situations (differences in 
delays/bw/losses). I use a test suite that verifies many combinations of 
those parameters. I also checked the influence of TSO. Basically TSO is 
good when we have high bandwidths (1gig), but for 10/100mbps, it is 
better to disable it, to enable finer grained scheduling.

Joerg Wagner has also recently provided a patch that allows dynamic 
addition/removal of paths, which is useful for mobility. I will probably 
integrate it soon.

I also implemented data reinjection (reinjecting segments from one 
subflow to another upon timeout), allowing survival from path failures, 
but some bugs still need to be fixed there.
> Were there protocol design choices, that if eliminated, would have dramatically simplified the implementation or allowed greater reuse?
>    
Globally, I think that most of the complexity comes from the desire to 
aggregate multiple TCP subflows under one single logical connection. 
That is, the source of complexity is the core... Now, details of the 
protocol do not look like critical to implement. Only the JOIN is a bit 
heavy to implement, but we can probably not replace it with something 
cheaper in the protocol.
> - Could you expand on buffering trade-offs, especially as relates to memory use, memory/data flow, implementation complexity, and obligations as relate to the specification -- "kernel memory" is expensive, especially in embedded mobile environments, and the apparent implications of copying and storing data many times are concerning.
Much work has already happened in that area. You seem to think that data 
is copied and stored many times. In fact it is not copied/stored any 
more times then in normal TCP. The data flow is, as for regular TCP: 
user space->kernel space, then kernel space->NIC (read from right to 
left for reception). When data is re-scheduled, only sequence numbers 
and linking are changed, the data itself is not moved nor copied. I 
agree OTOH that data re-scheduling, while having no memory cost, does 
have a processing cost, which is why we will evaluate the alternate 
design of using a single MSS for all subflows and pre-building the 
segments in a shared queue (see presentation). In that alternate design 
there is no need for re-scheduling and even for scheduling.
But this saves only processing, not memory. The only case where actual 
duplication is done is when a flow is failing, and we needed to reinject 
the data on another subflow, without removing it from the original one. 
But the impact from this is limited, since the number of segments to 
move is at most one congestion window. Currently I copy the segments, 
but as Costin proposed, we could replace this with a clone, meaning that 
only the control structure (skbuff) is copied, and the data part is kept 
in a single place.
Now we can remove the need for duplicating data altogether by changing 
the protocol and adding an "advance seqnum" option, allowing to tell the 
other end that a range of seqnums can be ignored. This was present in a 
previous version of the spec draft, but was later removed for middlebox 
compatibility reasons.
>   Could you specifically address the memory overhead as compared with regular TCP in various scenarios given the current implementation, and say a bit more about alternative implementations? (You talked a little about when to segment data and push it down to sub-flows, for example)
>    
Alternative implementations, and implementation-specific memory 
overheads are described in paragraph above, but then comes MPTCP memory 
overhead. I mean, the overhead that you __cannot__ avoid in any 
implementation, given you want to reasonably use all the paths.
MPTCP overhead is the following: with multiple subflows, not only you 
need to multiply the rcv/snd buffer size by the number of subflows, but 
in fact you need even to allow more than that. The receiver must be able 
to accept data on all subflows while the slowest of them is fast 
retransmitting, giving a global receive buf of size 
2*sum_i(bw_i*max_i(delay)) for each path i.
The sender must ensure that each of its subflows has equal height (see 
height definition in presentation), otherwise it cannot fully utilize 
subflows having lower values of cwnd. This gives an aggregate sndbuf of 
size 2*sum_i(bw_i*max_i(delay)), in fact the same as the receive buffer.

Now that we have the requirement for fully utilizing all subflows, 
nothing stops us from disabling some of them when we are under memory 
pressure.
> - Where do current prototypes diverge from the specification driven by complexity / feasibility concerns? Do you see resolving them through changes to the implementation, or changes to the protocol…
Currently I think that the spec is not a problem. As explained earlier, 
most of the complexity comes from the core principle of MPTCP, the rest 
are details.
The current divergence between implementation and specification is 
driven by development priorities, not by feasibility/complexity 
concerns. For example, my priority (other developpers may have other 
priorities) is to find out how MPCTP can work in a wide range of 
scenarios and give really improved experience for the application. Hence 
security for example is out of scope for me at the moment, and that's 
why I did not implement randomized IDSN, randomized token and CRC. Of 
course I hope that someone will add this so that we make spec and 
implementation closer and closer over time. Note that the spec can also 
still evolve, which is another reason to wait before implementing 
controversed stuff.
> - Could you expand on the "join" issue and its comparison to listen sockets. Listen sockets are one of the most complex and error-prone parts of current TCP implementations; in retrospect the join…
Indeed, it would be definitely possible to use SYN cookies, although 
this is not implemented yet.  As you say, I precisely follow almost 
exactly the code path for listening sockets. What I did currently, as a 
first step, is to copy-paste several critical functions from the 
listening socket code path into the mptcp-specific files, then adapt 
what is needed to make them work in the context of MPTCP. The 
alternative is to make legacy functions from that code path more 
general, so that MPCTP becomes able to call them. Here is a brief 
comparison between normal server-side establishment and JOIN-based 
establishment:
*server received a SYN. Regular TCP would make a socket lookup and find 
a LISTEN-state socket for that SYN.
MPTCP places a hook in the main entry point of TCP, before socket 
lookup, to replace this with a token-based lookup in MPTCP in case the 
JOIN option is present. The lookup result for regular TCP is a socket., 
for MPTCP it is a multipath control block, with a list of sockets.
*Then the SYN handling happens. If SYN cookies are not enabled, a 
minisock structure is created, the minisock being the smallest state 
possible needed to create the final socket when the establishment 
terminates. The minisock is created in both regular TCP and MPTCP. Then 
regular TCP attaches the minisock to an accept queue in the listening 
socket, while MPTCP attaches the minisock to an accept queue in the 
MPTCP control block.
*When the final ACK is received, regular TCP creates a full socket, 
based on the info in the minisock, and inheriting many things from the 
listening socket. The full socket is placed on a queue and the app is 
woken up. MPTCP creates a full socket as well and also enqueues it, but 
the app cannot be woken up because it is not waiting on an accept ! So 
what we do is that when the application enters a send/rcv syscall, we 
check if any new subflow has appeared in the "accept queue" of the 
multipath control block. If so, we attach this new socket to our list of 
subflows. This in turn complexify the receival procedure because a new 
subflow with new data in it can appear while the app is waiting for new 
data to arrive. Hence when the app is woken up, it must be prepared (the 
kernel part of the app I mean) to deal with either incoming data on any 
of its subflows, or appearance of a new subflow with new data in it.
*Finally, upon receival of a RST/FIN or close syscall, MPTCP can have 
several half-opened subflows that it must destroy correctly.
> - Could you say a bit more about your practical experience (and concerns) with the role of middle nodes, especially ones that don't change the "content" of the connection, but do make changes to se…
That's a good question I have not investigated very deeply, however 
there are a couple of things I can tell: TSO, as explained above, is 
well supported. I have tried to play with it and it works perfectly. 
However this does not mean that it is always efficient to use, because 
this forces the scheduler to sometimes allocate data with a minimum 
granularity of 64K, which is a lot. LRO is, to the best of my knowledge, 
not supported in current linux kernels. There are some patches around, 
but I think that they have never been merged into the mainline kernel. 
The same is true for TOE by the way.
I noticed that several firewalls change the ISN to fix themselves 
security flaws in windows98(maybe for some other reason as well). This 
is addressed in the current spec and implemented. NATs should be 
supported as well, but for some reason I have not explored yet, 
communications don't work accross them. But I guess this is a minor 
problem. I have not tried to play with other kinds of middleboxes.
> - How to use non-protocol policy sources to inform congestion control and scheduling decisions, such as affinity information in multicore/multi-queue environments, power management, out-of-band top…
I guess this is a question for the API guys. I did not look at this at 
the moment.
> - Interactions between existing load balancing technologies such as ECMP and RSS: where multipath TCP is helped, and where it is hurt, and how to influence future iterations of those technologies s…
Maybe someone else can comment on this. What I can say about the 
implementation, is that the 5-tuple can indeed be easily replaced by a 
logical connection identifier, since that is already what we do when 
MPTCP is used with Shim6.
An architecture proposal on how to deal with other ways to present paths 
can be found in section 3 of the following document:
http://trilogy-project.org/fileadmin/publications/Deliverables/D4_-_Design_Space_Analysis_for_Reachability.pdf
> - More generally: could you clarify the extent to which the current Linux prototype is a research platform vs. a tech transfer target -- very different things, and Sebastien's slides mentioning the…
I tried to design this implementation as both. However, there is clearly 
still some work ahead before it becomes acceptable for inclusion in the 
kernel. In particular we need to put Shim6 as a separate patch, that can 
be submitted separately/later. We also need to refactor part of the 
code, so as to optimize some structure sizes, as pointed out by a Linux 
reviewer.

BTW, what kind of trade-offs are you mentioning here ? I am not sure to 
follow that sentence.
> I'm particularly concerned that the current Linux prototype considers "SMP optimizations" a footnote rather than a primary design concern: one of the central thrusts of the last decade of OS design has been adapting to the multicore world. MP-TCP has immediate implications for multiprocessor efficiency for a variety of reasons, not least due to interaction with multi-queue network cards. While this may not be an immediate worry on the smart phone end (one of the strongest perceived applications for MP-TCP), remember that at the other end of the Internet are piles of multiprocessor servers in data centres. If MP-TCP reduces their scalability by 30% for busy TCP environments, that's a huge adoption concern in terms of power use, number of Us, etc. We need measurements to understand these issues concretely (i.e., do they really exist?), and from what I heard, it sounds like the current Linux prototype is not yet sufficiently mature to explore this issue. The results of that inve
>   stigation may drive protocol changes, so it's imperative that this be considered sooner rather than later.
>    
agreed. I hope that will be sooner :-). The number of developpers 
interested in contributing to this Linux prototype is currently 
increasing. We will certainly take your comments into account, and try 
to do your proposed evaluations asap.
> Rather than sound all-negative, I do want to say that MP-TCP is a really interesting area that we (the FreeBSD community) would like to engage with. We have lots of immediate downstream consumers o…
Thanks again for your in-depth comments ! This will definitely influence 
further work on the implementation.

regards !

Sébastien.
> Robert Watson
> University of Cambridge
> Computer Laboratory
> _______________________________________________
> multipathtcp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/multipathtcp
>    

-- 
Sébastien Barré
Researcher,
CSE department, UCLouvain, Belgium
http://inl.info.ucl.ac.be/sbarre

---

From: "Robert N. M. Watson" <[email-masked]>
Date: Mon, 26 Jul 2010 19:21:43 +0100

> I'll try to answer inline:

Hi Sebastien--

Thanks for the detailed reply -- it's given me much to chew on! I'll follow up when I've had time to digest (metaphorically speaking).

Robert