一種使信元流量實現最小抖動的加權輪詢方法
2023-09-18 20:22:20 1
專利名稱：一種使信元流量實現最小抖動的加權輪詢方法
技術領域：
本發明涉及一種使信元流量實現最小抖動的加權輪詢方法，確切地說，涉及一種在使用傳統加權輪詢算法時，信元在短時間上的抖動過大，以及在使用專用集成電路ASIC或現場可編程門陣列FPGA器件實現時，邏輯規模太大的問題得到較好解決的加權輪詢方法，屬於異步轉移模式和其他業務的恆定比特率CBR業務的信元流量調度控制技術領域。
背景技術：
加權輪詢(WRR)算法主要應用在ATM和其他業務的CBR業務的流量調度上。現在，對於控制信元流量的傳統加權輪詢算法一般採用下述實現方法為了計算和比較時標，每條隊列分配一個16位的時標計數器，初始值為0x0000，這裡確定時標為16位是為了減少寄存器的數量，加快比較速度；另一個關鍵參數-16位的發送時間間隔參數則存儲在寄存器參數表中，該參數是根據隊列的預約帶寬和權值計算得到的，隊列的權值和信元時間間隔參數需要CPU進行配置，在執行配置時寫入寄存器。採用16位的時間間隔參數，解析度為622M/64K＝9.8K；權值的計算公式為WEIGHT＝|R/9.8K|，式中R為每條隊列的預約速率。
每次通過輪詢選取隊列，找到一個隊列後，先檢查該隊列時標計數器的值是否符合發送條件隊列[n]Counter＜隊列[m]Counter？如果符合條件，就發送該隊列的一個信元，並把該隊列的計數器加上本隊列的時間間隔值，再輪詢進行下一次運算。否則，就發送另一個隊列的信元，並使其隊列的計數器加上本隊列的時間間隔值。如果一條隊列的計數值到達最大值0xFFFF，就等待另一隊列的計算。如果所有計數器都到達或接近最大值0xFFFF時，同時把所有的計數器清零，重新進行計算。
參見圖1，該圖描述了兩個隊列CBR_A和CBR_B分別使用權值為7和4、信元間隔參數為4和7進行上述傳統加權輪詢算法的簡化調度示意。在這種傳統加權輪詢算法中，對於兩個隊列需要比較該兩個時標寄存器的大小，還需要判斷這兩個寄存器是否接近於0xFFFF，以便對它們重新進行清零處理。對於多個隊列，就需要找出各個隊列時標寄存器的最小值來判斷哪個隊列滿足發送條件。
這種傳統加權輪詢算法能夠保證在較長的周期中各個隊列的帶寬是均勻的。但是，在有多個隊列、且各個隊列的帶寬相差較大時，傳統加權輪詢算法所得到的結果在短時上的抖動比較大。對於僅有兩個隊列的情況，各個隊列短時流量的抖動看起來還不太明顯。如果隊列數量較多，短時抖動就非常明顯了。
下面例舉一個簡化的有16個隊列的情況假設總帶寬為48M，總共有16個隊列業務(隊列序號小的優先級高)，各個隊列中需要的最小帶寬為1M。該簡化的16個隊列所需要的帶寬分配如下表所示
如果採用傳統加權算法進行隊列調度，得到的48個調度的順序如下表所示
參見圖2所示的其中編號為CBR_0和CBR_1的隊列發送時隙在時間軸上的一段局部分布狀況，從圖2可以清楚地看出編號為CBR_0和CBR_1的隊列速率在短時上的抖動相當大。
因此，傳統加權輪詢算法的缺點主要是流量的短時抖動比較大，對於有一些對短時抖動要求較高的應用就不甚合適。同時使用這種傳統技術實現時，需要通過多次比較才能得到一個最小值結果。在使用邏輯器件實現的時候，需要的資源很大；如果使用CPU進行計算，則速度很慢。
發明內容
本發明的目的是提供一種使信元流量實現最小抖動的加權輪詢方法，以解決現有技術存在的短時抖動過大，以及在使用ASIC或FPGA器件實現時邏輯規模太大的問題。
本發明的目的是這樣實現的一種使信元流量實現最小抖動的加權輪詢方法，其特徵在於該方法包括下列三個步驟A、對各個信元隊列進行編號；B、配置一個將各個隊列的編號均勻分布的查找表；C、按照查找表的順序發送各個隊列的信元，從而實現隊列的流量調度。
所述的步驟A中，對各個信元隊列進行編號之前，進一步包括下列步驟A1、確定需要實現的各個隊列的最小流量或流量控制的最小步進；A2、確定傳輸信道上可供使用的總帶寬；A3、根據上述最小流量和傳輸信道上可供使用的總帶寬，得到所需要的查找表的長度L∶L＝總帶寬/最小流量。
所述的步驟A3中，所需要的查找表是存儲該配置數據的RAM存儲器。
所述的查找表的長度是RAM存儲器的存儲深度，即存儲器的存儲空間。
所述的步驟A3中，根據計算公式L＝總帶寬/最小流量得到的所需要的查找表的長度L可以只取整數部分，以使該查找表的長度最短；也可以對查找表的長度L的計算結果精確到小數點後的若干位，即加大查找表的長度，使各個隊列的流量得到更精確的控制。
所述的步驟B中，配置一個將各個隊列的編號均勻分布的查找表是採用偽隨機交織的方法。
所述的步驟B中，在查找表中均勻分布配置各個隊列的編號時，其配置結果應該滿足下述三個條件各個隊列編號出現的次數與其配置的帶寬成正比，表示各個隊列的編號均勻分布在RAM存儲器空間上，以及如果將生成的查找表展開，在整個查找表中的任何一個節距上，各個隊列編號出現的次數與其在查找表內相應位置的個數的誤差不超過1個。
所述的步驟C中，按照查找表的順序發送各個隊列的信元，進一步包括下列步驟C1、根據上述配置的查找表順序，確定發送的隊列編號，同時發送該隊列的一個信元；C2、在每次發送一個信元之後，將查找表的地址加1，再讀出查找表內該新地址的數據，即確定下一個發送的隊列編號，接著發送該隊列的一個信元；C3、循環進行上述步驟C2的操作，直至所有隊列的信元全部發送完畢。
對於SDH/SONET承載包或POS/SPI系統包接口上的變長報文，先將其切割成定長的信元，再執行所述的各個步驟，可實現變長報文的流量調度。
本發明是一種使信元流量實現最小抖動的加權輪詢方法，該方法的技術關鍵是採用一個將各個隊列的編號均勻分布的查找表，來實現隊列的流量調度。本發明的優點是實現簡單，解決了傳統加權輪詢算法的缺陷，在實現時，無須比較各個隊列的時標寄存器，可以大大減小實現加權輪詢算法的難度和複雜度，在使用ASIC或FPGA實現本發明的時候，極大地減小了邏輯器件實現的規模和難度；同時極大地減小了傳統加權輪詢算法引起的短時流量的抖動，使短時抖動減小到最低程度。另外，由於本發明只進行查表，如果使用CPU進行計算，其速度很快，遠遠高於現有的加權輪詢算法的速度。本發明還可以在SDH/SONET承載包或系統包(POS/SPI，Packet Over SDH/SONET/System PacketInterface)接口上實現變長報文的流量調度，即先將變長報文切割成定長的信元，然後應用本發明方法進行調度。
圖1是傳統加權輪詢算法的簡化調度示意圖。
圖2是用圖1所示的傳統加權輪詢算法的實施例中編號為CBR_0和CBR_1的隊列速率在短時上抖動很大的情況示意圖。
圖3是本發明使信元流量實現最小抖動的加權輪詢方法的流程圖。
圖4是採用本發明的實施例中編號為CBR_0和CBR_1的兩個隊列在短時上的速率抖動明顯減少的情況示意圖。
具體實施例方式
本發明是一種使信元流量實現最小抖動的加權輪詢方法，該方法是先對各個信元隊列進行編號，再配置一個將各個隊列的編號均勻分布的查找表，並按照查找表的順序發送各個隊列的信元，從而實現隊列的流量調度。
參見圖3，該方法包括下列具體步驟(1)確定需要實現的各個隊列的最小流量或流量控制的最小步進(Bwsmin)；例如64K。
(2)確定傳輸信道上可供使用的總帶寬(Bwtmax)；例如一條光纖的帶寬，或者是系統分配的一條傳輸信道的帶寬622M。
(3)根據上述最小流量和傳輸信道上可供使用的總帶寬，得到所需要的查找表的長度L∶L＝總帶寬(Bwtmax)/最小流量(Bwsmin)，也就是RAM存儲器的深度(即地址空間)為622M/64K＝9800，為了減小RAM空間，可以對其結果L只取整數部分。
(4)將各個恆定比特率CBR業務逐一編號，假如有4096個隊列，則可將隊列編號為0～4095；再採用偽隨機交織的方法在可供使用的總帶寬空間裡均勻分布配置編號的各個隊列，即將各個隊列編號0～4095在9800地址空間內均勻分布配置，並將這些配置數據存入查找表中；且配置結果應該符合下列條件A、各個隊列編號出現的次數與其配置的帶寬成正比。如配置第0個CBR業務地帶寬為128K，那麼隊列0在查找表(即RAM)中出現的次數應為2次。B、表示各個隊列的編號應在RAM空間上均勻分配。C、在整個查找表9800地址中的任何一個節距上，各個隊列編號出現的次數與其在查找表內相應位置的個數一致，其誤差不超過1個。
(5)根據上述配置的查找表順序，確定發送的隊列編號，同時發送該隊列的一個信元；(6)在每次發送一個信元之後，將查找表的地址加1，再讀出查找表內該新地址的數據，即確定下一個發送的隊列編號，接著發送該隊列的一個信元；(7)循環進行上述步驟(6)的操作，直至所有隊列的信元全部發送完畢。
下面採用背景技術中的同一個實施例進一步具體說明之。假設總帶寬為48M，總共有16個隊列業務(隊列序號小的優先級高)，各個隊列中需要的最小帶寬為1M。該簡化的16個隊列所需要的帶寬分配如下表所示
採用本發明所述步驟中(1)～(5)的辦法得到用於隊列調度的查找表，它是一個4×48的RAM，RAM內的數據見下表
這個查找表與隊列調度的順序是一致的，也就是說，應該按照該查找表的順序發送隊列。
根據上述查找表，對於編號為CBR_0和CBR_1的隊列發送時隙在時間軸上的分布則如圖4所示。從圖4中可以明顯看到，採用本發明後，CBR_0和CBRCBR_1隊列在短時上的速率抖動顯著減小，各個隊列的信元均勻發送的好處是顯而易見的。同時本發明是採用查表的辦法省略了比較時標的程序，大大減少了用ASIC和FPGA器件實現的難度和規模。
本發明的方法已經在申請人研製的設備上進行試驗實施，實施的結果是成功的，實現了發明目的。
權利要求
1.一種使信元流量實現最小抖動的加權輪詢方法，其特徵在於該方法包括下列三個步驟A、對各個信元隊列進行編號；B、配置一個將各個隊列的編號均勻分布的查找表；C、按照查找表的順序發送各個隊列的信元，從而實現隊列的流量調度。
2.根據權利要求1所述的加權輪詢方法，其特徵在於所述的步驟A中，對各個信元隊列進行編號之前，進一步包括下列步驟A1、確定需要實現的各個隊列的最小流量或流量控制的最小步進；A2、確定傳輸信道上可供使用的總帶寬；A3、根據上述最小流量和傳輸信道上可供使用的總帶寬，得到所需要的查找表的長度L∶L＝總帶寬/最小流量。
3.根據權利要求2所述的加權輪詢方法，其特徵在於所述的步驟A3中，所需要的查找表是存儲該配置數據的RAM存儲器。
4.根據權利要求2或3所述的加權輪詢方法，其特徵在於所述的查找表的長度是RAM存儲器的存儲深度，即存儲器的存儲空間。
5.根據權利要求2所述的加權輪詢方法，其特徵在於所述的步驟A3中，根據計算公式L＝總帶寬/最小流量得到的所需要的查找表的長度L可以只取整數部分，以使該查找表的長度最短；也可以對查找表的長度L的計算結果精確到小數點後的若干位，即加大查找表的長度，使各個隊列的流量得到更精確的控制。
6.根據權利要求1所述的加權輪詢方法，其特徵在於所述的步驟B中，配置一個將各個隊列的編號均勻分布的查找表是採用偽隨機交織的方法。
7.根據權利要求1或6所述的加權輪詢方法，其特徵在於所述的步驟B中，在查找表中均勻分布配置各個隊列的編號時，其配置結果應該滿足下述三個條件各個隊列編號出現的次數與其配置的帶寬成正比，表示各個隊列的編號均勻分布在RAM存儲器空間上，以及如果將生成的查找表展開，在整個查找表中的任何一個節距上，各個隊列編號出現的次數與其在查找表內相應位置的個數的誤差不超過1個。
8.根據權利要求1所述的加權輪詢方法，其特徵在於所述的步驟C中，按照查找表的順序發送各個隊列的信元，進一步包括下列步驟C1、根據上述配置的查找表順序，確定發送的隊列編號，同時發送該隊列的一個信元；C2、在每次發送一個信元之後，將查找表的地址加1，再讀出查找表內該新地址的數據，即確定下一個發送的隊列編號，接著發送該隊列的一個信元；C3、循環進行上述步驟C2的操作，直至所有隊列的信元全部發送完畢。
9.根據權利要求1或2所述的加權輪詢方法，其特徵在於對於SDH/SONET承載包或POS/SPI系統包接口上的變長報文，先將其切割成定長的信元，再執行所述的各個步驟，可實現變長報文的流量調度。
全文摘要
一種使信元流量實現最小抖動的加權輪詢方法，該方法是先對各個信元隊列進行編號，再配置一個將各個隊列的編號均勻分布的查找表，並按照查找表的順序發送各個隊列的信元，從而實現隊列的流量調度。本發明的優點是實現簡單，解決了傳統加權輪詢算法的缺陷，在實現時，無須比較各個隊列的時標寄存器，可以大大減小實現加權輪詢算法的難度和複雜度，在使用ASIC或FPGA實現本發明的時候，極大地減小了邏輯器件實現的規模和難度；同時極大地減小了傳統加權輪詢算法引起的短時流量的抖動，使短時抖動減小到最低程度。另外，由於本發明只進行查表，如果使用CPU進行計算，其速度很快，遠遠高於現有的加權輪詢算法的速度。
文檔編號H04Q3/00GK1507212SQ0215533
公開日2004年6月23日 申請日期2002年12月10日 優先權日2002年12月10日
發明者胡正超 申請人:華為技術有限公司