Subject: Re: [iccrg] Background on my talk in iccrg

From: Bob Briscoe <[email-masked]>
Date: Wed, 3 Apr 2019 11:48:02 +0100

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.

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?...

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.

(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. 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...

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 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. 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.

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
>>> [email-masked]
>>> https://www.irtf.org/mailman/listinfo/iccrg
>>
>> -- 
>> ________________________________________________________________
>> Bob Briscoehttp://bobbriscoe.net/
>
> -- 
> ________________________________________________________________
> Bob Briscoehttp://bobbriscoe.net/

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/

---

From: Peyman Teymoori <[email-masked]>
Date: Wed, 3 Apr 2019 13:44:09 +0200

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.

A true additive signal was what we were looking for.

> our future work." Surely this is a sender-only algorithm, so there is 
> no deployment challenge? However, there is a (minor) implementation 
Yes, and I agree that it's a sender-side change, which cannot be major! 
and it needs router configurations as well.

> congestion level once per RTT, I don't think implementation will 
> present too much of a performance hit.
That's right.
> 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.
> 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 
> TCP gets more and more complicated with all the possible combinations 
> of modes you have to allow for.
>
I haven't tried it either but, that's a good hint on how to make the 
calculation easier!
> -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].
> 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

>>> (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:

---

From: Peyman Teymoori <[email-masked]>
Date: Wed, 3 Apr 2019 13:51:16 +0200

On 4/3/2019 1:44 PM, Peyman Teymoori wrote:
> Yes, and I agree that it's a sender-side change, which cannot be 
> major! and it needs router configurations as well.
>
>> and Peter Key's tutorial "Distributed Control and Resource Pricing" 
>> at SIGCOMM 2000. They used it when modelling TCP's AIMD.
>>
> 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].
>>>> 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.
>>>>

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 3 Apr 2019 15:47:09 +0100

Peyman,

On 03/04/2019 12:51, Peyman Teymoori wrote:
>>> 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?...
>>>
>>> log implementation. I'm not sure what to do when there's 100% 
>>> marking to avoid calculating -log(0) = +infinity. 
>>> 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.
>>>
>>> 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 also cannot think of a good way to reason about what base should 
>>> be used for the log.
>>>
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

Bob

---

From: "De Vleeschauwer, Danny (Nokia - BE/Antwerp)" <[email-masked]>
Date: Wed, 3 Apr 2019 16:34:04 +0000

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 <[email-masked]> On Behalf Of Bob Briscoe
Sent: Wednesday, April 03, 2019 4:47 PM
To: [email-masked]
Subject: Re: [iccrg] Background on my talk in iccrg

Peyman,

Hi Bob,

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.

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.

Thanks again,

Bob

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.

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

Dear all,

Kind regards,

Peyman

iccrg mailing list

[email-masked]<mailto:[email-masked]>

--

--

--

iccrg mailing list

[email-masked]<mailto:[email-masked]>

iccrg mailing list

[email-masked]<mailto:[email-masked]>

--