一種SDN中用戶群博弈的OpenFlow流調度策略

林曉勇 ，朱園園 ，梅杰 ，糜正琨

（1.南京郵電大學通信與信息工程學院，江蘇 南京 210003；2.北京郵電大學信息與通信工程學院，北京 100876）

一種SDN中用戶群博弈的OpenFlow流調度策略

林曉勇1，朱園園1，梅杰2，糜正琨1

（1.南京郵電大學通信與信息工程學院，江蘇 南京 210003；2.北京郵電大學信息與通信工程學院，北京 100876）

提出了一種基于用戶中心網絡的軟件定義網絡框架，建立了一種基于用戶群博弈策略的OpenFlow流調度模型，提取用戶群屬性及用戶最佳體驗參數，從用戶層面跨層至控制層進行調度，對比了非合作博弈調度與合作博弈調度。仿真結果顯示，合作博弈調度的用戶群整體滿意度最佳，有助于通信運營商實現“用戶為王”的理念。

用戶中心網絡；軟件定義網絡；用戶群博弈；合作博弈；滿意度

1 引言

4G／5G 時代，軟件定義網絡（software defined networking，SDN）、網絡功能虛擬化 （network function virtualization，NFV）和云計算（cloud computing，CC）技術使網絡與底層物理基礎設施分開，變成更抽象、靈活的，以軟件為中心的構架，可以通過編程調度來提供更佳的業務連接。互聯網+、移動應用技術、挖掘用戶行為特征的社交網絡的發展，演變為以用戶最佳體驗（user best experience，UBE）為中心的用戶中心網絡（user centric networking，UCN）。UCN 用戶可以基于某種激勵機制來交互和獲取信息，與傳統SDN相比，UCN能識別用戶的身份、喜好、認證等信息，實現由用戶而非僅設備驅動的流調度機制［1-3］。

2 相關研究工作

時代飛速發展，傳統的資源共享型互聯網轉變為用戶服務型網絡。封閉的運營商管道體系與以用戶為中心的客觀需求產生了不對稱性，如何在運營商“管道”上體現用戶“自定義服務”的特色，是SDN技術的起源。2008年，美國斯坦福大學Mckeown N教授的研究團隊［1］首次提出了OpenFlow的概念，之后進一步闡述SDN的概念［2］，受到了學術界和產業界的廣泛支持。

SDN與傳統網絡的最大不同在于控制平面（control plane，CP）與數據平面（data plane，DP）相分離，并將 CP 挪到交換機／路由器之外的應用中，通過安全套接層（secure sockets layer，SSL）通道連接應用與網絡設備。開放網絡基金會（Open Network Foundation，ONF）正式發布一個名為OpenFlow協議的開放式信令標準 （OpenFlow protocol，OFP），用于控制器和交換機之間的信令交互［3］。OpenFlow作為SDN的標準協議，通過流表進行消息傳遞，每張流表都由多個流表項組成，每個流表項對應網絡中傳輸的一條流，因此能合理高效地進行流調度，并為用戶提供無縫服務。CP中核心的控制器（controller）擁有全局網絡狀態并管控整個網絡，代表所有交換機做決定。DP仍然在交換機中，但不能獨立做決定，每當控制器做一個決定，它會給相應交換機發送消息來修改其流表，所有交換機只是根據它們流表中的指令來轉發數據分組。

可編程SDN的自適應結構可以很好地滿足定制業務（ordered service，OS）的需求，恰恰符合運營商以用戶為中心的需求，因此控制器控制并刷新網絡狀態，提高網絡資源利用率和降低運營成本，通過監控底層網絡流量來提供自我配置，通過區分、獨立的流量種類可以獲得更好的用戶體驗。

當前用戶數據全IP化，IPv4報文中的服務類型（type of service，ToS）占1 byte，將數據流簡化為8個優先級，RFC2474重新定義ToS為差分業務控制點（differentiated services code point，DSCP），至 64 級別，仍然只從數據流屬性角度衡量網絡服務質量（quality of service，QoS），未達到UCN以用戶為中心的體驗質量（quality of experience，QoE）的要求，因此本文的創新點為跨層獲取用戶屬性參數，從而重新優化資源調度。

傳統的資源分配方法是以各種最優化結果為目標，使端系統被動地得到資源［4］，用戶在競爭有限網絡資源的過程中，參與者惡性的競爭行為會使資源調度問題變得更為復雜，需要參與競爭的主體是“理性的”，因此借鑒經濟學中估量用戶“付費服務”的有效工具——博弈論來研究上述問題。在博弈論模型中，每個主體的收益不僅取決于它自身的行為屬性，也取決于其他人的行為屬性，理論界的博弈論算法以遞歸計算求最優值為主，迭代運算量大且耗時長，不符合路由器算法執行的有效性。本文以博弈論為基礎，設計出適合硬件執行的分布式博弈論算法來實現最優化、相對公平的資源調度。

3 基于UCN的改進SDN轉發機制

基于UCN的改進SDN架構如圖1所示。基礎設施層為網絡的底層轉發設備，主要由OpenFlow交換機組成；控制層集中維護網絡狀態及保證QoS，并通過南向接口（如OpenFlow）獲取底層基礎設施信息，同時為應用層提供可擴展的北向接口，用于應用程序檢測網絡狀態、下發控制策略［5］；UCN層可以是多媒體視頻網站（視頻流大客戶），也可以是社交網絡應用，或者是運營商分類業務用戶，包含各自的QoE指標。

UCN層用來提取用戶及用戶群的各種屬性參數，然后映射到UGG（user group gaming，用戶群博弈）調度策略中，從而實現以用戶群為中心的跨層調度。圖2給出了在OpenFlow1.4版本下，多OFP媒體流進入組入口（group entry）［6，7］，采用 UGG 策略的 SDN 調度機制。OFP 消息的結構如圖3所示，其中，0x16H在使用0x0F異或解析處理時，可以適配成標準的OpenFlow1.5協議［8］；也可在檢測到0x16H時調用UGG策略，同時在OFP凈荷的IP報文的頭部option字段提取用戶博弈因子（user gaming index，UGI）和用戶期望帶寬（user expected bandwidth，UEB）參數，執行UGG策略，OFP交換機的流表結構保持不變［9］。

圖1 改進的SDN架構

圖2 簡化的兼容UGG策略機制

圖3 改進的OFP消息結構

4 基于UGG的OpenFlow調度模型

已注冊UGG策略服務的用戶才會啟用博弈機制，未注冊用戶執行兼容的OpenFlow機制。UGG分布式部署在控制器中，會略微增加控制器的負荷，在OpenFlow1.5里引入數據分組類型識別流程和入口表（egress table）后，可以下發到OpenFlow交換機，從而增強了UGG模型的合理性。

4.1 UGG調度策略建模

首先對用戶的所有屬性進行模糊聚類劃分，將同類用戶歸為一個用戶群，這個網絡被用戶群集合S={1，…，S}共享，每個用戶群業務流速率為xs，s∈S，其動態范圍IS=［ms，Ms］，s∈S，其中，ms＞0，Ms＜+∞。

一個網絡包含單向的鏈路集合為：L={1，…，L}，每條鏈路的容量為 cl，l∈L。

L（s），（1≤s≤S）∩（L（s）?L）表示用戶群 S 的業務流路徑的集合，S（l）表示路由路徑經過鏈路l的用戶群集合，可以用矩陣A來表示所屬關系：

所以流的容量約束可定義為：AX≤C，其中，X=（x1，x2，…，xs）表示流速率向量，C=（c1，c2，…，cL）表示鏈路容量矢量。

用戶群的利益（效用）都由效用函數 Uβ（xs）表示，其中，β表示效用函數的類型。Uβ（xs）的數學表達式為：

Uβ（xs）的公平性由參數 β決定［10］，當 β→0 時，帶寬資源分配結果接近系統最優均值 （system optimal fairness）；當β→1 時，接近均衡平均值（proportional fairness）；當 β→2時，接近諧波均值（harmonic fairness）；當 β→+∞ 時，接近最大最小均值（max-min fairness）。由此可見，可以通過更改β的值來達到系統所需的“公平”。

引入用戶群博弈因子，該因子可以在生成用戶數據時打入IP報文的頭部標簽，通過對用戶參數的調研發現基于用戶行為的資源分配算法［11］，主要研究用戶群體的行為特征對資源分配的影響，從而統計信息，尋找規律動態分配資源，UGG策略模型只需能有效地區分不同用戶群的UGI參數以及用戶的內容劃分等級，對數據流的等級劃分可依據其對時延和分組丟失率等的要求做出評判。

對系統滿意度的定義如下：每個用戶有其期望的帶寬（UEB）和實際得到的帶寬（AB），定義用戶的期望滿意度（expected satisfaction degree，ESD）為 ESD=AB／UEB×100%，另外，對每個用戶群定義一個系統滿意度（system satisfaction degree，SSD），考察在一段時間內每個用戶群對帶寬分配的滿意度，在某一段時間內隨機取N個點，當用戶的實際帶寬超過最低滿意帶寬 （minimum bandwidth，MIB）就認為達到滿意，則有SSD=AB＞MIB的次數×100%。這樣可以通過對比合作與非合作博弈論下SSD的高低來分析不同策略的優劣。

4.2 用戶群排隊模型

單用戶訪問網絡符合泊松分布，獨立用戶訪問為離散獨立不相關事件，因此雖然不同用戶屬性的數學期望與方差不同，群變量的疊加符合線性組合關系，因此用戶群排隊模型符合設置用戶的概率分布，以最大限度地接近真實用戶群的上網特性。可以設置用戶群的上線人數服從泊松（Poisson）分布（到達率為λ），且每類用戶群的泊松分布參數不同；用戶群的在線（在線視頻業務）時長服從指數分布，數學期望為T。

4.3 用戶群的NCG調度策略建模

4.3.1 NCG調度策略

非合作博弈（non-cooperative gaming，NCG）研究人們在利益相關中如何使自己的收益最大［12］。相應在網絡中，每個自私的參與者都力圖使自己所占的帶寬達到最大，所謂“自私即私自”，采用ToS模式的IP網絡即以高優先級數據流犧牲低優先級數據流，類似于最殘酷的非合作博弈競爭。

非合作博弈論提供了一種類似市場機制的機制，參與者并不知道其他競爭者的具體消息，這使參與者之間的合作變得不可能。參考文獻［13］證明了納什均衡點在經典費用函數條件下的唯一性、存在性以及最優性。

非合作即競爭，因此比最大最小公平資源調度方法和成比例公平資源調度方法更容易造成惡性競爭，NCG思想是博弈論不可或缺的一部分，因此本文選擇NCG調度策略作為對比。

4.3.2 NCG模型的建立

定義x-i，1≤i≤S是除了第i個用戶群之外的所有用戶群生成的向量。定義任意一用戶群i的業務流流量上限為 ni（x-i），并且有：

定義有關用戶群i的費用函數Ji。Ji可以看成由價格函數 Pi和效用函數 Uβ（xi）兩項構成，Pi是通過價格來反映網絡的真實狀態，可以理解為用戶使用網絡所需付的費用：當網絡擁塞時，所需付的費用高；當網絡空閑時，所需付的費用低。綜上所述，可以定義費用函數Ji等于價格函數 Pi與效用函數 Uβ（xi）之差，即：

納什均衡點就是這個博弈對于每個參與者的最優解，從數學角度來講，在所有參與者達到均衡點時，用戶群i的費用最低，目標函數為：

4.4 用戶群的CG調度策略建模

4.4.1 用戶群CG策略思想

CG（cooperative gaming，合作博弈）是以最大化整個系統效用（利益）為最終目標［14］，CG采用了納什議價框架，核心思想［15］為：每個用戶群都會預定所需的最低帶寬，然后根據總效用函數最大化這個目標來進行調度。在CG模式下，首先要保證每個用戶群最基本的帶寬要求，然后適當地減少高等級用戶不必要的資源分配，這樣雖然損害了一方的些許利益，但系統滿意度（即運營商層面的服務滿意度指標）會提高。UCG策略就是要找到一種基于用戶群的最佳體驗，同時，即使運營商的交換機端“自主”調整業務流的流量，網絡資源逼近最佳帶寬分配點，也可以完成用戶群流調度的目標。

4.4.2 CG模型的建立

由于合作博弈論的核心思想是使系統利益 （效用函數）之和達到最大，可以表述為：對式（6）的極值問題進行拉格朗日變換，得到：

其中，pl是鏈路l的使用價格。所以轉化為給定鏈路價格的條件下滿足最大用戶收益的對偶問題：

其中，ps是用戶群s單位流量的價格，所以xsps可以看作用戶群s在流量為xs狀態下的總費用，并且 Bs（ps）可以看成用戶群s在給定價格ps下能獲得的最大效益。對于每個用戶，通過價格ps來引導解決最大值問題。對于任意的價格，當Uβ（xs）是嚴格凹函數時，用戶群s存在一個獨立的流量最大值解。

從對偶理論上講，只要找到問題D的最優解p*，對應的最佳帶寬解x*即可求出。最重要的一點是，每個網絡中的用戶群s在已知p*的情況下，獨自求出自身的最佳帶寬xs*，這一過程并不需要用戶之間的同步，易于實現。

5 仿真過程與結果

5.1 網絡構造

設置仿真網絡場景如圖4所示：共有13條鏈路、8個節點，代表OpenFlow交換機，共同隸屬于一個控制器，默認所有8個交換機都被同一自治域 （autonomous system，AS）的控制器調度，OpenFlow交換機與控制器的消息交互符合OpenFlow協議規范，鏈路容量為1 000 Mbit／s，共 10條光纖鏈路，這10條鏈路相當于骨干鏈路，其余鏈路的容量均為100 Mbit／s（代表電接口），網絡里面的每條鏈路都有接近實際情況的背景流，仿真計算時，左側的入口邊緣路由發送OFP消息數據流給右側邊緣路由器的出口端，數據流可以根據網絡狀態走不同的鏈路，步長為2 000個周期。

圖4 復雜網絡的拓撲結構

5.2 用戶參數的設定

根據某運營商服務器上的數據分析，設置3個等級A、B、C，具體參數見表 1。

表1 3類用戶的具體參數

對接近3類用戶的數目按 1：2：3的比例設置，結果見表 2。

表2 3類用戶人數的設置

5.3 鏈路背景流的設定

為了貼近實際網絡，考察了實際交換機一個端口一天內的流量圖，并進行了數學擬合，得到：

其中，N為周期，Am為正弦函數振幅，range為所取符合背景流的正弦函數幅度，random為生成的隨機函數，CI為鏈路容量。生成的背景流量如圖5所示，與實際端口流量走勢圖相比，具有極高的一致性。

圖5 仿真生成的鏈路背景流量

5.4 UCG策略實施機制

在交換機入口的OFP分組檢測到兼容UGG的0x16字節，入口首先完成差錯檢測和安全檢驗、分類或解多路復用、流量管理和控制等常規功能，然后提取該OPF分組攜帶的UGI和UEB參數，UEB采用速率模板形式映射等值帶寬，交換機如執行UGG策略，則向控制器發出OFPT_packet_in消息，控制器使用OFPT_features_request消息確認交換機并讀取其UGG請求參數，在單個執行周期內，對所有當前UGG請求執行NCG或CG算法，為每個目標用戶生成資源分配參數，生成的附加參數值插入OFP消息的填充（padding）字段，通過 OFPT_set_config消息發送給對應的交換機，交換機不再進行OFPT_features_reply響應確認，而是直接執行新參數對應的邏輯鏈路中的下一跳OFP交換機完成數據分組轉發。

5.5 UGG仿真結果

非合作博弈仿真計算結果見表3，合作博弈仿真計算結果見表4。

仿真結果用每類用戶群的平均帶寬來表示帶寬分配情況。圖6給出了數量最多的C類用戶的任一時刻的平均帶寬，可以看出即使在網絡背景流最大的情況下，鏈路也保持了較好的運行狀態。

表3 非合作博弈UGG中3類用戶帶寬分配情況

表4 合作博弈UGG中3類用戶帶寬分配

圖6 合作博弈UGG策略下C用戶群帶寬分配

通過基于CG的UG策略和NCG的對比可以看出，每個用戶群在合作博弈論的框架下被分配到更多的帶寬。

5.6 性能對比分析

綜合表3和表4可以看出，用戶采用CG的UGG策略時，各用戶群可以獲取比NCG框架下更大的平均帶寬，具體結果如圖7所示。

圖7 兩種算法在分配帶寬上的對比

而在系統滿意度這個指標上，NCG框架下A類用戶滿意度優于CG框架下的A類用戶，原因是CG框架更注重公平，它略微減少了A類用戶的高帶寬分配次數，從而滿足其他用戶群的要求，在基本不影響A類用戶滿意度的情況下使得所有用戶的滿意度得到提高，而NCG則忽略了這一點，從圖8可以看出，除了A類用戶的滿意度略有下降，但B、C類用戶的系統滿意度有較大增長。由此可見，采用CG框架的UGG調度策略在兼顧公平的基礎上能很好地分配資源，使所有用戶群都較為滿意。

圖8 兩種算法在系統滿意度上的對比

6 結束語

本文提出了一種在UCN思想下的SDN體系結構，給出一種新的OpenFlow流調度機制，從用戶群的角度出發，提出了用戶群博弈UGG的OpenFlow流調度策略，UGG的核心是采用合作博弈CG模型，在仿真中通過CG和NCG的對比，對UGG策略進行了效用評估，得到了預期的效果。本文側重結合用戶群的優先級和用戶滿意度體驗進行合作博弈資源調度，提出了一種有助于運營商實現“以用戶為中心”理念的網絡路由的新思路。

［1］MCKEOWN N，ANDERSON T，BALAKRISHNAN H.OpenFlow：enabling innovation in campus networks ［J］.ACM SIGCOMM Computer Communication Review，2008，38（2）：69-74.

［2］Open Networking Foundation.Software-defined networking：the new norm for networks［EB／OL］.（2012-04-13）［2013-06-30］.https：／／www.opennetworking.org／images／stories／downloads／sdn-resources／white-papers／wp-sdn-newnorm.pdf.

［3］Open Networking Foundation.OpenFlow switch specification 1.0.0［EB／OL］.（2009-12-31）［2012-07-25］.https：／／www.opennetworking.org／images／stories／downloads／sdn-resources／onf-specifications／OpenFlow／OpenFlow-spec-v1.0.0.pdf.

［4］陶軍，吳清亮，吳強.基于非合作競價博弈的網絡資源分配算法的應用研究［J］.電子學報，2006，34（2）：241-246.TAO J，WU Q L，WU Q.Application research of network resource allocation algorithm based on non-cooperative bidding game［J］.Acta Electronica Sinica，2006，34（2）：241-246.

［5］左青云，陳鳴，趙廣松，等.基于 OpenFlow的 SDN技術研究［J］.軟件學報，2013（5）：1078-1097.ZUOQY，CHENM，ZHAOGS，etal.Researchon OpenFlow-based SDN technologies［J］.Journal of Software，2013（5）：1078-1097.

［6］BAIK S，LIM Y，KIM J.Adaptive flow monitoring in SDN architecture ［C］／／17th Asia-PacificNetwork Operationsand Management Symposium （APNOMS），Aug 19-21，2015，Busan，Korea.New Jersey：IEEE Press，2015：468-470.

［7］梁昊馳.SDN可擴展路由及流表資源優化研究［D］.合肥：中國科學技術大學，2015.LIANG H C.Research on scalable routing and flow table resource optimization in software defined networks ［D］.Hefei：University of Science and Technology of China，2015.

［8］孔祥欣.軟件定義網絡分布式控制平臺的研究與實現［D］.北京：清華大學，2013.KONG X X.Research and implementation of distributed control plane of software-defined networking ［D］.Beijing：Tsinghua University，2013.

［9］Open Networking Foundation.OpenFlow switch specification 1.5.1 ［EB／OL］. （2009-12-31）［2015-06-16］. https：／／www.opennetworking.org／images／stories／downloads／sdn-resources／onfspecifications／OpenFlow／OpenFlow-switch-v1.5.1.pdf.

［10］FANG Z Y，BENSAOU B.Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks［C］／／23th Annual Joint Conference of the IEEE Computer and Communications Societies，March 7-11，2004，Tel Aviv，Israel.New Jersey：IEEE Press，2004：1284-1295.

［11］周景才，張滬寅，查文亮，等.云計算環境下基于用戶行為特征的資源分配策略［J］.計算機研究與發展，2014，51（5）：1108-1119.ZHOU J C，ZHANG H Y，ZHA W L，et al.User-aware resource provision policy for cloud computing ［J］.Journal of Computer Research and Development，2014，51（5）：1108-1119.

［12］ORDA A，ROM R，SHIMKIN N.Competitiveroutingin multiuser communication networks ［J］.IEEE／ACM Transactions on Networking，1993，1（5）：510-521.

［13］ALPCAN T，BASAR T.A game-theoreticframework for congestion control in general topology networks ［C］／／41st IEEE Conference on Decision and Control，Dec 10-13，2002，Las Vegas，NV，USA.New Jersey：IEEE Press，2002：1218-1224.

［14］YAICHE H，MAZUMDAR R R，ROSENBERG C.A game theoretic framework for bandwidth allocation and pricing in broadband networks［J］.IEEE／ACM Transactions on Networking，2000，8（5）：667-678.

［15］ROMANOUS B，BITAR N，ZAIDI S A R.A game theoretic approach for optimizing density of remote radio heads in user centric cloud-based radio access network［C］／／2015 IEEE Global Communications Conference （GLOBECOM），Dec 6-10，2015，San Diego，CA，USA.New Jersey：IEEE Press，2015：1-6.

A user group gaming policy of OpenFlow stream scheduling in SDN

LIN Xiaoyong1，ZHU Yuanyuan1，MEI Jie2，MI Zhengkun1
1.College of Communication and Information Engineering，Nanjing University of Postsamp;Telecommunications，Nanjing 210003，China 2.School of Information and Communication Engineering，Beijing University of Postsamp;Telecommunications，Beijing 100876，China

A user centric networking （UCN）structure based on SDN framework was proposed，which established an OpenFlow stream scheduling model named user group gaming policy.Non-cooperative and cooperative cross-layer scheduling were compared from UCN to control plane by extracting parameters of user gaming index and user expected bandwidth.Simulation results show that the user group satisfaction degree of cooperative gaming scheduling is the best and will help the communication operators to realize the concept of customer being king.

user centric networking，software defined networking，user group gaming，cooperative gaming，satisfaction degree

s： The NationalNaturalScience Foundation ofChina（No.61471203），Jiangsu ProvincialEducation Department Project（No.14KJA510004），Jiangsu Provincial Technology Department Project（No.BY2013095-2-12），2016 JPED Postgraduate Educationamp;Innovation Project

TN393.01

A

10.11959／j.issn.1000-0801.2016208

2016-06-22；

2016-07-29

糜正琨，mizk@njupt.edu.cn

國家自然科學基金資助項目（No.61471203）；江蘇省教育廳資助項目（No.14KJA510004）；江蘇省科技廳資助項目（No.BY2013095-2-12）；2016江蘇省教育廳研究生教育創新工程

林曉勇（1974-），男，博士，南京郵電大學通信與信息工程學院副教授，CCF會員，主要研究方向為軟件定義網絡、用戶中心網、未來網絡架構。

朱園園（1992-），女，南京郵電大學通信與信息工程學院碩士生，主要研究方向為軟件定義網絡、運營商網絡運營管理。

梅杰（1992-），男，北京郵電大學信息與通信工程學院碩士生，主要研究方向為無線通信理論、未來5G通信。

糜正琨（1946-），男，南京郵電大學通信與信息工程學院教授，主要研究方向為下一代寬帶通信網。