徐海龍,羅雙喜
(江蘇自動化研究所,江蘇 連云港222006)
時間同步的目的是維護一個全局一致的物理或邏輯時間[1]。確保各個節(jié)點與時間有關(guān)的事件在時間邏輯上的一致性。在各種信息處理系統(tǒng)中,我們對時間的應(yīng)用要求可能不盡相同,怎樣獲取滿足系統(tǒng)需求的時間,成為整個系統(tǒng)性能優(yōu)劣的一個重要內(nèi)容。如何低成本高精度的利用軟件方式實現(xiàn)時間同步,成為Windows平臺中一個亟待解決的問題。一些文章指出已經(jīng)實現(xiàn)了在Windows平臺上的亞毫秒級的時間同步,但是實現(xiàn)過程中都是基于相對虛擬時間[2],而沒有與系統(tǒng)時間關(guān)聯(lián)起來,這不是真正意義的解決問題?;诖?,通過在鏈路層獲取計數(shù)器并轉(zhuǎn)換為系統(tǒng)時間,同時引入時鐘頻率調(diào)整算法,從而實現(xiàn)了高精度時間同步。
在Windows平臺中,如果調(diào)用Windows API函數(shù)GetSystemTime來獲取時間,這個API函數(shù)返回一個SYSTEMTIME結(jié)構(gòu),該結(jié)構(gòu)包含一個wMilliseconds域,在MSDN文檔中說它保存當前的毫秒時間。但是在實際應(yīng)用中,由于Windows操作系統(tǒng)是非實時系統(tǒng),故獲取的時間最大精度不超過10ms[3]。這樣的結(jié)果,對于毫秒級以內(nèi)的時間標簽需求者來說顯然遠遠不夠。下面提出幾種有效獲取時間戳的方法并分析其有效性。
從時間同步過程中獲取時間戳的分析可知,時間戳獲取點距離網(wǎng)絡(luò)接口的遠近是導(dǎo)致時間報文網(wǎng)絡(luò)傳輸延遲計算誤差的重要因素。同步報文時間戳的3個主要可能獲取點如圖1中描繪所示。
(1)從應(yīng)用層直接獲取時間報文發(fā)送/接收到時間戳,即使用原始套接字,直接獲取同步報文到達應(yīng)用層時的系統(tǒng)時間。該方法操作簡單,能快速實時在系統(tǒng)應(yīng)用層捕獲數(shù)據(jù)包的發(fā)送/到達時刻。但受應(yīng)用程序、操作系統(tǒng)、協(xié)議棧處理等因素的影響,使時間準確度有毫秒量級的不確定性;且Windows等常用系統(tǒng)調(diào)用當前系統(tǒng)時間的最低有效位是毫秒,因此造成時間戳的獲取精度只能達到毫秒級。
圖1 時間同步報文傳遞過程
(2)使用或者自行編寫中間層驅(qū)動程序獲取時間報文發(fā)送/接收到時間戳。該方法也是微軟公司推薦使用的一種方法,用戶可以根據(jù)微軟提供的win2000DDK中提供的驅(qū)動程序?qū)r間報文的發(fā)送/接收時間進行標記。具體的實現(xiàn)方式上可分為用戶級和內(nèi)核級兩類。其中內(nèi)核級主要是NDIS中間層捕獲過濾驅(qū)動程序、NDIS捕獲過濾鉤子驅(qū)動程序等[4-6],它們都是利用網(wǎng)絡(luò)驅(qū)動來實現(xiàn)的;而用戶級的包括Windows2000包捕獲過濾接口等。
利用NDIS中間驅(qū)動程序可以在網(wǎng)卡驅(qū)動程序和傳輸驅(qū)動程序之間插入一層處理程序,從而可以用來截獲網(wǎng)絡(luò)封包并進行時戳獲取、重新封包及過濾等操作。由于NDIS中間驅(qū)動程序位于網(wǎng)卡和傳輸驅(qū)動程序之間,所以它可以截獲較為底層的封包。從而可以完成更為低級的操作,安全系數(shù)也較高。
(3)在網(wǎng)卡處理處的物理層獲取時間報文發(fā)送/接收到時間戳。該方法要借助于硬件從物理層獲取時間報文發(fā)送/接收到時間戳,其時間戳獲取精度理論上可達納秒級,基于PTP協(xié)議的IEEE1588標準即是采用這種時間標記方法。這種方法需要給每個系統(tǒng)增加額外的硬件設(shè)備提高時間標記的讀取精度,顯然增加了系統(tǒng)開發(fā)的成本,也不便于已有系統(tǒng)的使用。
以上3種方法,時間戳獲取點離網(wǎng)絡(luò)端口越近,獲得的時間戳精度就越高,但其對軟硬件的要求也隨之增加。在應(yīng)用層獲取時間戳,只需在應(yīng)用程序中加入系統(tǒng)支持的讀取時戳命令即可;在驅(qū)動層獲取時間戳,需要自行編寫驅(qū)動程序截獲時間報文并標記時戳;而在網(wǎng)卡物理層獲取時間戳,則需要加入硬件處理電路及相應(yīng)的處理程序才能獲得高精度時間戳。
通過對時間戳獲取途徑的分析,借鑒以上第二種方法,采用以下算法,本算法通過操作系統(tǒng)支持的NDIS標準接口,以NPF驅(qū)動方式獲取高精度的時間戳,以降低應(yīng)用程序負載、操作系統(tǒng)任務(wù)調(diào)度等因素引起的時間偏差抖動。
網(wǎng)絡(luò)時間同步過程中,客戶端/服務(wù)器從發(fā)送報文前記錄時間到實際從網(wǎng)卡發(fā)送出報文的時間,包括應(yīng)用層、協(xié)議棧、網(wǎng)卡等多個環(huán)節(jié)的處理時間。其中,應(yīng)用層、協(xié)議棧的處理時延因為受應(yīng)用程序負載、操作系統(tǒng)任務(wù)調(diào)度、協(xié)議棧緩沖隊列中的報文數(shù)量、長度及其處理等因素的影響而具有較大的不確定性。
對于現(xiàn)在廣泛使用的Intel Pentium系列計算機,可通過其本身提供的RDTSC指令 (read time stamp counter),獲得自計算機系統(tǒng)上電以來的64位時鐘周期數(shù) (時間計數(shù)器值),進而建立一個與系統(tǒng)時間關(guān)聯(lián)的、支持時間偏差修正與高精度系統(tǒng)時間獲取的虛擬時鐘,其精度與CPU的時鐘頻率有關(guān),由于CPU主頻非常高,其短時精度可以達到納秒級。
這種時間獲取方法避開了應(yīng)用層、協(xié)議棧等多個環(huán)節(jié)的處理時間以及一系列不確定因素,所以獲取的時間戳非常精確有效。如圖2所示。
圖2 鏈路層獲取精確時間戳
在一個小型計算機組網(wǎng)中,利用計算機晶振中斷計數(shù)實現(xiàn)計時,晶體振蕩器的頻率并不是恒定不變的。因此,計算機節(jié)點i在時刻t的本地時間表示為[7]
式中:c0——網(wǎng)絡(luò)節(jié)點晶振的標準頻率,yi(t)——晶振在t時刻的實際輸出頻率,t0——本節(jié)點系統(tǒng)開始計時的初始時刻。yi(t0)對應(yīng)i節(jié)點在t0時刻的時鐘值。由于現(xiàn)在的Intel Pentium系列計算機,晶振頻率變化非常小,所以在短時期內(nèi),可以認為節(jié)點晶振的頻率為一恒值。基于這一規(guī)律,根據(jù)上式可得:第i個計算機節(jié)點的時鐘模型又可表示為yi(t)=gi(t-t0)+yi(t0),其中g(shù)i=fi/f0,fi是節(jié)點i的晶體振蕩器的實際頻率。由于受到硬件實際性能影響,晶振的實際頻率與標準頻率之間存在極其微小的誤差,如下所示
式中:ρ——絕對頻率上限,通常ρ的值在1~100PPM之間[8]。
通過系統(tǒng)函數(shù)調(diào)用可以獲取時鐘頻率 (其值一般很大),如果在鏈路層得到的計數(shù)器仍然使用這個時鐘頻率,則通過它計算的時間間隔就不夠精確。所以我們從新計算一個在鏈路層使用的頻率值,然后在需要定時的時間的兩端分別調(diào)用計數(shù)器以取得計數(shù)器的數(shù)值,兩次數(shù)值的差值通過這個頻率即可換算成時間間隔,如圖3所示。
圖3 計數(shù)器與系統(tǒng)時間關(guān)系
假定系統(tǒng)運行開始時通過系統(tǒng)函數(shù)取得計數(shù)器為s_p,通過驅(qū)動獲取計數(shù)器值d_p,一個系統(tǒng)任務(wù)中斷后通過系統(tǒng)函數(shù)取得計數(shù)器為s_pl,通過驅(qū)動獲取計數(shù)器值d_p1,令σs為通過系統(tǒng)函數(shù)取得計數(shù)器之差,σd為通過驅(qū)動獲取計數(shù)器之差,則
設(shè)通過系統(tǒng)函數(shù)取得時鐘頻率為λ,由于我們基于鏈路層獲取時間戳,設(shè)我們在鏈路層的實際時鐘頻率為λr,則
設(shè)通過系統(tǒng)函數(shù)取得操作系統(tǒng)時間t為參考時間,設(shè)tn為后續(xù)時戳,則
其中n=1,2,3,…。
NTP適用于在無序的網(wǎng)絡(luò)環(huán)境下提供精確和健壯的時間服務(wù),只需單個標準時間源,實現(xiàn)成本較低[9]。
在一個簡單C/S組網(wǎng)中,設(shè)θ為時間客戶端與服務(wù)器端之間的時間偏差;設(shè)δ為時間同步過程中的網(wǎng)絡(luò)路徑延遲。那么客戶機與服務(wù)器進行時間同步時的時序過程如圖4所示。
圖4 NTP客戶機與服務(wù)器校時過程
圖4 中,從客戶端發(fā)送時間報文到接收到服務(wù)器的反饋報文這一個過程中,共記錄了4個時戳,報文在客戶端和服務(wù)器往返過程中,設(shè)總路徑的網(wǎng)絡(luò)時間延遲為δ,由于報文在從客戶端到服務(wù)器與從服務(wù)器到客戶端路徑相等,故都等于δ/2。以服務(wù)器時鐘為基準,設(shè)客戶端時鐘與服務(wù)器時鐘的時間偏差是θ,那么可以得到如下方程式
由此可以求出客戶機與服務(wù)器之間的時間偏差為
式中:T1——客戶端發(fā)送的時間報文,T2——服務(wù)器接收的時間報文,T3——服務(wù)器反饋的時間報文,T4——客戶端接收的服務(wù)器反饋報文。
同時可得到客戶機與服務(wù)器之間的半程網(wǎng)絡(luò)延遲為
基于即時時間和即時偏差的傳統(tǒng)時鐘調(diào)整策略會受到偶然過大即時偏差的影響,無法有效避免在得到時間偏差和延遲的基礎(chǔ)上,傳統(tǒng)的做法是利用這些來進行時鐘調(diào)整,但是網(wǎng)絡(luò)抖動,從而影響時統(tǒng)的準確性[10],針對此問題,使用了如下策略來進行時鐘調(diào)整。
對于現(xiàn)有裝備中廣泛使用的Intel Pentium系列計算機,為了使獲取的時間戳精確有效,首先我們介紹調(diào)整系統(tǒng)時鐘頻率的方法。拋開硬件的升級改造,我們從軟件處理的角度來調(diào)整。
每臺機器都有個計數(shù)器,該計數(shù)器每秒中斷H次,計數(shù)器溢出時,中斷處理程序就將軟件時鐘加1,軟件時鐘是從過去某一已知時間開始的所經(jīng)歷的tick數(shù)。下面將這個時鐘的值稱為C。更明確的說,當UTC時間為t時,機器p的時鐘值為Cp(t)。理想情況下,對于所有的p和t應(yīng)有Cp(t)=1。換句話說,理想情況下dC/dt為1。
實際的計數(shù)器不是準確的每秒中斷H次。理論上說,當H=60時,計數(shù)器應(yīng)每小時生成216 000次ticks。實際上,現(xiàn)代的計數(shù)器芯片的相對誤差大約為10-5,即一臺特定機器每小時的ticks數(shù)范圍為215 998到216 002[11]。更準確的說,如果存在一個常數(shù)ρ,當1-ρ≤dC/dt≤1+ρ成立,就可以認為計數(shù)器是正常工作的。常數(shù)ρ是由計數(shù)器的生產(chǎn)者指定的,稱為最大漂移率 (maximum drift rate)。圖5畫出了精確時鐘和快慢時鐘的關(guān)系。
圖5 時鐘快慢與準確時鐘關(guān)系
為了獲取時鐘漂移率,從而估計出時鐘頻率偏差,可以采用在一定時間內(nèi)獲得連續(xù)時戳數(shù)據(jù)來進行線性擬合[12-13],其算法描述如下:
2.4.1 計算漂移率
設(shè)n組偏差樣本值為 (t1,θ1) (t1,θ1) (t2,θ2)…(tn,,θn),其中ti代表接受到的來自服務(wù)器的第i個時間戳,θi代表即時偏差值,根據(jù)這組值我們列出線性趨勢方程
式中:b0——截距,b1——漂移率。采用最小二乘法即可求得b0,b1
2.4.2 調(diào)整頻率的方法
在網(wǎng)絡(luò)時間協(xié)議 (NTP)中,客戶端要與外部服務(wù)器保持時間同步,可以使用Windows提供的一個API函數(shù)SetSystemTimeAdjustment。這個API有兩個參數(shù),以100納秒為單位的時間調(diào)節(jié)器以及一個布爾值。布爾值變量表示W(wǎng)indows是否禁用時間調(diào)節(jié)器。當啟用時間調(diào)節(jié)器時,系統(tǒng)會在每個時鐘中斷時加上指定的時間調(diào)節(jié)器的值。當禁用時,系統(tǒng)會用添加缺省的時間增量取而代之。但是還有做產(chǎn)生了兩個問題。①首先啟用 (改變)時間調(diào)節(jié)器改變了參考頻率——時間流;②也是一個較大的問題,就是當系統(tǒng)時間被修改后,系統(tǒng)不發(fā)送啟用或禁止通知。即使以最小的156250個單位 (1單位100納秒)缺省時間增量改變某個系統(tǒng)上的時間調(diào)節(jié)器,也將導(dǎo)致參考頻率6.4PPM (1/156250)的改變。如果不加以調(diào)整,幾秒之后沒有進行再同步,就會偏離準確時間越來越遠。為了減少這類調(diào)整帶來的誤差,必須監(jiān)視當前時間調(diào)節(jié)的設(shè)置。對于這個問題的解決方案,我們可以通過調(diào)用SetSystem-TimeAdjustmen的伙伴函數(shù)—GetSystemTimeAdjustment來實現(xiàn)。在足夠短的間隔內(nèi)不斷地執(zhí)行這個檢查并且根據(jù)需要調(diào)整內(nèi)部頻率,就能夠避免客戶端時間偏離服務(wù)器時間太遠。
在得到時鐘漂移率的基礎(chǔ)上,每隔一定的周期調(diào)整時鐘頻率,下面介紹調(diào)整系統(tǒng)時鐘頻率的具體方法和步驟:
(1)獲取n組偏差樣本值為 (t1,θ1) (t1,θ1) (t2,θ2)… (tn,θn),采用最小二乘法即可求得漂移率η0;
(2)取int(η0)調(diào)整時鐘頻率 (int (η0)表示取整),然后再獲取n組偏差樣本值為 (t1,θ1) (t1,θ1) (t2,θ2)… (tn,θn),采用最小二乘法即可求得漂移率η1;
(3)重復(fù)步驟 (2),得漂移率η2,判斷漂移率η2是否大于門限Ω。若滿足則算法停止,否則繼續(xù)執(zhí)行步驟 (2)。
根據(jù)以上原理和方法,為了檢驗該時鐘頻率調(diào)整算法的有效性以及同步效果的精度,在基于相對時間同步[14-15]的小型實驗室局域網(wǎng)內(nèi)進行測試,網(wǎng)絡(luò)均采用100M網(wǎng)卡保持較高流量,采集了超過300個網(wǎng)絡(luò)數(shù)據(jù)來檢驗該時鐘頻率調(diào)整算法的有效性,在時間同步過程中采集了超過2000個網(wǎng)絡(luò)數(shù)據(jù)來計算平均的時鐘同步精度。
首先,選取兩臺裝有Windows XP操作系統(tǒng)的電腦,組網(wǎng)形式為C/S模式,時間同步報文發(fā)送周期為1s,運用時鐘頻率調(diào)整算法后其結(jié)果如圖6所示 (客戶機,其中:橫坐標表示樣本數(shù)量 [單位:個],縱坐標表示客戶機與服務(wù)器的時間差 [單位以微秒計])。
圖6 調(diào)整時鐘頻率前后所得時間同步效果
本實驗中,我們再把穩(wěn)定的時間差補償?shù)娇蛻魴C的系統(tǒng)時間上。再利用客戶機的絕對系統(tǒng)時間與服務(wù)器做時間同步,并記錄偏差樣本2200個,同步周期分別為1s、2s,得到的時間同步效果如圖7、圖8所示。
由圖6可看出,客戶機與服務(wù)器的時間差在561至564ms之間。在前50個樣本內(nèi),時間差值曲線斜率較大,遞減速度較快,這是由于客戶端時鐘和服務(wù)器時鐘存在一定的頻率誤差所致,而又沒有進行頻率調(diào)整。在50個樣本值后,系統(tǒng)進行了第一次頻率調(diào)整,消除了部分漂移率,可以看到曲線斜率變得平緩一些,但是還是在遞減中。再積累一定時間樣本后,系統(tǒng)進行了第二次調(diào)整,可以看到其后的差值曲線平穩(wěn) (150個樣本后),說明客戶端時鐘和服務(wù)器時鐘頻率幾乎一致,漂移率控制在很小的范圍內(nèi)。
時鐘頻率調(diào)整之后,把穩(wěn)定的時間偏差補償?shù)娇蛻魴C,并調(diào)整系統(tǒng)時間,從圖7可看出,在1s的周期下,服務(wù)器與客戶機的時間偏差均在亞毫秒級 (正/副100μs以內(nèi)),其偏差均值在20μs左右。圖8中,在2s的周期下,服務(wù)器與客戶機的偏差均值比1s周期下稍大,但仍低于50μs,且同樣穩(wěn)定 (正/副100μs以內(nèi))。
常用的基于計數(shù)器的相對時間同步方法,往往在應(yīng)用層獲取系統(tǒng)時間而精度不高,沒有與系統(tǒng)時間建立關(guān)聯(lián),也沒有考慮時鐘頻率漂移的影響。在我們的許多工程應(yīng)用上,由于時統(tǒng)不準確而導(dǎo)致的各種問題層出不窮,如何低成本,高效率的獲取精確時間,這已經(jīng)成為了我們技術(shù)更新升級的瓶頸之一。本文提供的算法,避免了對外部時鐘源的苛刻要求,且系統(tǒng)運行穩(wěn)定可靠,實現(xiàn)也相對簡單。在現(xiàn)代國防工業(yè)中,尤其對于小型艦載系統(tǒng)或者岸基系統(tǒng)內(nèi)部,可使其同步精度達到亞毫秒級,具有很大的現(xiàn)實應(yīng)用價值。
[1]ZHANG Yanjun,LIU Jingyu,GUO Kuo.Clock synchronization algorithm in distributed control systems [J].Industrial Control Computer,2006,19 (5):41-42 (in Chinese). [張彥軍,劉靖宇,郭廓.分布式控制系統(tǒng)的時鐘同步研究 [J].工業(yè)控制計算機,2006,19 (5):41-42.]
[2]CHEN Huajin,LUO Shuangxi,HE Jiazhou.New mechanism of realizing time-synchronization in LAN by using CPU time stamp[J].Journal of Computer Applications,2009,29(11):2920-2924 (in Chinese). [諶華金,羅雙喜,何佳洲.利用CPU時間戳實現(xiàn)局域網(wǎng)時間同步的新機制 [J],計算機應(yīng)用,2009,29 (11):2920-2924.]
[3]CHEN Huajin,HE Jiazhou.New mechanism of realizing timesynchronization in LAN based on data link layer [J].Journal of Computer Applications,2010,30 (5):1183-1187 (in Chinese).[諶華金,何佳洲.一種基于數(shù)據(jù)鏈路層的局域網(wǎng)時間同步新機制 [J].計算機應(yīng)用,2010,30 (5):1183-1187.]
[4]HU Xiaoyuan,SHI Haoshan.Analysis and application of Win-Pcap system [J].Computer Engineering,2005,31 (2):96-98(in Chinese).[胡曉元,史浩山.WinPcap包截獲系統(tǒng)的分析及其應(yīng)用 [J].計算機工程,2005,31 (2):96-98.]
[5]ZHOU Jinling,F(xiàn)AN Bingbing,QIN Jie.The simulation realization of the network protocol experiments based on WinPcap[J].Computer Applications and Software,2007,24 (9):218-221(in Chinese). [周金玲,范冰冰,秦潔.基于 Win-Pcap的網(wǎng)絡(luò)協(xié)議實驗的仿真實現(xiàn) [J].計算機應(yīng)用與軟件,2007,24 (9):218-221.]
[6]WU Liwei,YE Nianyu.The development of device driver under the Windows operation system [J].Computer & Digital Engineering,2007,35 (3):196-198 (in Chinese).[吳力煒,葉念渝.Windows平臺下的設(shè)備驅(qū)動程序開發(fā) [J].計算機與數(shù)字工程,2007,35 (3):196-198.]
[7]Shao Lei,Ray S.Rate-one space-frequency block codes with maximum diversity for MIMO-OFDM [J].IEEE Trans on Wireless Communications,2005,4 (4):1674-1685.
[8]SUN Jimin,SHEN Yulong,PEI Qingqi,et al.Abnormal time synchronization data filter algorithm in sensor networks[J].Journal of Xidian University Natural Science,2008,35(5):911-913 (in Chinese). [孫紀敏,沈玉龍,裴慶祺,等.傳感器網(wǎng)絡(luò)異常時間同步數(shù)據(jù)過濾算法 [J].西安電子科技大學學報,2008,35 (5):911-913.]
[9]QIN Mingwei,YAO Yuancheng,LI Yun.Time synchronization in network time-delay measurement [J].Communications Technology,2008,41 (8):149-150 (in Chinese).[秦明偉,姚遠程,李云.網(wǎng)絡(luò)時延測量中的時間同步系統(tǒng)應(yīng)用研究[J].通信技術(shù),2008,41 (8):149-150.]
[10] WANG Yini.Clock synchronization and stability analysis based on clock drift rate[D].Beijing:Beijing University of Chemical Technology,2008:1-71 (in Chinese). [王旖旎.基于時鐘漂移率的時鐘同步及穩(wěn)定性分析 [D].北京:北京化工大學,2008:1-71.]
[11]Andrew.Tanenbaum.Modern operating systems [M].CHEN Xiangqun,transl.China Machine Press,2005 (in Chinese).[Andrew.Tanenbaum.現(xiàn)代操作系統(tǒng) [M].陳向群,譯.機械工業(yè)出版社,2005.]
[12]ZHAO Ying.Analysis of clock adjusting strategy based on NTP[J].Journal of Chinese Computer Systems,2008,29 (10):1812-1815(in Chinese).[趙英.基于NTP的時鐘調(diào)整策略分析[J].小型微型計算機系統(tǒng),2008,29 (10):1812-1815.]
[13]LIN Guoyuan,XU Feng,HUANG Hao.Improving intrusion detection rate using high precision time stamps [J].Journal of System Simulation,2006,18 (9):2672-2675 (in Chinese).[林果園,許峰,黃皓.利用高精度時間戳提高入侵檢測率 [J].系統(tǒng)仿真學報,2006,18 (9):2672-2675.]
[14]GUO Qisheng,DONG Zhiming,SHAN Jiayuan,et al.Simulation systems [M].Beijing:National Defence Industrial Press,2006(in Chinese). [郭齊勝,董志明,單家元,等.系統(tǒng)仿真 [M].北京:國防工業(yè)出版社,2006.]
[15]TANG Qingmao,CHEN Ping,SHEN Bo.Clock synchronization algorithm in simulation systems [J].Computer Engneering,2009,35 (18):37-39 (in Chinese). [唐慶茂,陳平,沈博.仿真系統(tǒng)中的時鐘同步算法 [J].計算機工程,2009,35 (18):37-39.]