almost 8 years ago

Equal Cost Multi-Path Routing RFC2991
ECMP不是一種routing protocol,而是一種routing的策略
為了達到load balance,將流量分散在相同cost的不同路徑上,提高網路使用率,也能減少網路壅塞

Routing

因為只是一種routing策略而已,spec上對於如何尋找multi-path描述幾乎是沒有的
這個責任在routing protocol身上,OSPF, RIP或ISIS等如果要支援ECMP,自己要先能找到多條相同cost的路徑
Equal-Cost Multipath Routing in IP Networks中則有大略描述應該如何尋找多條路徑
實際上就是Dijkstra Algorithm的改良,首先先介紹single-path Dijkstra Algorithm

single-path Dijkstra pseudo code

 1 function Dijkstra(Graph, source):
 2   for each vertex v in Graph:               // Initializations
 3     dist[v] := infinity;                    // Mark distances from source to v as not yet computed
 4     visited[v] := false;                    // Mark all nodes as unvisited
 5     previous[v] := undefined;               // Previous node in optimal path from source
 6   end for
 7      
 8   dist[source]  := 0;                       // Distance from source to itself is zero
 9   insert source into Q;                     // Start off with the source node
10                                                                
11   while Q is not empty:                     // The main loop
12     u := vertex in Q with smallest distance in dist[] and has not been visited;  
13                                             // Source node in first case
14     remove u from Q;
15     visited[u] := true                      // mark this node as visited
16          
17     for each neighbor v of u:   
18       alt := dist[u] + dist_between(u, v);  // accumulate shortest dist from source
19       if alt < dist[v]:                                 
20         dist[v]  := alt;                    // keep the shortest dist from src to v
21         previous[v]  := u;
22         if !visited[v]:
23           insert v into Q;                  // Add unvisited v into the Q to be processed
24         end if
25       end if
26     end for
27   end while
28   return dist;
29 endfunction

變數

在整個演算法中,有一個distance vector(pseudo code中的dist[])
index為vertex的編號,內容存放著source到該vertex的最短距離
previous[]則代表路徑,index為vertex,內容存放的是要到達vertex的前一個點
如路徑A->B->C,則previous[C] = B, previous[B] = A
visited[]代表演算法已經處理過那些點了
Q是一個priority queue,未來要處裡的vertex都會放入Q中
優先序則是看source到vertex的距離(即dist[vertex]的值),距離越短,優先序越高
初始時只有source在Q中,之後開始演算法(line1~27)

演算法

每一次都從Q中取出優先序最高的vertex u(line12),接下來我們會針對u做處理
設定visited[u] = true(line15),代表我們已經處理過了(我們將會處理)
接著我們要計算與vertex u相鄰所有點的最短路徑(line17~26)
對於每一個vertex u的鄰居v(line 17)
我們先計算經過u到v所需要的成本alt(line18)
alt是dist[u]dist_between(u,v)的合,也就是source到u的成本(已知最小成本),加上u到v的成本
接著比較alt與dist[v]的大小(line 19),如果alt比較小,表示source到u之後,再到v的成本是目前算過最小的
那dist[v]就更新為alt(新的、更小的成本),並且設定previous[v] = u(表示要經過v,我們應該先經過u)(line 20, 21)
最後看v是否有處裡過,如果沒有處理過,就將之加入Q中,結束這次的處理

multi-path Dijkstra pseudo code

在single-path Dijkstra Algorithm中,我們比較時只會看最小成本的路徑
previous也只會記錄一個vertex
要將single-path版本改為multi-path很簡單
原則是一樣的,每次迴圈都挑出一個目前路徑成本最小的vertex u,並計算vertex u鄰居的路徑成本
不同的是,當要比較新的路徑成本(alt)和原本的路徑成本(dist[v])
如果發現路徑成本相同(alt == dist[v]),那就表示我們找到另一條成本相同路徑
就要把目前的路徑記錄起來,也就是從source,經過vertex u到達v,也是最短路徑

pseudo code如下

 1 function Multi-path Dijkstra(Graph, source):
 2   for each vertex v in Graph:               // Initializations
 3     dist[v] := infinity;                    // Mark distances from source to v as not yet computed
 4     visited[v] := false;                    // Mark all nodes as unvisited
 5     previous[v] := undefined;               // Previous node in optimal path from source
 6   end for
 7      
 8   dist[source]  := 0;                       // Distance from source to itself is zero
 9   insert source into Q;                     // Start off with the source node
10                                                                
11   while Q is not empty:                     // The main loop
12     u := vertex in Q with smallest distance in dist[] and has not been visited;  
13                                             // Source node in first case
14     remove u from Q;
15     visited[u] := true                      // mark this node as visited
16          
17     for each neighbor v of u:   
18       alt := dist[u] + dist_between(u, v);  // accumulate shortest dist from source
19       if alt < dist[v]:                     // find a shortest path
20         dist[v]  := alt;                    // keep the shortest dist from src to v
21         reset the previous[v]               // clear up the content of previous[v]
22         add u into previous[v]              // add the previous vertex u into previous[v]
23       else if alt == dist[v]:               // find another path that cost = dist[v]
24         add u into previous[v]
25       endif
26         if !visited[v]:
27           insert v into Q;                  // Add unvisited v into the Q to be processed
28         end if
29       end if
30     end for
31   end while
32   return dist;
33 endfunction

變數

與single-path版本不同,由於multi-path版本需要紀錄多條路徑
因此previous[]不再是一個一維陣列,而應該要用一個table來記錄
previous[v]中就記錄著想要到達vertex v,你可以走哪幾個vertex,其cost都是最短的

演算法

演算法大致與single-path相同,更動的地方僅有判斷成本的地方(line 19~25)
altdist[v]比較中,如果alt < dist[v](line 19),就表示我們找到更短的路徑
那麼應該要將previous[v]的內容清空,之後加把vertex u加進去(line 20, 21)
而如果alt == dist[v](line 23),就表示我們找到另一條成本相同的最短路徑
那就只要將vertex u加入previous即可

Decision

了解如何找多條路徑以後,接著就是要分配路徑
分配路徑的方法可能有很多種,spec上提到了三種
Round-Robin(RR)、Random、Hash
RR就是用輪詢的方式將封包送往不同的路徑上
Random就是將封包送往隨機一個路徑上
Hash則是將封包的header欄位做hash,來決定要送往哪條路徑

對於RR與Random方法雖然可以達到load-balancing,但是可能會出現一些問題
因為做RR(或Random)的對象是封包,因此對於相同目的地的數個封包可能會走不同的路徑
不同路徑上的傳送時間會不同(即使是相同成本)
這樣的情況可能會造成封包re-ordering,如此對於TCP的損傷就會很大,得到的流量可能不會變大,反而會變小
基於這個原因,一般要使用ECMP,不建議用packet來做分流的對象,而會使用flow來做對象

flow的定義會根據實作的不同而有所不同
flow可能只是destination address
也有可能是(source address, destination address),或者(source address, destination address, protocol id)
而基於flow來做的hash方法,spec也提供三種

  1. Modulo-N Hash
    將flow做hash之後,對N條路徑取餘數,其餘數R就代表該flow要走第R條路徑
    舉例來說,目前hash function所產生的值是0~14,目前共有3條不同路徑a, b, c
    a路徑的代表值為0
    b路徑的代表值為1
    c路徑的代表值為2
    當有個flow的hash值為8時,就計算8%2,得出0,因此走a路徑

    此方法好處是簡單好實作,缺點則是當有路徑新增或減少時,需要改變路徑的flow可能會很多
    這是因為每一個flow都直接對應到一個路徑,當新增或減少一條路徑時
    同樣的flow取出來的餘數可能就會改變,因此要改變原本的路徑

  2. Hash Threshold
    Hash Threadhold改進了Modulo-N Hash的缺點
    每一個flow同樣會有一個hash值
    但每一條路徑不再是代表一個值,而是代表一個值的範圍
    在判斷某個flow要走哪條路徑時,只要看該flow的hash值落在哪條路徑的範圍上即可
    舉例來說,目前hash function所產生的值是0~14,目前共有3條不同路徑a, b, c
    a路徑的值範圍就是[0,4]
    b路徑的值範圍就是[5,9]
    c路徑的值範圍就是[10,14]
    當要決定一個flow要走哪條路時,先算出flow的hash值,假設是8
    再去判斷值落在哪個範圍內,比較過後發現8落在b徑的範圍內
    此條flow就會走b路徑

    這樣的方法好處是當有路徑新增或減少時,需要改變路徑的flow數量較少(只有hash值在邊界的flow需要改變)

  3. Highest Random Weight (HRW)
    此作法和前兩個不太相同
    做hash的對象不只是flow的特徵,還要加上路徑的下一個點的ip address
    對於N條不同的路徑,我們需要計算N個不同的hash值
    並且在這些值中挑選出最大的值,其所屬的路徑就是此flow要走的路徑
    例如三條路徑a, b, c
    a路徑下一個點的ip address IPA
    b路徑下一個點的ip address IPB
    c路徑下一個點的ip address IPC
    則我們需要分別算出hash(flow, IPA) = HVA, hash(flow, IPB) = HVB, hash(flow, IPC) = HVC
    之後再比較HVA, HVB, HVC的大小
    假如HVA最大,則此條flow就走a路徑

    當有路徑新增或減少時,此方法能夠更好的減少flow的改變,但缺點就是對於同樣的flow,需要計算多次才能決定路徑

← floodlight module基本 Linux Command →