Max-min fairness 演算法

介紹

Max-min fairness 是在通訊網路中針對多工、有限的資源做分配的演算法,分配方式是對較高流量或是突發的流量進行限制。

跟 FSFS (first-come first-served) 比較起來,max-min fairness 具有 traffic shaping 的優勢,也就是做速率控制,可以用來改善延遲或是減緩壅塞狀況。Fair queuing 則是一個 Max-min fairness 的例子。

這個演算法是在 1997 年時由 Srinivasan Keshav 在「An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network」中所提出。

演算法

這演算法有一些基本定義:

  • 資源需求由小到大排序
  • 用戶所得到的資源必定不能大於該用戶的需求
  • 無法滿足的用戶則平分剩餘資源

範例一(無權重)

假設有四名用戶,所需資源分別為 [1, 2, 4, 5],因此總共需要 \(1+2+4+5=12\) 個資源,但資源總共只有 10個。那麼平均每名用戶可以分到 \(10 \div 4 = 2.5\) 個資源。

因此:

  1. 用戶 #1 獲得 1 個資源,剩下 1.5 個資源,因此把這 1.5 的資源平分給剩餘三人,每人可以得到 \(2.5 + (1.5 \div 3) = 3\)
  2. 用戶 #2 獲得 2 個資源,剩下 1 個資源,因此把資源再分給剩下的人,剩餘每人可以分得 \(3 + (1 \div 2) = 3.5\)
  3. 用戶 #3 跟 #4 都無法獲取所有資源,因此都是分到 3.5 個資源。

範例二(有權重)

定義:

  • 標準化權重,將最小權重設定為 1
  • 以權重來分配資源
  • 多出的資源再以權重比例去分配

假設有四名用戶,需資源分別為 [2, 3, 8, 10],因此總共需要 \(2+3+8+10=23\) 個資源,但資源總共只有 12 個。

又,他們有權重考量,分別為 [3, 1.5, 1, 0.5],標準化後為 [6, 3, 2, 1],這時需要分配的資源權重為 \(6+3+2+1=12\)

因此:

  1. 用戶 #1 獲得 2 個資源,會剩下 4 個資源。
  2. 用戶 #2 獲得 3 個資源,剩下 0 個資源。
  3. 用戶 #3 跟 #4 都沒有完全滿足,這時剛好剩下 4 個資源,因此按照 #3 與 #4 的權重來分配,分別配到 \(2.\overline{6}\)\(1.\overline{3}\)
  4. 用戶 #3 可以獲得 \(2+2.\overline{6} = 4.\overline{6}\) 的資源。
  5. 用戶 #4 可以獲得 \(1+1.\overline{3} = 2.\overline{3}\) 的資源。

補充

  • Traffic Shaping(流量整型):主要在做速率控制,核心理念是等待,可以用來改善延遲或是可用頻寬。可能會在企業內使用,以滿足 ISP 對企業的 CIR (Committed Information Rate),例:Token Bucket
  • Traffic Policing(流量維持):核心理念是丟包。可能會在 ISP 中使用,嚴格限制流量,超過的即丟棄,例:Leaky Bucket

comments powered by Disqus