軟件定義的VANET下流表用量感知的QoS路由機制

付 彬 查理佳 李仁發(fā) 肖雄仁

1(湖南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410082) 2(嵌入式與網(wǎng)絡(luò)計算省重點實驗室(湖南大學(xué)) 長沙 410082)

軟件定義的VANET下流表用量感知的QoS路由機制

付 彬1,2查理佳1,2李仁發(fā)1,2肖雄仁1

1(湖南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410082)2(嵌入式與網(wǎng)絡(luò)計算省重點實驗室(湖南大學(xué)) 長沙 410082)

VANET可以提供各類安全和非安全相關(guān)的服務(wù)，但現(xiàn)有的VANET難以保障應(yīng)用服務(wù)的QoS需求.軟件定義網(wǎng)絡(luò)(software defined networking, SDN)以系統(tǒng)化的靈活控制網(wǎng)絡(luò)的方式出現(xiàn)，其分離的數(shù)據(jù)與控制平面為網(wǎng)絡(luò)帶來了可編程性.因此首先設(shè)計了一種面向異構(gòu)多網(wǎng)接入的軟件定義的VANET架構(gòu)；接著提出一種流表用量感知的動態(tài)QoS保障框架，允許使用模塊化的方式管理網(wǎng)絡(luò)，并支持業(yè)務(wù)流的動態(tài)加入和退出；最后建立了多業(yè)務(wù)流多約束條件下流表用量感知的QoS路由模型，該模型不僅考慮了丟包、時延和吞吐量等鏈路參數(shù)，還考慮了業(yè)務(wù)需求和流表使用情況，從而為VANET應(yīng)用服務(wù)提供并發(fā)的QoS路由.實驗表明：流表用量感知的動態(tài)QoS路由機制不僅能夠滿足多業(yè)務(wù)對各自丟包、時延和吞吐量的要求，還能夠感知流表用量，從而避免流表溢出對QoS路由機制的影響，進(jìn)一步提高了網(wǎng)絡(luò)QoS保障的性能.

軟件定義網(wǎng)絡(luò)；車輛自組織網(wǎng)絡(luò)；服務(wù)質(zhì)量；路由模型；流表

車輛自組織網(wǎng)絡(luò)(vehicular ad hoc network， VANET)實現(xiàn)車與車(vehicle-to-vehicle， V2V)、車與基礎(chǔ)設(shè)施(vehicle-to-infrastructure， V2I)、車與人及互聯(lián)網(wǎng)的廣泛通信，從而能夠提供各類安全和非安全相關(guān)的服務(wù)[1].雖然VANET能夠支持許多新的服務(wù)和應(yīng)用，但是在部署VANET服務(wù)和應(yīng)用時仍然面臨三種主要挑戰(zhàn)：

1) 體系結(jié)構(gòu)的挑戰(zhàn).當(dāng)前的VANET架構(gòu)主要是基站和路邊單元(rode side unit, RSU)的V2V與V2I混合架構(gòu)，該架構(gòu)缺乏靈活性，導(dǎo)致大規(guī)模地部署和設(shè)置新的服務(wù)或協(xié)議是很困難的.

2) 通信流量的挑戰(zhàn).車輛的移動性使得網(wǎng)絡(luò)通信流量的動態(tài)性和不均衡性特征突出，現(xiàn)有的VANET缺乏全局視圖，在數(shù)據(jù)轉(zhuǎn)發(fā)過程中不能動態(tài)調(diào)度網(wǎng)絡(luò)資源來合理分配通信流量，從而提升網(wǎng)絡(luò)傳輸效率.

3) 網(wǎng)絡(luò)服務(wù)質(zhì)量(quality of service， QoS)的挑戰(zhàn).不同的VANET應(yīng)用對于網(wǎng)絡(luò)提供的QoS有著不同的要求.當(dāng)前VANET的眾多應(yīng)用主要依賴于傳統(tǒng)的IP分組網(wǎng)絡(luò)，該網(wǎng)絡(luò)的盡力而為服務(wù)模式不能為數(shù)據(jù)傳輸?shù)膸?、端到端延遲和包到達(dá)率等性能提供服務(wù)質(zhì)量保證.

針對以上問題，許多研究者提出將軟件定義網(wǎng)絡(luò)(software defined networking， SDN)[2-3]架構(gòu)引入VANET，從而分離VANET數(shù)據(jù)平面與控制平面，實現(xiàn)網(wǎng)絡(luò)的系統(tǒng)化靈活控制，帶來可編程性.例如：文獻(xiàn)[4]提出了一種基于SDN的VANET架構(gòu)，指出新架構(gòu)將提高路徑選擇、頻率/信道選擇、功率選擇方面的性能提升，并展望了新架構(gòu)的VANET應(yīng)用；文獻(xiàn)[5]提出了基于SDN的5G網(wǎng)絡(luò)VANET架構(gòu)，并說明了SDN對下一代5G網(wǎng)絡(luò)VANET的重要性；文獻(xiàn)[6]提出了面向無線異構(gòu)接入的軟件定義的VANET架構(gòu)，在該架構(gòu)下無線異構(gòu)設(shè)備諸如汽車、RSU都可以抽象為SDN交換機；文獻(xiàn)[7]提出了一種基于SDN并支持霧計算的VANET架構(gòu)，同時該架構(gòu)也支持無線異構(gòu)接入.

利用軟件定義VANET的控制與轉(zhuǎn)發(fā)相分離以及集中控制的優(yōu)勢，本文對軟件定義VANET的架構(gòu)以及動態(tài)QoS路由相關(guān)問題進(jìn)行了研究.本文的主要貢獻(xiàn)有4個方面：

1) 設(shè)計了一種面向異構(gòu)多網(wǎng)接入的軟件定義VANET架構(gòu)，完善了現(xiàn)有工作中數(shù)據(jù)平面的設(shè)計.

2) 針對現(xiàn)有的VANET難以保障應(yīng)用服務(wù)的QoS需求問題，本文提出一種流表用量感知的動態(tài)QoS保障框架，允許使用模塊化的方式管理網(wǎng)絡(luò)，并支持業(yè)務(wù)流的動態(tài)加入和退出.

3) 在框架的基礎(chǔ)之上建立了多業(yè)務(wù)流多約束條件下流表用量感知的QoS路由模型，該模型不僅考慮了丟包、時延和吞吐量等鏈路狀態(tài)參數(shù)，還考慮了應(yīng)用服務(wù)的需求以及交換機的流表使用情況，從而為VANET應(yīng)用服務(wù)提供并發(fā)的QoS路由.

4) 利用仿真平臺實現(xiàn)了本文所提出的保障框架的各個模塊并進(jìn)行了仿真實驗.實驗表明，本文提出的QoS路由機制不僅能夠滿足多業(yè)務(wù)對各自丟包、時延和吞吐量的要求，而且能夠感知流表用量從而避免流表溢出對QoS路由的影響，進(jìn)一步提高了網(wǎng)絡(luò)QoS保障的性能.

1 相關(guān)工作

在SDN架構(gòu)下，為了給應(yīng)用服務(wù)提供QoS路由保障，許多研究人員對動態(tài)QoS路由機制進(jìn)行了相關(guān)的理論和實踐研究.其中，文獻(xiàn)[8-14]提出了一些QoS路由算法，文獻(xiàn)[15-18]提出了QoS路由框架.

文獻(xiàn)[8]針對域內(nèi)網(wǎng)絡(luò)提出了面向SDN的可擴展路由和資源管理模型，SDN控制器基于此模型實施路由計算、權(quán)限控制和資源管理.

文獻(xiàn)[9]提出了一種基于QoS和動態(tài)負(fù)載均衡的路由策略，該算法兼顧了流的QoS需求，并用近似算法進(jìn)行多QoS約束的最優(yōu)路徑選擇.

文獻(xiàn)[10-11]都是關(guān)注視頻業(yè)務(wù)的QoS.其中，文獻(xiàn)[10]提出了基于SDN/OpenFlow的分析型架構(gòu)來優(yōu)化轉(zhuǎn)發(fā)策略；文獻(xiàn)[11]與文獻(xiàn)[10]類似，但文獻(xiàn)[11]定義了自己的受限最短路徑問題，可以動態(tài)調(diào)整路由策略.

文獻(xiàn)[12]修改Floodlight控制器的內(nèi)置模塊來優(yōu)化其對QoS的支持性能.由于Floodlight控制器采用的路由算法沒有考慮鏈路之間的代價，因此該文作者在此基礎(chǔ)上修改路由算法，考慮了鏈路負(fù)載與QoS.

文獻(xiàn)[13]描述了SDN的網(wǎng)絡(luò)架構(gòu)并分析了提供多媒體服務(wù)的機遇和必要性，因此該文作者提出了一種SDN框架，該框架集成了OpenFlow、網(wǎng)絡(luò)虛擬化、功能盒以及測試算法的接口.其中的“QoS路由算法”模塊可以作為運行不同QoS路由算法的容器.

Fig. 1 Software defined VANET framework圖1 軟件定義的VANET體系架構(gòu)

文獻(xiàn)[14]基于SDN/OpenFlow實施了一套QoS保障模型，可以實時地監(jiān)控網(wǎng)絡(luò)的QoS指標(biāo)并動態(tài)地改變業(yè)務(wù)的路由.此外，該文作者還提出了面向多業(yè)務(wù)多約束條件下的路徑模型，由此來為多業(yè)務(wù)分配滿足其QoS需求的路徑.

文獻(xiàn)[15]提出了一種SDN/OpenFlow控制器的設(shè)計方案OpenQoS，其目的是保障多媒體業(yè)務(wù)端到端傳輸?shù)腝oS.多媒體流的傳輸路徑可以根據(jù)當(dāng)前網(wǎng)絡(luò)的QoS指標(biāo)來進(jìn)行動態(tài)調(diào)整.

文獻(xiàn)[16]基于SDN/OpenFlow與OpenNaaS提出了網(wǎng)絡(luò)控制層(network control layer，NCL)的概念.網(wǎng)絡(luò)控制層包括SDN控制器、SDN監(jiān)控器和SDN APP，NCL的目標(biāo)是為服務(wù)提供端到端的動態(tài)QoS控制.

文獻(xiàn)[17]提出了QoS管理機制，能夠讓QoS指標(biāo)可以自動地配置在OpenFlow交換機里.此外，該文作者基于AQSDN設(shè)計了數(shù)據(jù)包上下文感知的QoS模型來提高網(wǎng)絡(luò)的QoS，此模型在數(shù)據(jù)包被標(biāo)記和進(jìn)入轉(zhuǎn)發(fā)隊列管理狀態(tài)時能夠考慮數(shù)據(jù)包的上下文.

文獻(xiàn)[18]提出了OpenFlow增強的QoE保障框架，當(dāng)多個用戶競爭網(wǎng)絡(luò)資源的時候最大化每個用戶的QoS，關(guān)注的是用戶級別的公平性和網(wǎng)絡(luò)的穩(wěn)定性.

由于SDN路由過程的實現(xiàn)必須依賴于交換機的流表管理，當(dāng)前研究者對流表的管理機制進(jìn)行了相關(guān)研究，但是流表對QoS路由的影響卻未見具體分析.

2 軟件定義的VANET體系架構(gòu)設(shè)計

ONF組織提出的SDN系統(tǒng)架構(gòu)主要由數(shù)據(jù)平面、控制平面和應(yīng)用平面構(gòu)成.數(shù)據(jù)平面只需要實現(xiàn)轉(zhuǎn)發(fā)和處理數(shù)據(jù)的功能；控制平面主要負(fù)責(zé)邏輯控制部分；應(yīng)用平面由若干個SDN應(yīng)用構(gòu)成，通過北向接口與SDN控制器進(jìn)行交互.

當(dāng)前提出的基于SDN的VANET架構(gòu)，如引言所述文獻(xiàn)[4-7]，主要描述了面向無線異構(gòu)接入的VANET架構(gòu).本文在遵循3層SDN平面劃分標(biāo)準(zhǔn)的基礎(chǔ)上，充分考慮了VANET架構(gòu)的特點，完善了數(shù)據(jù)平面的VANET異構(gòu)接入方式以及SDN交換層的設(shè)計.本文設(shè)計的軟件定義的VANET體系架構(gòu)如圖1所示.

該體系架構(gòu)的主要元素包括5個：

1) SDN APP.基于控制平面的北向接口，提供軟件支持、網(wǎng)絡(luò)監(jiān)控、規(guī)則定義等服務(wù)，并為VANET應(yīng)用服務(wù)提供網(wǎng)絡(luò)支持.

2) SDN控制器.是網(wǎng)絡(luò)的邏輯控制中心，管理并控制區(qū)域內(nèi)的網(wǎng)絡(luò)行為.此外，控制器之間通過東/西向接口協(xié)同合作管理網(wǎng)絡(luò).

3) SDN交換機.接受SDN控制器的控制，在數(shù)據(jù)平面上負(fù)責(zé)數(shù)據(jù)的轉(zhuǎn)發(fā)和處理.

4) 異構(gòu)接入網(wǎng)絡(luò).在數(shù)據(jù)平面上為車輛終端提供異構(gòu)多樣的接入方式.例如通過RSU，4 G/LTE等接入.

5) 終端.移動車輛作為數(shù)據(jù)收發(fā)的終端.

Fig. 3 Throughput changes of client in the flow table overflow situation圖3 流表溢出情況下的客戶端吞吐量的變化情況

在上述體系結(jié)構(gòu)中，車輛與控制器通信的方式有3種：1) 車輛終端通過蜂窩網(wǎng)絡(luò)接入SDN核心交換層與控制器通信；2) 車輛終端通過RSU接入SDN核心交換層與控制器通信；3) 車輛終端通過RSU接入蜂窩網(wǎng)絡(luò)再接入SDN核心交換層與控制器通信.

軟件定義的VANET可以提供的服務(wù)類型多樣，在實際網(wǎng)絡(luò)部署中，數(shù)據(jù)層面的SDN交換機擔(dān)負(fù)起數(shù)據(jù)轉(zhuǎn)發(fā)的功能，SDN交換機之間鏈路的傳輸帶寬、負(fù)載等情況直接影響數(shù)據(jù)傳輸?shù)男阅?本文對上述架構(gòu)中SDN核心交換層的QoS路由問題展開研究，主要考慮2點：

1) 由于車輛的移動性，RSU的任務(wù)負(fù)載量是動態(tài)變化的.因此，我們需要根據(jù)RSU當(dāng)前的任務(wù)負(fù)載量來考慮動態(tài)QoS路由，以達(dá)到保障接入RSU的車輛業(yè)務(wù)的QoS.

2) 由于VANET服務(wù)的實時性，因此我們需要考慮多業(yè)務(wù)并發(fā)的路由機制，以提高動態(tài)QoS路由的效率，及時保障接入RSU的車輛業(yè)務(wù)的QoS.

3 流表溢出對QoS路由機制的影響

SDN交換機的流表容量是有限的，每一條流表項代表一條轉(zhuǎn)發(fā)規(guī)則.OpenFlow1.3[19]對流表溢出的處理方法是當(dāng)流表項達(dá)到容量上限時，會丟棄新添加的流表項；而OpenFlow1.4[20]可以自定義丟棄機制，自動清理重要性更低的流表項.這些丟棄機制都會導(dǎo)致已成功接入業(yè)務(wù)的QoS降低.

因此，我們通過實驗研究流表溢出對QoS路由機制的影響.網(wǎng)絡(luò)中共有12臺交換機，鏈路隨機生成，并設(shè)定鏈路帶寬為10 Mbps，丟包率為1%，時延為10 ms.客戶端通過交換機S8接入網(wǎng)絡(luò)，通過服務(wù)器配置設(shè)定了視頻傳輸?shù)膸挒? Mbps.我們實現(xiàn)了以多約束條件的Dijkstra算法為路由算法的QoS路由機制，圖2所示的是QoS路由機制的選路結(jié)果，視頻傳輸選擇的路徑為S1—S2—S3—S8.

Fig. 2 Routing results of QoS routing mechanism圖2 QoS路由機制的選路結(jié)果

我們設(shè)置S2的流表容量為100條，并向S2的流表中插入100條流表，此時如若再向S2添加流表項則會發(fā)生溢出.我們重新啟動QoS路由機制為客戶端選路，選路結(jié)果仍然為S1—S2—S3—S8，當(dāng)控制器向S2添加流表項時發(fā)生了溢出，導(dǎo)致從S1向S2轉(zhuǎn)發(fā)的數(shù)據(jù)包大量丟失，造成了客戶端業(yè)務(wù)吞吐量的下降.此時，客戶端吞吐量變化情況如圖3所示.

圖3中流表溢出后吞吐量始終得不到提升的原因是：當(dāng)QoS路由機制發(fā)現(xiàn)當(dāng)前路徑不滿足客戶端的QoS需求時會重新啟動選路過程，然而QoS路由機制根據(jù)當(dāng)前選路指標(biāo)(丟包率、時延、吞吐量)所選出的路徑仍然與之前的路徑相同.QoS路由機制不斷為其重新選路，但客戶端業(yè)務(wù)的吞吐量卻始終得不到提升，造成了巨大的路由開銷.

從第1節(jié)對動態(tài)QoS路由機制的相關(guān)研究中可以看到，這些研究都沒有考慮交換機流表的使用情況，也就不能保證當(dāng)選路結(jié)果上的流表發(fā)生溢出時QoS機制能夠及時做出正確的處理，而SDN控制器具有網(wǎng)絡(luò)全局的視圖，具備監(jiān)測交換機流表用量的能力.因此，本文提出一種流表用量感知的動態(tài)QoS路由機制，能夠?qū)⒘鞅碛昧孔鳛镼oS路由的約束條件，解決流表溢出對QoS路由機制的影響.

4 流表用量感知的動態(tài)QoS保障框架

隨著移動設(shè)備和移動流量的增長，V2V和V2I將會有更多的需求并不斷增長.VANET提供了廣泛的服務(wù)，為了滿足具有不同特點的應(yīng)用服務(wù)的QoS，本節(jié)提出了軟件定義的VANET下流表用量感知的動態(tài)QoS保障框架，如圖4所示：

Fig. 4 Flow table usage-aware dynamic QoS provisioning framework圖4 流表用量感知的動態(tài)QoS保障框架

該框架在SDN的管理層來實現(xiàn)，管理層通過Floodlight控制器的北向接口與控制層進(jìn)行交互，整個框架主要由8個模塊構(gòu)成：

1) 網(wǎng)絡(luò)狀態(tài)監(jiān)視器.實時地搜集鏈路的狀態(tài)信息，比如每一條鏈路當(dāng)前的吞吐量，并將采集到的數(shù)據(jù)發(fā)送給網(wǎng)絡(luò)帶權(quán)圖生成器.

2) 網(wǎng)絡(luò)拓?fù)溆成淦?實時地監(jiān)測網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，比如，是否有交換機增減、是否有終端機增減，并將數(shù)據(jù)發(fā)送給網(wǎng)絡(luò)帶權(quán)圖生成器.

3) 網(wǎng)絡(luò)帶權(quán)圖生成器.接收網(wǎng)絡(luò)狀態(tài)監(jiān)視器和網(wǎng)絡(luò)拓?fù)溆成淦靼l(fā)送過來的鏈路與網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)，并按照一定的權(quán)重計算并生成網(wǎng)絡(luò)權(quán)重視圖.

4) 流表用量監(jiān)控器.負(fù)責(zé)實時地監(jiān)控所有交換機流表的使用情況，并將監(jiān)控的結(jié)果發(fā)送給路由計算模塊以便路由決策的進(jìn)行.

5) 路由計算模塊.等待路由觸發(fā)器的路由指令，根據(jù)網(wǎng)絡(luò)權(quán)重視圖、多業(yè)務(wù)的QoS需求以及流表使用情況來為多業(yè)務(wù)并發(fā)選路.此模塊執(zhí)行的具體路由算法，將在第5節(jié)詳細(xì)介紹.

6) 業(yè)務(wù)處理器.支持業(yè)務(wù)的動態(tài)接入和退出.當(dāng)有業(yè)務(wù)接入時，通知路由觸發(fā)器，若當(dāng)前的網(wǎng)絡(luò)資源不足以滿足業(yè)務(wù)需求則拒絕接入；當(dāng)有業(yè)務(wù)退出時，通知路由觸發(fā)器以便刪除業(yè)務(wù)的路由信息.

7) 路由觸發(fā)器.監(jiān)控成功接入業(yè)務(wù)的QoS，在業(yè)務(wù)QoS受影響時觸發(fā)路由計算，當(dāng)業(yè)務(wù)退出時刪除業(yè)務(wù)的路由信息以節(jié)省流表資源.

8) 動態(tài)路徑安裝模塊.根據(jù)路由計算模塊選路的結(jié)果下發(fā)業(yè)務(wù)的流表.

軟件定義的VANET下流表用量感知的動態(tài)QoS保障框架的工作流程如圖5所示：

Fig. 5 Workflow of flow table usage-aware dynamic QoS provisioning framework圖5 流表用量感知的動態(tài)QoS保障框架工作流程

VANET下流表用量感知的動態(tài)QoS保障框架的工作步驟如下：

1) 網(wǎng)絡(luò)拓?fù)溆成淦鳈z測網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，同時網(wǎng)絡(luò)狀態(tài)監(jiān)視器收集鏈路的狀態(tài)信息，它們都將數(shù)據(jù)發(fā)送給網(wǎng)絡(luò)帶權(quán)圖生成器生成網(wǎng)絡(luò)權(quán)重圖.

2) 業(yè)務(wù)處理器檢測新接入的業(yè)務(wù)，如果有業(yè)務(wù)接入，就通知路由觸發(fā)器，路由觸發(fā)器根據(jù)業(yè)務(wù)的需求觸發(fā)路由計算；接著，路由計算模塊根據(jù)網(wǎng)絡(luò)權(quán)重圖與流表使用情況執(zhí)行路由算法，如果路由失敗，即網(wǎng)絡(luò)當(dāng)前可用資源不能滿足新接入業(yè)務(wù)的QoS需求，業(yè)務(wù)處理器就會拒絕新業(yè)務(wù)的接入，否則就通過動態(tài)路徑安裝模塊解析路由結(jié)果并下發(fā)流表.

3) 路由觸發(fā)器監(jiān)控成功接入業(yè)務(wù)的QoS，如果發(fā)現(xiàn)業(yè)務(wù)的QoS不滿足其需求則重新選路，若業(yè)務(wù)退出則刪除此業(yè)務(wù)的路由信息.

5 流表用量感知的QoS路由模型

VANET可提供的服務(wù)具有不同的特點，有的實時性較高，但帶寬占用量較小，比如交通信息、新聞、天氣；而有的屬于帶寬密集型服務(wù)，比如視頻、語音通話.因此，構(gòu)建QoS路由模型需要考慮不同的VANET業(yè)務(wù)之間具有不同的QoS需求這一特點.

文獻(xiàn)[14]提出的路由模型結(jié)合了多商品流問題和受限最短路徑問題.多商品流問題是指在多源多目的的情況下，如何為所有商品分配滿足其約束的路徑并且總代價最小的問題；而結(jié)合了受限最短路徑問題的多商品流問題是指在多源多目的的情況下，如何為所有商品分配滿足其約束條件并且代價最小的最短路徑的問題.

因此，文獻(xiàn)[14]提出的路由模型適用于本文提出的不同類型VANET業(yè)務(wù)的QoS路由問題.但從第3節(jié)的實驗中可以看出，流表溢出會降低文獻(xiàn)[14]提出的QoS路由機制的性能，因此本文在文獻(xiàn)[14]提出的路由模型的基礎(chǔ)上進(jìn)行了改進(jìn)，增加了流表用量的限制條件，將流表用量也作為選路的依據(jù)，從而進(jìn)一步提升網(wǎng)絡(luò)QoS保障的性能.

我們根據(jù)鏈路狀態(tài)參數(shù)(丟包率、時延、吞吐量)、業(yè)務(wù)需求以及流表使用情況來選擇合適的路徑.假設(shè)網(wǎng)絡(luò)以有向圖G=(N，E)表示，N是節(jié)點集合，E是節(jié)點間鏈路集合，節(jié)點i和節(jié)點j之間鏈路帶寬表示為bi j，時延為di j，丟包率為pi j，每條流的開銷為ci j，網(wǎng)絡(luò)中需要路由的流的數(shù)量為k，節(jié)點i的流表使用量為ui.根據(jù)上述假設(shè)，我們構(gòu)建了線性規(guī)劃模型，模型的參數(shù)如表1所示.優(yōu)化的目標(biāo)是要找到滿足所有業(yè)務(wù)約束條件的最小代價和的路徑.

Table 1 The Parameters of Model表1 模型參數(shù)

目標(biāo)函數(shù)：

約束條件：

式(1)是目標(biāo)函數(shù)，我們需要找到滿足所有業(yè)務(wù)約束條件的最小代價和的路徑.對于路徑代價的計算，我們主要考慮了丟包率和時延2個因素，并分別賦予它們對路徑代價影響的權(quán)重：

ci j=αdi j+βpi j,?(i,j)∈A,

其中，α和β分別為時延和丟包率對鏈路代價影響的權(quán)重，我們可以通過管理這些參數(shù)來滿足不同類型業(yè)務(wù)的需求.時延的計算包括4個組成部分，定義為

dnodal=dproc+dqueue+dtrans+dprop,

總時延由dnodal表示；dproc，dqueue，dtrans，dprop分別表示處理時延、排隊時延、發(fā)送時延和傳播時延.式(2)為流量守恒定律，保證流的輸入和輸出守恒；式(3)～(5)分別為最大可接受丟包率、最大可接受時延和鏈路的帶寬容量限制；式(6)(7)是對變量取值范圍的限制，對于一條鏈路而言，我們有選和不選2種選擇，分別用1和0表示.此外式(6)(7)還考慮了對節(jié)點i流表溢出時的約束，即當(dāng)節(jié)點i的流表溢出時不再選擇經(jīng)過節(jié)點i的鏈路.

實時業(yè)務(wù)通常會對丟包率、時延、吞吐量、業(yè)務(wù)代價等多個參數(shù)同時提出要求，當(dāng)這些參數(shù)相互獨立時，選擇滿足多個參數(shù)限制的路由就成為NP-Complete[21]問題，對于求解上述線性規(guī)劃模型的算法時間復(fù)雜度的評估，變量數(shù)量與邊的數(shù)量和業(yè)務(wù)數(shù)量有關(guān)，等于|A‖K|，而約束條件的數(shù)量也與邊數(shù)和業(yè)務(wù)數(shù)量相關(guān)，等于|N‖K|+|A|+|K|.本文采用了IP_Solve[22]求解器來求解本文提出的線性規(guī)劃模型，求解器采用了改進(jìn)的分支定界法求解線性規(guī)劃模型，平均時間復(fù)雜度達(dá)到指數(shù)級，雖然在大規(guī)模網(wǎng)絡(luò)中計算開銷較大，但是能夠在一般規(guī)模網(wǎng)絡(luò)中快速找到最優(yōu)解，而計算開銷相對較小的智能優(yōu)化算法一般只能找到近似解.由于在大規(guī)模軟件定義VANET中，通常會由多個控制器實現(xiàn)分布式控制，因此，單個控制器所控制的網(wǎng)絡(luò)規(guī)模一般不會太大，因此本文采用了求解器求解的方式，以便能夠快速找到最優(yōu)解，同時滿足VANET環(huán)境的時延敏感的特性.

6 實驗評估

本文實驗采用Mininet2.2.1[23]作為仿真平臺，F(xiàn)loodlight1.1[24]作為SDN控制器，OpenFlow1.3作為控制器與數(shù)據(jù)平面交互的南向接口協(xié)議，并基于控制器的北向接口實現(xiàn)了第4節(jié)所提出的QoS保障框架中的所有模塊.網(wǎng)絡(luò)中共有12臺SDN交換機，交換機之間的鏈路隨機生成，并設(shè)定鏈路的帶寬為30 Mbps，丟包率為1%，時延為10 ms.視頻服務(wù)器采用VLC Media Player，通過cvlc命令推送高清視頻流到視頻客戶端，F(xiàn)TP服務(wù)器采用Apache FtpServer，在FTP客戶端通過wget命令下載文件，同時我們使用Iperf工具實現(xiàn)鏈路擁塞，服務(wù)器通過交換機S1接入網(wǎng)絡(luò)，并通過服務(wù)器配置設(shè)定了文件傳輸?shù)钠骄鶐挒? Mbps，視頻傳輸?shù)钠骄鶐挒? Mbps.實驗一共分為2部分:1)在流表未溢出的場景下對本文提出的QoS路由機制的性能評估；2)在流表溢出的場景下，對本文提出的QoS路由機制與文獻(xiàn)[14]提出的QoS路由機制進(jìn)行性能比較.

6.1動態(tài)QoS路由機制性能評估

1) 客戶端選路與吞吐量性能分析

Fig. 6 Routing results of starting and stopping QoS mechanism in the link congestion situation圖6 鏈路擁塞時啟用和關(guān)閉QoS路由機制的選路情況

在流表未溢出的場景下，首先評估了本文所提的QoS路由機制對業(yè)務(wù)QoS的保障性能.視頻客戶端和FTP客戶端分別通過S8與S12接入網(wǎng)絡(luò).我們通過啟用和不啟用本文所提出的QoS路由機制2種情況來觀察客戶端選路和吞吐量的變化情況，實驗結(jié)果如圖6和圖7所示.在該實驗場景中，我們通過在一定時間內(nèi)分別向鏈路S6—S11與S1—S2增加負(fù)載FTP-Loader與Video-Loader來改變該鏈路的擁塞情況，通過使S6—S11和S1—S2鏈路擁塞而讓FTP客戶端和視頻客戶端的QoS受到影響.圖6(a)所示的是未啟用QoS路由機制，是采用默認(rèn)最短路徑路由機制場景下的選路結(jié)果，可以看出，即使鏈路S6—S11和S1—S2發(fā)生了擁塞，控制器也不會為客戶端調(diào)整路徑，仍然按照原始路徑轉(zhuǎn)發(fā)數(shù)據(jù)；圖6(b)所示的是啟用QoS路由機制的選路情況，由于QoS路由機制檢測到了客戶端QoS受到鏈路擁塞的影響，所以及時地為客戶端調(diào)整了路徑，視頻服務(wù)選擇了非擁塞路徑S1—S6—S3—S8來傳輸視頻數(shù)據(jù)，而FTP服務(wù)選擇非擁塞路徑S1—S6—S7—S11—S12來傳輸數(shù)據(jù).

Fig. 7 Thoughput changes of client of starting and stopping QoS mechanism圖7 啟動和關(guān)閉QoS路由機制時客戶端吞吐量的變化情況

圖7所示的是客戶端吞吐量的變化情況，通過實驗統(tǒng)計設(shè)定了觸發(fā)重新選路的最低吞吐量閾值為2.5 Mbps，即當(dāng)QoS路由機制檢測到客戶端吞吐量小于2.5 Mbps時，會為客戶端重新選路.圖7(a)所示的是未啟用QoS路由機制時客戶端吞吐量的變化情況，F(xiàn)TP-Loader和Video-Loader分別在18 s和36 s時加入到網(wǎng)絡(luò)中來，造成了FTP客戶端和視頻客戶端的平均吞吐量分別下降到2.13 Mbps和2.06 Mbps，均低于最低吞吐量閾值；圖7(b)所示的是啟用QoS路由機制后客戶端吞吐量的變化情況，當(dāng)FTP-Loader和Video-Loader分別在18 s和36 s時加入到網(wǎng)絡(luò)中來時，F(xiàn)TP客戶端和視頻客戶端的平均吞吐量首先出現(xiàn)了下降，但是當(dāng)下降到閾值2.5 Mbps之后，吞吐量又迅速開始回升.FTP客戶端吞吐量在16 s時開始回升，視頻客戶端吞吐量在44 s時開始回升，并都回升到滿足其各自QoS的需求.因此，從實驗結(jié)果看到，本文所提QoS路由機制能夠檢測到客戶端吞吐量低于閾值并為其重新分配滿足其QoS需求的路徑，使得客戶端的吞吐量得到了回升.

2) 業(yè)務(wù)動態(tài)接入下的性能分析

在流表未溢出的場景下，本文還對動態(tài)QoS路由機制在業(yè)務(wù)動態(tài)接入的情況下進(jìn)行了性能測試，觀察業(yè)務(wù)動態(tài)接入的并發(fā)度與系統(tǒng)吞吐量之間的關(guān)系.當(dāng)QoS路由機制啟動之后會不停地檢測業(yè)務(wù)的動態(tài)接入，我們設(shè)置了每隔10 s向S12動態(tài)接入2個FTP業(yè)務(wù)，QoS路由機制為每批接入的業(yè)務(wù)分配合適的路徑并監(jiān)控接入業(yè)務(wù)的QoS.

圖8所示的是隨著業(yè)務(wù)接入數(shù)量的增加，業(yè)務(wù)并發(fā)度與系統(tǒng)吞吐量變化之間的關(guān)系.從圖8可以看出，隨著業(yè)務(wù)數(shù)量并發(fā)的增加，系統(tǒng)吞吐量呈增長的趨勢.該實驗說明了本文所提QoS保障框架能夠支持業(yè)務(wù)的動態(tài)加入，并同時保障多個業(yè)務(wù)的QoS.

Fig. 8 Relationship between business concurrency and change of throughput of system圖8 業(yè)務(wù)并發(fā)度與系統(tǒng)吞吐量變化的關(guān)系

Fig. 10 Throughput changes of video client in the flow table overflow situation of S2圖10 S2流表溢出時視頻客戶端吞吐量的變化情況

6.2流表溢出場景下的性能分析

在流表溢出的情況下，我們對本文提出的QoS路由機制與文獻(xiàn)[14]提出的QoS路由機制進(jìn)行了性能的比較.圖9和圖10分別所示的是S2流表溢出時QoS路由機制的選路情況和客戶端吞吐量的變化情況.我們設(shè)置S2的流表容量為100條，并向S2的流表中插入100條流表，此時如若再向S2添加流表項則會發(fā)生溢出.文獻(xiàn)[14]提出的QoS路由機制選路的結(jié)果為S1—S2—S3—S8，當(dāng)控制器向S2添加流表項時發(fā)生了溢出，但該QoS路由機制不會檢測到流表溢出的情況，會保持當(dāng)前的選路結(jié)果；而本文提出的QoS路由機制能夠檢測到流表溢出，并及時為客戶端更換了路徑，所選路徑為S1—S6—S3—S8.

Fig. 9 Routing choice comparison of QoS routing mechanism in the flow table overflow situation of S2圖9 S2流表溢出時QoS路由機制的選路情況對比

從圖10中可以看出，對于文獻(xiàn)[14]提出的QoS路由機制，由于S2流表的溢出，S1向S2轉(zhuǎn)發(fā)的數(shù)據(jù)包大量丟失，從而造成了客戶端吞吐量持續(xù)下降并低于閾值，導(dǎo)致QoS得不到保障.然而，本文提出的動態(tài)QoS路由機制及時感知到了流表的使用情況，避開了經(jīng)過流表溢出的交換機的鏈路，選擇的視頻傳輸路徑為S1—S6—S3—S8，能夠維持視頻客戶端正常的吞吐量水平.

7 總 結(jié)

軟件定義的VANET架構(gòu)可以為VANET中各類服務(wù)提供更有效的支持.本文首先設(shè)計了一種面向異構(gòu)多網(wǎng)接入的軟件定義VANET架構(gòu)，完善了現(xiàn)有工作中數(shù)據(jù)平面的設(shè)計；接著以此架構(gòu)為基礎(chǔ)提出了一種流表用量感知的動態(tài)QoS保障框架，并提出了多業(yè)務(wù)流多約束條件下流表用量感知的QoS路由模型，為VANET應(yīng)用服務(wù)提供并發(fā)的動態(tài)QoS路由，能夠滿足多業(yè)務(wù)對各自丟包、時延和吞吐量的要求，還能夠感知交換機流表的使用情況，避免流表溢出對QoS路由的影響，進(jìn)一步提高了網(wǎng)絡(luò)QoS保障的性能.

在保障應(yīng)用QoS的同時，動態(tài)QoS路由機制也帶來了網(wǎng)絡(luò)開銷.網(wǎng)絡(luò)開銷主要包括QoS路由機制啟動時采集網(wǎng)絡(luò)拓?fù)浜玩溌沸畔⑺鶐淼拈_銷以及啟動后定時采集業(yè)務(wù)QoS指標(biāo)和流表用量的開銷.QoS路由機制啟動時，需要采集交換機的基本信息、鏈路的基本信息和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，這部分開銷的大小會隨著交換機和鏈路數(shù)量的增加而增加；當(dāng)QoS路由機制啟動后，會定時(秒級)并發(fā)地采集業(yè)務(wù)的QoS指標(biāo)和流表使用情況，這部分的開銷不僅與交換機、鏈路的數(shù)量有關(guān)，還與系統(tǒng)的并發(fā)負(fù)載能力有關(guān).

在未來的工作中，我們將考慮不同業(yè)務(wù)具有不同的優(yōu)先級，并將其與多業(yè)務(wù)流多約束條件下流表用量感知的QoS路由機制相結(jié)合，進(jìn)一步提升在VANET場景下網(wǎng)絡(luò)對各類應(yīng)用的QoS保障能力.

[1]Cunha F D D, Boukerche A, Villas L, et al. Data communication in VANETs: A survey, challenges and applications[J]. Journal of Biological Chemistry, 2014, 274(39): 27605-27609

[2]Kirkpatrick K. Software-defined networking[J]. Communications of the ACM, 2013, 56(9): 16-19

[3]Zhang Chaokun, Cui Yong, Tang Heyi, et al. State-of-the-art survey on software-defined networking (SDN)[J]. Journal of Software, 2015, 26(1): 62-81 (in Chinese)(張朝昆, 崔勇, 唐翯祎, 等. 軟件定義網(wǎng)絡(luò)(SDN)研究進(jìn)展[J]. 軟件學(xué)報, 2015, 26(1): 62-81)

[4]Ku Ian, Lu You, Gerla M, et al. Towards software-defined VANET: Architecture and services[C]Proc of Ad Hoc Networking Workshop. Piscataway, NJ: IEEE, 2014: 103-110

[5]Li He, Dong Mianxiong, Ota K. Control plane optimization in software-defined vehicular ad hoc networks[J]. IEEE Trans on Vehicular Technology, 2016, 65(10): 7895-7904

[6]He Zongjian, Cao Jiannong, Liu Xuefeng. SDVN: Enabling rapid network innovation for heterogeneous vehicular communication[J]. IEEE Network, 2016, 30(4): 10-15

[7]Truong N B, Lee G M, Ghamri-Doudane Y. Software defined networking-based vehicular ad hoc network with fog computing[C]Proc of 2015 IEEE Int Symp on Integrated Network Management. Piscataway, NJ: IEEE, 2015: 1202-1207

[8]Celenlioglu M R, Mantar H A. An SDN based intra-domain routing and resource management model[C]Proc of IEEE Int Conf on Cloud Engineering. Piscataway, NJ: IEEE, 2015: 347-352

[9]Sun Jie, Li Li, Shen Subin. A routing strategy based on QoS and dynamic load balancing[J]. Computer Technology and Development, 2016, 26(11): 188-194 (in Chinese)(孫杰, 李莉, 沈蘇彬. 一種基于QoS和動態(tài)負(fù)載均衡的路由策略[J]. 計算機技術(shù)與發(fā)展, 2016, 26(11): 188-194)

[10]Egilmez H E, Civanlar S, Tekalp A M. An optimization framework for QoS-enabled adaptive video streaming over openflow networks[J]. IEEE Trans on Multimedia, 2013, 15(3): 710-715

[11]Civanlar S, Parlakisik M, Tekalp A M, et al. A QoS-enabled openflow environment for scalable video streaming[C]Proc of 2010 IEEE GlobeCom Workshops. Piscataway, NJ: IEEE, 2010: 351-356

[12]Adami D. A network control application enabling software-defined quality of service[C]Proc of 2015 IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2015: 6074-6079

[13]Caraguay V, Leonardo N, Fern P, et al. Framework for optimized multimedia routing over software defined networks[J]. Computer Networks, 2015, 92(P2): 369-379

[14]Ongaro F, Cerqueira E, Foschini L, et al. Enhancing the quality level support for real-time multimedia applications in software-defined networks[C]Proc of 2015 Int Conf on Computing, Networking and Communications. Piscataway, NJ: IEEE, 2015: 505-509

[15]Egilmez H E, Dane S T, Bagci K T, et al. OpenQoS: An openflow controller design for multimedia delivery with end-to-end quality of service over software-defined networks[C]Proc of the 2012 Asia Pacific Signal amp; Information Processing Association Annual Summit and Conf. Piscataway, NJ: IEEE, 2012: 1-8

[16]Bueno I, Aznar J I, Escalona E, et al. An OpenNaaS based SDN framework for dynamic QoS control[C]Proc of Future Networks and Services. Piscataway, NJ: IEEE, 2013: 1-7

[17]Wang Wendong, Qi Qinglei, Gong Xiaoyang, et al. Autonomic QoS management mechanism in software defined network[J]. China Communications, 2014, 11(7): 13-23

[18]Georgopoulos P, Elkhatib Y, Broadbent M, et al. Towards network-wide QoE fairness using openflow-assisted adaptive video streaming[C]Proc of the 2013 ACM SIGCOMM Workshop on Future Human-Centric Multimedia Networking. New York: ACM, 2013: 15-20

[19]Open Networking Foundation. Openflow switch specification 1.3.0[EBOL]. [2012-07-25]. https:www.opennetworking.orgimagesstoriesdownloadssdn-resourcesonf-specificationsopenflowopenflow-spec-v1.3.0.pdf

[20]Open Networking Foundation. Openflow switch specification 1.4.0[EBOL]. [2013-11-15]. https:www.opennetworking.orgimagesstoriesdownloadssdn-resourcesonf-specificationsopenflowopenflow-spec-v1.4.0.pdf

[21]Wang Zheng, Crowcroft J. Quality-of-service routing for supporting multimedia applications[J]. IEEE Journal on Selected Areas in Communications, 1996, 14(7): 1228-1234

[22]Sourceforge. Lpsolve: Mixed integer linear programming (MILP) solver[EBOL]. [2016-09-14]. https:sourceforge.netprojectslpsolve

[23]Mininet. The mininet documentation[EBOL]. [2016-08-20]. https:github.commininetmininetwikiDocumentation

[24]A Big Switch Networks Sponsored Community Project. The floodlight documentation[EBOL]. [2016-02-07]. https:floodlight.atlassian.netwikidisplayfloodlightcontrollerGetting+Started

FuBin, born in 1978. PhD. Lecturer in the College of Computer Science and Electronic Engineering, Hunan University. Member of CCF. Her main research interests include wireless communication, software defined networks and Internet of things.

ZhaLijia, born in 1991. Master candidate in the College of Computer Science and Electronic Engineering, Hunan University. His research interest is software defined networks (charlie91825@icloud.com).

LiRenfa, born in 1956. Professor and PhD supervisor in the College of Computer Science and Electronic Engineering, Hunan University. Senior member of CCF. His main research interests include embedded system, cyber-physical system and wireless networks (lirenfa@hnu.edu.cn).

XiaoXiongren, born in 1978. PhD candidate. Lecturer in the College of Computer Science and Electronic Engineering, Hunan University. Member of CCF. His main research interests include dependable distributed systems, embedded systems and computer networks (xxr@hnu.edu.cn).

AFlowTableUsage-AwareQoSRoutingMechanisminSoftwareDefinedVANET

Fu Bin1,2, Zha Lijia1,2, Li Renfa1,2, and Xiao Xiongren1

1(College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082)2(Key Laboratory for Embedded and Network Computing of Hunan Province(Hunan University), Changsha 410082)

VANET can provide a wide range of security and non-security related services. However, the existing VANET is difficult to guarantee the QoS of these services. Software defined networking (SDN), which appears in a systematic way, can control network flexibly and separate the data from the control plane, bringing programming ability to the network. Firstly, this paper designs a software defined VANET architecture for heterogeneous multi network access. Secondly, a flow table usage-aware dynamic QoS provisioning framework is proposed, which allows us to manage the network in a modular way and supports the dynamic entering and exiting of the service flows. Finally, this paper establishes a flow table usage-aware QoS routing model with multi-service flows and multi-constraints. The model considers not only the parameters of link state such as packet loss, delay and throughput, but also the service requirements and the flow table usage, and provides VANET application services for a concurrent dynamic QoS routing. Experiments show that QoS routing mechanism proposed in this paper can meet not only the service requirements of their packet loss, latency and throughput, but also the capable of perceiving the usage of flow table so as to avoid the influence of flow table overflow for QoS routing mechanism, which further improves the performance of network QoS.

software defined networking (SDN); vehicular ad hoc network (VANET); quality of service (QoS); routing model; flow table

2016-12-07；

2017-02-21

國家自然科學(xué)基金項目(61502162)；中央高?；究蒲袠I(yè)務(wù)費專項資金項目(531107040289)

This work was supported by the National Natural Science Foundation of China (61502162) and the Fundamental Research Funds for the Central Universities (531107040289).

(fubin@hnu.edu.cn)

TP393