Re: [iccrg] Background on my talk in iccrg

Hi all,
Two thoughts inline ...
Kind regards,
Danny

--
Danny De Vleeschauwer
Senior research engineer
Nokia Bell Labs
mob: +32 497 397548

Fortis 220-0002334-42
VAT BE 0404 621 642 Register of Legal Entities Antwerp

Disclaimer: This message (including any attachments) contains confidential information intended for a specific individual and purpose, and is protected by law.  If you are not the intended recipient, you should delete this message.  Any disclosure, copying, or distribution of this message, or the taking of any action based on it, is strictly prohibited without the prior consent of its author.

From: iccrg <iccrg-bounces@irtf.org> On Behalf Of Bob Briscoe
Sent: Wednesday, April 03, 2019 4:47 PM
To: iccrg@irtf.org
Subject: Re: [iccrg] Background on my talk in iccrg

Peyman,
On 03/04/2019 12:51, Peyman Teymoori wrote:

On 4/3/2019 1:44 PM, Peyman Teymoori wrote:

Hi Bob,

Thanks a lot for the comments!
On 4/3/2019 12:48 PM, Bob Briscoe wrote:
Peyman,

1/ I realize now that I incorrectly appeared to be dismissing your work in my email and my comment at the mic. I apologize.
Your -log(1-p) formulation does indeed have the correct additive property. Thank you for this.

A true additive signal was what we were looking for.

2/ Implementation
You say "...we will consider deployment challenges more thoroughly in our future work." Surely this is a sender-only algorithm, so there is no deployment challenge? However, there is a (minor)  implementation challenge. Perhaps that's what you meant?...

Yes, and I agree that it's a sender-side change, which cannot be major! and it needs router configurations as well.
2a/ With the current DCTCP approach of updating an EWMA of the congestion level once per RTT, I don't think implementation will present too much of a performance hit.
That's right.

(1-p) could be calculated by maintaining counters of the number of unmarked bytes and total bytes, then every RTT using an efficient integer division, such as do_div() in Linux, then using an efficient log implementation. I'm not sure what to do when there's 100% marking to avoid calculating -log(0) = +infinity.
In simulations, I just checked if 1-p = 1 before calculating log, and since p is the result of EWMA, there were very rare cases of having p = 1.

Aside from that issue, I don't think this calculation would harm performance too much, although I would prefer not to have a regular spike of processing time...
Right.

2b/ We liked p/(1-p) because it lends itself to a simple iterative calculation on every ACK or NACK. That's because there are (1-p)*cwnd ACKs per round trip and p*cwnd NACKs per round trip. So an increase can be applied on each ACK and a decrease on each NACK.

This insight was not our idea - I first saw it in Richard Gibbens's and Peter Key's tutorial "Distributed Control and Resource Pricing" at SIGCOMM 2000. They used it when modelling TCP's AIMD.

I much prefer iterative algorithms, cos they are stateless. Otherwise TCP gets more and more complicated with all the possible combinations of modes you have to allow for.

I can't think of a way to iteratively calculate -log(1-p). I've only tried for a few minutes, but I can't really fathom where to even start.
I haven't tried it either but, that's a good hint on how to make the calculation easier!

I also cannot think of a good way to reason about what base should be used for the log.
-log(1-p) and p/(1-p) have similar shapes, so maybe the latter would be a suitable approximation for the former anyway.
I plotted this for some different values of the log base. It seems like 1.5 as the base produces closer values to 1/(1-p) for p \in [0.4,0.8].
Fixing 1/(1-p) to p/(1-p): if base=2, they are close for p \in [0, 0.55].
Also the slopes have a similar form, and they're equal at p=0:

d (-log_b(1-p) ) =      1
dp                 ln(b)*(1-p)

d (p/(1-p)) =   1
dp            (1-p)2

[ddv>] -ln(1-p) = ln(1/(1-p)) = ln(1+p/(1-p)) =  p/(1-p) - (p/(1-p))^2/2 + ...
The last equality stems from ln(1+x) = x-x^2/2+x^3/3-x^4/4
BTW, since ln(1+x) <= x (just inspect the graph of both) for all x>-1, -ln(1-p) is always an underestimation. Therefore another base than e may be considered, but barring that, to match both for small p, the most logical selection for the base is e.

[ddv>] On the other hand, how "additive" is p/(1-p)?
Say that there are N congestion points each marking with their own p_n and marking in one point is statistically independent from all others. The total marking probability is then p = 1 - \prod_{n=1}^N (1-p_n) (which yields additivity for -log(1-p) for log of any base).
Define a_n=p_n/(1-p_n). It follows that 1-p_n = 1/(1+a_n). Notice that a_n is usually small(ish).
Then p/(1-p) = (1 - \prod_{n=1}^N (1-p_n))/(\prod_{n=1}^N (1-p_n)) = \prod_{n=1}^N (1+a_n) - 1
The leading term in this is \sum_{n=1}^N a_n, which is the (desired?) additivity.
The first correction term is \sum_{n=1}^N \sum_{m=n+1 }^N (a_n*a_m) and higher order terms of products of more than two a_n exist. However, the correction are small if the a_n are.

Bob

Normally I criticize others for developing solutions without any theoretical backing just because they are easy to implement. Now I'm guilty of it myself. I'm much happier now we can start from your theoretical ideal, then approximate it for ease of implementation.

... and I am very happy that you liked the idea!
Kind regards,
Peyman

Thanks again,

Bob
On 28/03/2019 16:56, Bob Briscoe wrote:
Addendum...
On 28/03/2019 17:03, Bob Briscoe wrote:
Peyman,

The approx additive property of combinatorial probability at low marking probability is only one way to get the additive network utility maximization property of the network.

Alternatively, you can transform the signal into the number space between [0,1] by using p/(1-p) which you can do in the end-system by measuring your congestion level as the distance between ECN marks, rather than the the probability of marking.

This is explained in the Unsaturated Marking section of this tech report:
http://bobbriscoe.net/projects/latency/ccdi_tr.pdf#subsection.3.1

We presented some of the highlights of this paper in ICCRG in the past, but I think we had to skip this section, due to lack of time (at least I cannot find the slides we originally prepared in the copy in the IETF proceedings, but I thought we had presented it at some time).
[BB] I just found it:
http://bobbriscoe.net/presents/1703ietf/1703L4S_DualQ_TCP_Prague-iccrg.pdf

Bob

Bob
On 21/03/2019 13:18, Peyman Teymoori wrote:

Dear all,

I would like to share the report (preprint) we have been working on with you before the meeting in Prague since my presentation will be about it. This is actually a research work, and we will consider deployment challenges more thoroughly in our future work.

Kind regards,

Peyman

_______________________________________________

iccrg mailing list

iccrg@irtf.org<mailto:iccrg@irtf.org>

https://www.irtf.org/mailman/listinfo/iccrg

--

________________________________________________________________

Bob Briscoe                               http://bobbriscoe.net/

--

________________________________________________________________

Bob Briscoe                               http://bobbriscoe.net/

--

________________________________________________________________

Bob Briscoe                               http://bobbriscoe.net/

_______________________________________________

iccrg mailing list

iccrg@irtf.org<mailto:iccrg@irtf.org>

https://www.irtf.org/mailman/listinfo/iccrg

_______________________________________________

iccrg mailing list

iccrg@irtf.org<mailto:iccrg@irtf.org>

https://www.irtf.org/mailman/listinfo/iccrg

--

________________________________________________________________

Bob Briscoe                               http://bobbriscoe.net/