基于通用PC的單向時延測量方法

劉愛東，黃 彬，張永輝

(1.海軍航空工程學院兵器科學與技術系，山東煙臺264001;2.海軍航空工程學院研究生管理大隊，山東煙臺264001)

0 引言

網絡性能代表了網絡基礎設施向上層應用提供的服務質量，單向時延是評價互聯網性能的重要參數之一。在網絡應用中，許多應用對不同方向上的時延指標具有不同的要求，測量單向時延指標可以比較準確的反映網絡向應用實際提供的服務水平［1］。單向時延也是測量時延抖動、網絡帶寬等性能指標的基礎，能夠應用于SLA(service level agreement)和QoS(quality of service)的管理，也在網絡性能監測、網絡行為分析、擁塞控制算法研究等領域得到了廣泛應用。

采用主動測量方法進行單向時延測量，在無端到端時鐘同步機制時，時鐘不同步是時延測量中誤差的主要來源，目前國內外學者對單向時延測量問題做了大量研究，提出了基于軟件算法的方法或基于外部時鐘源的方法來消除時鐘不同步的影響。基于軟件算法的測量方法主要有基于模式識別時鐘重置檢測算法、基于漂移補償的時間同步方法、基于擬合偏差法、分段最小優化法、最小面積法、基于凸集的優化法等［2-7］。這些方法均側重于對時鐘偏差 (clock skew)的糾正，并未解決時鐘偏移 (clock offset)的影響。且由于互聯網是一個不斷增長的、分布的、不協作、異質的復雜巨系統，具有諸多不確定因素，這些算法因計算復雜，難以實時跟蹤時延的變化，缺乏實用性。基于外部時鐘源的方法主要是采用全球定位系統GPS與專用于分組捕獲的DAG卡配合進行端到端時延測量。但是這種測量方式所需設備價格昂貴，且部署位置有限，不能得到大規模應用。

本文旨在找到一種基于通用PC架構的，不依賴于外部時間源且計算簡單，能夠實時追蹤端到端時延變化，避免時鐘不同步帶來的影響的單向時延測量方法。

1 單向時延分析

1.1 單向時延定義

在RFC 2679中將單向時延指標分為單次測量單向時延指標和多次抽樣統計測量時延指標兩種［8］。本文主要研究單向時延指標，其定義為:在T時刻從源節點發送測量分組的第一位，在T+dT時刻目的節點收到測量分組的最后一位，則從源節點到目的節點在時刻T的單向時延為dT。

1.2 單向時延的構成

當測量分組從發送主機生成到接收主機接收到完整分組的過程中，經歷的時延主要有以下幾個時延組成:

(1)傳輸時延

傳輸時延是把測量分組發送到鏈路上的時間，即從分組的第一位直至最后一位到達鏈路的時間，設分組的大小為L，鏈路的容量為C，則傳輸時延為L/C。

(2)傳播時延

傳播時延是一個測量分組從鏈路的一端傳播到鏈路的另一端，主要取決于鏈路的電氣特性。對于一個鏈路，如果其物理長度為d，信號傳播速度為v，則傳播時延為d/v。

(3)路由器時延

當一個測量分組到達路由器后，路由器處理分組的時間稱為處理時延。

由于網絡負載的突發性，當一個分組到達路由器時并不能立即得到處理而被放入緩沖隊列等待處理的時間稱為排隊時延。

由上所述，包含n跳的單向時延可以表示為

式中:L——測量分組的長度，Ci——第i跳鏈路的帶寬，di——第i跳鏈路的物理長度，vi——第i跳鏈路的傳播速率，pi——測量分組在第i個路由器上的處理時延，qi——測量分組在第i個路由器上的排隊時延。

1.3 單向時延性質分析

當鏈路在測量期間保持穩定且測量分組長度一致時，傳輸時延、傳播時延和處理時延是不變的，而排隊時延隨著網絡負載情況的變化而不同，則式 (1)可以改寫為

并且有

研究發現，無論是網絡路徑還是路由器，短時間內測量到其最小單向時延的概率非常大［9］，所以，間隔時間T發出兩個測量分組到達接收端時均沒有經歷排隊時延的概率也非常大，該結論在下文中將被使用。

1.4 單向時延的測量

采用主動測量方法時，通用方法是在測量分組中打上發送端發送分組時的時間戳，在接收端記錄接收測量分組時的時間戳，通過比較兩個時間戳得到單向時延值。如上所述，時鐘不同步對單項時延的測量帶來了很大影響，如圖1所示，時鐘的不同步造成時延測量結果出現了隨時間推移而增加的趨勢。

圖1 時鐘不同步時單向時延測量結果

2 使用時間戳計數器測量單向時延分析

2.1 時間源的選擇

2.1.1 時間戳計數器簡介

時間戳計數器 (time stamp counter，TSC)是 Intel自Pentium系列CPU以來提供的一個部件，它以64位無符號整型數的方式，記錄了自CPU上電以來所經過的時鐘周期數，并且提供了一條RDTSC匯編指令供應用程序讀取其值。為敘述方便，下文均稱時間戳計數器為TSC。

2.1.2 采用TSC值作為時間源分析

(1)時間分辨率

采用TSC值作為時間源，其分辨率取決于CPU頻率，若CPU頻率為H，則TSC分辨率為1/H。目前，主流通用PC主機CPU頻率已經超過2GHz，則以TSC值為時鐘源，可以達到納秒級的時鐘分辨率，且只需一條匯編指令就能讀取其值，相較于其他計時方式開銷更小。

(2)計時穩定性

文獻［10］中，比較了采用TSC值作為時間源與采用操作系統時鐘作為時間源，這兩種方法的開銷大小，穩定性和準確性，證明前者要優于后者。由此，采用TSC值作為時間源是完全可行的。

2.2 時間戳分析

設參考時鐘為標準時間，測量分組的發送端與接收端主機的時間源采用其TSC值，發送主機CPU上電的時刻為ts0，CPU頻率為hs，ts為發送時的標準時刻，則發送端主機的時間戳函數為

同理，設接收端時鐘的初始值為tr0，CPU頻率為hr，tr為接收的標準時刻，則接收端主機的時間戳函數為

2.3 測量方法分析

設第i次測量中，真實時間時刻S時發送端發出測量分組，則由式 (4)，發送時間為

同理，設真實時間時刻R時接收端收到測量分組，則由式 (5)，接收時間為

而探測到的單向時延值ti為

聯立 (6)、(7)、(8)整理得到

以接收端主機CPU頻率為參考，有

由式 (10)改寫式 (9)得到

令θ=tr0－ts0，則θ表示的含義為接收端和發送端主機CPU上電時間差。

綜上 (11)式可寫為

分析式 (12)，設相鄰兩次測量值分別為

則有

由式 (15)可以看出，相鄰兩項測量值之間的差值，當主機CPU頻率測量準確且測量分組沒有經過排隊時延時，其值為零，當主機CPU頻率測量不準確時，其值為一個不為零的常數，測量得到的單向時延值表現為一條有斜率的直線。

至此，按照式 (12)可以采用TSC值作為時間源進行單向時延的測量，所需量為雙端主機的CPU上電時間差，接收端主機CPU頻率，及收發雙方收發測量分組時的時間。

綜上所述，采用TSC值作為時間源測量單向時延時，其影響主要來自雙端主機CPU頻率的不一致，接收主機CPU頻率值的準確與否和雙端主機CPU的上電時間差測量準確與否，測量值理論分析結果如圖2所示。如何測量到真實時延值的關鍵就在于消除上述3種影響帶來的誤差。

圖2 測量值理論分析

2.4 各量測量方法與糾斜處理

2.4.1 CPU頻率的測量

(1)利用NTP服務器測量CPU頻率

NTP(Network Time Protocol)是一個基于TCP/IP的、跨越廣域網或局域網的復雜的同步時間協議，通常可獲得毫秒級的同步精度。網絡中的NTP服務器之間采用GPS全球同步授時，同步精度可以達到微秒級，因此可以認為NTP服務器的時間即為標準時間。

文獻［10］中提出了利用NTP服務器，周期向其請求時間戳，通過計算標準時間段內TSC增加的值來推算CPU主頻的方法。這種方法能夠比較準確的測量出CPU主頻，但是并不是所有主機都支持NTP協議，也不是所有網絡環境都有NTP服務器或者標準時間服務器，因此文獻 ［10］提出的測量主頻的方法并不能得到廣泛應用。

(2)利用系統時間估算CPU頻率

利用操作系統的時間為參考時間，可以估算出CPU頻率。例如，在以操作系統時間為參考的1s內，TCS值增加的數值即為CPU主頻。

由于系統負載的影響，系統時間計時會出現一定的波動，導致測量得到的結果也會出現小范圍波動，因此，采用這種方式估算CPU頻率時應當統計一段時間內的所有測得的CPU頻率值，取其統計平均值，這樣測量結果隨著測量時間的增加而趨于穩定。

由于調用系統計時也需要一定的時間開銷，導致TSC寄存器增加的值偏大，即測得的CPU頻率大于實際CPU頻率，在測量單向時延時會導致 (15)式的值不為零，所以在進行單向時延測量值的計算與處理時要有糾斜處理，關于糾斜的方法將在下文闡述。

2.4.2 發送端與接收端的CPU頻率差測量

所以得到

由上文，間隔時間T發出兩個測量分組到達接收端時沒有經歷排隊時延的概率很大，即取最小的概率

很大，則在多次測量中必然能夠測量到準確的α值，且

2.4.3 CPU上電時間差的測量

設測量分組的發送端與接收端主機分別為A機與B機，測量時，測量分組在A、B間往返均為同一條鏈路。定義從A機到B機的鏈路為前向路徑，對應的單向時延為前向時延，設其最小值為tAB，同樣的定義從B機到A機的鏈路為后向路徑，對應的單向時延為后向時延，設其最小值為tBA，如圖3所示。

由上文分析可得，在測量次數足夠多時，前向時延和后向時延均能取得最小值，即tAB、tBA，則由圖有

設A機CPU頻率為hs，其CPU上電時刻為ts0，t1時刻TSC寄存器值為N1，t4時刻TSC寄存器值為N4，同理，設B機CPU頻率為hr，其CPU上電時刻為tr0，t2時刻TSC寄存器值為N2，t3時刻TSC寄存器值為N3。

結合 (6)、(7)、(8)、(9)得到

又θ=tr0－ts0，hs=αhr，且往返均為同一條鏈路，有tAB=tBA，結合式 (18)、(19)，得到

則在已測得hr和α的基礎上，按照式 (22)可以計算出θ的大小，其準確度取決于hr測量的準確與否。

2.4.4 糾斜處理

由上文可知，采用利用操作系統時間計算CPU頻率時，得到的接收端頻率估值大于實際值，造成實際測量結果近似為一條有斜率的直線，明顯不符合實際情況，為了得到正確的單向時延測量值需要做進一步的糾斜處理。

圖3 CPU上電時間差測量

設在相鄰測量分組沒有經歷排隊時延且接收端CPU頻率估計不準的情況下，按照式 (15)令

則對任意的相鄰測量分組之間，有

得到

其中n表示測量的次數，整理得

結合式 (12)，在實時測量時，對測量得到的時延值進行糾斜處理，有

3 測量實例

3.1 測量分組與鏈路選擇

測量分組選用UDP分組，以發送端主機系統時間為參考，間隔1s周期發送測量分組，分組包含的內容為發送時刻發送主機的TSC寄存器值，即發送端的時間戳，分組大小為100字節。

測量選擇的鏈路為:從山東煙臺的某電信接入點到山東煙臺的某聯通接入點，測量期間使用用Trace Route工具進行追蹤，結果顯示測量期間鏈路保持穩定，且往返鏈路為同一條，所經路由IP地址如表1所示。

表1 測量實例鏈路包含路由的IP地址

3.2 測量結果和說明

接收端主機CPU頻率測量采用利用系統時間估算CPU頻率的方式，其測量結果如圖4所示。

圖4 利用系統時間測量CPU頻率的結果

在單向時延測量開始前，雙方主機協作發送測量分組，按照上文所述方法進行了CPU上電時間差的測量，測量得到雙端主機CPU上電時間差為238.5126 s。

圖5左圖中的是經過測量得到的t'i值，未消除CPU上電時間差的影響，右圖中的是消除CPU上電時間差影響之后的測量值。由圖5可以發現由于接收端主機CPU頻率在測量時不準確，造成單向時延測量值表現下降的趨勢。

圖5 消除CPU上電時間差前后對比

圖6 中是對已消除CPU上電時間差影響的測量值進行糾斜處理的結果。

圖6 糾斜前后對比

圖7 顯示是的對原始測量值進行各步糾正，并得到最終結果的效果圖。

圖7 各步糾正效果對比

4 結束語

本文首次采用時間戳計數器值作為時間戳來源，應用到單向時延測量的方法中。通過理論推導，證明了該方法測量單向時延的可行性，并且闡述了消除誤差的理論方法，通過測量CPU頻率差，雙端主機協作測量CPU上電時間差及對測量結果進行糾斜的方式得到可信的測量結果。由于采用時間戳計數器值取代操作系統時間，避免了目前各種單向時延測量方法所要面對的時鐘偏差和時鐘偏移的問題，并且通過實例測量，驗證了該方法的有效性。

［1］YANG Jiahai，WU Jianping，AN Changqing.The theory and application of internet measurement［M］.Beijing:Post＆ Telecom Press，2009:98-165(in Chinese).［楊家海，吳建平，安長青.互聯網絡測量理論與應用［M］.北京:人民郵電出版社，2009:98-165.］

［2］YANG Tan，SUN Hanlin，JIN Yuehui，et al.An glgorithm for adaptive detection of clock reset based on pattern recognition ［J］.Chinese High Technology Letters，2008(5):441-446(in Chinese).［楊談，孫韓林，金躍輝，等.基于模式識別的自適應時鐘重置檢測算法 ［J］.高技術通訊，2008(5):441-446.］

［3］QUAN Yujuan，LIU Guixiong，LIU Bo，et al.A RCR clock synchronization model with drift compensation［J］.Journal of South China University of Technology，2010，38(5):76-79(in Chinese).［全渝娟，劉桂雄，劉波，等.具有漂移補償的RCR時鐘同步模型［J］.華南理工大學學報 (自然科學版)，2010，38(5):76-79.］

［4］ZHAO Ying，WANG Yini，MA Yan，et al.Clock synchronnization based on fitting offset［J］.Computer Engineering，2008，34(16):13-15(in Chinese).［趙英，王旖旎，馬嚴，等.基于擬合偏差的時鐘同步 ［J］.計算機工程，2008，34(16):13-15.］

［5］NIE Yuting，GAO Zhonghe.Time synchronization in one-way delay measurement［J］.Coummunications Technology， 2009， 10(42):125-127(in Chinese).［聶玉婷，高仲合.單向時延測量中的時間同步問題 ［J］.通信技術，2009，10(42):125-127.］

［6］LI Leimin，SUN Jie.Study of time synchronization alglorithm based on subsection ［J］.Computer Engineering and Applications，2008，44(23):110-113(in Chinese).［李磊民，孫杰.基于分段過濾時間同步算法研究［J］.計算機工程與應用，2008，44(23):110-113.］

［7］WANG Yini，ZHAO Ying.Client system of clock synchro nization based on clock drift rate［J］.Computer Applications and Software，2009，26(12):18-20(in Chinese).［王旖旎，趙英.基于時鐘漂移率的時鐘同步客戶端系統［J］.計算機研究與軟件，2009，26(12):18-20.］

［8］Almes G，Kalidindi S，Zekauskas M.A one-way delay metric for IPPM ［Z］.RFC 2679:Internet Engineering Task Force，1999.

［9］Pagugiannaki EMoon S，Fraleigh C.Measurement and analysis of single-hop delay on an IPbackbone network［J］.IEEE Journal on Selected Areas in Communications，2003，21(6):908-921.

［10］LI Wenwei，ZHANG Dafang，XIE Gaogang，et al.A high precision approach of network delay measurement based on general PC［J］.Journal of Software，2006，27(2):275-284(in Chinese).［黎文偉，張大方，謝高崗，等.基于通用PC架構的高精度網絡時延測量 ［J］.軟件學報，2006，17(2):275-284.］