[發(fā)明專利]一種基于加權(quán)公平隊列的調(diào)度實現(xiàn)方法及裝置

有效

• 申請?zhí)枺?/td>: 201210241086.8
• 申請日: 2012-07-12
• 公開（公告）號: CN103546393A
• 公開（公告）日: 2014-01-29
• 發(fā)明（設(shè)計）人: 高繼偉;徐健
• 申請（專利權(quán)）人: 中興通訊股份有限公司
• 主分類號: H04L12/867
• 分類號: H04L12/867
• 代理公司: 北京安信方達知識產(chǎn)權(quán)代理有限公司 11262
• 代理人: 吳艷;龍洪

1.一種基于加權(quán)公平隊列的調(diào)度實現(xiàn)方法，其特征在于，

當(dāng)調(diào)度隊列的活動鏈表被服務(wù)完畢之后，按照以下方式進行計數(shù)器累加，并根據(jù)新的計數(shù)器值選擇下一個調(diào)度隊列：

用位圖empty表示各調(diào)度隊列鏈表的狀態(tài)，根據(jù)所述empty的最低非零位的位索引，記為x，得出2的最低非零位的位索引次冪Qn，即Qn＝2^x；并得出所述empty的最低非零位及其左邊的位全為1的位索引mask；

根據(jù)計數(shù)器當(dāng)前計數(shù)值counter與Qn*2^(t-1)的和得到第t個中間結(jié)果acct，其中t為正整數(shù)；

對第一個中間結(jié)果acc1進行驗證，如果所述acc1驗證通過，則選擇所述acc1和所述mask按位與運算結(jié)果作為新的計數(shù)器值；否則，選擇第二個中間結(jié)果acc2和所述mask按位與運算結(jié)果作為新的計數(shù)器值、或者選擇所述acc2至acct中的最小值和所述mask按位與運算結(jié)果作為新的計數(shù)器值。

2.如權(quán)利要求1所述的方法，其特征在于，采用以下方式對所述acc1進行驗證：

將所述acc1和所述mask進行按位與運算得到acc1mask，并得出所述acc1mask的最低非零位索引，記為m，提取empty的m位的值，記為flag；

如果所述flag非零，則所述acc1驗證通過；否則，如果所述flag為零，則所述acc1驗證未通過。

3.如權(quán)利要求1所述的方法，其特征在于，所述方法還包括，按照以下方式進行Flow的移動：

1)求出被調(diào)度隊列或流權(quán)重的倒序w’；

2)根據(jù)所述w’的最小非零位，得到計數(shù)器累加的步進值I；

3)計算新的計數(shù)器值D∶D＝(counter+I)mod(2N)，并找出D的最低非零位p；

4)計算q：判斷w’和p按位與結(jié)果是否為零，如果不為零，則q＝p；否則q＝I；

求得q后，將q作為其對應(yīng)的非零位的位置索引index，將該調(diào)度隊列或流添加至qindex的鏈尾。

4.一種基于加權(quán)公平隊列的調(diào)度實現(xiàn)裝置，其特征在于，所述裝置包括調(diào)度信息存儲提取模塊，flow移動模塊，和計數(shù)器累加模塊，其中：

所述調(diào)度信息存儲提取模塊，用于維護WFQ調(diào)度器及調(diào)度隊列的活動鏈表中flow鏈表信息、活動鏈表首尾指針信息以及活動鏈表狀態(tài)信息；當(dāng)所述WFQ調(diào)度器受到觸發(fā)時，讀取所述WFQ調(diào)度器的當(dāng)前計數(shù)器值，提取所述當(dāng)前計數(shù)器值對應(yīng)的調(diào)度隊列的活動鏈表的首尾指針，再讀取所述活動鏈表中flow的權(quán)重信息，發(fā)送給所述flow移動模塊；

所述flow移動模塊，用于根據(jù)收到的所述當(dāng)前計數(shù)器值，選擇相應(yīng)的活動鏈表，提取所述活動鏈表首指針對應(yīng)的flow的權(quán)重，進行flow移動的計算；

所述計數(shù)器累加模塊，用于受到觸發(fā)后，進行計數(shù)器累加，得出新的計數(shù)器值，返回給所述調(diào)度信息存儲提取模塊。

5.如權(quán)利要求4所述的裝置，其特征在于，

所述計數(shù)器累加模塊用于，按照以下方式進行計數(shù)器累加，得出新的計數(shù)器值：

用位圖empty表示各調(diào)度隊列鏈表的狀態(tài)，根據(jù)所述empty的最低非零位的位索引，記為x，得出2的最低非零位的位索引次冪Qn，即Qn＝2^x；并得出所述empty的最低非零位及其左邊的位全為1的位索引mask；

根據(jù)計數(shù)器當(dāng)前計數(shù)值counter與Qn*2^(t-1)的和得到第t個中間結(jié)果acct，其中t為正整數(shù)；

對第一個中間結(jié)果acc1進行驗證，如果所述acc1驗證通過，則選擇所述acc1和所述mask按位與運算結(jié)果作為新的計數(shù)器值；否則，選擇第二個中間結(jié)果acc2和所述mask按位與運算結(jié)果作為新的計數(shù)器值、或者選擇所述acc2至acct中的最小值和所述mask按位與運算結(jié)果作為新的計數(shù)器值。