李 佟,韓春靜,李 俊

1(中國科學(xué)院 信息工程研究所,北京 100093)2(中國科學(xué)院 計算機(jī)網(wǎng)絡(luò)信息中心,北京 100190)3(中國科學(xué)院大學(xué),北京 100049)

SDN網(wǎng)絡(luò)虛擬化中規(guī)則映射研究①

李 佟1,2,3,韓春靜1,李 俊2

1(中國科學(xué)院 信息工程研究所,北京 100093)2(中國科學(xué)院 計算機(jī)網(wǎng)絡(luò)信息中心,北京 100190)3(中國科學(xué)院大學(xué),北京 100049)

軟件定義網(wǎng)絡(luò)(SDN)為網(wǎng)絡(luò)虛擬化提供了新的解決方案,通過網(wǎng)絡(luò)虛擬化技術(shù)可以將一套基礎(chǔ)設(shè)施虛擬化為多個邏輯網(wǎng)絡(luò)從而滿足不同的網(wǎng)絡(luò)需求.本文研究了SDN網(wǎng)絡(luò)虛擬化時多個物理交換機(jī)虛擬為一個大虛擬交換機(jī)的過程中,虛擬網(wǎng)絡(luò)規(guī)則與物理網(wǎng)絡(luò)規(guī)則的映射問題.綜合考慮鏈路負(fù)載、規(guī)則分布以及節(jié)點(diǎn)負(fù)載,提出了三段式規(guī)則映射優(yōu)化算法.首先根據(jù)虛擬網(wǎng)絡(luò)的規(guī)則請求生成組播源節(jié)點(diǎn)和后的節(jié)點(diǎn)集,采用MPH算法生成規(guī)則映射樹;然后采用入節(jié)點(diǎn)最近原則,將虛擬網(wǎng)絡(luò)規(guī)則請求的指令序列部署到規(guī)則映射樹中的中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)中;最后考慮節(jié)點(diǎn)負(fù)載,對規(guī)則部署進(jìn)行微調(diào),最終生成虛擬規(guī)則映射策略.通過仿真實驗,與直接邊緣節(jié)點(diǎn)部署相比,平均降低了網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)則總數(shù)量40%以上.

軟件定義網(wǎng)絡(luò);網(wǎng)絡(luò)虛擬化;OpenFlow;規(guī)則映射;大交換機(jī)

近年來,軟件定義網(wǎng)絡(luò)(SDN)在網(wǎng)絡(luò)研究與應(yīng)用領(lǐng)域取得了飛速的發(fā)展,軟件定義網(wǎng)絡(luò)技術(shù)采用集中式控制,將網(wǎng)絡(luò)的控制平面與數(shù)據(jù)平面完全解耦,從而使得網(wǎng)絡(luò)從封閉走向了開放;網(wǎng)絡(luò)應(yīng)用可以根據(jù)自己的需求定義訪問規(guī)則、路由策略、甚至定義并實現(xiàn)創(chuàng)新型網(wǎng)絡(luò)協(xié)議[1,2].OpenFlow作為軟件定義網(wǎng)絡(luò)技術(shù)中使用最為廣泛的技術(shù)之一,在負(fù)載均衡、虛擬機(jī)遷移、訪問控制以及廣域網(wǎng)流量調(diào)度等領(lǐng)域得到了實現(xiàn)和應(yīng)用.后前的各種開源控制器如OpenDaylight、ONOS、Floodlight等將網(wǎng)絡(luò)設(shè)備單獨(dú)管理,網(wǎng)絡(luò)應(yīng)用需要了解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與網(wǎng)絡(luò)狀態(tài),并需要將網(wǎng)絡(luò)應(yīng)用策略轉(zhuǎn)化為底層設(shè)備的單條規(guī)則單獨(dú)下發(fā),這種模型使得應(yīng)用開發(fā)者需要維護(hù)底層網(wǎng)絡(luò)設(shè)備與鏈路信息,包括路徑選擇,單個交換機(jī)上的流表與流表空間等,增加了網(wǎng)絡(luò)應(yīng)用開發(fā)的復(fù)雜度.

對于SDN網(wǎng)絡(luò)應(yīng)用來說,需要控制器提供良好的底層抽象,并維護(hù)底層網(wǎng)絡(luò)設(shè)備狀態(tài),應(yīng)用僅僅關(guān)心數(shù)據(jù)轉(zhuǎn)發(fā)規(guī)則策略定義、網(wǎng)絡(luò)負(fù)載以及路由策略等.根據(jù)不同應(yīng)用場景,網(wǎng)絡(luò)應(yīng)用關(guān)心的高層策略可以分為如下兩個方面:

1)端點(diǎn)策略

端點(diǎn)規(guī)則將全網(wǎng)視為一個“大交換機(jī)”(Big Switch),應(yīng)用開發(fā)人員僅僅需要關(guān)注網(wǎng)絡(luò)邊緣端點(diǎn)策略的定義,如入端口,處理策略,出端口等策略內(nèi)容,而不需要關(guān)注網(wǎng)絡(luò)底層的拓?fù)浣Y(jié)構(gòu),網(wǎng)絡(luò)內(nèi)部的流量與策略不需要由上層應(yīng)用處理,由控制器完成網(wǎng)絡(luò)內(nèi)部的路由選擇定義、鏈路負(fù)載均衡等內(nèi)容.

2)路由策略

路由策略關(guān)注了兩個設(shè)備之間的路由與負(fù)載,路由策略的定義通常由流量工程優(yōu)化目標(biāo)來生成,可以根據(jù)最小時延、最大利用率等相關(guān)優(yōu)化目標(biāo)生成路由策略.

為了使一套網(wǎng)絡(luò)基礎(chǔ)設(shè)施能夠滿足不同的應(yīng)用需求,入了網(wǎng)絡(luò)虛擬化以及切片技術(shù).網(wǎng)絡(luò)虛擬化的核心目標(biāo)是通過虛擬化技術(shù),將一個物理網(wǎng)絡(luò)分割為多個虛擬網(wǎng)絡(luò),或者將多個物理網(wǎng)絡(luò)設(shè)備的部分轉(zhuǎn)發(fā)能力提取并抽象為一個邏輯虛擬網(wǎng)絡(luò),不同的虛擬網(wǎng)絡(luò)之間的服務(wù)質(zhì)量能夠得到不同級別的保障,從而為上層的應(yīng)用提供網(wǎng)絡(luò)服務(wù)[3].網(wǎng)絡(luò)虛擬化打破了網(wǎng)絡(luò)物理設(shè)備和羅輯業(yè)務(wù)層之間的綁定關(guān)系,并且能夠?qū)⑽锢砭W(wǎng)絡(luò)進(jìn)行切片(slicing)[4,5],滿足更加復(fù)雜的業(yè)務(wù)需求.SDN技術(shù)是網(wǎng)絡(luò)虛擬化的一個新思路和新方法[3],已經(jīng)在全球網(wǎng)絡(luò)創(chuàng)新試驗環(huán)境(GENI)[4]以及數(shù)據(jù)中心[5]中開展了研究與應(yīng)用.

本文就SDN網(wǎng)絡(luò)虛擬化中多個物理設(shè)備虛擬成為一個虛擬設(shè)備,也就是“大交換機(jī)”中的規(guī)則映射問題進(jìn)行了分析,研究了在大交換機(jī)中流表規(guī)則映射模型,對Openflow中的指令(Instruction)和動作進(jìn)行分類,提出多個物理設(shè)備虛擬為一個虛擬大交換機(jī)場景下的規(guī)則映射算法.

1 相關(guān)研究工作

1.1 基于SDN的網(wǎng)絡(luò)虛擬化中間件技術(shù)

基于中間件的網(wǎng)絡(luò)虛擬化方案是在SDN設(shè)備和控制器之間添加一個虛擬化層,從物理SDN設(shè)備來看,網(wǎng)絡(luò)虛擬化中間件就是它的控制器;從虛擬網(wǎng)絡(luò)的控制器角度來看,控制器所面對的就是一系列虛擬的交換機(jī)以及他們之間的虛擬鏈路.在后前基于OpenFlow的虛擬化領(lǐng)域中,FlowVisor[7]、OpenVirteX[8]、CoVisor[9]、FlowN[10]等采用了這種思想實現(xiàn)了網(wǎng)絡(luò)虛擬化.

1.2 SDN規(guī)則映射以及優(yōu)化技術(shù)

文獻(xiàn)[11]關(guān)注于大交換機(jī)的網(wǎng)絡(luò)抽象和大交換機(jī)的流表規(guī)則映射問題,這種網(wǎng)絡(luò)抽象將整個網(wǎng)絡(luò)視為一個交換機(jī)從而實現(xiàn)網(wǎng)絡(luò)的扁平化管理,從應(yīng)用的角度來看,整個網(wǎng)絡(luò)是一個交換設(shè)備,簡化了移動性管理、網(wǎng)絡(luò)訪問策略管理等工作.該文獻(xiàn)提出了大交換機(jī)中端點(diǎn)策略的分配問題,采用路徑探測的方式將端點(diǎn)策略在路徑上進(jìn)行分配來減少網(wǎng)絡(luò)邊緣節(jié)點(diǎn)的流表數(shù)量.

文獻(xiàn)[12]提出的Palette分布式框架關(guān)注于分布式流表,將端點(diǎn)策略表拆分為多個子表并將其分布在多個交換機(jī)上,轉(zhuǎn)發(fā)保證每個數(shù)據(jù)包能夠在子表中經(jīng)過一次,這樣就等價于在邊緣節(jié)點(diǎn)上處理了流表規(guī)則中的所有動作.由于Palette采用了最短路徑優(yōu)先的策略實現(xiàn)流表的分布,這可能導(dǎo)致某個節(jié)點(diǎn)中流表規(guī)則聚集從而造成負(fù)載過重.

2 本文研究內(nèi)容

本文針對網(wǎng)絡(luò)虛擬化中的大交換機(jī)虛擬化模式,對文獻(xiàn)[11]與文獻(xiàn)[12]中的規(guī)則映射進(jìn)行了擴(kuò)展,充分考慮了Openflow中流表匹配規(guī)則、不同指令與動作類型以及流表中多出端口等情況.提出了三階段虛擬流表映射算法 MPH-DRP(Minimum Path Heuristic Dynamic Rule Placement),并進(jìn)行了原型實現(xiàn)、仿真與驗證.

3 SDN網(wǎng)絡(luò)虛擬化中的規(guī)則映射模型

本文就SDN網(wǎng)絡(luò)中的規(guī)則映射模型定義如下:

拓?fù)?拓?fù)涫侵窼DN基礎(chǔ)設(shè)施網(wǎng)絡(luò),可以用二元組 G(V,E)來定義,其中 V 是交換機(jī)節(jié)點(diǎn)集合,E 為交換機(jī)節(jié)點(diǎn)間鏈路集合,可以定義節(jié)點(diǎn)容量函數(shù):Capacity(n):V->R+其中,R+為非負(fù)實數(shù)集;鏈路容量函數(shù) Cost(e):E->R+其中,R+為非負(fù)實數(shù)集.

交換機(jī):交換機(jī)可以定義為一個網(wǎng)絡(luò)上的節(jié)點(diǎn),每個交換機(jī)包含一系列的規(guī)則列表[r1,r2,……,rk],其中ri為交換機(jī)上的規(guī)則.

規(guī)則:規(guī)則 r 可定義為 Match->Instructions.其中,Match 為匹配,Instructions為指令序列.一個數(shù)據(jù)包p與Match匹配后按順序執(zhí)行指令序列中的序列.

匹配:匹配(Match)是一個匹配列表,可以包括入端口匹配以及數(shù)據(jù)包字段匹配兩個部分.形式化表示為Match:{ingressPort=h1,matchField=(m1,m2…mn)}.其中ingressPort定義為某個交換機(jī)上的一個入端口,ingressPort所在的交換機(jī)定義為ingressNode,matchField為需要匹配的字段集合.

指令:指令(Instruction)是數(shù)據(jù)包匹配后所操作的指令,通常,指令以指令序列的形式來執(zhí)行,可以形式化表示為 Instructions:{(instructionSet1,Output=Output1),(instructionSet2,Output=Output2)….(instructionSetn,Output=Outputn)},該指令序列由Output動作進(jìn)行拆分,表示一個數(shù)據(jù)包在經(jīng)過指令操作后在多個端口轉(zhuǎn)發(fā).我們將Output端口定義為出端口(egressPort),出端口所在的交換機(jī)定義為出節(jié)點(diǎn)(egressNode).

不失一般性,本文中將OpenFlow中的ApplyActions中的系列動作統(tǒng)一看作特殊的指令來進(jìn)行處理.考慮到指令可能對數(shù)據(jù)包的修改,這里將指令分為兩類:數(shù)據(jù)包修改指令I(lǐng)nstructionW與數(shù)據(jù)包只讀指令I(lǐng)nstructionR.

Instructionw是指對數(shù)據(jù)包的數(shù)據(jù)字段進(jìn)行修改的指令與動作,以 Openflow1.3 為例,包括 AddFiled 指令、RemoveFiled指令以及SetField指令等相關(guān)指令.

InstructionR是指對數(shù)據(jù)包內(nèi)容沒有進(jìn)行修改的指令與動作.如 ApplyMeter、ApplyCounter、GotoTable等相關(guān)指令.

規(guī)則映射:一個規(guī)則映射是將應(yīng)用對虛擬大交換機(jī)的規(guī)則請求映射成為底層物理交換機(jī)上的規(guī)則的過程:

rv->Rphy.其中Rphy是物理交換機(jī)上的規(guī)則集合Rphy={rphy| rphy是物理交換機(jī)上的一條流表規(guī)則}.

映射模型:給定物理網(wǎng)絡(luò)拓?fù)銰和一個應(yīng)用請求rv,給出物理交換機(jī)上的規(guī)則集合Rphy,使其對數(shù)據(jù)包p的操作結(jié)果等價,即rv(p)=Rphy(p).

規(guī)則映射樹:在進(jìn)行規(guī)則映射時,一條虛擬規(guī)則最終映射為物理規(guī)則時,需要參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)和鏈路構(gòu)成的轉(zhuǎn)發(fā)樹,成為規(guī)則映射樹T.

映射樹路徑代價:給定網(wǎng)絡(luò)G(V,E)和規(guī)則請求rv,生成一個包含ingress端口所在節(jié)點(diǎn)s以及egress端口所在節(jié)點(diǎn)集合D的樹T,該樹T的路徑代價可以分為:

路徑代價:

最優(yōu)化目標(biāo):在給定網(wǎng)絡(luò)容量條件下,采用最小的代價將對大交換機(jī)的規(guī)則請求rv映射到物理拓?fù)渲?給出Rphy.

4 基于 MPH-DRP 的 SDN 規(guī)則映射

根據(jù)第三章的定義,將一個大交換機(jī)的規(guī)則請求rv映射到物理網(wǎng)絡(luò)中求出Rphy是一個NP難的問題.這是因為,在將請求rv映射到物理拓?fù)涞倪^程中,如果在rv的指令序列中Output動作前不包括任何操作指令,則該問題退化成為一個組播樹生成最優(yōu)化的問題,而組播樹生成最優(yōu)化問題為一個NP難問題[13],因此,大交換機(jī)規(guī)則映射問題也是一個NP難問題.

將一個虛擬規(guī)則映射到物理拓?fù)渲?我們可以根據(jù)第三章的模型定義將大交換機(jī)的一個虛擬規(guī)則轉(zhuǎn)化為一系列物理交換機(jī)上的物理規(guī)則,這些物理規(guī)則對數(shù)據(jù)包p的作用結(jié)果與虛擬規(guī)則作用的結(jié)果一致,包括匹配(Match),指令(Instruction)序列.其中虛擬規(guī)則的匹配(Matchv)被分散在多個物理節(jié)點(diǎn)上生成物理匹配規(guī)則(Matchphy),虛擬規(guī)則的指令(Instruction)序列,被分散在多個物理節(jié)點(diǎn)上,這些物理節(jié)點(diǎn)上的規(guī)則作用于數(shù)據(jù)包后,與虛擬規(guī)則作用等價.

為了優(yōu)化規(guī)則映射樹生成,本文采用三階段的方法對大交換機(jī)的流表規(guī)則請求映射進(jìn)行優(yōu)化.首先,確定Output指令所在的egressNode集合作為組播的接收節(jié)點(diǎn),將ingressPort所在的ingressNode作為組播源,采用MPH算法生成規(guī)則映射樹;第二,對指令序列中的非Output指令進(jìn)行處理,采用入端口最近規(guī)則部署(IngressPort Nearest Rule Placement)原則,根據(jù)指令前綴遞歸遍歷轉(zhuǎn)發(fā)樹,在規(guī)則映射樹節(jié)點(diǎn)中分配非Output指令所在位置.最后,遍歷規(guī)則映射樹對節(jié)點(diǎn)規(guī)則部署進(jìn)行微調(diào),如果步驟二中某些規(guī)則所在的節(jié)點(diǎn)的兒孫節(jié)點(diǎn)只有一個兒子節(jié)點(diǎn),則該規(guī)則可以放置在當(dāng)前節(jié)點(diǎn)或者其某個兒孫節(jié)點(diǎn)上,從而避免規(guī)則映射樹退化成為鏈表時規(guī)則聚集在入口節(jié)點(diǎn),實現(xiàn)節(jié)點(diǎn)的負(fù)載均衡.

階段一:基于MPH的規(guī)則映射樹生成

提取出虛擬拓?fù)渲噶顁v中的Output動作,確定Output動作所在交換機(jī),生成規(guī)則映射樹,該規(guī)則映射樹生成問題等價于組播樹生成問題.

組播樹生成優(yōu)化問題已經(jīng)有了比較深入的研究,比較典型的算法有MPH[13]算法、KMB[14]算法、ADH[15]算法等等,其中時間復(fù)雜度分別為O(mn2),O(n3)以及 O(mn2+e).MPH(Minimum Path Cost Heuristic)是大家討論得較多的一種方法 ,同時,也是一個非常優(yōu)秀的求解組播樹的算法.在文獻(xiàn)[13]中,S Ramanathan把MPH作為比較組播樹算法的一種標(biāo)準(zhǔn)算法.幾種算法的優(yōu)化目標(biāo)都是組播樹的總費(fèi)用,同時,優(yōu)于組播樹生成算法是NP難問題,幾種算法都是基于啟發(fā)式來生成組播樹的近似解.基于以上考慮本文采用MPH算法作為規(guī)則映射樹生成算法.

轉(zhuǎn)發(fā)組播樹生成過程如下:

1)假設(shè) T=為部分組播樹,初始化為只包含 ingressPort所在的交換機(jī) s,此時 Vt={s},Et=Φ,Ct=Φ.

2)在余下的egressPort所在的端節(jié)點(diǎn)DVt中搜索出到當(dāng)前最小生成樹T的路徑最短的端節(jié)點(diǎn)u(若有多個符合條件則任取一個即可),將從u到T的最短路徑并入生成樹T(端節(jié)點(diǎn)u及路徑上的所有節(jié)點(diǎn)并入Vt,該路徑上的邊并入Et,對應(yīng)邊的費(fèi)用并入Ct).

3)重復(fù)步驟2)直到D中的所有節(jié)點(diǎn)都包含到Vt中,產(chǎn)生的T為近似最小成本組播樹.

階段二:入端口最近規(guī)則部署

該階段將指令序列中非Output指令在階段一中生成的映射樹中部署,這里我們采用指令前綴遞歸遍歷規(guī)則映射樹的方法完成指令放置,盡量將指令部署在距離源端口距離近的節(jié)點(diǎn),從而減少指令在egressPort的聚集并減少整個網(wǎng)絡(luò)中規(guī)則的總數(shù)量,使得物理節(jié)點(diǎn)上的規(guī)則數(shù)最少.

根據(jù)前文所述,非Output指令包括兩種類型,instructionW與InstructionR兩種類型.由于InstructionW會對數(shù)據(jù)包進(jìn)行修改,這種操作將導(dǎo)致對匹配內(nèi)容的修改,不失一般性,本文中對修改后的數(shù)據(jù)包匹配采用將原Match形式化變換為Match’,后續(xù)節(jié)點(diǎn)的匹配以 Match’為基準(zhǔn)進(jìn)行數(shù)據(jù)包匹配,Match’的生成可以由原Match以及instructionW共同生成,本文關(guān)注于指令放置,對Match’生成不進(jìn)行深入討論.

入端口最近規(guī)則部署主要步驟如下:

1)根據(jù) Output指令,對 rv中的指令進(jìn)行匯聚,決定每個指令對應(yīng)的egressPort列表,放置于insEgressPortsmap數(shù)據(jù)結(jié)構(gòu)中.

2)將所有非Output指令放置于instructions列表數(shù)據(jù)結(jié)構(gòu)中,指令部署指針放置于instructions列表表頭,并將遍歷指針至于規(guī)則映射樹的根節(jié)點(diǎn);

3)從根節(jié)點(diǎn)開始,采用遞歸的方法放置instructions中的各個指令.當(dāng)該指令出現(xiàn)在當(dāng)前遍歷節(jié)點(diǎn)下所有egressPort上時,將該指令放置于該節(jié)點(diǎn)上,指令部署指針指向下一個指令,并重復(fù)3)遍歷當(dāng)前指針的所有兒子節(jié)點(diǎn);否則重復(fù)步驟3)遍歷當(dāng)前指針的所有兒子節(jié)點(diǎn).

算法偽代碼描述如下:

階段三:規(guī)則映射樹上指令部署優(yōu)化

該階段基于階段二的指令部署結(jié)果,根據(jù)規(guī)則映射樹結(jié)構(gòu)及其節(jié)點(diǎn)負(fù)載情況,深度優(yōu)先遍歷規(guī)則映射樹,進(jìn)一步優(yōu)化節(jié)點(diǎn)規(guī)則部署.對規(guī)則映射樹生成過程中退化為鏈表數(shù)據(jù)結(jié)構(gòu)的節(jié)點(diǎn)上的規(guī)則進(jìn)行進(jìn)一步優(yōu)化.

指令部署優(yōu)化階段偽代碼描述如下:

以如圖1的基礎(chǔ)設(shè)施網(wǎng)絡(luò)拓?fù)錇槔f明指令的放置過程,其中,節(jié)點(diǎn)以大寫字母A、B、C、D等進(jìn)行命名,節(jié)點(diǎn)括號中數(shù)字表示當(dāng)前該節(jié)點(diǎn)的規(guī)則容量.

對于規(guī)則rv= Match->Instructions;

其中 Match={ingressport=( a,match)|a 為節(jié)點(diǎn) A 上的一個ingress端口}

Instructions={Ins1,Output=e,Ins2,Output=g,ins3,egerss=Output,ins4,Output=b|e,g,h,b 分別為 E,G,H,B節(jié)點(diǎn)上的egress端口}.

圖1 基礎(chǔ)設(shè)施網(wǎng)絡(luò)拓?fù)鋱D

數(shù)據(jù)包p經(jīng)過規(guī)則rv處理后,根據(jù)Instructions指定的轉(zhuǎn)發(fā)出口,該數(shù)據(jù)包需要分別在在e、g、h、b四個端口轉(zhuǎn)發(fā)出SDN網(wǎng)絡(luò).首先,對于該拓?fù)浣Y(jié)構(gòu)執(zhí)行步驟一,基于 MPH 算法,以 A 為入節(jié)點(diǎn),E、G、H、B出節(jié)點(diǎn),生成規(guī)則映射樹,生成的規(guī)則映射樹如圖2所示.

圖2 基于 MPH 的規(guī)則映射樹

生成規(guī)則映射樹后,轉(zhuǎn)發(fā)路徑與出端口需要執(zhí)行指令如表1所示.

表1 邊緣端口路徑與指令表

執(zhí)行步驟二,經(jīng)過入端口最近規(guī)則部署算法處理后,指令被分配于規(guī)則映射樹中,放置情況如表2所示.

表2 MPH-INRP 算法指令部署表

對于當(dāng)前指令放置執(zhí)行步驟三.可以看出經(jīng)過步驟二后,節(jié)點(diǎn)C只有一個兒子節(jié)點(diǎn),因此指令I(lǐng)ns2可以部署在C節(jié)點(diǎn)或者D節(jié)點(diǎn)上,而D節(jié)點(diǎn)容量較大,則Ins2將被優(yōu)化部署在節(jié)點(diǎn)D上.執(zhí)行步驟三后指令部署如表3所示.

表3 MPH-DRP 算法指令部署表

5 算法評價與實驗分析

本問題提出的SDN規(guī)則映射分為三個獨(dú)立的步驟,映射樹生成步驟、指令放置步驟以及指令優(yōu)化步驟.對映射樹生成步驟,是典型的MPH組播樹生成的算法,設(shè)基礎(chǔ)拓?fù)涞墓?jié)點(diǎn)個數(shù)為n,egressPoint個數(shù)為m,根據(jù)文獻(xiàn)[13]其算法時間復(fù)雜度為:O(m2n+e).

對于步驟二,設(shè)映射樹中節(jié)點(diǎn)數(shù)量為m,指令序列中除去Output指令的指令個數(shù)為k,那么,對于指令序列的遍歷需要執(zhí)行k次,對于轉(zhuǎn)發(fā)組播樹的節(jié)點(diǎn)遍歷需要執(zhí)行m次,因此,最壞情況下,需要對每個節(jié)點(diǎn)進(jìn)行k次遍歷,復(fù)雜度為m*k,同時在循環(huán)中需要判斷Instruction是否作用于每個端點(diǎn),需要執(zhí)行m次循環(huán),因此步驟二最壞情況下的時間復(fù)雜度為O(m2k).

對于步驟三,需要對映射樹進(jìn)行深度優(yōu)先遍歷,在最壞的情況下,映射樹退化為一條n個節(jié)點(diǎn)鏈表,k個非Output指令在步驟二中部署在入口節(jié)點(diǎn).需要將k個非Output指令部署在n個節(jié)點(diǎn)的鏈表上,這里我們將k個非Output指令部署于負(fù)載最輕的節(jié)點(diǎn),復(fù)雜度最壞情況下為O(n).

因此整個算法的時間復(fù)雜度為O(m2n+e+m2k+n),即O(m2(n+k)+e+n).

由于基于MPH算法的組播樹生成問題已經(jīng)有比較深入的研究,本文對映射樹生成不進(jìn)行深入探討.在實驗中,我們實現(xiàn)了MPH-DRP兩端式規(guī)則放置算法,并實現(xiàn)了文獻(xiàn)[16,17]中提出的將規(guī)則直接部署于egerssNode算法,為了便于比較,我們稱之為MPH-ERP(Minimum Path Heuristic Egress Rule Placement),實驗中將 MPHERP與MPH-DRP進(jìn)行了如下兩種實驗比較:

實驗一.采用6*6網(wǎng)格形的基礎(chǔ)設(shè)施拓?fù)浣Y(jié)構(gòu),經(jīng)過大交換機(jī)虛擬化之后,在拓?fù)浣Y(jié)構(gòu)中選擇隨機(jī)選擇一個入端口,并在基礎(chǔ)設(shè)施中隨機(jī)選擇4個出端口作為egressPort上進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā),并定義instruction序列為:Instructions={Ins1,Output=p1,Ins2,Output=p2,ins3,Output=p2,ins4,Output=p4|pi分別為大交換機(jī)的egress端口}.

在虛擬網(wǎng)絡(luò)中部署101條虛擬指令,每部署一條指令后,每次記錄所有節(jié)點(diǎn)上分配的規(guī)則總數(shù)量以及基礎(chǔ)設(shè)施拓?fù)渲幸?guī)則最多節(jié)點(diǎn)中部署的規(guī)則數(shù)量,并進(jìn)行比較,仿真實驗結(jié)果如圖3、圖4所示.

圖3 隨機(jī)端口選取部署基礎(chǔ)設(shè)施規(guī)則總數(shù)量

圖4 隨機(jī)端口選取部署負(fù)載最重節(jié)點(diǎn)規(guī)則數(shù)量

在隨機(jī)部署的條件下,MPH-DRP算法的總規(guī)則數(shù)量平均為MPH-ERP部署的43.45%,在基礎(chǔ)設(shè)施中負(fù)載最大節(jié)點(diǎn)規(guī)則數(shù)量方面,MPH-DRP算法的最大負(fù)載節(jié)點(diǎn)的負(fù)載平均為MPH-ERP部署的60.07%.性能有顯著提升.

實驗二.與實驗一相同,采用6*6網(wǎng)格形的基礎(chǔ)設(shè)施拓?fù)?經(jīng)過大交換機(jī)虛擬化之后,隱藏了所有中間節(jié)點(diǎn),在拓?fù)浣Y(jié)構(gòu)中選擇隨機(jī)選擇邊緣節(jié)點(diǎn)上的端口作為入端口,并在基礎(chǔ)設(shè)施6*6個節(jié)點(diǎn)中隨機(jī)選擇4個邊緣節(jié)點(diǎn)的端口作為egressPort進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā),定義 instruction 序列為:Instructions={Ins1,Output=p1,Ins2,Output=p2,ins3,Output=p2,ins4,Output=p4|pi分別為大交換機(jī)的egress端口}.

在虛擬網(wǎng)絡(luò)中部署101條虛擬指令,每部署一條指令后,記錄所有節(jié)點(diǎn)上分配的物理規(guī)則總數(shù)量以及基礎(chǔ)設(shè)施拓?fù)渲形锢硪?guī)則最多節(jié)點(diǎn)的規(guī)則數(shù)量,實驗結(jié)果如圖5、圖6所示.

圖5 隨機(jī)邊緣端口選取部署基礎(chǔ)設(shè)施規(guī)則總數(shù)量

圖6 隨機(jī)邊緣端口選取部署負(fù)載最重節(jié)點(diǎn)規(guī)則數(shù)量

在隨機(jī)邊緣端口部署的條件下,MPH-DRP算法的總規(guī)則數(shù)量平均為MPH-ERP部署的44.69%,對于基礎(chǔ)設(shè)施中負(fù)載最大節(jié)點(diǎn)規(guī)則數(shù)量方面,MPH-DRP算法的最大負(fù)載節(jié)點(diǎn)的負(fù)載平均為MPH-ERP部署的56.61%.性能有顯著提升.

6 結(jié)語與進(jìn)一步研究工作

本文針對網(wǎng)絡(luò)虛擬化中大交換機(jī)流表映射問題,提出了MPH-DRP算法,該算法采用兩階段方案,通過組播樹生成算法構(gòu)造轉(zhuǎn)發(fā)樹,并采用入端口最近優(yōu)先的規(guī)則部署策略,優(yōu)化了大交換機(jī)虛擬化中一個端口進(jìn)入,多端口轉(zhuǎn)發(fā)并執(zhí)行相關(guān)指令的問題.該算法與邊緣規(guī)則部署相比,性能有顯著的提升.

本文中提出的MPH-DRP算法在出端口僅為一個時,退化為文獻(xiàn)[11,12]中的規(guī)則部署問題,本文中將規(guī)則部署與負(fù)載最輕的節(jié)點(diǎn),還沒有進(jìn)一步優(yōu)化在鏈表上的規(guī)則部署,因此算法還有優(yōu)化空間,提升基礎(chǔ)設(shè)施容量.

1 McKeown N,Anderson T,Balakrishnan H,et al.Openflow:Enabling innovation in campus networks.ACM SIGCOMM Computer Communication Review,2008,38(2):69–74.[doi:10.1145/1355734]

2 Song HY.Protocol-oblivious forwarding:Unleash the power of SDN through a future-proof forwarding plane.Proc.of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking.Hong Kong,China.2013.127–132.

3 Kabir Chowdhury NM,Boutaba R.A survey of network virtualization.Technology Report CS-2008-25.Waterloo:University of Waterloo,2008.

4 Berman M,Chase JS,Landweber L,et al.GENI:A federated testbed for innovative network experiments.Computer Network,2014,61:5–23.[doi:10.1016/j.bjp.2013.12.037]

5 Sherwood R,Chan M,Covington A,et al.Carving research slices out of your production networks with OpenFlow.ACM SIGCOMM Computer Communication Review,2010,40(1):129–130.[doi:10.1145/1672308]

6 Bari MF,Boutaba R,Esteves R,et al.Data center network virtualization:A survey.IEEE Communications Surveys &Tutorials,2013,15(2):909–928.

7 Sherwood R,Gibb G,Yap KK,et al.FlowVisor:A network virtualization layer.Stanford:Deutsche Telekom Inc.R&D Lab,2009.

8 Al-Shabibi A,De Leenheer M,Gerola M,et al.OpenVirteX:Make your virtual SDNs programmable.Proc.of the Third Workshop on Hot Topics in Software Defined Networking.Chicago,Illinois,USA.2014.25–30.

9 Jin X,Gossels J,Rexford J,et al.CoVisor:A compositional hypervisor for software-defined networks.Proc.of the 12th USENIX Conference on Networked Systems Design and Implementation.Oakland,CA,USA.2015.87–101.

10 Drutskoy DA.Software-defined network virtualization with flown[MSc.thesis].Princeton:Princeton University,2012.

11 Kang NX,Liu ZM,Rexford J,et al.Optimizing the “One big switch” abstraction in software-defined networks.Proc.ofthe Ninth ACM Conference on Emerging Networking Experiments and Technologies.Santa Barbara,California,USA.2013.13–24.

12 Kanizo Y,Hay D,Keslassy I.Palette:Distributing tables in software-defined networks.Proc.IEEE INFOCOM.Turin,Italy.2013.545–549.

13 Ramanathan S.Multicast tree generation in networks with asymmetric links.IEEE/ACM Trans.on Networking,1996,4(4):558–568.[doi:10.1109/90.532865]

14 Shaikh A,Shin K.Destination-driven routing for low-cost multicast.IEEE Journal on Selected Areas in Communications,2006,15(3):373–381.

15 Waxman BM.Routing of multipoint connections.IEEE Journal on Selected Areas in Communications,1988,6(9):1617–1622.[doi:10.1109/49.12889]

16 Casado M,Freedman MJ,Pettit J,et al.Rethinking enterprise network control.IEEE/ACM Trans.on Networking,2009,17(4):1270–1283.[doi:10.1109/TNET.2009.2026415]

17 Ioannidis S,Keromytis AD,Bellovin SM,et al.Implementing a distributed firewall.Proc.of the 7th ACM Conference on Computer and Communications Security.Athens,Greece.2000.190–199.

Research of Rule Mapping on Network Virtualization in SDN

LI Tong1,2,3,HAN Chun-Jing1,LI Jun2

1(Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China)2(Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China)3(University of Chinese Academy of Sciences,Beijing 100049,China)

Software Defined Network (SDN)provides a new solution for network virtualization,which can virtualize a set of infrastructures to multiple logical networks to meet different network requirements.This paper studies the mapping of virtual network rules to physical network rules when multiple physical switches are virtualized into one big switch in SDN network virtualization.Considering link load,rule distribution and node load,this paper proposes a three-stage rule mapping optimization algorithm.First,according to the rules of the virtual network,the multicast source node and a destination node set are located,and a rule mapping tree is generated by using the MPH algorithm.Then,the rules of the virtual network rules are deployed to multiple nodes of the physical network.Finally,with the consideration of the node load,the rule deployment is finely-tuned to generate the virtual rule mapping strategy.Simulation results show that compared with direct egress node deployment the average number of network node rules is reduced by more than 40%.

SDN;network virtualization;OpenFlow;rule mapping;big switch

李佟,韓春靜,李俊.SDN 網(wǎng)絡(luò)虛擬化中規(guī)則映射研究.計算機(jī)系統(tǒng)應(yīng)用,2017,26(9):238–245.http://www.c-s-a.org.cn/1003-3254/5970.html

①基金項后:中國科學(xué)院先導(dǎo)專項(XDA06010306);國家基金委青年基金項后(F020802)

2016-12-30;采用時間:2017-01-26