Subject: Shared bottleneck concern with CMT [was Re: FW: ssthressh]

From: Janardhan Iyengar <[email-masked]>
Date: Tue, 19 Jul 2005 13:24:35 -0400 (EDT)

Brian,

Thank you for the detail you have provided in this email.

>> That is what we had intended when we introduced the term "CMT". Glad to
>> see that you use the term in the same sense.
>
> Well, am I using it the same way you are then, or not?

Yes.

>> I do not know how you do it.. I have asked you
>> repeatedly, in vain, to share your algos in the past. I see that you have
>> given more info in the email to Randy - comments below.
>
> The selection algorithm was last posted to tsvwg, 31 Mar 2005, under the
> thread "SCTP load balancing policy - reg".

I saw the email. In gist, you have two parts:

/*
  *  RATE ROUTE
  * 
-------------------------------------------------------------------------
  *  Rate the provided route according to a weighting function.
  */

and

/*
  *  BREAK TIE
  * 
-------------------------------------------------------------------------
  *  Break a tie between two equally rated routes.
  */

It is still a path selection mechanism for sending, and I have seen that 
several times. I still do not understand how it covers CMT, reordering 
troubles, and shared bottleneck detection!

> Actually, I lied.  Looking at the code, this is done at the receiver to handle
> sacks.  So, let me describe things again.
>
> 1. At the receiver, when I receive a new TSN and while performing gap
>   algorithm I determine whether the sender is making "progress", where
>   progress is defined as a shrinking or collapsing gap.  When the
>   receiver goes to send a SACK due to gap reports, I suppress the SACK
>   generation (and fall back to delayed SACK) iff the sender was making
>   progress.  (See function sctp_recv_data).
>
> 2. At the receiver, when I go to send a SACK, I don't if there are more
>   received packets to process in the socket's receive queue (packets
>   that passed checksum and vtags checks and arrived at the socket while
>   I was processing the current packet.  Due to queuing delays, this
>   normally only occurs in implementation when a packet is received from
>   an interface which is independent from the interface for the packet
>   that is currently being processed.  (See functions sctp_bundle_more
>   and sctp_bundle_sack.)
>
> 3. At the sender, when I receive a SACK acknowledging data, and I have
>   gaps, I mark all destinations with messages outstanding in gaps as
>   "eligible for FR".  Then, if the SACK acknowledges data within a
>   gap, I mark the destination to which that data belonged as
>   "ineligible for FR".  Then, when I go to do FR calculations on
>   messages unacknowledged in the gap, I skip the calculation for
>   messages sent to destinations marked "ineligible for FR".  This not
>   only works for CMT but makes FR less sensitive to networks that
>   reorder messages (even for single-homed associations).  As it is less
>   aggressive than RFC 2960, it is probably OK.  Also, it does not change
>   the situation that if a block of messages is consistently reported
>   as missing in SACK gap reports, FR will be performed on those
>   messages.  I should point out, however, that this is a more recent
>   improvement, I used to to the same thing as in (1.) above at both
>   the receiver and sender and that older method is what the performance
>   results posted at http://www.openss7.org/sctp_perf.html were base on.
>   (See function sctp_recv_sack.)

Thank you for these details! I am assuming that what you mean by less 
aggressive than RFC2960 is that your sender might need more missing 
reports before an FR.

These are reasonable heuristics. And like you mention, your sender is less 
aggressive than RFC2960 *when marking for FR*. That is, unnecessary FRs 
would be reduced.

But the reason I do multiple queues is because I do not want to be less 
aggressive than RFC2960. I want to be *as aggressive as* RFC2960 when 
marking for FR, for performance reasons. Multiple queues gives me that 
ability, and is not much of a hassle to code into existing stacks. Randy 
and I are adding the code for multiple queues in the KAME stack, and it 
was quite easy to integrate. Also the way the algos are written as deltas 
to existing code, the added complexity should (hopefully) not be much.

> The last time we discussed this (October of last year) you were going to 
> write (update) an internet-draft on which I was looking forward to 
> commenting.  How is that coming along?

Thank you for reminding me, I almost forgot about it! The algo has been 
published as the SFR-CACC algo earlier though. I'll try to get it out soon 
for either this or the next IETF.

> I'm sorry but I do not want to spend too much time walking you through
> all of the details, when you appear to refuse to download the code and
> look at it yourself, [...]

Thank you for sharing whatever details you have shared so far, and 
particularly in this email. I do see that your heuristics will help reduce 
unnecessary FRs and reduce ack traffic. I still disagree that the shared 
bottleneck problem does not exist in your case. You also haven't addressed 
the concern of separating cumack info per path.

In my CMT algos, I have tried to get deterministic behavior for the most 
part, and I also sincerely think that I have *tighter* heuristics when I 
use heuristics. The only place I can think of where I use heuristics is in 
the DAC algo (for reducing ack traffic).

- jana

---------------------------------------------------------------
Janardhan R. Iyengar           http://www.cis.udel.edu/~iyengar
Protocol Engineering Lab  --   CIS   --  University Of Delaware
---------------------------------------------------------------

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Tue, 19 Jul 2005 16:22:09 -0600

Janardhan,

Elementary Queuing Theory tells us the the type of deterministic traffic
splitting that you describe, when applied to pure birth-death arrival
processes, will result in independent (pure birth-death process) traffic
flows.  It is, of course, the basis of Markov chains, and holds because
the "memoryless" properties of the pure birth-death process are
preserved across the split.

Thus, it would be no surprise that your splitting algorithm is unfair
through a bottleneck, because the resulting flows can be considered
"independent" pure birth-death processes of their own right.

Mine, on the other hand, makes all service units for all non-optimal
destination wait behind the service units for the optimal destination.
This spitting removes the memoryless property of pure birth-death
processes (that the probability of arrival of one service unit does not
depend upon the arrival of another service unit).

Now, it is true that in the non-bottleneck case, this constraint does
not impede the other flows (because, whether you think of it a 1 server
that work N times as fast, or N servers instead of 1, non-optimal
destinations are not impeded so).

But, in the bottleneck case, non-optimal destinations only get traffic
after the entire bottleneck bandwidth has already been utilized by the
optimal destination, making it behave like one flow.

This choice of the best destination, the algorithm that you have ignored
for many years, has several other advantages, too, as demonstrated by
Lockheed Martin's 20ms destination failure recovery results.

I suggest you try it rather than blindly professing that it must behave
like your arbitrary selection.

--brian

On Tue, 19 Jul 2005, Janardhan Iyengar wrote:

> Brian,
> 
> I do not think I agree with you. Stock SCTP or TCP tries to send a window 
> of data over the time window of what should be one RTT. Given that, you 
> shouldn't really be sending more that one window of data to the receiver 
> in one RTT.
> 
> If you repeatedly did change_primary in SCTP, and kept sending to 
> different destination addresses, you are being aggressive (if the paths to 
> the destination addresses share a bottleneck). Which I think is close to 
> what you are doing.
> 
> 
> > If you want to get closer to my CMT algorithm, when you go to send,
> > check the send buffer availability on both TCP connections, chose the
> > one with the largest buffer space, and send to it until the buffer is
> > full.  Then do the comparison again, and send again until the next
> > connection's buffer is full, and so on.
> 
> If you assume a infinitely large file transfer (there is always data to 
> send), you will always be sending as much as both cwnds allow.
> 
> Effectively, your sending algorithm is too aggressive if the bottleneck 
> is shared.
> 
> 
> > You cannot model either stock SCTP or a persistent CMT algorithm as
> > multiple completely independent flows.  They are not independent at all.
> 
> I do not understand what you mean. For congestion control purposes, they 
> are independent. There is SACK information that is shared across the 
> paths, but I assume that is not what you are talking about.
> 
> 
> > The papers you cite cover independent concurrent TCP flows, with, I
> > assume, some determinate traffic splitting (round robin).  Try altering
> > the algorithm for selecting the TCP stream as detailed above.
> 
> What I do is, in fact, quite similar to what you describe. When the sender 
> is able to send, I pick a destination arbitrarily (this I think is where 
> we differ), and send to it until the cwnd is full. I then move on to the 
> next destination, and so on. If my application is a large file transfer, 
> then I am sending as much as the cwnds allow, to all destinations.
> 
> - jana

---

From: Janardhan Iyengar <[email-masked]>
Date: Wed, 20 Jul 2005 14:12:07 -0400 (EDT)

Brian,

> depend upon the arrival of another service unit).

I do not agree. If my splitting creates independent flows, so does yours. 
My sender sends until the cwnd of one (the first, any) path is full, then 
attempts the next. Your sender sends until the cwnd of the "best" path is 
full, then attempts the next. Further, yes, just like you, I have tried 
prioritized sending to destinations (in my case, in order of increasing 
lossrate) - no surprises; the results are the same as without prioritized 
sending.

Like I said in the previous email, if your sender has an infinite data 
source, you will send as much as both cwnds allow. Effectively, your 
sender will not be limited even if your sending to different destinations 
is prioritized. Your sender "waits" to send to a lower priority 
destination until the cwnd of the higher priority destination is not full. 
My sender does that too, except that the priority is not taken into 
account.

> like your arbitrary selection.

If your prioritized sending works as a panacea for all of your CMT 
concerns, so be it. I have tried prioritized sending based on lossrate. 
Assuming an infinite data source, it does not make a difference in the 
results. More specifically, and more relevant to this thread, the shared 
bottleneck issue does not disappear because the sender prioritizes 
sending. Just as I would expect.

And in my reality, the shared bottleneck concern still exists.

- jana

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Wed, 20 Jul 2005 14:31:11 -0600

Janardhan,

> concerns, so be it. I have tried prioritized sending based on lossrate. 

I would expect that prioritized based on lossrate would yield the
same results as arbitrary through a bottleneck because all destinations
through a bottleneck experience the same loss rate.

On the other hand, my prioritization is based on congestion window,
and by exhausting the bandwidth of one path first, exhibits the necessary
characteristic through a bottleneck.

Your concern comes from a failure to try.

--brian

-- 
Brian F. G. Bidulock    ¦ The reasonable man adapts himself to the ¦
[email-masked]    ¦ world; the unreasonable one persists in  ¦
http://www.openss7.org/ ¦ trying  to adapt the  world  to himself. ¦
                        ¦ Therefore  all  progress  depends on the ¦
                        ¦ unreasonable man. -- George Bernard Shaw ¦

---

From: Janardhan Iyengar <[email-masked]>
Date: Wed, 20 Jul 2005 22:26:23 -0400 (EDT)

Brian,

> characteristic through a bottleneck.

As I have mentioned to you earlier, if your prioritization indeed works, 
then you have just nailed the problem of end-to-end bottleneck detection 
using a window based sender in an EXTREMELY simple way. I do not think 
that is the case, and I therefore disagree with you.

Since I completely disagree with you on this issue, I am not going to 
invest time/energy trying out something that is a moot point as far as I 
am concerned.

If you are convinced that your idea works, fine.

Since this discussion is not really being productive (for me at least), 
and I think I'm just repeating myself, I do not wish to drag this thread 
any further.

- jana

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Wed, 20 Jul 2005 21:08:43 -0600

Janardhan,

I will leave you to investigating more complicated solutions, then.

--brian