Max-min fairness 演算法

好讀版：https://jackkuo.org/post/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÷4=2.5

個資源。

因此：

1. 用戶 #1 獲得 1 個資源，剩下 1.5 個資源，因此把這 1.5 的資源平分給剩餘三人，每人可以得到 2.5+(1.5÷3)=3。
2. 用戶 #2 獲得 2 個資源，剩下 1 個資源，因此把資源再分給剩下的人，剩餘每人可以分得 3+(1÷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.6 與 1.3。
4. 用戶 #3 可以獲得 2+2.6=4.6 的資源。
5. 用戶 #4 可以獲得 1+1.3=2.3 的資源。

補充

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