互聯(lián)網(wǎng)宏觀拓?fù)浣Y(jié)構(gòu)瓶頸延遲特征的演化分析

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

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

中圖分類號：TP393

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

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

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

1 基本定義

定義1.1路徑（Path）：一個數(shù)據(jù)包在從探測源節(jié)點SRC到達(dá)目的節(jié)點DST的過程中，中間分別經(jīng)過節(jié)點R1，R2，…，Rn-1，令R=（SRC，R1，R2，…，Rn-1，DST），則稱R為從源節(jié)點到目的節(jié)點間的一個路徑，對應(yīng)的n被稱為訪問直徑（Traveling Diameter）。若沿途所有節(jié)點對ICMP探測數(shù)據(jù)包都響應(yīng)并返回相應(yīng)的信息到源節(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)絡(luò)延遲（Network Delay）[9-10]：指從監(jiān)測源節(jié)點發(fā)送一個探測數(shù)據(jù)包到目的節(jié)點，如果數(shù)據(jù)包在傳輸?shù)倪^程中完整地到達(dá)目的節(jié)點，則把數(shù)據(jù)包從監(jiān)測節(jié)點到目的節(jié)點所消耗的時間稱為一個有效的網(wǎng)絡(luò)延遲。

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

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

2 瓶頸延遲特征量的演化

2.1 有效路徑的演化

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

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

2.2 訪問直徑的演化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xià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)絡(luò)瓶頸測量研究[D].武漢科技大學(xué)，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拓?fù)渖L模型的設(shè)計與實現(xiàn)[J].東北大學(xué)學(xué)報（自然科學(xué)版），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].電子學(xué)報，2008（06）：1063-1067.

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

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