Re: [aqm] FQ-PIE kernel module implementation

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

Yes, if we use timestamp, then we can have separate PIE per queue.

Rong

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

>Rong,
>
>Since the timestamp discussion came up in the context of FQ-PIE, it is
>not clear how we would use timestamp-based delay values measured across
>many queues to perform the computation of p. The delays experienced in
>different queues can have vastly different values.
>FQ-PIE has a single instance of PIE across all queues and a single value
>of p. How do you compute est_del from the various delay values from
>multiple queues?
>Or are you thinking of using a separate PIE instance per queue?
>Can you please elaborate?
>
>Thanks,
>Anil
>
>-----Original Message-----
>From: Rong Pan (ropan) [mailto:[e-mail]]
>Sent: Wednesday, July 08, 2015 2:17 PM
>To: Agarwal, Anil; 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
>
>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_hiro
>>>>nor
>>>>iokano_fq-2Dpie_blob_master_sch-5Ffq-5Fpie.c&d=AwIGog&c=jcv3orpCsv7C4
>>>>ly8 
>>>>-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1
>>>>Jvq 
>>>>4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJJEBMToS4eye5KU&s=90jYjRUO0hcRiGb1Kd3
>>>>owx
>>>>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_mail
>>>man 
>>>_listinfo_aqm&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r
>>>=Fy 
>>>vaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkr
>>>eFJ JEBMToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=
>>
>>
>>
>>_______________________________________________
>>aqm mailing list
>>[e-mail]
>>https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailm
>>an_ 
>>listinfo_aqm&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=F
>>yva 
>>klKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJ
>>JEB MToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=
>