[發明專利]一種基于網絡演算的軟件定義網絡性能上界分析方法

在審

• 申請號: 202210252407.8
• 申請日: 2022-03-15
• 公開（公告）號: CN114726760A
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 魏德賓;劉暢;楊力;潘成勝
• 申請（專利權）人: 大連大學
• 主分類號: H04L43/0852
• 分類號: H04L43/0852;H04L41/142;H04L49/9005;H04L49/15;G06F17/11
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 李猛

1.一種基于網絡演算的軟件定義網絡性能上界分析方法，其特征在于：包括以下步驟：

A、SDN數據流處理流程描述

在SDN中，交換機負責網絡數據的高速轉發，是網絡轉發平面；交換機由邏輯集中的控制器進行全局控制，控制器在建立OpenFlow通道時，給交換機設置初始流條目，以使交換機將流表未命中的數據包送往控制器，控制器進行路由決策，在計算出下一端口時下發流條目給交換機，交換機完全依賴于流條目轉發數據包；流經過SDN的處理流程描述如下：

設A1表示進入交換機的流，經過流表管道處理后，會出現兩種情形：流表命中流H1和流表未命中流M1；H1在管道處理過程結束后執行動作集，所述動作集包括轉發、丟棄、排隊和修改域；流表未命中時交換機向控制器發送一個異步消息Packet-in，該消息中包含完整的數據包或僅包含包頭，但交換機要對數據包進行緩存，且消息中包含緩沖區ID；控制器對Packet-in消息處理后，向交換機發送Packet-out消息，將數據包從交換機的指定端口轉發出去，相應的，消息中含有完整數據包或緩沖區ID；若控制器在決策時得到數據包的下一跳，發送Flow-Mod消息，以向流表中添加相應流條目，防止后續數據包再次觸發Packet-in消息；M1*實線表示控制器對Packet-in消息處理后，向交換機發送Packet-out消息；M1*虛線表示控制器向流表中添加相應流條目；M2和M2*分別表示來自其他交換機的未命中流和控制器的輸出流；

B、建立網絡演算中的基本定義

定義1：廣義增函數集

設f(·)是非負實數集上的函數，如果對任意非負實數s,t有：

則稱F是廣義增函數集；

定義2：最小加卷積

設f(·),g(·)∈F，它們的最小加卷積為

式中，為卷積運算符，inf為函數的下確界；

定義3：到達曲線

設α(t),t≥0是一個廣義增函數，R(t)是數據流的累積輸入函數，如果對于0≤s≤t，有R(t)-R(s)≤α(t-s)，則稱α(t)為R(t)的到達曲線；

仿射到達曲線用表示；參數ρ和σ分別稱為平均速率和突發量；

定義4：服務曲線

設有一個系統S和通過系統S的流，該流的累積輸入和輸出函數分別為R(t)和R^*(t)，如果β(t)是廣義遞增的，β(0)＝0且則稱系統S向流提供了一條服務曲線β(t)；

系統S提供給流的服務曲線是系統S保證給流的服務能力的下界；使用延遲-速率函數β(t)＝R(t-T)⁺表示服務曲線；這里的R為系統服務速率，T為系統服務延遲，(t-T)⁺＝max{0,t-T}；

定義5：時延上界與積壓上界

給定一個流，進入系統S時被到達曲線α(t)約束，通過系統S時系統S提供服務曲線β(t)，在任意時刻t，時延上界為

其中h(α,β)為α與β的水平距離；數據積壓上界為

其中sup是函數的上確界；

C、分析流表命中時的網絡性能

在SDN中，設流經網絡的數據流具有仿射到達曲線α(t)＝ρt+σ，路徑上有N個交換機，第i個交換機為該流提供的延遲-速率服務曲線為βⁱ(t)＝R_i(t-T_i)⁺,i∈{1,2,…,N}，R_i和T_i分別為第i個交換機的服務速率和服務延遲，d為交換機間的線路的時延，它提供服務曲線為δ_d(t)；多服務節點串聯分析在網絡演算理論中遵循“pay-bursts-only-once”；故由串聯屬性得整個網絡為該流提供的服務曲線為：

則當ρ≤R_i,i＝1,2,…,N時，網絡端到端時延上界和數據積壓上界的計算公式為：

D、分析流表未命中時網絡性能

流表未命中時，交換機向控制器發送Packet-in消息，在交換機安裝流條目之前，該流后續數據包進入交換機后依舊觸發流表未命中的問題，分為數據包被緩存在交換機和數據包被轉發至控制器兩種情況，具體步驟如下：

D1、未命中時數據包被緩存在交換機

為防止包頭相同的數據包再次觸發Packet-in消息，交換機為該流建立HOLD流條目，流后續數據包匹配此流條目而被緩存在交換機中；若為網絡最差情況，后續流在此交換機所經歷的額外時延表示為：

其中t_sd為交換機處理時延，t_cq為控制器中排隊時延，t_cd為控制器中處理時延，d_c為OpenFlow控制通道時延；M為SDN中流的數量，L_max表示數據包的最大長度，R_s是交換機的服務速率，R_c是控制器的服務速率；

流在交換機i處發生流表未命中，則此交換機i與控制器視為提供了服務曲線為未命中后續流所經歷的額外時延，根據最小加運算的交換律、結合律，則整個網絡提供的服務曲線表示為：

設到達曲線為仿射函數α(t)＝ρt+σ，當ρ≤R_i,i＝1,2,…,N時，網絡端到端時延上界D(t)和積壓上界B(t)計算公式為：

D2、未命中時數據包被轉發至控制器

交換機安裝控制器下發的流條目前，后續數據包均流表未命中，匹配table-miss流條目而被送往控制器；因流條目timeout字段，在兩終端通信的過程中，流表命中及未命中兩種情況會交替出現，即A₁＝H₁+M₁，在同一時刻，H₁與M₁其中之一的速率為0，兩者相當于A₁的兩個分量；確定性網絡演算理論是計算網絡發生最差情況時的性能邊界，若在t₁時刻流表未命中，在t₂時刻流條目下發且被安裝好，在t₃時刻流條目被刪除，網絡最差情況為：在時間段(t₁,t₂]內，數據包被交換機送往控制器；在時間段內(t₂,t₃]無數據包到達交換機，導致流條目因idle_timeout字段設置的超時被刪除，即t₂+idle＝t₃，其中idle為超時的時間；交換機刪除此流條目后，后續數據包因流表未命中重復此過程；在此情形下，為了得到更準確的SDN網絡端到端時延上界和積壓上界，設置流的到達曲線為自定義函數α_M1(t)，該到達曲線比仿射到達曲線更為嚴格，即α_M1(t)≤α(t)；

其中為下取整函數，若控制器為流M₁提供的服務曲線為β_c，則整個網絡為流M₁提供的服務曲線表示為：

其中，R_c是控制器為在t_miss階段送往控制器的流提供的服務速率，T_c是控制器的服務延遲；

則此時的端到端時延上界與仿射到達曲線的時延上界相同，即：

令R＝min{R₁,…,R_N,R_c}，x＝t_miss+idle，根據到達曲線的特點，在每個((n-1)x,nx]內討論數據積壓；

令當T∈((n-1)x,T₁]時，數據積壓上界在T處取得，即將T帶入積壓上界計算公式可得：

當T∈(T₁,nx]，因R·(nx-T)＜min{ρ·idle,σ}，數據積壓上界在nx處取得，于是有數據積壓上界的計算公式為：

B(t)≤σ+n[ρt_miss+min{ρ·idle,σ}]-R[n(t_miss+idle)-T] (16)。