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:
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.netReceived on Sat Dec 12 2009 - 19:02:11 ART
This archive was generated by hypermail 2.2.0 : Sat Jan 02 2010 - 11:11:08 ART