虛擬化光無線融合接入網多路徑可靠傳輸機制

鄒 虹，陳 霄

(重慶郵電大學 光通信與網絡重點實驗室，重慶 400065)

光無線(Fiber-Wireless， FiWi)融合接入網是由前端無線網狀網(Wireless Mesh Network，WMN)和后端無源光網絡(Passive Optical Network， PON)組成[1]，具有PON的高帶寬、低損耗、傳輸穩定和WMN的易部署、支持移動性等優點，能夠以更加靈活的方式為用戶提供更高質量的接入服務．隨著FiWi網絡規模的逐步擴大，網絡承載的業務種類也更加多樣化，這些都對FiWi接入網的可靠性設計提出了更高的技術要求[2-3]．因此，設計合理的可靠性保障機制，在保證網絡可靠性的同時減少預留資源使用，提高網絡資源利用率，成為FiWi網絡的一大研究熱點[4]．

近年來，FiWi接入網中業務的可靠性傳輸問題受到廣泛關注．文獻[5]提出一種基于輔助圖的保障機制，解決了故障恢復過程中最大流最小跳問題，提高了資源利用率．文獻[6]對光網絡單元(Optical Network Unit， ONU)故障級的恢復路由進行了改進，通過建立備用無線路徑以確保故障ONU到其可替代ONU之間存在有效路徑．以上機制在一定程度上提高了業務傳輸的可靠性，但數據轉發路徑均由本地節點獲知的部分網絡信息決定，無法根據全局節點狀態綜合選擇最優路徑，導致時延增大，影響業務質量．文獻[7]利用網絡虛擬化在控制平面完成對拓撲路徑及虛擬節點的最優分配利用，但是其采用加權輪詢算法對資源進行調度，并沒有利用虛擬化的全局視角優勢對不同服務質量(Quality of Service， QoS)需求的數據流采用不同的權重分配方法．文獻[8]提出多路徑映射，將虛擬鏈路映射到多條物理路徑上，提高了網絡資源利用率．但其不區分業務大小，將業務全部通過多路徑傳輸，增大了額外開銷，無法均衡鏈路負載與鏈路傳輸開銷之間的關系．文獻[9]通過對鏈路采用全備份保護，雖然生存性得到了保障，但備份資源在主鏈路無故障的狀況下長期處于閑置狀態，導致了資源浪費．

針對上述問題，筆者在網絡虛擬化的基礎上綜合考慮節點和鏈路的資源利用率及多徑傳輸開銷，提出一種按比例分配備份資源的多路徑可靠虛擬網絡映射(Multipath Reliable Virtual Network Embedding， MRVNE)算法．首先根據節點及鏈路的總資源與可用資源的比值選擇節點及鏈路，有效保障了資源的負載均衡．其次，預留虛擬鏈路需求資源的一部分作為備份，提高了單鏈路故障的生存性及多鏈路故障狀況下的高可靠性．最后，對網絡資源需求不同的業務采用不同的方式進行資源分配，避免了對所有業務都進行多路徑傳輸造成的資源競爭，減少了額外時延，提高了網絡服務性能．

1 FiWi資源虛擬化

網絡虛擬化技術將數據傳輸平面和控制平面分離，打破了物理網絡和業務之間的強耦合．應用虛擬化方法對FiWi接入網進行資源抽象，使控制平面對整個網絡資源進行集中控制調配．與傳統FiWi網絡相比，控制平面可以更加準確地獲知節點和鏈路容量、當前負載及節點、鏈路故障情況等參數，進而更加合理地實現數據分流及多路徑選擇，同時有效避開網絡中的故障節點和鏈路，極大地提高了網絡資源利用率及傳輸可靠性[10]．

FiWi接入網虛擬化的過程就是將網絡的物理資源抽象成虛擬資源的過程．通過抽象物理節點和鏈路ID、位置、功能屬性、非功能屬性等資源，屏蔽FiWi接入網中光域和無線域拓撲結構、鏈路帶寬等網性能的差異．圖1為融合網絡虛擬化的整體架構，文中將虛擬化FiWi分為3層: 基礎設施層(InFrastructure， InF)、虛擬化管理層(Virtualization Management， VM)以及網絡服務層(Service Provider， SP)．其中InF層負責部署、管理和維護底層物理網絡資源，主要包括光鏈路終端(Optical Linear Terminal， OLT)、ONU、無線路由器、鏈路等，通過虛擬化技術將底層物理資源抽象成功能實體為上層提供統一編程接口，屏蔽底層基礎設施的差異．VM層負責組建虛擬網絡并提供優化管理、資源回收等服務．SP層根據服務請求的特點生成面向虛擬化管理層的虛擬網請求．

圖1 融合網絡虛擬化模型

設備供應商作為基礎設施層，其功能是為虛擬化管理層提供物理網絡資源，并將資源信息抽象為加權無向圖GS= (NS，ES)的方式同步到虛擬化管理層，其中，NS表示所有物理設備的集合，ES表示所有物理鏈路的集合;虛擬化管理層將抽象得到的虛擬資源表示為GV= (NV，EV)，進而管理虛擬資源．其中，NV表示所有虛擬節點的集合，EV表示所有虛擬鏈路的集合; 業務提供商作為網絡服務層負責接收業務請求，當有業務到達時，SP根據業務特點生成面向虛擬化管理層的虛擬網請求，VM根據虛擬網請求組建虛擬網絡．然后將組建好的虛擬網絡反饋給SP．最后，通過開放的編程接口定制路由協議，將虛擬網絡映射到物理網絡進行傳輸．

2 最小化備份資源的多路徑傳輸算法

2.1 多路徑選取數學模型

網絡虛擬化的資源集中控制及屏蔽異構性等優勢為融合網絡的多路徑選擇提供了更加準確的網絡狀態信息[11]．為有效減輕無線域網絡對FiWi接入網吞吐量的限制，筆者提出一種線性優化算法MRVNE-OP，將業務在無線側通過k條不相交路徑進行傳輸，而PON側由于光纖鏈路帶寬資源較大，將業務通過單條鏈路傳輸．并在無線側為其分配Breq/k帶寬資源作為備份保護，而PON側相鄰ONU之間互為備份，以提高網絡傳輸可靠性．將同一目的地址的業務按比例均分為k-1 條數據流，并為每條數據流分配標有順序號的新數據包頭進行傳輸．考慮到FiWi接入網中光纖一側與無線一側帶寬的差異，選擇ONU作為聚合節點，對數據流進行重組．令ps為虛擬鏈路ev分流后映射到物理網絡的路徑集合，假設虛擬鏈路ev∈EV有映射關系:

M(ev)=(f1，f2，…，fk) ,

(1)

物理鏈路es的剩余帶寬為該鏈路總帶寬與分流映射到該鏈路的各業務占用帶寬之差，即

(2)

其中，B(es)指鏈路總帶寬，b(fm)指各業務占用的鏈路帶寬．

端到端路徑可承受的帶寬請求由該路徑上最小的鏈路可用帶寬決定，即

(3)

多路徑傳輸會減少備份資源的使用，然而傳輸路徑增多帶來的額外開銷也會隨之增大，因此需要均衡傳輸路徑的數量和開銷．同時，每條路徑的拆分都會產生路由列表的更新、源節點和目的節點的緩存及額外時延等開銷．關于虛擬網絡映射開銷，從以下3方面進行考慮．

(4)

其中，C(ns)指物理節點的中央處理器(Central Processing Unit，CPU)處理能力，r(ns)指節點可用處理能力，s(ns)指節點ns轉發數據占用的內存開銷，權重因子的約束使算法優先選擇負載較小的節點進行數據轉發，保證了節點的負載均衡．

(2) 節點分流與合流開銷．主要是指將虛擬鏈路映射為多條路徑傳輸時，映射到底層網絡的源節點和目的節點分裂與聚合k條路徑轉換占用的內存．用d1(ns，k)和d2(ns，k)分別表示在物理節點ns∈NS處分流與合流的開銷，則節點的分流與合流開銷為

d(ns，k)=d1(ns，k)+d2(ns，k) ,

(5)

虛擬鏈路分流與合流的總開銷為

(6)

(3) 鏈路傳輸開銷．該開銷主要考慮物理鏈路的帶寬和鏈路的質量，根據業務的不同要求，鏈路質量q(es)由鏈路穩定性、丟包率、故障率等指標進行衡量，q(es)∈ [0，1]．鏈路質量越差，q(es)值越低．同時，考慮到負載均衡，仍將鏈路總帶寬與鏈路可用帶寬的比值作為權重因子用以鏈路的選擇．綜合考慮鏈路質量、鏈路可用帶寬及業務需求帶寬因素，其開銷為

(7)

其中，r(es)為當前該鏈路的可用帶寬．由于k條路徑中要預留一條路徑作為備份，因此每條路徑占用的帶寬為b(ev)/ (k-1)．鏈路質量根據業務的QoS需求動態地作為權重進行衡量．

為了使用戶在最小化備份資源保障網絡可靠性的同時，以較小代價獲得較優的網絡服務，文中將上述3種開銷之和最小化作為優化的目標函數，則

(8)

由于S(ev，ps)和D(ev，ps，k)是CPU執行速度單位MIPS，而L(ev，ps，k)的單位是Mbit/s，為統一單位，式中為S(ev，ps)和D(ev，ps，k)分別乘以一個權重因子α．目標函數最小，即使S(ev，ps)、D(ev，ps，k)、L(ev，ps，k)三者最小，目標函數越小，數據流在融合網絡中傳輸越均衡，故障率越小，所需開銷也越少．

約束條件物理節點的CPU資源必須能夠滿足虛擬節點的能力需求，即映射到物理節點上的所有虛擬節點資源請求應不超過物理節點的處理能力，即

(9)

并且在同一個虛擬網絡中，每一個虛擬節點nv在基礎設施層都有且只有一個物理節點與其對應，而一個物理節點至多被一個虛擬節點映射，因此有

(10)

同樣，映射到鏈路上所有虛擬網絡的帶寬請求應不大于該條鏈路的總帶寬．即對于所有包含該條鏈路的映射路徑，其占用帶寬之和應小于或等于該條鏈路的總帶寬，即

上式是對鏈路可用帶寬的要求，即源節點至目的節點間物理路徑的可用帶寬應不小于虛擬鏈路分流后的請求帶寬．為簡化計算過程，提高搜索效率，文中將虛擬鏈路帶寬平均分配，以均分后的值作為參考．

2.2 啟發式業務分流可靠傳輸

上述混合線性規劃MRVNE-OP對于小規模網絡可快速找到問題的最優解，但隨著虛擬網絡規模增大，計算時間變得讓人難以接受．因此，對于大規模網絡，筆者提出一種可擴展的貪婪算法MRVNE用于業務多路徑傳輸．該算法通過構建廣度優先搜索樹尋找映射節點，通過最短路徑法尋找鏈路的方式獲得次優解．

算法首先構建一個廣度優先搜索樹GV，根節點是虛擬網絡中最大CPU能力請求節點．然后將節點以CPU請求的大小遞減的方式進行排序，并對每個虛擬節點建立滿足條件的物理網絡候選映射節點集合．且集合中元素也按照CPU能力遞減的方式進行排序．最后以廣度優先的方式將虛擬節點映射到兩節點間存在k條最短路徑 (k≥2) 的物理節點上．

在進行鏈路映射時，研究表明導致網絡擁塞的業務量可能只占10%，這些業務的流量占總流量的90%，被稱為“大象流”．而網絡中90%的業務量，幾乎只占總流量的10%，被稱為“老鼠流”[11]．當FiWi接入網中存在大量并發業務時，對所有業務采用多路徑傳輸會增大傳輸時延及亂序、丟包等不利因素．受文獻[11]的啟發，根據業務所需帶寬大小的不同將業務進行動態區分，對“大象流”通過多路徑傳輸而對“老鼠流”采取單路徑方式傳輸，以減小各數據流對網絡資源的競爭．虛擬化管理層根據虛擬請求及約束條件找到源節點與相應ONU間的k條路徑后，記錄每條路徑的可用帶寬容量，然后將其值降序排列．為了保證業務傳輸過程中始終有滿足條件的路徑作為備份保護，文中將降序排列后的可用帶寬次大值作為區分大象流和老鼠流的標準．即

(13)

(14)

2.3 算法復雜度分析

在最小化備份資源的多路徑傳輸算法中，針對小規模網絡與大規模網絡的不同特性，文中分別使用線性規劃算法與啟發式算法進行具體分析．

在基于線性規劃的多路徑選取模型中，假設網絡中有n個節點，節點之間的連接概率為0.5．從期望意義上來說，在節點數目為n的網絡中，任意源、目的節點間的中繼節點數目為 logn級別，而在每次中繼決策過程中，共有n種選擇．因此，源、目的節點間總的路徑數量為nlog n．此外，在節點選擇與鏈路選擇過程中，加入了限制條件，在每次選擇過程中，選取整體開銷最小的節點與鏈路，即每次從n個節點或鏈路中選擇最優的1個節點或1條鏈路．根據上述分析，可得文中基于線性規劃的多路徑選取模型的時間復雜度為O(nnlog n)．

針對啟發式業務分流可靠傳輸算法，首先，在節點選擇過程中，使用廣度優先搜索算法，其算法時間復雜度為O(n+e)，其中，n為物理節點的數量，e為節點間連接的鏈路數量．然后按照CPU請求大小對節點進行排序，經典排序算法的最優時間復雜度為O(nlogn)．因此，節點選擇過程的整體時間復雜度為O(nlogn+n+e)．其次，在鏈路映射過程中，文中使用最短路徑法尋找滿足條件的路徑集合，經過分析可知，最短路徑法的整體時間復雜度為O(e(nlogn+e))．最后，故障恢復策略的整體時間復雜度為O(e)．根據上述分析，可得文中啟發式業務分流可靠傳輸算法的整體時間復雜度為O((n+e+nlogn)(e(nlogn+e))+e)．相比于鏈路選擇過程的時間復雜度，故障恢復過程的時間復雜度可忽略不計，因此，經過合理簡化的啟發式業務分流可靠傳輸算法的整體時間復雜度為O((n+e+nlogn)(e(nlogn+e)))．

根據上述分析可知，基于線性規劃的多路徑選取模型的時間復雜度為O(nnlog n)，即非多項式時間，而啟發式業務分流可靠傳輸算法的時間復雜度為O((n+e+nlogn)(e(nlogn+e)))，其算法時間復雜度的最高指數形式為常值，遠小于 logn，即為多項式時間．因此，其算法時間復雜度遠低于基于線性規劃的多路徑選取模型的時間復雜度．

3 仿真分析

3.1 仿真環境設定

筆者使用NS2(Network Simulator 2)仿真平臺驗證所提機制性能，對比機制為文獻[7]提出的全備份保護算法(Full Backup Scheme， FBS)和文獻[12]提出的共享備份保護算法(Shared Backup Scheme， SBS)．網絡拓撲由GT-ITM工具隨機產生[13]，包括1個OLT，8個ONU，64個路由器．其中光纖鏈路帶寬為 1 000 Mbit/s，無線側帶寬為 54 Mbit/s; 節點分流與合流開銷均設為10單位，節點轉發開銷設為5單位，節點資源請求服從 [5 GHz，15 GHz] 均勻分布，鏈路帶寬請求服從 [5 Mbit/s，50 Mbit/s] 均勻分布，網絡請求服從λ= 0.05的泊松分布[14]．其中，每個ONU都有內置的無線通信模塊，連接PON和mesh網絡．虛擬節點間有虛擬鏈路的概率為50%，即n個節點的虛擬網絡平均含有n(n-1)/4 條鏈路．每一個虛擬網絡請求的存續時間滿足均值為 1 000 個時間單位的指數分布．整個網絡抽象后得到的物理資源由虛擬管理層統一調度．

圖2 不同網絡負載的網絡接受率

3.2 仿真結果與分析

圖2和圖3表示不同負載時4種算法的接受率和備份帶寬的關系．由圖2可見，隨著負載增大網絡接受率均下降．負載較小時流量都是“老鼠流”，MRVNE、MRVNE-OP與FBS傳輸方式相似，備份資源占用較多．而SBS是備份資源共享，可用于傳輸的鏈路資源較多且接受率最高．隨著負載增大，MRVNE及MRVNE-OP開始多路徑傳輸，更有效地利用底層資源，表現出更高的請求接受率．而FBS和SBS不能很好的利用資源切片，當負載增大時其接受率下降較快．圖3給出了備份資源分配情況，由于FBS進行1∶1備份保護，備份資源比例大于0.5．而SBS備份資源共享，其備份資源比例最小．MRVNE原則上隨著路徑增多備份資源比例無限減小．然而，由于資源開銷的限制，k不可能無限增大，因此，其備份資源先下降后逐漸趨于穩定并接近SBS，比FBS方式節約了40%～50%的備份資源．圖4給出了不同故障等級時的網絡故障率．其中，故障等級為鏈路故障率與網絡請求到達率之比(即γ=λF/λV)．由圖可見，隨著故障等級增加，故障率隨之增大．其中，MRVNE-OP和MRVNE將業務通過多條路徑傳輸，只有當虛擬鏈路映射的多條物理路徑全故障時，虛擬鏈路才故障，因此，其故障率最低．FBS算法由于采用1∶1備份保護，故障時可以將其轉移到備份路徑，因此故障等級較小時，其性能表現優于MRVNE算法．隨著故障等級增加，新生成的虛擬網絡造成故障又會影響到已存在的網絡，單路徑傳輸的劣勢使其故障率逐漸高于MRVNE算法．而SBS采取共享備份，當故障出現時，備份資源可能已被占用，因此故障率最大幾乎是MRVNE-OP的兩倍．

圖3 不同負載備份資源比例圖4 不同故障等級的網絡故障率

文中所提機制的特點是傳輸路徑越多，所需備份資源越少．然而傳輸路徑增多帶來的額外資源開銷也會隨之增大，因此要在路徑條數和資源開銷之間進行權衡．為了確定合適的路徑條數k值，將一條虛擬鏈路在不同負載及路徑條數下進行傳輸計算其開銷．結果如圖5所示，初始時，開銷均隨著k值增大而減小，這是因為當k=2 時相當于FBS情況，備份資源占用比例較大，同時考慮負載均衡導致鏈路開銷較大．從k=4 之后，開銷隨著路徑條數的增大而增大，這是因為路徑的增多帶來的節點轉發，數據傳輸及分流與合流的額外開銷隨之增大．當路徑超過6條之后，增加更加明顯．并且當路徑條數超出8時，較大的時延導致傳輸質量嚴重下降而無法進行仿真．圖6給出了3種算法的平均傳輸開銷．由圖可見，FBS、SBS算法的開銷相差不大，而MRVNE算法的開銷幾乎是前兩者的2～3倍．這是因為FBS、SBS算法均是通過單路徑傳輸，而MRVNE算法是多路徑傳輸，額外占用的節點及鏈路增大了其傳輸開銷．但這些額外開銷使得網絡負載均衡得到較好的實現，同時網絡生存性得到了更好的保障，使網絡具有更高的接受率，因此帶來了更大的網絡收益．

圖5 不同鏈路的傳輸開銷圖6 不同網絡負載時的平均傳輸開銷

4 結 束 語

通過將FiWi接入網虛擬化，筆者利用虛擬管理層資源集中管理的優勢，統一調度FiWi網絡資源為用戶提供服務．首先提出了FiWi網絡虛擬化抽象模型，描述了各層之間的關聯及各自職能．然后在虛擬化的基礎上提出了一種按比例分配備份資源的多路徑傳輸算法．最后通過仿真驗證所提算法在網絡可靠性及網絡接受率方面均獲得良好的性能．相比于FBS、SBS保護方案，文中所提算法用更少的備份資源保障了單鏈路故障的可恢復性及多鏈路故障的可生存性，并且有效地實現了負載均衡，提高了網絡資源利用率．