基于網絡演算的網絡性能分析研究

王 帥，陳彥德，朱 磊

(解放軍理工大學 通信工程學院，江蘇 南京 210007)

引言

被稱為第三次工業革命的信息技術產業發展至今，網絡已在人們日常生活中變得不可或缺。各式各樣的新興業務使網絡從數據型通信網絡向能夠傳送語音、圖像、視頻、動畫的多媒體綜合網絡發展。新興的多媒體業務和實時業務的業務流復雜度與突發性與以前相比有了很大變化，對網絡服務質量(即QoS，Quality of Service)也有了更高的要求。QoS是一種可控的系統行為，是服務性能綜合效果的體現［1］，可以由服務可行性、適應性、活性等多種描述來表示，具體到網絡性能定量分析上，主要指帶寬(吞吐量)、時延、時延抖動、數據積壓等。對QoS有需求的業務往往對一項或多項指標要求較高，如音頻和視頻業務等會話類業務要求時延和時延抖動盡量小以防止失真，而流媒體點播業務則更看重控制丟包率的大?。?］。

對網絡性能進行定量分析以求得各項QoS指標是網絡選擇、接納控制、資源預留、垂直切換等網絡研究的基礎，這一課題涉及網絡服務模型、網絡業務流模型、節點服務策略以及網絡性能分析方法等。傳統網絡性能分析主要基于排隊論、統計學、隨機過程和圖論，結合盡力服務(best effort)模型求解網絡穩定狀態下的性能指標，在刻畫和分析復雜業務流的實時網絡性能上比較欠缺。伴隨著IntServ［3］(Integrate Service)、DiffServ(Differentiated Service)等QoS服務模型和自相似業務流模型的提出，網絡演算［4］因為能夠直觀、準確、實時地描述業務流端到端性能而獲得了廣泛地關注。

本文就基于網絡演算的網絡性能分析研究這一課題，對如何應用網絡演算分析網絡端到端性能進行論述。介紹了網絡演算的理論知識和網絡性能分析中到達曲線和服務曲線的求解，如何求解各項網絡性能指標并進行了總結和展望。

1 網絡演算介紹

1.1 網絡演算概述

網絡演算是近十年來新興的對網絡排隊系統性能定量分析的數學工具。它是一套基于最小加代數的數學演算理論。網絡演算以廣義增函數為運算對象，以節點為研究目標，通過分析流經節點的端到端業務流，推算整個網絡的服務性能。網絡演算最早由 R.L.Cruz［5］提出，他所定義的(σ，ρ)流量模型發展形成了到達曲線。服務曲線則由Cruz和Sariowan［6］在GPS模型的基礎上提出，服務曲線能夠看作是對服務策略和調度策略的一種抽象描述。另外C.S.Chang［7］、J.Y.Le Boundec、Gallager等人也做出了大量基礎研究工作，提出并總結出基于到達曲線和服務曲線的網絡分析方法，最終形成了網絡演算理論體系。網絡演算又分為確定網絡演算(Deterministic Netwrok Calculus)和隨機網絡演算(Statistical Network Calculus)。確定網絡演算研究已比較成熟，用于分析端到端業務流最壞情況下的網絡性能。隨機網絡演算在最近幾年內發展迅速，主要是將概率論的相關知識引入最小加代數體系，將網絡演算的適用范圍從確定性問題擴展到隨機性問題上。

1.2 網絡演算理論基礎

定義一廣義增函數集合

若f(x)連續且一階可導，則定義廣義增函數集合為:

最小加卷積滿足結合律和交換律，且當f(0)=g(0)且均為凹函數時，f?g≤min{f，g}。

定義三最小加反卷積(Min-plus Deconvolution)

φ與最小加卷積類似，?f，g∈F，f與g的最小加反卷積為:

定義四到達曲線(Arrival Curve)

假設一端到端業務流流經網絡節點，到達曲線可以看作是對流入節點業務流的限制，即流量包絡［8］。給定廣義遞增函數α(t)，定義域t≥0，假設數據流流經某節點且其到達累積函數為I(t)，則對?s≤t，當滿足:

稱α(t)為I(t)的到達曲線，或稱I(t)受限于到達曲線α(t)。

定義五服務曲線(Service Curve)

服務曲線描述了節點的服務能力，確切地說是節點為滿足業務QoS需求所需要提供的服務下限。給定廣義遞增函數β(t)，定義域t≥0。假設流入流出節點的業務流的累積函數分別為I(t)和O(t)，對?t≥0，?t≥0 ≤ t，t0≥0，滿足:

則稱β(t)為節點提供的服務曲線，或稱節點提供給業務流的服務能力受限于服務曲線β(t)。

定義六網絡服務曲線(Service Curve)

節點以串聯方式依次流過N個網絡節點，假設每個節點提供的服務曲線為βn(n=1，2，…N)。則這N個節點串聯形成的端到端網絡服務曲線為:

網絡演算是基于單個節點的網絡性能分析理論，通過網絡服務曲線可以把N個節點的串聯系統等效成一個大型節點進行分析，克服了傳統網絡性能分析方法對網絡拓撲依賴性強、無法很好地對如戰場通信網絡這樣拓撲結構變化起伏較大的網絡進行分析的缺點。

定義七有效到達曲線

則稱αε為到達流量I(t)的有效到達曲線［8］，當ε=0時有效到達曲線退化成定義四中的到達曲線α(t)。

定義八有效服務曲線

則稱βε為到達流量I(t)的有效服務曲線［8］，可以理解為節點以(1－ε)的概率為業務流提供服務曲線βε，當ε=0時有效服務曲線退化成定義五中的服務曲線β(t)。

2 到達曲線與服務曲線的求解

2.1 業務流建模與到達曲線的求解

提取業務流的流量特征，構建業務流模型，進而獲得到達曲線是進行網絡演算的前提。在傳統的網絡性能分析中，通常用排隊論和隨機過程刻畫業務流模型，如泊松模型、開關模型和Markov模型［9］。而在新興業務中，業務流的復雜性和突發性大大增加。隨著業務流建模研究的不斷發展，在不同類型網絡和QoS保障體系中，對業務流模型的分類也不盡相同。在實際應用網絡演算解決具體問題時，需根據應用場景的特征對相應業務流建模獲得到達曲線。如從宏觀角度可根據業務流的自相似和多分形特征將業務流模型分為短程相關模型、長程相關模型和自相似模型［10］。而在無線蜂窩網絡中業務流可分為受約束流、無記憶開關流、分形布朗運動流三類。本節以確定網絡演算和隨機網絡演算中應用最為廣泛幾種流量模型為例［11-12］，對到達曲線進行綜述。

2.1.1 漏桶模型

漏桶算法(Leaky Bucker Algorithm)是一種典型的QoS業務流規整算法，主要用于描述數據型流量。

根據到達曲線可以看出，數據源能夠一次發送數據量為b(bit)的數據，但在較長時間內速率不會超過γ(bit/s)。

2.1.2 通用信元速率模型

通用信元速率算法(Generic Cell Rate Algorithm)主要應用于描述ATM網絡當中的業務流。

它的到達曲線由一個階梯函數刻畫:

通用信元速率模型描述的是發送分組大小恒為k個數據單元的業務流，分組間時間間隔為T'個時間單元，修正參數 表示實際時間間隔與理想時間間隔T'之間的差值。

2.1.3 恒定比特流模型和可變比特流模型

漏桶模型和通用信元速率模型刻畫了大多數的QoS數據業務，恒定比特流模型和可變比特流模型作為這兩種模型的擴展在特定場景下也有廣泛的應用。恒定比特流是最簡單的業務比特流，可以看作是桶深無限大的漏桶模型的一個特例，到達曲線為:

可變比特流的代表是RSVP(ReSerVation Protocol)協議中的path報文。它描述了確保服務中定義的T-SPEC流量特征信息，到達曲線為:

其中參數M為最大報文長度，p為峰值速率，b為桶深，r為平均速率。在進行業務QoS協商和資源預留時，會話發起方首先發向目的節點送path報文，中間節點會讀取業務流信息并根據自身服務能力判斷能否達到業務流的QoS需求，達到需求才繼續更新和傳遞path報文，最后得到能夠提供可靠服務的業務流端到端傳輸路徑。

2.1.4 無記憶開關流模型

無記憶開關流多用于語音電話、彩鈴、視頻電話業務。對于無記憶開關流，在ON狀態下業務以恒定速率R產生數據流，而OFF狀態下則不產生數據流。無記憶開關流的流量特性具有統計性，用確定網絡演算無法描述，它的有效到達曲線為:

2.1.5 分形布朗運動流模型

分形布朗運動流是一種典型的自相似流，它主要用于描述手機電視、手機游戲、WAP等多媒體業務。分形布朗運動的到達累積函數I(t)=ρt+βZt。Zt為自相似參數為H的分形布朗運動，ρ代表流量均值，β2代表流量方差。分形布朗運動流的有效到達曲線為:

2.2 通用服務曲線的求解

網絡演算最早是針對IntServ服務體系提出的。在IntServ中各類業務流根據流量特征被分類建模，并通過資源預留與QoS協商達到確保服務。資源預留的過程是一個分組調度過程，而服務曲線正是對分組調度過程的抽象。Parekh和Gallagher通過研究GPS(Generalized Processing Sharing)調度算法定義了嚴格服務曲線，描述了節點向業務流提供最低服務的能力。包括GPS在內，虛擬時鐘調度(Virtual Clock Scheduling)、自時鐘公平排隊(Self-clock Fair Scheduling)等調度算法都滿足保證速率GR(Guranteed Rate)框架，并符合速率延遲時間(Rate-lantency)模型。因此，IETF定義了通用服務曲線，為各應用場景下服務曲線的推算提供了模版。

通用服務曲線定義為:

其中R為節點提供的服務速率，T是與R有關的時延參數。R與節點自身服務能力以及調度算法有關，在不能直接求得R時，可以將R等效為該節點到下一節點間的鏈路吞吐量求解。

T主要用于表示一定的時延，具體定義為:

3 網絡性能指標的計算

本節主要介紹網絡演算如何通過到達曲線和服務曲線求解網絡節點的主要性能指標。假設一條流經N個節點的數據流，記廣義增函數Ih(t)、Oh(t)分別為為節點h的輸入輸出流量累積函數。節點的到達曲線和服務曲線如圖1所示:

圖1 節點網絡性能分析示意圖

3.1 時延

對業務流量來說，節點對數據的處理過程可以看作一個排隊問題，假設節點對數據的處理是無時延的，那么一個數據比特進入和流出節點的時間應該相同。則任意時刻t0下，時延D0(t)為服務曲線與到達曲線之間的水平偏差值，即O(t0+D(t0))=I(t0)。最大水平偏差值D即為時延上界:

時延上界表示業務流經過節點經歷的最大可能時延，即只有D不超過業務流的時延限制，節點才能為該業務流提供可靠的服務保障［25］。

3.2 時延抖動

時延抖動一般有兩種定義方法，一是定義為數據傳輸中時延的最大差值，即:

二是定義為時延函數的方差，即:

時延抖動能夠體現業務對時延穩定程度的需求。

3.3 數據積壓

假設業務流流經節點沒有數據損失，則任意時刻t0下，數據積壓B0(t)為到達曲線與服務曲線之間的垂直偏差值，即O(t0)+B(t0)=I(t0)。最大垂直偏差B(t)為數據積壓上界:

數據積壓上界為業務流經過節點進行排隊處理時的最大隊列長度，即只有節點緩沖區大小不小于B(t)，節點才能為該業務流提供可靠地服務保障。

3.4 可用帶寬、有效帶寬和等效容量

假設一條到達曲線為α(t)，且要求時延不超過DQoS的業務流能夠以確保服務通過預留緩沖區長度為BQoS的節點。當α(t)為凹函數時，可用帶寬、有效帶寬和等效容量如圖2所示。

圖2 可用帶寬示意圖

可用帶寬E為節點實際能夠為業務流提供的傳輸速率，表現為服務曲線的斜率。有效帶寬ED為能夠滿足時延 DQoS要求的最小傳輸速率，表現為t=－D處與到達曲線之間的斜率，即:

等效容量為給定到達曲線α(t)和節點緩沖區長度為BQoS時的傳輸速率，表現為縱坐標數據量為B處與到達曲線的斜率，即:

4 總結與展望

網絡演算能夠直觀、準確、實時地分析節點網絡性能，進而計算整個網絡的性能邊界，在解決復雜業務流的QoS保障問題上得到了廣泛應用。在近十年的發展中，確定網絡演算的理論已相對成熟，并應用于解決各種網絡性能分析問題［13-15］。隨機網絡演算將網絡演算的應用從求解最壞情況下的性能邊界擴展到求解一般情況下的具體性能，使網絡演算能對使用統計復用的多媒體業務流進行更加準確的分析。但由于將概率論完全引入最小加代數系統還存在一定難度，隨機性網絡演算的研究還有很大的發展空間。總之，基于網絡演算的網絡性能分析方法能夠填補傳統網絡性能分析方法的不足，為解決各類網絡分析問題提供了新的方法和思路，具有良好的應用前景，值得進一步關注和研究。

［1］ 陳艷平.基于網絡演算的QoS分析方法與保障技術［T］.哈爾濱工業大學博士研究生學位論文，2012:3.

［2］ C.Partridge S.Shenker，R.Guerin.Specification of guaranteed quality of service［C］.RFC 2212，Internet Engineering Task Force.September 1997:889-893.

［3］ S.Berson S.Herzog R.Braden(Ed.)，L.Zhang，S.Jamin.Resource reSer Vation Protocol(RSVP)version 1，functional specification［C］.RFC 2205，Internet Engineering Task Force.September 1997:953-962.

［4］ Jean-Yves Le Boudec，Patrick Thiran.Network Calulus:A Theory of Determinstic Queuing System for the Internet［C］.Herdelberg:Springer-Verlag.2004:140-151.

［5］ R.L.Cruz.A calculus for network delay，part I:Network elements in isolation［J］.IEEE Trans Inform Theory.Jan 1991，37:114-131.

［6］ H.Aariowan.A service curve approach to performance guarantees in integrated service networks［C］.PhD dessertation，Univ Calif San Diego.1996:46.

［7］ C.S.Chang.Performance Guarantees in Communication Networks［C］.Springer-Verlag.New York.2000:930-939.

［8］ 倪銳，周武旸，衛國.基于網絡演算的無線蜂窩網建模及其業務匹配研究.通信學報［J］.2010，31(7):33-39.

［9］ C.Florin，B.Almut，L.Jorg.Sealing properties of Statistieal End-to-End Bounds in the Network Caleulus［J］.IEEE Transaetionson Information Theory，2006，52 (6):2300-2312.

［10］ G.AndrasB Jozsef Astochastie Extension of Network Caleulus for Workload Loss Examinations［J］.IEEE Conununications Letters，2006，10(5):399-401.

［11］ M Flider，S Recker.Conjugate network calculats:a dual approach to applying the legendre transform［J］.Computer Networks，2006 50(8):1026-1039.

［12］ A.Burchard C.Li，J.Liebeherr.A network calculus with effective bandwidth［C］.Technical Report CS － 2003-20，U-niversity ofVirginia，Computer Science Department.Nov 2003.

［13］ 李慶華.基于網絡演算的無線自組網QoS確定性能確定上界研究［J］.通信學報，2008，29(9):32-39.

［14］ 喻莉，姜烈，羅晶晶，張婕.基于跨層網絡演算模型的無線網絡移動性能分析［J］.電子與信息學報，2012，34(1):57-62.

［15］ 李慶華.基于網絡演算的無線自組網TCP性能分析與改進［T］.中南大學，研究生博士學位論文，2010:42-56.