Re: [iccrg] Background on my talk in iccrg

[Bob Briscoe <[e-mail]>]

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




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

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