楊榮寬,張奇支,趙淦森,鄭偉平

1（華南師范大學(xué) 計算機(jī)學(xué)院,廣州 510631）

2（廣州市云計算安全與測評技術(shù)重點(diǎn)實(shí)驗(yàn)室,廣州 510631）

1 引言

1.1 研究背景及介紹

SDN（Software-Defined Networking）是一種將網(wǎng)絡(luò)控制平面和數(shù)據(jù)平面分離、具備可編程性的新型網(wǎng)絡(luò)架構(gòu)[1].基于OpenFlow協(xié)議的SDN架構(gòu)將底層基礎(chǔ)設(shè)施抽象出來,使用戶能夠通過編程來集中控制網(wǎng)絡(luò)轉(zhuǎn)發(fā)行為.當(dāng)網(wǎng)絡(luò)狀態(tài)發(fā)生變化時,SDN控制器可通過下發(fā)新的轉(zhuǎn)發(fā)規(guī)則更新交換機(jī)流表項(xiàng),從而管理整個網(wǎng)絡(luò)狀態(tài).盡管SDN實(shí)現(xiàn)了網(wǎng)絡(luò)的集中控制,但數(shù)據(jù)平面設(shè)備的分布式特性也帶來了許多問題,如交換機(jī)自身安裝流表項(xiàng)的速度、交換機(jī)間的傳輸延遲等.這使得流表項(xiàng)生效時間難以一致,進(jìn)而導(dǎo)致更新不一致,增加了集中管理的難度[2].

目前,我們正在參與一項(xiàng)國家重點(diǎn)研發(fā)計劃子課題的項(xiàng)目研究.該項(xiàng)目的一個主要研究目標(biāo)是在政務(wù)通信網(wǎng)絡(luò)中提出一種能保證數(shù)據(jù)轉(zhuǎn)發(fā)高可靠性、提供細(xì)粒度QoS保障的機(jī)制.而數(shù)據(jù)轉(zhuǎn)發(fā)的可靠性和細(xì)粒度QoS直接依賴于SDN轉(zhuǎn)發(fā)策略的更新一致性.因此,保證SDN流表更新一致,對保證項(xiàng)目中的數(shù)據(jù)轉(zhuǎn)發(fā)高可靠性和細(xì)粒度QoS具有重大意義.本文在此基礎(chǔ)上,研究能保證SDN流表更新一致、數(shù)據(jù)可靠轉(zhuǎn)發(fā)、更新性能好的更新方案.

1.2 SDN流表一致性更新

在SDN網(wǎng)絡(luò)中,當(dāng)交換機(jī)收到一個數(shù)據(jù)報后,它首先查找轉(zhuǎn)發(fā)流表.若有匹配的流表項(xiàng),則執(zhí)行相應(yīng)的動作.否則交換機(jī)會向控制器發(fā)送packetin消息,將報文上報至控制器進(jìn)行處理.控制器處理后,會向交換機(jī)下發(fā)新的轉(zhuǎn)發(fā)流表項(xiàng)指導(dǎo)后續(xù)轉(zhuǎn)發(fā).此外,當(dāng)網(wǎng)絡(luò)狀態(tài)發(fā)生變化時,控制器會主動或被動向交換發(fā)送新的轉(zhuǎn)發(fā)流表項(xiàng),以形成新的轉(zhuǎn)發(fā)路徑[3].

由于數(shù)據(jù)平面的交換機(jī)呈分布式排列,控制器向每臺交換機(jī)下發(fā)新流表的時延會有不同,交換機(jī)內(nèi)部的更新速度也有差異,這會導(dǎo)致新規(guī)則的所有流表項(xiàng)無法同時生效,使數(shù)據(jù)包出現(xiàn)錯誤的轉(zhuǎn)發(fā)處理,引發(fā)數(shù)據(jù)轉(zhuǎn)發(fā)中斷、環(huán)路等問題,影響網(wǎng)絡(luò)流量傳輸?shù)目煽啃院图?xì)粒度QoS的保證.

因此,在新舊規(guī)則的更新過程中,必須要保持流表的一致性更新.即控制器在更新交換機(jī)中的流表項(xiàng)時,那些正在傳輸?shù)臄?shù)據(jù)包在每個交換機(jī)上要么匹配舊規(guī)則流表項(xiàng),要么匹配新規(guī)則流表項(xiàng),不能出現(xiàn)在交換機(jī)A上匹配舊規(guī)則,而在交換機(jī)B上又匹配新規(guī)則的情況.為了更好地說明SDN流表更新不一致性引起的問題,下面以圖1進(jìn)行舉例說明.其中節(jié)點(diǎn)Ni（1≤i≤8）代表交換機(jī),實(shí)線代表舊轉(zhuǎn)發(fā)路徑,虛線代表新轉(zhuǎn)發(fā)路徑.

圖1 路由更新實(shí)例

假設(shè)某時刻SDN控制器同時向各個交換機(jī)下發(fā)更新命令:將轉(zhuǎn)發(fā)規(guī)則更新至新路徑.由于控制器和不同交換機(jī)的傳輸時延差異,交換機(jī)無法同時完成更新.當(dāng)N1完成更新而N8尚未更新時,即N8沒有匹配數(shù)據(jù)流的轉(zhuǎn)發(fā)規(guī)則,則轉(zhuǎn)發(fā)到N8的數(shù)據(jù)流將不知作何處理.如果默認(rèn)動作是丟棄報文,則會引起流中斷.此外,如果交換機(jī)N6更新了而N5尚未更新,就會形成環(huán)路N6→N5→N6.這會長時間占用鏈路直至報文的TTL超時,從而降低鏈路利用率和轉(zhuǎn)發(fā)性能.

通常來說,SDN流表更新出現(xiàn)不一致時,可能會導(dǎo)致網(wǎng)絡(luò)中斷、環(huán)路、安全漏洞等問題.為確保從舊規(guī)則過渡到新規(guī)則期間,網(wǎng)絡(luò)能正確轉(zhuǎn)發(fā)報文,則必須要考慮所有可能出現(xiàn)的中間狀態(tài)及其屬性[4].很明顯,流表的一致性更新,關(guān)系到網(wǎng)絡(luò)配置能否正確實(shí)現(xiàn).

目前,針對SDN流表更新一致性問題,研究者已經(jīng)提出了多種更新方案,如兩階段更新[5]、反向更新[6]、基于分類時序更新[7]、時間觸發(fā)更新[8]、分段更新[9]等.

1.3 相關(guān)工作

為了確保更新無黑洞和無循環(huán)的一致性屬性,Reitblatt等首先提出每流/每包一致性的定義[5],并基于此定義提出了兩階段更新方案進(jìn)行策略轉(zhuǎn)發(fā)更新.

周曄等[10]、齊嬋等[7]在兩階段更新的基礎(chǔ)上分別提出了基于分類和基于分類時序的流表更新一致性方案,核心均在于根據(jù)更新操作類別對交換機(jī)進(jìn)行分類,并按照一定的順序更新規(guī)則.不同的是,分類時序更新增加了對流表項(xiàng)的細(xì)分操作.分類時序更新雖算法簡單,但其根據(jù)嚴(yán)格設(shè)定的順序來更新新舊轉(zhuǎn)發(fā)路徑上的節(jié)點(diǎn),忽略了同時是新舊路徑上的交換機(jī)的情況,存在應(yīng)用場景局限性.此外,不管更新拓?fù)鋸?fù)雜與否,都需要等待一定的端到端最長時延才能進(jìn)行下一階段,方案更新輪次固定,更新時延過長.

基于節(jié)點(diǎn)依賴關(guān)系,Diogo等[6]提出了反向更新方案.該方案雖算法簡單,但其節(jié)點(diǎn)依賴復(fù)雜,也沒有考慮節(jié)點(diǎn)規(guī)則無須更新的情況,嚴(yán)格依據(jù)新規(guī)則轉(zhuǎn)發(fā)路徑從目的節(jié)點(diǎn)遞歸向前更新以避免環(huán)路.因此,更新輪次多,致使更新時延長.另外,Fu等[11]提出雙向更新方案.通過尋找滿足當(dāng)前更新狀態(tài)下其子節(jié)點(diǎn)都已更新至新規(guī)則,或者在最終狀態(tài)下其所有父節(jié)點(diǎn)都已經(jīng)更新至新規(guī)則這兩個條件的節(jié)點(diǎn)依次更新.但每次最多更新2個節(jié)點(diǎn),更新輪數(shù)依然過多.針對依賴問題,Mahajan等[12]提出了最優(yōu)化更新.方案設(shè)定每個節(jié)點(diǎn)都具有3個狀態(tài),在保證無環(huán)的情況下,讓盡可能多的節(jié)點(diǎn)并行更新,從而最大程度減少更新輪次.但此方案每一輪都要全局遍歷以更新節(jié)點(diǎn)狀態(tài),節(jié)點(diǎn)搜索復(fù)雜度高.

1.4 基于分類搜索的無環(huán)更新

針對分類時序更新應(yīng)用場景適用性差和更新時延長、最優(yōu)化更新計算復(fù)雜度高等問題,本文在兩者基礎(chǔ)上,提出基于分類搜索的無環(huán)更新一致性方案（Categorical Search based loop-free Consistent Update scheme,CSCU）.在CSCU方案中,我們設(shè)計了一種交換機(jī)分類模型和一種環(huán)路搜索優(yōu)化模型,其中優(yōu)化模型包括環(huán)路檢測模塊和搜索模塊.兩種模型結(jié)合的更新流程可概括為:分類模型先分析所有節(jié)點(diǎn)的更新前后狀態(tài)并初始化; 再調(diào)用環(huán)路搜索優(yōu)化模型的環(huán)路檢測模塊獲取對應(yīng)節(jié)點(diǎn)集的可更新節(jié)點(diǎn)進(jìn)行更新.最后,在未更新節(jié)點(diǎn)集中循環(huán)調(diào)用優(yōu)化模型的搜索模塊查找滿足條件的可更新節(jié)點(diǎn),直至更新完成.

本文的主要貢獻(xiàn)在于:

（1）改進(jìn)分類時序更新算法中的分類方式,構(gòu)建了一種新的交換機(jī)分類模型,它可以增大應(yīng)用場景的適用性和減少更新等待時延.

（2）在分類和節(jié)點(diǎn)依賴的基礎(chǔ)上,通過分析更新前后轉(zhuǎn)發(fā)規(guī)則的差異,構(gòu)建相應(yīng)的環(huán)路搜索優(yōu)化模型,優(yōu)化了更新的搜索計算復(fù)雜度和更新效率.

（3）在分類模型和環(huán)路搜索優(yōu)化模型的基礎(chǔ)上,提出一種基于分類搜索的更新方案,它具有更新時延短,更新效率高的優(yōu)點(diǎn).

2 SDN系統(tǒng)模型

在本節(jié)中,我們通過構(gòu)建網(wǎng)絡(luò)模型和更新模型對整個SDN網(wǎng)絡(luò)的更新過程進(jìn)行分析.

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

我們將網(wǎng)絡(luò)建模抽象為一個圖G=（N,L）,其中,N是網(wǎng)絡(luò)的節(jié)點(diǎn)集,L是節(jié)點(diǎn)間的鏈路集.為了簡化,本節(jié)假設(shè)網(wǎng)絡(luò)模型為單一控制器C0和多OpenFlow交換機(jī)S={s1,…,sn-1}的模式,圖2展示了本節(jié)所述的網(wǎng)絡(luò)模型.其中,實(shí)線是交換機(jī)間轉(zhuǎn)發(fā)數(shù)據(jù)包的數(shù)據(jù)鏈路,虛線是控制器和OpenFlow交換機(jī)間的控制鏈路（也稱OpenFlow通道）.

圖2 SDN網(wǎng)絡(luò)示意圖

在SDN網(wǎng)絡(luò)中,節(jié)點(diǎn)集N可用數(shù)學(xué)表示為:N=C∪S,其中,C是控制器集,S是交換機(jī)集.鏈路集L可定義為 L=Lcc∪Lcs∪Lss,其中,Lcc指代控制器與控制器之間的鏈路集,Lcs指代控制器和交換機(jī)間的控制鏈路集,Lss指代交換機(jī)和交換機(jī)間的傳輸鏈路.由于模型簡化為單控制器模式,因此集合Lcc為空,集合Lcs的元素個數(shù)為|S|=n-1.

交換機(jī)流表規(guī)則Ri可定義為一個三元組.其中,Pri指代規(guī)則的優(yōu)先級,Mi指代規(guī)則的匹配域集（OpenFlow協(xié)議中,流規(guī)則使用多個字段來匹配數(shù)據(jù)包,包括以太網(wǎng)源地址、以太網(wǎng)目的地址、VLAN ID等）,Ai指代規(guī)則的動作集.如果進(jìn)入網(wǎng)絡(luò)的數(shù)據(jù)包同時匹配多條規(guī)則,則選擇優(yōu)先級最高的規(guī)則,并執(zhí)行相應(yīng)的動作.

2.2 更新模型

網(wǎng)絡(luò)更新是對網(wǎng)絡(luò)配置的更新操作:SDN控制器生成更新消息并將其轉(zhuǎn)發(fā)給交換機(jī),然后交換機(jī)根據(jù)此消息改變它的規(guī)則表.很明顯,更新前后涉及交換機(jī)狀態(tài)的變化.因此可將t時刻的交換機(jī)狀態(tài)定義為[2]:

其中,Ri（t）指在t時刻的交換機(jī)Si的規(guī)則集,Lcsi（t）代表t時刻與Si相關(guān)的控制鏈路集,Lssi（t）代表t時刻與Si相關(guān)的數(shù)據(jù)傳輸鏈路集.

網(wǎng)絡(luò)配置,即網(wǎng)絡(luò)中所有交換機(jī)的狀態(tài)并集,則t時刻的網(wǎng)絡(luò)配置可定義為:

網(wǎng)絡(luò)更新是對網(wǎng)絡(luò)配置的更新操作,即不同時刻的網(wǎng)絡(luò)配置的遷移.因此,網(wǎng)絡(luò)更新可定義為:

其中,Esrc（ti）代表更新前的網(wǎng)絡(luò)配置,Edst（tj）代表更新后的網(wǎng)絡(luò)配置,U指代網(wǎng)絡(luò)配置遷移過程的更新操作集.

基于OpenFlow協(xié)議中流表的組成部分,可以將數(shù)據(jù)包在交換機(jī)中的處理定義為布爾函數(shù):

其中,s代表交換機(jī),p代表數(shù)據(jù)包; X代表匹配域,Y代表處理結(jié)果（包含動作:將數(shù)據(jù)包轉(zhuǎn)發(fā)到其他交換機(jī)或?qū)?shù)據(jù)包上傳至控制器）.

數(shù)據(jù)包從進(jìn)入網(wǎng)絡(luò)到離開網(wǎng)絡(luò),是數(shù)據(jù)包在交換機(jī)間的相互轉(zhuǎn)發(fā)過程.由式（4）可知,數(shù)據(jù)包在網(wǎng)絡(luò)轉(zhuǎn)發(fā)是個迭代處理過程,因此,可將數(shù)據(jù)包在網(wǎng)絡(luò)中的操作以布爾函數(shù)的形式定義為網(wǎng)絡(luò)轉(zhuǎn)發(fā)函數(shù)F（p）:

其中,p指代數(shù)據(jù)包,i,j,k指代交換機(jī)編號（假設(shè)數(shù)據(jù)包在網(wǎng)絡(luò)中的傳輸路徑為i→j→k,即數(shù)據(jù)包p先在交換機(jī)Si被處理,然后根據(jù)定義（4）得到的結(jié)果,將數(shù)據(jù)包轉(zhuǎn)發(fā)到交換機(jī)Sj中進(jìn)行處理,以此類推,直至轉(zhuǎn)發(fā)完成）.

使用πold表示舊數(shù)據(jù)包,則舊數(shù)據(jù)包可定義為:如果一個數(shù)據(jù)包p被尚未更新的交換機(jī)處理,那么它就被標(biāo)記為πold.同理,使用πnew表示新數(shù)據(jù)包,則可定義為:如果一個數(shù)據(jù)包被已更新了的交換機(jī)處理,它將被標(biāo)記為πnew.因此可將網(wǎng)絡(luò)轉(zhuǎn)發(fā)函數(shù)拓展為:

其中,Fnew（p）和Fold（p）代表πnew和πold由新/舊規(guī)則集處理.

包一致性.由網(wǎng)絡(luò)轉(zhuǎn)發(fā)函數(shù)定義可得:每個數(shù)據(jù)包的傳輸函數(shù)應(yīng)該只涉及一個規(guī)則集:F（p）=Fnew（p）或F（p）=Fold（p）,而不能是兩者的混合.

更新持續(xù)時間（Ud）.Ud指控制器發(fā)送第一個更新消息和最后一個交換機(jī)更新完成之間的時間間隔.

更新輪次（Uround）.本節(jié)假設(shè)在單個交換機(jī)上安裝的規(guī)則之間沒有沖突或者依賴關(guān)系,從而可以在單輪消息傳遞中更新交換機(jī)而不影響網(wǎng)絡(luò)一致屬性.Uround指更新過程所需的階段更新次數(shù),在一定條件下,Uround直接影響Ud,兩者成正相關(guān).每輪中,控制器更新一個交換機(jī)子集,并保證以任何順序更新該子集的交換機(jī)都能確保無環(huán)路產(chǎn)生.控制器在確認(rèn)前一輪中選擇的交換機(jī)都已經(jīng)在內(nèi)存中安裝了新的規(guī)則后,再開始新一輪的更新.

節(jié)點(diǎn)操作復(fù)雜度（Ncp）.指更新過程對交換機(jī)流表操作的復(fù)雜程度.流表規(guī)則更新操作類型和操作次數(shù)是Ncp的關(guān)鍵影響因素,會直接影響Ud和更新性能.

本節(jié)模型構(gòu)建主要為了優(yōu)化更新調(diào)度算法,提升更新性能.因此,我們可將本模型的優(yōu)化目標(biāo)和約束問題描述為:

其中,式（7）為優(yōu)化目標(biāo),即通過最大程度的減少更新輪次Uround和降低節(jié)點(diǎn)操作復(fù)雜度Ncp來減少更新持續(xù)時間Ud.式（8）和式（9）為約束問題,其中,式（8）代表更新過程需保證不會引起轉(zhuǎn)發(fā)環(huán)路、式（9）代表更新過程需保持包級一致性.

本模型的難點(diǎn)在于如何設(shè)計更新調(diào)度算法,在保證更新過程無環(huán)路產(chǎn)生、數(shù)據(jù)包轉(zhuǎn)發(fā)保證一致性的前提下,盡可能的減少更新所需時間,提升更新性能.由于單輪更新不會影響網(wǎng)絡(luò)的一致屬性,因此,SDN控制器可協(xié)調(diào)交換機(jī)間的規(guī)則更新,通過設(shè)計更新算法,使更新輪次最小化,減少完成更新的所需時間.已經(jīng)證明,最小化更新輪數(shù)是NP完全問題[13].

3 基于分類搜索的無環(huán)一致性更新方案

3.1 問題描述

定義Pold和Pnew分別代表Esrc（ti）下的數(shù)據(jù)原始傳輸路徑和Edst（tj）下的數(shù)據(jù)最終傳輸路徑,nexthop（s,Pold/Pnew）代表節(jié)點(diǎn)s在路徑Pold或Pnew的下一跳.更新過程中,配置是否更新成功受設(shè)備之間的實(shí)時交互時延、設(shè)備的實(shí)時更新操作所影響,可能會因?yàn)樯鲜鲆蛩貙?dǎo)致網(wǎng)絡(luò)中出現(xiàn)環(huán)路等問題.基于以上定義,可將方案的問題描述為:已知Esrc（ti）和Edst（tj）,通過分析Pold和Pnew上的節(jié)點(diǎn),在滿足式（8）和式（9）的前提下,設(shè)計更新算法,尋找更新輪數(shù)較少、更新性能較優(yōu)的操作集U,求得式（7）的最優(yōu)解.

3.2 基于分類搜索的更新方案

3.2.1 CSCU方案的節(jié)點(diǎn)集合定義

在構(gòu)建模型過程中,本方案基于分類和節(jié)點(diǎn)依賴搜索思想,需要創(chuàng)建和更新以下相關(guān)集合,如表1.其中,Pnew[length-1]指代最終傳輸路徑上的最后一個節(jié)點(diǎn)、Ssubi代表每一輪更新后剩余的待更新節(jié)點(diǎn)集、rmax代表完成整個更新過程所需要的最大更新輪數(shù)、check_loop（s,Pold,Pnew）用于判斷更新節(jié)點(diǎn)s是否引入環(huán)路、judge_allfather（s,Pold,Pnew）用于判斷節(jié)點(diǎn)s的父節(jié)點(diǎn)是否都已經(jīng)更新至新規(guī)則.

表1 相關(guān)節(jié)點(diǎn)集

3.2.2 CSCU方案的流程

先給出節(jié)點(diǎn)依賴關(guān)系的定義:當(dāng)節(jié)點(diǎn)Na必須在節(jié)點(diǎn)Nb更新完成之后才能更新,則節(jié)點(diǎn)Na依賴于節(jié)點(diǎn)Nb.另外,由于目的節(jié)點(diǎn)不涉及規(guī)則更新,定義為不需要更新節(jié)點(diǎn).CSCU方案的更新流程如圖3所示.

圖3 CSCU更新流程

首先,CSCU方案利用節(jié)點(diǎn)分類模型對Esrc（ti）和Edst（tj）進(jìn)行分析,通過對比Pold和Pnew節(jié)點(diǎn)狀態(tài),初始化表1中的節(jié)點(diǎn)集.

分類模型初始化后,執(zhí)行環(huán)路搜索優(yōu)化模型中的第一個模塊.調(diào)用基于拓?fù)渑判蛩惴ǖ沫h(huán)路檢測模塊逐一檢測Snode中的全部節(jié)點(diǎn)—直接給節(jié)點(diǎn)增添新的轉(zhuǎn)發(fā)規(guī)則.如果check_loop（Ni,Pold,Pnew）=True,即不會引入環(huán)路,則將Ni添加到節(jié)點(diǎn)集Ti中（此時i=1）.檢測完畢后,并行更新節(jié)點(diǎn)集Ti和Sdel_old中的節(jié)點(diǎn).其中,對Ti中的節(jié)點(diǎn)實(shí)施以下操作:下發(fā)新規(guī)則替換舊規(guī)則,同時將節(jié)點(diǎn)轉(zhuǎn)移至節(jié)點(diǎn)集Supdated中.對于Sdel_old中的節(jié)點(diǎn),直接刪除對應(yīng)的舊規(guī)則后,移除該節(jié)點(diǎn).舊規(guī)則是否刪除,同樣是判斷一個節(jié)點(diǎn)是否已經(jīng)更新的依據(jù).Sdel_old存儲只需刪除舊規(guī)則的節(jié)點(diǎn),由于節(jié)點(diǎn)規(guī)則失效時間不確定,如果沒有及時刪除Sdel_old中節(jié)點(diǎn)的舊規(guī)則,會影響方案接下來根據(jù)依賴關(guān)系搜索可更新節(jié)點(diǎn)的算法.當(dāng)以上節(jié)點(diǎn)集更新完成,算法繼續(xù).

接著,調(diào)用環(huán)路搜索優(yōu)化模型中的第二個模塊.對Ni∈Snode?Supdated依次搜索可更新節(jié)點(diǎn),將滿足條件Find_father（Ni）=null或judge_allfather（Ni,Pold,Pnew）=True的節(jié)點(diǎn)Ni加入Ti中,前面兩個條件表示當(dāng)前狀態(tài)下的節(jié)點(diǎn)Ni無父節(jié)點(diǎn)或者父節(jié)點(diǎn)都已更新.搜索完后,并行更新Ti的節(jié)點(diǎn),同時將Ti的節(jié)點(diǎn)轉(zhuǎn)移至Supdated中.如果Snode?Supdated≠null,則循環(huán)執(zhí)行搜索.直至Snode?Supdated=null,方案結(jié)束.

后文我們將證明,結(jié)合分類模型和環(huán)路搜索優(yōu)化模型雙模型,CSCU方案能有效提高更新效率,且具有更低的計算復(fù)雜度.

3.2.3 CSCU方案的更新示例

現(xiàn)以圖4所示拓?fù)錇槔?將網(wǎng)絡(luò)抽象為一個點(diǎn)對點(diǎn)有向圖來演示CSCU方案的更新過程.其中,實(shí)線代表網(wǎng)絡(luò)配置更新前數(shù)據(jù)轉(zhuǎn)發(fā)路徑,虛線代表更新后數(shù)據(jù)轉(zhuǎn)發(fā)路徑.更新步驟如圖4所示.

圖4 更新例子

（1）執(zhí)行節(jié)點(diǎn)分類模型初始化集合得:Snode={N1,N2,N3,N4,N6,N7,N9,N11},Sdel_old={N5},Sun={N8,N10},Supdated=null,Ti=null.

（2）調(diào)用環(huán)路搜索優(yōu)化模型的環(huán)路檢測模塊檢測得:T1={N1,N2,N4,N6,N11}.并行更新節(jié)點(diǎn)集Sdel_old和T1中的節(jié)點(diǎn),對s∈T1執(zhí)行新舊規(guī)則替換并將s轉(zhuǎn)移至Supdated中.對s∈Sdel_old執(zhí)行刪除舊規(guī)則操作,并移除節(jié)點(diǎn)s.此時得到Supdated={N1,N2,N4,N6,N11},Sdel_old=null.

（3）然后,調(diào)用搜索模塊從Snode-Supdated依次搜索符合條件的節(jié)點(diǎn)得T2={N3,N7},執(zhí)行更新后,此時得到Supdated={N1,N2,N3,N4,N6,N7,N11}.

（4）循環(huán)搜索得T3={N9},執(zhí)行更新后得Snode={N1,N2,N3,N4,N6,N7,N9,N11}.很明顯,此時Snode-Supdated=null且Sdel_old=null,更新完畢.

3.2.4 與其他方案對比

以圖4為例將CSCU方案與其他方案做比較:

（1）基于分類時序更新[7]:① 控制器將交換機(jī)初始化,分成4類:入口交換機(jī)、新路徑交換機(jī)、舊路徑交換機(jī)、出口交換機(jī).② 更新出口交換機(jī){N10}和新路徑交換機(jī)Snew={N1,N3,N2,N4,N11,N8,N9,N7,N6},執(zhí)行插入待新增流表項(xiàng)操作.③ 等待一個最長端到端時延后,更新入口交換機(jī){N1},執(zhí)行修改流表項(xiàng)操作.④ 等待最長端到端時延,更新舊路徑交換機(jī)Sold={N1,N2,N3,N4,N5,N6,N7,N8,N9}和出口交換機(jī){N10},執(zhí)行刪除流表項(xiàng)操作,全部更新完畢.顯然,在新舊規(guī)則所涉及的交換機(jī)存在復(fù)雜關(guān)聯(lián)時,方案需要在不同階段對大量共同交換機(jī)、不需更新的交換機(jī)進(jìn)行不同的流表操作,增加了交換機(jī)更新操作次數(shù),這會增加更新的等待時延.

（2）反向更新[6]:該方案所有的節(jié)點(diǎn)嚴(yán)格依據(jù)新規(guī)則從目的節(jié)點(diǎn)遞歸向前更新.由于默認(rèn)目的節(jié)點(diǎn)不需更新,因此,所需的更新輪次=新規(guī)則涉及的節(jié)點(diǎn)數(shù)-1.由圖4示例可知,新規(guī)則轉(zhuǎn)發(fā)路徑涉及的節(jié)點(diǎn)數(shù)為10,即需要9輪才能完成更新.

（3）雙向更新[11]:依據(jù)兩個搜索條件得到{（N1,N6）→（N2,N7）→（N3,N9）→（N4,N8）→（N5,N11）},共需要5輪才能完成更新.

（4）最優(yōu)化更新[12]:依次加入新規(guī)則對所有節(jié)點(diǎn)進(jìn)行無環(huán)檢測,找到的依賴森林根節(jié)點(diǎn)有{N1,N2,N4,N5,N6,N11},分別刪除其舊規(guī)則,再通過無環(huán)檢測尋找其子節(jié)點(diǎn),得到依賴樹有:N2→N3,N6→N7→N9,故整個依賴森林為{N1,N2→N3,N4,N5,N6→N7→N9,N11}.其中,依賴森林中依賴樹的最大高度為所需更新輪次,即完成更新共需要3輪.

本文提出的CSCU方案:執(zhí)行分類模型后,通過執(zhí)行環(huán)路搜索優(yōu)化模型的無環(huán)檢測模塊,得到的T1={N1,N2,N4,N6,N11},再循環(huán)執(zhí)行搜索模塊獲得T2={N3,N7},T3={N9}.所以,經(jīng)過3輪即可完成更新.

3.3 CSCU無環(huán)性驗(yàn)證

無環(huán)性是方案的主要研究點(diǎn),證明如下:

（1）首先,環(huán)路搜索優(yōu)化模型中的無環(huán)檢測模塊不會引入環(huán)路.事實(shí)上,在更新過程中,基于拓?fù)渑判虻臒o環(huán)檢測模塊對節(jié)點(diǎn)集Snode中的節(jié)點(diǎn)進(jìn)行檢測,是根據(jù)直接增加新規(guī)則是否會產(chǎn)生環(huán)路來決定.若產(chǎn)生環(huán)路則保持狀態(tài)不變,否則就將它逐一添加進(jìn)節(jié)點(diǎn)集Ti中.然后并行更新Ti和Sdel_old中的節(jié)點(diǎn):對s∈T1執(zhí)行新舊規(guī)則替換并加入Supdated中,對s∈Sdel_old執(zhí)行舊規(guī)則刪除.因?yàn)楣?jié)點(diǎn)只有通過無環(huán)檢測才確定是否更新,并行更新Ti中的節(jié)點(diǎn)的過程顯然不會引入環(huán)路.另外,對s∈Sdel_old執(zhí)行刪除舊規(guī)則的操作,只是釋放相應(yīng)的交換機(jī)內(nèi)存空間,不會引起無環(huán).所以,無環(huán)檢測更新過程不會引入環(huán)路.

（2）其次,環(huán)路搜索優(yōu)化模型中的循環(huán)搜索模塊也不會引入環(huán)路.事實(shí)上,按默認(rèn)方法更新至最終狀態(tài)的路徑是不存在環(huán)路的.現(xiàn)假設(shè)當(dāng)前狀態(tài)下有局部鏈路N1→N2→Ncur,Ncur尚未更新,其父節(jié)點(diǎn)N1,N2都已更新.更新Ncur,形成環(huán)路Ncur→N1→N2→Ncur,而根據(jù)假設(shè),其父節(jié)點(diǎn)都已更新,即整個環(huán)路鏈路涉及的節(jié)點(diǎn)都已更新至新規(guī)則.該環(huán)路是整個更新至最終狀態(tài)的一個局部鏈路,則與最終狀態(tài)下的新規(guī)則中無環(huán)路的矛盾,所以更新Ncur不會引入環(huán)路.循環(huán)搜索更新,直至Snode-Supdated=null時更新完畢,整個更新過程都不會出現(xiàn)環(huán)路.

3.4 相關(guān)研究比較

本節(jié)將從適用性、更新持續(xù)時間Ud、更新節(jié)點(diǎn)操作復(fù)雜度Ncp、更新算法計算復(fù)雜度4個方面進(jìn)行比較.適用性,指方案場景適用范圍.Ud為整個更新過程每個階段所用時間總和,集中體現(xiàn)于更新過程的所需輪次Uround,更新所需輪次越多,等待更新的時間越長,Ud越大.Ncp指更新過程對節(jié)點(diǎn)操作的復(fù)雜程度,集中體現(xiàn)于:需在不同更新階段執(zhí)行不同更新操作的節(jié)點(diǎn)越多、對同一節(jié)點(diǎn)更新操作的次數(shù)越多,更新等待時延就越長,Ud越大.更新算法計算復(fù)雜度,指切換更新規(guī)則過程中相應(yīng)邏輯功能計算的復(fù)雜性.

本節(jié)將本文方案與第2節(jié)的相關(guān)研究進(jìn)行比較,結(jié)果如表2所示.

表2 本文與相關(guān)方案比較

（1）適用性.不管網(wǎng)絡(luò)拓?fù)鋸?fù)雜與否,分類時序更新都依據(jù)新舊轉(zhuǎn)發(fā)路徑上的節(jié)點(diǎn)嚴(yán)格設(shè)定階段進(jìn)行更新.若網(wǎng)絡(luò)配置簡單,使用該方案反而降低更新效率.若配置更新存在大量的共同交換機(jī),則需要分別在不同的更新階段,對同一交換機(jī)進(jìn)行不同的流表操作,更新操作量增加.因此,分類時序存在一定的應(yīng)用場景局限性,適用性較差.本方案在分類初始化基礎(chǔ)上,設(shè)計能減少更新輪數(shù)的環(huán)路搜索優(yōu)化模型,無論拓?fù)浣Y(jié)構(gòu)復(fù)雜與否,本方案更新效率都有保證.

（2）更新持續(xù)時間Ud.分類時序更新設(shè)定固定階段更新,下一個階段的節(jié)點(diǎn)更新必須等待上一個階段的節(jié)點(diǎn)更新完畢才能進(jìn)行,更新輪次固定.若更新配置復(fù)雜,還會因?yàn)榈却f包流出網(wǎng)絡(luò)等待端到端的最長時延,增加更新時間.反向更新和雙向更新節(jié)點(diǎn)依賴復(fù)雜,導(dǎo)致更新輪次多,更新時延高.本方案結(jié)合分類模型和環(huán)路搜索優(yōu)化模型,平均更新輪次接近最優(yōu)化更新,更新持續(xù)時間短.

（3）更新節(jié)點(diǎn)操作復(fù)雜度Ncp.如3.2.4節(jié)所述,更新配置復(fù)雜時,分類時序更新需在不同階段對大量節(jié)點(diǎn)進(jìn)行不同的流表更新操作,大量節(jié)點(diǎn)更新操作次數(shù)多.因此,方案的更新節(jié)點(diǎn)操作復(fù)雜程度高,更新等待的時延長.雖說細(xì)化流表項(xiàng)操作在更新某一階段能使新舊數(shù)據(jù)包并行傳輸,一定程度上降低控制器負(fù)載.但與其產(chǎn)生的等待時延相比,時間開銷更為重要.本方案只需針對相應(yīng)節(jié)點(diǎn)集執(zhí)行相應(yīng)規(guī)則操作,操作復(fù)雜度低,等待時延少,能進(jìn)一步減少Ud.

（4）算法計算復(fù)雜度.假設(shè)使用鄰接矩陣存儲節(jié)點(diǎn)信息.最優(yōu)化更新中,初始化所有節(jié)點(diǎn)狀態(tài)、加入新規(guī)則檢測是否引入環(huán)路都為O（n）,在狀態(tài)轉(zhuǎn)換過程中,更新節(jié)點(diǎn)狀態(tài)和下一輪節(jié)點(diǎn)的判環(huán)操作也都為O（n）.因此,最優(yōu)化更新的時間復(fù)雜度為O（n4）.CSCU方案中,分類初始化和對待更新的節(jié)點(diǎn)判環(huán)操作的總時間復(fù)雜度為O（n2）,搜索可更新的節(jié)點(diǎn)為O（n）,因此總的時間復(fù)雜度為O（n3）.而基于分類時序更新只需遍歷矩陣進(jìn)行分類,然后在不同節(jié)點(diǎn)進(jìn)行更新,時間復(fù)雜度為O（n2）.

4 仿真分析

為了分析比較相關(guān)方案在不同情況下更新的效果,本文基于自主搭建的SDN仿真平臺進(jìn)行模擬實(shí)驗(yàn).平臺所用設(shè)備為Ubuntu 16.04操作系統(tǒng),RYU開源控制器和mininet網(wǎng)絡(luò)仿真器.仿真實(shí)驗(yàn)設(shè)定實(shí)驗(yàn)拓?fù)涔?jié)點(diǎn)數(shù),設(shè)定源點(diǎn)和目的節(jié)點(diǎn).每次實(shí)驗(yàn)通過隨機(jī)更改相鄰節(jié)點(diǎn)的邊權(quán)值來模擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化,相鄰節(jié)點(diǎn)的邊權(quán)值服從（1-1000）的均勻分布.權(quán)值確定后,再通過OSPF算法獲取源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑.

① 關(guān)于更新輪次和更新持續(xù)時間Ud的關(guān)系,在上一節(jié)已經(jīng)有詳細(xì)解釋.在此,通過300次仿真實(shí)驗(yàn)測試,對相關(guān)研究方案每一次實(shí)驗(yàn)的更新輪次進(jìn)行分析對比,結(jié)果如圖5所示.

圖5 不同方案下的更新輪次情況

實(shí)驗(yàn)結(jié)果顯示,反向更新的所需的更新輪次普遍多于其它方案,這是因?yàn)榉聪蚋轮慌c新的轉(zhuǎn)發(fā)規(guī)則相關(guān),更新輪次=新規(guī)則轉(zhuǎn)發(fā)相關(guān)節(jié)點(diǎn)-1.由于分類時序更新嚴(yán)格設(shè)計更新階段,因此更新輪次固定.本方案的更新輪次接近最優(yōu)化更新,比其他方案都少.

② 配置更新交叉程度.指配置更新過程中,同時在新、舊路徑上的交換機(jī)占與更新相關(guān)的交換機(jī)總數(shù)的比例.配置更新交叉程度的大小影響CSCU方案的更新性能.更新過程中,在新路徑上而不在舊路徑上的交換機(jī)數(shù)越多,涉及舊規(guī)則的交換機(jī)就越少,就越難形成回路.因此,更新輪次就越少,更新性能越好.相反則需要更多的輪數(shù)來完成更新.

至此,就配置更新交叉程度對本方案更新輪次的影響進(jìn)行實(shí)驗(yàn)分析.由于交叉程度低的時候形成環(huán)路的可能性低,所以交叉程度為0和25%的結(jié)果參考價值不大.因此本實(shí)驗(yàn)只對交叉程度為50%、75%、100%的情況進(jìn)行實(shí)驗(yàn),結(jié)果如圖6所示.

圖6 CSCU方案在不同配置交叉程度下的更新輪次情況

為了更好的與分類時序更新對比分析,綜合CSCU方案在不同交叉程度更新情況的實(shí)驗(yàn)結(jié)果,求得配置更新不同交叉程度下的平均更新輪次.實(shí)驗(yàn)結(jié)果表明,本方案在配置更新交叉程度為0、50%、75%、100%下的平均更新輪次都比分類時序更新少,結(jié)果如圖7所示,其中,0、50%、75%、100%分別代表CSCU方案的配置更新交叉程度,timing代表分類時序更新.

圖7 不同交叉程度下與分類時序更新的比較

③ 更新過程的節(jié)點(diǎn)操作復(fù)雜度直接體現(xiàn)于對同一交換機(jī)的流表項(xiàng)操作次數(shù)大于1的交換機(jī)數(shù).用num_large_1表示對同一交換機(jī)的流表項(xiàng)操作次數(shù)大于1的交換機(jī)數(shù).顯然num_large_1越大,更新的節(jié)點(diǎn)總操作次數(shù)越多,更新過程的節(jié)點(diǎn)操作復(fù)雜度就越高.針對節(jié)點(diǎn)操作復(fù)雜度,本節(jié)設(shè)計多次實(shí)驗(yàn),假設(shè)實(shí)驗(yàn)的節(jié)點(diǎn)數(shù)固定為20、新舊路徑跳數(shù)相同.對分類時序更新進(jìn)行測試分析,得出num_large_1的平均值隨路徑跳數(shù)變化的情況,實(shí)驗(yàn)結(jié)果如圖8所示.實(shí)驗(yàn)設(shè)定新舊路徑源、目的節(jié)點(diǎn),所以num_large_1≥2.

圖8 不同路徑跳數(shù)的更新節(jié)點(diǎn)操作復(fù)雜度

分析實(shí)驗(yàn)可得,網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)一定的情況下,num_large_1隨著路徑跳數(shù)的增大而增大.即隨著路徑跳數(shù)的增多,同是新舊路徑上的節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)就越多,對所有節(jié)點(diǎn)的總操作次數(shù)就越多.因此,更新過程的節(jié)點(diǎn)操作復(fù)雜度就越高.而本方案經(jīng)分類初始化后,與更新配置復(fù)雜度無關(guān),更新節(jié)點(diǎn)操作復(fù)雜度低.

綜上所述,相較于分類時序更新,基于分類搜索的無環(huán)更新一致性方案有更好的場景適用性、更低的節(jié)點(diǎn)操作復(fù)雜度Ncp和更少的更新輪次Uround,能夠在滿足模型約束條件（8）和（9）的前提下有效減少更新持續(xù)時間Ud、提升更新效率,實(shí)現(xiàn)模型的優(yōu)化目標(biāo).另外,在更新輪次方面,本方案相對于其他相關(guān)研究方案都有著不同方面的性能提升.

5 結(jié)語

本文根據(jù)在研項(xiàng)目的研究目標(biāo),對SDN流表更新一致性的相關(guān)研究成果進(jìn)行了詳細(xì)的研究.并針對基于分類時序更新方案存在應(yīng)用場景適用性差、更新時延長和節(jié)點(diǎn)更新復(fù)雜程度高等問題,提出了一種基于分類搜索的無環(huán)更新方案.隨后,本文通過更新示例的展示,在適用性、更新時間等性能方面對該方案和相關(guān)研究方案進(jìn)行了對比分析.此外,本文對該方案的無環(huán)一致性更新進(jìn)行了理論分析,證明了方案的可行性.最后,通過搭建SDN仿真平臺進(jìn)行了仿真實(shí)驗(yàn).仿真實(shí)驗(yàn)針對更新輪次對該方案與相關(guān)研究方案進(jìn)行了分析對比,也針對不同配置更新交叉程度和節(jié)點(diǎn)操作復(fù)雜度單獨(dú)跟分類時序方案進(jìn)行了對比.仿真結(jié)果表明,CSCU方案具備應(yīng)用場景適用性高、節(jié)點(diǎn)更新操作復(fù)雜度低的優(yōu)點(diǎn),是一種能夠有效的減少更新所需輪次、更新時延和降低計算時間復(fù)雜度的高效率更新方案.