Re: [iccrg] Background on my talk in iccrg

[Peyman Teymoori <[e-mail]>]

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].
>> 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/
>
> _______________________________________________
> iccrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/iccrg