李雅波，姜麗芬，劉 濤，張 棟

（天津師范大學(xué)計算機與信息工程學(xué)院，天津 300387）

軟件定義網(wǎng)絡(luò)（software defined networking，SDN）是當(dāng)今最熱門的網(wǎng)絡(luò)技術(shù)之一，SDN利用分層的思想，將控制平面和數(shù)據(jù)平面相分離，分別部署在獨立的設(shè)備上實現(xiàn)[1].與傳統(tǒng)網(wǎng)絡(luò)技術(shù)相比，SDN有許多優(yōu)點[1]：（1）控制平面統(tǒng)一控制轉(zhuǎn)發(fā)平面上的網(wǎng)絡(luò)設(shè)備，同時向上提供便捷的可編程操作；（2）網(wǎng)絡(luò)運營商和第三方能根據(jù)自身需求開發(fā)新的控制方案，提供全新的網(wǎng)絡(luò)應(yīng)用和服務(wù)；（3）網(wǎng)絡(luò)用戶不必在意底層設(shè)備的技術(shù)細節(jié)，只需通過簡潔的編程操作就能迅速達成目標(biāo)應(yīng)用的需求；（4）SDN可以提供靈活的網(wǎng)絡(luò)資源管理和基于數(shù)據(jù)流的快速靈活的路由配置，能夠自動優(yōu)化網(wǎng)絡(luò)資源的利用.因此，近年來SDN引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注.

SDN需要周期性地進行路由更新，更新執(zhí)行的速度是決定網(wǎng)絡(luò)性能的關(guān)鍵[2]，更新執(zhí)行越慢，傳輸過程中數(shù)據(jù)丟失和造成網(wǎng)絡(luò)擁塞的可能性就越高.因此，路由更新是SDN的關(guān)鍵問題之一，眾多學(xué)者對SDN路由更新方法進行了深入研究[2-15].其中：一類更新方法[2-3]預(yù)先設(shè)定了轉(zhuǎn)發(fā)規(guī)則更新的次序，但這類方法很難適應(yīng)實際數(shù)據(jù)量的動態(tài)特點；文獻[4-5]提出根據(jù)當(dāng)前數(shù)據(jù)流整體狀況進行轉(zhuǎn)發(fā)規(guī)則的更新，但隨著執(zhí)行更新的數(shù)據(jù)流逐漸增加，網(wǎng)絡(luò)性能變差，實驗分析表明[6]，只更新10 kB數(shù)據(jù)流，完成流表更新尚約80 s，而實際中等規(guī)模數(shù)據(jù)中心中數(shù)據(jù)流到達的速度約為1 250~1 667 B/s.文獻[9]針對更新的帶寬開銷和交換機處理延遲等問題，提出基于通配符的請求成本優(yōu)化流統(tǒng)計收集（CO-FSC）方案，該方案通過具有近似因子f的基于舍入的算法來降低帶寬開銷和交換機轉(zhuǎn)發(fā)規(guī)則處理的延遲.文獻[10]提出一種基于時間的更新實用方法，使用三態(tài)內(nèi)容尋址存儲器條目中的時間戳字段，來實現(xiàn)原子束更新，以高精度地協(xié)調(diào)網(wǎng)絡(luò)更新.考慮到網(wǎng)絡(luò)功能的隨機性，文獻[11]對基于馬爾可夫鏈的路由更新算法進行了補充，在更新過程中，數(shù)據(jù)包通過選定路由的傳輸以比較所有可能的替代路由，實現(xiàn)了更新算法的虛擬化服務(wù)，并根據(jù)執(zhí)行的算法為選擇最佳路由提供建議.文獻[12]首次提出了動態(tài)路由更新期間無縫保持一致性的方法，避免了頻繁更新而導(dǎo)致數(shù)據(jù)包到達過程中出現(xiàn)明顯的不規(guī)則延遲或“通信中斷”.上述工作討論了在路由更新中如何保持更新一致性及避免擁塞的問題，而沒有考慮實時更新的問題.文獻[13]探討快速路由更新的問題，利用線性規(guī)劃方法解決流的選取，其缺點是選擇更新數(shù)據(jù)流時沒有考慮當(dāng)前鏈路的負載狀況和公平性，造成數(shù)據(jù)流的選擇不合理，并且線性規(guī)劃算法執(zhí)行速度較慢.文獻[14]提出一種快速路由更新方法，適用于數(shù)據(jù)中心網(wǎng)絡(luò)和廣域網(wǎng)的更新，文獻[15]提出了一種智能規(guī)則劃分方法（SARD）來實現(xiàn)SDN中的快速更新，這2種方法的缺點是更新的數(shù)據(jù)流數(shù)量均較大，可能導(dǎo)致更新延遲過長.

本文提出一種基于模糊理論的數(shù)據(jù)流選擇及路由更新策略（fuzzy quantified based flow selection and route update，F(xiàn)ANS）.首先，使用語言量詞和模糊量化命題確定各數(shù)據(jù)流相對于路由更新標(biāo)準(zhǔn)的符合程度，并結(jié)合鏈路可用容量決定更新的數(shù)據(jù)流，然后，利用鏈路容量和交換機存儲容量限制尋找同步更新的數(shù)據(jù)流，進一步降低路由更新的延遲.仿真實驗結(jié)果表明，本文的路由更新方法具有較優(yōu)越的性能.

1 模型描述

1.1 網(wǎng)絡(luò)模型

設(shè)網(wǎng)絡(luò)結(jié)構(gòu)為G=（S，L），S={s1，s2，…，sn}表示交換機構(gòu)成的集合，L為鏈路集.路由更新的目的是將網(wǎng)絡(luò)從狀態(tài)C={f，Pc（f），f∈T}更新為狀態(tài)C′={f，Pd（f），f∈T}，其中：T為進行路由更新的流的集合，C和C′分別為數(shù)據(jù)流的目前傳輸路徑集合和目標(biāo)傳輸路徑集合，Pc（f）為流f更新之前的傳輸通路，Pd（f）為相應(yīng)更新后的通路.假設(shè)每個數(shù)據(jù)流僅擁有一條傳輸通路.

交換機可以記錄通過它的數(shù)據(jù)流，根據(jù)交換機的統(tǒng)計記錄，控制器可以獲知數(shù)據(jù)流的強度.但在實際情況中，數(shù)據(jù)流的強度可能會在空間和時間上呈現(xiàn)動態(tài)性，這種情況下控制器無法獲知數(shù)據(jù)流的強度.文獻[16]利用鏈路能夠負載數(shù)據(jù)流的數(shù)量進行強度估計，鏈路容量為歷史統(tǒng)計中能夠一次通過的最大流數(shù).本文中，若數(shù)據(jù)流的強度無法獲知，則每隔一段時間記錄該時間段內(nèi)一次通過鏈路e的最大流數(shù)max（Tn，e）.設(shè)F（n）為當(dāng)前通過鏈路e的最大流數(shù)，由指數(shù)加權(quán)平均法有

其中：F（n-1）為上一次統(tǒng)計中一次通過鏈路e的最大流數(shù)，β為權(quán)重.式（1）可寫為

利用指數(shù)加權(quán)平均法預(yù)測最大流數(shù)，既考慮了歷史狀況，又考慮了網(wǎng)絡(luò)當(dāng)前的流量狀態(tài).優(yōu)化算法中通常取 β≥0.9，此時有 β1/(1-β)≈1/e.由于越早的 max（Tn，e）權(quán)重越小，因此每次只需考慮最近1/（1-β）次的數(shù)據(jù)流最大個數(shù)的統(tǒng)計值，從而大大降低了交換機的存儲代價.

1.2 延遲模型

設(shè)di為插入一個轉(zhuǎn)發(fā)規(guī)則的時長，dm為修改一個流轉(zhuǎn)發(fā)規(guī)則的時長.令d（s，Pc（f），Pd（f））為交換機s將流f從Pc（f）更新到Pd（f）的時長，且dm≈10 ms，di≈3.3 ms，則有

2 路由更新過程

2.1 更新數(shù)據(jù)流的選擇

為滿足路由的實時更新，利用人工智能的模糊理論確定各數(shù)據(jù)流相對于更新標(biāo)準(zhǔn)的符合程度.

2.1.1 模糊量詞

令Q、X、A、B分別為模糊語言量詞、論域和2個模糊謂詞，模糊量化命題的形式為“Q XareA”或“Q B XareA”.相關(guān)研究表明[17-18]，模糊量化命題“Q XareA”適用于描述用戶偏好.當(dāng)Q為增量量詞時，模糊量化命題“P：Q XareA”的真值TP是X的子集，

其中μA（x1）≥μA（x2）≥…≥μA（xn）.

2.1.2 基于模糊運算的路由更新排序及選擇根據(jù)如下因素選擇待更新數(shù)據(jù)流：

（1）數(shù)據(jù)流強度（flow intensity），即流數(shù)大小s（f）；

（2）數(shù)據(jù)流當(dāng)前路由的負載（route load），定義為數(shù)據(jù)流當(dāng)前路由上鏈路的最大負載，即其中H為鏈路帶寬；

（3）數(shù)據(jù)流當(dāng)前路由的擁塞程度（route congestion level），即負載較重的鏈路條數(shù)與總鏈路條數(shù)的比值；

（4）選擇優(yōu)先級（select priority），定義為某數(shù)據(jù)流在前m輪被選為待更新數(shù)據(jù)流的次數(shù).

基于以上因素，每個數(shù)據(jù)流f被描述為一個具有4個對的集合{（cfk，ofk），k=1、2、3、4}，其中：cfk是流f的屬性，of k為其具體取值.為選擇待更新數(shù)據(jù)流，定義選擇標(biāo)準(zhǔn)fselect，相應(yīng)的，fselect具有 4 個對（cfk,pfk）,k=1、2、3、4,pfk為對于cfk的選擇偏好.數(shù)據(jù)流f相對于選擇標(biāo)準(zhǔn)fselect的符合程度（記為τ（fselect|f））是模糊量化命題“幾乎所有的偏好都被滿足”的真值.基于式（4），τ（fselect|f）的取值為

其中μp（cfs′）為數(shù)據(jù)流f的屬性對選擇偏好的符合程度,由模糊隸屬函數(shù)求出,且μp（cf1′）≥μp（cf2′）≥…≥μp（cfm′）.各因素的模糊隸屬函數(shù)見圖1.

圖1 模糊隸屬函數(shù)Fig.1 Fuzzy membership functions

得到各數(shù)據(jù)流相對于選擇標(biāo)準(zhǔn)的符合程度后,對于結(jié)果不為零的數(shù)據(jù)流,按照符合程度由大到小排列,形成序列Q.從序列Q的第1個流開始依次選擇,對于流f的路徑集Rf（所有可選路徑的集合）內(nèi)的各條傳輸路徑,計算其上各鏈路的目前容量c（e）,進而得到傳輸路徑P的目前容量C（P）為

從路徑集Rf中選出容量最大的路徑Pmax，由式（7）判斷Pmax能否容納f，若能則將f分配給路徑Pmax.

其中λ為負載參量.上述路徑分配算法的偽代碼如下：

算法目標(biāo)路徑分配

2.2 同步更新數(shù)據(jù)流的挖掘

在保證鏈路無擁塞的前提下,控制器在相應(yīng)的時間段內(nèi)選擇多個流同步更新,可以進一步降低路由更新的延遲.為此,在更新部分數(shù)據(jù)流的基礎(chǔ)上,從鏈路容量限制和交換機流表容量限制2個方面進一步挖掘同步更新的數(shù)據(jù)流.

2.2.1 鏈路容量限制

鏈路容量限制保證同步更新數(shù)據(jù)流時鏈路無擁塞.對于Q中的流f，能夠與該流同步更新的數(shù)據(jù)流滿足

其中：Rnu，e為通過鏈路e且不需要更新路徑的數(shù)據(jù)流集合，Ru，e為源路由通過鏈路e的數(shù)據(jù)流集合，Rt，e為目標(biāo)路由通過鏈路e的數(shù)據(jù)流集合.

2.2.2 交換機流表容量限制

交換機流表容量限制保證在路由更新過程中交換機的流表大小不超過最大容量.設(shè)交換機s的流表容量為CP（s）,若更新后的路由通過交換機s，則其流表大小增加一個規(guī)則占用的空間rule（1）,其大小取決于openflow協(xié)議的版本號.設(shè)Rnu，s為源路由通過交換機s且暫不需要更新的數(shù)據(jù)流集合，Ru，s為源路由通過交換機s且需要更新的數(shù)據(jù)流集合，Rt，s為目標(biāo)路由通過交換機s的數(shù)據(jù)流集合,則有

3 仿真實驗與性能分析

3.1 實驗環(huán)境

使用mininet生成網(wǎng)絡(luò)拓撲,同時使用與文獻[16]相同的網(wǎng)絡(luò)拓撲生成工具，此生成工具是PSGen拓撲生成工具的一個修改版，能夠模擬真實的大規(guī)模網(wǎng)絡(luò)拓撲.實驗網(wǎng)絡(luò)拓撲包含25臺交換機，100條鏈路，6 000個數(shù)據(jù)流，控制器選擇Ryu.模擬的數(shù)據(jù)流遵循標(biāo)準(zhǔn)的2-8原則[19].實驗中設(shè)β=0.9，λ=0.56.

采用2個性能指標(biāo)評價路由更新算法的性能：（1）網(wǎng)絡(luò)負載率（network load ratio），該指標(biāo)用于衡量網(wǎng)絡(luò)負載均衡度；（2）路由更新延遲（route update delay），即更新完成數(shù)據(jù)平面的總時間.

3.2 實驗結(jié)果

將 FANS 與已有算法 EMCF+DS[16]、GRSU[16]和OSPF進行性能比較，本文設(shè)計了4組實驗.

3.2.1 第1組實驗

第1組實驗考察當(dāng)不同數(shù)量的數(shù)據(jù)流存在于網(wǎng)絡(luò)中時，路由更新延遲和網(wǎng)絡(luò)負載率的變化.

由于OSPF算法始終為數(shù)據(jù)流選擇最短路徑，所以這里不考慮它的更新延遲問題，圖2給出了路由更新延遲隨數(shù)據(jù)流數(shù)量的變化情況.

圖2 數(shù)據(jù)流的數(shù)量對路由更新延遲Fig.2 Number of flows vs.route update delay

由圖2可見，F(xiàn)ANS的路由更新延遲要小于EMCF+DS和GRSU，當(dāng)數(shù)據(jù)流數(shù)量為6 000時，F(xiàn)ANS的路由更新延遲分別比EMCF+DS和GRSU低約2.1 s和0.8 s.EMCF+DS每次都要更新網(wǎng)絡(luò)中的全部大象流，因此造成更新延遲較長，GRSU在更新流的選擇時沒有考慮數(shù)據(jù)流的強度以及選擇的公平性等因素，導(dǎo)致更新效果略差.

圖3給出了網(wǎng)絡(luò)負載率隨數(shù)據(jù)流數(shù)量的變化情況.由圖3可見，F(xiàn)ANS的網(wǎng)絡(luò)負載率低于GRSU，略高于EMCF+DS，但FANS的更新延遲遠低于EMCF+DS，綜合考慮，F(xiàn)ANS算法更具優(yōu)勢.另外，OSPF算法的網(wǎng)絡(luò)負載率最高，當(dāng)數(shù)據(jù)流數(shù)量為6 000時，其網(wǎng)絡(luò)負載率約為0.7，這是因為數(shù)據(jù)流數(shù)量增大之后，某些主要鏈路的負載大大加重.

圖3 數(shù)據(jù)流的數(shù)量對網(wǎng)絡(luò)負載率Fig.3 Number of flows vs.network load ratio

3.2.2 第2組實驗

第2組實驗在第1組實驗的基礎(chǔ)上為FANS和GRSU設(shè)定一個最大更新延遲的閾值D0=1.5 s.因為GRSU為交換機設(shè)置了最大更新時延，另外當(dāng)數(shù)據(jù)流量或網(wǎng)絡(luò)規(guī)模較大時，實時更新可能無法保證，所以通過設(shè)定這樣一個閾值來限制更新延遲.圖4和圖5分別給出了此時路由更新延遲和網(wǎng)絡(luò)負載率隨數(shù)據(jù)流數(shù)量的變化情況.

圖4 數(shù)據(jù)流的數(shù)量對路由更新延遲（D0=1.5 s）Fig.4 Number of flows vs.route update delay（D0=1.5 s）

圖5 數(shù)據(jù)流的數(shù)量對網(wǎng)絡(luò)負載率（D0=1.5 s）Fig.5 Number of flows vs.network load ratio（D0=1.5 s）

由圖4可見，由于設(shè)定了閾值，此時數(shù)據(jù)流數(shù)量的增大對FANS和GRSU的更新延遲沒有影響，而EMCF+DS的更新延遲依然會隨數(shù)據(jù)流數(shù)量的增大而增大.對比圖5和圖3，在設(shè)定閾值的情況下，F(xiàn)ANS的網(wǎng)絡(luò)負載率增大約5%，這是因為限定閾值后數(shù)據(jù)流較之前增多，能夠更新的數(shù)據(jù)流數(shù)量比無設(shè)定時少，因此路由更新后的效果變差.由圖4和圖5可以看出，F(xiàn)ANS的網(wǎng)絡(luò)負載率稍高于EMCF+DS，但FANS的更新延遲卻大大低于EMCF+DS.當(dāng)數(shù)據(jù)流數(shù)量為4 000時，F(xiàn)ANS的負載率比EMCF+DS高約5%，但其更新延遲比EMCF+DS低約1.8 s，當(dāng)數(shù)據(jù)流數(shù)量為6 000時，F(xiàn)ANS的更新延遲比EMCF+DS低約2.5 s，而負載率僅高約8%，說明FANS算法通過更新部分數(shù)據(jù)流，達到了負載率和更新延遲的平衡.

3.2.3 第3組實驗

在第3組實驗中，在默認函數(shù)基礎(chǔ)上將大象流的門限進行擴大.當(dāng)大象流的門限逐漸擴大時，圖6和圖7給出了路由更新延遲和網(wǎng)絡(luò)負載率的變化情況.

由圖6可見，隨著大象流門限值成倍增加，F(xiàn)ANS的更新延遲一直低于其他算法.由圖7可見，隨著大象流門限值增加，4種算法的負載率均不斷增大，F(xiàn)ANS的負載率僅高于EMCF+DS，當(dāng)大象流門限為原來的4倍時，F(xiàn)ANS的負載率比EMCF+DS高約5%，但更新延遲卻低約2.5 s，因此FANS的性能更優(yōu).

圖6 大象流門限對路由更新延遲Fig.6 Elephant flow threshold vs.route update delay

圖7 大象流門限對網(wǎng)絡(luò)負載率Fig.7 Elephant flow threshold vs.network load ratio

3.2.4 第4組實驗

在第4組實驗中，固定數(shù)據(jù)流數(shù)量，考察最大更新延遲閾值D0對網(wǎng)絡(luò)負載率的影響.圖8（a）和（b）分別給出了當(dāng)數(shù)據(jù)流數(shù)量為4 000和6 000時，網(wǎng)絡(luò)負載率隨D0的變化情況.

圖8 最大更新延遲閾值對網(wǎng)絡(luò)負載率Fig.8 Update delay constraint vs.network load ratio

由圖8可見，隨著D0的增大，F(xiàn)ANS的負載率逐漸接近EMCF+DS，并且一直低于GRUS.但由于EMCF+DS需要更新全部大象流，因此其更新延遲會遠大于FANS，另外，F(xiàn)ANS采用了模糊邏輯，選擇的數(shù)據(jù)流更加合理，因此負載率略低于GRSU.

3.2.5 負載參量λ對FANS性能的影響

數(shù)據(jù)流更新路徑的選擇與λ有關(guān)，因此FANS的性能受λ影響.圖9給出了數(shù)據(jù)流數(shù)量為4 000和6 000時，不同λ值下FANS的網(wǎng)絡(luò)負載率.由圖9可見，λ=0.6時負載率最低.當(dāng)λ從0.6緩慢增大時，網(wǎng)絡(luò)負載率會逐漸增大，這是因為λ較大會導(dǎo)致一些主要鏈路負載較高，所以網(wǎng)絡(luò)負載率也會增大.當(dāng)λ較小時，鏈路容量沒有得到充分利用，也會造成負載率較高.因此，選擇合適的負載參量對路由更新算法的性能也很重要.

圖9 負載參量對網(wǎng)絡(luò)負載率Fig.9 Network load factor vs.network load ratio

4 結(jié)語

針對軟件定義網(wǎng)絡(luò)中的實時路由更新問題，本文利用人工智能算法的語言量詞和模糊量化命題處理數(shù)據(jù)流的選擇問題，同時考慮流的屬性和各流相對選擇標(biāo)準(zhǔn)的符合程度，盡量選擇符合程度較高的數(shù)據(jù)流進行更新，這種策略可以保證在維持網(wǎng)絡(luò)較小的更新延遲與開銷的情況下，盡量降低網(wǎng)絡(luò)負載率.仿真實驗驗證了本文所提路由更新方法具有較優(yōu)越的性能.