基于Rsync算法的增量網(wǎng)絡編程

許 宏

(淮陰工學院，江蘇淮安223003)

0 引言

隨著智能終端在各個領域的廣泛應用，智能終端軟件的維護變得日益重要。因此，智能終端軟件的更新逐漸成為智能終端實際應用的一個重要問題。當智能終端安裝數(shù)量較多，或安裝位置不方便的情況下，采用人工更新方式會花費較大的人力和物力。

網(wǎng)絡及通信技術的飛速發(fā)展，Internet越來越普及到人們的日常生活中，人們對Internet的需求也越來越大，Internet所帶來的好處也越來越得到體現(xiàn)，使許多的信息家電、智能儀表等非PC智能終端接入到互聯(lián)網(wǎng)成為可能，從而實現(xiàn)網(wǎng)絡化、智能化的集中管理。智能終端投入實際環(huán)境中運行后，一部分在軟件開發(fā)過程中無法充分測試的錯誤便會暴露出來;在智能終端的運行期內(nèi)，用戶也往往會對智能終端軟件提出新的功能要求和性能要求。增量網(wǎng)絡編程可以通過遠程通信的方式實現(xiàn)智能的自動更新，有效降低了更新和維護成本。

1 增量網(wǎng)絡編程原理

增量網(wǎng)絡編程主要分為三個步驟:編碼、分發(fā)和解碼。在編碼階段，主控系統(tǒng)只讀入程序代碼并將每一行都保存在一個隊列中，并準備分發(fā)的代碼包［1］。

在分發(fā)階段，主控系統(tǒng)將程序代碼以數(shù)據(jù)包的格式發(fā)送，智能終端將接收到的數(shù)據(jù)包存放在外部閃存中。由于網(wǎng)絡編程模塊以用戶級別運行，無法直接將程序代碼寫入程序存儲區(qū)，所以將其存放在外部閃存，同時智能終端請求主控系統(tǒng)重新傳送丟失的數(shù)據(jù)包。

寫入到外部閃存的代碼包與初始的程序代碼具有相同的格式，在解碼階段，智能終端只要驗證程序映像并調(diào)用BootLoader將程序代碼保存在程序存儲區(qū)。BootLoader是在系統(tǒng)內(nèi)核運行之前運行的一段小程序。通過這段小程序，可以初始化硬件設備、建立內(nèi)存空間的映射圖，從而將系統(tǒng)的軟硬件環(huán)境帶到一個合適的狀態(tài)，以便為最終調(diào)用系統(tǒng)內(nèi)核準備好正確的環(huán)境。BootLoader具有向程序存儲區(qū)的用戶應用程序部分寫入數(shù)據(jù)的權限。然后重新啟動系統(tǒng)，執(zhí)行最新建立的應用程序。

圖1 增量網(wǎng)絡編程過程

為了設計一個增量網(wǎng)絡程序編程機制，需要考慮許多影響系統(tǒng)性能的因素。由于網(wǎng)絡編程時間與更新的數(shù)據(jù)量成正比，同時數(shù)據(jù)量也決定了傳輸數(shù)據(jù)的網(wǎng)絡成本，因此盡可能地降低更新的數(shù)據(jù)量可以縮短網(wǎng)絡編程的時間，降低使用成本。程序代碼存儲在外部閃存，而外部閃存的訪問速度要遠遠低于片上存儲器，為了獲得更好的性能，應該盡可能減少訪問外部閃存。由于智能終端的處理能力有限，應該將大部分處理放在主控系統(tǒng)執(zhí)行，而智能終端只處理最基本的操作［2］。

在外部閃存中，劃分兩塊存儲區(qū)域，一塊用于以前的程序映像，另一塊用于存儲將要建立的新映像(圖2)。其優(yōu)點在于可以提供相同的內(nèi)存映射并最小限度的影響B(tài)ootLoader代碼的重寫。通過對BootLoader的修改，使其可以從由網(wǎng)絡編程模塊傳遞的基地址處讀取程序代碼。

圖2 存儲器組織結構

2 基于Rsync算法的增量網(wǎng)絡編程

2.1 增量代碼的產(chǎn)生

對于增量網(wǎng)絡編程，通常使用的方法為:主控系統(tǒng)將程序映像文件分割為尺寸固定的塊，并比較以前版本和最新版本相應的塊來獲得改變的程序塊(圖3)，將其稱為固定塊比較。當程序代碼映像移位時，固定塊比較無法找到相同的程序塊，因而該方法的效率不高。為此，采用Rsync算法［3］來產(chǎn)生增量并重建代碼映像。Rsync算法最初主要用于通過低帶寬網(wǎng)絡在兩個設備間進行二進制代碼的更新。

圖3 通過固定塊比較產(chǎn)生增量代碼

Rsync算法可以找出最新版本程序中哪些部分和原有程序中某個部分匹配，這部分的內(nèi)容就不需要通過網(wǎng)絡傳輸，需要的只是對原有程序相應部分的引用，而新程序中無法匹配的部分就只能逐字傳輸。智能終端根據(jù)對原有程序的部分引用和逐字傳輸?shù)膬?nèi)容來構造出新程序的一個副本。假設主控系統(tǒng)α的最新版本程序為Fnew，智能終端β的原有程序為Fold，算法的步驟為:

(1)智能終端β將文件Fold分成互不重疊、尺寸固定的一系列數(shù)據(jù)塊，塊的尺寸為S字節(jié)，S∈［500，1000］，最后一個數(shù)據(jù)塊可能少于S字節(jié);

(2)智能終端β計算所有數(shù)據(jù)塊的校驗和:32位的滾動弱檢驗和Ri以及128位的MD4強檢驗和Mi，記為hi＜Ri，Mi＞。建立哈希表，對于每一對校驗值，以滾動校驗和為關鍵值進行哈希排序，并將哈希表傳送給主控系統(tǒng)α;

(3)主控系統(tǒng)α在文件Fnew中為所有長度為S字節(jié)的數(shù)據(jù)塊(這些數(shù)據(jù)塊對于文件頭的位移量可以是任意的，不只是S的倍數(shù))計算滾動校驗和并與哈希表中的hi＜Ri，Mi＞中的Ri比較，發(fā)現(xiàn)與Ri相匹配的數(shù)據(jù)塊，再計算其強校驗和與Mi比較，如果強校驗和相等，說明這兩個數(shù)據(jù)塊相同，記錄該數(shù)據(jù)塊的索引，即hash指示值，繼續(xù)比較下一個數(shù)據(jù)塊;如果不相等，說明這兩個數(shù)據(jù)塊不同，則記錄該數(shù)據(jù)塊第一個字節(jié)，然后向后移動一個偏移量，繼續(xù)比較，直到文件末尾;

(4)比較完成后，智能終端β收到主控系統(tǒng)α包含差異內(nèi)容和hash指示值的數(shù)據(jù)流，更新Fold，生成Fnew。

Rsync算法在新文件上進行滑動查找，移動一個字節(jié)或一個塊長。它能實現(xiàn)快速查找，很大部分要歸功于采用了滾動校驗和。

圖4 差異增量的產(chǎn)生

2.2 智能終端程序的重構

為了實現(xiàn)智能終端程序的更新，主控系統(tǒng)一般采用兩種操作來描述差異:Copy(CMD_COPY_BLOCK)和Download(CMD_DOWNLOAD_BLOCK)。在增量更新中，主控系統(tǒng)給每個匹配的模塊發(fā)送Copy報文，當智能終端接收后，就將該數(shù)據(jù)塊從原有的映像中復制到當前的映像［4］。對每個不匹配的模塊，主控系統(tǒng)發(fā)送一個或多個下載報文。

每個復制報文的數(shù)據(jù)尺寸為SREC行尺寸的倍數(shù)，而下載報文的數(shù)據(jù)尺寸為任意數(shù)值。當下載報文的尺寸大于一個SREC行(16字節(jié))時，主控系統(tǒng)將其分為多個片段。

如果程序的結構沒有改變時，程序映像的重構比較簡單。智能終端只需要寫入下載模塊及執(zhí)行復制操作。當程序映像發(fā)生偏移時，情況就會變得復雜。假設模塊從原有的映像中偏移了k位，并且k不是SREC行的整數(shù)倍［5］。這就導致數(shù)據(jù)塊橫跨兩個SREC行，需要兩次SREC行寫入。為此可以采取下面的方法來解決:

當下載的數(shù)據(jù)塊小于SREC行時，智能終端按照一行SREC寫入，而不填充其他的數(shù)據(jù)。這時，將SREC行的尺寸設為實際的數(shù)據(jù)長度(圖5)。復制數(shù)據(jù)塊時，從SREC行的起始位置進行復制。這樣可以確保將每行數(shù)據(jù)塊復制到一個SREC行，同時將SREC行的SREC地址域改為在新映像中的偏移地址。

為能實現(xiàn)智能終端程序的自動更新，我們對Rsync算法進行了改進，當智能終端收到一個復制消息時，網(wǎng)絡編程模塊立即編譯執(zhí)行，無須將其放入隊列中。由于沒有保存腳本命令，所以當有消息丟失時，網(wǎng)絡編程模塊必須檢查重構的程序映像。因為不知道丟失的復制或下載消息是否導致丟失錯誤，所以每次丟失記錄都要發(fā)送重傳請求，而這將額外花費大量的時間。

為此，在智能終端中，將所有的腳本命令保存在隊列中，并檢查所有包含腳本命令的數(shù)據(jù)包是否丟失，當智能終端接收到解碼消息后，就對腳本信息進行解碼。

圖5 新程序映像重構

2.3 改進的Rsync算法

為了發(fā)送腳本命令，主控系統(tǒng)將每個腳本命令嵌入到CMD_DOWNLOADING消息中，而嵌入消息保存在外部閃存中，CID代表在腳本隊列中，SREC行的數(shù)量。為了使復制腳本與其他消息類型區(qū)別，在 SREC類型域使用了特殊數(shù)值。在SREC規(guī)定中，該域只允許使用幾個數(shù)值(0，1，2，3，5，7，8和9)，在這里使用10來代表一個嵌入的復制消息。這樣既可以使其具有與其他類型的數(shù)據(jù)相同的存儲方式，又能夠確保正確的解釋復制命令。

圖6 CMD_DOWNLOADING格式

由于外部閃存有足夠的空間，使用外部閃存來存儲腳本命令，為此，將外部閃存分為三個部分:以前程序映像、新程序映像及腳本隊列。

主控系統(tǒng)以“下載”(CMD_DOWNLOADING)消息發(fā)送腳本，智能終端將這些腳本保存在腳本隊列中。當主控系統(tǒng)查詢?nèi)魏蝸G失腳本命令時，智能終端掃描該腳本隊列。如果智能終端發(fā)現(xiàn)丟失記錄，則請求重新發(fā)送。主控系統(tǒng)響應該請求，重新發(fā)送丟失的信息。智能終端接收到解碼命令后，開始對腳本進行解碼，分別將嵌入在腳本命令中的下載或復制命令提取出來，并對命令進行相應的解釋(圖7)。

3 實驗結果分析

在實驗環(huán)境下，綜合各方面的因素，按照前面設計的算法，實現(xiàn)了增量更新系統(tǒng)。實驗時，一個主控端同時對三個智能終端進行更新，結果表明改進后的增量網(wǎng)絡編程，通過Rsync算法產(chǎn)生兩個程序的映像差異，再將差異部分傳輸給智能終端，達到快速地對智能終端編程的目的。以遠程通信的方式實現(xiàn)智能的自動更新。

圖7 解碼腳本命令

4 結束語

本文以智能終端的增量網(wǎng)絡編程為基礎，對Rsync算法進行了改進，實現(xiàn)智能終端的自動更新，而且改進后的算法沒有涉及任何具體的程序代碼，具有很好的移植性。

［1］Linda Wills.An open platform for recongurable control.IEEE Control Systems Magazine［J］.2001(6):34 －36.

［2］Rahul Kapur，Tom Yeh，Ujjwal Lahoti.Differential Wireless Reprogramming of Sensor Networks［J］.UCLA CS213 Project Report，2003(12):23 －25.

［3］Andrew Tridgell.Efficient Algorithms for Sorting and Synchronization［D］.Canberra:Australian National University，1999.

［4］Adam Chlipala，Jonathan Hui，Gilman Tolle.Deluge:Data Dissemination in Multi－ Hop Sensor Networks［J］.UC Berkeley CS294 －1 Project Report，2003(12):5 －9.

［5］SOURCE A.SANs sharing storage to infinity and beyond［J］.Electronic Design，2004，52(9):16 － 19.

［6］全勇，楊杰，鄧志鵬.基于增量余弦RBF網(wǎng)絡的慣性導航初始對準［J］.上海交通大學學報，2002，36(12):35－38.