1、隊列及擁塞管理隊列及擁塞管理擁塞管理的中心內容是當擁塞發生時如何制定一個策略，用于決定報文轉發的處理次序和丟棄原則，一般采用隊列技術。隊列指的是在緩存中對報文進行排序的邏輯。當流量的速率超過接口帶寬或超過為該流量設置的帶寬時，報文就以隊列的形式暫存在緩存中。報文離開隊列的時間、順序，以及各個隊列之間報文離開的相互關系則由隊列調度算法決定。L口說明:路由器轉發平面的流量管理器TM(TrafficManager)上有一些高速緩存，用于報文的緩沖和轉發，緩存由所有端口共享，各端口競爭使用。為了避免有的端口長時間搶不到緩存而出現斷流，路由器給每個端口分配了一塊最小可用緩存，并且分配到端口的各個隊列上，

2、保證每個隊列均有緩存可用。當TM收到報文時，將報文放入緩存，網絡不擁塞時，報文能被及時轉發，不會在緩存中產生堆積。這種情況下報文在緩存中的時間為as級，延遲時間可以忽略不計。當網絡擁塞時，報文在緩存中產生堆積，被延遲處理，延遲時間會大幅增加。延遲時間的大小主要取決于隊列的緩存長度以及該隊列獲得的輸出帶寬，可以使用如下公式計算時延：隊列時延=隊列緩存長度/隊列輸出帶寬華為路由器設備的每個端口上都有8個下行隊列，稱為CQ(ClassQueue)隊列，也叫端口隊列(Port-queue),分別為BE、AF1、AF2、AF3、AF4、EF、CS6和CS7。單個隊列的報文采用FIFO(FirstInFi

3、rstOut)原則入隊和出隊。圖1報文入隊出隊方式FIFO修則人隊列報文3報文2世文1FIFOUNJ出巴列匚極義3薄又2施官1隊列調度算法本文介紹幾種常見隊列調度算法: 先進先出FIFO(FirstInFirstOut) 嚴格優先級SP(StrictPriority) 輪詢RR(RoundRobin) 力口權車&詢WRR(WeightedRoundRobin) 差分輪詢DRR(DeficitRoundRobin) 差分力口權輪詢DWRR(DeficitWeightedRoundRobin) 加權公平隊歹UWFQ(WeightedFairQueuing)FIFOFIFO不對報文進彳f分類

4、。FIFO按報文到達接口的先后順序讓報文進入隊列，在隊列的出口讓報文按進隊的順序出隊，先進的報文將先出隊，后進的報文將后出隊，如IMoSPSP(StrictPriority)調度就是嚴格按照隊列優先級的高低順序進行調度。只有高優先級隊列中的報文全部調度完畢后，低優先級隊列才有調度機會。假設端口有3個采用SP調度算法的隊列，分別為高優先(High)隊列、中優先(Medium)隊列、和低優先(Low)隊列，它們的優先級依次降低。如圜工，其中報文編號表示報文到達順序。圖2SP調度 當優史以隊即|報拈j驅必卜優先級口廠限也”報£41HZ3氏憂米祖鼠掰在報文出隊的時候，首先讓高優先隊列中的報文

5、出隊并發送，直到高優先隊列中的報文發送完,然后發送中優先隊列中的報文，直到發送完，接著是低優先隊列。在調度低優先級隊列時，如果高優先級隊列又有報文到來，則會優先調度高優先級隊列。這樣，較高優先級隊列的報文將會得到優先發送，而較低優先級的報文后發送。SP調度的缺點是：擁塞發生時，如果較高優先級隊列中長時間有報文存在，那么低優先級隊列中的報文就會由于得不到服務而餓死”。RRRR調度采用輪詢的方式，對多個隊列進行調度。RR以環形的方式輪詢多個隊列。如果輪詢的隊列不為空，則從該隊列取走一個報文；如果該隊列為空，則直接跳過該隊列，調度器不等待。圖3RR調度報文3/2蟆1|據文8八班文8：報文1代丈9報報

6、丈L皿上山鼠列匚二>擢*9報文呂根文3.報文史|艱文5i寸陽開的祖文WRR加權輪詢WRR(WeightedRoundRobin)調度主要解決RR不能設置權重的不足。在輪詢的時候，WRR每個隊列享受的調度機會和該隊列的權重成比例。RR調度相當于權值為1的WRR調度。WRR的實現方法是為每個隊列設置一個計數器Count,根據權重進行初始化。每次輪詢到一個隊列時，該隊列輸出一個報文且計數器減一。當計數器為0時停止調度該隊列，但繼續調度其他計數器不為0的隊列。當所有隊列的計數器都為0時，所有計數器重新根據權重初始化，開始新一輪調度。在一個循環中，權重大的隊列被多次調度。第4個輪詢第3個輪詢蚯&#

7、163;4=垠£3Couri(21=a|Count(2|-1jEI推文6：Count3=0Count3=1圖4WRR調度隊列1：5。%時膽25%隊列3：25%假設某端口有3個隊列采用WRR調度，為每個隊列配置一個權值，依次為50%、25%、25%,詳細的調度過程如下:首先計數器初始化：Count1=2,Count2=1,Count3=1。 第1個輪詢：從隊列1取出報文1發送，Count1=1;從隊列2取出報文5發送，Count2=0;從隊列3取出報文8發送，Count3=0。 第2個輪詢：從隊列1取出報文2發送，Count1=0;由于Count2=0,Count3=0,隊列2和隊列3

8、不參與此輪調度。此時，Count1=0,Count2=0,Count3=0,將計數器重新初始化：Count1=2,Count2=1,Count3=1。 第3個輪詢:從隊列1取出報文3發送，Count1=1;從隊列2取出報文6發送，Count2=0;從隊列3取出報文9發送，Count3=0。 第4個輪詢：從隊列1取出報文4發送，Count1=0;由于Count2=0,Count3=0,隊列2和隊列3不參與此輪調度。此時，Count1=0,Count2=0,Count3=0,將計數器重新初始化：Count1=2,Count2=1,Count3=1。從統計上看，各隊列中的報文流被調度的次數與該隊列的

9、權值成正比，權值越大被調度的次數相對越多。如果該端口為100Mbps,則可以保證最低權重的隊列至少獲得25Mbps帶寬，避免了采用SP調度時低優先級隊列中的報文可能長時間得不到服務的缺點。WRR對于空的隊列直接跳過，循環調度的周期變短，因此當某個隊列流量小的時候，剩余帶寬能夠被其他隊列按照比例占用。WRR調度有兩個缺點： WRR調度按照報文個數進行調度，因此每個隊列沒有固定的帶寬，同等調度機會下大尺寸報文獲得的實際帶寬要大于小尺寸報文獲得的帶寬。而用戶一般關心的是帶寬。當每個隊列的平均報文長度相等或已知時，通過配置WRR權重，用戶能夠獲得想要的帶寬；但是，當隊列的平均報文長度變化時，用戶就不能

10、通過配置WRR權重獲取想要的帶寬。 低延時需求業務(如語音)得不到及時調度。DRR差分輪詢DRR(DeficitRoundRobin)調度實現原理與RR調度基本相同。DRR與RR的區別是：RR調度是按照報文個數進行調度，而DRR是按照報文長度進行調度。DRR為每個隊列設置一個計數器Deficit,Deficit初始化為一次調度允許的最大字節數，一般為接口MTUo每次輪詢到一個隊列時，該隊列輸出一個報文且計數器Deficit減去報文長度。如果報文長度超過了隊列的調度能力，DRR調度允許Deficit出現負值，以保證長報文也能夠得到調度。但下次輪循調度時該隊列將不會被調度。當計數器為0或負數時停止

11、調度該隊列，但繼續調度其他計數器為正數的隊列。當所有隊列的Deficit都為0或負數時，將所有隊列的Deficit計數器加上初始值，開始新一輪調度。假設某端口MTU=150Bytes,有2個隊列Q1和Q2采用DRR調度，Q1隊列中有多個200Bytes的長報文，Q2隊列中有多個100Bytes的端報文，則調度過程如圖_5。梨冷前調修著I調度轉1遍嚏前口前訊1=0產IIJeficiqiROQ停|上調度償匕調度II益口*；200IiWI>詞變后IDenclt1=-150,LiI1謂我前西度宜I調度前調度前口喃血胃=100以而咽=前1|SODeficit21=10DX100+IXX11100-

12、rI100+討度后四度卮1淑度后I因度后Daficit2=0Deficit25-501n麗咽:50Defcit20匏b俯第5輪見4相第3用由于上一輪所有DefiGiKR,*輪詢度前,所有Defidt都加上初始值由上圖可以看出，經過第16輪DRR調度，Q1隊列被調出了3個200Bytes的報文，Q2隊列被調出了6個100Bytes的報文。從長期的統計看，Q1和Q2的實際輸出帶寬比是1:1,為公平的比例。DRR調度避免了采用SP調度時低優先級隊列中的報文可能長時間得不到服務的缺點。但是,DRR調度不能設置權重，且也具有低延時需求業務(如語音)得不到及時調度的缺點。DWRR差分加權輪詢DWRR(De

13、ficitWeightedRoundRobin)調度主要解決DRR不能設置權重的不足。DRR調度相當于權值為1的DWRR調度。DWRR為每個隊列設置一個計數器Deficit,Deficit初始化為Weight*MTU。每次輪詢到一個隊列時，該隊列輸出一個報文且計數器Deficit減去報文長度。當計數器為0時停止調度該隊列，但繼續調度其他計數器不為0的隊列。當所有隊列的計數器都為0時，所有計數器的Deficit都加上Weight*MTU,開始新一輪調度。假設某端口MTU=150Bytes,有2個隊列Q1和Q2采用DRR調度，Q1隊列中有多個200Bytes的長報文，Q2隊列中有多個100Byte

14、s的端報文，Q1和Q2配置權重比為weight1:weight2=2:1。則DWRR調度過程如圖6。圖6DWRR調度制3輪調度前口白加收120口I笫2輪；魂度前!口M叫1卜10口第1輪四度檔D白Q1：加2叩12001120。一2Q0一洲出0境度前調施后Deficrt1)=10q111我度前I1DM亡可即=苑I11調度后。號曲叩卜的0調度醫Daficitp=l5OQ2:1001001001Q&100100100411Q041004璃度后Bfic峭F調度一1調用后Ofid憫=50 第一次調度Deficit1=weight1*MTU=300,Deficit2=weight2*MTU=150,

15、從Q1隊列取出200Bytes報文發送，從Q2隊列取出100Bytes發送；發送后，Deficit1=100,Deficit2=50。 第二次調度從Q1隊列取出200Bytes報文發送，從Q2隊列取出100Bytes發送；發送后，Deficit1=-100,Deficit2=-50。 第三次調度此時兩個隊列都為負，因此，Deficit1=Deficit1+weight1*MTU=-100+2*150=200,Deficit2=Deficit2+weight2*MTU=-50+1*150=100。從Q1隊列取出200Bytes報文發送，從Q2隊列取出100Bytes發送；發送后，Deficit1

16、=0,Deficit2=0。由上圖可以看出，經過第13輪DWRR調度，Q1隊列被調出了3個200Bytes的報文，Q2隊列被調出了3個100Bytes的報文。從長期的統計看，Q1和Q2的實際輸出帶寬比是2:1,與權重比相符。DWRR調度避免了采用SP調度時低優先級隊列中的報文可能長時間得不到服務的缺點，也避免了各隊列報文長度不等或變化較大時，WRR調度不能按配置比例分配帶寬資源的缺點。但是，DWRR調度也具有低延時需求業務(如語音)得不到及時調度的缺點。WFQ加權公平隊列WFQ(WeightedFairQueuing)調度是按隊列權重來分配每個流應占有出口的帶寬。同時，為了使得帶寬分配更加公平

17、”，WFQ以bit為單位進行調度，類似于旦工的bit-by-bit調度模型。圖7Bit-by-bit調度模型隊創1；50%4biti:;，上出隊列BrtWbrt：SiM到3：25%8bitI忸離開的推文Bit-by-bit調度模型可以完全按照權重分配帶寬，防止長報文比短報文獲得更多帶寬，從而減少大小報文共存時的時延抖動。但Bit-by-bit調度模型只是理想化的模型，實際上，華為路由器實現的WFQ是按照一定的粒度,例如256B、1KB,或其他粒度，具體按何種粒度，與單板類型相關。WFQ的優點:不同的隊列獲得公平的調度機會，從總體上均衡各個流的延遲。 短報文和長報文獲得公平的調度：如果不同隊列間

18、同時存在多個長報文和短報文等待發送,讓短報文優先獲得調度，從而在總體上減少各個流的報文間的抖動。 從統計上看，權重越小，所分得的帶寬越少。權重越大，所分得的帶寬越多。端口隊列調度方式對于華為路由器設備每個接口上的8個端口隊列，用戶可以為其都配置成SP調度，或者是基于權重的調度。根據隊列調度算法，8個端口隊列可以分為三組： PQ隊列PQ隊列之間采用SP調度算法，當從隊列調度報文時，先從高優先級的隊列調度報文。這樣，可對不同業務數據提供絕對的優先，對時間敏感的實施應用如VoIP的延時可以得到保證，對優先業務的報文帶寬占用可以絕對優先。PQ的缺點：如果不對高優先級的報文帶寬加限制，會造成低優先級報文

19、得不到帶寬，可能出現餓死'現象。華為路由器允許將8個端口隊列都配置成PQ隊列，但不建議這么配置。通常情況下，只時延敏感的業務入PQ隊列。 WFQ隊列WFQ隊列是按權重進行調度的，調度算法可以是WRR、DWRR或WFQ調度算法中的其中一種，這些算法都是按權重進行剩余帶寬的分配。P40-E子卡使用的是DWRR;其他類型單板使用WFQ或WRR。 LPQ隊列LPQ隊列是在高速鏈路（以太網）接口上實現的隊列調度機制。低速鏈路（如Serial、MP-Group）上不支持LPQ隊列。PQ隊同FQ隊式至7LPQ認列空三種隊列的調度順序果還有剩余帶寬則分配給LPQ實際應用中，可以將BE流用LPQ進行調度

20、。這樣，在網絡負載較重時，BE流可以完全被限制，優先滿足其它業務。所有的8個端口隊列可以全部配置成WFQ,也可以全部配置成PQ,也可以全部配置成LPQ,也可以組合PQ、WFQ、LPQ之間采用SP調度算法，優先調度PQ隊列，再調度WFQ隊列，最后調度LPQ隊列，如圖8。詳細流程如圖9圖9隊列間的調度流程LPQ隊列之間的調度方式與PQ隊列一樣，也采用SP調度。不同在于擁塞時PQ可以搶占WFQ的帶寬，而LPQ不可以搶占WFQ的帶寬。在PQ和WFQ隊列調度結束后，如圖8端口隊列調度順序執打輪FQ調度執行一輪IRQ調用執才J一輪WFQ調出WFQ 在調度出隊的時候，若PQ隊列中有報文，則總是優先發送PQ隊

21、列中的報文，直到PQ隊列中沒有報文時才調度發送WFQ隊列中的報文。只要PQ隊列中有報文，系統就會優先發送PQ隊列中的報文。 若PQ隊列中沒有報文時，則調度WFQ隊列。如果在調度WFQ隊列過程中，PQ隊列又有報文到來，則會優先調度PQ隊列。 直到WFQ中的報文被發送完畢，才調度LPQ隊列中的報文。上述調度的結果是：首先保證PQ隊列的PIR帶寬，剩余帶寬在各WFQ隊列間按權重分配；如果某些隊列沒有用完帶寬（即已滿足PIR帶寬且還有剩余），則剩余帶寬在未滿足PIR的隊列之間按權重分配；如果還有剩余帶寬再在未滿足PIR的隊列間分配如此反復，直到滿足所有WFQ隊列的PIR帶寬；如果此時還有剩余帶寬，則分

22、配給LPQ。CQ說明：這里的PIR是指使用port-queue命令配置的整形速率。隊列帶寬分配示例1假設某端口整形速率為100Mbps（缺省情況下，接口的整形速率是接口帶寬），該接口各業務的輸入帶寬及配置的PIR如下。隊列類型隊列類型輸入帶寬（bps）PIR(bps)CS7PQ65M55MCS6PQ30M30MEFWFQ,權重510M5MAF4WFQ,權重410M10MAF3WFQ,權重310M15MAF2WFQ,權重220M25M隊列類型隊列類型輸入帶寬(bps)PIR(bps)AF1WFQ,權重120M20MBELPQ100M未配置則帶寬分配過程如下:首先進行PQ調度。100Mbps先供C

23、S7使用，CS7輸出帶寬=Min(端口整形速率，CS7輸入帶寬，CS7的PIR帶寬)=Min(100M,65M,55M)=55M,剩余45Mbps供CS6使用,CS6輸出帶寬=Min(剩余帶寬，CS6輸入帶寬，CS6的PIR帶寬)=Min(45Mbps,30Mbps,30Mbps)=30MbpsPQ調度后，剩余帶寬=100Mbps-55Mbps-30Mbps=15Mbps。接著進行第一輪WFQ調度，剩余帶寬在各WFQ隊列中按權重分配。計算公式：分給某WFQ隊列的帶寬=剩余帶寬*本隊列權重/所有WFQ隊列權重之和=15Mbps*本隊列權重/15,因此,本輪分配給EF的帶寬=15Mbps*5/15

24、=5Mbps=PIR分配給EF的帶寬沒有剩余本輪分配給AF4的帶寬=15Mbps*4/15=4Mbps<PIRAF4的帶寬沒有剩余本輪分配給AF3的帶寬=15Mbps*3/15=3Mbps<PIRAF3的帶寬沒有剩余本輪分配給AF2的帶寬=15Mbps*2/15=2Mbps<PIRAF2的帶寬沒有剩余本輪分配給AF1的帶寬=15Mbps*1/15=1Mbps<PIRAF1的帶寬沒有剩余此時剩余帶寬為0,BE流量沒有獲得調度，輸出帶寬為各隊列輸出帶寬如下:隊列類型隊列類型輸入帶寬(bps)PIR(bps)輸出帶寬(bps)CS7PQ65M55M55MCS6PQ30M30M

25、30M隊列類型隊列類型輸入帶寬(bps)PIR(bps)輸出帶寬(bps)EFWFQ,權重510M5M5MAF4WFQ,權重410M10M4MAF3WFQ,權重310M15M3MAF2WFQ,權重220M25M2MAF1WFQ,權重120M20M1MBELPQ100M未配置0隊列帶寬分配示例2假設某端口整形速率為100Mbps,該接口各業務的輸入帶寬及配置的PIR如下隊列類型隊列類型輸入帶寬(bps)PIR(bps)CS7PQ15M25MCS6PQ30M10MEFWFQ,權重590M100MAF4WFQ,權重410M10MAF3WFQ,權重310M15M隊列類型隊列類型輸入帶寬(bps)PIR

26、(bps)AF2WFQ,權重220M25MAF1WFQ,權重120M20MBELPQ100M未配置則帶寬分配過程如下: 首先進行PQ調度，保證PQ流隊列的PIR帶寬。PQ調度后，剩余帶寬=100Mbps-15Mbps-10Mbps=75Mbps。 接著進行第一輪WFQ調度，剩余帶寬在各WFQ隊列中按權重進行分配。計算公式：分給某WFQ隊列的帶寬=剩余帶寬*本隊列權重/所有WFQ隊列權重之和=75Mbps*本隊列權重/15,因此，,分配給EF的帶寬沒有剩余,AF4實際獲得帶寬,AF3實際輸入帶寬只有,分配給AF2的帶寬沒有剩余,分配給AF1的帶寬沒有剩余本輪分配給EF帶寬=75Mbps*5/15

27、=25Mbps<PIR本輪分配給AF4帶寬=75Mbps*4/15=20Mbps>PIR=PIR=10Mbps,分配給AF4的帶寬剩余10Mbps本輪分配給AF3帶寬=75Mbps*3/15=15Mbps=PIR10Mbps,因此分配給AF3的帶寬剩余5Mbps本輪分配給AF2帶寬=75Mbps*2/15=10Mbps<PIR本輪分配給AF1帶寬=75Mbps*1/15=5Mbps<PIR 此時，端口剩余帶寬15Mbps,因此在未滿足PIR的隊列(EF、AF2和AF1)之間按權重分配剩余帶寬本輪分配給EF的帶寬=15Mbps*5/8=9.375Mbps,此時EF獲得帶寬

28、共34.375Mbps,依然小于PIR,因此分配給EF的帶寬沒有剩余本輪分配給AF2保證帶寬=15Mbps*2/8=3.75Mbps,此時AF2獲得帶寬共13.75Mbps,依然小于PIR,因此分配給AF2的帶寬沒有剩余本輪分配給AF1保證帶寬=15Mbps*1/8=1.875Mbps,此時AF1獲得帶寬共6.875Mbps,依然小于PIR,分配給AF1的帶寬沒有剩余此時剩余帶寬為0,BE流量沒有獲得調度，輸出帶寬為0。各隊列輸出帶寬如下:隊列類型隊列類型輸入帶寬(bps)PIR(bps)調度輸出帶寬(bps)1CS7PQ15M25M15MrCS6PQ30M10M10M1EFWFQ,權重590M100M34.375MAF4WFQ,權重410M10M10MAF3WFQ,權重310M15M10MAF2WFQ,權重220M25M13.75MAF1WFQ,權重120M20M6.875MBELPQ100M未配置0隊列帶寬分配示例3假設某端口整形速率為10