Subject: [multipathtcp] q about initiating subflows and slow-start

From: Yoshifumi Nishida <[email-masked]>
Date: Tue, 15 Jun 2010 18:33:55 -0700

Hello,
While I was working on ns-2 implementation, I encountered several questions
about mptcp protocol.
These might be implementation issues, but I personally would like to bring
up this so that we might be able to see if there're any potential issues.

1: starting new subflow
    let's say we have two endpoints (A,B) and both nodes have two addresses
(A1, A2) and (B1, B2)
    We presume A only knows B1 to reach B. Here, how these two nodes
exchange address information and initiate subflows?
    I have the following tentative cases in my mind for the sequence of
initiating subflows.

     case 1:
         subflow1: A1->B1  (since A knows B1)
         subflow2: B2->A1  (since B now knows A1)
         subflow3: A2->B1
         subflow4: B1->A2  (since B now knows A2)
         subflow5: A1->B2  (since A now knows B2)
         subflow6  A2->B2  (if necessary? )

     case 2:
         subflow1: A1->B1 (since A knows B1)
              A tells B that A2 is available by addr option
              B tells A that B2 is available by addr option
         subflow2: B1->A2 (since B now knows A2)
         subflow3: A1->B2 (since A now knows B2), but failed to establish
connection?
         subflow4: A2->B2 (if necessary?)

     Here, I have several questions.
       1: case 1 looks a bit redundant. Can we have better sequence?
       2: case 2 expects that all multi-homed end nodes to send addr option
properly, but is this a right way?
       3: To initiate a connection like (A2-B2),  mptcp stack will need to
specify src IP address for subflow, but isn't it a bit tricky?

2: slow-start
    I guess we probably should disallow subflows to perform slow-start
simultaneously.
    I think we need to clarify this point in the draft, although no draft
mentions about this so far.

   Also, if we allow only one subflow to perform slow-start at a time. we'll
have the following questions.
      1: during one subflow is performing slow-start, shouldn't we initiate
new subflow?
      2: or, during one subflow is performing slow-start, can we initiate
subflows with congestion avoidance?
      3: or, during one subflow is performing slow-start, can we initiate
subflows and perform slow-start with round-robin scheduling?
   Doesn't these choice affect the performance of congestion control?

Thanks,
--
Yoshifumi Nishida
[email-masked]

---

From: Ehsan Elahi <[email-masked]>
Date: Wed, 16 Jun 2010 01:04:06 -0700 (PDT)

1: starting new subflow:       I think both cases looks a bit redundant. By doing like this we can never ensure that the subflows are passing through distinct paths. Every time at least two or more subflows will be passing through some shared bottleneck. By adding the redundant subflows may not contribute in the performance improvement. In the given scenario, I think only two subflows should be initiated not more than these and the case may be like this:
 subflow1: A1->B1 (since A knows B1)              Only B tells A that B2 is available by addr option (Because A initiated first flow therefore it should also initiate subsequent flows)  subflow2: A2->B2 (if A2 is available)
2: slow-start      I could not understand why we should disallow subflows to perform slow-start simultaneously?
Regards
Ehsan
--- On Wed, 6/16/10, Yoshifumi Nishida <[email-masked]> wrote:

From: Yoshifumi Nishida <[email-masked]>
Subject: [multipathtcp] q about initiating subflows and slow-start
To: [email-masked]
Date: Wednesday, June 16, 2010, 6:33 AM

Hello,While I was working on ns-2 implementation, I encountered several questions about mptcp protocol. These might be implementation issues, but I personally would like to bring up this so that we might be able to see if there're any potential issues. 

1: starting new subflow    let's say we have two endpoints (A,B) and both nodes have two addresses (A1, A2) and (B1, B2)    We presume A only knows B1 to reach B. Here, how these two nodes exchange address information and initiate subflows?
    I have the following tentative cases in my mind for the sequence of initiating subflows.
     case 1:          subflow1: A1->B1  (since A knows B1)         subflow2: B2->A1  (since B now knows A1)
         subflow3: A2->B1           subflow4: B1->A2  (since B now knows A2)         subflow5: A1->B2  (since A now knows B2)         subflow6  A2->B2  (if necessary? )   

     case 2:         subflow1: A1->B1 (since A knows B1)              A tells B that A2 is available by addr option              B tells A that B2 is available by addr option 
         subflow2: B1->A2 (since B now knows A2)         subflow3: A1->B2 (since A now knows B2), but failed to establish connection?          subflow4: A2->B2 (if necessary?)

     Here, I have several questions.        1: case 1 looks a bit redundant. Can we have better sequence?       2: case 2 expects that all multi-homed end nodes to send addr option properly, but is this a right way?
       3: To initiate a connection like (A2-B2),  mptcp stack will need to specify src IP address for subflow, but isn't it a bit tricky?  
2: slow-start    I guess we probably should disallow subflows to perform slow-start simultaneously.
    I think we need to clarify this point in the draft, although no draft mentions about this so far.       Also, if we allow only one subflow to perform slow-start at a time. we'll have the following questions.
      1: during one subflow is performing slow-start, shouldn't we initiate new subflow?

      2: or, during one subflow is performing slow-start, can we initiate subflows with congestion avoidance?      3: or, during one subflow is performing slow-start, can we initiate subflows and perform slow-start with round-robin scheduling?  
   Doesn't these choice affect the performance of congestion control?

Thanks,--Yoshifumi [email-masked]

-----Inline Attachment Follows-----

_______________________________________________
multipathtcp mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/multipathtcp

---

From: "Koojana Kuladinithi" <[email-masked]>
Date: Wed, 16 Jun 2010 10:51:27 +0200

Hello,

Since the following discussion is related to the initiation of sub flows,
thought of asking  a very basic question.

In practice, can somebody point out an example where a server can initiate a
connection to a client? 

If not, how does the following discussion related to sub-flow initiation
from both side work? Does mptcp define some special signaling to let the
server know a port in the client to connect?

Koojana 

From: [email-masked] [mailto:[email-masked]]
On Behalf Of Ehsan Elahi
Sent: Wednesday, June 16, 2010 10:04 AM
To: [email-masked]
Subject: Re: [multipathtcp] q about initiating subflows and slow-start

1: starting new subflow:

       I think both cases looks a bit redundant. By doing like this we can
never ensure that the subflows are passing through distinct paths. Every
time at least two or more subflows will be passing through some shared
bottleneck. By adding the redundant subflows may not contribute in the
performance improvement. In the given scenario, I think only two subflows
should be initiated not more than these and the case may be like this:

              Only B tells A that B2 is available by addr option (Because A
initiated first flow therefore it should also initiate subsequent flows) 

 subflow2: A2->B2 (if A2 is available)

2: slow-start

      I could not understand why we should disallow subflows to perform
slow-start simultaneously?

Regards

Ehsan

Hello,

1: starting new subflow

     case 1: 

         subflow3: A2->B1  

     case 2:

 

2: slow-start

Thanks,

--

Yoshifumi Nishida

[email-masked]

---

From: Costin Raiciu <[email-masked]>
Date: Wed, 16 Jun 2010 09:55:17 +0100

Hi Yoshifumi,

These are very good questions. 

Case 1 clearly opens too many subflows - 2 per path. I would say the max number of subflows is the number of available paths (in this case 4 subflows). 

To achieve Case 2, we can both client and server to send SYNs for all paths (as in 1): some of these SYNs will overlap in flight, and we'll have simultaneous opens (assuming the ports are known). Others will not overlap in flight and will do the regular open (i.e. if you haven't sent a syn for a path, and you get a syn for it, you send back a syn/ack).

Your question 2: I don't understand what you mean by sending the addr option properly.
For question 3: say the client stack specifies the source ip. If it happens to be natted, the server won't be able to connect. The server will also send B2; if this is natted too, A2-B2 won't be set up.

An interesting question is how many subflows to open. The max is the number of paths. Currently this should not be an issue, we will most likely have one single homed box connect to a multi-homed box in most cases.
However, the question of how many subflows we should open assuming max is some big number (say 20), and when to open them is still open. Research needs to be done to understand the tradeoffs between having small windows on each subflow (which happens if you have many of them sharing a common bottleneck), and increased throughput and robustness given by using different paths.

For slow start:
Why do you think we should disallow simultaneous slow start? If two subflows slow start together on a bottleneck, they will behave as a single subflow that started slow start one rtt earlier. I don't see this as being bad.
Disallowing slow start once one or a few subflows are in cong avoidance might make sense if they share a common bottleneck: in this case, the new subflow will cause losses to the existing ones. I don't see this as particularly bad, so I don't think it's worth optimizing for. More importantly, slow start allows us to get up to speed when the subflow starts on a new path. A good property of  the congestion controller is that it does not try to detect  shared bottlenecks explicitly. I think we should keep the same feature for slow start.

Cheers,
Costin

On 16 Jun 2010, at 02:33, Yoshifumi Nishida wrote:

> Hello,
> While I was working on ns-2 implementation, I encountered several questions about mptcp protocol. 
> These might be implementation issues, but I personally would like to bring up this so that we might be able to see if there're any potential issues. 
> 
> 1: starting new subflow
>     let's say we have two endpoints (A,B) and both nodes have two addresses (A1, A2) and (B1, B2)
>     We presume A only knows B1 to reach B. Here, how these two nodes exchange address information and initiate subflows?
>          subflow3: A1->B2 (since A now knows B2), but failed to establish connection? 
>        2: case 2 expects that all multi-homed end nodes to send addr option properly, but is this a right way?
>     I guess we probably should disallow subflows to perform slow-start simultaneously.
>     I think we need to clarify this point in the draft, although no draft mentions about this so far.
>     
>    Also, if we allow only one subflow to perform slow-start at a time. we'll have the following questions.
>       2: or, during one subflow is performing slow-start, can we initiate subflows with congestion avoidance?
>       3: or, during one subflow is performing slow-start, can we initiate subflows and perform slow-start with round-robin scheduling?

---

From: "Koojana Kuladinithi" <[email-masked]>
Date: Wed, 16 Jun 2010 10:59:46 +0200

I think issues related to slow-start have to be considered specially when
physical connections are sharing some links. In this situation, use of one
flow might perform better than using several flows simultaneously ?

Koojana

1: starting new subflow:

2: slow-start

Regards

Ehsan

Hello,

1: starting new subflow

     case 1: 

         subflow3: A2->B1  

     case 2:

 

2: slow-start

Thanks,

--

Yoshifumi Nishida

[email-masked]

---

From: Mark Handley <[email-masked]>
Date: Wed, 16 Jun 2010 10:36:39 +0100

For the most part we're talking about heuristics here, and so long as
interoperability is not affected, different endpoints can apply
different heuristics in different circumstances.
Anyway, here's what I've been assuming, but we really should figure
out some experiments to validate these heuristics.

Case 1:
The most common circumstance is probably what we could call Internet
client-server.  In such a case, the client can be expected by default
to be NATed and the server can by default be assumed to not be NATed.
Thus the default setup would be:

subflow1: A1->B1
  server sends B2 in Add Address option.
  client can now choose from A2->B1, A2->B2, or A2->B2.  Best choice
is A2->B2 as it is maximally diverse.
subflow2: A2->B2
  If things are working well, we might stop there.
  Client may have local policy as to preferred interfaces, costs, etc.
 If it has a preference, next subflow uses that policy.  If not, given
clients are more often the the bottleneck than the server, then the
next subflow would be via whichever client address has the larger
rate.
If W1/RTT1 > W2/RTT2, then:
  subflow 3: A1->B2
  if desired, subflow 4: A2->B1
else:
  subflow 3: A2->B1
  if desied, subflow 4: A1->B2

When would we not use this policy?

Case 2.  server is NATed too, so Add Address isn't useful.
Case 3.  both client and server are on same L2 subnet (can assume no NATing).

Case 2.
   For anything to work when both client and server are NATed, we need
simultaneous open.  That only works with bound local ports.  If you
bind the local port or address, MP-TCP would by default turn itself
off because the app has expressed a preference about subflow IDs.  So,
realistically this isn't an issue without using an extended API.  If
you have an extended API, the app controls subflow setup in this case.

Case 3.
  This is the likely case on a LAN or in a data centre.  To answer the
question here, we need to get into hypothetical topologies.  Suppose
for example that A1 and B1 are on one subnet and A2 and B2 are on a
different subnet (probably these are VLANs).  In this case we get:
  subflow 1: A1->B1
    Add Address can be sent in both directions - likely this is a
sysctl that is enabled when desired.  Whichever side decides there's
enough data to warrant starting a new subflow kicks it off.
 subflow 2: B2->A2
   or
 subflow 2: A2->B2
No more subflows should be started because both subflows are link-local.

There's another interesting case:
Case 4:
  Client and server are MP-TCP capable but only have one address each.
 Normally they wouldn't start any additional subflows, but this can be
overridden by a sysctl.  Why would you want to?  Because the site uses
ECMP to load balance across multiple links.  In this case, if enabled,
the client sets up additional subflows between A1 and B1, but using
additional local ports so the flows hash differently on the ECMP
links.

There are probably other special-case heuristics too, but these seem
to be some common ones.

- Mark

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 16 Jun 2010 03:33:46 -0700

>    If things are working well, we might stop there.

I don't see how the client can tell that the set {A1->B1, A2->B2} 
contains more diversity than the set {A1->B2, A2->B1}. Here is an 
example where the former set shares a bottleneck link and the latter 
does not:

      A1 --- ISPX --- B2
               |
      A2 --- ISPY --- B1

Thus wouldn't we want to create all four subflows and see which perform 
better?

    Erik

---

From: Mark Handley <[email-masked]>
Date: Wed, 16 Jun 2010 12:02:53 +0100

On 16 June 2010 11:33, Erik Nordmark <[email-masked]> wrote:
> I don't see how the client can tell that the set {A1->B1, A2->B2} contains
> more diversity than the set {A1->B2, A2->B1}. Here is an example where the
> former set shares a bottleneck link and the latter does not:
>
>     A1 --- ISPX --- B2
>              |
>     A2 --- ISPY --- B1
>

Yes, it would be reasonable to create all four flows if the data
transfer is long enough to warrant it.  For any heuristic you can come
up with counter cases - that's why they're heuristics.  But you've got
to pick a default heuristic, and congestion is most commonly on tail
circuits.  So using all the available tail circuits (to the extent you
can tell from addresses) as early as possible in the connection is as
good a default heuristic as I can think of.

Now a second question would be whether there's any good heuristic to
tell you to stop at two, or to continue on to more?

 - Mark

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 16 Jun 2010 05:35:16 -0700

> good a default heuristic as I can think of.

For bandwidth the tail circuits might be more likely to be the limit.
But delay is probably different. And historically we've had internet 
exchanges with significant packet drops - I don't know if that is an 
issue of the past or not.

> tell you to stop at two, or to continue on to more?

One could try to infer some "closeness" by looking at the number of 
common bits between a source address and destination address, which is 
basically assuming that if A1 and B2 have 15 bits in common and A1 and 
B1 only have 6 bits in common, then A1 and B2 are more likely to be 
connected to the same ISP. RFC 3484 has that as one component in the 
IPv6 source address selection.

In simplistic cases like my example that might help, but there might be 
other cases where it would make no difference or even hurt.

Short of that (or something similar that looks at information available 
before the subflows are set up), one would have to setup the N*M 
subflows and observe their performance.

    Erik

---

From: Yoshifumi Nishida <[email-masked]>
Date: Wed, 16 Jun 2010 17:21:50 -0700

Hello Costin,

Thanks for the response.

The reason why I thought we should disallow simultaneous slow-start is it
might violate our goal2 in congestion control (Do not Harm).
If we allow simultaneous slow-start, I guess mptcp will be able to eat
bandwidth number of subflows times faster than normal TCP when they all use
the same bottleneck. Isn't it a bit aggressive behavior?

Thanks,
--
Yoshifumi Nishida
[email-masked]

2010/6/16 Costin Raiciu <[email-masked]>

>
> For slow start:
> Why do you think we should disallow simultaneous slow start? If two
> subflows slow start together on a bottleneck, they will behave as a single
> subflow that started slow start one rtt earlier. I don't see this as being
> bad.
> Disallowing slow start once one or a few subflows are in cong avoidance
> might make sense if they share a common bottleneck: in this case, the new
> subflow will cause losses to the existing ones. I don't see this as
> particularly bad, so I don't think it's worth optimizing for. More
> importantly, slow start allows us to get up to speed when the subflow starts
> on a new path. A good property of  the congestion controller is that it does
> not try to detect  shared bottlenecks explicitly. I think we should keep the
> same feature for slow start.
>
> Cheers,
> Costin
>
>

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sun, 20 Jun 2010 18:42:20 -0700

Hi Mark and folks,
thanks for the very nice clarification.
I personally think that we'll need to have a proper logic to initiate
subflows, otherwise some implementations do this in too redundant ways
and others do this in too conservative ways. I feel a draft (protocol
draft?) needs to mention this.

So, I'm trying to think about a minimal recommendable logic for mptcp
end-point. How about something like this?

1: Passive end-point.
    If it has another address, send the info with add addr option unless
          a) the address is not NATed.
          b) any other condition?

    Add addr option will be sent
          a) with syn ack ?
          b) with first non-syn data or ack packet from this end-point?
          c) triggered by timer ?
          c) any other choice?

2: Active end-point
    Wait for add addr options until
           a) a certain amount of  time has passed to get as many options as
possible?
           b) no waiting?
           c) any other choice?

    if it gets new addresses through options, it initiates new subflows to
new addresses.
            the source address will be chosen to maximize diversity unless
there are other policy requirements.

    if it don't get any addr options for a certain amount of time, it starts
new subflows

I think this logic can support case1 and case3.
Since case2 and case4 don't look common cases, I think they can be excluded
from normal procedure.

Thanks,
--
Yoshifumi Nishida
[email-masked]

2010/6/16 Mark Handley <[email-masked]>