軟件定義網(wǎng)絡(luò)分布式控制信道構(gòu)建協(xié)議

彭 鑫，劉志鵬，李 文，申巧巧，黃 鑫

1(湖南理工學(xué)院 信息與通信工程學(xué)院，湖南 岳陽(yáng) 414000) 2(湖南理工學(xué)院 復(fù)雜工業(yè)物流系統(tǒng)智能控制與優(yōu)化湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 岳陽(yáng) 414000) 3(湖南大學(xué) 嵌入式與網(wǎng)絡(luò)計(jì)算湖南省重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)沙 410082) E-mail：peng-xin@foxmail.com

1 引 言

現(xiàn)有的互聯(lián)網(wǎng)由1969年美國(guó)國(guó)防部遠(yuǎn)景研究規(guī)劃局提出的ARPANET(Advanced Research Project Agency Networks)[1]演化而來(lái).互聯(lián)網(wǎng)以其TCP/IP[2]層次化結(jié)構(gòu)體現(xiàn)出良好的開(kāi)放性，在全世界范圍內(nèi)迅速普及.但是隨著互聯(lián)網(wǎng)規(guī)模的發(fā)展，網(wǎng)絡(luò)負(fù)載不斷增加，網(wǎng)絡(luò)設(shè)備封裝的協(xié)議日益復(fù)雜，導(dǎo)致TCP/IP協(xié)議棧面臨諸多問(wèn)題，從而增加了服務(wù)提供商優(yōu)化維護(hù)網(wǎng)絡(luò)的難度[3].而且，各廠商網(wǎng)絡(luò)設(shè)備的封閉性也讓科研人員不能在真實(shí)網(wǎng)絡(luò)環(huán)境中實(shí)時(shí)部署新的協(xié)議.

針對(duì)這一問(wèn)題，學(xué)術(shù)界和工業(yè)界已經(jīng)開(kāi)展對(duì)未來(lái)互聯(lián)網(wǎng)體系架構(gòu)的相關(guān)研究[4]，具有代表性的有美國(guó)全球網(wǎng)絡(luò)創(chuàng)新環(huán)境 (GENI：Global Environment for Network Innovations)[5]、歐洲未來(lái)互聯(lián)網(wǎng)研究實(shí)驗(yàn)(FIRE：Future Internet Research and Experimentation)[6]和中國(guó)下一代互聯(lián)網(wǎng)示范工程(CNGI：China′s Next Generation Internet)[7].在未來(lái)網(wǎng)絡(luò)體系架構(gòu)研究過(guò)程中，可編程網(wǎng)絡(luò)是重要的發(fā)展方向.軟件定義網(wǎng)絡(luò)(SDN：Software Definednetwork，SDN)[8]則是可編程網(wǎng)絡(luò)的典型方案.

軟件定義網(wǎng)絡(luò)將傳統(tǒng)互聯(lián)網(wǎng)的控制任務(wù)從網(wǎng)絡(luò)節(jié)點(diǎn)中分離，由控制器承擔(dān)，并對(duì)網(wǎng)絡(luò)中分散的控制器進(jìn)行邏輯上的集中管理，通過(guò)控制器對(duì)不同的應(yīng)用實(shí)施不同的服務(wù)規(guī)則.SDN能通過(guò)網(wǎng)絡(luò)虛擬化技術(shù)與現(xiàn)有網(wǎng)絡(luò)無(wú)縫銜接，具有良好的演進(jìn)能力.由于網(wǎng)絡(luò)應(yīng)用的不斷發(fā)展，SDN控制器應(yīng)具有較好擴(kuò)展性才能滿足網(wǎng)絡(luò)服務(wù)的多樣性需求.控制器與網(wǎng)絡(luò)節(jié)點(diǎn)的時(shí)延和管理拓?fù)浣Y(jié)構(gòu)是影響控制器擴(kuò)展性的重要因素[9，10].現(xiàn)有的研究工作中，控制器都使用鏈路層發(fā)現(xiàn)協(xié)議來(lái)發(fā)現(xiàn)控制信道從而形成網(wǎng)絡(luò)管理拓?fù)鋄11].但是鏈路層發(fā)現(xiàn)協(xié)議不能進(jìn)行控制器的負(fù)載分配，只能實(shí)現(xiàn)網(wǎng)絡(luò)狀態(tài)的更新.而網(wǎng)絡(luò)的物理拓?fù)浣Y(jié)構(gòu)是控制器對(duì)網(wǎng)絡(luò)進(jìn)行有效管理的重要基礎(chǔ).所以，要構(gòu)建能夠在控制層發(fā)現(xiàn)物理網(wǎng)絡(luò)信息并實(shí)施管理的通用平臺(tái)，其核心是控制器的控制信道構(gòu)建策略[12].文獻(xiàn)[13]提出了一種有效的分布式控制信道構(gòu)建協(xié)議SDN-RDP，協(xié)議采用異步模式進(jìn)行控制信道的發(fā)現(xiàn)，形成樹(shù)形的控制拓?fù)洌瓿煽刂茖拥膭?chuàng)建，但是，協(xié)議沒(méi)有考慮網(wǎng)絡(luò)鏈路的改變對(duì)創(chuàng)建過(guò)程的影響和控制拓?fù)涞娜哂喽?

本文提出了一種軟件定義網(wǎng)絡(luò)控制拓?fù)浒l(fā)現(xiàn)協(xié)議.第2節(jié)給出網(wǎng)絡(luò)模型；第3節(jié)詳細(xì)闡述提出的SDN資源發(fā)現(xiàn)協(xié)議；第4節(jié)對(duì)提出的協(xié)議進(jìn)行仿真分析；最后是結(jié)論.

2 網(wǎng)絡(luò)模型描述

令G(V，E)表示軟件定義網(wǎng)絡(luò)，其中E為網(wǎng)絡(luò)鏈路集合，V表示網(wǎng)絡(luò)節(jié)點(diǎn)集合.V包含控制器和數(shù)據(jù)節(jié)點(diǎn)，即V=C∪S，C={Ci|i=1，2，…}表示網(wǎng)絡(luò)控制器集合，S={si|i=1，2，…}為數(shù)據(jù)節(jié)點(diǎn)集合.Na表示網(wǎng)絡(luò)節(jié)點(diǎn)a的鄰居集.LCi=(SCi,εCi)表示由控制器Ci形成的控制層，其中SCi?S表示受控于Ci的節(jié)點(diǎn)集，εCi?E表示LCi的控制信道.LC={LC1，LC2，…，LCnC}表示由nC個(gè)控制器構(gòu)成的網(wǎng)絡(luò)全局控制層.協(xié)議由某控制器Ci發(fā)起，在網(wǎng)絡(luò)G(V，E)的拓?fù)浣Y(jié)構(gòu)上，構(gòu)建控制層LC.在構(gòu)建控制拓?fù)渲埃刂破鰿i并不知道數(shù)據(jù)節(jié)點(diǎn)的分布情況，數(shù)據(jù)節(jié)點(diǎn)si也無(wú)法知道受哪個(gè)控制器管理，因此本協(xié)議中節(jié)點(diǎn)的消息只能發(fā)給自己的鄰居，而不能在網(wǎng)絡(luò)中路由.

協(xié)議執(zhí)行過(guò)程由控制器Ci在某時(shí)刻t1發(fā)起.協(xié)議在時(shí)間τ內(nèi)執(zhí)行完畢，協(xié)議結(jié)果反饋時(shí)間t2滿足t1≤t2≤t1+τ.令I(lǐng)=(t1，t2)表示協(xié)議的運(yùn)行時(shí)長(zhǎng).協(xié)議發(fā)現(xiàn)的網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)P(i，j)表示網(wǎng)絡(luò)存在鏈路.考慮到協(xié)議執(zhí)行過(guò)程中，可能出現(xiàn)網(wǎng)絡(luò)環(huán)境改變或節(jié)點(diǎn)故障等情況，協(xié)議發(fā)現(xiàn)的網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)P不能保證與當(dāng)前網(wǎng)絡(luò)狀態(tài)完全一致.為此，對(duì)反饋的拓?fù)鋽?shù)據(jù)P作如下限制.令sender(·)表示協(xié)議消息的發(fā)送方，dest(·)表示接收方，st(·)表示消息發(fā)送時(shí)間，rt(·)表示接收時(shí)間，parent(·，·)表示節(jié)點(diǎn)的某一父節(jié)點(diǎn).如果消息接收失敗，則rt(·)→∞.協(xié)議為消息的確認(rèn)時(shí)間設(shè)定一個(gè)閾值假定節(jié)點(diǎn)i向節(jié)點(diǎn)j發(fā)送消息m.如果消息m的確認(rèn)時(shí)間超過(guò)閾值δ，即rt(m)>δ，則認(rèn)為消息發(fā)送失敗.linkable(i，j，I)表示節(jié)點(diǎn)i和j在時(shí)間間隔I內(nèi)的可達(dá)性，如果用B表示網(wǎng)絡(luò)路徑，則linkable()可定義為：

(1)

如果協(xié)議發(fā)現(xiàn)的拓?fù)湫畔P中存在鏈路TP(i，j)，表示在協(xié)議執(zhí)行時(shí)間內(nèi)，至少有1個(gè)控制消息經(jīng)鏈路發(fā)送，且i和j之間為父子關(guān)系，即：

(2)

(3)

協(xié)議返回的網(wǎng)絡(luò)控制結(jié)構(gòu)應(yīng)當(dāng)屬于網(wǎng)絡(luò)穩(wěn)定條件下的鏈路集合，不會(huì)向控制器返回不存在的控制鏈路，因而返回的控制結(jié)構(gòu)應(yīng)滿足公式(2)和公式(3).

3 控制信道發(fā)現(xiàn)協(xié)議

控制層的建立可以分為兩個(gè)階段，分別是前向階段和后向階段.在前向階段控制器公告自身存在信息，從而發(fā)現(xiàn)能夠進(jìn)行控制信道創(chuàng)建過(guò)程的節(jié)點(diǎn)；在后向階段，創(chuàng)建控制信道的節(jié)點(diǎn)選擇受控制器管理的子節(jié)點(diǎn)，從而形成控制結(jié)構(gòu).協(xié)議總體流程圖如圖1所示.

圖1 協(xié)議流程圖Fig.1 Protocol flow chart

每個(gè)節(jié)點(diǎn)在本地維護(hù)的表單結(jié)構(gòu)如表1所示.

表1 節(jié)點(diǎn)維護(hù)的表單結(jié)構(gòu)Table 1 Form architecture of data nodes

協(xié)議使用的控制消息類(lèi)型主要有如下幾種：

1)前向請(qǐng)求消息(FWReq：Forward Request Message)：控制器通過(guò)FWReq消息向網(wǎng)絡(luò)發(fā)布其存在性消息.數(shù)據(jù)節(jié)點(diǎn)對(duì)收到的FWReq消息進(jìn)行轉(zhuǎn)發(fā).消息結(jié)構(gòu)如表2所示.

2)后向響應(yīng)消息(BWResp：Backward Response Message)：這類(lèi)消息直接用于創(chuàng)建控制信道.節(jié)點(diǎn)通過(guò)BWResp消息請(qǐng)求成為某節(jié)點(diǎn)的子節(jié)點(diǎn)，并發(fā)送BWLeave消息告知鄰居，已受其他節(jié)點(diǎn)管理，消息字段如表3所示.

表2 FWReq消息字段說(shuō)明Table 2 Segments of FWReq message

表3 BWResp消息字段說(shuō)明Table 3 Segments of BWResp message

3)更新消息(BWUpdate)：節(jié)點(diǎn)通過(guò)該消息通知鄰居已發(fā)現(xiàn)離控制器更近的父節(jié)點(diǎn).消息字段如表4所示.

表4 BWUpdate消息字段說(shuō)明Table 4 Segments of BWUpdate message

3.1 前向階段

前向階段由控制器發(fā)起，為資源發(fā)現(xiàn)請(qǐng)求過(guò)程.前向階段主要有兩方面作用.首先，節(jié)點(diǎn)可以生成本地父節(jié)點(diǎn)列表L；其次，為生成以控制器為根的網(wǎng)絡(luò)控制結(jié)構(gòu)提供基礎(chǔ).控制器通過(guò)廣播FWReq消息，告知鄰居節(jié)點(diǎn)其存在信息.通常設(shè)備接入網(wǎng)絡(luò)后，可以通過(guò)交換消息發(fā)現(xiàn)相鄰節(jié)點(diǎn)及相關(guān)鏈路的傳輸時(shí)延.為保證協(xié)議的可靠性，每個(gè)節(jié)點(diǎn)可以記錄H個(gè)FWReq消息的發(fā)送方作為父節(jié)點(diǎn)，H的取值由控制器決定.節(jié)點(diǎn)廣播的FWReq消息包含控制器ID，發(fā)送節(jié)點(diǎn)的ID以及到控制器的時(shí)延.接收到FWReq消息后，節(jié)點(diǎn)首先判斷，是否為收到的第一個(gè)FWReq消息.如果為收到的第一個(gè)FWReq消息，則記錄到控制器的時(shí)延，并將發(fā)送方作為父節(jié)點(diǎn)；如果收到的不是第一個(gè)FWReq，當(dāng)節(jié)點(diǎn)的父節(jié)點(diǎn)少于H個(gè)，消息的ParentID字段不在本地父節(jié)點(diǎn)列表中，且消息的Mdelay時(shí)延字段值小于或等于本地Ndelay字段值，節(jié)點(diǎn)才能將發(fā)送方添加到本地的Parents列表，并記錄其到控制器的時(shí)延.然后節(jié)點(diǎn)將自己的ID寫(xiě)入消息的SenderID字段，并將消息的Mdelay字段增加當(dāng)前鏈路時(shí)延后重新廣播.如果收到的數(shù)據(jù)包Parent字段就是接收節(jié)點(diǎn)本身則不廣播該消息，而是將發(fā)送方加入Children列表.每個(gè)節(jié)點(diǎn)重復(fù)執(zhí)行這一過(guò)程，直至將FWReq消息廣播到全網(wǎng).采用這種傳播機(jī)制，發(fā)送節(jié)點(diǎn)會(huì)收到來(lái)自下游節(jié)點(diǎn)的廣播包，由于每轉(zhuǎn)發(fā)一次，節(jié)點(diǎn)都會(huì)更新消息的父節(jié)點(diǎn)字段，所以通過(guò)返回的消息，節(jié)點(diǎn)不僅可以獲知自己的子節(jié)點(diǎn)，而且事實(shí)上完成對(duì)已發(fā)送消息的確認(rèn).如果節(jié)點(diǎn)的父節(jié)點(diǎn)列表已滿，或已經(jīng)接收到H個(gè)FWReq消息，則不再?gòu)V播該消息，并成為已知(State=known)節(jié)點(diǎn).節(jié)點(diǎn)可以通過(guò)父節(jié)點(diǎn)到控制器的時(shí)延信息發(fā)現(xiàn)到控制器的最佳路徑，同時(shí)可以通過(guò)BWUpdate消息告知其他鄰節(jié)點(diǎn)，自己找到到達(dá)控制器的更好路徑.其鄰居節(jié)點(diǎn)收到BWUpdate消息后，也相應(yīng)修正自己到控制器的時(shí)延，從而引起B(yǎng)WUpdate消息在網(wǎng)絡(luò)中的逐跳轉(zhuǎn)發(fā)，直至到達(dá)無(wú)法更新與控制器時(shí)延的節(jié)點(diǎn)為止.由于本協(xié)議并不要求全網(wǎng)同步，網(wǎng)絡(luò)控制器不能保證同步發(fā)起協(xié)議，如果控制器收到來(lái)自其他控制器的FWReq消息，則繼續(xù)協(xié)議的執(zhí)行.這樣可以確保網(wǎng)絡(luò)的管理任務(wù)分配到各個(gè)控制節(jié)點(diǎn).協(xié)議前向階段算法步驟如下：

算法1.前向階段

1.Controller initialize and broadcast FWreq message mf；

2.For nodeni;

4.SetHops=Hopcount;

5.SetNdelay=Mdelay;

6.Else If(|Parents|

7. addSenderIDtoParents;

8.Hopcount=Hopcount+1;

9.Ndelay=Mdelay+st(mf)-rt(mj);

10.Mdelay=Ndelay;

11. setParentID=SenderID;

12. setSenderID=ni;

13. Broadcastni;

14. End If

15. If(ni=ParentID)

顧盼選的是警，槍法很準(zhǔn)，阮小棉總是剛露個(gè)頭就被他爆掉。他最后點(diǎn)了支煙笑說(shuō)，這兩下子都沒(méi)有，就不要當(dāng)賊。

16. addSenderIDtoChildren;

17. End If

18. If(|Parents|=h||Fsenders=L),Then

19.State=known;

20. End If

21.End If

為保留網(wǎng)絡(luò)節(jié)點(diǎn)的鄰接信息，節(jié)點(diǎn)會(huì)將收到的所有FWReq消息的發(fā)送方添加到本地鄰居列表L，并在后向階段匯聚到控制器.

3.2 后向階段

算法2.后向階段

1.Leaf nodes initialize and send BWresp messagembrBWLeave messagemw;

2.For known nodeI1

4. SetI1.Parents=I1.Parents-mb.SenderID;

5.End If

6.IfParents=?

7.I1.State=isolated;

8.mb.isolated=1;

9. broadcastmb;

10.End If

12.I1.Descendent=I1.DescendentUmb.Controinfo;

13. Setmb.Controinfo=I1.Desendents;

14. Ifp1.Ndelay=min?pn∈Parents(l1)pn.Ndelay,Then

15. Sendmbtop1;

16. SendmwtoL-p1;

17. End If

18.End If

19.If ?,mfwas deadlocked,Then

20. Ift(p1,I1)+p1.Ndelay≥t(pn,ln)+pn.Ndelay+t(I1,In);Then

21. Sendmbtopn;

22. End If

23.End If

3.3 異常處理

控制結(jié)構(gòu)構(gòu)建過(guò)程中有兩種情況會(huì)影響協(xié)議的正常執(zhí)行，分別是轉(zhuǎn)發(fā)沖突和鏈路失效.下面對(duì)兩種情況分別進(jìn)行分析.

3.3.1 轉(zhuǎn)發(fā)沖突

協(xié)議在前向階段某些節(jié)點(diǎn)收到FWReq消息后，可能通過(guò)同一鏈路向?qū)Ψ睫D(zhuǎn)發(fā)該消息，這時(shí)可能導(dǎo)致節(jié)點(diǎn)處于等待來(lái)自對(duì)方響應(yīng)的死鎖狀態(tài).針對(duì)這一問(wèn)題，協(xié)議在后向階段進(jìn)行如下判斷.對(duì)于節(jié)點(diǎn)i和j，可通過(guò)同一鏈路轉(zhuǎn)發(fā)或接收FWReq消息.不失一般性，令Cm,Cl∈C為控制器，pi和pj分別表示節(jié)點(diǎn)i和j的父節(jié)點(diǎn)，t(·,·)表示鏈路時(shí)延.對(duì)于節(jié)點(diǎn)i，如果有t(pi,Cm)+t(i,pi)≤t(pj,Cl)+t(j,pj)+t(i,j)，則表示i經(jīng)過(guò)父節(jié)點(diǎn)pi到達(dá)控制器Cm的時(shí)延比經(jīng)過(guò)j到達(dá)控制器Cl的時(shí)延更短，無(wú)需通過(guò)j到達(dá)控制器.如果當(dāng)時(shí)節(jié)點(diǎn)j向i發(fā)送的FWReq消息失敗，對(duì)節(jié)點(diǎn)i和j之間的關(guān)系無(wú)任何影響.如果節(jié)點(diǎn)i發(fā)現(xiàn)t(pi,Cm)+t(i,pi)>t(pj,Cl)+t(i,j)，則意味著通過(guò)j到達(dá)控制器Cl的時(shí)延比到達(dá)Cm的時(shí)延要小.此時(shí)，i直接將j加入自己Parents列表，并繼續(xù)執(zhí)行后向階段.如果節(jié)點(diǎn)i發(fā)現(xiàn)t(pj,Cl)+t(j,pj)≥t(pi,Cm)+t(i,pi)+t(i,j)，說(shuō)明節(jié)點(diǎn)j通過(guò)i到達(dá)控制器Cm的時(shí)延較小，因而在后向階段，節(jié)點(diǎn)i會(huì)等待來(lái)自j的加入請(qǐng)求；如果超時(shí)，節(jié)點(diǎn)i會(huì)認(rèn)為j找到了更短的控制路徑，因而不會(huì)等待來(lái)自j的消息.

通過(guò)上述判定準(zhǔn)則，節(jié)點(diǎn)可以發(fā)現(xiàn)經(jīng)過(guò)哪個(gè)鄰居到達(dá)控制器的時(shí)延較小.無(wú)需額外的通信過(guò)程即可避免鏈路沖突造成的死鎖.

3.3.2 鏈路失效

網(wǎng)絡(luò)節(jié)點(diǎn)故障或線路中斷都會(huì)造成鏈路失效的情況.鏈路失效可能導(dǎo)致上層節(jié)點(diǎn)無(wú)法接收下層節(jié)點(diǎn)的消息.本協(xié)議中對(duì)節(jié)點(diǎn)Parents字段長(zhǎng)度的限制，實(shí)際上對(duì)網(wǎng)絡(luò)的冗余度給出了約束.對(duì)于冗余度k較小的網(wǎng)絡(luò)，鏈路失效將嚴(yán)重影響控制信道的建立.而冗余度k較大的網(wǎng)絡(luò)，則對(duì)鏈路失效表現(xiàn)出更好的健壯性.為避免這種情況，節(jié)點(diǎn)收到來(lái)自子節(jié)點(diǎn)第一個(gè)響應(yīng)消息后便激活一個(gè)計(jì)時(shí)器，計(jì)時(shí)器到期后便繼續(xù)向上層節(jié)點(diǎn)匯聚網(wǎng)絡(luò)控制結(jié)構(gòu)信息，而不會(huì)無(wú)限制等待失效鏈路的消息.計(jì)時(shí)器的時(shí)長(zhǎng)需要合理選擇，等待時(shí)間過(guò)短可能來(lái)不及匯總?cè)孔庸?jié)點(diǎn)的消息，時(shí)間過(guò)長(zhǎng)又影響協(xié)議的收斂時(shí)間.令二元組P(j，i)表示節(jié)點(diǎn)j的第i個(gè)父節(jié)點(diǎn)，并且到控制器的跳數(shù)為HopsP(j，i).則j經(jīng)過(guò)P(j，i)到達(dá)控制器的跳數(shù)為HopsP(j，i)+1.maxh表示控制器與最遠(yuǎn)節(jié)點(diǎn)的跳數(shù)，maxt表示與最遠(yuǎn)節(jié)點(diǎn)的時(shí)延.maxh和maxt可以由控制器通過(guò)FWreq消息的Maxdist和Mdelay字段確定.則計(jì)時(shí)器時(shí)長(zhǎng)

(4)

如果失效的鏈路過(guò)多，節(jié)點(diǎn)無(wú)法向父節(jié)點(diǎn)反饋消息，則進(jìn)入isolated狀態(tài).進(jìn)入isolated狀態(tài)的父節(jié)點(diǎn)向鄰居廣播將BWresp消息的Isolated字段置1并向鄰居廣播，收到該消息的鄰居會(huì)將進(jìn)入isolated模式的節(jié)點(diǎn)從自己的Parents列表中刪除.如果節(jié)點(diǎn)i是j的父節(jié)點(diǎn).當(dāng)i進(jìn)入isolated狀態(tài)，j將i從其Parents列表中刪除，如果刪除后Parents列表為空，則j也進(jìn)入isolated模式.

4 協(xié)議分析

對(duì)于協(xié)議的正確性，本文要求協(xié)議返回的控制拓?fù)浣Y(jié)構(gòu)不能包含任何不存在的通信鏈路和故障節(jié)點(diǎn)，即返回的控制結(jié)構(gòu)所包含的鏈路在協(xié)議執(zhí)行周期內(nèi)，均保證至少有一個(gè)消息通過(guò).據(jù)此要求，給出如下定理：

定理1.協(xié)議返回的網(wǎng)絡(luò)控制拓?fù)浣Y(jié)構(gòu)滿足公式(2)和公式(3)的要求.

證明：利用反證法.首先考慮節(jié)點(diǎn)處于非isolated模式.如果網(wǎng)絡(luò)物理狀態(tài)穩(wěn)定，節(jié)點(diǎn)鏈路要么存在(連通)，要么不存在(中斷).本協(xié)議的前向和后向過(guò)程通過(guò)FWreq消息和BWresp消息建立節(jié)點(diǎn)間的父子關(guān)系和控制結(jié)構(gòu)，確保所有節(jié)點(diǎn)對(duì)控制器來(lái)說(shuō)都是可達(dá)的.如果不滿足公式(2)，就表示存在穩(wěn)定鏈路且為父子關(guān)系的不包含在拓?fù)湫畔⒅校鶕?jù)公式(3)可知，節(jié)點(diǎn)i和j是不可達(dá)的或不是父子節(jié)點(diǎn)關(guān)系，顯然矛盾.

當(dāng)節(jié)點(diǎn)處于isolated狀態(tài).如果鏈路穩(wěn)定，且i為控制器可達(dá)，則i可以收到j(luò)的消息.當(dāng)j的父節(jié)點(diǎn)失去響應(yīng)，進(jìn)入isolated模式，則j通過(guò)鏈路將拓?fù)湫畔U(kuò)散給i，而i是控制器可達(dá)的，并成為j的父節(jié)點(diǎn)，所以j也可達(dá).TP(i，j)仍然是控制拓?fù)涞囊徊糠郑瞎?2)要求.證畢.

5 仿真實(shí)驗(yàn)

本節(jié)通過(guò)OMNET++*www.omnetpp.org對(duì)提出的協(xié)議進(jìn)行仿真分析，并與文獻(xiàn)[13]協(xié)議進(jìn)行了對(duì)比.在15*15km的區(qū)域內(nèi)隨機(jī)生成不同規(guī)模的網(wǎng)絡(luò).網(wǎng)絡(luò)鏈路容量為100-1000 Mbps.

首先使用4個(gè)控制器的個(gè)數(shù)，在50到400個(gè)節(jié)點(diǎn)規(guī)模的網(wǎng)絡(luò)上，選擇不同的連通度水平，比較節(jié)點(diǎn)平均消息個(gè)數(shù)，結(jié)果如圖2所示.從圖中不難看出，在連通度不變的情況下，網(wǎng)絡(luò)規(guī)模越大平均每個(gè)節(jié)點(diǎn)處理的控制消息數(shù)量也基本保持不變，當(dāng)連通度增加時(shí)，節(jié)點(diǎn)消息開(kāi)銷(xiāo)顯著增加.這是由于當(dāng)連通度一定時(shí)，前向階段的節(jié)點(diǎn)發(fā)現(xiàn)過(guò)程消息開(kāi)銷(xiāo)主要取決于鄰節(jié)點(diǎn)數(shù)目，也就是由連通度決定.在后向階段，節(jié)點(diǎn)選擇父節(jié)點(diǎn)，并告知鄰節(jié)點(diǎn)自身的選擇消息，該過(guò)程同樣受連通度的制約.圖3顯示在相同條件下協(xié)議的計(jì)算時(shí)間開(kāi)銷(xiāo).從圖中不難看出，隨著網(wǎng)絡(luò)連通度的增加，協(xié)議的時(shí)間開(kāi)銷(xiāo)有逐漸降低的趨勢(shì).此外，網(wǎng)絡(luò)規(guī)模越大，協(xié)議的時(shí)間開(kāi)銷(xiāo)也越大.這是因?yàn)閰f(xié)議產(chǎn)生的控制結(jié)構(gòu)以控制器為根，當(dāng)網(wǎng)絡(luò)中連通度水平增加時(shí)，網(wǎng)絡(luò)平均路徑長(zhǎng)度在減小，協(xié)議消息可以快速收斂于控制器，從而縮短協(xié)議的執(zhí)行時(shí)延.而當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，雖然平均每個(gè)節(jié)點(diǎn)處理的控制消息個(gè)數(shù)相同，但是由于網(wǎng)絡(luò)規(guī)模擴(kuò)大，消息路徑增加，協(xié)議總的時(shí)間開(kāi)銷(xiāo)也會(huì)增大.

圖2 不同網(wǎng)絡(luò)規(guī)模條件下的平均消息開(kāi)銷(xiāo)Fig.2 Messageoverheadinvariousnetworkscale圖3 不同網(wǎng)絡(luò)規(guī)模條件下的協(xié)議時(shí)間開(kāi)銷(xiāo)Fig.3 Timeoverheadinvariousnetworkscale

在200個(gè)節(jié)點(diǎn)規(guī)模條件下，改變網(wǎng)絡(luò)的連通度水平，比較了協(xié)議在不同控制器個(gè)數(shù)下的消息和時(shí)間開(kāi)銷(xiāo).軟件定義網(wǎng)絡(luò)控制器通常是一對(duì)多的控制形式，為了確保網(wǎng)絡(luò)配置的實(shí)時(shí)性，往往根據(jù)網(wǎng)絡(luò)規(guī)模選擇不同的控制器個(gè)數(shù)，所以，本實(shí)驗(yàn)分別使用1到6個(gè)控制器，進(jìn)行性能對(duì)比.圖4顯示在網(wǎng)絡(luò)規(guī)模和連通度水平不變的情況下，隨著控制器個(gè)數(shù)增加，節(jié)點(diǎn)的平均消息開(kāi)銷(xiāo)保持一致.當(dāng)連通度增加時(shí)，節(jié)點(diǎn)的平均消息開(kāi)銷(xiāo)則相應(yīng)增加.這是由于在前向階段和后向階段協(xié)議的處理機(jī)制均受鄰節(jié)點(diǎn)的影響，連通度增加時(shí)處理的消息個(gè)數(shù)也相應(yīng)增加.圖5顯示相同條件下的協(xié)議時(shí)間開(kāi)銷(xiāo).從圖中不難看出，隨著控制器的增多協(xié)議的時(shí)間開(kāi)銷(xiāo)有降低的趨勢(shì)，但是當(dāng)連通度降低時(shí)，時(shí)間開(kāi)銷(xiāo)相應(yīng)增大.因?yàn)楫?dāng)控制器增多時(shí)，節(jié)點(diǎn)可以選擇距離較近的控制加入，降低了時(shí)延，而當(dāng)連通度降低，雖然節(jié)點(diǎn)的平均消息開(kāi)銷(xiāo)降低，但是消息向控制器的收斂速度變慢，所以協(xié)議時(shí)間開(kāi)銷(xiāo)也相應(yīng)增大.

圖4 不同控制器個(gè)數(shù)條件下的平均開(kāi)銷(xiāo)Fig.4 Messageoverheadindifferentcontrollernumber圖5 不同控制器條件下的協(xié)議時(shí)間開(kāi)銷(xiāo)Fig.5 Timeoverheadindifferentcontrollernumber

為評(píng)價(jià)協(xié)議在鏈路出現(xiàn)故障條件下的性能，在400個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，確定連通度，在不同的鏈路中斷概率條件下與SDN-RDP協(xié)議對(duì)比了控制拓?fù)涞钠骄?jié)點(diǎn)距離，結(jié)果如圖6議的平均節(jié)點(diǎn)距離均增加，但是本文協(xié)議表現(xiàn)要優(yōu)于SDN-RDP協(xié)議.這是由于隨著節(jié)點(diǎn)故障率的增加，協(xié)議只能尋求次優(yōu)路徑作為控制信道，因而導(dǎo)致控制拓?fù)淦骄嚯x的增大，當(dāng)鏈路出現(xiàn)中斷時(shí)，本文協(xié)議會(huì)改變節(jié)點(diǎn)狀態(tài)，并將狀態(tài)信息向子節(jié)點(diǎn)反饋，使其尋找更佳控制信道，而SDN-RDP協(xié)議在鏈路中斷條件下，由當(dāng)前結(jié)點(diǎn)繼續(xù)發(fā)現(xiàn)次優(yōu)控制信道.

圖6 在不同鏈路中斷率條件下的協(xié)議性能對(duì)比Fig.6 Average path length in various link terminate rate

6 結(jié) 論

本文提出了一種軟件定義網(wǎng)絡(luò)分布式控制拓?fù)錁?gòu)造協(xié)議.控制拓?fù)涞臉?gòu)建分為兩個(gè)階段，首先由控制器發(fā)起網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)過(guò)程，并將節(jié)點(diǎn)的時(shí)延和鄰接關(guān)系保存在本地節(jié)點(diǎn)中，然后，從葉子節(jié)點(diǎn)開(kāi)始，根據(jù)發(fā)現(xiàn)的局部網(wǎng)絡(luò)拓?fù)鋭?chuàng)建以控制器為根，具有最小延遲的樹(shù)形控制拓?fù)洌M(jìn)而形成控制層.協(xié)議采用異步工作方式，無(wú)需進(jìn)行網(wǎng)絡(luò)全局初始化，也無(wú)需全局網(wǎng)絡(luò)信息.此外，考慮到協(xié)議執(zhí)行過(guò)程中的鏈路故障問(wèn)題，協(xié)議采用了故障處理機(jī)制，盡量保證控制拓?fù)涞耐暾?仿真結(jié)果顯示，提出的協(xié)議能夠有效地完成軟件定義網(wǎng)絡(luò)的控制拓?fù)鋭?chuàng)建過(guò)程.

[1] O′N(xiāo)eill J E.The role of ARPA in the development of the ARPANET，1961-1972[J].IEEE Annals of the History of Computing，1995，17(4)：76-81.

[2] Behrouz A.Forouzan，Sophia Chung Fegan.TCP/IP protocol suite[M].New York，USA，McGraw-Hill Higher Education，2002.

[3] McKeown N，Anderson T，Balakrishnan H，et al.Open-Flow：enabling innovation in campus networks[J].ACM Sigcomm Computer Communication Review，2008，38(2)：69-74.

[4] Lin Chuang，Jia Zi-xiao，Meng Kun.Research on adaptive future internet architecture[J].Chinese Journal of Computers，2012，35(6)：1077-1093.

[5] Surhone L M，Tennoe M T，Henssonow S F.Global environment for network innovations[M].London，UK，Betascript Publishing，2010.

[6] Gavras A，Karila A，F(xiàn)dida S，et al.Future internet research and experimentation：the FIRE initiative[J].ACM Sigcomm Computer Communication Review，2007，37(3)：89-92.

[7] Wu J，Wang J H，Yang J.CNGI-CERNET2：an IPv6 deployment in China[J].Acm Sigcomm Computer Communication Review，2011，41(2)：48-52.

[8] Hu F，Hao Q，Bao K.A survey on software-defined network and OpenFlow：from concept to implementation[J].IEEE Communications Surveys & Tutorials，2014，16(4)：2181-2206.

[9] Hassas S，Tootoonchian A，Ganjali Y.On scalability of softwaredefine networking[J].IEEE.Communication Magazine，2013，51(2)，136-141.

[10] Reitblatt M，F(xiàn)orter N，Rexford J，et al.Consistent updates for software-defined networks：Change you can believe in![C].Proc.ofthe 10th ACM Workshop on Hot Topics in Networks.New York，USA.ACM，2011：1-6.

[11] Wang Qiang.Network resource discovery in software defined network and networking application[D].Beijing：Beijing University of Posts and Telecommunications，2014.

[12] Nunes B A A，Mendonca M，Nguyen X N，et al.A survey of software-defined networking：Past，present，and future of programmable networks[J].IEEE Communications Surveys & Tutorials，2014，16(3)：1617-1634.

[13] Jimenez Y，Cervello-Pastor C，Garcia A.Dynamic resource discovery protocol for software defined networks[J].IEEE Communications Letters，2015，19(5)：743-746.

附中文參考文獻(xiàn)：

[4] 林 闖，賈子驍，孟 坤.自適應(yīng)的未來(lái)網(wǎng)絡(luò)體系架構(gòu)[J].計(jì)算機(jī)學(xué)報(bào)，2012，35(6)：1077-1093.

[11] 王 強(qiáng).軟件定義網(wǎng)絡(luò)資源發(fā)現(xiàn)及組網(wǎng)應(yīng)用研究[D].北京：北京郵電大學(xué)，2014.