Re: [aqm] FQ-PIE kernel module implementation

["Rong Pan (ropan)" <[e-mail]>]

We can take the timestamp values to figure out latency and plug into PIE’s
basic control law. 

p = p + alpha*(est_del-target_del) + beta*(est_del-est_del_old);

We have tried this implementation before for comparison purpose. This
would react slowly than deriving latency for queue length because latency
value is only available when a packet leaves a queue. But it would remove
any inaccuracy in calculating the latency. For PIE, we go for rate
estimation as we think timestamping packets in hardware would be hard.
FQ_PIE is a different story. If someone affords to implement FQ, then
timestamping would not be too much of an overhead.

The other twist works as well. We will experiment and decide what we want
to do.
 

Drop_Queue_i = (Queue_lenth_i / Longest_Queue_length) * drop_prob

Thanks,

Rong


On 7/8/15, 1:06 AM, "Agarwal, Anil" <[e-mail]> wrote:

>Rong,
>
>Can you please elaborate on how packet timestamps would be used with
>FQ-PIE?
>It is not obvious.
>
>Is there a written description of FQ-PIE?  Does it describe use of
>timestamps as well?
>
>For equation -
>	Drop_Queue_i = (Queue_lenth_i / Longest_Queue_length) * drop_prob
>is there a fast algorithm for computing Longest_Queue_length for large
>number of queues?
>
>Thanks,
>Anil
>
>-----Original Message-----
>From: aqm [mailto:[e-mail]] On Behalf Of Rong Pan (ropan)
>Sent: Tuesday, July 07, 2015 7:00 PM
>To: Francini, Andrea (Andrea); Polina Goltsman; Fred Baker (fred); Toke
>Høiland-Jørgensen
>Cc: [e-mail]; Hironori Okano -X (hokano - AAP3
>INC at Cisco); AQM IETF list
>Subject: Re: [aqm] FQ-PIE kernel module implementation
>
>My bad, my memory has slipped. What you quote below is accurate..
>
>
>
>Rong
>
>
>
>On 7/7/15, 3:58 PM, "Francini, Andrea (Andrea)"
>
><[e-mail]> wrote:
>
>
>
>>Hi Rong,
>
>>
>
>>In the ns2 version of (then) SFQ-PIE described in the May 2014 CableLabs
>
>>document titled "ACTIVE QUEUE MANAGEMENT IN DOCSIS 3.X CABLE MODEMS", a
>
>>different formula than the one you gave below was used to compute the
>
>>drop probability of Queue i:
>
>>
>
>>Drop_Queue_i = (Queue_lenth_i / Longest_Queue_length) * drop_prob
>
>>
>
>>i.e., the length of the longest queue was used at the denominator instead
>
>>of the aggregate queue length (Total_Queue_Length).
>
>>
>
>>I am curious about the reason that required that particular algorithmic
>
>>change. 
>
>>
>
>>Thank you,
>
>>
>
>>Andrea
>
>>
>
>>
>
>>-----Original Message-----
>
>>From: aqm [mailto:[e-mail]] On Behalf Of Rong Pan (ropan)
>
>>Sent: Tuesday, July 07, 2015 6:33 PM
>
>>To: Polina Goltsman; Fred Baker (fred); Toke Høiland-Jørgensen
>
>>Cc: [e-mail]; Hironori Okano -X (hokano - AAP3
>
>>INC at Cisco); AQM IETF list
>
>>Subject: Re: [aqm] FQ-PIE kernel module implementation
>
>>
>
>>FQ_PIE still uses rate estimation so the aggregated queue length would
>
>>give us more precise estimation of the latency. Actually, on second
>
>>thought, if we are going to afford the complexity of FQ, then timestamp
>
>>packets become trivial. If we use time stamp in FQ_PIE, all these
>>concerns
>
>>would be gone. 
>
>>
>
>>Having said that, drop probability can be easily tuned according to each
>
>>queue¹s queue length:
>
>>Drop_Queue_i = Queue_lenth_i/Total_Queue_length*drop_prob. This has shown
>
>>to work. Hiro¹s previous implementation of FQ_PIE has it and it is
>
>>working. Unfortunately, in his new version of FQ_PIE, this somehow gets
>
>>lost. 
>
>>
>
>>He will update FQ_PIE accordingly. But I will vote for timestamp this
>>time
>
>>as FQ is a lot more complicated than time stamp. If one decides to use
>>FQ,
>
>>timestamp comes easy as well.
>
>>
>
>>Thanks,
>
>>
>
>>Rong
>
>>
>
>>
>
>>
>
>>
>
>>
>
>>On 7/3/15, 2:45 AM, "Polina Goltsman" <[e-mail]> wrote:
>
>>
>
>>>
>
>>>
>
>>>On 07/03/2015 01:30 AM, Fred Baker (fred) wrote:
>
>>>>> On Jul 2, 2015, at 4:21 PM, Toke Høiland-Jørgensen <[e-mail]>
>
>>>>>wrote:
>
>>>>>
>
>>>>> This is, as far as I can tell from your explanation, different than
>
>>>>>what
>
>>>>> fq_pie does.
>
>>>> OK, apologies for the misinformation.
>
>>>>
>
>>>> In any event, the matter is not fundamental to fair queuing.
>
>>>According to the code and Toke in FQ-Codel there are separate state
>
>>>variables for each queue,
>
>>>whereas in FQ-PIE there is a single instance of state (see line 72-75 in
>
>>>sch_fq_pie.c
>
>>>  
>>><https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_hironor
>>>iokano_fq-2Dpie_blob_master_sch-5Ffq-5Fpie.c&d=AwIGog&c=jcv3orpCsv7C4ly8
>>>-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq
>>>4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJJEBMToS4eye5KU&s=90jYjRUO0hcRiGb1Kd3owx
>>>wftY2Pd3WrK2Hs-sq619E&e= >).
>
>>>This is [should be] equivalent to a PIE queue
>
>>>which uses FQ instead of FIFO as a child queue.
>
>>>
>
>>>As I understand the FQ-Codel draft, it seems to be fundamental to
>
>>>FQ-Codel that each queue has separate state variables.
>
>>>So my question is: is it indeed fundamental ?
>
>>>
>
>>>P.S. comment on line sch_fq_pie.c  should probably be updated
>
>>
>
>>_______________________________________________
>
>>aqm mailing list
>
>>[e-mail]
>
>>https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman
>>_listinfo_aqm&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=Fy
>>vaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJ
>>JEBMToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=
>
>
>
>_______________________________________________
>aqm mailing list
>[e-mail]
>https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_
>listinfo_aqm&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=Fyva
>klKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJJEB
>MToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=