介紹
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.5 個資源，因此把這 1.5 的資源平分給剩餘三人，每人可以得到 $2.5 + (1.5 \div 3) = 3$。
- 用戶 #2 獲得 2 個資源，剩下 1 個資源，因此把資源再分給剩下的人，剩餘每人可以分得 $3 + (1 \div 2) = 3.5$。
- 用戶 #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 獲得 2 個資源，會剩下 4 個資源。
- 用戶 #2 獲得 3 個資源，剩下 0 個資源。
- 用戶 #3 跟 #4 都沒有完全滿足，這時剛好剩下 4 個資源，因此按照 #3 與 #4 的權重來分配，分別配到 $2.\overline{6}$ 與 $1.\overline{3}$。
- 用戶 #3 可以獲得 $2+2.\overline{6} = 4.\overline{6}$ 的資源。
- 用戶 #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