早在ARPANET年代就出現(xiàn)了對網(wǎng)絡(luò)延時(shí)的系統(tǒng)測量,并用于考察延時(shí)在一天內(nèi)的不同時(shí)刻,或者一周內(nèi)的不同日期之間的變化情況【Queueing Systems. Volume 2: Computer Applications, Wiley-Interscience, New York 1976】.此后,Mills【Internet delay experiments. RFC-889】為改進(jìn)TCP的重傳機(jī)制,研究了數(shù)據(jù)包的往返延時(shí)與數(shù)據(jù)包的長度的關(guān)系.
上世紀(jì)90年代初,有學(xué)者開始把互聯(lián)網(wǎng)的端到端延時(shí)與丟包率等特性一起進(jìn)行研究,但與近年來滿足新興的強(qiáng)交互性應(yīng)用需求的目的不同,這些研究通常把端到端延時(shí)的劇烈變化作為證實(shí)互聯(lián)網(wǎng)動態(tài)特性的根據(jù),或者與數(shù)據(jù)包丟失等現(xiàn)象一起作為間接反映網(wǎng)絡(luò)墉塞的啟發(fā)式信息.盡管如此,早期研究中觀測到的現(xiàn)象卻客觀地反映了互聯(lián)網(wǎng)端到端延時(shí)的本質(zhì)特點(diǎn).【On the Dynamics and Significance of Low Frequency Components of Internet Load, Technical Report CIS-92-83, University of Pennysylvania, Philadelphia, PA, December 1992】使用每間隔1分鐘發(fā)送一組ICMP ECHO數(shù)據(jù)包的方法探測延時(shí),每組10個(gè)數(shù)據(jù)包,相鄰數(shù)據(jù)包的發(fā)送間隔為1秒鐘,對每個(gè)數(shù)據(jù)包計(jì)算延時(shí)后按組平均.本文使用的數(shù)據(jù)的采集方法除相鄰兩組的發(fā)送間隔為15分鐘外與該文基本相同.作者通過統(tǒng)計(jì)一對主機(jī)間不同時(shí)刻的延時(shí)均值的概率密度發(fā)現(xiàn),每對主機(jī)間的延時(shí)分布都能很好地用帶有一個(gè)常數(shù)偏移量的Gamma分布描述,參數(shù)的取值取決于具體的主機(jī)和時(shí)段.而且該文還指出丟包率以及需要重排序的數(shù)據(jù)包數(shù)量都與延時(shí)的各種統(tǒng)計(jì)特征正相關(guān).【Experimental Assessment of End-to-End Behavior on Internet】持續(xù)地每39.06毫秒發(fā)送一個(gè)基于UDP的小數(shù)據(jù)包探測分別部署在UMD,Stanford和MIT的3臺主機(jī)間的延時(shí).盡管使用了更小的探測間隔,但一對節(jié)點(diǎn)節(jié)點(diǎn)間的延時(shí)未表現(xiàn)出任何規(guī)則性的變化規(guī)律,按作者的結(jié)論"RTT會在短期內(nèi)會發(fā)生實(shí)質(zhì)性的變化".Bolot在【Characterizing End-to-End Packet Delay and Loss in the Internet】一文中對之前關(guān)于端到端延時(shí)的研究做了充分總結(jié).該文探討了使用時(shí)間序列模型研究延時(shí)的可行性,并使用簡單的有限長度的先入先出緩沖區(qū)模型解釋了端到端延時(shí)表現(xiàn)出的部分現(xiàn)象和特點(diǎn).
【Analysis of End-to-End Delay Measurements in Internet】開始強(qiáng)調(diào)端到端延時(shí)對新興互聯(lián)網(wǎng)業(yè)務(wù)的意義,并把延時(shí)作為一個(gè)獨(dú)立的研究問題.與其它研究中測量延時(shí)的方法不同,作者使用了100字節(jié)的IP數(shù)據(jù)包探測單向端到端延時(shí).該文根據(jù)造成延時(shí)的原因把端到端延時(shí)分為處理延時(shí),傳輸延時(shí),傳播延時(shí)和排隊(duì)延時(shí)四部分,然后又從測量的角度把延時(shí)分為隨機(jī)的和確定的兩部分.作者把一段時(shí)間內(nèi)延時(shí)的概率分布情況分為四大類,除少數(shù)延時(shí)的概率密度函數(shù)曲線出現(xiàn)多峰等現(xiàn)象外,約84%的表現(xiàn)出類似于Gamma分布的重尾特征.,作者測量了無負(fù)載情況下確定部分的延時(shí),并估計(jì)了每臺路由器造成的平均延時(shí).
數(shù)據(jù)集
狹義的端到端延時(shí)是指數(shù)據(jù)包從源節(jié)點(diǎn)開始發(fā)送到它被目標(biāo)節(jié)點(diǎn)成功接收的單向的延時(shí),但因?yàn)闇y量單向延時(shí)需要源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間進(jìn)行時(shí)間同步等協(xié)作,復(fù)雜性較高,所以在實(shí)際應(yīng)用中,衡量端到端延時(shí)最常用的指標(biāo)是數(shù)據(jù)包在兩端主機(jī)間的往返延時(shí),即RTT.本文中端到端延時(shí)的含義屬于往返延時(shí),更確切地說是指基于PING的方式計(jì)算的RTT;我們此后默認(rèn)RTT與端到端延時(shí)的含義相同.
相比網(wǎng)絡(luò)流量和路由信息的數(shù)據(jù)都能夠用被動方式采集,端到端延時(shí)一般需要采用主動探測的方式,這不可避免地將為互聯(lián)網(wǎng)造成額外負(fù)載,影響互聯(lián)網(wǎng)的正常業(yè)務(wù)運(yùn)行.有時(shí)候甚至?xí)鼓承┳灾斡虻墓芾韱T或入侵檢測系統(tǒng)誤以為受到了非法攻擊. PAPP項(xiàng)目提供的端到端延時(shí)數(shù)據(jù)幫助解決了這個(gè)問題.本節(jié)將首先介紹PlanetLab網(wǎng)絡(luò)平臺和PAPP項(xiàng)目的基本情況,解釋RTT數(shù)據(jù)采集的具體方法;然后,說明數(shù)據(jù)的正確性檢驗(yàn);最后,討論本文抽象和使用數(shù)據(jù)的方法及其對研究結(jié)果的影響.
PAPP項(xiàng)目
PlanetLab是一個(gè)用于部署,評估和實(shí)驗(yàn)全球規(guī)模的網(wǎng)絡(luò)服務(wù)的分布式平臺,由一個(gè)研究團(tuán)體負(fù)責(zé)管理和維護(hù).截至到2005年11月,PlanetLab已經(jīng)包含分布在世界各地的600多臺主機(jī),覆蓋近300個(gè)域.運(yùn)行PlanetLab相關(guān)服務(wù)的主機(jī)一般被稱作節(jié)點(diǎn),我們將在下文中沿用這一名稱.
All Pairs Pings起始于2003年2月,是到目前為止PlanetLab平臺上歷時(shí)最久的項(xiàng)目之一.它使用被廣泛用于檢測網(wǎng)絡(luò)可用性的網(wǎng)絡(luò)探測工具PING來測量一對節(jié)點(diǎn)間的RTT.PING的工作原理基于RFC-792中定義的ICMP反射功能.測量一對節(jié)點(diǎn)間的RTT時(shí),發(fā)起探測的節(jié)點(diǎn)(源節(jié)點(diǎn))首先向目標(biāo)節(jié)點(diǎn)的IP地址發(fā)送一個(gè)缺省為64字節(jié)(8字節(jié)ICMP包頭和56字節(jié)數(shù)據(jù))長的ECHO_REQUEST請求數(shù)據(jù)包,其中包含一個(gè)時(shí)間戳記錄發(fā)送時(shí)間.如果兩個(gè)節(jié)點(diǎn)間的網(wǎng)絡(luò)連接及目標(biāo)節(jié)點(diǎn)都工作正常,目標(biāo)節(jié)點(diǎn)在接收到該請求數(shù)據(jù)包后立即回送一個(gè)ECHO_RESPONSE的應(yīng)答數(shù)據(jù)包.源節(jié)點(diǎn)在接到應(yīng)答數(shù)據(jù)包后就能夠計(jì)算出一個(gè)數(shù)據(jù)包在其自身與目標(biāo)節(jié)點(diǎn)之間往返需要的時(shí)間,即RTT.All Pairs Pings在每個(gè)連續(xù)運(yùn)行的PlanetLab節(jié)點(diǎn)(Production Node)上部署一組Perl腳本,用于控制該節(jié)點(diǎn)周期性探測所有其它節(jié)點(diǎn).每間隔15分鐘(一個(gè)時(shí)段),每個(gè)節(jié)點(diǎn)就會使用PING向所有其它節(jié)點(diǎn)陸續(xù)發(fā)起一輪不間斷的探測,直到源節(jié)點(diǎn)得到10次有效的RTT或者在120秒后因超時(shí)導(dǎo)致該次探測結(jié)束.源節(jié)點(diǎn)如果在超時(shí)前采集到一組到達(dá)目標(biāo)節(jié)點(diǎn)的有效的RTT,那么就會統(tǒng)計(jì)并記錄下這組RTT的最小值,均值和最大值(我們稱這樣一組RTT的最小值,均值和最大值為一個(gè)RTT元組);否則就認(rèn)為目標(biāo)節(jié)點(diǎn)在該輪探測中不可達(dá).All Pairs Pings使用一臺特定的服務(wù)器每隔1小時(shí)左右收集一次所有節(jié)點(diǎn)記錄的它自身與其它節(jié)點(diǎn)間的RTT元組數(shù)據(jù),并把屬于同一輪探測的RTT元組整理成一個(gè)RTT元組矩陣,與該輪探測中在線節(jié)點(diǎn)的IP地址列表一起存儲在一個(gè)文件里.
PAPP數(shù)據(jù)的選擇和檢驗(yàn)
經(jīng)過比較和調(diào)研,我們選用了PAPP項(xiàng)目從2005年6月1日到2005年8月31日(在這段時(shí)期內(nèi)PAPP數(shù)據(jù)的各時(shí)段的節(jié)點(diǎn)數(shù)量相對穩(wěn)定)的數(shù)據(jù)進(jìn)行研究.這些數(shù)據(jù)共包括8813個(gè)文件,對應(yīng)于8813輪探測結(jié)果,平均每輪探測又包含大約478個(gè)節(jié)點(diǎn)的IP地址列表以及這些節(jié)點(diǎn)的RTT元組矩陣.如果按照All Pairs Pings相鄰兩輪探測的時(shí)間間隔為15分鐘計(jì)算,這段時(shí)間內(nèi)應(yīng)該進(jìn)行了8832輪探測,這說明All Pairs Pings在長時(shí)間采集大量數(shù)據(jù)時(shí)可能出現(xiàn)意外或錯(cuò)誤.因此,為保證研究結(jié)果的可靠性,我們檢查了本文使用的所有數(shù)據(jù),并將數(shù)據(jù)中出現(xiàn)的錯(cuò)誤和沖突分為以下3種情況:
不可修正錯(cuò)誤:延時(shí)元組殘缺不全或者混入了難以正確分離的字符,例如".945/156.088/",稱為元組錯(cuò)誤;或者,延時(shí)元組矩陣中某一行的延時(shí)元組數(shù)量與該時(shí)段的節(jié)點(diǎn)數(shù)量不等,稱為行錯(cuò)誤;
可修正錯(cuò)誤:某些非法字符串混入延時(shí)元組中,但可人為實(shí)現(xiàn)無歧義地修復(fù),例如 "199.77.128.193148.945/149.088/149.281",而"199.77.128.193"為該時(shí)段內(nèi)某個(gè)節(jié)點(diǎn)的IP地址;
矛盾數(shù)據(jù):延時(shí)元組的最小值,均值和最大值之間相互矛盾,例如"171.196/2114.788/21546.315"中均值小于最大值的1/10,根據(jù)All Pairs Pings的原理這種元組是不可能出現(xiàn)的.
實(shí)際上,出現(xiàn)錯(cuò)誤的延時(shí)元組的比例非常小:8813個(gè)延時(shí)元組矩陣中僅有唯一1個(gè)矩陣出現(xiàn)了1個(gè)行錯(cuò)誤,我們將該行的全部延時(shí)元組作缺失數(shù)據(jù)處理;約1,400,000,000個(gè)延時(shí)元組中僅出現(xiàn)了130個(gè)可修正錯(cuò)誤,分布在128個(gè)延時(shí)元組矩陣中,我們一一進(jìn)行了手工修正;還有197個(gè)矛盾數(shù)據(jù)分布在179個(gè)延時(shí)元組矩陣中,因大部分矛盾數(shù)據(jù)實(shí)際上由舍入誤差造成,我們未做任何改動.
除排除數(shù)據(jù)錯(cuò)誤外,因?yàn)锳ll Pairs Pings在各文件中使用IP地址標(biāo)識節(jié)點(diǎn),所以我們必須考慮是否存在同一個(gè)IP地址先后被多個(gè)不同節(jié)點(diǎn)使用的問題.PlanetLab的另一個(gè)項(xiàng)目CoMon提供了每5分鐘更新一次的PlanetLab的節(jié)點(diǎn)列表.通過分析該項(xiàng)目的歷史數(shù)據(jù),我們發(fā)現(xiàn)所有的IP地址在與本文研究有關(guān)的一段時(shí)期內(nèi)都僅對應(yīng)過一個(gè)域名,所以有理由相信在這段時(shí)間內(nèi)每個(gè)IP都對應(yīng)唯一的節(jié)點(diǎn).
PAPP數(shù)據(jù)的使用方法
如果一對節(jié)點(diǎn)在時(shí)段的RTT元組數(shù)據(jù)有效,我們就用其中的均值作為這對節(jié)點(diǎn)的RTT在時(shí)段的采樣值,記為.在此,需要考察這樣一個(gè)問題:均值能否表征這個(gè)時(shí)段的RTT;換句話說,如果一個(gè)時(shí)段內(nèi)連續(xù)探測得到的一組RTT過于分散,那么它們的均值并不適合作為RTT在該時(shí)段的采樣值.假設(shè)一組RTT為,均值為,則它們的無偏標(biāo)準(zhǔn)差與均值的比值是衡量這組RTT分散程度的常用指標(biāo),我們稱為這組RTT生成的RTT元組的分散系數(shù).但是,由于PAPP的RTT元組僅記錄了的最小值,均值和最大值,我們無法直接求取這組RTT的標(biāo)準(zhǔn)差和分散系數(shù),我們借助以下定理1解決這個(gè)問題.
定理1 對任意個(gè)非負(fù)實(shí)數(shù),已知其最小值,均值,最大值分別為,且定義函數(shù)和如下
其中,則這個(gè)數(shù)的標(biāo)準(zhǔn)差使不等式 成立.
依據(jù)定理1,由于是的單調(diào)遞減函數(shù),故僅需計(jì)算便可求得分散系數(shù)的下限;要計(jì)算 的上限,需要先求出的最大值,我們使用了將從2到10(由于無偏標(biāo)準(zhǔn)差的定義在時(shí)無意義,所以如果一個(gè)延時(shí)元組的最小值,均值和最大值都相等,我們假設(shè)該元組至少由兩個(gè)或兩個(gè)以上的測量值計(jì)算所得)窮舉的方法.
圖 1 全部RTT元組分散系數(shù)的上限和下限的累積概率分布函數(shù);
的累積概率分布函數(shù)曲線應(yīng)介于圖中的兩條曲線之間
從圖 1可以看到80%以上的RTT元組的分散系數(shù)小于0.1,90%以上小于0.25,這說明每個(gè)時(shí)段內(nèi)的連續(xù)探測得到的一組RTT相當(dāng)集中地分布在均值附近,因此均值有很好的表征作用,我們用均值作為RTT在一個(gè)時(shí)段的采樣值是合理的.
按照上述方法,PAPP的數(shù)據(jù)可以看作每對節(jié)點(diǎn)的RTT間隔為15分鐘的采樣間序列.根據(jù)采樣定理,只有當(dāng)采樣頻率不低于RTT本身變化的最高頻率分量的兩倍時(shí),才可能完全恢復(fù)RTT在一段時(shí)間內(nèi)的變化過程.然而,這在現(xiàn)實(shí)中是無法實(shí)現(xiàn)的:首先,我們無法知道RTT本身變化的最高頻率分量;其次,測量RTT的探測方法本身也受到設(shè)備收發(fā)數(shù)據(jù)包能力的限制而具有頻率上限.圖 2為2005年12月23日連續(xù)30分鐘內(nèi)分別使用200毫秒,1秒和5秒的間隔探測一對節(jié)點(diǎn)(源節(jié)點(diǎn)為pli2-pa-1.hpl.hp.com,目標(biāo)節(jié)點(diǎn)為thu1.6planetlab.edu.cn)的RTT得到的時(shí)間序列圖像,可以看出RTT在不同采樣間隔下的時(shí)間序列圖像之間并無實(shí)質(zhì)差別,互聯(lián)網(wǎng)上的端到端延時(shí)與網(wǎng)絡(luò)流量類似,也表現(xiàn)出自相似性的特點(diǎn).這說明采樣間隔并不會影響本文研究結(jié)果的一般性.
圖 2 不同采樣間隔下的RTT時(shí)間序列圖像
端到端延時(shí)的隨機(jī)過程模型
圖 3是一對節(jié)點(diǎn)間的RTT在有限時(shí)間內(nèi)的不同時(shí)刻的采樣值,通常被稱為RTT的時(shí)間序列圖像,它直觀地說明了眾多現(xiàn)有研究都已指出的互聯(lián)網(wǎng)的端到端延時(shí)會在短期內(nèi)發(fā)生劇烈變化的特點(diǎn).從圖中可以直觀地發(fā)現(xiàn)RTT隨時(shí)間變化的情況大致分為兩類:一類是持續(xù)不斷的無規(guī)則變化,我們稱之為"攝動";另一類則使RTT的本質(zhì)特征都發(fā)生了變化,我們稱之為"躍變".我們將基于本節(jié)稍后給出的RTT的隨機(jī)過程模型更嚴(yán)謹(jǐn)?shù)亟忉?quot;攝動"和"躍變"的含義.
圖 3 一對節(jié)點(diǎn)間RTT的時(shí)間序列圖像
隨機(jī)過程模型
根據(jù)對圖 3和其它近百對節(jié)點(diǎn)的RTT的時(shí)間序列圖像的觀察,我們提出一對節(jié)點(diǎn)的RTT可以抽象為隨機(jī)過程模型:假設(shè)為一對節(jié)點(diǎn)間RTT的樣本空間,隨機(jī)變量表示它們的RTT在時(shí)刻的取值,那么可以用一族依賴于的隨機(jī)變量來描述這對節(jié)點(diǎn)間的RTT,簡記為隨機(jī)過程.
在這個(gè)模型的基礎(chǔ)上,一對節(jié)點(diǎn)的RTT在這段時(shí)間內(nèi)發(fā)生了"躍變"的含義是這對節(jié)點(diǎn)的RTT分別在時(shí)刻和對應(yīng)隨機(jī)變量和具有不同的統(tǒng)計(jì)特征(數(shù)學(xué)期望和方差).如果一對節(jié)點(diǎn)的RTT在一段時(shí)間內(nèi)僅發(fā)生"攝動"變化,我們就假設(shè)這對節(jié)點(diǎn)的RTT在內(nèi)的隨機(jī)過程為均值遍歷的(寬)平穩(wěn)過程;在后文中,我們稱這種過程為RTT的攝動過程.
理論上,數(shù)學(xué)期望是在最小二乘意義下對一個(gè)平穩(wěn)過程的最佳常值估計(jì);而均值遍歷性則保證一個(gè)平穩(wěn)過程的時(shí)間均值與統(tǒng)計(jì)均值即數(shù)學(xué)期望相等.依據(jù)這兩個(gè)性質(zhì),我們能夠用一對節(jié)點(diǎn)的RTT在當(dāng)前或過去一段時(shí)間內(nèi)的測量值去估計(jì)這對節(jié)點(diǎn)的RTT的數(shù)學(xué)期望,并用它預(yù)測這對節(jié)點(diǎn)間未來一段時(shí)間的RTT;而且,直到這對節(jié)點(diǎn)的RTT發(fā)生下一次躍變之前,數(shù)學(xué)期望能夠在所有常值估計(jì)中使均方誤差最小.
躍變和攝動的主要原因
為分析造成RTT發(fā)生躍變和攝動的主要原因,更深入地理解互聯(lián)網(wǎng)端到端延時(shí)特性,我們首先把端到端延時(shí)分為幾部分,然后逐一分析影響各部分的主要因素.
根據(jù)數(shù)據(jù)交換網(wǎng)絡(luò)中一個(gè)數(shù)據(jù)包在端到端通信中經(jīng)歷的過程,我們把一對節(jié)點(diǎn)的RTT分為三部分:
終端延時(shí):終端節(jié)點(diǎn)接收,發(fā)送和處理數(shù)據(jù)包的時(shí)間;
交換延時(shí):網(wǎng)絡(luò)中繼設(shè)備接收,發(fā)送和處理數(shù)據(jù)包的時(shí)間;
傳播延時(shí):數(shù)據(jù)包在通信媒介中傳播的時(shí)間.
表 1 影響RTT的主要因素(加*表示該因素與路由有關(guān))
組成
決定性因素
隨機(jī)性因素
終端延時(shí)
終端節(jié)點(diǎn)的處理能力
終端節(jié)點(diǎn)的接入方式
終端節(jié)點(diǎn)的接入帶寬
終端節(jié)點(diǎn)的處理器負(fù)載
終端節(jié)點(diǎn)的網(wǎng)絡(luò)負(fù)載
交換延時(shí)
* 經(jīng)過的網(wǎng)絡(luò)中繼設(shè)備數(shù)量
* 每臺網(wǎng)絡(luò)中繼設(shè)備的處理能力
* 網(wǎng)絡(luò)中繼設(shè)備的負(fù)載
* 網(wǎng)絡(luò)中繼設(shè)備的調(diào)度策略
傳播延時(shí)
* 傳輸媒介
* 傳輸路程
無
表 1為給定一條路由時(shí),影響每部分延時(shí)的決定性因素和隨機(jī)性因素.不難發(fā)現(xiàn),當(dāng)路由不變時(shí),造成RTT變化的因素主要是終端節(jié)點(diǎn)和網(wǎng)絡(luò)中繼設(shè)備的負(fù)載變化,它們的統(tǒng)計(jì)特征基本上不受時(shí)間影響;但當(dāng)路由發(fā)生變化時(shí),不僅會影響某些隨機(jī)性因素,還會同時(shí)改變RTT的很多決定性因素,從而使RTT的根本性質(zhì)也發(fā)生變化.
基于以上分析,我們認(rèn)為一對節(jié)點(diǎn)的RTT發(fā)生躍變主要是這對節(jié)點(diǎn)間的路由變化造成的;而RTT的攝動則主要是終端節(jié)點(diǎn)和網(wǎng)絡(luò)中繼設(shè)備的處理器和網(wǎng)絡(luò)的負(fù)載發(fā)生變化造成的.
模型的驗(yàn)證
為檢驗(yàn)4.1節(jié)提出的隨機(jī)過程模型是否與實(shí)際相符,首先,我們把PAPP數(shù)據(jù)中一對節(jié)點(diǎn)的RTT在各個(gè)時(shí)段內(nèi)的采樣值可以看作是隨機(jī)過程的一個(gè)樣本函數(shù)的采樣序列,稱為這對節(jié)點(diǎn)的RTT序列,用表示;然后,我們設(shè)計(jì)一種判別RTT躍變的方法,將一對節(jié)點(diǎn)的RTT序列劃分為若干個(gè)攝動過程的子序列;最后,我們用這些子序列驗(yàn)證攝動過程的平穩(wěn)性和均值遍歷性.
躍變的判別方法
我們用時(shí)段附近的(為便于計(jì)算,一般選為奇數(shù))個(gè)連續(xù)的RTT采樣值的中位數(shù)來估計(jì)一對節(jié)點(diǎn)的RTT在時(shí)段的數(shù)學(xué)期望.用少量樣本估計(jì)一個(gè)隨機(jī)變量的數(shù)學(xué)期望的常用方法有兩種:一種是使用樣本的平均值;另一種是使用樣本的中位數(shù).根據(jù)現(xiàn)有的研究成果及我們的直觀觀察,一對節(jié)點(diǎn)的RTT可近似為類似與Gamma分布的單向重尾分布.當(dāng)樣本數(shù)量較少時(shí),使用中位數(shù)能夠比平均值更準(zhǔn)確的估計(jì)這種分布的數(shù)學(xué)期望.
圖 4 躍變判別方法示意圖
本文把用于估計(jì)RTT的數(shù)學(xué)期望的個(gè)連續(xù)的RTT采樣值稱為一個(gè)采樣窗.如圖 4所示,我們用采樣窗估計(jì)一對節(jié)點(diǎn)的RTT在當(dāng)前時(shí)段的數(shù)學(xué)期望,用采樣窗估計(jì)一對節(jié)點(diǎn)的RTT在過去某一時(shí)段的數(shù)學(xué)期望,而且使采樣窗與之間存在一定間隔(在圖中用表示).我們假設(shè)當(dāng)和在一對節(jié)點(diǎn)的RTT序列上滑動到達(dá)一次攝動過程的邊緣即將發(fā)生躍變時(shí)的時(shí)刻為,躍變前和躍變后的攝動過程的數(shù)學(xué)期望分別為和,方差分別為和,躍變后的攝動過程持續(xù)的時(shí)間為(假設(shè)).我們分別用和表示采樣窗和的中位數(shù),分別用和表示二者的方差.在隨后一段時(shí)間內(nèi),,和,的取值大致分別如圖 5 (a),(b),(c),(d)所示.下面,我們以求取在時(shí)刻的取值為例說明近似計(jì)算和隨時(shí)間變化情況的方法:首先求采樣窗在時(shí)刻的均值;然后由求得采樣窗在時(shí)刻的方差為可見是的二次函數(shù),而且可近似為為軸的開口向下的拋物線.
圖 5 采樣窗的數(shù)學(xué)期望和方差隨時(shí)間的變化
如果采樣窗和估計(jì)的RTT的數(shù)學(xué)期望的變化量在某個(gè)時(shí)刻超過某一閾值,我們就認(rèn)為RTT在對應(yīng)的時(shí)段內(nèi)發(fā)生了一次跳躍:若,就稱RTT發(fā)生了一次上跳;否則,若,就稱RTT發(fā)生了一次下跳.我們將所有RTT在其中發(fā)生上跳和下跳的時(shí)段按各時(shí)間順序排成一列上跳序列和下跳序列.由于存在著攝動變化的影響,并不是RTT在(或)中的每個(gè)時(shí)段內(nèi)都一定發(fā)生了躍變.為減小攝動的干擾,降低對RTT躍變的誤判率,我們設(shè)計(jì)了以下兩種機(jī)制:
我們把躍變的閾值設(shè)定為(其中為常數(shù));
只有當(dāng)序列(或)中的一個(gè)時(shí)段滿足時(shí),我們才判定在RTT在時(shí)段到時(shí)段之間發(fā)生了一次躍變,然后,我們用迭代公式對(或)處理后再搜索下一次躍變.
第一種機(jī)制的思想是在判定RTT躍變時(shí)參考攝動的程度,如果攝動劇烈那么判定躍變的閾值也應(yīng)該相應(yīng)提高.圖 6解釋了第二種機(jī)制的思想:當(dāng)采樣窗和滑經(jīng)一對節(jié)點(diǎn)的RTT的一次躍變時(shí),一旦采樣窗和估計(jì)的RTT的數(shù)學(xué)期望的變化量在某個(gè)時(shí)刻超過了躍變閾值,那么這種狀態(tài)將至少持續(xù)個(gè)時(shí)段(事實(shí)上,我們放松了約束條件,僅要求在未來個(gè)時(shí)段內(nèi)有個(gè)時(shí)段出現(xiàn)相同方向的RTT跳躍).
盡管上述判別方法降低了將RTT的攝動判定為躍變的錯(cuò)誤率,但它可能會使漏判率增加.因?yàn)楫?dāng)RTT的相鄰兩次躍變相隔的時(shí)間較短時(shí),若兩次相鄰躍變方向相同,一般會漏判第一次躍變;若方向相反,則一般會同時(shí)漏判這兩次躍變.因此,在確定參數(shù),和的取值時(shí)需要兼顧躍變的誤判率和漏判率.
圖 6 采樣窗數(shù)學(xué)期望的變化量與躍變閾值的關(guān)系
RTT的躍變頻率和躍變間隔
使用上述判別RTT躍變的方法,我們考察了【附錄1】中590對節(jié)點(diǎn)(要求源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)不同)的RTT序列.我們選擇的參數(shù)的取值如表 2所示,這樣賦值會對相隔小于6個(gè)時(shí)段(1.5個(gè)小時(shí))的RTT躍變發(fā)生漏判;不過,根據(jù)文獻(xiàn)【End-to-End Routing Behavior in the Internet,Dynamics of Internet Routing Information】的研究成果――互聯(lián)網(wǎng)上的端到端路徑主要由一條占絕對優(yōu)勢的路由控制,而且90%以上的路由會持續(xù)幾個(gè)小時(shí)以上,又考慮到路由變化是造成RTT躍變的主要原因(本文4.2節(jié)),所以因此被漏判的RTT躍變應(yīng)該不超過10%.
表 2 RTT躍變判定方法的參數(shù)取值
參數(shù)名稱
參數(shù)值
5
3
5
對于一對節(jié)點(diǎn)的RTT序列,我們定義它們的RTT的躍變頻率為.圖 7說明80%以上的節(jié)點(diǎn)對的RTT序列的躍變頻率小于0.01;所有節(jié)點(diǎn)對的RTT序列的躍變頻率都小于0.03,也就是說所有節(jié)點(diǎn)對的RTT都平均每隔30個(gè)時(shí)段(大約7.5個(gè)小時(shí))以上的時(shí)間才發(fā)生一次RTT躍變.
圖 7 躍變頻率的累積概率密度函數(shù)曲線
躍變頻率無法精確地反映RTT的躍變間隔,因?yàn)橐粚?jié)點(diǎn)的RTT可能集中在某段較短時(shí)間內(nèi)頻繁發(fā)生躍變,此時(shí)即使RTT的躍變頻率很低,這對節(jié)點(diǎn)的RTT發(fā)生相鄰兩次躍變的實(shí)際間隔仍可能遠(yuǎn)遠(yuǎn)低于平均間隔.圖 8給出了躍變間隔的統(tǒng)計(jì)狀況,可以看出大約40%以上的躍變間隔大于50個(gè)時(shí)段(12個(gè)小時(shí)左右).我們對躍變間隔的估計(jì)是保守的,因?yàn)樵诒?2中設(shè)定的參數(shù)值偏向于保證較低的漏判率,所以,當(dāng)RTT在某段時(shí)間內(nèi)的攝動劇烈時(shí)很可能被誤判為躍變.
圖 8 躍變間隔的累積概率密度函數(shù)曲線
攝動過程的平穩(wěn)性
攝動過程的平穩(wěn)性是RTT隨機(jī)過程模型的重要假設(shè),我們通過考察一對節(jié)點(diǎn)的攝動過程的RTT序列是否平穩(wěn)來間接地檢驗(yàn)這一假設(shè)的合理性.觀察時(shí)間序列圖像是檢驗(yàn)序列平穩(wěn)性最簡單的方法,我們提出的模型就源于觀察圖像受到的啟發(fā),但這種方法容易受主觀因素影響,更嚴(yán)格地檢驗(yàn)序列平穩(wěn)性的方法是統(tǒng)計(jì)檢驗(yàn)中普遍采用的"單位根"方法.
我們選用了單位根方法中最常用的ADF檢驗(yàn)【Eviews4 User's Guide】,有關(guān)單位根檢驗(yàn)和ADF檢驗(yàn)的具體原理和過程請參閱相關(guān)資料,我們在此僅不嚴(yán)格地說明這種檢驗(yàn)方法的基本思想.首先,我們建立零假設(shè),假設(shè)待檢驗(yàn)的時(shí)間序列是非平穩(wěn)的(是存在單位根的隨機(jī)游走序列);基于假設(shè)的模型,我們計(jì)算這個(gè)時(shí)間序列的某個(gè)統(tǒng)計(jì)量;然后,對于某個(gè)選定的顯著性水平(通常取1%或5%),我們從ADF臨界值表中查到臨界值;最后,我們把與比較:若,則拒絕假設(shè)(顯著),并認(rèn)為待檢驗(yàn)序列是平穩(wěn)的,而且我們判斷錯(cuò)誤的概率不會超過顯著性水平(一般越小,我們的判斷就越可靠);反之,則認(rèn)為假設(shè)成立(不顯著),待檢驗(yàn)序列的確是不平穩(wěn)的.
下面,我們以源節(jié)點(diǎn)為pli2-pa-1.hpl.hp.com,目標(biāo)節(jié)點(diǎn)為thu1.6planetlab.edu.cn的一對節(jié)點(diǎn)(圖 3)分別在2005年7月26日和2005年8月31日的RTT序列為例,解釋ADF檢驗(yàn)結(jié)果的含義.由于PAPP存在數(shù)據(jù)缺失,為對比公平,我們選擇的兩組時(shí)間序列都包含92個(gè)對應(yīng)時(shí)刻的采樣點(diǎn)(去掉的4個(gè)采樣點(diǎn)對應(yīng)的時(shí)刻分別為2:15,9:45,21:45和22:15).我們使用Eviews軟件對這兩組RTT序列的平穩(wěn)性進(jìn)行ADF檢驗(yàn)的結(jié)果如表 3所示.從表中的結(jié)果可以看出,在顯著性水平為1%的情況下,這對節(jié)點(diǎn)在2005年8月31日的RTT序列的檢驗(yàn)統(tǒng)計(jì)量仍明顯小于ADF檢驗(yàn)的臨界值,因此我們有99%以上的把握判定這組序列是平穩(wěn)的;而即使在顯著性水平為5%的情況下,RTT在7月26日的時(shí)間序列的檢驗(yàn)統(tǒng)計(jì)量仍大于ADF檢驗(yàn)的臨界值,不能否定假設(shè),所以這組序列是不平穩(wěn)的,而造成這種結(jié)果的主要原因是這對節(jié)點(diǎn)的RTT在7月26日上午發(fā)生了一次躍變(圖 3所示).
表 3 RTT序列平穩(wěn)性的ADF檢驗(yàn)結(jié)果
RTT的時(shí)間序列
2005年7月26日
2005年8月31日
檢驗(yàn)統(tǒng)計(jì)量
-2.775
-6.109
檢驗(yàn)統(tǒng)計(jì)量
的臨界值
1%顯著性水平下
-3.503
-3.501
5%顯著性水平下
-2.893
-2.893
使用上述的ADF檢驗(yàn)方法,我們隨機(jī)檢驗(yàn)了50對節(jié)點(diǎn)的RTT的攝動過程序列,發(fā)現(xiàn)它們都能在在顯著性水平1%的情況下否定假設(shè),即表現(xiàn)出平穩(wěn)性.檢驗(yàn)時(shí),我們選用了ADF檢驗(yàn)中僅含有常數(shù)項(xiàng)的回歸方程,并把最大滯后項(xiàng)設(shè)置為3.
攝動過程的均值遍歷性
遍歷性又稱各態(tài)歷經(jīng)性,是平穩(wěn)隨機(jī)過程的最重要的性質(zhì)之一,只有當(dāng)一個(gè)平穩(wěn)過程是各態(tài)歷經(jīng)的,這個(gè)過程的統(tǒng)計(jì)特征才與它的一個(gè)樣本函數(shù)在不同時(shí)刻的采樣值的統(tǒng)計(jì)特征相同.在本文的隨機(jī)過程模型中,攝動過程滿足均值遍歷性是使用一對節(jié)點(diǎn)過去一段時(shí)間內(nèi)的RTT的采樣值估計(jì)這對節(jié)點(diǎn)未來短期內(nèi)的RTT的理論基礎(chǔ).
研究一個(gè)平穩(wěn)隨機(jī)過程的均值遍歷性的常用方法是借助均值各態(tài)歷經(jīng)性定理.均值各態(tài)歷經(jīng)性定理證明平穩(wěn)隨機(jī)過程滿足均值遍歷性,即的充要條件是,其中為的自相關(guān)系數(shù).
下面,我們通過檢驗(yàn)攝動過程的RTT序列是否滿足均值各態(tài)歷經(jīng)性定理的充要條件來間接驗(yàn)證攝動過程具有均值遍歷性的假設(shè).具體講,假設(shè)某對節(jié)點(diǎn)的RTT在某段時(shí)間內(nèi)的攝動過程的RTT序列為,如果(其中),則說明這段攝動過程的RTT序列是均值遍歷的;如果很多不同的節(jié)點(diǎn)對的RTT的各段攝動過程的RTT序列對應(yīng)的都接近于0,那么就證實(shí)了攝動過程的確具有均值遍歷性.
使用本文5.1節(jié)中提出的判別躍變的方法,我們將【附錄1】中源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)不同的590對節(jié)點(diǎn)的RTT序列劃分成若干段攝動過程的子序列.從圖 9可以看出60%以上的攝動過程的RTT序列的值都小于0.02,80%以上的都小于0.5.而且,我們發(fā)現(xiàn)造成某些攝動過程的RTT序列的值大于1(甚至達(dá)到左右)的主要原因是這些RTT序列的除個(gè)別采樣值極大(10000到100000之間)外,其它采樣值基本相等(95%的致信區(qū)間的寬度小于平均值的1%);這些反常的采樣值非?？赡苁且馔庖蛩卦斐傻?總之,上述結(jié)果基本上能夠證實(shí)RTT的攝動過程具有均值遍歷性.
圖 9 的累積概率分布函數(shù)曲線
基于同質(zhì)節(jié)點(diǎn)對的驗(yàn)證方法
在描述這種方法之前,我們先定義以下幾個(gè)概念:
同拓?fù)涔?jié)點(diǎn):由同一組織維護(hù),且具有相同的域名,地理位置及24位以上的IP地址前綴的節(jié)點(diǎn);基本上可判定同拓?fù)涔?jié)點(diǎn)位于同一局域網(wǎng)內(nèi);
同質(zhì)節(jié)點(diǎn):具有相同的硬件配置,接入方式和帶寬的同拓?fù)涔?jié)點(diǎn);
同質(zhì)節(jié)點(diǎn)對:如果若干對節(jié)點(diǎn)的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)都分別是同質(zhì)節(jié)點(diǎn),那么這些節(jié)點(diǎn)對稱為同質(zhì)節(jié)點(diǎn)對.
基于同質(zhì)節(jié)點(diǎn)對的驗(yàn)證方法的基本原理是:如果RTT的攝動過程可近似為均值遍歷的平穩(wěn)過程,那么同質(zhì)節(jié)點(diǎn)對的RTT在長時(shí)間相同時(shí)段內(nèi)采樣的平均值應(yīng)該基本相等.其中要求在相同時(shí)段對同質(zhì)節(jié)點(diǎn)對的RTT采樣是為了消除躍變的干擾,因?yàn)椴煌瑫r(shí)段的RTT采樣可能屬于不同的攝動過程.出于這種考慮,只有當(dāng)一個(gè)時(shí)段內(nèi)每個(gè)同質(zhì)節(jié)點(diǎn)對的RTT的采樣值都在PAPP的數(shù)據(jù)中存在時(shí),我們才把該時(shí)段作為RTT序列的一個(gè)采樣點(diǎn).盡管在同一時(shí)段內(nèi)兩對同質(zhì)節(jié)點(diǎn)對的RTT的采樣也不是完全同步的,仍可能在其間發(fā)生路由變化,但這種可能造成的影響是可忽略的.
圖 10為源節(jié)點(diǎn)為planetlab1.singapore.equinix.planet-lab.org,目標(biāo)節(jié)點(diǎn)分別為Duke大學(xué)的3個(gè)同質(zhì)節(jié)點(diǎn)planetlab1/2/3.cs.duke.edu構(gòu)成的三對同質(zhì)節(jié)點(diǎn)對的RTT的時(shí)間序列圖像.可以看出在同一時(shí)段內(nèi),同質(zhì)節(jié)點(diǎn)對的RTT采樣值之間可能差別很大,而它們的RTT序列的均值卻基本相等,分別為279.93ms,281.71ms和280.64.
圖 10 同質(zhì)節(jié)點(diǎn)對的RTT序列
為確信RTT的隨機(jī)性變化背后的確隱含著基本不變的統(tǒng)計(jì)特征,我們選擇了100個(gè)節(jié)點(diǎn)與Duke大學(xué)的3個(gè)節(jié)點(diǎn)組成100組(每組3對)同質(zhì)節(jié)點(diǎn)對.圖 11分別為這100組同質(zhì)節(jié)點(diǎn)對的RTT采樣序列(每組節(jié)點(diǎn)對的RTT的采樣次數(shù)都大于8000)的均值和方差,可以看出每組同質(zhì)節(jié)點(diǎn)對的統(tǒng)計(jì)特征基本相同.這在一定程度上證實(shí)了RTT的隨機(jī)過程模型及性質(zhì).
圖 11 統(tǒng)計(jì)節(jié)點(diǎn)對具有基本相同的統(tǒng)計(jì)特征
RTT的直接估計(jì)方法
使用大量測量值估計(jì)RTT的數(shù)學(xué)期望是無法在實(shí)際中應(yīng)用的.在短期內(nèi)進(jìn)行頻繁探測會給網(wǎng)絡(luò)和終端系統(tǒng)帶來嚴(yán)重負(fù)載,甚至?xí)蝗肭謾z測系統(tǒng)誤認(rèn)為攻擊;而依靠長時(shí)間的采樣積累則會受RTT躍變影響降低跟蹤能力.目前對RTT的直接估計(jì)一般都使用最簡單的方法,即用RTT的最近一次測量值進(jìn)行預(yù)測.本節(jié)的目的是找到一種能更準(zhǔn)確預(yù)測未來短期內(nèi)的RTT的方法,但仍然僅需要依靠少量的近期RTT采樣值.
評價(jià)指標(biāo)
尋找和評價(jià)一種RTT的直接估計(jì)方法,可以在數(shù)學(xué)上抽象為以下問題:假設(shè)表示一對節(jié)點(diǎn)的RTT序列,現(xiàn)在希望找到一個(gè)映射:,使估計(jì)誤差最小,其中為和之間的某種距離函數(shù).注意,一種RTT的估計(jì)方法除與映射本身有關(guān)外,還與使用的歷史采樣值的個(gè)數(shù)和預(yù)測持續(xù)的時(shí)間有關(guān).對于任意給定的和,最簡單常用的直接估計(jì)方法是,我們將這種方法的估計(jì)誤差稱為標(biāo)準(zhǔn)誤差.
本文選用最常用的平方誤差作為距離函數(shù),即,這樣估計(jì)誤差就變成了最小二乘意義下的均方誤差.由于各種方法的估計(jì)誤差可能差別較大,為便于比較,我們將使用一種方法的估計(jì)誤差與標(biāo)準(zhǔn)誤差的比值作為評價(jià)這種方法估計(jì)效果的指標(biāo),稱為相對估計(jì)誤差.
估計(jì)方法及其比較
對于任意給定的和,以下3種映射都可構(gòu)成3種不同的估計(jì)方法.
均值映射:;
中位數(shù)映射:,其中表示的中位數(shù):假設(shè)已經(jīng)由小到大排列,若為奇數(shù)則它們的中位數(shù)等于處于中間位置的那個(gè)數(shù),若為偶數(shù)則它們的中位數(shù)等于處于中間位置的兩個(gè)數(shù)的均值.
最小值映射:;
隨和分別取不同的值,我們稱使用相同映射的估計(jì)方法為同族的.下面我們將使用【附錄1】中的610對PAPP節(jié)點(diǎn)的RTT序列作為測試集,表 5給出了使用不同的歷史采樣值的個(gè)數(shù)和預(yù)測持續(xù)的時(shí)間時(shí),各族估計(jì)方法的平均相對誤差.
表 4 各族估計(jì)方法的平均相對誤差(//)
.856/.856/.763
.843/.843/.730
.840/.840/.718
.839/.839/.712
.839/.839/.708
.832/.846/.809
.808/.800/.759
.800/.781/.737
.796/.771/.724
.794/.765/.715
.837/.830/.869
.804/.781/.805
.790/.760/.774
.782/.748/.755
.777/.741/.741
.854/.900/.931
.811/.833/.853
.792/.801/.813
.781/.782/.788
.773/.769/.769
從表 5中可以看到,族估計(jì)方法的誤差基本上隨著使用的歷史采樣值個(gè)數(shù)的增加而減小,這是由于RTT的分布為類似Gamma分布的重尾分布,使用樣本的平均值估計(jì)這種分布的數(shù)學(xué)期望時(shí)通常需要較多的樣本才能消除"重尾"效應(yīng);但是當(dāng)大到一定程度后,RTT躍變的影響逐漸顯現(xiàn)出來,使得誤差減小的趨勢明顯變緩甚至出現(xiàn)了反彈.
族估計(jì)方法的誤差隨的變化情況基本與族的方法相同;的估計(jì)效果一般優(yōu)于,這是由于RTT的分布為單邊重尾分布,當(dāng)樣本數(shù)較少時(shí)使用中位數(shù)能夠比平均值更準(zhǔn)確地估計(jì)這種分布的數(shù)學(xué)期望;對比和的情況可以發(fā)現(xiàn),RTT躍變導(dǎo)致誤差反彈的現(xiàn)象在族方法中比族方法中更為明顯,這是因?yàn)楫?dāng)RTT發(fā)生躍變時(shí)族方法的誤差一般會大于族方法.
令人意外的是,在表 5中比較的所有估計(jì)方法中,使用最近兩次()RTT采樣的最小值()來預(yù)測未來的RTT竟然達(dá)到了最好的估計(jì)效果.
也許有人會注意到一個(gè)與直觀感受相悖的現(xiàn)象――表 5給出的結(jié)果中各族估計(jì)方法的相對誤差都隨著的增大而減小,這是否意味著越大即預(yù)測未來的時(shí)間越長估計(jì)的誤差就越小呢 事實(shí)上,根據(jù)相對誤差的定義,它是一種估計(jì)方法的均方誤差與標(biāo)準(zhǔn)誤差的比值,而標(biāo)準(zhǔn)誤差本身就是隨變化的函數(shù),所以,每種方法在不同值下的相對誤差并不具備直接的可比性.
圖 12 三種RTT估計(jì)方法的相對誤差的累積概率密度函數(shù)曲線
圖 12給出了時(shí)映射,和分別對應(yīng)的最佳(平均相對誤差最小)估計(jì)方法對測試集中的610對節(jié)點(diǎn)估計(jì)得到的相對誤差的概率分布情況.可以看到并不存在一種估計(jì)方法對于所有節(jié)點(diǎn)對的RTT的估計(jì)效果都優(yōu)于其它方法,只能在統(tǒng)計(jì)意義上評價(jià)一種估計(jì)方法的優(yōu)劣.一般地,族估計(jì)方法對不同節(jié)點(diǎn)對的RTT序列的估計(jì)效果的差別最大,對某些節(jié)點(diǎn)對的效果優(yōu)于族方法,而對于另外一些節(jié)點(diǎn)對的效果卻可能不如族方法.
相比之下,族的估計(jì)方法則同時(shí)具有其它二者的優(yōu)點(diǎn),既跟族估計(jì)方法一樣具有普適性(對不同節(jié)點(diǎn)對的RTT的估計(jì)效果差別較小),又能達(dá)到與族估計(jì)方法一樣的最好情況(適于估計(jì)某些特定節(jié)點(diǎn)對的RTT).此外,考慮到族的估計(jì)方法在時(shí)達(dá)到最優(yōu),即僅要求使用最近兩次RTT測量值中的較小者預(yù)測未來的RTT,因此,無論從方法復(fù)雜性角度還是測量代價(jià)角度,這種估計(jì)方法都具有顯著優(yōu)勢.
估計(jì)RTT的啟發(fā)信息
某些情況下,需要在沒有通過探測得到RTT的測量值之前對一對節(jié)點(diǎn)間的端到端延時(shí)具有粗略的估計(jì).例如,當(dāng)某個(gè)玩家希望從數(shù)百臺服務(wù)器中選擇延時(shí)最小的玩在線游戲時(shí),如果用直接估計(jì)方法測量玩家中斷到每臺服務(wù)器間的RTT,那么不僅會給網(wǎng)絡(luò)和處理器帶來較重負(fù)載,而且會使用戶等待較長時(shí)間;但是,如果能夠依靠某些容易獲得的啟發(fā)信息預(yù)先對候選的服務(wù)器進(jìn)行選擇或排序,則能夠有效減小測量開銷和等候時(shí)間.為此,我們將在本節(jié)分別研究兩種啟發(fā)信息――地理位置關(guān)系和IP地址的共同前綴的長度,與RTT的平均值的聯(lián)系.在此之前,我們先考察終端節(jié)點(diǎn)的異質(zhì)性對RTT平均值的影響程度.
終端節(jié)點(diǎn)的異質(zhì)性對RTT均值的影響
PlanetLab節(jié)點(diǎn)的異質(zhì)性主要體現(xiàn)在硬件配置以及接入的方式和帶寬上.在使用PING探測RTT的應(yīng)用背景下,終端節(jié)點(diǎn)處理數(shù)據(jù)包的計(jì)算量很小,PlanetLab上一般配置的節(jié)點(diǎn)(如Dell Precision 420)處理數(shù)據(jù)包花費(fèi)的平均時(shí)間應(yīng)該不超過幾十納秒,這相對于互聯(lián)網(wǎng)上幾十到幾百毫秒的RTT是完全可以忽略的.為了驗(yàn)證上面的想法,我們選擇了分別由美國的MIT,UCB和意大利Hebrew大學(xué)維護(hù)的3組僅硬件配置不同的同質(zhì)節(jié)點(diǎn),它們的數(shù)量及硬件配置情況如表 5所示.
表 5 三組僅硬件配置不同的同質(zhì)節(jié)點(diǎn)
MIT
Berkeley
Hebrew
配置I
Dell Poweredge 1650
HP DL320 G2
IBM ThinkCenter (P4 2.4GHz)
數(shù)量I
2
1
1
配置II
Dell 650
Dell 650
Dell Precision 420
數(shù)量II
3
9
2
圖 13為MIT的一組節(jié)點(diǎn)分別作為源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)時(shí),與其它200個(gè)節(jié)點(diǎn)的RTT的平均值情況,可以看出兩種不同硬件配置并未導(dǎo)致MIT的這組節(jié)點(diǎn)與其它節(jié)點(diǎn)的RTT的平均值出現(xiàn)顯著差別.從Berkeley和Hebrew的兩組節(jié)點(diǎn)得到的結(jié)果與MIT的在實(shí)質(zhì)上幾乎完全相同,因篇幅問題,我們不再贅述.
圖 13 200個(gè)節(jié)點(diǎn)與MIT的一組節(jié)點(diǎn)間的RTT均值
接入帶寬對端到端延時(shí)的影響與使用的探測數(shù)據(jù)包的大小有關(guān),而數(shù)據(jù)包的大小除應(yīng)用層數(shù)據(jù),ICMP包頭和IP包頭外,根據(jù)不同的接入方式,還可能需要添加不同長度的鏈路層包頭.盡管如此,我們可以先粗略估算一下接入方式和帶寬對延時(shí)可能造成的影響的程度.假設(shè)PAPP使用的詢問和應(yīng)答的探測數(shù)據(jù)包大小都為100字節(jié),每次探測兩端節(jié)點(diǎn)都需要各自發(fā)送和接收1個(gè)數(shù)據(jù)包,相當(dāng)于各傳送200字節(jié)數(shù)據(jù);若探測節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的接入帶寬都為100Kbps,則傳輸數(shù)據(jù)所用的總時(shí)間為200 * 8 / (100 * 1000)) = 0.0016 s = 1.6 ms,即使兩端節(jié)點(diǎn)的接入帶寬都增大1000倍變?yōu)?00Mbps,也僅能將端到端延時(shí)減小1.5ms左右.使用類似的方法,我們也研究了若干組僅接入帶寬不同的同質(zhì)節(jié)點(diǎn)的RTT均值,結(jié)果證明終端節(jié)點(diǎn)的接入方式和帶寬對平均RTT的影響也是可以忽略的.
對比圖 13中兩圖可以發(fā)現(xiàn),一對節(jié)點(diǎn)顛倒源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)后,它們的RTT均值基本不變,這一方面啟示我們一對節(jié)點(diǎn)的RTT具有對稱性,另一方面也在某種說明了終端節(jié)點(diǎn)的異質(zhì)性幾乎不影響RTT的均值.
地理位置對RTT的影響
兩端節(jié)點(diǎn)的地理位置是影響它們的網(wǎng)絡(luò)拓?fù)潢P(guān)系的重要因素,而后者又直接決定了RTT各組成部分中的交換延時(shí)和傳播延時(shí),但是由于互聯(lián)網(wǎng)拓?fù)浜陀蜷g路由的復(fù)雜性,節(jié)點(diǎn)的地理位置與RTT并不是簡單相關(guān)的.由于無法從PAPP的數(shù)據(jù)中恢復(fù)出兩節(jié)點(diǎn)間路由的歷史信息,而且在長達(dá)3個(gè)月的時(shí)間內(nèi)兩點(diǎn)間的路由可能會發(fā)生多次變化,所以我們難以獲知一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)在通信媒介中傳播的精確距離.為此,我們把地球假設(shè)為一個(gè)半徑為1的球體,利用PlanetLab節(jié)點(diǎn)的經(jīng),緯度坐標(biāo)計(jì)算兩節(jié)點(diǎn)間的球面距離.
圖 14 采樣次數(shù)大于1000的節(jié)點(diǎn)對的平均RTT與地理距離的關(guān)系
圖 14為PAPP數(shù)據(jù)中RTT的有效采樣次數(shù)大于1000的全部節(jié)點(diǎn)對(共133519對)的平均RTT與地理距離的關(guān)系,初步來看二者并不具有明顯的相關(guān)性.出人意料的是,有相當(dāng)數(shù)量的節(jié)點(diǎn)對之間的平均RTT達(dá)到了10秒鐘,這是難以用正常情況下造成互聯(lián)網(wǎng)端到端延時(shí)的原因解釋的,盡管我們無法找到確切的證據(jù),但這些明顯超出互聯(lián)網(wǎng)上正常端到端延時(shí)(廣域網(wǎng)RTT應(yīng)在幾十到幾百毫秒之間)的RTT很可能是由于鏈路故障或終端節(jié)點(diǎn)的處理器負(fù)載過重等特殊原因造成的.
圖 15 采樣次數(shù)大于8500的節(jié)點(diǎn)對的平均RTT與地理距離的關(guān)系
圖 15為PAPP數(shù)據(jù)中RTT的有效采樣次數(shù)大于8500的全部節(jié)點(diǎn)對(共29373對)的平均RTT與地理距離的關(guān)系,可以發(fā)現(xiàn)與圖 14的圖像存在顯著差別.節(jié)點(diǎn)對的RTT不僅與地理距離表現(xiàn)出相關(guān)性,而且為近似正比的關(guān)系,尤其是在各種距離下的RTT下限(圖 15的紅色直線).如果假設(shè)地球的半徑近似為6500千米,則根據(jù)圖 15中直線的斜率可以估算出數(shù)據(jù)包的最大平均傳播速度為60千米/毫秒.注意數(shù)據(jù)包經(jīng)由的實(shí)際地理路徑一般與連接兩點(diǎn)的地球球面圓弧并不吻合,但圖 15的圖像說明確實(shí)存在著網(wǎng)絡(luò)路徑與球面圓弧非常接近的節(jié)點(diǎn)對,即使兩節(jié)點(diǎn)間的地理距離很遠(yuǎn).我們認(rèn)為圖 15與圖 14的差別可以這樣解釋:PAPP數(shù)據(jù)中有效采樣次數(shù)大的節(jié)點(diǎn)對之間的網(wǎng)絡(luò)路徑和節(jié)點(diǎn)本身的可靠性都比較高.從這種意義上說,圖 15反映的節(jié)點(diǎn)對的RTT和地理距離的關(guān)系具有更大的代表性和可信度.圖 15的平均RTT一般都在正常范圍之內(nèi),而圖 14中違背規(guī)律的節(jié)點(diǎn)對的平均RTT一般都明顯超過正常范圍也證明了這一點(diǎn).
圖 16分別為數(shù)據(jù)包在中國,美國,歐洲內(nèi)部,以及跨越太平洋或大西洋時(shí),兩端節(jié)點(diǎn)的地球球面距離(假設(shè)地球半徑為6500千米)與RTT的比值(我們在本文中稱之為數(shù)據(jù)包的傳播速度)的概率分布函數(shù)曲線.可以看到,中國內(nèi)部和美國內(nèi)部的曲線非常相似;相比之下,數(shù)據(jù)包在歐洲內(nèi)部的平均傳播速度則明顯低于在中國內(nèi)部和美國內(nèi)部.當(dāng)數(shù)據(jù)包在不同大洲之間遠(yuǎn)距離傳輸時(shí),它的傳播速度差別更為顯著:統(tǒng)計(jì)意義上,數(shù)據(jù)包在美國和歐洲之間傳播最快,在中國和美國之間次之,但在兩種情況都比在中國和歐洲之間快1倍左右.從RTT的均值來看,中國和美國之間為283.4毫秒,美國和歐洲之間為233.8毫秒,而中國和歐洲之間接近二者之和為456.4毫秒.
圖 16 數(shù)據(jù)包在不同地理位置的節(jié)點(diǎn)間傳播速度的累計(jì)概率密度函數(shù)曲線
(假設(shè)地球?yàn)榘霃綖?500千米的球體)
某些網(wǎng)絡(luò)具有特殊的網(wǎng)絡(luò)拓?fù)?這會對RTT造成顯著影響,從而使地理位置的啟發(fā)信息失效.例如,由于中國教研網(wǎng)(CERNET)的所有對外出口都設(shè)置在北京(圖 17所示),所以盡管位于廣州的華南理工大學(xué)的節(jié)點(diǎn)與香港科技大學(xué)的節(jié)點(diǎn)僅距離150千米左右,數(shù)據(jù)包卻要先從廣州經(jīng)由2000千米以外的北京的對外出口再到達(dá)香港.華南理工的節(jié)點(diǎn)與清華的節(jié)點(diǎn)間的平均RTT約為40毫秒左右,清華與香港科技的節(jié)點(diǎn)間的平均RTT約為100毫秒左右,而華南理工與香港科技間的平均RTT恰好約為前兩者之和為140毫秒左右.
圖 17 CERNET拓?fù)鋱D
IP地址共同前綴的長度與RTT的關(guān)系
IP地址由互聯(lián)網(wǎng)信息中心(InterNIC)負(fù)責(zé)管理和分配.IP-V4的地址為32位,起初被劃分為A,B,C,D,E五類,實(shí)際中一般常提到前三類;每類地址都含有一個(gè)固定的前綴和相應(yīng)的范圍.由于A類地址太少,而一個(gè)C類地址段對一個(gè)組織機(jī)構(gòu)而言又通常不夠用,所以大多數(shù)情況下被分配都是B類地址,致使B類地址已快被分發(fā)殆盡.為解決這個(gè)問題,InterNIC在1993-1994年前后采用了無類別地址域間路由(CIDR)技術(shù)【An Architecture for IP Address Allocation with CIDR】.CIDR使用一個(gè)IP地址前綴作為子網(wǎng)掩碼,如果兩個(gè)IP地址與子網(wǎng)掩碼進(jìn)行位與運(yùn)算結(jié)果相同,那么路由器會認(rèn)為它們位于同一地址段.例如,166.111.248.0/25表示與166.111.248.0具有相同的25位前綴IP地址段,該段共含有128個(gè)IP地址.這樣, InterNIC就能夠通過子網(wǎng)掩碼更靈活地控制分配的IP地址段的容量.
CIDR的另一個(gè)重要作用是有效減小域間路由器的路由表長度.在BGP協(xié)議中,路由器一般為同一網(wǎng)段的所有IP僅存儲一條路由記錄,例如,"166.111.248.0/25 next_hop"表示目標(biāo)地址為166.111.248.0到166.111.248.128的任意數(shù)據(jù)包都將被轉(zhuǎn)發(fā)到同一臺下一跳的路由器.
從上面的原理不難看出,IP地址前綴在一定程度上與物理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對應(yīng),因而會直接影響端到端的延時(shí)性能.直觀上考慮,兩個(gè)節(jié)點(diǎn)具有的IP地址前綴越長,它們的網(wǎng)絡(luò)距離越小,同屬于一個(gè)接入網(wǎng)或網(wǎng)絡(luò)服務(wù)商(ISP)的可能性越大,它們通信時(shí)經(jīng)過的自治域和網(wǎng)絡(luò)中繼設(shè)備的數(shù)量越少,所以,它們的端到端延時(shí)性能會越好.

圖 18 按位計(jì)算的IP地址共同前綴的長度分別與RTT和地理距離的關(guān)系
從圖 18可以看出,隨著節(jié)點(diǎn)的IP地址共同前綴長度的增大,它們的RTT和地理距離都在統(tǒng)計(jì)意義上稱減小趨勢,但這種關(guān)系并不是簡單單調(diào)的,這啟示我們應(yīng)該使用較大的劃分粒度來減小誤用啟發(fā)信息的概率,例如使用字節(jié)為單位計(jì)算IP地址共同前綴的長度與RTT和地理距離的啟發(fā)式關(guān)系(圖 19所示).
圖 19 按字節(jié)計(jì)算的IP地址共同前綴的長度分別與RTT和地理距離的關(guān)系
結(jié)論
本文提出了一種描述互聯(lián)網(wǎng)端到端延時(shí)的隨機(jī)過程模型,將延時(shí)的變化分為躍變和攝動兩種.延時(shí)的躍變主要是路由變化造成的,發(fā)生的頻率較低,但一般會改變延時(shí)的統(tǒng)計(jì)特征;延時(shí)的攝動主要是處理器和網(wǎng)絡(luò)負(fù)載變化造成的,無時(shí)無刻不在發(fā)生,但在攝動過程中延時(shí)的統(tǒng)計(jì)特征一般保持不變,可以近似為均值遍歷的平穩(wěn)過程.我們使用PAPP項(xiàng)目的RTT數(shù)據(jù)分別驗(yàn)證了端到端延時(shí)的確具有這些性質(zhì),從而證實(shí)了模型的有效性.這個(gè)模型為使用近期測量值預(yù)測未來短期內(nèi)的延時(shí)提供了理論基礎(chǔ).
我們用PAPP的數(shù)據(jù)實(shí)際考察和比較了幾種延時(shí)預(yù)測方法,結(jié)果表明使用最近兩次測量的較小值能夠使預(yù)測的均方誤差最小.
最后,我們研究了地理位置和IP地址共同前綴的長度與節(jié)點(diǎn)間端到端延時(shí)的聯(lián)系,討論如何恰當(dāng)?shù)乩盟鼈冏鳛閱l(fā)信息,在使用探測手段前對延時(shí)進(jìn)行初步的粗略估計(jì).
附錄一 節(jié)點(diǎn)對列表
源節(jié)點(diǎn)IP列表
128.214.112.92
130.208.18.30
160.36.57.172
192.38.109.144
198.78.49.56
128.223.6.112
130.75.87.83
161.106.240.18
193.10.64.35
202.79.220.49
129.240.228.138
132.227.74.40
169.229.50.8
193.205.215.74
205.189.32.129
129.242.19.197
132.65.240.102
171.64.64.217
198.32.154.187
205.189.33.178
129.74.152.66
147.83.118.123
192.208.48.3
198.32.154.227
219.243.201.65
目標(biāo)節(jié)點(diǎn)IP列表
219.243.201.65
205.189.33.178
205.189.32.129
198.32.154.187
198.32.154.202
171.64.64.217
160.36.57.172
198.32.154.210
198.32.154.227
128.223.6.112
219.243.200.41
219.243.200.49
129.240.228.138
130.208.18.30
128.214.112.92
169.229.50.8
193.10.64.35
193.205.215.74
143.89.126.13
129.242.19.197
132.227.74.40
130.75.87.83
147.83.118.123
192.38.109.144
132.65.240.102
IP地址
域名
維護(hù)單位
128.214.112.92
planetlab2.hiit.fi
Helsinki Institute for Information Technology
128.223.6.112
planetlab2.cs.uoregon.edu
University of Oregon
129.240.228.138
planetlab2.simula.no
Simula Research Laboratory
129.242.19.197
planetlab2.cs.uit.no
University of Tromso
129.74.152.66
planetlab1.cse.nd.edu
University of Notre Dame
130.208.18.30
planetlab2.ru.is
Reykjavik University - Network Laboratory
130.75.87.83
planet1.learninglab.uni-hannover.de
L3S University of Hannover
132.227.74.40
planetlab-01.ipv6.lip6.fr
Laboratoire d'Informatique de Paris
132.65.240.102
planet3.cs.huji.ac.il
The Hebrew University of Jerusalem
143.89.126.13
plab2.cs.ust.hk
The Hong Kong University of Science and Technology
147.83.118.123
planetlab3.upc.es
Universitat Politenica de Catalunya
160.36.57.172
pl1.cs.utk.edu
University of Tennessee at Knoxville
161.106.240.18
planetlab1lannion.rdfrancetelecom.com
France Telecom R&D Lannion
169.229.50.8
planetlab6.millennium.berkeley.edu
University of California at Berkeley
171.64.64.217
planetlab-2.stanford.edu
Stanford University
192.208.48.3
pli1-crl-1.crl.dec.com
HP Labs, Cambridge
192.38.109.144
planetlab2.diku.dk
Datalogisk Institut Copenhagen
193.10.64.35
planetlab1.sics.se
Swedish Institute of Computer Science
193.205.215.74
planetlab1.science.unitn.it
University of Trento - DIT
198.32.154.187
planetlab2.dnvr.internet2.planet-lab.org
Internet2 0 Denver
198.32.154.202
planetlab1.kscy.internet2.planet-lab.org
Internet2 - Kansas City
198.32.154.210
planetlab1.losa.internet2.planet-lab.org
Internet2 - Los Angeles
198.32.154.227
planetlab2.wash.internet2.planet-lab.org
Internet2 - Washington
198.78.49.56
planetlab4.nbgisp.com
Intel Labs - Oregon
202.79.220.49
planetlab1.singapore.equinix.planet-lab.org
Equinix - Singapore
205.189.32.129
planet1.calgary.canet4.nodes.planet-lab.org
Canarie - Calgary
205.189.33.178
planet1.ottawa.canet4.nodes.planet-lab.org
Canarie - Ottawa
219.243.200.41
tju1.6planetlab.edu.cn
CERNET - Tianjin University
219.243.200.49
neu1.6planetlab.edu.cn
CERNET - Northeast University
219.243.201.65
pku2.6planetlab.edu.cn
CERNET - Peiking University
注:由于PAPP的數(shù)據(jù)缺失問題,上述節(jié)點(diǎn)共組成610對節(jié)點(diǎn)(15對節(jié)點(diǎn)的RTT序列缺失),所有節(jié)點(diǎn)對的RTT序列的采樣次數(shù)都大于8390.
附錄二 定理1的證明
證明:若,則易得,命題成立;
若,不失一般性,假設(shè),則.由于
又根據(jù)柯西不等式,可得 ,
所以,有 ,當(dāng)且僅當(dāng)時(shí)等號成立;
要嚴(yán)格證明,可把問題轉(zhuǎn)化為以為目標(biāo)函數(shù)對進(jìn)行有約束非線性規(guī)劃的問題,借助Lagrange成子和Kuhn-Tucker條件可以求出的最大值即為.因篇幅限制,我們用另一種直觀的方法來證明右邊不等號成立.首先證明當(dāng)取得最大值時(shí),中至多有1個(gè)數(shù)既不不等于,也不等于,即不存在這樣的和滿足.使用反證法,假設(shè)存在這樣的和,若,令,顯然,而且;若,令,同樣有,而且;故有

這與已使取得最大值的條件矛盾.而不難證明,當(dāng)中至多有1個(gè)數(shù)既不不等于,也不等于時(shí),,即是的最大值,從而.
證畢.
6月有數(shù)十個(gè)文件在RTT元組矩陣后多出了一行非法字符,因其不對本文造成任何影響,故沒有列出.
這與兩端節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)潢P(guān)系有關(guān),因?yàn)橛醒芯拷Y(jié)果表明互聯(lián)網(wǎng)的負(fù)載受人類的作息習(xí)慣影響,例如企業(yè)網(wǎng)絡(luò)在工作日的負(fù)載高于周末,而家庭用戶則恰恰相反;但是,當(dāng)兩個(gè)節(jié)點(diǎn)間的路由需要經(jīng)過較多異質(zhì)網(wǎng)絡(luò)(如兩個(gè)位于不同大洲的節(jié)點(diǎn))時(shí),這種效應(yīng)幾乎可以忽略.
選擇的原則是它們與Duke大學(xué)的3個(gè)節(jié)點(diǎn)間RTT采樣數(shù)據(jù)缺失最少
本文的討論僅限于PAPP中使用PING探測RTT的情況.在實(shí)際應(yīng)用中,如果上次業(yè)務(wù)要求終端節(jié)點(diǎn)對數(shù)據(jù)包進(jìn)行較大計(jì)算量的處理或者需要傳送較大的數(shù)據(jù)包,那么終端節(jié)點(diǎn)的硬件配置,接入方式和帶寬可能會對平均RTT造成不可忽略的影響.
從PING的工作原理來看,源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)進(jìn)行的操作不同.如果RTT的數(shù)學(xué)期望受終端節(jié)點(diǎn)的硬件配置或接入方式和網(wǎng)絡(luò)帶寬的影響顯著,那么RTT應(yīng)該不具有對稱性.
考慮到RTT的均值具有對稱性(本文3.3.5節(jié)),所以我們僅統(tǒng)計(jì)了中國的節(jié)點(diǎn)作為源節(jié)點(diǎn),美國和歐洲的節(jié)點(diǎn)分別作為目標(biāo)節(jié)點(diǎn);以及美國的節(jié)點(diǎn)作為源節(jié)點(diǎn),歐洲節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)對.