Re: [iccrg] Background on my talk in iccrg

[Bob Briscoe <[e-mail]>]

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

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