Re: Policing and CIR,PIR,BC,BE

Cool. Are those formulas documented anywhere?
Regards,

Joe Astorino - CCIE #24347 R&S
Technical Instructor - IPexpert, Inc.
Cell: +1.586.212.6107
Fax: +1.810.454.0130
Mailto: jastorino_at_ipexpert.com

-----Original Message-----
From: Petr Lapukhov <petr_at_internetworkexpert.com>
Date: Sat, 12 Dec 2009 22:18:40
To: <jastorino_at_ipexpert.com>
Cc: karim jamali<karim.jamali_at_gmail.com>; amr mahmoud<amr10_2_at_hotmail.com>; CCIE Groupstudy<ccielab_at_groupstudy.com>
Subject: Re: Policing and CIR,PIR,BC,BE

OK, here is the quick idea (sorry running out of time here)

1) In packet-based approach, every time a packet arrives, the router
needs to replentish the token bucket using the core computation
CIR*(t1-t0), which involves multiplication operation (more CPU
intensive than addition).

2) In scheduler based approach the token bucket is replentished in
background using a fixed rate timer. The replentish operation only
involves adding tokens, i.e. additions only (well plus some
comparsions which are quick).

3) Both approaches compare the incoming packet sizes with the
accumuated token bucket size. This operation involves comparsion and
subtraction.

Based on that, (2) approach (2) saves approximately
"PPS*number_of_CPU_cycles_to_do_multiplication" CPU cycles at high PPS
rate. More than that, with multiple policers, approach (1) needs to
perform multiplications for EVERY policer separately as packets arrive
asyncrhonously. Approach (2) could reuse the SAME scheduler to
replentish ALL token buckets at the same hardware interrupt run.

This is in short where the CPU savings come from.

HTH,

-- 
Petr Lapukhov, petr_at_INE.com
CCIE #16379 (R&S/Security/SP/Voice)
Internetwork Expert, Inc.
http://www.INE.com
Toll Free: 877-224-8987
Outside US: 775-826-4344
2009/12/12 Joe Astorino <jastorino_at_ipexpert.com>:
> Petr,
>
> Since the router chooses the number of tokens to add  based on the minimum between Bc or (time arrived - time of previous) * CIR I would think it still needs to calculate both to know which is smaller. Because it still needs to do both operations how does that help cpu utilization if it chooses the static bc value?
> Regards,
>
> Joe Astorino - CCIE #24347 R&S
> Technical Instructor - IPexpert, Inc.
> Cell: +1.586.212.6107
> Fax: +1.810.454.0130
> Mailto:  jastorino_at_ipexpert.com
>
> -----Original Message-----
> From: Petr Lapukhov <petr_at_internetworkexpert.com>
> Date: Sat, 12 Dec 2009 19:02:11
> To: karim jamali<karim.jamali_at_gmail.com>
> Cc: Joe Astorino<jastorino_at_ipexpert.com>; amr mahmoud<amr10_2_at_hotmail.com>; Cisco certification<ccielab_at_groupstudy.com>
> Subject: Re: Policing and CIR,PIR,BC,BE
>
> Karim,
>
> You correcly ouline the "packet-based" token bucket algorith
> formulation. Like I said, both implementations implement the token
> bucket metaphor. However, the "packet-based" approach is intuitively
> simpler and has unlimited precision. The "periodic scheduler"
> approach, however has bounded complexity and perfectly fits hardware
> based implementations. I would like to refer you to the following
> document:
>
> http://www.cisco.com/en/US/products/hw/switches/ps646/products_tech_note09186a00800feff5.shtml#parameters
>
> which precisely describes the "scheduler-based" approach implemented
> in the 3550 switches. By the way, even though it's never been clearly
> documented anywhere, I believe the legacy "rate-limit" command
> implement token-bucket metpahor using the "scheduler" approach.  You
> may also want to look at the following wiki post:
>
> http://en.wikipedia.org/wiki/Token_bucket
>
> which outlines the "scheduler-based" token-bucket formulation. And of
> course I covered all that stuff in our VOL1 QoS section (QoS is my
> favorite ;)
>
> HTH,
> --
> Petr Lapukhov, petr_at_INE.com
> CCIE #16379 (R&S/Security/SP/Voice)
>
> Internetwork Expert, Inc.
> http://www.INE.com
> Toll Free: 877-224-8987
> Outside US: 775-826-4344
>
>
> 2009/12/12 karim jamali <karim.jamali_at_gmail.com>:
>> Dear Gents,
>>
>> I would like to thank Petr & Joe for such a wonderful knowledge sharing. The
>> main point of discussion as I understand is how the token bucket is updated
>> with policing:
>>
>> 1)Scheduler Approach which Petr mentioned relies on adding a number of
>> packets every scheduling interval (without having to do anything with the
>> way packets arrive and inter-arrival time).
>>
>> 2)Packet based approach: which relies on the inter-arrival time of packets
>>
>>
>> Specifically, the token arrival rate is calculated as follows:
>>
>> (time between packets<which is equal to t-t1>* policer rate)/8 bits per byte
>>
>>
>>
>> Looking at the formulas that Joe used from Cisco's website:
>>
>> Tc(t) = min(CIR * (t-t1) + Tc(t1), Bc)
>> Tp(t) = min(PIR * (t-t1) + Tp(t1), Be)
>>
>> It seems that the either the Packet based approach or the Scheduler based
>> approach could be used (based on the minimum). We are comparing the number
>> of tokens currently in the bucke (at time t): addition of what we have put
>> CIR * (t-t1) as well as what was already in the bucket at time t1. We
>> compare this value to the Bc. This comparison will lead to using either
>> packet or scheduled mode.
>>
>> Please correct me if i am wrong in my understanding!
>>
>> Once again,Petr & Joe can't thank you enough!
>>
>> Best Regards,
>>
>> Karim
>>
>> On Sat, Dec 12, 2009 at 6:25 A
>> M, Joe Astorino <jastorino_at_ipexpert.com> wrote:
>>
>>> One last thing --
>>>
>>> With the single rate two-color policer (police <rate> command) there
>>> actually is no BE possible...you have conform and exceed.  Conform meaning
>>> you are within the bounds of the policed rate and exceed meaning you went
>>> over Bc, not Be...there is no excess burst with the single rate two-color
>>> policer.
>>>
>>> Apologies for any confusion, I've had to brush up on the very specifics of
>>> this technology.   One last summary
>>>
>>> police <rate> (with no violate action configured) <--- single rate two
>>> color policer.  This does not allow excess burst.  If you go over the Bc
>>> burst that is considered exceeding
>>>
>>> police <rate> (with violate action configured) <--- single rate three color
>>> policer.  This DOES allow excess burst and has 3 actions; conform, exceed,
>>> violate.  Exceed means you went over the rate but are still < Bc.  Violate
>>> means you went over the Be.  There are two buckets here, one for Bc and one
>>> for Be and they get filled everytime a packet hits the interface with the
>>> formula ((time of packet - time of previous packet) * CIR) / 8
>>>
>>> police cir <cir> <--- dual rate three color policer.  This actually polices
>>> at TWO separate rates, CIR and PIR and has 3 actions; conform, exceed,
>>> violate.  Exceed means you went over the configured normal burst (Bc) but
>>> are still less than the excessive burst (Be).  Violate means you went over
>>> the excessive burst (Be).  The difference is in how Bc and Be get filled
>>> here.  With PIR configured Bc still gets filled the same, but the 2nd token
>>> bucket (PIR) gets filled with Bc + Be tokens EVERY time
>>>
>>> police cir percent <--- similar to above but dealing with percentages.  You
>>> specify the CIR as a percent of the interface bw and you specify your bc and
>>> be in milliseconds.  The router figures out the actual Bc/Be values based on
>>> this.
>>>
>>> Again, sorry for such a long thread and going back and forth with myself
>>> hehe...just wanted to make sure everybody got the message clearly after I
>>> found some mistakes in my original posts.  Thank You!
>>>
>>>
>>> On Fri, Dec 11, 2009 at 7:31 PM, Joe Astorino <jastorino_at_ipexpert.com>wrote:
>>>
>>>> Another quick correction I wanted to make for everybody -- Contrary to
>>>> popular belief, the rate at which your token bucket or buckets refresh in
>>>> policing has nothing to do with a static value Tc like in shaping.  The
>>>> number of tokens that get put back into your bucket depends on a calculation
>>>> the router does based on the interval of packets arriving.  Every time a
>>>> packet arrives on the interface this gets checked and your tokens are added
>>>> as follows:
>>>>
>>>> Bc = ((Time of packet arriving - Time of previous packet arriving) * CIR)
>>>> / 8
>>>>
>>>> This essentially gives us a "pro-rated" amount of tokens being refreshed
>>>> which makes sense.  Imagine I am policing to 64Kbps.  I get a packet at T =
>>>> 1 second and another at T = 2 seconds.  At T = 1 second I get my CIR in
>>>> bytes placed into my bucket.  At T = 2 I will have another CIR in bytes
>>>> placed into my bucket...say I get another packet at T = 2.5 seconds...OK
>>>> well now I only get .5 seconds worth of tokens instead of a full seconds
>>>> worth.
>>>>
>>>>
>>>> On Fri, Dec 11, 2009 at 3:40 PM, Joe Astorino <jastorino_at_ipexpert.com>wrote:
>>>>
>>>>> Quick Edit:
>>>>>
>>>>>
>>>>> "If we are over the policed rate, but still within the max burst (Be in
>>>>> bytes) then we do something else based on the exceed action (usually drop or
>>>>> mark down)."
>>>>>
>>>>> What I meant to say was if we are over the max burst rate (Be) then we do
>>>>> something else entirely... So exceed with the single rate 2 color policer is
>>>>> "I went over Be".  Sorry.
>>>>>
>>>>>
>>>>> On Fri, Dec 11, 2009 at 3:33 PM, Joe Astorino <jastorino_at_ipexpert.com>wrote:
>>>>>
>>>>>> Hi!
>>>>>>
>>>>>> This is certainly one of the more confusing topics : )
>>>>>>
>>>>>> 1) The plain vanilla "police <bps>" command implements EITHER what we
>>>>>> call a single-rate two-color policer or a single rate three-color policer
>>>>>> depending on if you specify a violate action or not.  In other words, with
>>>>>> no violate action defined we police based on only ONE rate, which would be
>>>>>> what you specify in bps in the command, and we can do certain things -- if
>>>>>> we are within the rate we "conform" and do some action (usually transmit).
>>>>>> If we are over the policed rate, but still within the max burst (Be in
>>>>>> bytes) then we do something else based on the exceed action (usually drop or
>>>>>> mark down).  IF you choose to specify a violate action you are now
>>>>>> implementing a single-rate three-color policer.  This is essentially the
>>>>>> same thing but more granular.  Now you can say if I am within the policed
>>>>>> rate then I conform and do this thing...if I am over the rate but still less
>>>>>> than the Be that do something else (you went over the rate, but you are
>>>>>> still somewhere between the normal burst Bc and the max burst Be) and
>>>>>> finally if I am over the max burst do something else entirely.  So you have
>>>>>> three options instead of two, hence the three colors.
>>>>>>
>>>>>> 2) The command "police cir" gets more "interesting" : )  When you do
>>>>>> police cir you are implementing a DUAL-rate three-color policer.  This
>>>>>> introduces the whole concept of PIR.  You are actually policing based on TWO
>>>>>> entirely different rates, as you actually have two separate token buckets
>>>>>> involved, Tc and Tp and you have different actions for each bucket being
>>>>>> policed.  Essentially, you still have your three options (conform, exceed,
>>>>>> violate) but now exceed means "I went over the policed CIR rate but I am
>>>>>> still under the peak rate." The burst rate here would be related to the
>>>>>> first token bucket.  Every Tc time interval you get Bc tokens in the first
>>>>>> bucket to play with. So essentially exceed means that you went over your
>>>>>> allotted Bc tokens per Tc and you need to wait for Bc to refill if you want
>>>>>> to send at that rate.  The violate action here relates to the PIR and means
>>>>>> "I went over the policed CIR rate, AND I went over the PIR rate too...now
>>>>>> I'm screwed".  The PIR rate relates to the 2nd token bucket you are policing
>>>>>> which gets Bc + Be tokens every Tc interval.
>>>>>>
>>>>>> 3) Remember that with policing your Bc and Be are specified in terms of
>>>>>> BYTES usually.  Be careful.
>>>>>>
>>>>>> So in summary:
>>>>>>
>>>>>> police <bps>  -- single rate two color OR single rate three color
>>>>>> depending on options.  conform means within the bps rate.  Exceed means you
>>>>>> went over the Bc rate and Violate means you are over Bc + Be.
>>>>>> police <cir> -- dual rate three color policer. conform means within the
>>>>>> CIR rate. Exceed means you went over policed rate of the FIRST bucket (Be).
>>>>>> Violate means you are over the policed rate of the SECOND bucket (PIR)
>>>>>>
>>>>>> HTH!!!
>>>>>>
>>>>>>
>>>>>> On Fri, Dec 11, 2009 at 3:04 PM, karim jamali <karim.jamali_at_gmail.com>wrote:
>>>>>>
>>>>>>> Dear Amr,
>>>>>>>
>>>>>>> The link brings a good understanding of Policing:
>>>>>>>
>>>>>>> http://wiki.nil.com/QoS_Policing_in_Cisco_IOS
>>>>>>>
>>>>>>> Petr's Policing vs Shaping article on INE Blog:
>>>>>>>
>>>>>>>
>>>>>>> http://blog.internetworkexpert.com/2008/07/03/at-a-glance-the-difference-between-shaping-and-policing/
>>>>>>>
>>>>>>>
>>>>>>> I do believe in some sort or the other the values do correspond to each
>>>>>>> other (I mean shaping & policing values).
>>>>>>> The way it is explained is the token bucket; tokens are always added to
>>>>>>> the
>>>>>>> bucket in case of policing at the rate of the cir, when a packet comes,
>>>>>>> if
>>>>>>> enough tokens in the bucket exist to send the packet it is sent;
>>>>>>> otherwise
>>>>>>> it is discarded.
>>>>>>>
>>>>>>> Then the concept of PIR is introduced, it comes with some ISPs which
>>>>>>> will
>>>>>>> allow you to go above the CIR; filling the regular token bucket with
>>>>>>> the
>>>>>>> rate of CIR and an additional excess token bucket with the PIR rate. So
>>>>>>> now
>>>>>>> if a packet comes we will check if enough tokens (CIR+PIR) are
>>>>>>> available to
>>>>>>> send the packet otherwise it will be dropped. When both CIR & PIR are
>>>>>>> specified this is a dual token bucket where three actions can take
>>>>>>> place
>>>>>>> (Conform/Exceed/Violate).
>>>>>>>
>>>>>>> Police & Police cir as far as i believe do the same function. However
>>>>>>> police
>>>>>>> rate is used for control-plane policing(traffic destined to the control
>>>>>>> plane).
>>>>>>>
>>>>>>> Check this link for the difference between Police commands:
>>>>>>>
>>>>>>>
>>>>>>> http://www.cisco.com/en/US/docs/ios/12_3t/qos/command/reference/qos_o1gt.html#wp1090915
>>>>>>>
>>>>>>> Best Regards,
>>>>>>>
>>>>>>> --
>>>>>>> KJ
>>>>>>>
>>>>>>>
>>>>>>> Blogs and organic groups at http://www.ccie.net
>>>>>>>
>>>>>>>_______________________________________________________________________
>>>>>>> Subscription information may be found at:
>>>>>>> http://www.groupstudy.com/list/CCIELab.html
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Regards,
>>>>>>
>>>>>> Joe Astorino CCIE #24347 (R&S)
>>>>>> Sr. Technical Instructor - IPexpert
>>>>>> Mailto: jastorino_at_ipexpert.com
>>>>>> Telephone: +1.810.326.1444
>>>>>> Live Assistance, Please visit: www.ipexpert.com/chat
>>>>>> eFax: +1.810.454.0130
>>>>>>
>>>>>> IPexpert is a premier provider of Classroom and Self-Study Cisco CCNA
>>>>>> (R&S, Voice & Security), CCNP, CCVP, CCSP and CCIE (R&S, Voice, Security &
>>>>>> Service Provider) Certification Training with locations throughout the
>>>>>> United States, Europe and Australia. Be sure to check out our online
>>>>>> communities at www.ipexpert.com/communities and our public website at
>>>>>> www.ipexpert.com
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Regards,
>>>>>
>>>>> Joe Astorino CCIE #24347 (R&S)
>>>>> Sr. Technical Instructor - IPexpert
>>>>> Mailto: jastorino_at_ipexpert.com
>>>>> Telephone: +1.810.326.1444
>>>>> Live Assistance, Please visit: www.ipexpert.com/chat
>>>>> eFax: +1.810.454.0130
>>>>>
>>>>> IPexpert is a premier provider of Classroom and Self-Study Cisco CCNA
>>>>> (R&S, Voice & Security), CCNP, CCVP, CCSP and CCIE (R&S, Voice, Security &
>>>>> Service Provider) Certification Training with locations throughout the
>>>>> United States, Europe and Australia. Be sure to check out our online
>>>>> communities at www.ipexpert.com/communities and our public website at
>>>>> www.ipexpert.com
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> Regards,
>>>>
>>>> Joe Astorino CCIE #24347 (R&S)
>>>> Sr. Technical Instructor - IPexpert
>>>> Mailto: jastorino_at_ipexpert.com
>>>> Telephone: +1.810.326.1444
>>>> Live Assistance, Please visit: www.ipexpert.com/chat
>>>> eFax: +1.810.454.0130
>>>>
>>>> IPexpert is a premier provider of Classroom and Self-Study Cisco CCNA
>>>> (R&S, Voice & Security), CCNP, CCVP, CCSP and CCIE (R&S, Voice, Security &
>>>> Service Provider) Certification Training with locations throughout the
>>>> United States, Europe and Australia. Be sure to check out our online
>>>> communities at www.ipexpert.com/communities and our public website at
>>>> www.ipexpert.com
>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> Regards,
>>>
>>> Joe Astorino CCIE #24347 (R&S)
>>> Sr. Technical Instructor - IPexpert
>>> Mailto: jastorino_at_ipexpert.com
>>> Telephone: +1.810.326.1444
>>> Live Assistance, Please visit: www.ipexpert.com/chat
>>> eFax: +1.810.454.0130
>>>
>>> IPexpert is a premier provider of Classroom and Self-Study Cisco CCNA (R&S,
>>> Voice & Security), CCNP, CCVP, CCSP and CCIE (R&S, Voice, Security & Service
>>> Provider) Certification Training with locations throughout the United
>>> States, Europe and Australia. Be sure to check out our online communities at
>>> www.ipexpert.com/communities and our public website at www.ipexpert.com
>>>
>>>
>>>
>>
>>
>> --
>> KJ
>>
>>
>> Blogs and organic groups at http://www.ccie.net
>>
>>_______________________________________________________________________
>> Subscription information may be found at:
>> http://www.groupstudy.com/list/CCIELab.html
Blogs and organic groups at http://www.ccie.net