網(wǎng)絡數(shù)據(jù)包傳輸占用緩存大小混沌特性分析

唐 紅，胡 容，廖榮南

(重慶郵電大學網(wǎng)絡與計算研究中心，重慶400065)

0 引言

互聯(lián)網(wǎng)是一個規(guī)模巨大、難以控制的復雜網(wǎng)絡系統(tǒng)［1］，已發(fā)現(xiàn)其拓撲結(jié)構具有無尺度特性［2］，節(jié)點度具有冪律分布特性［3－4］，流量具有自相似性［5］，在自治系統(tǒng)(autonomous system，AS)層面互聯(lián)網(wǎng)具有富人俱樂部現(xiàn)象［6］，Internet業(yè)務量的多重分形特性［7－9］等一系列重要的復雜系統(tǒng)特性及現(xiàn)象，對互聯(lián)網(wǎng)運行維護和管理控制帶來嚴峻挑戰(zhàn)。路由器是互聯(lián)網(wǎng)中為信息流或數(shù)據(jù)分組選擇路由的設備，是網(wǎng)絡之間互連的樞紐。路由器緩存是分組交換網(wǎng)絡的重要傳輸機制，在數(shù)據(jù)包傳輸過程中，路由節(jié)點的緩存占用情況也展現(xiàn)出各種復雜的網(wǎng)絡行為，深入研究認識這些行為可以為新機制、新協(xié)議的設計及網(wǎng)絡管理提供參考，具有重要的理論和工程意義。

袁堅等對網(wǎng)絡內(nèi)部節(jié)點的整體行為進行了探討，發(fā)現(xiàn)各網(wǎng)絡節(jié)點的緩存占用大小在時間和空間上均呈現(xiàn)冪律分布［10－11］，網(wǎng)絡節(jié)點的整體行為表現(xiàn)出自組織臨界現(xiàn)象［10］。劉鋒等提出了一種描述計算機互聯(lián)網(wǎng)絡數(shù)據(jù)包傳輸?shù)暮唵文Ｐ?，并研究了沿著網(wǎng)絡固定路徑中路由節(jié)點數(shù)據(jù)包占用緩存大小的統(tǒng)計特性，研究結(jié)果表明系統(tǒng)存在自由流和擁塞流兩種相態(tài)，在自由流狀態(tài)，數(shù)據(jù)包占用緩存大小服從冪律分布，在擁塞狀態(tài)，路由節(jié)點數(shù)據(jù)包占用緩存大小呈現(xiàn)白噪聲特性［12］。還有研究結(jié)果表明，網(wǎng)絡節(jié)點數(shù)據(jù)包占用緩存大小在時間序列上具有自相似特性，自相似程度呈現(xiàn)負相關;在功率譜圖中具有冪律分布特性，在高頻段呈現(xiàn)出白噪聲特性［13］。這些研究結(jié)果表明，網(wǎng)絡節(jié)點緩存占用大小分布具有復雜網(wǎng)絡特性。

為了能更深入的研究緩存占用大小分布的復雜網(wǎng)絡行為，考慮到互聯(lián)網(wǎng)是無尺度網(wǎng)絡這一特性，本文建立了一個無尺度元胞自動機模型，以互聯(lián)網(wǎng)中實際運行的擁塞控制機制等作為元胞之間交互的規(guī)則，模擬數(shù)據(jù)包的傳輸過程，得到更為符合網(wǎng)絡實際的緩存占用大小數(shù)據(jù)，然后通過計算Lyapunov指數(shù)對節(jié)點緩存占用大小的混沌特性進行分析。

1 基于無尺度網(wǎng)絡的元胞自動機模型及仿真

1.1 仿真模型

元胞自動機是定義在一個由具有離散、有限狀態(tài)的元胞組成的元胞空間上，并按照一定局部交互規(guī)則，在離散的時間維上演化的動力學系統(tǒng)［14］。元胞自動機模型最初主要用于生物、交通和地理信息系統(tǒng)等方面的動力學研究。近年來，元胞自動機模型也被應用到網(wǎng)絡行為的研究，并且因其結(jié)構簡單，容易在計算機上實現(xiàn)，能突現(xiàn)出宏觀上的一些復雜行為，已經(jīng)成為網(wǎng)絡復雜行為的重要研究方法［15］。

大量的研究已證明互聯(lián)網(wǎng)是無尺度網(wǎng)絡，為了更為真實地模擬互聯(lián)網(wǎng)行為，本文采用Barabási和Abert［16］提出的算法構建了一個無尺度元胞自動機模型，并將元胞分為核心元胞和普通元胞。

1)核心元胞:節(jié)點度超過10的元胞定義為核心元胞，與網(wǎng)絡中核心路由器相對應。核心元胞只具有存儲和轉(zhuǎn)發(fā)數(shù)據(jù)包的功能。

2)普通元胞:節(jié)點度少于10的元胞定義為普通元胞，與網(wǎng)絡中邊緣路由器及與之相連的終端相對應，具有隨機產(chǎn)生數(shù)據(jù)包和存儲轉(zhuǎn)發(fā)數(shù)據(jù)包功能。

每個元胞都具有一個緩存空間Cn，定義元胞單位時間內(nèi)能處理數(shù)據(jù)包的最大個數(shù)為元胞的處理速度Vrouter。元胞的鄰居是在無尺度網(wǎng)絡中與該元胞有直接邊相連的節(jié)點。t時刻某元胞的狀態(tài)不但受當前時刻鄰居元胞狀態(tài)的影響，還受自己在前一時刻狀態(tài)的影響。所有元胞在局部交互規(guī)則的作用下，相互協(xié)作完成數(shù)據(jù)包的傳輸。

1.2 交互規(guī)則

網(wǎng)絡中路由器轉(zhuǎn)發(fā)數(shù)據(jù)包的實際過程是:終端隨機產(chǎn)生的數(shù)據(jù)包首先到達邊緣路由器，路由器根據(jù)數(shù)據(jù)包攜帶的目的IP地址查看路由表，然后將數(shù)據(jù)包按照正確的端口轉(zhuǎn)發(fā)到下一個路由器，經(jīng)歷過若干個中間節(jié)點，最終達到目的端。

根據(jù)這個過程，模型中的數(shù)據(jù)包通過一系列的元胞存儲轉(zhuǎn)發(fā)到達目的節(jié)點。元胞在為數(shù)據(jù)包進行路由選擇時采取靜態(tài)路由算法，即路由過程中即使發(fā)生了擁塞現(xiàn)象，元胞也不會再選擇其他的路徑。采用Floyd算法求出前述無尺度網(wǎng)絡中任意兩個元胞之間的最短路徑并存儲在每個元胞的路由表中。

模型中采用以下方式轉(zhuǎn)發(fā)數(shù)據(jù)包:在每一時刻，按照先入先出的順序取出數(shù)據(jù)包并根據(jù)路由表確定該數(shù)據(jù)包要轉(zhuǎn)發(fā)到的下一個元胞，如果下一個元胞緩存已經(jīng)飽和，則數(shù)據(jù)包在這一時刻停留在原來的元胞緩存隊列中;如果沒有飽和，則對數(shù)據(jù)包進行轉(zhuǎn)發(fā)。

參照TCP擁塞控制機制，定義了元胞交互機制如下［13］。

1)t=0時刻，初始化每個元胞已占用的緩存隊列qn，緩存隊列大小為Cn，最大時步T。

2)由于真實網(wǎng)絡中每時刻終端隨機的產(chǎn)生一定數(shù)量的數(shù)據(jù)包，因此在每一時步每個普通元胞按照均勻分布方式產(chǎn)生數(shù)據(jù)包vterminal(t)，這些數(shù)據(jù)包把與該普通元胞直接相連的元胞作為源節(jié)點，其余元胞為目的節(jié)點的數(shù)據(jù)包，并排在該元胞緩存隊列的最后面。元胞每步可以處理的數(shù)據(jù)包個數(shù)由路由最大轉(zhuǎn)發(fā)速率Vrouter(n)和發(fā)送速率vn_out(t)決定，未得到處理的數(shù)據(jù)包在緩存隊列中等待。

3)按每一時步，進行以下步驟。

第1步，每個普通元胞按照均勻分布方式隨機產(chǎn)生n個數(shù)據(jù)包，其中1nM，M=50。

第2步，計算緩存隊列大小。

(1)式中:vn_in(t)為t時刻元胞n接收的數(shù)據(jù)包數(shù)量，等于所有鄰居元胞在t時刻發(fā)送到該元胞的數(shù)據(jù)包總和;vn_out(t)為該元胞在t時刻發(fā)送出去的數(shù)據(jù)包總數(shù)。

第3步，判斷每個數(shù)據(jù)包是否到達目的端，如果沒有達到則該數(shù)據(jù)包生存時間加1。

第4步，計算每個元胞的最大發(fā)送速率vn_max(t+1)，規(guī)則如下。

第5步，計算每個元胞的期望發(fā)送速率vn_expect(t+1)。

根據(jù)實際的擁塞控制機制，為發(fā)送速率設置一個門限值，該門限值設置為該時刻此元胞最大發(fā)送速率的一半vn_max(t)/2，如果vn_out(t)vn_max(t)/2，期望發(fā)送速率成指數(shù)級增長，類似于TCP擁塞控制算法中的“慢速啟動”過程;當vn_max(t)/2≤vn_out(t)vn_max(t)時，說明網(wǎng)絡已經(jīng)快要達到飽和狀態(tài)，應該以一個較小的增長速率a進行數(shù)據(jù)的發(fā)送，模型進入“擁塞避免”階段，防止網(wǎng)絡產(chǎn)生大量的丟包。當vn_out(t)≥vn_max(t)時，采用“快速恢復”策略，網(wǎng)絡緩存隊列已經(jīng)發(fā)生擁塞，則馬上調(diào)整網(wǎng)絡的發(fā)送速率，設置一個減少系數(shù)b，用于控制發(fā)包速度，減少擁塞程度，規(guī)則如下

第6步，計算每個元胞的實際發(fā)送速率vn_out(t+1)

第7步，統(tǒng)計每一時步的丟包數(shù)，當生命周期到達時數(shù)據(jù)包都還沒有轉(zhuǎn)發(fā)到目的終端，則認為已經(jīng)丟包，并把這個數(shù)據(jù)包從元胞的緩存隊列中清除。

第8步，如果t小于時刻T，則返回第一步繼續(xù)執(zhí)行，否則退出。

1.3 仿真結(jié)果

采用無尺度網(wǎng)絡模型，生成了一個有291條邊和100個元胞構成的網(wǎng)絡拓撲，其中有11個核心元胞和89個普通元胞。利用上述局部交互機制，應用元胞自動機模型進行數(shù)據(jù)包傳輸過程的仿真，緩存隊列大小Cn=5 000，元胞處理速度vrouter(n)=500，為防止模型中在初始時刻內(nèi)發(fā)生擁塞，設置數(shù)據(jù)包數(shù)量M=50，初始發(fā)送速率vn_out(t=0)=1，參數(shù)a=1，b=1/2，經(jīng)過T=10 000步得到每一時刻元胞的緩存占用大小分布情況，總體上核心元胞的緩存占用比普通元胞的緩存占用多，但它們的分布都是隨時間波動的，而在不同時刻，100個元胞的緩存占用大小的分布卻是相似的。因文章篇幅有限，在所有元胞中隨機選取了一個核心元胞和一個普通元胞的緩存占用大小隨時間的分布情況如圖1所示。

從圖1中可以看出單個元胞緩存占用大小隨時間波動比較大，核心元胞的緩存占用大小數(shù)值分布在100—430，普通元胞的緩存占用大小數(shù)值分布在20—150范圍內(nèi)，核心元胞緩存占用大小比普通元胞的更大，產(chǎn)生該現(xiàn)象的原因是核心元胞具有更多的鄰居，每時刻流經(jīng)核心元胞的數(shù)據(jù)包數(shù)量比普通元胞多。

為了觀察不同時刻該模型中所有元胞的緩存占用大小的分布情況，取出第1 000，5 000和10 000時刻的數(shù)據(jù)，如圖2所示，分別代表了整個過程的初始階段，中間階段和結(jié)束時刻，其中X軸為不同的元胞編號，元胞按照無尺度模型中加入的先后順序編號。

圖1 節(jié)點緩存占用大小Fig.1 Size of node＇s cache occupied

圖2 不同時刻緩存占用大小分布圖Fig.2 Cache occupied size distribution in different time

從圖2中可以看出，在不同時刻，系統(tǒng)中元胞的緩存占用大小分布是相似的，系統(tǒng)處于穩(wěn)定狀態(tài)。為了驗證這個直觀結(jié)論，采用Lyapunov指數(shù)來對緩存占用大小的特性進行定量分析。

2 緩存占用大小的Lyapunov指數(shù)分析

Lyapunov指數(shù)是衡量系統(tǒng)動力學特性的一個重要定量指標，它表征了系統(tǒng)在相空間中相鄰軌道間收斂或發(fā)散的平均指數(shù)率。Lyapunov指數(shù)沿某一方向取值的正負和大小，表示長時間系統(tǒng)在吸引子中相鄰軌道沿該方向平均發(fā)散或收斂的快速程度，任何(平庸的和穩(wěn)定的)吸引子必定有一個Lyapunov指數(shù)是負的;對于混沌，必有一個Lyapunov指數(shù)是正的，因此，只要由計算得知，吸引子至少有一個正的Lyapunov指數(shù)，便可以肯定它是混沌的。即對離散動力系統(tǒng)，或者說是非線性時間序列，往往不需要計算出所有的Lyapunov指數(shù)，通常只需計算出其最大的 Lyapunov指數(shù)即可［17］。1993年，Rosenstein M T等［18］提出了一種基于小數(shù)據(jù)集計算最大Lyapunov指數(shù)的方法。在此基礎上，很多學者利用最大Lyapunov指數(shù)來分析系統(tǒng)的混沌性。由于基于無尺度元胞自動機模型中每一時刻每個元胞都不斷的有新的數(shù)據(jù)包到達和離開，是一個由大量元胞相互作用的非線性復雜系統(tǒng)，因此我們采用Lyapunov指數(shù)來對占用的緩存大小的混沌特性進行分析。

采用Michael T.Rosenstein等提出的小數(shù)據(jù)量法［18］計算最大Lyapunov指數(shù)，具體步驟如下。

1)利用 Kim.H.S 等［22］1999 年提出的 C－C 算法計算時間延遲τ、嵌入維m。

2)求出功率譜及頻率:Power=Y(1:N/2)2，f=(1:N/2)/(N);周期:period=1/f。

3)依計算時間延遲τ、嵌入維m重構相空間{Yj，j=1，2，…，M}。

4)找相空間中每個點Yj的最近鄰點Y^j，并限制短暫分離，即

5)對相空間中每個點Yj計算出該鄰點對的第i個離散時間步后的距離dj(i)

6)對每個i，求出所有j的dj(i)平均y(i)，即

7)用最小二乘法作回歸直線，該直線的斜率就是最大Lyapunov指數(shù)。

3 實驗和結(jié)果分析

3.1 單個元胞的緩存占用大小混沌特性分析

為了避免初值和過渡態(tài)的影響，取出圖1所示的元胞緩存占用大小最后1 000個數(shù)據(jù)作為分析的基礎數(shù)據(jù)，采用上節(jié)所述方法計算單個元胞緩存占用大小的最大Lyapunov指數(shù)，結(jié)果如下:計算普通元胞平均周期得到p=8.62(如圖3所示)和最佳延遲 tau=3，時間窗tw=27，嵌入維m=10(如圖4所示);計算核心元胞平均周期得到p=11.49和最佳延遲 tau=3，時間窗tw=16，嵌入維m=6.33。

曲線擬合求得普通元胞最大Lyapunov指數(shù)為0.007 1，如圖5所示，核心元胞最大Lyapunov指數(shù)為0.003，如圖6所示。

通過上面所示的流程及前面計算出來的最佳時延τ、最優(yōu)嵌入維m及平均周期p，計算出單個普通元胞和核心元胞在本次實驗中的最大Lyapunov指數(shù)分別為0.007 1和0.003，由上面介紹知道，最大Lyapunov指數(shù)為正數(shù)，便可以肯定它是奇怪的，從而知道單個普通元胞或核心元胞在不同時刻占用緩存大小變化是混沌的。

圖3 計算平均周期圖Fig.3 Calculating the average cycle

圖4 最佳延遲，時間窗，嵌入維圖Fig.4 Optimal delay，time window，embedding dimension

3.2 系統(tǒng)的緩存占用大小混沌特性分析

為了分析在不同時刻整個系統(tǒng)的緩存占用大小的混沌特性，采用圖2所示的第1 000時刻、第5 000時刻和第10 000時刻所有元胞的緩存占用大小作為分析的基礎數(shù)據(jù)。通過計算，在第1 000時刻曲線擬合求得最大Lyapunov指數(shù)為－0.822 84，如圖7所示;在第5 000時刻曲線擬合求得最大Lyapunov指為－0.683 9，如圖8所示;在第10 000時刻曲線擬合求得最大Lyapunov指為－1.183 1，如圖9所示。

圖6 核心元胞最大Lyapunov指數(shù)分布Fig.6 Most Lyapunov exponent distribution of kernel cell

圖7 第1 000時刻最大Lyapunov指數(shù)分布Fig.7 Most Lyapunov exponent distribution of the one thousand moment

圖8 第5 000時刻最大Lyapunov指數(shù)分布Fig.8 Most Lyapunov exponent distribution of the five thousand moment

通過分析在某時刻元胞之間的占用緩存大小的最大Lyapunov指數(shù)，發(fā)現(xiàn)在第1 000，5 000和10 000時刻所有元胞占用緩存大小最大Lyapunov指數(shù)均小于零，故可認為所有元胞構成的系統(tǒng)在不同時刻占用的緩存大小分布都比較均勻，系統(tǒng)處于穩(wěn)定狀態(tài)。這可以說明雖然單個元胞的緩存占用大小變化都是混沌的，但系統(tǒng)的緩存占用大小在元胞間相互作用下則處于穩(wěn)定狀態(tài)。

圖9 第10 000時刻最大Lyapunov指數(shù)分布Fig.9 Most Lyapunov exponent distribution of the ten thousand moment

上面的計算和分析表明，網(wǎng)絡中單個節(jié)點的緩存占用大小表現(xiàn)出不穩(wěn)定的混沌特性，而所有節(jié)點構成的系統(tǒng)的緩存占用大小整體上則是穩(wěn)定的。

4 結(jié)論

本文提出了一種無尺度元胞自動機模型，并引入擁塞控制等網(wǎng)絡運行機制來更真實地模擬網(wǎng)絡中數(shù)據(jù)包的傳輸;采用最大Lyapunov指數(shù)來定量分析單個節(jié)點及整體的緩存占用大小的混沌特性，發(fā)現(xiàn)單個節(jié)點的緩存占用大小是混沌的，而所有節(jié)點構成的系統(tǒng)的緩存占用大小是穩(wěn)定的，這說明該系統(tǒng)是一個復雜系統(tǒng)，雖然其中的個體狀態(tài)是不穩(wěn)定的，但整體卻突現(xiàn)出了穩(wěn)定性。下一步工作可進一步通過最佳延遲，最佳嵌入維和最大Lyapunov指數(shù)來預測下一時刻節(jié)點的緩存占用情況，從而減少擁塞發(fā)生的概率，提高數(shù)據(jù)包傳輸效率。

［1］PARK K，WILLINGER W.The Internet as a large－scale complex system［M］.USA:Oxford University Press，2005:322.

［2］YASUHIRO Sato，SHINGO Ata，IKUO Oka.A strategic approach for re－organizing the Internet topology by applying social behavior dynamics［J］.Journal of Network and Systems Management，2009，12(1－2):208－229.

［3］MICHALIS Faloutsos，PETROS Faloutsos，CHRISTOS Faloutsos.On power－law relationships of the Internet topology［C］//In SIGCOMM＇99 Proceedings of the conference on Applications，technologies，architectures，and protocols for computer communication.USA:ACM New York，1999，29(4):251－262.

［4］GEORGOS Siganos，MICHALIS Faloutsos，PETROS Faloutsos，et al.Power laws and the AS－Level Internet topology［J］.IEEE/ACM TRANSACTIONS ON NETWORKING，2003，11(4):514－524.

［5］LELAND W E，TAQQU M S，WILLINGER W，et al.On the self－simlar nature of Ethernet traffic(extended version) ［J］.IEEE/ACM Transactions on Networking，1994，2(1):1－5.

［6］ZHOU S，MONDRAGON R J.The rich－club phenomenon in the Internet topology［J］.IEEE Communication Letters，2004，8(3):180－182.

［7］FELDMANN A，GILBERT A，WILLINGER W.The changing nature of network traffic:Scaling phenomena［J］.Computer Communication Review，1998.28(2):5－29.

［8］GILBERT A，WILLINGER W，F(xiàn)ELDMANN A.Scaling analysis of random cascades，with applications to network traffic［J］.IEEE Transactions on Information Theory，1999，45(3):971－991.

［9］RUDOLF H，MATTHEW S，CROUSE V，et al.A multifractal wavelet model with application to network traffic［J］.IEEE Transactions on Information Theory，1999，45(3):991－1018.

［10］袁堅，任勇，山秀明.一種計算機網(wǎng)絡的元胞自動機模型及分析［J］. 物理學報，2000，49(3):398－402.YUAN Jian，REN Yong，SHAN Xiuming.Investigation of a cellular automation model for computer network［J］.Journal of Physics，2000，49(3):398－402.

［11］TANG Hong，WANG Ying，WANG Haitao.A network emergent computing model based on cellular automaton［C］//Sixth International Conference on Network and Parallel Computing.US:IEEE Computer Society，Oct 2009:240－245.

［12］劉鋒，任勇，山秀明.互聯(lián)網(wǎng)絡數(shù)據(jù)包傳輸?shù)囊环N簡單元胞自動機模型［J］.物理學報，2002，51(6):1175－1180.LIU Feng，REN Yong，SHAN Xiuming.A simple cellular automata model for packet transport in the Internet［J］.Journal of Physics，2002，51(6):1175－1180.

［13］唐紅，廖榮南，胡容.無尺度網(wǎng)絡的數(shù)據(jù)包傳輸元胞自動機模型研究［J］.計算機應用研究，2010，27(12):4686－4689.TANG Hong，LIAO Rongnan，HU Rong.Cellular automata model for packet transmission on scale－free network［J］.Application Research of Computers，2010，27(12):4686－4689.

［14］WOLFRAM S.Cellular automata as models of complexity［J］.Nature，1984，10(311):419－424.

［15］賀正求，賀建民，張葉琳.一種自組織的二維元胞自動機網(wǎng)絡模型及分析［J］.計算機應用，2007，27(6):1330－1333.HE Zhengqiu，HE Jianmin，ZHANG Yelin.Analysis of a self－organized network model based on two－dimensional cellular automation［J］.Computer Applications，2007，27(6):1330－1333.

［16］BARABáSI A L，ABERT R.Emergence of scaling in random networks［J］.Science，1999，286(5439):509－512.

［17］蘇捷.基于Swarm的突現(xiàn)計算模型仿真及挖掘［D］.重慶:重慶郵電大學，2009.SU Jie.The simunation and mining based on the emergent computation model of Swarm［D］.Chong Qing:Chongqing University of Posts and Communications，2009.

［18］ROSENSTEIN M，COLLINS J，LUCA C，et al.A practical method for calculating largest lyapunov exponents from small data sets［J］.Physical D，1993，65(1－2):l17－134.

［19］CHEN Xiaoyu，LEI Humin.Study of lyapunov exponent of the chaotic signal wave interception［C］//In ICECE＇10 Proceedings of 2010 International Conference on Electrical and Control Engineering.USA:IEEE Computer Society，Jun 2010:2039－2042.

［20］CHEN A，LIU Jingjing.Identification of chaotic characteristic of power load based on lyapunov exponents［C］//2009 Second Asia－Pacific Conference on Computational Intelligence and Industrial Applications.US:IEEE Computer Society，2009:461－463.

［21］MARTINEZ F，GUILLAMON A，ALCARAZ J，et al.Detection of chaotic behaviour in speech signals using the largest lyapunov exponent［C］//14th International Conference on Digital Signal Processing，US:［s.n.］，2002:317－320.

［22］KIM H S，EYKHOLT R，SALAS J D.Nonlinear dynamics，delay Times，and embedding windows［J］.Physica D，1999，127(1－2):48－60.