面向多業務需求的NFV和SDN融合的資源優化算法

朱曉榮，張倩

?

面向多業務需求的NFV和SDN融合的資源優化算法

朱曉榮，張倩

（南京郵電大學通信與信息工程學院，江蘇 南京 210003）

物聯網的多種業務需要靈活的網絡部署來保障其服務質量。針對物聯網服務功能鏈部署問題，將網絡功能虛擬化（NFV, network function virtualization）與軟件定義網絡（SDN, software defined networking）相結合，綜合考慮轉發成本以及流量平衡情況，給出了虛擬網絡功能放置與服務功能鏈路由的聯合優化模型，該優化模型是NP-Hard問題。為了求解該問題，提出兩種啟發式算法：一種是先路由后放置（FRTP, first routing then placing）的服務鏈部署算法，另一種是基于節點優先級的先放置后路由（PFBR, placing followed by routing）的服務鏈部署算法。仿真結果表明，與其他算法相比，提出的FRTP和PFBR算法能顯著平衡網絡中的流量負載，改善鏈路擁塞情況，從而提高服務功能鏈請求接受率。

物聯網；虛擬網絡功能；服務功能鏈部署；節點優先級；負載均衡

1 引言

隨著物聯網的發展，各種各樣的業務對網絡的需求日益多樣化[1]。例如，車聯網中的通信對時間的敏感度高；工業制造中要求低分組丟失率和低時延；而移動視頻監控網絡可以容忍適度的誤碼率和時延，但需要高帶寬。現有的專用硬件網絡系統架構面臨著諸多嚴重缺陷，例如，網絡體系架構僵硬、網絡升級維護困難、功能平面劃分不合理等，難以應對日新月異的物聯網業務需求。

SDN通過數據平面與控制平面的分離，并借助開放的接口，為形式各異的網絡應用提供靈活的承載服務。NFV使用虛擬化技術以消除對專用硬件的依賴[2]，并使很多不同的網絡設備類型合并到行業標準高容量服務器、交換機及存儲器上，通過靈活的部署策略來提高網絡基礎設施的資源利用率和服務質量[3]。

雖然SDN和NFV技術的應用有望滿足物聯網多樣化的業務對網絡靈活組網的需求，但是NFV技術對網絡服務重新抽象和細粒度分解，使其組成成分更加復雜，關鍵的挑戰在于服務功能鏈（SFC, service function chain）的部署。由于巨大的服務規模以及高動態的網絡負載，物聯網復雜業務驅動的動態服務網絡構建機制無論對當前還是未來都是一個挑戰。

Wang等在文獻[4]中，針對NFV資源分配問題，提出一種綜合的成本模型，在滿足用戶需求的基礎上實現最低成本的資源分配目標。Hendrik Moens和Filip De Turck考慮了物理網絡功能（PNF, physical network function）和虛擬網絡功能（VNF, virtualized network function）共存的場景，決定網絡中功能的正確放置位置，可以較為充分地利用物理和虛擬資源[5]，以實現服務功能鏈部署的擴展性和靈活性。Kanizo等[6]用圖論來解決NFV的資源分配問題，將虛擬網絡功能和服務器（具有多個虛擬機）看作二分圖中兩個互不相交的子集，側重于解決節點功能失效時，由支持該功能的服務器進行恢復，從而使故障功能恢復的可能性最大。

Mohammadkhan等[7]將關注點聚焦于網絡功能的放置以及業務流路由的均衡問題。為了給特定的服務功能鏈分配資源，Leivadeas等[8]在放置VNF和為功能鏈選路的同時，用加權系數對資源利用率和帶寬利用率進行權衡，以實現網絡中負載平衡，從而有效提高資源利用率。Lopez等[9]提出了一個根據網絡拓撲放置虛擬網絡功能并構建功能鏈的方案，并給出了幾種啟發式算法，但更加側重于功能放置構建服務功能鏈的方法。

Seliuchenko等[10]提出擴展的多商品流模型（multi-commodity flow model），使用服務質量標準來平衡負載，業務流的路由問題可以根據分類進一步細化。Pham等[11]對NFV多徑路由的負載平衡問題進行了分析，研究了基于NFV的網絡系統用戶需求的變化，提高響應能力，從而優化網絡性能。

Nam等[12]將NFV服務功能鏈引入無線接入網，使移動邊緣計算（MEC, mobile edge computing）功能可以分配給附近的基站，從而使業務接入用戶設備獲得更低的時延體驗。為了實現NFV的全部潛力，NFV擴展到無線接入部分[13]，其缺點在于每個SFC需求的功能只能部署一次，而且每個功能需要放置在不同的節點上，這在一定程度上會引入鏈路時延。

Bari等[14]定位在企業網絡，致力于降低部署網絡功能的總成本。為了實現服務鏈部署，Sun等[15]考慮在服務鏈之間共享虛擬網絡功能，并在相同的節點中，部署相鄰的虛擬網絡功能以避免帶寬消耗。Hirwe等[16]針對VNF的放置影響交換機負載和帶寬利用效率等問題，提出一種高效的算法——LightChain，以消除乒乓流量。針對多個服務功能鏈的VNF共享，Savi等[17]考慮到升級成本和上下文轉移成本的影響，以最小化NFV激活節點作為優化目標。Beck等[18]考慮的是物理網絡的節點與鏈路出現故障時，如何進行資源合理分配的問題。如果某些節點失效，則需要將部署在該節點處的網絡功能進行合理的遷移或由備份的VNF實現，以保障彈性和擴展性。

針對VNF鏈如何最佳地協調分配到網絡基礎設施上，Beck等[19]提出一種啟發式方法—— CoordVNF，旨在合理的運行時間內最大限度地降低帶寬利用率。Liu等[20]試圖確定放置中間件的最佳位置，以便優化服務鏈性能，并提出兩種啟發式算法——貪婪算法和模擬退火算法來獲得次優解，結果表明，其可以減少22％的端到端時延，平均節省38％的帶寬消耗。Bouet等[21]出于對網絡安全的考慮，將vDPI（virtual deep packet inspection）部署在網絡中，以成本最小化為目標建立模型，結果證明提出的基于中心的貪婪算法很好地趨近最優解。Mijumbi等[22]針對VNF部署問題，側重于提出虛擬網絡功能的映射與調度算法，其提出的3種貪婪算法以及基于禁忌搜索的啟發式算法中，后者表現出稍許的優勢。

雖然目前已有很多文獻對NFV資源分配和SDN路由策略進行了研究，但是仍存在著很多不足。例如，大多數文獻中構成功能鏈的VNF，其占用資源單一，幾乎沒有考慮同時需要計算、存儲等多維資源需求的場景。另外，有些文獻僅從NFV資源分配或SDN路由策略某一個方面重點考慮，容易陷入局部最優解，如何協調二者之間的關系，值得深入研究。

在這種背景下，本文研究動態服務網絡的NFV和SDN融合的資源優化算法，根據網絡狀態的動態變化、業務特性提出聯合優化模型，確定業務驅動的最優傳輸性能的資源優化方法，從而有效保障用戶QoS，并實現網絡性能優化。為了方便求解優化模型，本文根據VNF放置與業務流選路的順序提出了兩種啟發式算法——FRTP算法和PFBR算法。FRTP算法側重從用戶角度出發，使大量的數據分組在數據平面快速轉發，提高用戶體驗；基于節點優先級的PFBR算法，能有效地平衡網絡中的流量負載，提高服務鏈請求接受率。

2 系統模型

NFV技術將用戶的請求轉化為VNF構成的服務功能鏈，SDN將流量管理與流量轉發分離，實現集中控制。在控制平面，SDN控制器管理網絡資源并控制全局網絡流量。基于網絡狀態信息，控制器可相對于服務功能鏈的QoS需求，確定通信路徑，從而做出靈活的流量控制決策，經由OpenFlow南向API，數據平面硬件用于轉發數據分組，優化整個網絡的運行。本文將服務功能鏈部署問題分為兩個階段。根據服務功能鏈的源節點、目的節點以及VNF次序，將服務功能鏈所需的一系列VNF放置在網絡上的NFV節點，以滿足用戶定制的網絡服務需求；SDN控制器根據服務功能鏈的需求，為其選擇一條最佳路徑，直至構成一條完整的端到端路徑。

圖1給出了一條服務功能鏈的資源分配與鏈路映射示意，該條服務功能鏈共有5個虛擬網絡功能， SDN控制器以及VNF管理編排器（MANO, management and orchestration）依據SFC請求以及當前網絡狀態，實時地將服務功能鏈所需的VNF分配在物理節點1、物理節點2、物理節點2、物理節點5、物理節點3處，另一方面，SDN控制器為該條服務功能鏈規劃的路徑為(s,1)→(1,2)→(2,3)→(3,5)→(5,4)→(4,3)→(3,)。

圖1 服務功能鏈資源分配與鏈路映射示意

3 NFV和SDN融合的資源優化模型

本文提出的NFV和SDN融合的資源優化模型分別如式(4)~式(12)所示。

4 算法描述

眾所周知，NP-Hard問題難以在多項式時間內求解，因此，本文根據VNF放置與業務流選路的順序提出了兩種啟發式算法求解NFV和SDN融合的資源優化模型。一種是對SFC先進行靈活的路由決策，然后在該路徑上依次順序地放置所需的VNF，稱為先路由后放置的服務鏈部署算法；另一種則剛好相反，先將服務功能鏈所需的VNF放置在優先級最高的節點上，繼而遍歷源節點、該節點以及目的節點，形成一條完整的路徑，稱為先放置后路由的服務鏈部署算法。

4.1 先路由后放置的服務鏈部署算法

算法1 先路由后放置的服務鏈部署算法

步驟1 根據該階段所有服務功能鏈的速率需求降序排序，標注優先級，向SDN控制器請求更新所有節點的可用資源以及網絡鏈路的剩余帶寬。

步驟3 為該條服務功能鏈選擇從源節點至目的節點的最短路徑作為最佳路徑。

步驟4 為該條服務功能鏈選擇從源節點至目的節點的前條最短路徑中剩余帶寬最大的一條作為最佳路徑。

步驟5 判斷該條最佳路徑的最小鏈路剩余帶寬是否大于速率需求，若是，轉向步驟6；否則，轉向步驟8。

步驟7 對選擇的路徑依次經過的節點順序地放置VNF，直至放置完成，結束。

步驟8 繼續搜索從源節點到目的節點的次佳路徑，重復步驟5~步驟7，若均不滿足，則結束，即拒絕該條服務功能鏈。

步驟9 重復步驟2~步驟8，直至所有的服務功能鏈均被部署或拒絕。

4.2 先放置后路由的服務鏈部署算法

算法2 先放置后路由的服務功能鏈部署算法

步驟1 根據該階段所有服務功能鏈的速率需求降序排序，標注優先級，并依次為服務功能鏈進行VNF的放置。

步驟2 對物理網絡中能夠承載虛擬網絡功能的節點進行優先級降序排序，排序的標準由式(14)所示，節點的優先級由該節點的可用資源以及選擇該節點引入的跳數共同決定。

步驟3 對于每條服務功能鏈，其每一跳的放置依據為選擇優先級最大的節點作為當前的最佳位置，判斷當前選中的節點是否有足夠的資源承載VNF，即是否滿足資源需求式(13)，若滿足，轉向步驟4；否則轉向步驟5。

步驟4 將該條服務鏈所需的VNF貪婪地放置在該節點上，動態更新節點的可用資源。

步驟5 繼續搜索節點優先級次高的節點作為當前最佳節點，直到能夠放置VNF，否則視為拒絕該服務功能鏈。

步驟7 在該條服務功能鏈的源節點、VNF的放置節點以及目的節點之間的每一跳，都采用最短路徑，形成首尾相連的完整路徑。

步驟8 判斷選擇的路徑的最小鏈路剩余帶寬是否大于速率需求，若大于，則該條服務功能鏈部署成功；否則轉步驟9。

步驟9 在該條服務功能鏈的源節點、VNF的放置節點以及目的節點之間的每一跳，對其進行條最短路徑搜索，得到剩余帶寬最大的路徑。

步驟10 判斷選擇的路徑鏈路可用帶寬是否大于SFC速率需求，若大于，則該條服務功能鏈部署成功；否則視為拒絕該服務功能鏈。

步驟11 重復步驟2~步驟10，直至所有的服務功能鏈均被部署或拒絕。

4.3 算法復雜度分析

5 實驗結果及性能分析

為了對本文提出的FRTP和PFBR算法進行評估，將提出的啟發式算法重點在總轉發成本、負載均衡度、平均運行時間以及服務功能鏈請求接受率等方面與基于最短路徑的服務功能鏈部署算法（其中VNF放置策略與FRTP算法相同）以及NAaP算法和AaP算法[15]進行對比。NAaP算法和AaP算法在路由階段均優先采用最短路徑，進行VNF的放置時采用貪心算法，二者的區別在于后者將源節點與目的節點相同的SFC進行融合，其中，帶寬需求疊加，相同的VNF可以共享。

表1 6節點網絡拓撲的算法結果

5.1 實驗環境和參數設置

由于本文提出的服務功能鏈部署算法，可以分為兩個階段，既包含VNF放置階段的算法，也包括服務鏈路由的算法。其中，VNF放置階段的算法運行在Matlab 2015a環境中；FRTP和PFBR算法中的服務功能鏈路由算法部分寫入Ryu控制器（SDN控制器），利用Mininet仿真工具生成網絡拓撲，在Ubuntu系統里進行驗證。

網絡中的節點具有承載VNF的能力，節點數量越多，其具有的VNF所需的各類資源越多，服務功能鏈部署成功的概率越大，請求被接受的越多。因此，本文在設置仿真實驗時，將服務功能鏈數量與網絡節點數量進行相應的調節。

本文實驗在初始階段采用6個節點、8條鏈路的拓撲，每個節點具有3種資源類型，資源總量服從均值為100、方差為31.8的均勻分布，鏈路帶寬為200 unit。SFC的數量為50~100，VNF種類共有7種，服務功能鏈所需的VNF為2~4種，對3種類型的資源需求均為0.2~1 unit，服務功能鏈的速率需求為1~5 unit，各種算法的對比結果如表1所示。然后，將網絡規模擴展為20~100節點的隨機網絡，VNF的種類共有9種，每條服務功能鏈所需的VNF為3~6種，SFC數量由200條逐漸增加到1 000條。

5.2 性能分析

在較小網絡規模下，服務功能鏈的數量由50遞增至100，由表1可知，FRTP算法和PFBR算法在總帶寬成本以及流量負載均衡這兩個方面“勢均力敵”，并未表現出太多的差異。FRTP算法和PFBR算法與基于最短路徑的算法以及NAaP算法和AaP算法相比，總轉發成本略高一些，而負載均衡度得到了降低，這是由于后者總是優先以最短路徑進行業務流的轉發，因此，總轉發成本相對較低，相應地，負載均衡度會急劇升高。FRTP算法的時間開銷略高于PFBR算法，其原因在于，在網絡規模較小的情況下，FRTP算法先確定轉發路徑，繼而依次順序（相對平均地）將VNF放置在選定的路徑經過的節點上，其主要復雜度在于對每一條SFC中的VNF所需資源與節點資源總量進行比對；而PFBR算法由于對服務功能鏈選擇優先級最大的節點進行VNF貪婪的放置方法，因此，在網絡規模較小時，運行時間更短一些。但是，與最短路徑算法、NAaP算法、AaP算法相比，本文提出的兩種算法由于復雜度更高，平均運行時間相對更長。AaP算法由于對SFC進行融合，相比逐條部署SFC，算法復雜度更低，其部署速度更快。

圖2顯示了網絡拓撲節點數目為50時的隨機網絡中服務功能鏈數量與轉發成本的關系。總體而言，轉發成本隨著服務功能鏈數量的增大而增大，FRTP算法的轉發成本低于PFBR算法，由于總轉發成本與選擇的路徑長度呈正相關，因此，二者的轉發成本均高于最短路徑算法、NAaP算法、AaP算法。

圖2 總轉發成本與SFC數量的關系

但僅考慮如何降低轉發成本是非常片面的，容易造成網絡中流量負載分布不均，有些鏈路異常擁塞，而有些鏈路非常空閑的情況。圖3展示了隨著SFC數量的增加網絡中負載均衡度的變化。FRTP算法的負載均衡效果稍微遜色于PFBR算法，但這兩種算法與最短路徑算法、NAaP算法、AaP算法相比，在負載均衡方面表現出更強的優勢。

圖3 網絡中負載均衡度與SFC數量的關系

在網絡規模逐漸增大時，服務功能鏈的數量固定為500條，總轉發成本并未隨著節點的增大而呈現較大差異，這是由于生成的隨機網絡的平均距離大致相同，選擇的路徑長度也差別不大，因此，FRTP算法、PFBR算法的總轉發成本相差不大。但是，網絡中負載均衡度卻有著較為明顯的差別，圖4描述了在網絡規模逐漸增大時負載均衡度的變化趨勢。整體而言，PFBR算法的負載均衡效果優于FRTP算法，而最短路徑算法、NAaP算法、AaP算法明顯劣于本文提出的兩種算法，由此可見，FRTP算法、PFBR算法在路由階段的優化起到了至關重要的作用。

圖4 網絡中負載均衡度與網絡節點數量的關系

當網絡拓撲固定為50個節點的隨機網絡時，算法的平均運行時間隨著服務功能鏈數量的增大而增大，如圖5所示。基于最短路徑的算法與NAaP算法、AaP算法的時間開銷相差不大，而本文提出的算法尋求帶寬剩余量較多的空閑鏈路以平衡流量負載，其代價是更長的時間開銷。FRTP算法的時間開銷低于PFBR算法，與網絡規模較小時的結論看似相反，實際由于FRTP算法的服務鏈部署算法選擇的路徑長度幾乎不可能超過節點的數量，因此，PFBR的服務鏈部署算法在對每一條SFC計算節點優先級時需花費更多的時間。圖6描述了網絡規模逐漸增大時，各算法的時間開銷，與SFC數量增多時的結論無異。

圖5 算法時間開銷與SFC數量的關系

圖6 算法時間開銷與網絡節點數量的關系

本文實驗還設置了一組仿真，在節點為20的隨機網絡中，將鏈路帶寬上限設為100 unit，服務功能鏈的速率需求約為4~10 unit，驗證不同服務請求的接收率。圖7展示了在不同服務功能鏈請求強度下，各種算法的服務功能鏈請求接受率。AaP算法比最短路徑算法、NAaP算法的接受率略高，這是由于在帶寬和節點資源一定的情況下，AaP算法能夠通過在多條SFC之間共享相同的VNF，從而降低由于節點資源不足以承載VNF導致服務鏈部署失敗的概率。與最短路徑算法、NAaP算法、AaP算法相比，本文提出的服務鏈部署算法表現出了顯著的優勢。其中，由于PFBR算法相比FRTP算法能夠較好地平衡網絡中的資源流量負載，因此，網絡的資源能夠得到更加充分的利用，服務功能鏈請求接受率相比其他算法有明顯的提高。

圖7 不同服務功能鏈請求強度與接受率的關系

綜上，本文提出的FRTP算法、PFBR算法與最短路徑算法、NAaP算法、AaP算法相比，在犧牲一部分轉發成本的基礎上，獲取了更多的鏈路可用資源，能更有效地平衡網絡中的流量負載，且提升服務功能鏈請求接受率。但FRTP算法與PFBR算法相比，更側重于降低總轉發成本，使大量的數據流在網絡中快速轉發，在一定程度上可降低服務功能鏈響應速度，提高用戶體驗，其也可以作為在線算法，實時地部署服務功能鏈。另一方面，基于PFBR的服務鏈部署算法在中、大規模網絡以及SFC數量較多時可以更加有效地平衡網絡中的負載，從而提高網絡中整體的鏈路利用率，提升服務功能鏈請求接受率，其優勢用于離線算法中更為明顯。

6 結束語

本文主要研究了物聯網環境下服務功能鏈的部署問題，根據網絡狀態的動態變化、業務特性，提出NFV和SDN融合的虛擬網絡功能放置與服務鏈路由的聯合優化模型。為了方便求解優化模型，本文提出了兩種啟發式算法，經仿真驗證，與其他算法相比，FRTP和PFBR算法能顯著平衡網絡中的流量負載，提高請求接受率。就本文提出的算法而言，FRTP算法作為在線算法，在實時部署服務功能鏈方面，能夠使大量的數據分組在數據平面快速轉發，提高用戶體驗；而PFBR算法可作為離線算法，雖然其在降低總轉發成本方面略顯遜色，但在負載均衡方面優勢凸顯，使服務功能鏈請求接受率得到顯著提高。兩種算法的有益結合能夠更好地部署服務功能鏈。在大規模網絡和業務請求非常多的場景中，本文提出的兩種算法雖能有效平衡網絡流量負載，但時間開銷增加很快。因此，在今后的工作中，期望研究更優化的啟發式算法，在兼顧負載平衡的同時，盡可能地降低時間開銷。

[1] BIZANIS N, KUIPERS F A. SDN and virtualization solutions for the Internet of Things: a survey[J]. IEEE Access, 2016, 4(99): 5591-5606.

[2] MECHTRI M, GHRIBI C, SOUALAH O, et al. NFV orchestration framework addressing SFC challenges[J]. IEEE Communications Magazine, 2017, 55(6):16-23.

[3] 袁泉, 湯紅波, 黃開枝, 等. 基于Q-learning算法的vEPC虛擬網絡功能部署方法[J]. 通信學報, 2017, 38(8): 172-182.

YUAN Q, TANG H B, HUANG K Z, et al. Deployment method for vEPC virtualized network function via Q-learning[J]. Journal on Communications, 2017, 38(8): 172-182.

[4] WANG L H, LU Z M, WEN X M, et al. Joint optimization of service function chaining and resource allocation in network function virtualization[J]. IEEE Access, 2016, 4: 8084-8094.

[5] MOENS H, TURCK F D. Customizable function chains: managing service chain variability in Hybrid NFV networks[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 711-724.

[6] KANIZO Y, ROTTENSTREICH O, SEGALL I, et al. Optimizing virtual backup allocation for middleboxes[J]. IEEE Journals & Magazines, 2017, 25(5): 2759-2772.

[7] MOHAMMADKHAN A, GHAPANI S, LIU G, et al. Virtual function placement and traffic steering in flexible and dynamic software defined networks[C]//The 21st IEEE International Workshop on Local and Metropolitan Area Networks. 2015: 1-6.

[8] LEIVADEAS A, FALKNER M, LAMBADARIS I, et al. Resource management and orchestration for a dynamic service chain steering model[C]//2016 IEEE Global Communications Conference (GLOBECOM). 2016.

[9] LOPEZ M A, MATTOS D M F, DUARTE O C M B. Evaluating allocation heuristics for an efficient virtual Network Function chaining[C]//2016 7th International Conference on the Network of the Future (NOF). 2016.

[10] SELIUCHENKO M, LAVRIV O, PANCHENKO O, et al. Enhanced multi-commodity flow model for QoS-aware routing in SDN[C]//2016 International Conference Radio Electronics & Info Communications (UkrMiCo). 2016.

[11] PHAM T M, PHAM L M. Load balancing using multipath routing in network functions virtualization[C]//2016 IEEE RIVF International Conference on Computing & Communication Technologies, Research, Innovation, and Vision for the Future (RIVF).2016: 85-90.

[12] NAM Y, SONG S, CHUNG J M. Clustered NFV service chaining optimization in mobile edge clouds[J]. IEEE Communications Letters, 2017, 21(2): 350-353.

[13] RIGGIO R, BRADAI A, HARUTYUNYAN D, et al. Schedulingwireless virtual networks functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(2): 240-252.

[14] BARI M F, CHOWDHURY S R, AHAMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 725-739.

[15] SUN Q Y, LU P, LU W, et al. Forecast-assisted NFV service chain deployment based on affiliation-aware vNF placement[C]//2016 IEEE Global Communications Conference (GLOBECOM). 2016.

[16] HIRWE A, KATAOKA K. LightChain: A lightweight optimization of VNF placement for service chaining in NFV[C]//2016 IEEE NetSoft Conference and Workshops (NetSoft). 2016, 33-37.

[17] SAVI M, TOMATORE M, VERTICALE G. Impact of processing costs on service chain placement in network functions virtualization[C]//2015 IEEE Conference on Network Function Virtualization and Software Defined Network (NFV-SDN). 2015: 191-197.

[18] BECK M T, BOTERO J F, SAMELIN K. Resilient allocation of service function chains[C]//2016 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN). 2016: 128 - 133.

[19] BECK M T, BOTERO J F. Coordinated allocation of service function chains[C]//2015 IEEE Global Communications Conference (GLOBECOM). 2015: 1-7.

[20] LIU J, LI Y, ZHANG Y, et, al. Improve service chaining performance with optimized middlebox placement[J]. IEEE Transactions on Services Computing, 2017, 10(4): 560-573.

[21] BOUET M, LEGUAY J, CONAN V. Cost-based placement of vDPI functions in NFV infrastructures[C]//The 2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-9.

[22] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]//The 2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-9.

[23] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: W H Freeman & Company. 1979.

Resource optimization algorithm of combination of NFV and SDN for application of multiple services

ZHU Xiaorong, ZHANG Qian

College of Communications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Various services of internet of things (IoT) require flexible network deployment to guarantee different quality of service (QoS). Aiming at the problem of IoT service function chain deployment, network function virtualization (NFV) and software defined networking (SDN) were combined to optimize resources. Considering forwarding cost and traffic load balance, a joint optimization model of virtual network function placement and service function chain routing was given and was proved to be NP-Hard. In order to solve this model, two heuristic algorithms were proposed. One was the service chain deployment algorithm of first routing then placing (FRTP) and the other was the placing followed by routing (PFBR) based on node priority. Simulation results demonstrate that FRTP and PFBR algorithm can significantly balance network traffic load while alleviating congestion and improving the acceptance ratio of the chain requests compared with other algorithms.

internet of things, VNF, service function chain deployment, node priority, load balance

TN915.81

A

10.11959/j.issn.1000?436x.2018235

朱曉榮（1977–），女，山東臨沂人，南京郵電大學教授、博士生導師，主要研究方向為5G通信系統、異構網絡、物聯網等關鍵技術及系統研發。

張倩（1994–），女，江蘇徐州人，南京郵電大學碩士生，主要研究方向為網絡功能虛擬化、軟件定義網絡等。

2018?01?29；

2018?05?10

朱曉榮，xrzhu@njupt.edu.cn

國家自然科學基金資助項目（No.61871237）；江蘇省高校自然科學研究重大項目基金資助項目（No.16KJA510005）；江蘇省研究生科研與實踐創新計劃基金資助項目（No.KYCX17_0767）

The National Natural Science Foundation of China (No.61871237), The Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (No.16KJA510005), Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX17_0767)