令牌桶演算法

⑴ 令牌桶演算法的令牌桶工作參數

工作過程包括3個階段：產生令牌、消耗令牌和判斷數據包是否通過。其中涉及到2個參數：令牌產生的速率CIR（Committed Information Rate）/EIR（Excess Information Rate）和令牌桶的大小CBS（Committed Burst Size）/EBS（Excess Burst Size）。下面用圖形簡要概括一下這3個階段與2個參數的關系。
產生令牌：周期性的以速率CIR/EIR向令牌桶中增加令牌，桶中的令牌不斷增多。如果桶中令牌數已到達CBS/EBS，則丟棄多餘令牌。 消耗令牌：輸入數據包會消耗桶中的令牌。在網路傳輸中，數據包的大小通常不一致。大的數據包相較於小的數據包消耗的令牌要多。 判斷是否通過：輸入數據包經過令牌桶後的結果包括輸出的數據包和丟棄的數據包。當桶中的令牌數量可以滿足數據包對令牌的需求，則將數據包輸出，否則將其丟棄。

⑵ 什麼是漏桶演算法和令牌桶演算法

什麼是令牌桶
在我們討論突發數據量之前，我們首先要理解令牌桶的概念。令牌桶本身沒有丟棄
和優先順序策略，
令牌桶是這樣工作的：
1． 令牌以一定的速率放入桶中。
2． 每個令牌允許源發送一定數量的比特。
3． 發送一個包，流量調節器就要從桶中刪除與包大小相等的令牌數。
4． 如果沒有足夠的令牌發送包，這個包就會等待直到有足夠的令牌（在整形
器的情況下）或者包被丟棄，也有可能被標記更低的DSCP（在策略者的情況下）。
5． 桶有特定的容量，如果桶已經滿了，新加入的令牌就會被丟棄。因此，在
任何時候，源發送到網路上的最大突發數據量與桶的大小成比例。令牌桶允許突發，
但是不能超過限制。
Cisco IOS 流量策略（Traffic Policers）
IOS支持兩種流量策略：
1． 傳統的Cisco流量策略：CAR承諾接入速率，使用命令
Router(config-if)#rate-limit {input | output} CIR (bps)
Bc（burst-normal） Be(burst-max) conform-action action exceed-action action
2． 新型的Cisco流量策略：基於類的策略（Class-based policer），使用模
塊化Qos CLI（MQC）語法。可以使用MQC命令建立流量策略並把策略應用到介面。
一個流量策略包括一個流量類（traffic class）和一個或多個Qos特性。Policy
命令用來執行流量策略特性，它指定了一個流量類所需要的最大速率，超過這個速
率Qos系統會立刻執行一個操作，標準的操作是丟棄或重置包頭的DSCP欄位。Policy
命令的語法是：
police cir<bps> Bc<bc> Be<be> conform<conform-action> exceed
<exceed-action> violate<violate-action>
理解Bc和Be
對於超額的數據包，流量策略並不會把它們緩存稍候轉發，只有整形器（shaper）
會這樣做。流量策略只執行一個發送或不發送的策略。因為不能緩存數據包，所以
在發生擁塞時，所能做的最好的方法就是通過配置適當的超額突發數據量Be來不那
么過分的丟棄數據包。這一點對理解流量策略使用Bc和Be來保證達到CIR是非常
重要的。
超額參數模仿路由器的通用緩存規則。The rule recommends configuring buffering
equal to the round-trip time bitrate to accommodate the outstanding TCP
windows of all connections in times of congestion.
突發參數 目的 推薦公式
普通突發 · 執行標準的令牌桶 · 設置最大數量的令牌(盡管如
果Be>Bc的話可以借到令牌). · 決定令牌桶有多大，因為如果桶已經滿了那麼令
牌將被丟棄而不會再加入到桶中。 CIR [bps] * (1 byte)/(8 bits) * 1.5
seconds Note: 1.5 seconds is the typical round trip time.
超額突發 · 為令牌桶提供超額突發能力 · 如果Bc = Be那麼不
支持超額突發 · 當Bc = Be，流量調節器就不能借令牌，當令牌不夠時只能丟棄數
據包 兩倍的Bc
對TCP流量的測試表明，Bc 和Be的數值應該近似等於配置的平均速率在兩秒鍾內
的流量。如果你想限制流量在1Mb，應該把Bc 設置在1-2Mb，Be在2-4Mb。
舉個例子，如果我們想把輸出速率限制在1.5Mbps，我們可以做一下步驟：
1． 把承諾速率從比特轉換成位元組，因為突發數據量的單位為位元組。
1500000 bits / 8 bits = 187500 bytes
2． 使用標準的1.5秒往返時間（round-trip time）計算Bc
187500 bytes * 1.5秒 = 281250 bytes
3． 兩倍的Bc為Be
281250 bytes * 2 = 562500 bytes
使用命令
rate-limit input 1500000 281250 562500 conform-action {action}
exceed-action {action}
超額突發數據量
當數據包到達時可用的令牌數目小於包的大小，就可以使用超額突發數據量。包會
請求借用令牌。可以通過配置大於Bc的Be的數值來為令牌桶提供超額突發能力。
可以通過下面兩個例子來理解Be。
第一個例子說明怎樣配置CAR策略來允許所有的IP流量。管理員在T3線路上提供
了便宜的20Mbps的子速率服務。用戶只花費子速率帶寬的金額，也可以按需要增加
帶寬。CAR限制了用戶可用的流量速率，用戶只能使用規定的速率加上承諾的突發
數據量。可以適當的設置Be=32000。
interface hssi 0/0/0
rate-limit output 20000000 24000 32000 conform-action transmit
exceed-action drop
下一個例子，用戶只能發送24000位元組的突發數據量，所有超過限制的數據包都要
被丟棄，因為設置Bc=Be，數據包流不能通過超額突發能力來借用令牌。
interface Hssi0/0/0
rate-limit output 20000000 24000 24000 conform-action transmit
exceed-action drop
正確設置突發數據量的重要性
策略以位元組為單位指定了突發數據量，基於類的策略（class-based policer）支持
最小的突發數據量為1000位元組，包括第二層包頭。
突發數據量的目的是逐漸的丟棄數據包，就像RED那樣，並且避免尾丟棄。設置足
夠高的突發數據量對保證良好的吞吐量是非常重要的。
設置突發數據量時，考慮一下內容：
1． 如果突發數據量設置的過低，數據到達的速率將遠遠低於配置的速率。
2． 懲罰暫時突發對TCP流的吞吐量來說是相當不利的，具體情況請察看RFC
2001 and Random Early Detection (RED) gateways for Congestion Avoidance。
設置突發數據量來允許路由器容納暫時突發。
3． 對離開介面的數據包的處理基於包的大小和桶中剩餘的令牌數。
4． 在基於類的策略中，流量測量器不論介面是否擁塞都是激活的。每個包都
會經過令牌桶測量系統來決定是否符合配置的參數。
5． 如果數據突發量非常大而且非常突然，那麼配置較高的超額突發數據量可
以保證超額令牌桶中存放較多的令牌。而且可以調整介面的MTU等於或大於突發數
據量大小。
允許的突發數據量數值
最初，包括IOS12.0，rate-limit命令支持承諾和超額的突發數據量的范圍是：
Router1(config-if)#rate-limit input 18000000 ?
<8000-2000000> Normal burst bytes
Router1(config-if)#rate-limit input 18000000 2000000 ?
<8000-8000000> Maximum burst bytes
Router1(config-if)#rate-limit input 18000000 2000000
IOS12.1增加了突發數據量的最大值：
7500-107(config)#interface atm 1/0/0
7500-107(config-if)#rate-limit output ?
<8000-2000000000> Bits per second
access-group Match access list
qos-group Match qos-group ID<b

⑶ 令牌桶演算法的分類

基於令牌桶的典型標記器有多種演算法實現方案，基本演算法主要有IN/OUT公平標記器（FM）和三色標記器（TCM），擴展的演算法主要有單速率三色標記器（srTCM）和雙速率三色標記器（trTCM）。其中單速率標記器和雙速率標記器已分別稱為IETF的標准建議。
IN/OUT 公平標記器（FM）
FM是一種雙色單令牌桶標記器，它的Tspec是系統的分組平均速錄為R，允許的突發度為B，工作原理就是當IP分組到達時若桶中有足夠的令牌，則將符合Tspec的分組標記為IN；若此時沒有足夠的令牌，則認為該到達分組不符合Tpsec，不符合Tpsec的分組將被標記為OUT，網路將可能對這些被標記為不同屬性的分組依據相應的策略進行不同的處理。
單速率三色標記器（srTCM）
srTCM是一種三色雙令牌桶標記器，它的Tpsec有三個參數：承諾信息速率，承諾突發尺寸和超額突發尺寸。CIR的單位是bps，CBS及EBS的單位是Byte。
srTCM由兩個令牌桶C和E組成，它們的CIR相同，容量則分別為CBS和EBS，C桶內存放黃色令牌，開始時令牌桶C與E都是滿的。進入的分組沒有超過CBS就標記為綠色；超過了CBS而沒有超過EBS就標記為黃色；否則標記為紅色。在DiffServ中，紅、黃、綠可映射為不同的DSCP值。
雙速率標記器（trTCM）
trTCM也是一種三色雙令牌桶標記器，它的Tpsec有4個參數：峰值信息速率（PIR）、峰值突發尺寸（PBS）、承諾信息速率（CIR）和承諾突發尺寸（CBS）。PIR和CIR的單位是bps，PBS和CBS的單位是Byte。

⑷ 流量整形的流量整形的核心演算法

流量整形的核心演算法有以下兩種，具體採用的技術為GTS（Generic Traffic Shaping），通用流量整形： 漏桶演算法（Leaky Bucket）
漏桶演算法是網路世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經常使用的一種演算法，它的主要目的是控制數據注入到網路的速率，平滑網路上的突發流量。漏桶演算法提供了一種機制，通過它，突發流量可以被整形以便為網路提供一個穩定的流量。 令牌桶演算法（Token Bucket）
有時人們將漏桶演算法與令牌桶演算法錯誤地混淆在一起。而實際上，這兩種演算法具有截然不同的特性並且為截然不同的目的而使用。它們之間最主要的差別在於：漏桶演算法能夠強行限制數據的傳輸速率，而令牌桶演算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。
在某些情況下，漏桶演算法不能夠有效地使用網路資源。因為漏桶的漏出速率是固定的參數，所以即使網路中不存在資源沖突（沒有發生擁塞），漏桶演算法也不能使某一個單獨的流突發到埠速率。因此，漏桶演算法對於存在突發特性的流量來說缺乏效率。而令牌桶演算法則能夠滿足這些具有突發特性的流量。通常，漏桶演算法與令牌桶演算法可以結合起來為網路流量提供更大的控制。

⑸ 計算機操作系統中的漏桶，令牌桶演算法

我也不明白

⑹ VoIP的基本原理

VoIP的基本原理是通過語音的壓縮演算法對語音數據編碼進行壓縮處理，然後把這些語音數據按 TCP/IP 標准進行打包，經過 IP 網路把數據包送至接收地，再把這些語音數據包串起來，經過解壓處理後，恢復成原來的語音信號，從而達到由互聯網傳送語音的目的。 IP 電話的核心與關鍵設備是 IP 網關，它把各地區電話區號映射為相應的地區網關 IP 地址。這些信息存放在一個資料庫中，數據接續處理軟體將完成呼叫處理、數字語音打包、路由管理等功能。 在用戶撥打長途電話時，網關根據電話區號資料庫資料，確定相應網關的 IP 地址，並將此 IP 地址加入 IP 數據包中，同時選擇最佳路由，以減少傳輸延時， IP 數據包經 Internet 到達目的地的網關。在一些 Internet 尚未延伸到或暫時未設立網關的地區，可設置路由，由最近的網關通過長途電話網轉接，實現通信業務。

VoIP是一種以IP電話為主，並推出相應的增值業務的技術。

VoIP主要有以下三種方式：
網路電話：完全基於Internet傳輸實現的語音通話方式，一般是PC和PC之間進行通話[1] 。
與公眾電話網互聯的IP電話：通過寬頻或專用的IP網路，實現語音傳輸。終端可以是PC或者專用的IP話機[1] 。
傳統電信運營商的VoIP業務：通過電信運營商的骨幹IP網路傳輸語音。提供的業務仍然是傳統的電話業務，使用傳統的話機終端。通過使用IP電話卡，或者在撥打的電話號碼之前加上IP撥號前綴，這就使用了電信運營商提供的VoIP業務[1] 。
VoIP相對比較便宜。這是因為VoIP電話不過是互聯網上的一種應用。從本質上說，VoIP電話與電子郵件，即時訊息或者網頁沒有什麼不同，它們均能在經過了互聯網連接的機器間進行傳輸。這些機器可以是電腦，或者無線設備，比如手機或者掌上設備等等。

⑺ 漏桶演算法的漏桶演算法和令牌桶演算法的區別

漏桶演算法與令牌桶演算法在表面看起來類似，很容易將兩者混淆。但事實上，這兩者具有截然不同的特性，且為不同的目的而使用。漏桶演算法與令牌桶演算法的區別在於：
l 漏桶演算法能夠強行限制數據的傳輸速率。
l 令牌桶演算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。
需要說明的是：在某些情況下，漏桶演算法不能夠有效地使用網路資源。因為漏桶的漏出速率是固定的，所以即使網路中沒有發生擁塞，漏桶演算法也不能使某一個單獨的數據流達到埠速率。因此，漏桶演算法對於存在突發特性的流量來說缺乏效率。而令牌桶演算法則能夠滿足這些具有突發特性的流量。通常，漏桶演算法與令牌桶演算法結合起來為網路流量提供更高效的控制。

⑻ 令牌桶演算法的簡介

在網路中傳輸數據時，為了防止網路擁塞，需限制流出網路的流量，使流量以比較均勻的速度向外發送。令牌桶演算法就實現了這個功能，可控制發送到網路上數據的數目，並允許突發數據的發送。
令牌桶演算法是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種演算法。典型情況下，令牌桶演算法用來控制發送到網路上的數據的數目，並允許突發數據的發送。
大小固定的令牌桶可自行以恆定的速率源源不斷地產生令牌。如果令牌不被消耗，或者被消耗的速度小於產生的速度，令牌就會不斷地增多，直到把桶填滿。後面再產生的令牌就會從桶中溢出。最後桶中可以保存的最大令牌數永遠不會超過桶的大小。
傳送到令牌桶的數據包需要消耗令牌。不同大小的數據包，消耗的令牌數量不一樣。
令牌桶這種控制機制基於令牌桶中是否存在令牌來指示什麼時候可以發送流量。令牌桶中的每一個令牌都代表一個位元組。如果令牌桶中存在令牌，則允許發送流量；而如果令牌桶中不存在令牌，則不允許發送流量。因此，如果突發門限被合理地配置並且令牌桶中有足夠的令牌，那麼流量就可以以峰值速率發送。
令牌桶演算法的基本過程如下：
假如用戶配置的平均發送速率為r，則每隔1/r秒一個令牌被加入到桶中；
假設桶最多可以存發b個令牌。如果令牌到達時令牌桶已經滿了，那麼這個令牌會被丟棄；
當一個n個位元組的數據包到達時，就從令牌桶中刪除n個令牌，並且數據包被發送到網路；
如果令牌桶中少於n個令牌，那麼不會刪除令牌，並且認為這個數據包在流量限制之外；
演算法允許最長b個位元組的突發，但從長期運行結果看，數據包的速率被限製成常量r。對於在流量限制外的數據包可以以不同的方式處理：
它們可以被丟棄；
它們可以排放在隊列中以便當令牌桶中累積了足夠多的令牌時再傳輸；
它們可以繼續發送，但需要做特殊標記，網路過載的時候將這些特殊標記的包丟棄。
注意：令牌桶演算法不能與另外一種常見演算法「漏桶演算法（Leaky Bucket）」相混淆。這兩種演算法的主要區別在於「漏桶演算法」能夠強行限制數據的傳輸速率，而「令牌桶演算法」在能夠限制數據的平均傳輸速率外，還允許某種程度的突發傳輸。在「令牌桶演算法」中，只要令牌桶中存在令牌，那麼就允許突發地傳輸數據直到達到用戶配置的門限，因此它適合於具有突發特性的流量。

⑼ 誰能·幫我解釋一下Qos 的cir bc be之間的關系啊

BC：承諾突發量，即一次性加進的令牌數量 TC：向令牌桶中添加的令牌的時間周期，默認125ms，即1s要向令牌中放8次令牌。 CIR：承諾信息速率。即每秒鍾往桶里加的令牌的速率，這個速率也就決定了用戶流量，這是一個平均量，可由公式：CIR=BC/TC得出。 令牌桶演算法的三種模式： 1.單速雙色 在單速雙色的令牌桶演算法中，只存在一個令牌桶，並且流量只會出現兩種結果，即符合CIR（conform）和超出CIR（exceed）。在一秒鍾結束後，沒有用完的令牌會被全部清空，由下一秒重新加入。 因此無論上一秒鍾是否傳過數據，這一秒都可以保持CIR，並且如果每秒流量超過了CIR後，超過的流量都會採取已經設定的動作。 2.單速三色 在單速三色的令牌桶演算法中，使用兩個令牌桶，用戶每秒的可用帶寬，總是兩個桶的令牌之和。第一個桶的機制和單速雙色演算法沒有區別。第二個桶的令牌卻不是直接加入，只有當一秒鍾結束後，第一個桶中存在剩餘令牌時，這些剩餘令牌就可以從第一個桶中被轉移到第二僅供學習參考，請勿用於商業活動~ 2 個桶中。最大數量被稱為 Excess Burst size（Be），Be是不可能超過CIR的，因為第一個桶每秒的所有令牌就是CIR，即使所有令牌全部被移到第二個桶，Be最多也只能等於CIR。註：Be和Bc卻毫無關系。在每一秒結束時，若用戶沒有將第二個桶的令牌用完，那麼第二個桶的令牌也是要全部清除的，第二個桶中的令牌，都來自於上一秒第一個桶沒用完的令牌。 缺點：要使用戶在某一秒的速度能夠達到CIR+Be，唯一的辦法是用戶在上一秒鍾以低於CIR的速度傳輸。因此，用戶不可能每一秒都以CIR+Be的速度傳輸。 3. 雙速三色 雙速三色的令牌桶演算法，同樣使用兩個令牌桶，然而這兩個桶是相互獨立的，並不會將第一個桶未用的令牌放入第二個桶。第一個桶與以往的演算法相同，而第二個桶可以直接設置為CIR+Be之和，稱為PIR。當用戶的數據通過介面時，總是先檢查第二個桶的PIR，如果超出則採取動作，如果未超出，再檢查是是否符合第一個桶的CIR，如果超出CIR，則採取第二個桶的策略傳輸，如果未超過，則正正常傳輸。 由於直接設置兩個速率，因此用戶可以直接以CIR+Be之和的速率進行傳輸。 這是某大神做的總結。