Subject: [multipathtcp] draft terminology: MPTCP control block variable SND.NXT

From: Nigel Williams <[email-masked]>
Date: Mon, 12 Nov 2012 17:53:37 +1100

Hi all.

Thanks to Yoshifumi for keeping an eye on jabber during the session, 
though the time-lag did prove to be a bit of an obstacle.

Following on from the point we had regarding 'DS SND.NXT'.

 From the draft [1] v12, p59, Section B.1.2 (variables in the MPTCP 
control block):
"SND.NXT (64 bits):  This is the Data Sequence Number of the next byte 
to be sent.  SND.NXT is used to determine the value of the DSN in the 
DSS option."

This terminology is borrowed from regular single flow TCP, but it's 
meaning does not seem to us to be the same in the MPTCP context. When a 
subflow asks the scheduler for new data to send, the scheduler allocates 
a chunk of the TX socket buffer to the subflow, tells the subflow the 
starting DS value for the chunk and the length of the chunk. The subflow 
then proceeds to send a DS map for the chunk and all the associated data 
before calling back up to the scheduler to get a new chunk allocated.

Each subflow's internal concept of snd.nxt makes sense as in the regular 
single flow TCP case, but at the DS level, packets leave the machine 
with DS-level sequence numbers that jump all over the place (when using 
mappings > 1-MSS on multiple subflows). The interesting variable at the 
DS level is really the largest DS value mapped to a subflow i.e. the 
right most edge of the TX socket buffer which designates the boundary 
between bytes which have been mapped into subflows and bytes which have 
not. This is not analogous to an individual TCP flow's SND.NXT though, 
hence the point of discussion.

cheers,
nigel

[1] http://www.ietf.org/id/draft-ietf-mptcp-multiaddressed-12.txt

---

From: Christoph Paasch <[email-masked]>
Date: Mon, 12 Nov 2012 10:14:27 +0100

Hi Nigel,

On Monday 12 November 2012 17:53:37 Nigel Williams wrote:
> mappings > 1-MSS on multiple subflows).

This depends on the scheduler, and I don't see why mappings > 1-MSS affects 
this.

Is the data leaving the sender out-of-order on the data-sequence number space 
in your implementation?

In our implementation, even if the mapping would be > 1-MSS, the SND.NXT is 
simply increasing as new data is pushed out on the network.
I believe that. sending the data in-order on the DS-level allows an easier 
handling of the meta-level retransmission timer.

Cheers,
Christoph

> The interesting variable at the
> _______________________________________________
> multipathtcp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/multipathtcp
-- 
IP Networking Lab --- http://inl.info.ucl.ac.be
MultiPath TCP in the Linux Kernel --- http://mptcp.info.ucl.ac.be
Université Catholique de Louvain
--

---

From: Yoshifumi Nishida <[email-masked]>
Date: Mon, 12 Nov 2012 18:04:06 -0800

Hi Christoph, Nigel,

In my understanding, in TCP, seqno before SND.NXT is already sent to
the network, while in case of MPTCP, this is not always correct. So,
in a sense, the meaning of SND.NXT might be slightly different,
although I'm not very sure if this is a problem.

Thanks,
--
Yoshifumi

---

From: Nigel Williams <[email-masked]>
Date: Wed, 14 Nov 2012 10:57:58 +1100

Hi Christoph,

> This depends on the scheduler, and I don't see why mappings > 1-MSS affects

This is why we think the variable name might be inappropriate, as, 
depending on the scheduler, ds snd.nxt might not always be the actual 
bytes 'sent next'. So in cases where the scheduler might provide 
multiple packet mappings to multiple subflows at the same time, the 
single-flow TCP meaning of snd.nxt doesn't translate to mptcp (as what 
snd.nxt points to is not always the next bytes transmitted).

> Is the data leaving the sender out-of-order on the data-sequence number space

In our implementation, depending on the scheduler, for certain scenarios 
where there are multiple subflows and DS mappings that cover multiple 
packets, it would be possible for packets to leave the sender 
out-of-order (DS-wise). A quick explanation of how our send buffer works 
might help demonstrate this.

Given that the subflows share a send buffer, in order to minimise 
locking of the send buffer and mptcp control structure a scheduler might 
pre-allocate 'chunks' of data to each subflow. The subflow knows the 
DS-number at the start of the chunk and is able to send the entire chunk 
without needing to call into the mptcp layer/sendbuffer. We do not 
strictly increment a DS-level snd.nxt at this time, our equivalent might 
be called the 'ds_unmapped' (i.e. the highest sequence number that has 
been mapped to a subflow + 1). Each subflow maintains its own snd.nxt 
pointer into the mapping (as per standard tcp).

At the subflow level, DSS maps can be used for the first packet of the 
mapping. For example, in the case where we have two subflows 
transmitting data at the same time, they are each allocated a contiguous 
chunk from the send buffer (Subflows A and B in Figure 1). Each subflow 
then will attempt to transmit the bytes it has been allocated from the 
send buffer, and does not call back into the ds-level until the map is 
exhausted (ideally). Given that subflow A and B start from different 
DS-numbers, and they are transmitting at the same time, the segments 
leave the sender out-of-order at the DS level.

      <--------- increasing DS
+=========+========+=========+
|uuuuuuuuuubbbbbbbbbaaaaaaaaaa
|uuuuuuuuuubbbbbbbbbaaaaaaaaaa
+=========+========+=========+
           |        |       | |
      ds_unmapped   B       | A
                            |
                     ds_una (for e.g.)

Figure 1: Maps allocated to subflows A and B from the send buffer. 
Assume maps are greater than 1-MSS. ds_una is increased based on D-ACKS.

So from the implementation perspective, the variable represents the next 
unmapped byte in the DS-space, rather than the next DS byte to be sent.

> simply increasing as new data is pushed out on the network.

I can't picture how this works, would you be able to provide a similar 
explanation (as above) as to how you are able to transmit packets in 
DS-order with multiple concurrent subflows with mappings > 1-MSS? 
Perhaps we could schedule a Skype chat to discuss some of these points?

cheers,
nigel

---

From: Christoph Paasch <[email-masked]>
Date: Wed, 14 Nov 2012 10:48:44 +0100

Hi Nigel,

On Wednesday 14 November 2012 10:57:58 Nigel Williams wrote:

[...]

> > Is the data leaving the sender out-of-order on the data-sequence number
> > space in your implementation?
> 

ok, I understand now what you mean. Thanks for the clarifications.

The DS-snd.nxt must be seen from the MPTCP-level point-of-view, where the 
subflow-level is one layer below the MPTCP-level.
As soon as a subflow has been allocated to a chunk of the data, this chunk has 
"moved" from the MPTCP-level to the subflow-level, and thus the send-next must 
increase. "moving" the chunk to the subflow-level can be seen as sending the 
data.

It is the same as for the TCP-level snd-nxt. Pushing a segment from the TCP-
layer down to the IP-layer, and thus increasing snd-nxt, does not necessarily 
mean that the segment is "physically" leaving the machine. It may be delayed 
for a long time in underlying queues (e.g., inside a tc qdisc) of the 
operating system.

So, in general I would say that "send" just means that the data is "moved" one 
layer further down the stack.

> Perhaps we could schedule a Skype chat to discuss some of these points?

For me, "sending" at the MPTCP-layer simply means that the data is pushed one 
level further - thus down to the subflow-level. So, the packets may be leaving 
the machine out-of-order at the DS-level, but we anyways can't control this.

Cheers,
Christoph