轉貼 流量控制系列手冊頁：tc-cbq

簡介
CBQ實現了一個豐富的共享連接的類別層次，既有固定(shaping)頻寬的能力，也具有頻寬優先級管理的能力。頻寬固定是通過計算連接的空閒時間完成的。空閒時間的計算標準是資料包離隊事件發生的頻率和下層連接(資料鏈路層)的頻寬。

By nixe0n

CBQ
原文最近更新時間：2001年12月16日
來源http://lartc.org/

名字
　　CBQ - 基於類別排隊(Class Based Queueing)
摘要
tc qdisc ... dev dev (parent classid | root) [ handle major: ] cbq [ allot bytes] avpkt bytes bandwidth rate [ cell bytes] [ ewmalog ] [ mpu bytes ]
tc class ... dev dev parent major:[minor] [ classid major:minor] cbq allot bytes [ bandwidth rate ] [ rate rate] prio priority [ weight weight] [ minburst packets] [ maxburst packets ] [ ewma log] [ cell bytes] avpkt bytes[ mpu bytes] [ bounded isolated ] [ split handle& defmapdefmap ] [ estimator interval timeconstant]

簡介
CBQ實現了一個豐富的共享連接的類別層次，既有固定(shaping)頻寬的能力，也具有頻寬優先級管理的能力。頻寬固定是通過計算連接的空閒時間完成的。空閒時間的計算標準是資料包離隊事件發生的頻率和下層連接(資料鏈路層)的頻寬。

頻寬固定算法
當把一條10mbit/s的連接限制為1mbit/s時，這條連接將有90%的時間是空閒的。如果不是，它就會調低頻寬以滿足90%空閒時間的限制。
在操作過程中，空閒時間還要進行指數平滑移動平均(exponential weighted moving average,EWMA)計算，在這種計算方法中最近經過的資料包權重是前面資料包權重的指數。UNIX系統的平均負載就是使用這種算法計算的。

最後，由EWMA計算的值減去空閒時間，所得結果叫做avgidle。最好的情況是avgidle等於0，也就是資料包是嚴格地按照計算的時間間隔到達。

而過載連接的avgidle值是負數，如果這個負數太大，CBQ就會調低頻寬，這就造成了過度限制(overlimit)的情況。

相反，一個空閒的連接會積累下一個很大的正數avgidle，這樣可能造成經過一段空閒後，使頻寬失控。為了防止出現這種情況的出現，可以使用maxidle參數限制avgidle的值。

如果處於過度限制(overlimit)的情況，CBQ會限制資料包通過的時間間隔嚴格按照計算的值。不過，由於時鐘解析度的原因，這樣可能不太合適。見minburst參數。

類別劃分
在一個CBQ實例中，可以存在很多分類。每個類有可以包括其它的QDisc，預設情況下，是pfifo。
在為資料包排隊時，CBQ作為根，使用不同的方法確定那個類接收資料包。

如果沒有一些不常見的配置選項，這個過程非常簡單。我們在每個節點上查詢一個指令，接著按照指令的指示讓資料包進入某個類。如果這個類是一個葉子節點，我們就把資料包排到這裡；如果這個類還有子節點，我們就重複以上過程。

我們在每個節點上重複以下操作，直到資料包被送出到其它節點，或者這個過程由於其它原因中止。

查詢附屬於類上的過濾器，如果過濾器把資料包發到某個葉子節點，處理完畢；否則，開始下一個查詢。
在defmap中查詢這個資料包的優先級，優先級倚賴於TCP頭的TOS域。檢查這個類是否還繼續分類，如果是重新開始下一個查詢。
向defmap要求獲得best effort優先級的指令，檢查應答是否還存在分類，如果不是則重新開始下一個查詢。
如果上述操作都沒有返回一個指令，就在這個節點把資料包排隊
這個算法可以保證資料包最終會有歸宿，即使你正在建立流量控制的配置。

連接共享算法
在向網路設備送出資料包時，CBQ首先要決定發出哪個類的資料包。它對所有的類採用加權輪轉(Weighted Round Robin)的方式處理，使每個類的資料包都有機會被送出。WRR處理首先從優先級最高(數字最小的優先級)的類開始處理，直到處理完類中所有的資料包，再接著處理優先級次之的類。
每個類可以從其兄弟類借頻寬。一個類可以使用bounded聲明其頻寬不可外借；也可以使用isolated聲明不原意外借頻寬。

QDISC
一個CBQ QDisc類的根有如下參數：

parent major:minor | root
這個命令的參數決定這個CBQ實例所在的位置，或者是在一個網路接口的根(root)，或者位於一個現有的類裡面。
handle major:
和其它的QDisc一樣，CBQ QDisc也可以指定一個句柄。句柄只能包含主識別號(major number)和一個冒號。數字的選擇是隨意的，不過如果在這個QDisc裡面會繼續分類，這個數字非常有用。
allot bytes
這個參數用於分配的頻寬，決定資料包傳輸的時間表。QDisc的allot參數和類的allot參數略有不同。數字bytes是任意的。預設是一個根據avpkt得到的數字。
avpkt bytes
資料包的平均大小，它用於計算最大空閒時間(maxidle)，也用於確認allot參數的值是安全的。
bandwidth rate
為了決定空閒時間(idle time)，CBQ必須知道底層物理接口的頻寬，或者父QDisc的頻寬。這是一個極為重要的參數，下面會繼續討論。
cell time
time的值決定進行資料包傳輸時間計算的時間間隔。使用預設值是比較明智的。
mpu bytes
一個大小為0的資料包仍然會消耗時間來傳輸。用這個參數設置小於bytes個位元組的資料包在進行傳輸時間的計算忽略不計。預設值是0。
ewma log
在CBQ需要測量平均空閒時間時，它會使用加權指數移動平均算法來平滑測量的值，得到一個移動平均值。log決定平滑因子的大小。這個數值介於0到31之間，數值越小敏感度越大。預設值是5。
一個CBQ QDisc只需要知道底層連接的大小。實際的頻寬限制由其子類完成。

分類
有很多參數可以用於分類的配置操作：

parent major:minor
確定父QDisc的位置，把這個類加入到樹狀結構中。如果它是直接附屬於一個QDisc，而且這個QDisc沒有其它的類，minor可以被忽略。這個參數是必須的。
classid major:minor
和QDisc一樣，類也可以命名。主識別號(major number)必須等於其父QDisc的主識別號。這個參數是可選的，只有它還需要再細分才需要。
weight weight
在從隊列中取出資料包通過網路接口向外送出時，CBQ會採用輪轉的方式輪流從隊列中取出屬於不同分類的資料包。weight設置每個類的權重。權重越高，在每個循環CBQ取出的資料包也就越多。一個類中所有的權重都會被換算成與rate參數設定值的百分比。
allot bytes
這個參數設置每個循環可以有多少個位元組出隊。這個值最小為avpkt的2/3。這個參數是必須的。
prio priority
設置類的優先級，在輪轉過程中，priority數字較小(優先級高)的類的資料包優先出隊。這個參數也是必須的。
avpkt bytes
參見QDisc中的相關介紹。
rate rate
設置這個類可以達到的最大速率，以及所有子類速率總和可以達到的值。這個參數是必需的。
bandwidth rate
這個參數不同於建立CBQ時的bandwidth參數。只有在決定maxidle和offtime時才有用，在設置maxburst或者minburst時，CBQ會使用maxidle和offtime進行計算。如果需要設置最大突發(maxburst)或者最小突發(miniburst)，這個參數是必需的。
maxburst
這個參數設置的數字用於計算maxidle，以便avgidle的值等於maxidle時，在avgidle達到0之前，允許設定的資料包突發性地通過。這個數字越大，對於突發流量的適應性越好。你不能直接設置maxidle，只能通過這個參數來設置。
minburst
上面講過，在過度限制(overlimit)情況下，CBQ需要調低頻寬。為了避免這種情況的出現，比較理想的解決方案是精確地空閒某個時間，然後放行一個資料包。然而，對於UNIX內核來說，很難對時間間隔小於10ms的事件進行調度，因此只好把等待時間放長，接著突發性地放行多個資料包。
上面所說的等待時間叫做offtime。minburst的值越高，在一個較長時間內進行的頻寬限制越準確，但是也會導致更大的突發流量。這個參數是可選的。

minidle
如果avgidle小於0，需要等待avgidle增加到一個足夠大的值才能送出一個資料包。為了避免在一個長期處於關閉狀態下的連接出現突發流量，如果avgidle太低就會被復位為minidle參數設置的數值。
minidle的單位是負微秒，10表示avgidle不能低於-10微秒。這個參數是可選的。

bounded
表示這個類的頻寬概不外借。
isolated
表示這個類的頻寬不原意外借。
split major:minor & defmap bitmap[/bitmap]
如果附屬於這個類的過濾器不能判斷資料包所屬類別，CBQ也可以根據資料包的優先級為它們分類。優先級共有8個，範圍是0到7。
defmap設置這個類接受具備哪些優先級的資料包，接受的優先級使用bitmap來計算，CBQ用bitmap和資料包的優先級域進行and計算。最低有效位(Least Significant Bit)對應優先級0。split告訴CBQ需要做出決定的類，參數應該是其父類。

例如：tc class add ... classid 10:1 cbq .. split 10:0 defmap c0，這條命令告訴類10:0把優先級為6和7的資料包都送到子類10:1。

然後最好使用tc class add ... classid 10:2 cbq ... split 10:0 defmap 3f命令決定其它優先級資料包的流向，把優先級為0、1、2、3、4和5的資料包都送給10:2。

C0的二進制是11000000，3F的二進制是001111111，因此這兩個defmap可以匹配資料包優先級域的所有位。C0匹配6和7，對應的是interactive和control位；而3F匹配餘下的位。

estimator interval timeconstant
CBQ能夠計量每個類使用了多少頻寬，tc過濾器能夠把資料包分類。CBQ使用一種簡單的估算方式計算每interval微秒通過多少流量，判斷自己使用的頻寬。另外，還需要進行指數平滑移動平均的計算，時間常數由timeconstant設置。它決定對短期突發流量平均值的敏感程度，這個值越高敏感度越低。

BUGS
底層鏈路的頻寬可能是無法預知的。例如，PPoE或者PPTP連接實際上是一個邏輯的通道，而不是一個物理設備。CBQ對於主要的頻寬配置錯誤有很大的彈性，代價可能就是頻寬固定(shaping)精度降低。
預設情況下，內核依靠粗糙的計時資訊進行頻寬固定。在一個較長的時間段內，可以維持很好的精度，但是在以秒為單位進行計量的時間段內，其結果就不準確了。

參考tc-cbq-details(8)(這個文檔至今尚未完成)改進這個問題。

參考
o Sally Floyd and Van Jacobson, "Link-sharing and Resource Management Models for Packet Networks", IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995

o Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995

o Sally Floyd, "Notes on Class-Based Queueing: Setting Parameters", 1996

o Sally Floyd and Michael Speer, "Experimental Results for Class-Based Queueing", 1998, not published.

tc(8)

作者
作者：Alexey N. Kuznetsov, <[email protected]>.
維護：bert hubert <[email protected]>.
中文翻譯：nixe0n <http://www.linuxaid.com.cn/articles/8/6/[email protected]>.