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