最近自己研究了下多路徑路由技術(shù)，一來和一個(gè)項(xiàng)目相關(guān)本慕，提前預(yù)熱，為以后專業(yè)知識(shí)打基礎(chǔ)悠轩，二來培養(yǎng)自己一個(gè)新領(lǐng)域快速學(xué)習(xí)和總結(jié)能力间狂。

目前網(wǎng)絡(luò)中路由方案大多為單路徑路由，基于給定限制尋找一條最優(yōu)路徑火架，只有該路徑失效時(shí)才會(huì)重新計(jì)算或者選用備用路徑鉴象，這種做法有以下三個(gè)不足：

• 大部分情況下其他多數(shù)路徑都處于空閑狀態(tài)，不能很好地利用網(wǎng)絡(luò)資源
• 當(dāng)數(shù)據(jù)量較大時(shí)何鸡，容易造成網(wǎng)絡(luò)擁塞
• 不能很好實(shí)現(xiàn)業(yè)務(wù)驅(qū)動(dòng)網(wǎng)絡(luò)纺弊，由于業(yè)務(wù)對(duì)網(wǎng)絡(luò)要求不同，如帶寬骡男、時(shí)延淆游、丟包率等，但單路徑路由不會(huì)進(jìn)行區(qū)分服務(wù)隔盛。
  本文主要介紹一下兩方面的內(nèi)容犹菱，一是目前主流用到的多路徑技術(shù)，包括ECMP吮炕、WCMP腊脱、OSPF-OMP，二是學(xué)術(shù)界比較有影響的多路徑思路

ECMP總結(jié)：

ECMP（等價(jià)多路徑）是一種路由技術(shù)龙亲，實(shí)現(xiàn)將數(shù)據(jù)包在不同的路徑上傳輸陕凹，原理相對(duì)簡(jiǎn)單，首先計(jì)算出網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)的最短路徑鳄炉，如果有多條等價(jià)最短路徑杜耙，則進(jìn)行負(fù)載均衡，這也是ECMP最大局限性所在拂盯，表現(xiàn)為：首先在一個(gè)網(wǎng)絡(luò)中佑女，等價(jià)最短路徑限制太強(qiáng)，再者將流量平均分配到不同路徑上沒有考慮到網(wǎng)絡(luò)實(shí)際能力磕仅，比如兩條等價(jià)最短路徑若帶寬不對(duì)稱珊豹，平均分配流量可能造成一條鏈路擁塞而另一條相對(duì)空閑。

ECMP具體實(shí)現(xiàn)過程

ECMP基于hash算法榕订，主要包括以下步驟
1、 key值的生成蜕便。路由器選擇數(shù)據(jù)包的一個(gè)頭部字段（如源地址劫恒、目的地址等）通過hash算法得到一個(gè)鍵值key。
2、 查找hash表两嘴，看該鍵值落在哪個(gè)具體丛楚，該區(qū)域?qū)?yīng)的下一跳就是該數(shù)據(jù)轉(zhuǎn)發(fā)的下一個(gè)目的地。
假如說找到四條等價(jià)最短路徑憔辫，即有四個(gè)下一跳可供選擇趣些，分配的表大小為keyspace.size，則每個(gè)下一跳負(fù)責(zé)的區(qū)域大小為

         regionsize = keyspace.size / #{nexthops}  

區(qū)域序號(hào)為：

         region = key / regionsize;

由此找出了對(duì)應(yīng)的下一跳地址贰您。
值得注意的是坏平，ECMP只是實(shí)現(xiàn)了粗粒度的控制，每個(gè)流走的路徑是一樣的锦亦，不存在數(shù)據(jù)包重新排序問題,細(xì)粒度的負(fù)載均衡是基于數(shù)據(jù)包舶替。值得進(jìn)一步思考的是當(dāng)端口失效或者新加一條通路時(shí)重排序問題。在文獻(xiàn)[1]中有提到杠园。ECMP原理在OSPF中使用顾瞪。

WCMP

Weighted Cost Multipathing ,為了解決數(shù)據(jù)中心流量負(fù)載均衡問題而提出[2]，主要針對(duì)ECMP存在的問題進(jìn)行了改善

Paste_Image.png

如圖抛蚁，簡(jiǎn)單解釋下陈醒，將數(shù)據(jù)從S10發(fā)送到S12，利用ECMP瞧甩，即流量在各個(gè)出口鏈路上平均分配钉跷，但實(shí)際到S20有兩條上行鏈路而到S12只有一條下行鏈路，導(dǎo)致S20亲配，S21尘应，S22下行數(shù)據(jù)不公平，不能很好利用資源吼虎。若在各個(gè)鏈路上采取 1:1:2:2分配犬钢，即WCMP原則，實(shí)現(xiàn)流量的平均分配思灰。

WCMP實(shí)現(xiàn)原理

Paste_Image.png

0-3為ECMP等價(jià)選路玷犹，4-15為WCMP按權(quán)重分配。

multipath TCP

Paste_Image.png

同時(shí)打開多個(gè) TCP 會(huì)話洒疚，這種方式將數(shù)據(jù)分成多個(gè)部分歹颓，然后每個(gè)會(huì)話發(fā)送其中的部分。有效開放多個(gè)并行的 TCP 會(huì)話油湖，為MulTCP巍扛，在一個(gè) TCP 會(huì)話模擬多個(gè)并行的 TCP 會(huì)話的行為。這些行為為并行的 TCP 會(huì)話假設(shè)相同的端點(diǎn)幾相同的端到端網(wǎng)絡(luò)路徑乏德。一個(gè)使用多個(gè)并行會(huì)話的 TCP 進(jìn)化撤奸，但試圖通過網(wǎng)絡(luò)以多種路徑傳輸這些會(huì)話吠昭，這就是多路徑 TCP。

參考文獻(xiàn)：
[1] Hopps C E. Analysis of an equal-cost multi-path algorithm[J]. 2000.
[2] Zhou J, Tewari M, Zhu M, et al. WCMP: Weighted cost multipathing for improved fairness in data centers[C]//Proceedings of the Ninth European Conference on Computer Systems. ACM, 2014: 5.
[3] https://www.oschina.net/translate/mptcp
[4] He J, Rexford J. Toward internet-wide multipath routing[J]. IEEE network, 2008, 22(2).