基于網(wǎng)絡演算的網(wǎng)絡性能分析研究

王 帥，陳彥德，朱 磊

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

引言

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

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

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

1 網(wǎng)絡演算介紹

1.1 網(wǎng)絡演算概述

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

1.2 網(wǎng)絡演算理論基礎

定義一廣義增函數(shù)集合

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

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

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

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

定義四到達曲線(Arrival Curve)

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

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

定義五服務曲線(Service Curve)

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

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

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

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

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

定義七有效到達曲線

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

定義八有效服務曲線

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

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

2.1 業(yè)務流建模與到達曲線的求解

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

2.1.1 漏桶模型

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

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

2.1.2 通用信元速率模型

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

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

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

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

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

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

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

2.1.4 無記憶開關流模型

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

2.1.5 分形布朗運動流模型

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

2.2 通用服務曲線的求解

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

通用服務曲線定義為:

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

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

3 網(wǎng)絡性能指標的計算

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

圖1 節(jié)點網(wǎng)絡性能分析示意圖

3.1 時延

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

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

3.2 時延抖動

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

二是定義為時延函數(shù)的方差，即:

時延抖動能夠體現(xiàn)業(yè)務對時延穩(wěn)定程度的需求。

3.3 數(shù)據(jù)積壓

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

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

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

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

圖2 可用帶寬示意圖

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

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

4 總結與展望

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

［1］ 陳艷平.基于網(wǎng)絡演算的QoS分析方法與保障技術［T］.哈爾濱工業(yè)大學博士研究生學位論文，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］ 倪銳，周武旸，衛(wèi)國.基于網(wǎng)絡演算的無線蜂窩網(wǎng)建模及其業(yè)務匹配研究.通信學報［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］ 李慶華.基于網(wǎng)絡演算的無線自組網(wǎng)QoS確定性能確定上界研究［J］.通信學報，2008，29(9):32-39.

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

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