Re: [iccrg] Background on my talk in iccrg

[Peyman Teymoori <[e-mail]>]

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