趙錦元，羅文，熊兵，羅可，胡志剛

(1.長(zhǎng)沙師范學(xué)院 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙，410199；2.中南大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙，410083；3.長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，湖南 長(zhǎng)沙，410114)

軟件定義網(wǎng)絡(luò)(software-defined networking，SDN)作為一種新型網(wǎng)絡(luò)架構(gòu)，將控制平面與數(shù)據(jù)平面相分離，并通過(guò)OpenFlow 協(xié)議靈活定義數(shù)據(jù)平面的分組轉(zhuǎn)發(fā)行為，極大提升了網(wǎng)絡(luò)的開(kāi)放性、靈活性和可管控性，成為未來(lái)互聯(lián)網(wǎng)最有前景的發(fā)展方向之一[1]。近年來(lái)，OpenFlow 的SDN 技術(shù)被廣泛應(yīng)用于廣域網(wǎng)(WAN)中，有效降低了廣域網(wǎng)的部署成本，提高了數(shù)據(jù)傳輸效率，改善了應(yīng)用程序性能[2]。谷歌早在2013年就部署了私有軟件定義廣域網(wǎng)B4，將其遍布全球的數(shù)據(jù)中心連接起來(lái)。經(jīng)過(guò)不斷演進(jìn)，B4 網(wǎng)絡(luò)從提供最大限度的內(nèi)容復(fù)制服務(wù)發(fā)展為電信級(jí)可用性服務(wù)，且能容納100倍以上的網(wǎng)絡(luò)流量，從而滿足未來(lái)海量數(shù)據(jù)的發(fā)展需求[3]。隨著萬(wàn)物互聯(lián)時(shí)代的到來(lái)，網(wǎng)絡(luò)數(shù)據(jù)流量迅猛增長(zhǎng)[4]，對(duì)廣域網(wǎng)的數(shù)據(jù)傳輸性能提出了更高的要求。在軟件定義廣域網(wǎng)(softwaredefined wide-area networks,SD-WAN)中，新流分組到達(dá)OpenFlow 交換機(jī)后，需發(fā)送流安裝請(qǐng)求給SDN 控制器，待控制器下發(fā)對(duì)應(yīng)的流規(guī)則后，再轉(zhuǎn)發(fā)該流中的分組，這導(dǎo)致新流分組的轉(zhuǎn)發(fā)時(shí)延明顯較大，增加了網(wǎng)絡(luò)應(yīng)用請(qǐng)求的響應(yīng)時(shí)間，進(jìn)而影響網(wǎng)絡(luò)應(yīng)用性能。為保障網(wǎng)絡(luò)應(yīng)用性能，有必要在SD-WAN 網(wǎng)絡(luò)部署前量化評(píng)估其性能。在目前已有的性能評(píng)估方法中，解析建模能夠在短時(shí)間內(nèi)快速且準(zhǔn)確地估計(jì)系統(tǒng)性能，而不需要進(jìn)行大量的仿真實(shí)驗(yàn)。排隊(duì)論作為解析建模的主流方法之一，主要關(guān)注系統(tǒng)在穩(wěn)定狀態(tài)下的平均性能，已廣泛應(yīng)用于網(wǎng)絡(luò)性能評(píng)估。因此，運(yùn)用排隊(duì)論評(píng)估SD-WAN 網(wǎng)絡(luò)性能可為其實(shí)際部署提供快捷、有效的參考。目前，METTER 等[5-10]對(duì)OpenFlow 交換機(jī)的分組處理過(guò)程進(jìn)行排隊(duì)建模，進(jìn)而估計(jì)平均分組轉(zhuǎn)發(fā)時(shí)延等性能指標(biāo)，但未區(qū)分分組類型，忽略了新流分組觸發(fā)交換機(jī)請(qǐng)求控制器安裝流規(guī)則的過(guò)程。MIAO等[11-16]基于分組優(yōu)先級(jí)建立數(shù)據(jù)平面優(yōu)先制排隊(duì)模型。同時(shí)，ALGHADHBAN 等[17-21]對(duì)交換機(jī)和控制器分別建立排隊(duì)模型，進(jìn)而構(gòu)建OpenFlow 分組轉(zhuǎn)發(fā)性能模型，以求解OpenFlow 網(wǎng)絡(luò)的關(guān)鍵性能參數(shù)。然而，上述模型未考慮控制器下發(fā)消息的處理過(guò)程，忽略了交換機(jī)處理不同類型分組的差異性，從而影響了SDN網(wǎng)絡(luò)性能評(píng)估的準(zhǔn)確性。

針對(duì)軟件定義廣域網(wǎng)這一典型部署場(chǎng)景，本文通過(guò)分析OpenFlow 交換機(jī)中的分組處理過(guò)程，將到達(dá)OpenFlow 交換機(jī)的網(wǎng)絡(luò)分組分為新流分組、舊流分組和消息分組，并考慮OpenFlow 交換機(jī)中不同類型分組的處理速率差異性，為OpenFlow交換機(jī)的分組處理過(guò)程構(gòu)建M/H3/1排隊(duì)模型，推導(dǎo)平均逗留時(shí)間等關(guān)鍵性能指標(biāo)的表達(dá)式。此外，針對(duì)新流分組觸發(fā)OpenFlow 交換機(jī)發(fā)送的Packet-in 消息，將其在控制器集群中的處理過(guò)程建模為M/M/n 排隊(duì)模型，在此基礎(chǔ)上，建立OpenFlow 分組轉(zhuǎn)發(fā)性能模型，并求解平均分組轉(zhuǎn)發(fā)時(shí)延，為SD-WAN 網(wǎng)絡(luò)的實(shí)際部署提供參考依據(jù)。

1 相關(guān)工作

目前已有不少研究者利用排隊(duì)論對(duì)SDN 數(shù)據(jù)平面性能進(jìn)行評(píng)估。METTER 等[5-6]通過(guò)建模分析單個(gè)流對(duì)流表占用率和產(chǎn)生的控制器流量的影響，進(jìn)而通過(guò)調(diào)整M/M/∞排隊(duì)系統(tǒng)擴(kuò)展到多個(gè)流的情形，給出了特定應(yīng)用參數(shù)對(duì)消息速率和流表占用率的影響。MONDAL等[7]將OpenFlow交換機(jī)分組處理過(guò)程建模為C-M/M/1/K 排隊(duì)模型，分析了OpenFlow 交換機(jī)中緩存區(qū)的最優(yōu)數(shù)目和最優(yōu)值。SOOD 等[8]忽略了OpenFlow 交換機(jī)與控制器之間的交互，利用M/Geo/1 排隊(duì)模型分析了OpenFlow交換機(jī)的流表、包到達(dá)速率、規(guī)則數(shù)量、規(guī)則位置等關(guān)鍵因素。SHEN 等[9]將流表項(xiàng)的生命過(guò)程劃分為Packet-in消息發(fā)送過(guò)程、處理過(guò)程和流表項(xiàng)服務(wù)過(guò)程，并分別建模為M/M/1、M/M/1 和M/G/c/c 模型，進(jìn)而建立流表空間估計(jì)模型，在給定路徑建立失敗的上界概率約束下，預(yù)估每個(gè)交換機(jī)所需流表存儲(chǔ)空間的最小值。TAYACHI 等[10]提出了一種具有有限緩沖區(qū)的排隊(duì)模型，假定數(shù)據(jù)包批到達(dá)系統(tǒng)，通過(guò)使用類生滅過(guò)程獲得平均隊(duì)列大小、阻塞概率和平均逗留時(shí)間等性能指標(biāo)，評(píng)估具有多個(gè)網(wǎng)絡(luò)接口卡的虛擬交換機(jī)的性能。這些工作重點(diǎn)關(guān)注OpenFlow 交換機(jī)的分組處理排隊(duì)模型，但未充分考慮分組的不同類型，導(dǎo)致性能評(píng)估結(jié)果存在明顯偏差。

一些研究者考慮分組優(yōu)先級(jí)，構(gòu)建了數(shù)據(jù)平面優(yōu)先制排隊(duì)模型，如：MIAO等[11]提出一種SDN數(shù)據(jù)平面的搶占式分組調(diào)度方案，以提高整體公平性，減少丟包率，并建立一個(gè)解析模型，量化評(píng)估該調(diào)度方案的性能，以準(zhǔn)確定位SDN 架構(gòu)的性能瓶頸。為減少失配數(shù)據(jù)包的平均逗留時(shí)間，REN 等[12-13]提出一種SDN 數(shù)據(jù)平面的優(yōu)先制服務(wù)排隊(duì)模型，運(yùn)用大偏差原則LDP 推導(dǎo)排隊(duì)長(zhǎng)度和排隊(duì)時(shí)延的概率分布，以評(píng)估SDN 數(shù)據(jù)平面輸入自相似網(wǎng)絡(luò)流量的服務(wù)質(zhì)量QoS。SINGH 等[14]利用類生滅過(guò)程分別對(duì)帶內(nèi)部緩沖區(qū)的SDN 軟件和硬件交換機(jī)建立優(yōu)先制排隊(duì)模型，求解系統(tǒng)吞吐量和排隊(duì)長(zhǎng)度等關(guān)鍵性能參數(shù)，并分析內(nèi)部緩沖區(qū)的最優(yōu)值。羅可等[15]針對(duì)軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)場(chǎng)景，利用多優(yōu)先級(jí)M/G/1 排隊(duì)模型刻畫OpenFlow 交換機(jī)的分組處理過(guò)程。RAHOUTI等[16]將SDN 網(wǎng)絡(luò)建模成帶反饋機(jī)制的雙隊(duì)列排隊(duì)系統(tǒng)，將分組劃分成多個(gè)優(yōu)先級(jí)隊(duì)列，以提供差異化的QoS 服務(wù)。上述模型區(qū)分考慮網(wǎng)絡(luò)分組的不同優(yōu)先級(jí)，但假設(shè)OpenFlow 交換機(jī)對(duì)所有分組的處理時(shí)間相同，從而影響了SDN 網(wǎng)絡(luò)性能評(píng)估的準(zhǔn)確性。

同時(shí)，還有研究人員研究了OpenFlow 網(wǎng)絡(luò)架構(gòu)下的分組轉(zhuǎn)發(fā)排隊(duì)模型。ALGHADHBAN 等[17]考慮主動(dòng)/被動(dòng)流安裝模式對(duì)匹配概率的影響，提出一個(gè)新流安裝過(guò)程的時(shí)延模型，將數(shù)據(jù)平面設(shè)備和南向通道建模為M/M/1，并采用M/G/1建?？刂破矫嬖O(shè)備，推導(dǎo)評(píng)估了系統(tǒng)容量和阻塞概率。熊兵等[18]建立了一個(gè)OpenFlow 網(wǎng)絡(luò)分組轉(zhuǎn)發(fā)優(yōu)先制排隊(duì)模型，將OpenFlow 交換機(jī)的分組轉(zhuǎn)發(fā)過(guò)程和控制器的Packet-in 消息處理過(guò)程分別建模為非搶占優(yōu)先制的M/M/n/m 和M/M/1/m 排隊(duì)系統(tǒng)，進(jìn)而求出平均分組轉(zhuǎn)發(fā)時(shí)延及其累積分布函數(shù)CDF。針對(duì)軟件定義廣域網(wǎng)，ZHAO等[19]分別對(duì)OpenFlow交換機(jī)的分組轉(zhuǎn)發(fā)過(guò)程和控制器集群的Packet-in消息處理過(guò)程構(gòu)建M/G/1 和M/M/n 排隊(duì)系統(tǒng)，并進(jìn)一步建立了控制器集群部署的優(yōu)化模型，以此獲得最優(yōu)的控制器數(shù)量。上述模型同樣忽略了不同分組類型的處理速率差異性。為此，SHANG等[20]以及ABBOU等[21]分別將交換機(jī)的分組轉(zhuǎn)發(fā)過(guò)程和控制器的Packet-in 消息處理過(guò)程建模成M/H2/1 排隊(duì)模型和M/M/1 排隊(duì)模型。然而，上述工作均忽略了控制器下發(fā)的消息分組在OpenFlow 交換機(jī)中的處理過(guò)程。

2 軟件定義廣域網(wǎng)

傳統(tǒng)網(wǎng)絡(luò)將控制邏輯和數(shù)據(jù)轉(zhuǎn)發(fā)功能集成在獨(dú)立且封閉的設(shè)備實(shí)體中，導(dǎo)致網(wǎng)絡(luò)設(shè)備結(jié)構(gòu)復(fù)雜、功能繁多、升級(jí)困難，很難直接部署新技術(shù)和新協(xié)議，阻礙了網(wǎng)絡(luò)的創(chuàng)新與演進(jìn)，越來(lái)越難以滿足未來(lái)互聯(lián)網(wǎng)的發(fā)展需求。隨著云計(jì)算、物聯(lián)網(wǎng)、邊緣計(jì)算等新型網(wǎng)絡(luò)模式的不斷涌現(xiàn)，網(wǎng)絡(luò)流量特性不斷改變，需要網(wǎng)絡(luò)能主動(dòng)適應(yīng)業(yè)務(wù)流量的變化。同時(shí)，網(wǎng)絡(luò)電視、在線直播和短視頻共享等數(shù)據(jù)密集型應(yīng)用層出不窮，所產(chǎn)生的龐大數(shù)據(jù)量給廣域網(wǎng)的傳輸性能和服務(wù)質(zhì)量帶來(lái)了嚴(yán)峻的挑戰(zhàn)。SDN 的引入使廣域網(wǎng)具有傳輸獨(dú)立性、智能路徑控制、自動(dòng)靈活配置等優(yōu)勢(shì)，為解決廣域網(wǎng)面臨的性能問(wèn)題提供了新思路，促進(jìn)了軟件定義廣域網(wǎng)快速興起。

軟件定義廣域網(wǎng)的典型部署場(chǎng)景如圖1所示。在控制平面中，SDN 控制器集群提供全局網(wǎng)絡(luò)的拓?fù)涔芾?、路徑?jì)算和策略控制等功能，通過(guò)北向接口為應(yīng)用提供統(tǒng)一的編程接口，從而使得網(wǎng)絡(luò)用戶能夠靈活制定并部署各種網(wǎng)絡(luò)策略，實(shí)現(xiàn)資源管理、業(yè)務(wù)編排、數(shù)據(jù)可視化、運(yùn)行情況監(jiān)測(cè)等服務(wù)。同時(shí)，控制器集群通過(guò)以O(shè)penFlow 為代表的南向接口協(xié)議對(duì)網(wǎng)絡(luò)交換設(shè)備進(jìn)行集中管理，建立全局網(wǎng)絡(luò)視圖，并制定分組轉(zhuǎn)發(fā)策略，以實(shí)現(xiàn)網(wǎng)絡(luò)流量的靈活調(diào)度。依據(jù)SDN 控制器下發(fā)的流規(guī)則集合快速轉(zhuǎn)發(fā)分組，使數(shù)據(jù)平面得到了充分簡(jiǎn)化。OpenFlow 交換機(jī)則通過(guò)高速鏈路將移動(dòng)通信網(wǎng)、企業(yè)網(wǎng)、校園網(wǎng)等進(jìn)行互聯(lián)，從而實(shí)現(xiàn)各種終端、數(shù)據(jù)中心、服務(wù)器及智能設(shè)備間網(wǎng)絡(luò)分組轉(zhuǎn)發(fā)處理。

圖1 SD-WAN典型部署場(chǎng)景Fig.1 A typical SD-WAN deployment scenario

在上述SD-WAN 場(chǎng)景中，當(dāng)OpenFlow 交換機(jī)收到1個(gè)網(wǎng)絡(luò)分組時(shí)，先提取其關(guān)鍵字段，然后查找OpenFlow 流表。若查找成功，則依據(jù)命中的流表項(xiàng)中的動(dòng)作集進(jìn)行處理；若查找失敗，則該分組被判定屬于新流。OpenFlow 交換機(jī)將數(shù)據(jù)包信息封裝成Packet-in 消息，并發(fā)送給SDN 控制器，新流分組則被存入緩沖區(qū)等待處理。SDN 控制器根據(jù)全局網(wǎng)絡(luò)視圖生成流規(guī)則，然后，以Flowmod 或Packet-out 消息下發(fā)給流路徑上的所有交換機(jī)。對(duì)于Flow-mod消息，OpenFlow交換機(jī)將其中的流規(guī)則更新到流表，進(jìn)而據(jù)此處理該流的所有分組，而無(wú)需控制器參與。對(duì)于Packet-out 消息，OpenFlow交換機(jī)依據(jù)其中的流規(guī)則直接處理分組，而不更新流表。

3 OpenFlow交換機(jī)排隊(duì)建模

3.1 排隊(duì)模型

在軟件定義廣域網(wǎng)中，大量網(wǎng)絡(luò)分組匯聚到OpenFlow 交換機(jī)，形成隊(duì)列等待處理。根據(jù)不同OpenFlow 交換機(jī)的處理方式，可分為新流分組、舊流分組和消息分組。對(duì)于新流分組，流表查找將失敗，需將其存入緩沖區(qū)，并將其信息封裝成Packet-in消息發(fā)送給控制器，待對(duì)應(yīng)的流規(guī)則下發(fā)后再轉(zhuǎn)發(fā)處理分組。對(duì)于舊流分組，流表查找將成功匹配1條流表項(xiàng)，進(jìn)而按其中的動(dòng)作集進(jìn)行轉(zhuǎn)發(fā)處理。對(duì)于消息分組，首先從其中提取流規(guī)則，然后將其更新到流表中，進(jìn)而轉(zhuǎn)發(fā)處理緩沖區(qū)中屬于該流的分組。不同類型分組在OpenFlow 交換機(jī)中的處理流程如圖2所示。

圖2 OpenFlow交換機(jī)中不同類型分組的處理流程Fig.2 The processing of different types of packets in OpenFlow switches

OpenFlow 交換機(jī)對(duì)每類分組的處理過(guò)程相互獨(dú)立，處理時(shí)間無(wú)記憶性，因而，每類分組的處理時(shí)間可視為服從負(fù)指數(shù)分布。上述3類分組在交換機(jī)中的處理過(guò)程存在差異性，處理速率各不相同，因此，OpenFlow 交換機(jī)的分組處理時(shí)間可視為服從3階超指數(shù)分布。在廣域網(wǎng)中，由于數(shù)據(jù)分組來(lái)源廣，流量匯聚程度高，分組在傳輸過(guò)程中的高度復(fù)用破壞了其時(shí)間相關(guān)性，使得到達(dá)交換機(jī)的分組趨于相互獨(dú)立，故交換機(jī)的分組到達(dá)過(guò)程可視為服從泊松分布[22]?；谏鲜雠抨?duì)特性分析，可將OpenFlow 交換機(jī)的分組處理過(guò)程建模為M/H3/1排隊(duì)模型。

3.2 模型求解

基于排隊(duì)論求解OpenFlow交換機(jī)的M/H3/1排隊(duì)模型，其過(guò)程為：1)分組到達(dá)過(guò)程服從泊松分布，且達(dá)到速率為λ；2)交換機(jī)按先到達(dá)先處理原則處理每個(gè)分組，且到達(dá)過(guò)程與處理過(guò)程相互獨(dú)立；3)處理時(shí)間服從3 階超指數(shù)分布，新流分組、舊流分組和消息分組的處理速率分別為μ1、μ2、μ3，對(duì)應(yīng)的概率分別為q1、q2、q3，且滿足q1+q2+q3=1。

為求解上述排隊(duì)模型，首先定義OpenFlow 交換機(jī)的狀態(tài)(a，b)。其中，a表示交換機(jī)當(dāng)前正在處理的分組類型，a為0表示沒(méi)有分組正在處理；a為1、2、3分別表示正在處理的是新流分組、舊流分組、消息分組，因此，a∈{0，1，2，3}；b表示交換機(jī)內(nèi)當(dāng)前正在處理和等待處理的分組總數(shù)，若b=0，則表明交換機(jī)內(nèi)沒(méi)有分組，a=0，即該模型的初始狀態(tài)。此時(shí)，若到達(dá)1 個(gè)分組，則b=1。因?yàn)榻粨Q機(jī)空閑，可對(duì)該分組直接進(jìn)行處理。根據(jù)分組類型不同，新的狀態(tài)可能有3 種。設(shè)第i(i=1，2，3)種類型分組的概率為qi，則狀態(tài)從(0，0)轉(zhuǎn)移到(i，0)的速率為qiλ。當(dāng)b≠0 時(shí)，后續(xù)到達(dá)的分組都需要進(jìn)入隊(duì)列等待處理，于是，狀態(tài)從(i，b)轉(zhuǎn)移到(i，b+1)的速率為λ。

此外，當(dāng)交換機(jī)處于處理狀態(tài)時(shí)，若處理完成，則狀態(tài)會(huì)發(fā)生轉(zhuǎn)移。當(dāng)b≥2時(shí)，除了正在接受處理的分組外，還有分組等待處理，而即將處理的分組是第l(l=1，2，3)種類型的概率為ql，于是，正在處理的分組服務(wù)完畢后，狀態(tài)從(i，b)轉(zhuǎn)移到(l，b-1)的速率為qlμi。當(dāng)b=1 時(shí)，OpenFlow 交換機(jī)只有正在處理的一個(gè)分組，故狀態(tài)從(i，1)轉(zhuǎn)移到(0，0)的速率為μi。圖3所示為M/H3/1 排隊(duì)模型的狀態(tài)轉(zhuǎn)移圖。

圖3 M/H3/1排隊(duì)模型的狀態(tài)轉(zhuǎn)移圖Fig.3 The state transition diagram of M/H3/1 queueing model

用pi(m)表示OpenFlow交換機(jī)內(nèi)有m個(gè)分組而正在處理的分組是第i類的概率，其中，m=1，2，…；i=1，2，3。p(0)表示OpenFlow 交換機(jī)內(nèi)沒(méi)有分組的概率。根據(jù)上述狀態(tài)轉(zhuǎn)移圖，可得下列穩(wěn)態(tài)方程：

下面利用概率母函數(shù)求解式(1)。用p(m)表示OpenFlow 交換機(jī)內(nèi)有m個(gè)分組的概率，則p(m)=p1(m)+p2(m)+p3(m)。定義概率p(m)的母函數(shù)P(x)為

同時(shí)，定義概率pi(m)的母函數(shù)Pi(x)為

則P(x)可以表示為

對(duì)式(1)中第一個(gè)等式和第二個(gè)等式兩邊分別同時(shí)乘以qix和x2，其余等式兩邊同時(shí)乘以xm+1，可得

將式(5)中所有等式兩邊分別相加，再將式(3)代入，可得

為求解Pi(x)，首先求出P1(x)、P2(x)和P3(x)的表達(dá)式。對(duì)于式(6)，分別取i=1，2，3，可得以下三元一次方程組：

令

Ai(x)=λx+μix-λx2;i=1，2，3

于是，求解式(7)中方程組得

由式(6)可知

將P1(x)、P2(x)和P3(x)的解代入式(9)，可得Pi(x)的表達(dá)式為

然后，利用洛必達(dá)法則可求出Pi(1)：

對(duì)于式(4)，令x=1，據(jù)式(11)可得P(1)的解為

由于P(1)=1，可得p(0)為

對(duì)Pi(x)求導(dǎo)，并利用洛必達(dá)法則可解得P′i(1)為

進(jìn)而可得P′(1)為

將p(0)的解代入式(14)，可計(jì)算出平均分組隊(duì)列長(zhǎng)度Ls為

利用Little 公式，可進(jìn)一步求出平均分組逗留時(shí)間W(s)為

令ρi=λ/μi，則W(s)可表示為

由于交換機(jī)只有1個(gè)處理窗口，所以，正在被處理的分組個(gè)數(shù)為0 或1，對(duì)應(yīng)的概率分別為p(0)和1-p(0)。于是，可計(jì)算出平均處理隊(duì)列長(zhǎng)度Ls為

進(jìn)一步可求得平均分組等待時(shí)間Wq為

特別地，當(dāng)μ1=μ2=μ3=μ時(shí)，令ρ=λ/μ，則平均分組逗留時(shí)間W(s)可表示為

此時(shí)，M/H3/1模型簡(jiǎn)化為M/M/1模型。

4 OpenFlow分組轉(zhuǎn)發(fā)性能模型

在軟件定義廣域網(wǎng)中，大量OpenFlow 交換機(jī)將發(fā)送Packet-in 消息到控制平面，形成隊(duì)列等待處理。為及時(shí)處理大量的Packet-in 消息，控制平面通常采用控制器集群部署方式，以增強(qiáng)其處理能力[23]。當(dāng)Packet-in 消息到達(dá)控制器集群時(shí)，若存在空閑的控制器，則直接進(jìn)行處理；否則，按到達(dá)順序加入Packet-in 消息隊(duì)列等待被處理。對(duì)于Packet-in 消息，控制器根據(jù)全局網(wǎng)絡(luò)視圖生成流規(guī)則，然后以Flow-mod 或Packet-out 消息下發(fā)給流路徑上的所有交換機(jī)。結(jié)合上述OpenFlow 交換機(jī)排隊(duì)模型，可建立OpenFlow 網(wǎng)絡(luò)分組轉(zhuǎn)發(fā)性能模型，如圖4所示。

圖4 OpenFlow分組轉(zhuǎn)發(fā)性能模型Fig.4 OpenFlow-based packet forwarding performance model

網(wǎng)絡(luò)測(cè)量結(jié)果表明，在廣域網(wǎng)中，由于流量匯聚程度高，網(wǎng)絡(luò)流之間趨于相互獨(dú)立，流到達(dá)過(guò)程往往服從泊松分布[22]。對(duì)于到達(dá)的每條新流，OpenFlow 交換機(jī)會(huì)發(fā)送1 條Packet-in 消息給控制平面。根據(jù)上述OpenFlow 交換機(jī)排隊(duì)模型，新流分組的處理時(shí)間服從負(fù)指數(shù)分布。根據(jù)泊松流的性質(zhì)可知，每臺(tái)交換機(jī)發(fā)送的Packet-in 消息仍為泊松流。假設(shè)所有交換機(jī)發(fā)送的Packet-in 消息相互獨(dú)立，根據(jù)泊松流的可加性可知，控制器集群的Packet-in 消息到達(dá)過(guò)程仍服從泊松分布。假設(shè)集群中所有控制器的Packet-in消息處理速率相同，處理時(shí)間服從負(fù)指數(shù)分布，且處理過(guò)程彼此獨(dú)立，則可將控制器集群的Packet-in 消息處理過(guò)程建模為M/M/n排隊(duì)模型。

由于平均舊流分組轉(zhuǎn)發(fā)時(shí)延Wk(old)即為分組在交換機(jī)中的平均逗留時(shí)間Wk(s)，且新流分組概率為qk1，故第k臺(tái)交換機(jī)的平均分組轉(zhuǎn)發(fā)時(shí)延Wk為

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

5.1 模型對(duì)比

為有效評(píng)估本文所提出的分組轉(zhuǎn)發(fā)性能模型，采用OpenFlow網(wǎng)絡(luò)仿真工具M(jìn)ininet 2.1.0，模擬1個(gè)簡(jiǎn)單的SD-WAN拓?fù)浣Y(jié)構(gòu)，包含3臺(tái)控制器組成的集群和20臺(tái)OpenFlow交換機(jī)。其中，交換機(jī)采用Open vSwitch 2.5.0，控制器采用OpenDaylight Beryllium，OpenFlow協(xié)議版本設(shè)為1.3。在本實(shí)驗(yàn)中，交換機(jī)的分組處理速率為30×103個(gè)/s，控制器的Packet-in消息處理速率為20×103個(gè)/s。每臺(tái)交換機(jī)同時(shí)模擬產(chǎn)生不同速率的網(wǎng)絡(luò)分組，其中新流分組占比q1為4%[24]，測(cè)得交換機(jī)的平均分組逗留時(shí)間如圖5所示。

圖5 交換機(jī)中不同分組到達(dá)速率下各模型的平均分組逗留時(shí)間對(duì)比Fig.5 Comparison of average packet sojourn time of various models with different packet arrival rates in switches

由于OpenFlow 交換機(jī)接收到新流分組后，請(qǐng)求控制器集群安裝流規(guī)則，集群將以Packet-out/Flow-mod 消息的形式下發(fā)給流路徑上的所有交換機(jī)。此外，交換機(jī)還將收到控制器下發(fā)的其他類型消息，因此，交換機(jī)收到的消息分組多于新流分組。設(shè)消息分組概率q3和新流分組概率q1的關(guān)系為q3=cq1+q0，其中，c為權(quán)重，q0為常量。在本實(shí)驗(yàn)中，c=1.2，q0=0.01，q1=0.04，則q3=0.058，進(jìn)而得到舊流分組概率q2=1-q1-q3=0.902。新流分組、舊流分組和消息分組的處理速率分別為：μ1=40×103個(gè)/s，μ2=30×103個(gè)/s，μ3=20×103個(gè)/s。將上述參數(shù)代入本文所提出的M/H3/1 模型以及現(xiàn)有的M/M/1 模型[17]和Mk/M/1 模型[25]，進(jìn)而估算出交換機(jī)的平均分組逗留時(shí)間，如圖5所示。

從圖5可以看出：由本文模型得到的估計(jì)時(shí)延比現(xiàn)有模型得到的估計(jì)時(shí)延更接近于測(cè)量時(shí)延。Mk/M/1 模型假設(shè)分組成批到達(dá)，平均每個(gè)分組的估計(jì)排隊(duì)時(shí)延更大，導(dǎo)致其估計(jì)時(shí)延與測(cè)量時(shí)延相差較大。在分組到達(dá)速率較小時(shí)，M/M/1 模型可較準(zhǔn)確地估計(jì)交換機(jī)的分組處理時(shí)間。但隨著分組到達(dá)速率不斷增加，數(shù)量最少的新流分組處理速率快，排隊(duì)時(shí)延短，而數(shù)量較多的舊流分組和消息分組處理速率慢，排隊(duì)時(shí)延越來(lái)越長(zhǎng)，導(dǎo)致其估計(jì)時(shí)延偏差越來(lái)越大。相比而言，M/H3/1模型考慮了不同類型分組的處理速率差異性，因而，其估計(jì)時(shí)延更接近于測(cè)量時(shí)延。此外，當(dāng)分組到達(dá)速率接近于交換機(jī)處理速率時(shí)，交換機(jī)將會(huì)逐步丟棄分組，故測(cè)量時(shí)延不會(huì)無(wú)限增大。

實(shí)驗(yàn)將交換機(jī)的分組到達(dá)速率設(shè)為20×103個(gè)/s，將接入集群的交換機(jī)數(shù)量設(shè)為3臺(tái)，然后，不斷增加新流分組概率q1，測(cè)得對(duì)應(yīng)的平均分組逗留時(shí)間，如圖6所示。同時(shí)，對(duì)于本文所提出的M/H3/1模型，消息分組概率q3和新流分組概率q1的關(guān)系保持不變。將上述參數(shù)代入本文所提出的M/H3/1模型和現(xiàn)有M/M/1 模型和Mk/M/1 模型，估算出交換機(jī)的平均分組逗留時(shí)間，如圖6所示。

圖6 交換機(jī)中不同新流分組概率下各模型的平均分組逗留時(shí)間對(duì)比Fig.6 Comparison of average packet sojourn time of various models with different probabilities of packets in new flows of switches

從圖6可以看出：與現(xiàn)有模型相比，本文所提出的模型的估計(jì)時(shí)延更接近于測(cè)量時(shí)延；隨著新流分組概率增加，測(cè)量時(shí)延逐漸增大。這是由于當(dāng)新流分組概率越大時(shí)，控制器下發(fā)的消息分組數(shù)量也越多，且消息分組的數(shù)量比新流分組的數(shù)量略多，而處理速率更慢，進(jìn)而導(dǎo)致交換機(jī)的平均分組逗留時(shí)間增加。本文所提出的模型由于考慮了不同類型分組的處理速率存在差異性，故估計(jì)時(shí)延也會(huì)隨之增大，始終接近測(cè)量時(shí)延。相反，M/M/1和Mk/M/1 模型由于未考慮上述差異性，其估計(jì)時(shí)延始終保持不變，與測(cè)量時(shí)延有明顯偏差。

5.2 數(shù)值分析

采用數(shù)值分析方法研究不同參數(shù)對(duì)交換機(jī)的平均分組逗留時(shí)間的影響。在實(shí)驗(yàn)中，新流分組概率、舊流分組概率和消息分組概率仍分別取值為：q1=0.040，q2=0.902，q3=0.058。這3 種類型分組的處理速率分別默認(rèn)為：μ1=40×103個(gè)/s，μ2=30×103個(gè)/s，μ3=20×103個(gè)/s，隨后調(diào)整其中1種處理速率，而其他2 種處理速率不變。根據(jù)上述參數(shù)設(shè)置，可得交換機(jī)的平均分組逗留時(shí)間與分組到達(dá)速率的關(guān)系，如圖7所示。

圖7 交換機(jī)平均分組逗留時(shí)間與分組到達(dá)速率的關(guān)系Fig.7 Relationship between the average packet sojourn time and packet arrival rates in switches

從圖7可以看出：舊流分組處理速率μ2對(duì)交換機(jī)的平均分組逗留時(shí)間影響最大，消息分組處理速率μ3的影響次之，新流分組處理速率μ1的影響最小，這是因?yàn)樾铝鞣纸M概率很小，其分組處理速率的變化對(duì)平均分組逗留時(shí)間的影響極小，可忽略不計(jì)。消息分組概率比新流分組概率略大，其處理速率最慢，所以，提高其處理速率會(huì)明顯減小平均分組逗留時(shí)間，但隨著其處理速率持續(xù)提高，平均分組逗留時(shí)間的下降幅度越來(lái)越小。相比而言，舊流分組概率極大，因此，其處理速率提高會(huì)顯著降低交換機(jī)的平均分組逗留時(shí)間。

分組處理速率仍為：μ1=40×103個(gè)/s，μ2=30×103個(gè)/s，μ3=20×103個(gè)/s。調(diào)整其中1 種處理速率，而其他2種處理速率保持不變。將分組到達(dá)速率設(shè)為20×103個(gè)/s，不斷增加新流分組概率q1，且消息分組概率q3和新流分組概率q1的關(guān)系保持不變。根據(jù)上述參數(shù)設(shè)置，可得交換機(jī)的平均分組逗留時(shí)間與新流分組概率的關(guān)系，如圖8所示。

圖8 交換機(jī)平均分組逗留時(shí)間與新流分組概率的關(guān)系Fig.8 Relationship between average packet sojourn time and the probability of packets in new flows of switches

從圖8可以看出：隨著新流分組概率增加，新流分組處理速率μ1對(duì)平均分組逗留時(shí)間的影響較小，消息分組處理速率μ3的影響急劇增大，而舊流分組處理速率μ2的影響逐漸減小。對(duì)于正常網(wǎng)絡(luò)流量，新流分組概率很小，新流分組處理速率的改變基本上不會(huì)影響平均分組逗留時(shí)間，而消息分組概率略大于新流分組概率，且消息分組處理速率較慢，因此，提高其處理速率將會(huì)明顯減少平均分組逗留時(shí)間。此時(shí)，舊流分組概率很大，其處理速率的變化將對(duì)平均分組逗留時(shí)間產(chǎn)生顯著影響。對(duì)于異常網(wǎng)絡(luò)流量，新流分組概率逐漸變大，消息分組概率隨之增大，而舊流分組概率隨之變小，此時(shí)，新流分組處理速率對(duì)平均逗留時(shí)間產(chǎn)生的影響較小，消息分組處理速率則產(chǎn)生顯著影響，而舊流分組處理速率的影響變小。

將每臺(tái)交換機(jī)的分組到達(dá)速率設(shè)為20×103個(gè)/s，3 種類型分組的處理速率分別為：μ1=40×103個(gè)/s，μ2=30×103個(gè)/s，μ3=20×103個(gè)/s，每個(gè)控制器的消息處理速率為20×103個(gè)/s。根據(jù)上述參數(shù)設(shè)置，并設(shè)置不同的控制器數(shù)量，可得平均分組轉(zhuǎn)發(fā)時(shí)延與交換機(jī)數(shù)量的關(guān)系，如圖9所示。

圖9 平均分組轉(zhuǎn)發(fā)時(shí)延與交換機(jī)數(shù)量的關(guān)系Fig.9 Relationship between average packet forwarding delay and the number of switches

從圖9可以看出：隨著交換機(jī)數(shù)量增加，平均分組轉(zhuǎn)發(fā)時(shí)延不斷增大。這是因?yàn)楫?dāng)交換機(jī)數(shù)量增加時(shí)，發(fā)送給控制器集群的Packet-in 消息速率增大，Packet-in消息的平均逗留時(shí)間增大，最終導(dǎo)致平均分組轉(zhuǎn)發(fā)時(shí)延增大。當(dāng)交換機(jī)數(shù)量較少時(shí)，發(fā)送給控制器集群的Packet-in 消息速率較小，Packet-in消息的排隊(duì)時(shí)延小，因此，平均分組轉(zhuǎn)發(fā)時(shí)延基本保持穩(wěn)定。當(dāng)交換機(jī)數(shù)量增多時(shí)，控制器集群的Packet-in 消息到達(dá)速率不斷增大。當(dāng)Packet-in消息到達(dá)速率接近控制器集群的處理速率時(shí)，Packet-in消息的排隊(duì)時(shí)延迅速增大，導(dǎo)致平均分組轉(zhuǎn)發(fā)時(shí)延急劇增大，此時(shí)，需要增加控制器數(shù)量以提高集群的處理能力，有效控制平均分組轉(zhuǎn)發(fā)時(shí)延。

將每臺(tái)交換機(jī)的處理速率設(shè)為：μ1=40×103個(gè)/s，μ2=30×103個(gè)/s，μ3=20×103個(gè)/s。共有50 臺(tái)交換機(jī)接入控制器集群，每個(gè)控制器的處理速率為20×103個(gè)/s。根據(jù)上述參數(shù)設(shè)置，并設(shè)置不同的控制器數(shù)量，可得交換機(jī)平均分組轉(zhuǎn)發(fā)時(shí)延與分組到達(dá)速率的關(guān)系，如圖10所示。

圖10 平均分組轉(zhuǎn)發(fā)時(shí)延與分組到達(dá)速率的關(guān)系Fig.10 Relationship between average packet forwarding delay and packet arrival rates

從圖10 可以看出：隨著分組到達(dá)速率增加，平均分組轉(zhuǎn)發(fā)時(shí)延逐漸增大。這是因?yàn)楫?dāng)分組到達(dá)速率增大時(shí)，交換機(jī)發(fā)送給控制器集群的Packet-in消息速率增大，此時(shí)，分組在交換機(jī)中的排隊(duì)時(shí)延和Packet-in 消息在控制器集群中的排隊(duì)時(shí)延均會(huì)增大，導(dǎo)致平均分組轉(zhuǎn)發(fā)時(shí)延快速增大。當(dāng)Packet-in 消息到達(dá)速率接近控制器集群的處理速率時(shí)，平均分組轉(zhuǎn)發(fā)時(shí)延急劇增大，有必要增加控制器數(shù)量以控制平均分組轉(zhuǎn)發(fā)時(shí)延。此外，控制器數(shù)量越多，平均分組轉(zhuǎn)發(fā)時(shí)延隨分組到達(dá)速率增加而增大的速度越緩慢。這是因?yàn)榭刂破骷旱腜acket-in 消息處理速率明顯超出其到達(dá)速率，Packet-in消息在控制器集群的排隊(duì)時(shí)延不會(huì)太大，而分組在交換機(jī)中的排隊(duì)時(shí)延逐步成為平均分組轉(zhuǎn)發(fā)時(shí)延的主要部分。

6 結(jié)論

1)針對(duì)軟件定義廣域網(wǎng)這一典型部署場(chǎng)景，通過(guò)分析OpenFlow 交換機(jī)中的分組處理過(guò)程，將到達(dá)OpenFlow 交換機(jī)的網(wǎng)絡(luò)分組分為新流分組、舊流分組和消息分組?？紤]到OpenFlow 交換機(jī)中不同類型分組的處理速率的差異性，為OpenFlow交換機(jī)的分組處理過(guò)程構(gòu)建M/H3/1 排隊(duì)模型，并推導(dǎo)出平均逗留時(shí)間等關(guān)鍵性能指標(biāo)的表達(dá)式。在此基礎(chǔ)上，結(jié)合控制器集群的Packet-in 消息排隊(duì)模型，建立OpenFlow 分組轉(zhuǎn)發(fā)性能模型，并推導(dǎo)出平均分組轉(zhuǎn)發(fā)時(shí)延。

2)通過(guò)實(shí)驗(yàn)驗(yàn)證了本文所提出的模型的分組轉(zhuǎn)發(fā)時(shí)延比現(xiàn)有模型更接近測(cè)量時(shí)延。隨著新流分組概率增加，測(cè)量時(shí)延逐漸增大。本文所提出的模型由于考慮了不同類型分組的處理速率的差異性，其估計(jì)時(shí)延也會(huì)隨之增大，始終接近測(cè)量時(shí)延。同時(shí)，采用數(shù)值分析方法對(duì)比各種因素對(duì)平均分組轉(zhuǎn)發(fā)時(shí)延的影響。平均分組轉(zhuǎn)發(fā)時(shí)延主要取決于舊流分組處理速率和新流分組概率，同時(shí)受消息分組處理速率和控制器數(shù)量的影響。這可為SD-WAN的實(shí)際部署提供參考依據(jù)。