Weighted Round Robin(WRR) vs Deficit Round Robin(DRR) vs Modified Deficit Round Robin(MDRR)

◎Weighted Round Robin(WRR)


佇列調度將每個interface分為多個輸出佇列,佇列之間輪流調度,保證每個佇列都得到一定的服務時間,WRR可為每個佇列配置一個加權值(依次為W3、W2、W1、W0),加權值表示獲取資源的比重。


如一個FE interface,配置它的WRR佇列調度算法的加權值為50、30、10、10(依次對應W3、W2、W1、W0),這樣可以保證最低優先等級佇列至少獲得10Mbits/sec頻寬,避免了採用PQ調度時低優先等級佇列中的封包可能長時間得不到服務的缺點。WRR佇列還有一個優點是,雖然多個佇列的調度是輪番進行的,但是對每個佇列不是固定地分配服務時間片段 - 如果某個佇列為空,那麼馬上換到下一個佇列調度,這樣頻寬資源可以得到充份的利用。
(借錢不還)



◎Deficit Round Robin(DRR)


Deficit Round Robin 機制與 WRR 相似,但可適合不同封包長度的應用,並解決了一些WRR頻寬分配不準確的問題(byte count and MTU ratio過大或過小)。DRR 也是和 WRR 一樣去掃瞄每一個有封包的佇列,只不過每次服務固定的 byte count,如果有剩下的byte count,則會被紀錄起來,等待下次再輪到這個佇列時還可使用。
(有借有還)



◎Modified Deficit Round Robin(MDRR)


當我們使用MDRR當成佇列策略時,非空的佇列會以輪流的方式(round-robin fashion)被一個接著一個被服務(發送出去)。每當一個佇列被服務時,一個固定數量的資料從佇列中被送出離開。這個演算法接著再去服務下一個佇列。當某佇列被服務時,MDRR會將被送出佇列的資料位元超出所設定數值的數量記錄下來。下一次,當該佇列被再度服務時,較少的資料會被送出佇列用以補償之前服務超過的資料數量。最後,每個佇列被送出的平均資料數量將會趨近於所設定的數值。附帶一說,MDRR中擁有一個可以被優先服務的優先佇列(Priority Queue)。

在每個MDRR的佇列中定義了兩個變數:

Quantum value – 這是每一輪被服務的平均位元數量。
Deficit counter – 這是用來紀錄每一輪中各佇列被傳送出去的位元數量。初始值等於Quantum value。

只要Deficit counter大於0,在佇列中封包就會被服務。每個封包被服務之後就會將Deficit counter減去封包的位元長度。當deficit counter變成0或是負數之後,該佇列就無法再被服務。在每一次新的循環中,每個非空佇列的deficit counter會被加上各個佇列的quantum value。

附註:總而言之,佇列的quantum size必定不可小於介面的maximum transmission unit (MTU)。這可確保在排程上每個非空佇列至少會服務一個以上的封包。

每個MDRR佇列可以被指定一個相對性的權重(weight),在一個群組中其中一個佇列被定義成一個優先佇列(Priority Queue)。當介面發生擁塞時,這個權重指派了每個佇列相對的可用頻寬。如果在佇列中有資料需要被傳送的話,MDRR演算法將會從每個佇列中以輪流的方式送出資料。

如果所有的標準MDRR佇列中都有資料的話,它們將會以下列方式被服務:

0-1-2-3-4-5-6-0-1-2-3-4-5-6...

在每一個循環週中,佇列可以被發送根據它所設定權重(weight)的位元數量(byte count/quantum)。在Engine 0和Engine 2的介面模板上,數量1就等於給予介面一個相當於它MTU長度的權重(weight)。每增量超過1時,佇列的權重就增加512個位元。比方如,如果特定介面的MTU長度為4470,佇列的權重被設定為3,每次通過循環時,4470 + (3-1)*512 = 5494位元將會被允許發送出去。如果兩個正常的DRR佇列,Q0和Q1,被使用時,Q0被設定的權重為1而Q1被設定的權重為9。如果兩個佇列都發生生擁塞,每次循環週期中,Q0將被允許傳送4470位元,而Q1將會被允許傳送[4470 + (9-1)*512] = 8566位元。這將使得Q0中的流量使用將近1/3的頻寬,Q1中的流量使用約2/3的頻寬。

Comments

Popular posts from this blog

L2TPv3 Enables Layer 2 Services for IP Networks

TCP/IP 明確擁塞通知 (ECN)

Q-in-Q(Dot1Q Tunnel) Sample Configuration