基于二維路由的流量工程解決方案

耿 男，楊 芫，徐明偉

(清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系, 北京 100084)

0 引 言

隨著互聯(lián)網(wǎng)的高速發(fā)展，網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)中的數(shù)據(jù)流量也迅速增加，給網(wǎng)絡(luò)帶來了巨大的壓力和挑戰(zhàn)。單純地進(jìn)行硬件升級不僅難以解決負(fù)載不均衡的問題，而且還造成了極大的資源浪費(fèi)和升級費(fèi)用[1]，流量工程(traffic engineering)成為解決互聯(lián)網(wǎng)高速發(fā)展所帶來壓力的更有效途徑。流量工程可以進(jìn)行流量控制，解決負(fù)載不均衡、網(wǎng)絡(luò)資源利用率低、時(shí)延長等問題，還可以預(yù)留鏈路帶寬資源應(yīng)對網(wǎng)絡(luò)故障和突發(fā)流量。流量工程提升了網(wǎng)絡(luò)性能，提高了網(wǎng)絡(luò)服務(wù)提供商的服務(wù)質(zhì)量，從而也提升了用戶體驗(yàn)。

當(dāng)前流量工程受限于對網(wǎng)絡(luò)流量的認(rèn)識和當(dāng)前的路由技術(shù)。對于前者，網(wǎng)絡(luò)中各條鏈路的流量狀況對流量工程進(jìn)行流量調(diào)度有很大的影響，在知曉哪些鏈路擁堵、哪些鏈路空閑、哪些數(shù)據(jù)流是造成網(wǎng)絡(luò)擁堵的主因等這些信息后，才能做出最為恰當(dāng)?shù)牧髁空{(diào)度決策。然而，統(tǒng)計(jì)網(wǎng)絡(luò)中的流量信息面臨著很多困難，如準(zhǔn)確性、統(tǒng)計(jì)開銷等。因而很多研究工作提出了各自的流量工程方案來應(yīng)對這一挑戰(zhàn)，如大流測量等。實(shí)際上，網(wǎng)絡(luò)中大流特征十分明顯，少數(shù)的幾條大流占據(jù)了絕大部分的鏈路流量，且持續(xù)時(shí)間長，非常適合流量調(diào)度。

對于后者，流量工程的實(shí)施必須受限于已有的路由技術(shù)。比如基于目的地址轉(zhuǎn)發(fā)、流量不分流等。有一類工作在現(xiàn)有的約束條件下設(shè)計(jì)合理的方案進(jìn)行流量工程，如帶約束的優(yōu)化、基于地址分塊的流量拆分；另外，還有一類工作則是在原始路由技術(shù)的基礎(chǔ)上用較低的開銷進(jìn)行改造，實(shí)現(xiàn)更為細(xì)粒度和靈活的流量控制，如多維路由。不過多維路由面臨著轉(zhuǎn)發(fā)表空間膨脹，可擴(kuò)展性差等問題。

事實(shí)上，上述2個(gè)挑戰(zhàn)是相互獨(dú)立的，很多解決方案也是可以通過一定方式進(jìn)行組合的，實(shí)現(xiàn)優(yōu)勢互補(bǔ)。

二維路由(two-dimensional IP routing)[2]作為多維路由的一種，在進(jìn)行路由決策和轉(zhuǎn)發(fā)數(shù)據(jù)報(bào)文的時(shí)候不僅考慮目的地址，同時(shí)還要考慮源地址。本文中我們提出了二維路由大流調(diào)度方案，并結(jié)合大流測量技術(shù)建立了二維路由優(yōu)化模型，然后提出了隨機(jī)算法求得優(yōu)化問題的近似解。該方案不僅實(shí)現(xiàn)了網(wǎng)絡(luò)流量細(xì)粒度的靈活控制，而且還具有很好的可擴(kuò)展性以及更低的多維流表開銷。我們通過實(shí)驗(yàn)證明方案的可行性，并通過仿真實(shí)驗(yàn)證明，二維路由比傳統(tǒng)路由方式具有更好的流量工程效果，并且二維路由方案已接近最優(yōu)方案，不需要額外的維度進(jìn)行流量控制。

1 流量工程主要挑戰(zhàn)和相關(guān)研究

1.1 流量矩陣測量挑戰(zhàn)

流量矩陣也即任意2個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)之間鏈路上流統(tǒng)計(jì)信息的集合，如流量大小。很多流量工程方案[3-4]的實(shí)施需要測量或估計(jì)網(wǎng)絡(luò)的流量矩陣，從而根據(jù)網(wǎng)絡(luò)狀況制定合適的調(diào)度方案，因而流量矩陣測量的準(zhǔn)確性會對流量工程的效果產(chǎn)生直接的影響。很多研究工作[5-6]都是在假設(shè)流量矩陣已知的前提下進(jìn)行的。盡管測量網(wǎng)絡(luò)流量矩陣的方案有很多[7]，但是測量結(jié)果誤差仍然接近20%[8]，主要就是因?yàn)殒溌飞蠑?shù)據(jù)流量在實(shí)時(shí)變化，并且難以預(yù)測。除此之外，在現(xiàn)有設(shè)備上測量鏈路流量所帶來的開銷也為基于流量矩陣的流量工程增添了很多阻礙。

1.1.1 非流量感知路由

非流量感知路由可以在流量矩陣測量不準(zhǔn)確、網(wǎng)絡(luò)流量時(shí)刻變化的情況下，實(shí)現(xiàn)魯棒的流量工程。文獻(xiàn)[9]提出了一種最優(yōu)靜態(tài)路由的方式，其將最小化最大鏈路利用率作為流量工程的優(yōu)化目標(biāo)。對于給定的網(wǎng)絡(luò)拓?fù)?，此時(shí)存在一個(gè)最優(yōu)路由方式rD對應(yīng)的最大鏈路利用率(maximum link utilization，MLU)為MLU(D,rD)，靜態(tài)路由方式r對應(yīng)的最大鏈路利用率為MLU(D,r)，其中，D為任意流量需求，亦即流量矩陣。定義性能比α為各種流量矩陣D下MLU(D,r)與MLU(D,rD)的最大比值，最優(yōu)靜態(tài)路由的優(yōu)化目標(biāo)就是最小化這一比值。文獻(xiàn)[10]研究表明，在其實(shí)驗(yàn)拓?fù)湎拢瑢τ谌我饬髁烤仃?，存在一種靜態(tài)路由方式使得性能比α不超過2。不過文獻(xiàn)[9-10]這種非流量感知的路由方式具有自己的局限性，首先單純基于目的地址進(jìn)行流量調(diào)度效果并不好，基于源和目的地址進(jìn)行流調(diào)度[11]粒度更細(xì)、效果更優(yōu)，其次求解最優(yōu)路由需要解大型線性規(guī)劃問題，復(fù)雜度高，可擴(kuò)展性一般，最后，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)或鏈路發(fā)生故障的時(shí)候需要進(jìn)行重路由，開銷較大。

1.1.2 高效的流量測量

實(shí)際網(wǎng)絡(luò)鏈路中的數(shù)據(jù)流量其實(shí)是由極少數(shù)的大流(通常稱為elephant flow或者large flow)主導(dǎo)的[12]。這類大流數(shù)目很少，但是數(shù)據(jù)量很大，而且持續(xù)時(shí)間通常較長。顯然這些大流非常適合進(jìn)行流量調(diào)度，開銷小，調(diào)度效果仍有保證，而且調(diào)度策略的時(shí)效性長。僅僅測量網(wǎng)絡(luò)中的大流信息，對于測量誤差和鏈路狀況變動都具有更高的容忍性。

文獻(xiàn)[13]提出的ICE-Buckets(independent counter estimation buckets)算法實(shí)現(xiàn)了基于per-flow的低誤差率大流測量；文獻(xiàn)[14]提出了一種利用緩存輔助的大流測量方案CASE(cache-assisted stretchable estimator)，能夠?qū)崿F(xiàn)300 Gbit/s的吞吐量和低誤差率；文獻(xiàn)[15]提出了2個(gè)方案，分別是CSS(compact space-saving)和WCSS(window compact space-saving)。CSS對經(jīng)典方法space-saving[16]進(jìn)行了改進(jìn)，消除了大量指針操作并減少了75%的存儲空間；WCSS結(jié)合了CSS和滑動窗口策略，能夠周期性更新大流統(tǒng)計(jì)信息。

基于大流進(jìn)行流量調(diào)度的工作有很多，其應(yīng)用場景以數(shù)據(jù)中心為主。Hedera[17]使用OpenFlow協(xié)議通過交換機(jī)獲得數(shù)據(jù)統(tǒng)計(jì)信息，然后通過近似算法放置大流，實(shí)驗(yàn)結(jié)果顯示，這種集中式的大流調(diào)度方案能起到有效的流量調(diào)度效果。Mahout[18]和MicroTE(micro traffic engineering)[19]與Hedera不同，它們在主機(jī)上獲得統(tǒng)計(jì)信息，降低了測量大流信息的開銷，實(shí)現(xiàn)了另一種基于大流的流量工程。

1.2 路由設(shè)備轉(zhuǎn)發(fā)控制能力挑戰(zhàn)

路由設(shè)備轉(zhuǎn)發(fā)控制能力是制約流量工程效果的另一重要因素。這里路由設(shè)備轉(zhuǎn)發(fā)控制能力是指流量工程中路由設(shè)備對網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)控制的粒度。盡管互聯(lián)網(wǎng)是基于分組進(jìn)行數(shù)據(jù)傳輸?shù)?，但是流量工程中進(jìn)行分組級別的調(diào)度在技術(shù)上是難以實(shí)現(xiàn)的。在傳統(tǒng)網(wǎng)絡(luò)的路由設(shè)備中，一般是基于目的IP地址進(jìn)行數(shù)據(jù)報(bào)文的轉(zhuǎn)發(fā)，當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)，路由器會根據(jù)數(shù)據(jù)包的目的IP地址在轉(zhuǎn)發(fā)表中匹配相應(yīng)的轉(zhuǎn)發(fā)表項(xiàng)，然后依據(jù)下一跳指令執(zhí)行轉(zhuǎn)發(fā)操作。在進(jìn)行流量工程時(shí)，可以配置一些靜態(tài)路由改變轉(zhuǎn)發(fā)策略。實(shí)際上，數(shù)據(jù)包包頭包含了很多信息(源地址、目的地址、源端口號、目的端口號等)，這些字段能夠支持更加細(xì)粒度的流量調(diào)度，獲得更好的流量工程效果。細(xì)粒度的流量工程已經(jīng)成為當(dāng)前互聯(lián)網(wǎng)的重要需求[20]，不過，在傳統(tǒng)設(shè)備上實(shí)施細(xì)粒度的流量工程開銷很大，因而路由設(shè)備的轉(zhuǎn)發(fā)控制能力一定程度上制約了流量工程的實(shí)施。

1.2.1 帶約束的優(yōu)化

很多工作將路由和轉(zhuǎn)發(fā)機(jī)制的種種限制作為約束加入到流量工程的優(yōu)化模型當(dāng)中，例如流量不可拆分、基于目的地址轉(zhuǎn)發(fā)等。這些優(yōu)化模型加上約束后通常由普通的線性規(guī)劃變?yōu)?混合)整數(shù)規(guī)劃，直接求解這類優(yōu)化問題十分困難，通常會選擇一些啟發(fā)式的方法求得問題的近似解。文獻(xiàn)[21]提出DEFT(distributed exponentially-weighted flow splitting)方案，其將鏈路權(quán)值和鏈路流量均作為變量加入到流量分割模型中，然后通過一種二階段迭代的方式求得接近最優(yōu)的近似解，實(shí)現(xiàn)負(fù)載均衡。文獻(xiàn)[22]提出在軟件定義網(wǎng)絡(luò)(software defined network，SDN)在增量部署的情況下，利用其集中控制的特性收集全網(wǎng)信息，建立線性規(guī)劃方程求解?？傮w而言，使用帶約束的優(yōu)化方式進(jìn)行流量工程，如何保證求解方案接近最優(yōu)且保持低開銷是每個(gè)工作都要考慮的問題。

1.2.2 基于地址塊拆分流量

基于地址塊拆分流量最簡單、最常見的方式是基于哈希的等價(jià)多路徑(equal-cost multi-path，ECMP)，即將數(shù)據(jù)流通過五元組哈希的方式分散到多條等價(jià)路徑上，之后又有人提出了加權(quán)成本多路徑(weighted cost multi-path，WCMP)處理帶有特定權(quán)值的流分割需求。文獻(xiàn)[23]提出了Niagara方法，基于源地址或者目的地址進(jìn)行流量拆分。一個(gè)簡單的例子，假如我們要將某鏈路流量按照1∶3∶4的比例拆分到3條路徑上去，可以設(shè)置地址塊對應(yīng)相應(yīng)的轉(zhuǎn)發(fā)表項(xiàng)，比如3條轉(zhuǎn)發(fā)表項(xiàng)分別是目的地址為*000的流去往路徑1且具有高優(yōu)先級；目的地址為*0的流的去往路徑2且具有低優(yōu)先級；目的地址為*1的流去往路徑3且具有低優(yōu)先級。這種基于地址塊的分流方式，可以大大縮減流表存儲空間，實(shí)驗(yàn)表明，Niagara只需要原始流表數(shù)的1.2%～37%。不過，該方法與ECMP共有的局限性在于無法依據(jù)流量在地址塊上的分布進(jìn)行流量分割，可能會造成實(shí)際分割的流量比例與預(yù)期的分流比例相差較大。

1.2.3 多維路由

如果數(shù)據(jù)流的轉(zhuǎn)發(fā)不僅僅通過目的地址進(jìn)行控制，而且還支持源地址、端口號、協(xié)議號等域值的匹配，那么這種路由方式就是多維路由。多維路由能夠?qū)崿F(xiàn)細(xì)粒度的流量控制，達(dá)到更靈活、高效的流量工程效果，但需要路由和轉(zhuǎn)發(fā)機(jī)制的支持。

多協(xié)議標(biāo)簽交換(multi-protocol label switching，MPLS)[24]可以在端到端之間建立隧道，支持源和目的IP地址、源和目的端口號、協(xié)議號等多個(gè)維度，然而MPLS配置復(fù)雜，開銷大，難以跨域，流量的變動會使隧道性能大大降低，因而MPLS并未在全球廣泛部署。SDN的OpenFlow協(xié)議為轉(zhuǎn)發(fā)表項(xiàng)提供了40多個(gè)匹配域，流量控制粒度很細(xì)?；赟DN的分流方式也有很多，如MicroTE[19]等方式，它們通過控制器下發(fā)流表規(guī)則進(jìn)行細(xì)粒度的分流。不過，這種多維流表的方式勢必會造成轉(zhuǎn)發(fā)表空間的爆炸，目前SDN交換機(jī)支持的流表數(shù)目只有上萬條，而主干網(wǎng)目的地址轉(zhuǎn)發(fā)表項(xiàng)就已經(jīng)超過了60萬條，而且已有的多維流表壓縮方案也并不能從根本上解決該問題[25]。因而盡管SDN在細(xì)粒度的流量工程方面存在著很大的便利性，但是要想大規(guī)模部署仍然面臨著很大的阻礙。文獻(xiàn)[2]提出了二維路由策略，在傳統(tǒng)路由方式的基礎(chǔ)上只增加了一個(gè)維度，即路由轉(zhuǎn)發(fā)決策不僅僅依賴于目的地址，也依賴于源地址。

2 二維路由方案介紹

2.1 二維路由概念與特點(diǎn)

二維路由是多維路由的一種，與傳統(tǒng)路由相比，二維路由在目的地址的維度基礎(chǔ)上又增加了源地址的維度。從控制層面來講，路由器在進(jìn)行路由決策的時(shí)候，不僅考慮目的地址，而且還要考慮源地址，也就是說，具有相同目的地址不同源地址的報(bào)文可能具有不同的下一跳。從數(shù)據(jù)層面上來講，轉(zhuǎn)發(fā)表項(xiàng)中需要加入源地址匹配字段，參與轉(zhuǎn)發(fā)匹配。顯然源地址的加入使得路由轉(zhuǎn)發(fā)設(shè)備對流量的控制粒度更加細(xì)化，在進(jìn)行流量工程的時(shí)候可以有更加靈活的選擇。

若將傳統(tǒng)網(wǎng)絡(luò)和SDN分別看做維度上的2個(gè)極端，那么二維路由則是二者的折中，并且更加傾向于傳統(tǒng)網(wǎng)絡(luò)。這就使得二維路由具有很多優(yōu)質(zhì)的特性：①二維路由實(shí)現(xiàn)了細(xì)粒度的轉(zhuǎn)發(fā)控制，能夠?qū)崿F(xiàn)更加靈活的流量工程策略；②二維路由是基于傳統(tǒng)路由協(xié)議改造的，因而具有很多傳統(tǒng)網(wǎng)絡(luò)的特性，如魯棒性、可擴(kuò)展性等，支持增量部署[26]；③二維路由相比于SDN，具有更少的維度，實(shí)際上2個(gè)維度已經(jīng)足夠?qū)崿F(xiàn)高效的流量工程，并且大大減少三態(tài)內(nèi)容尋址存儲器(ternary content addressable memory，TCAM)空間的消耗，支持更大規(guī)模的網(wǎng)絡(luò)；④二維路由是一種思想，它還可以靈活地與其他流量工程技術(shù)相結(jié)合，實(shí)現(xiàn)更好的流量調(diào)度效果。

2.2 二維路由大流調(diào)度方案

由1.1.2可知，單純調(diào)度大流就可以實(shí)現(xiàn)較好的流量工程效果，由于大流數(shù)目很少，因而在二維路由中只需要很少的二維轉(zhuǎn)發(fā)表項(xiàng)即可，開銷很小，且策略有效性持續(xù)較長。綜上，基于大流的二維路由進(jìn)一步增強(qiáng)了方案的可擴(kuò)展性。

二維路由應(yīng)用的場景一般是傳統(tǒng)的企業(yè)網(wǎng)或廣域網(wǎng)，本文提出的二維路由大流調(diào)度方案是基于開放最短路徑優(yōu)先(open shortest path first，OSPF)協(xié)議的系統(tǒng)設(shè)計(jì)，硬件設(shè)備是傳統(tǒng)的路由設(shè)備，二維轉(zhuǎn)發(fā)表使用的是訪問控制列表(access control list，ACL)。

二維路由大流調(diào)度系統(tǒng)主要由3部分組成：分別為大流測量；集中路徑計(jì)算；轉(zhuǎn)發(fā)決策下發(fā)和執(zhí)行。

2.2.1 大流測量

由于傳統(tǒng)路由設(shè)備不能像OpenFlow交換機(jī)那樣具有數(shù)據(jù)統(tǒng)計(jì)功能，因而不能直接進(jìn)行流量統(tǒng)計(jì)，更不能進(jìn)行大流統(tǒng)計(jì)。文獻(xiàn)[13-15]已經(jīng)提出了線速、準(zhǔn)確、低開銷的大流測量方案，本文并沒有提出新的大流測量方案，而是直接采用了文獻(xiàn)[15]中的一種設(shè)計(jì)方案進(jìn)行大流測量。

大流測量需要執(zhí)行大流檢測算法，并且需要將統(tǒng)計(jì)數(shù)據(jù)匯報(bào)給集中路徑計(jì)算單元。一種直接的方式是將大流檢測算法放到路由設(shè)備上執(zhí)行，但是這樣會給路由器帶來很大的負(fù)擔(dān)；另一種方式是在路由設(shè)備間添加一個(gè)新的測量設(shè)備，然而這種方式會帶來一定的時(shí)延，還有一種方式是通過交換機(jī)鏡像將鏈路上的數(shù)據(jù)流導(dǎo)入到一臺測量設(shè)備上進(jìn)行大流檢測。本文采用的是最后一種方法。

2.2.2 集中路徑計(jì)算

本方案需要一個(gè)路徑計(jì)算單元，能夠收集測量設(shè)備統(tǒng)計(jì)的流信息，進(jìn)行大流調(diào)度的計(jì)算。本文中，我們根據(jù)二維大流調(diào)度場景，提出了一個(gè)專門針對該場景的數(shù)學(xué)優(yōu)化模型，并修改了隨機(jī)取整算法[27]求得優(yōu)化模型的近似解。

2.2.3 轉(zhuǎn)發(fā)決策下發(fā)和執(zhí)行

路徑計(jì)算單元計(jì)算得到大流的調(diào)度決策，需要將轉(zhuǎn)發(fā)決策下發(fā)到路由器執(zhí)行生成相應(yīng)的二維轉(zhuǎn)發(fā)表。本文仍舊采用OSPF(open shortest path first)中基于最短路徑的路徑計(jì)算方式，令每一臺路由器不僅維持一個(gè)正常的鏈路權(quán)值矩陣，還要維持一組針對每一條大流的調(diào)度鏈路權(quán)值矩陣。每一個(gè)調(diào)度鏈路權(quán)值矩陣的最短路徑計(jì)算結(jié)果正好是該大流的調(diào)度路徑，該過程很容易通過簡單算法實(shí)現(xiàn)。路徑計(jì)算單元計(jì)算出這些調(diào)度鏈路權(quán)值矩陣之后，通過類似文獻(xiàn)的鏈路狀態(tài)通告(link-state advertisement，LSA)擴(kuò)展方案，將權(quán)值信息通告給全網(wǎng)，路由器收到擴(kuò)展LSA之后對相應(yīng)的調(diào)度鏈路權(quán)值矩陣執(zhí)行最短路徑算法生成二維轉(zhuǎn)發(fā)表配置到ACL中。當(dāng)數(shù)據(jù)包到達(dá)的時(shí)候，路由器優(yōu)先匹配ACL中的二維轉(zhuǎn)發(fā)表，然后匹配傳統(tǒng)的轉(zhuǎn)發(fā)表。

2.3 二維大流調(diào)度模型和求解算法

2.3.1 二維路由大流調(diào)度模型

minφ=max{ue,?e:(u,v)∈E}

(1)

subject to:

?e:(u,v)∈E

(2)

(3)

(4)

fe+be≤ce,?e:(u,v)∈E

(5)

(6)

(7)

2.3.2 優(yōu)化模型求解

上述優(yōu)化問題屬于一種0-1整數(shù)規(guī)劃問題，容易證明其屬于NP-hard問題，并不能在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解。

需要注意的是上述模型并沒有強(qiáng)調(diào)二維路由，也就是該模型同樣適用于傳統(tǒng)路由。二維路由與傳統(tǒng)路由的差異體現(xiàn)在大流需求i的定義上，使用二維路由，可以將基于目的地址的大流分割為較小的子流，從而更加細(xì)粒度的控制流量。

2.4 真實(shí)實(shí)驗(yàn)和仿真實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

2.4.1 真實(shí)實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析

本文實(shí)現(xiàn)了一個(gè)二維路由大流調(diào)度的系統(tǒng)原型：①依照文獻(xiàn)[15]實(shí)現(xiàn)了測量大流和背景流的測量算法，并部署到一臺計(jì)算機(jī)上；②在另一臺筆記本上實(shí)現(xiàn)了路徑計(jì)算單元，通過2.3.2節(jié)中所提算法求得調(diào)度路徑，然后轉(zhuǎn)換成調(diào)度鏈路矩陣權(quán)值，通過擴(kuò)展LSA告知路由器；③修改了Quagga代碼，使其識別擴(kuò)展LSA并能進(jìn)行二維路由轉(zhuǎn)發(fā)路徑的計(jì)算和轉(zhuǎn)發(fā)表(access control list,ACL)生成。

使用9臺真實(shí)路由器搭建了Abilene研究網(wǎng)絡(luò)，每個(gè)鏈路容量為1 Gbit/s，鏈路權(quán)值均設(shè)為50。使用交換機(jī)將關(guān)鍵鏈路的流量鏡像到測量設(shè)備上。測量設(shè)備與路徑計(jì)算單元通過socket建立連接。

本文通過一個(gè)簡單案例驗(yàn)證了該系統(tǒng)的反應(yīng)時(shí)間，實(shí)驗(yàn)結(jié)果如圖1所示。首先我們使用iperf在每條鏈路上產(chǎn)生150 Mbit/s的背景流量，然后在t=0 s時(shí)刻，在Denver節(jié)點(diǎn)使用iperf產(chǎn)生一條100 Mbit/s的去往New York節(jié)點(diǎn)的UDP(user datagram protocol)流，并通過link 1。在t=2 s時(shí)，產(chǎn)生一條除源地址外都相同的流。由圖1可以發(fā)現(xiàn)，其中一條流在0.2 s內(nèi)調(diào)度到了link 2上，因而在該案例中，可知該系統(tǒng)能夠?qū)崿F(xiàn)較快的流量調(diào)度。

圖1 大流調(diào)度實(shí)驗(yàn)結(jié)果Fig.1 Experiment results of large flow scheduling

2.4.2 仿真實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析

實(shí)驗(yàn)拓?fù)溥x取Rocket fuel公開的網(wǎng)絡(luò)拓?fù)鋷?，如?所示，AS表示拓?fù)渌鶎僮灾斡蛳到y(tǒng)。拓?fù)涞逆溌窓?quán)值使用公開數(shù)據(jù)庫中提供的數(shù)值，鏈路容量依照下面規(guī)則給出：若鏈路兩端節(jié)點(diǎn)的度都大于5，則鏈路容量為9 953 Mbit/s，否則鏈路容量為2 488 Mbit/s。

表1 Rocketfuel拓?fù)銽ab.1 Rocketfuel topologies

通過對Caida(the cooperative association for Internet data analysis)公開數(shù)據(jù)分析，網(wǎng)絡(luò)背景流量大約為鏈路容量的15%～20%，大流大小(數(shù)據(jù)速率)為100～120 Mbit/s，每個(gè)節(jié)點(diǎn)對間包含的大流數(shù)目大約為0～2條。實(shí)驗(yàn)中，隨機(jī)產(chǎn)生15%～20%鏈路容量范圍內(nèi)的背景流量，然后隨機(jī)選取30個(gè)具有不同源和目的節(jié)點(diǎn)的節(jié)點(diǎn)對(節(jié)點(diǎn)對可相同)，每個(gè)節(jié)點(diǎn)對之間隨機(jī)一條速率為100～120 Mbit/s的基于目的地址的大流。二維數(shù)據(jù)流(基于源和目的地址的流)由目的大流分解得到，具體來說，對于每一條目的大流，首先隨機(jī)產(chǎn)生0～2條子流，這些子流占目的大流總量的15%～40%，剩下的大流流量再分割成若干子流，這些子流每條占目的大流數(shù)據(jù)總量的5%～15%。每個(gè)實(shí)驗(yàn)結(jié)果取10次仿真結(jié)果的平均值。

本文對表1中的6個(gè)拓?fù)溥M(jìn)行了仿真，對比了OSPF、基于目的地址的大流調(diào)度(dst-based randomized rounding)以及基于二維路由的大流調(diào)度(TD-based randomized rounding)這3種方案的性能比(含義同2.2.1節(jié)中的性能比)，仿真結(jié)果如圖2所示?？梢杂^察到，對于每一種拓?fù)?，OSPF的性能比最高，也就是負(fù)載最不均衡；基于目的地址進(jìn)行大流調(diào)度的性能比大約在1.1；而基于二維的大流調(diào)度性能比接近1.0。顯然基于二維路由的大流調(diào)度效果高于傳統(tǒng)路由方式，而且接近最優(yōu)，不需要再添加額外的維度。

3 結(jié)束語

本文從流量矩陣測量和路由設(shè)備轉(zhuǎn)發(fā)控制能力2個(gè)角度出發(fā)，介紹了流量工程的這2個(gè)挑戰(zhàn)和解決挑戰(zhàn)的一些研究角度及現(xiàn)有方案。本文結(jié)合上述挑戰(zhàn)提出了二維路由大流調(diào)度方案，具有細(xì)粒度、可擴(kuò)展性、低開銷的特性，真實(shí)實(shí)驗(yàn)證明了方案的可行性，仿真實(shí)驗(yàn)證明了方案的有效性。

圖2 大流調(diào)度仿真結(jié)果Fig.2 Simulation results of large flow scheduling

[1] HONG C Y, KANDULA S, MAHAJAN R, et al. Achieving high utilization with software-driven WAN[C]//ACM SIGCOMM.Hong Kong,China:ACM Press,2013:15-26.

[2] YANG S, XU M, WANG D, et al. Two dimensional router: Design and implementation[R]. Beijing: Tsinghua University, 2012.

[3] SRIDHARAN A,GUéRIN R,DIOT C.Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks[J].IEEE/ACM TON,2005,13(2):234-247.

[4] SRIVASTAVA S, AGRAWAL G, PIORO M, et al. Determining link weight system under various objectives for OSPF networks using a Lagrangian relaxation-based approach[J]. IEEE TNSM, 2005, 2(1): 9-18.

[5] BHATIA R, HAO F, KODIALAM M, et al. Optimized network traffic engineering using segment routing[C]//IEEE INFOCOM.Hong Kong, China: IEEE Press, 2015: 657-665.

[6] HARTERT R, SCHAUS P, VISSICCHIO S, et al. Solving segment routing problems with hybrid constraint programming techniques[C]//Springer International Publishing Switzerland CP. Cork, Ireland: Springer, Cham Press, 2015: 592-608.

[7] MEDINA A, TAFT N, SALAMATIAN K, et al. Traffic matrix estimation: Existing techniques and new directions[C]//ACM SIGCOMM. Pittsburgh, Pennsylvania: ACM Press, 2002, 32(4): 161-174.

[8] ZHANG Y, ROUGHAN M, DUFFIELD N, et al. Fast accurate computation of large-scale IP traffic matrices from link loads[C]//ACM SIGMETRICS. San Diego, CA, USA: ACM Press, 2003, 31(1): 206-217.

[9] APPLEGATE D, COHEN E. Making routing robust to changing traffic demands: algorithms and evaluation[J]. IEEE/ACM TON, 2006, 14(6): 1193-1206.

[10] APPLEGATE D, COHEN E. Making intra-domain routing robust to changing and uncertain traffic demands: Understanding fundamental tradeoffs[C]//ACM SIGCOMM.Karlsruhe,Germany:ACM Press,2003:313-324.

[11] CHIESA M, RéTVRI G, SCHAPIRA M. Lying Your Way to Better Traffic Engineering[C]//ACM CoNEXT. Irvine, California, USA: ACM Press, 2016: 391-398.

[12] ESTAN C,VARGHESE G.New directions in traffic measurement and accounting:Focusing on the elephants,ignoring the mice[J].ACM TOCS,2003,21(3):270-313.

[13] EINZIGER G, FELLMAN B, KASSNER Y. Independent counter estimation buckets[C]//IEEE INFOCOM. Hong Kong, China: IEEE Press, 2015: 2560-2568.

[14] LI Y,WU H,PAN T,et al.Case:Cache-assisted stretchable estimator for high speed per-flow measurement[C]//IEEE INFOCOM.San Francisco,CA,USA:IEEE Press,2016:1-9.

[15] BEN-BASAT R, EINZIGER G, FRIEDMAN R, et al. Heavy hitters in streams and sliding windows[C]//IEEE INFOCOM.San Francisco,CA,USA:IEEE Press,2016:1-9.

[16] METWALLY A, AGRAWAL D, EL ABBADI A. Efficient computation of frequent and top-k elements in data streams[C]//Springer Verlag Berlin Heidelberg ICDT. Edinburgh,UK:Springer,Berlin,Heidelberg Press,2005:398-412.

[17] AL-FARES M, RADHAKRISHNAN S, RAGHAVAN B, et al. Hedera: Dynamic Flow Scheduling for Data Center Networks [C]//USENIX NSDI. Boston, MA, USA: USENIX Press, 2010, 10: 19-19.

[18] CURTIS A R, KIM W, YALAGANDULA P. Mahout: Low-overhead datacenter traffic management using end-host-based elephant detection[C]//IEEE INFOCOM. Shanghai, China: IEEE Press, 2011: 1629-1637.

[19] BENSON T, ANAND A, AKELLA A, et al. MicroTE: Fine grained traffic engineering for data centers[C]//ACM CoNEXT. Tokyo, Japan: ACM Press, 2011: 8.

[20] MENDIOLA A, ASTORGA J, JACOB E, et al. A survey on the contributions of Software-Defined Networking to Traffic Engineering[J]. IEEE Communications Surveys & Tutorials, 2017, 19(2): 918-953.

[21] XU D, CHIANG M, REXFORD J. DEFT: Distributed exponentially-weighted flow splitting[C]//IEEE INFOCOM. Anchorage,Alaska,USA:IEEE Press,2007:71-79.

[22] AGARWAL S, KODIALAM M, LAKSHMAN T V. Traffic engineering in software defined networks[C]//IEEE INFOCOM.Turin,Italy:IEEE Press,2013:2211-2219.

[23] KANG N, GHOBADI M, REUMANN J, et al. Efficient traffic splitting on commodity switches[C]//ACM CoNEXT. Heidelberg, Germany: ACM Press, 2015: 6.

[24] AWDUCHE D O. MPLS and traffic engineering in IP networks[J].IEEE communications Magazine,1999,37(12):42-47.

[25] ZHU H, XU M, LI Q, et al. MDTC: An efficient approach to TCAM-based multidimensional table compression[C]//IEEE IFIP Networking. Toulouse, France: IEEE Press, 2015: 1-9.

[26] XU M, YANG S, WANG D, et al. Efficient Two Dimensional-IP routing: An incremental deployment design[J]. Elsevier CN, 2014(59): 227-243.

[27] RAGHAVAN P, TOMPSON C D. Randomized rounding: a technique for provably good algorithms and algorithmic proofs[J]. Combinatorica, 1987, 7(4): 365-374.

(編輯：劉 勇)