摘 要：以往的研究中，對瓶頸延遲從時間維度上來討論其演化特征的相關(guān)論文很少，個別研究由于其獲得探測數(shù)據(jù)的探測方式有限，因此只是局限于小時間尺度上對其進行研究分析，無法從宏觀拓撲結(jié)構(gòu)上把握整體網(wǎng)絡行為中瓶頸延遲的演化特征，而本文從CAIDA授權(quán)的海量真實拓撲數(shù)據(jù)中選取五年數(shù)據(jù)開展瓶頸延遲的演化特征的分析，將有助于進一步認識Internet中瓶頸延遲的本質(zhì)。

關(guān)鍵詞：網(wǎng)絡延遲；瓶頸延遲；演化分析

中圖分類號：TP393

近年來隨著信息技術(shù)的不斷發(fā)展，網(wǎng)絡規(guī)模正在以指數(shù)速度突飛猛進的擴大中，互聯(lián)網(wǎng)已逐漸演化成為當今最具市場潛力、發(fā)展最快的產(chǎn)業(yè)之一。伴隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡性能[1]的可靠性、網(wǎng)絡的效率及網(wǎng)絡服務的質(zhì)量也越來越引起網(wǎng)絡用戶以及相關(guān)科研工作者的注意[2-3]。

從復雜網(wǎng)絡的角度來探索整個互聯(lián)網(wǎng)拓撲特征的演化，不少人是從復雜網(wǎng)絡的社團[4]、路由、新生與消亡節(jié)點的演化[5]特征入手的。姚冬[6]等人在2009年對網(wǎng)絡中的新生、消亡節(jié)點進行演化分析，網(wǎng)絡中新生與消亡節(jié)點的變化幅度也隨著網(wǎng)絡的發(fā)展逐漸趨于穩(wěn)定；Palla G[7]在2007年對社會網(wǎng)絡中的社團問題進行演化分析；Fay D[8]在2010年認為Internet與生俱來的異構(gòu)性、動態(tài)性、發(fā)展的非集中性以及如今龐大的規(guī)模給網(wǎng)絡拓撲演化建模帶來巨大挑戰(zhàn)。但是目前還鮮有研究人員從延遲乃至瓶頸延遲的角度研究互聯(lián)網(wǎng)拓撲結(jié)構(gòu)的演化特征，因此本文對網(wǎng)絡延遲，尤其是對網(wǎng)絡延遲產(chǎn)生重要影響的瓶頸延遲的特征量進行演化分析，勢必會對發(fā)現(xiàn)網(wǎng)絡瓶頸、優(yōu)化網(wǎng)絡配置等方面的工作產(chǎn)生一定的意義。

本文采取的數(shù)據(jù)樣本為CAIDA的amw探測節(jié)點數(shù)據(jù)，時間跨度為2009-2013五年時間每年五月某一周期（三天為一周期）的數(shù)據(jù)。

1 基本定義

定義1.1路徑（Path）：一個數(shù)據(jù)包在從探測源節(jié)點SRC到達目的節(jié)點DST的過程中，中間分別經(jīng)過節(jié)點R1，R2，…，Rn-1，令R=（SRC，R1，R2，…，Rn-1，DST），則稱R為從源節(jié)點到目的節(jié)點間的一個路徑，對應的n被稱為訪問直徑（Traveling Diameter）。若沿途所有節(jié)點對ICMP探測數(shù)據(jù)包都響應并返回相應的信息到源節(jié)點端，則稱該路徑為一個完整的有效路徑，本文中全部選取有效路徑。

定義1.2鏈路（Link）：對于一條完整的路徑R=（SRC，R1，R2，…，Rn-1，DST），其中SRC，R1，R2，…，Rn-1，DST分別為某一條路徑中數(shù)據(jù)包所經(jīng)過的節(jié)點，則稱任意相鄰兩點間（SRC，R1）、（R1，R2）、…、（Rn-1，DST）分別為該路徑中的第1條鏈路、第2條鏈路、…、第n條鏈路。

定義1.3網(wǎng)絡延遲（Network Delay）[9-10]：指從監(jiān)測源節(jié)點發(fā)送一個探測數(shù)據(jù)包到目的節(jié)點，如果數(shù)據(jù)包在傳輸?shù)倪^程中完整地到達目的節(jié)點，則把數(shù)據(jù)包從監(jiān)測節(jié)點到目的節(jié)點所消耗的時間稱為一個有效的網(wǎng)絡延遲。

定義1.4鏈路延遲（Link Delay）：是指在網(wǎng)絡上傳播過程中的數(shù)據(jù)包，設網(wǎng)絡直徑為n，網(wǎng)絡延遲為T，中間經(jīng)過的節(jié)點為{R1，R2，…，Rn}，共n段鏈路，每段鏈路所消耗的時間分別為{t1j，t2j，t3j，…，tnj}，則{t1j，t2j，t3j，…，tnj}表示為第j條路徑的鏈路延遲。所謂最大鏈路延遲是指，設tmaxj=max{tij|i=1，2，…，n}，則稱tmaxj為該鏈路延遲中的最大鏈路延遲。

定義1.5瓶頸延遲（Bottleneck Delay）：在網(wǎng)絡中，從監(jiān)測節(jié)點src到目的節(jié)點dst傳播過程中的數(shù)據(jù)包，設網(wǎng)絡直徑為n，網(wǎng)絡延遲為T，中間經(jīng)過的節(jié)點的鏈路延遲分別為{t1j，t2j，t3j，…，tnj}，設tmaxj=max{tij|i=1，2，…，n}，如果tmaxj≥εT（ε為修正參數(shù)，0<ε<1，且n>>1/ε），當ε>30%時，定義tmaxj為路徑中的瓶頸延遲，相應的瓶頸延遲所在的鏈路被稱為延遲瓶頸（Delay Bottleneck）；當ε>50%時，定義tmaxj為路徑中的絕對支配延遲，即tmaxj在路徑中占據(jù)著絕對支配的地位。

2 瓶頸延遲特征量的演化

2.1 有效路徑的演化

所謂產(chǎn)生瓶頸延遲的有效路徑是指數(shù)據(jù)包在傳輸?shù)牡爻讨?，沿途所?jīng)過的節(jié)點都有響應，并都返回信息到源節(jié)點端的路徑稱為有效路徑。下面具體的看一看近五年內(nèi)瓶頸延遲有效路徑的演化，如圖1所示：

如圖1所示，有效路徑的條數(shù)到2012年達到頂峰，五年時間有效路徑增加約10000余條，之后2013年瓶頸延遲的有效路徑條數(shù)有所下降。從整體上來看，雖然2011年有效路徑數(shù)目有所下降，但瓶頸延遲的有效路徑數(shù)目整體上呈現(xiàn)出增加的趨勢，即瓶頸延遲有效路徑條數(shù)的演化是逐漸增加的。

2.2 訪問直徑的演化

網(wǎng)絡延遲和訪問直徑之間呈現(xiàn)出弱相關(guān)性，即不能把訪問直徑看成是影響網(wǎng)絡延遲的因素。那么五年的訪問直徑的演化是否能發(fā)現(xiàn)訪問直徑對瓶頸延遲的影響呢？演化情況如圖3所示：

由圖2可知：訪問直徑均值從整體上來看是呈下降趨勢的。從2009到2013年訪問直徑的變化范圍區(qū)間為[15，16.7]，變化范圍不足2跳，說明近些年來，訪問直徑的演化并不大，即在網(wǎng)絡中傳輸?shù)臄?shù)據(jù)包平均都要經(jīng)過15-16跳左右的傳輸才能到達目的地址端。因此可以判定訪問直徑對瓶頸延遲沒有影響。

2.3 瓶頸延遲均值與網(wǎng)絡延遲均值的演化

通過對瓶頸延遲均值與網(wǎng)絡延遲均值的演化分析，觀察在相同的時間內(nèi)，瓶頸延遲與網(wǎng)絡延遲的關(guān)系。如圖3所示。

由圖3可知：五年時間內(nèi)，瓶頸延遲均值和網(wǎng)絡延遲均值都是逐年增加的，且二者間增加趨勢也很相似，說明近些年來隨著信息化的逐漸普及，網(wǎng)絡中的通信量逐漸上升，網(wǎng)絡延遲均值與瓶頸延遲均值都呈現(xiàn)出逐漸增加的趨勢。

3 瓶頸延遲在地理上的演化分析

在討論瓶頸延遲在地理上的演化特征之前，先來分析的近五年來網(wǎng)絡延遲在地理上演化特征，因為瓶頸延遲是網(wǎng)絡延遲的重要組成部分，分析瓶頸延遲的特性離不開網(wǎng)絡延遲做鋪墊。

3.1 網(wǎng)絡延遲在地理上的演化特征演化

從網(wǎng)絡延遲兩端IP地址在地理上的分布演化和網(wǎng)絡延遲兩端實際地理距離L（km）的演化兩方面來討論網(wǎng)絡延遲在地理上的演化特征，首先來討論網(wǎng)絡延遲兩端IP地址在地理上的分布演化，如圖4所示：

如圖4所示：網(wǎng)絡延遲兩端IP地址跨洲分布部分有逐年上升的趨勢；網(wǎng)絡延遲兩端IP地址在同一國家的分布有逐年下降的趨勢。由于CAIDA的探Ark探測方式的轉(zhuǎn)變，由于探對于源探測節(jié)點amw中的目的IP地址列表中的目的IP地址的選擇更傾向于面向跨越大洲間的探測，這種在地理上的探測行為特征的演化也越來越適合更進一步地對網(wǎng)絡各行為特征量進行分析。

接下來從網(wǎng)絡延遲兩端IP地址相距實際地理距離L（km）的角度討論其在近五年內(nèi)的演化情況，如圖5所示：

從圖5可以得出：[2500，6200]km范圍的曲線較平穩(wěn)，說明網(wǎng)絡延遲兩端IP節(jié)點間的實際地理距離分布在這一范圍內(nèi)的路徑極少，幾乎沒有目的IP地址落在該區(qū)域內(nèi)，主要是因為距離源監(jiān)測節(jié)點[2500，6200]km處的范圍大部分為海洋所覆蓋；同一地理距離上，網(wǎng)絡延遲兩端地理距離的累積分布有逐年下降的趨勢，說明隨著時間的增加，網(wǎng)絡延遲分布在距源監(jiān)測節(jié)點近距離范圍內(nèi)的目的IP在逐年下降；在同一累積分布上，網(wǎng)絡延遲兩端地理距離有逐年上升的趨勢。由此可以得出，網(wǎng)絡延遲兩端IP地址的實際地理距離，在遠距離區(qū)域內(nèi)的分布演化是在逐年上升的，即有越來越多的目的IP地址與源IP地址是跨洲分布的。

3.2 瓶頸延遲在地理上的演化特征

近五年來瓶頸延遲在地理分布上的演化特征如圖6所示。

如圖6中所示，與圖4相比可知，瓶頸延遲在地理上的分布增加在同一地點的分布，即瓶頸延遲兩端的IP地址的實際地理距離為0；瓶頸延遲跨洲分布沒有表現(xiàn)出太強的有規(guī)律性的演化特征，即瓶頸延遲兩端IP地址的跨洲分布部分的演化沒有太多規(guī)律；瓶頸延遲兩端IP地址在同一地點的分布占瓶頸延遲路徑比例達到一半以上或接近一半，說明瓶頸延遲絕大部分發(fā)生在一個國家的內(nèi)部，尤其以同一地點居多。

接下來從瓶頸延遲兩端IP地址相距實際地理距離L（km）的角度討論其在近五年內(nèi)的演化情況，如圖7所示：

從圖7中可以看到：2009-2013年五條曲線中都至少有超過50%的路徑中其瓶頸延遲兩端IP地址實際地理距離相距為0，即瓶頸延遲在地理分布上的主要組成部分為同一地點的分布；隨著距離的增大，五條曲線并沒有顯示出很明顯的演化規(guī)律。

4 結(jié)束語

通過對近五年來瓶頸延遲的基本特征量的演化分析，發(fā)現(xiàn)瓶頸延遲與網(wǎng)絡延遲均值呈現(xiàn)逐年增加的趨勢，瓶頸延遲均值在網(wǎng)絡延遲均值中所占比例達到50%以上，且瓶頸延遲在路徑中出現(xiàn)的相對位置越來越接近于網(wǎng)絡中的中間部位；瓶頸延遲更傾向于出現(xiàn)在一個國家之內(nèi)，尤其以同一地點的分布居多。瓶頸延遲是影響網(wǎng)絡延遲的一個重要因素，且隨著互聯(lián)網(wǎng)的發(fā)展，瓶頸延遲的演化分布正逐漸趨于平穩(wěn)。

參考文獻：

[1]Adrian E.Coronado Mondragon，Etienne S.Coronado Mondragon，Christian E.Coronado Mondragon.Estimating the performance of intelligent transport systems wireless services for multimodal logistics applications[J].Expert Systems with Applications，2012：3939-3949.

[2]夏彪.端到端網(wǎng)絡瓶頸測量研究[D].武漢科技大學，2009.

[3]Abdelkefi A，Jiang Y.A Structural Analysis of Network Delay[A].Communication Networks and Services Research Conference （CNSR），2011 Ninth Annual. IEEE[C]，2011：41-48.

[4]Ge X，Wang H.Community overlays upon real-world complex networks[J].The European Physical Journal B，2012（01）：1-10.

[5]Zhang G，Quoitin B，Zhou S.Phase changes in the evolution of the IPv4 and IPv6 AS-Level Internet topologies[J].Computer Communications，2011（05）：649-657.

[6]趙海，姚冬，張昕.基于AS級Internet拓撲生長模型的設計與實現(xiàn)[J].東北大學學報（自然科學版），2009（05）：640-643.

[7]Palla G，Barabási A L，Vicsek T.Quantifying social group evolution[J].Nature，2007（7136）：664-667.

[8]Fay D，Haddadi H，Thomason A.Weighted spectral distribution for internet topology analysis：theory and applications[J].Networking，IEEE/ACM Transactions on，2010（01）：164-176.

[9]Albert R，Barabá A L.Statistical mechanics of complex networks [J].Reviews of Modern Physics，2002（01）：47?97.

[10]李超，趙海，張昕.Internet中支配延遲的特征行為研究[J].電子學報，2008（06）：1063-1067.

作者簡介：馮穎（1970-），女，遼寧盤錦人，遼寧林業(yè)職業(yè)技術(shù)學院教授，在讀博士；趙海（1959-），男，遼寧沈陽人，教授。

作者單位：東北大學 信息科學與工程學院，沈陽 110819