基于模糊二分查找的幀分片算法設(shè)計與實現(xiàn)

鄭 昱 洪 偉 蔡曉磊

(西安電子工程研究所 西安 710100)

0 引言

為了降低網(wǎng)絡(luò)設(shè)計的復(fù)雜性，絕大多數(shù)網(wǎng)絡(luò)通信系統(tǒng)都由多個協(xié)議層構(gòu)成一個整體的協(xié)議棧，例如常見的TCP/IP協(xié)議棧由應(yīng)用層、傳輸層、網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層和物理層組成[1]。各層之間具有數(shù)據(jù)交互，上層的數(shù)據(jù)幀作為下層數(shù)據(jù)幀的有效載荷進行分裝處理。各層數(shù)據(jù)幀的有效載荷通常具有最大長度上限，所以經(jīng)常會出現(xiàn)下層數(shù)據(jù)幀的最大有效載荷比上層數(shù)據(jù)幀長度更小的情況，這時為了下層數(shù)據(jù)幀能夠承載上層數(shù)據(jù)幀進行有效傳輸，則需要對上層數(shù)據(jù)幀進行分片處理，并在接收端對分片進行聚合處理，恢復(fù)原先的上層數(shù)據(jù)幀[2]。

對數(shù)據(jù)幀進行分片處理需要耗費處理時間，如何設(shè)計一種性能優(yōu)越的幀分片處理算法，對減小協(xié)議開銷，提高數(shù)據(jù)吞吐量，降低系統(tǒng)實現(xiàn)難度具有重要意義。本文設(shè)計了一種高效的幀分片算法，并基于C語言對其進行了實現(xiàn)。

1 幀分片算法

1.1 算法簡介

下層數(shù)據(jù)幀最典型的為物理層幀，常見物理層數(shù)據(jù)幀的有效載荷長度具有以下兩個特點：

1)最大有效載荷長度會根據(jù)下層某些動態(tài)變化的發(fā)送參數(shù)(例如調(diào)制編碼方式等)而動態(tài)改變，即不同發(fā)送參數(shù)具有不同的最大有效載荷長度。

2)在同一發(fā)送參數(shù)的情況下，最大有效載荷的長度范圍內(nèi)，不可隨意選擇載荷長度，只有若干大小不一的固定載荷長度可選。

根據(jù)上文可分析得出，當(dāng)上層數(shù)據(jù)幀長度大于下層最長有效載荷長度時，需要將上層數(shù)據(jù)幀分片，切分成下層有效載荷能夠承載的數(shù)據(jù)長度。考慮數(shù)據(jù)傳輸?shù)男剩趯ι蠈訑?shù)據(jù)幀進行分片時，分片數(shù)量應(yīng)該越少越好，所以優(yōu)先考慮使用當(dāng)前發(fā)送參數(shù)條件下的最大分片長度對上層數(shù)據(jù)幀進行分片，當(dāng)上層數(shù)據(jù)幀剩余長度不足最大分片長度時，再考慮使用能夠承載上層數(shù)據(jù)幀剩余長度且最接近的分片長度進行分片。

如何快速地找出當(dāng)前發(fā)送參數(shù)條件下能夠承載最后一個分片的最小有效載荷長度是分片算法的關(guān)鍵。

1.2 數(shù)據(jù)結(jié)構(gòu)

1)分片長度表

分片長度查找表是用于存儲不同發(fā)送參數(shù)條件下的不同可用分片長度，可用分片長度即下層幀有效載荷長度，根據(jù)上文介紹的有效載荷長度的兩個特點，分片依據(jù)發(fā)送參數(shù)的不同具有若干大小不一的分片長度。因此，分片長度查找表為二維查找表，如表1所示，其中縱坐標(biāo)為發(fā)送參數(shù)，橫坐標(biāo)為分片序號，表中以升序的方式對同一發(fā)送參數(shù)的不同可用分片長度進行排序。

表1 分片長度查找表

分片序號發(fā)送參數(shù) 12345……發(fā)送參數(shù)11010101010發(fā)送參數(shù)2263474106138發(fā)送參數(shù)34258138202266…………

2)幀結(jié)構(gòu)

幀的分片傳輸至接收端后需要重新聚合成為完整的一個上層數(shù)據(jù)幀，這就需要接收端能夠區(qū)分各個分片屬于哪個上層數(shù)據(jù)幀，分片的有效數(shù)據(jù)長度，以及判別分片的順序，因此在下層數(shù)據(jù)幀的幀頭中需要使用序號域、有效數(shù)據(jù)長度和更多分片指示，如圖1所示。

其中，序號域又由幀序號子域和分片序號子域組成，幀序號子域用于區(qū)別分片屬于哪一個上層數(shù)據(jù)幀，分片序號子域用于區(qū)分分片在同一上層數(shù)據(jù)幀的順序；由于分片中承載的上層數(shù)據(jù)幀的有效數(shù)據(jù)長度不一定與分片長度相一致，所以需要使用有效數(shù)據(jù)長度來說明該分片中承載的上層數(shù)據(jù)幀有效數(shù)據(jù)長度數(shù)值；更多分片指示用于接收端判斷該分片是否為最后一個分片。

幀序號分片序號有效數(shù)據(jù)長度更多分片指示

圖1分片幀頭結(jié)構(gòu)

1.3 算法流程

如前文所述，幀分片算法的關(guān)鍵在于快速地在分片長度查找表中找出當(dāng)前發(fā)送參數(shù)條件下最合適的最后一個分片長度。常見的表查找方法有順序查找、二分查找、塊查找等，考慮到分片長度查找表為有序表，對于順序表而言二分查找的性能是最優(yōu)的[3]，所以采用二分查找的方式查找合適分片長度最為合適。但是，普通的二分查找算法基本都是精確查找算法，即精確地查找出表中與關(guān)鍵字相等的元素。而數(shù)據(jù)分片時是查找能夠承載上層數(shù)據(jù)幀剩余長度且最接近的分片長度，這個分片長度可能與數(shù)據(jù)幀剩余長度相等，也可能比數(shù)據(jù)幀剩余長度更長，所以普通的二分查找算法并不適用于數(shù)據(jù)分片處理，本文對常用二分查找算法進行相應(yīng)的改進，形成一種模糊查找的二分查找算法，用于分片長度的查找和選擇。

具體算法步驟如圖2所示：

1)首先，假設(shè)當(dāng)前分片長度查找表中的分片長度是按照升序的方式進行排列，將表中間位置作為當(dāng)前查找位置，當(dāng)前查找的分片長度與數(shù)據(jù)幀剩余長度進行比較，如果兩者相等，則查找成功，當(dāng)前位置記錄的分片長度即是所需的分片長度，如果不相等，則進入步驟2；

2)否則，再判斷該分片長度是否大于數(shù)據(jù)幀剩余長度，如果是，則進入步驟3，如果否，則進入步驟5；

3)判斷當(dāng)前查找位置是否為表首位置，如果是，則查找成功，當(dāng)前位置記錄的分片長度即是所需的分片長度，如果否，則進入步驟4；

4)判斷當(dāng)前查找位置之前的一個元素的分片長度是否小于數(shù)據(jù)幀剩余長度，如果是，則查找成功，當(dāng)前位置記錄的分片長度即是所需的分片長度，如果否，則將當(dāng)前查找位置之前的各元素作為一個子表，回到步驟1進行進一步遞歸查找；

5)將當(dāng)前查找位置之后的各元素作為一個子表，回到步驟1進一步遞歸查找。

1.4 算法性能分析

在分片長度查找表中查找最合適的分片長度時，最為常用的查找方法為順序查找，這里通過與順序查找方法進行對比，來分析模糊二分查找算法的算法性能。

普通二分查找的算法過程可以對應(yīng)一棵有n個結(jié)點的二叉樹[4]，假設(shè)該二叉樹是一個滿二叉樹，則對應(yīng)的最多比較次數(shù)為log2(n+1)，所以平均查找長度為log2(n+1)-1。

模擬二分查找與普通二分查找的最大區(qū)別在于每次從查找表查找的分片長度是否適合的判斷標(biāo)準(zhǔn)不僅僅是與數(shù)據(jù)長度是否相等，還可以是大于數(shù)據(jù)長度的最小分片長度。僅僅是每次比較時與普通二分查找算法的判斷標(biāo)準(zhǔn)不同，并不增加平均查找長度，因此與普通二分查找的時間復(fù)雜度一致，仍為O(log2n)。

由以上分析得知，模糊二分查找算法的平均查找長度和時間復(fù)雜度都優(yōu)于常用的順序查找算法。

2 分片軟件模塊實現(xiàn)與測試

2.1 模塊實現(xiàn)

依據(jù)上文基于模糊二分查找的分片算法，實現(xiàn)標(biāo)準(zhǔn)C語言軟件模塊[5]，該模塊具有以下特點：

1)分片參數(shù)可靈活配置；

2)分片長度可根據(jù)下層需求進行動態(tài)調(diào)整；

3)對于常規(guī)的各類數(shù)據(jù)傳輸過程中分片和聚合處理具有普適性，稍作更改就可以應(yīng)用于各種數(shù)據(jù)幀分片聚合系統(tǒng)。

分片模塊設(shè)計主要包含以下兩個處理部分：

1)以最大分片長度對數(shù)據(jù)進行分片：按照當(dāng)前發(fā)送參數(shù)條件下最長分片長度對數(shù)據(jù)進行分片，將數(shù)據(jù)長度除以最長分片長度，計算出以最長分片長度進行分片的分片個數(shù)，對分片進行組幀并傳輸分片；

2)查找最后一個分片的分片長度，并對數(shù)據(jù)進行分片：使用基于模糊查找的二分查找算法查找最后一個分片的分片長度，對最后一個分片進行組幀并傳輸分片。

具體流程如圖3所示，具有以下16個步驟：

1)開始，更新幀序號，確定當(dāng)前數(shù)據(jù)的幀序號，并進入步驟2；

2)初始化數(shù)據(jù)分片的幀頭，填入當(dāng)前數(shù)據(jù)的幀序號，并進入步驟3；

3)將數(shù)據(jù)長度除以當(dāng)前發(fā)送參數(shù)條件下的最長分片長度，得到以最長分片長度進行分片的分片個數(shù)max_frag_cnt，并進入步驟4；

4)初始化循環(huán)計數(shù)變量i為0，并進入步驟5；

5)判斷i是否小于max_frag_cnt，如果是，則進入步驟6，否則進入步驟10；

6)更新分片序號，將分片序號填入分片幀頭的分片序號子域，設(shè)置分片幀頭中的更多分片標(biāo)識為1，并進入步驟7；

7)計算分片中有效數(shù)據(jù)載荷的長度，將長度值填入分片幀頭的有效數(shù)據(jù)長度域，并進入步驟8；

8)將分片幀頭部分拷貝至發(fā)送緩沖區(qū)，接著將數(shù)據(jù)中需要填入分片載荷的部分拷貝至發(fā)送緩沖區(qū)，更新偏移量，并進入步驟9；

9)將發(fā)送緩沖區(qū)中的分片數(shù)據(jù)發(fā)送出去，并進入步驟10；

10)獲取以最大分片長度進行分片后剩余的數(shù)據(jù)長度，并進入步驟11；

11)判斷剩余的數(shù)據(jù)長度是否大于0，如果是，則進入步驟12，否則結(jié)束分片處理；

12)調(diào)用get_last_frag_len函數(shù)，使用基于模糊查找的二分查找算法，在分片長度查找表中查找出合適的分片長度，作為最后一個分片的分片長度(具體算法流程參照1.3節(jié))，并進入步驟13；

13)更新分片序號，將分片序號填入分片幀頭的分片序號子域，設(shè)置分片幀頭中的更多分片標(biāo)識為0，并進入步驟14；

14)計算分片中有效數(shù)據(jù)載荷的長度，將長度值填入分片幀頭的有效數(shù)據(jù)長度域，并進入步驟15；

15)將分片幀頭部分拷貝至發(fā)送緩沖區(qū)，接著將數(shù)據(jù)中需要填入分片載荷的部分拷貝至發(fā)送緩沖區(qū)，更新偏移量，并進入步驟16；

16)將發(fā)送緩沖區(qū)中的分片數(shù)據(jù)發(fā)送出去，結(jié)束分片處理。

2.2 模塊測試

該軟件模塊主要實現(xiàn)對數(shù)據(jù)包的分片功能，軟件具有極強的通用性，通過修改軟件接口、全局變量/常量和宏定義的數(shù)值即可適配各種數(shù)據(jù)傳輸軟硬件系統(tǒng)中。因此，在對該軟件模塊進行測試時，為了增強測試過程的可靠性和測試結(jié)果的真實性，降低測試的實現(xiàn)難度，避免傳輸過程中不可預(yù)期的數(shù)據(jù)錯誤，采用在單機條件下軟件模擬數(shù)據(jù)傳輸過程的方式對其進行測試。這種測試方式，可以模擬數(shù)據(jù)正確或者錯誤傳輸?shù)倪^程，且不受除軟件模塊以外的軟硬件因素的影響。

測試方法步驟如下：

1)首先定義各種宏定義、全局變量和常量，并初始化分片查找表；其次通過軟件生成一個一定長度帶奇偶校驗的數(shù)據(jù)幀；

2)調(diào)用分片函數(shù)對其進行分片，并在每片分片結(jié)束后調(diào)用模擬傳輸函數(shù)模擬數(shù)據(jù)傳輸?shù)倪^程；

3)在模擬傳輸函數(shù)中調(diào)用對各個分片進行聚合，直到得到聚合后的數(shù)據(jù)，對聚合后的數(shù)據(jù)進行奇偶校驗驗證分片聚合過程的正確性。

如圖4所示，數(shù)據(jù)分片長度為1200字節(jié)，通過分片模塊對其進行分片，此時發(fā)送參數(shù)為0，一共分為3個分片，分片長度分別為405字節(jié)、405字節(jié)和390字節(jié)，再將三個分片進行聚合，最后得到的聚合后數(shù)據(jù)長度也為1200字節(jié)，且數(shù)據(jù)校驗和與原數(shù)據(jù)一致，說明數(shù)據(jù)分片聚合成功且正確。

以上步驟為正常處理過程，還能通過在模擬傳輸函數(shù)中添加條件判斷語句，使得某些分片傳輸錯誤，驗證和測試聚合函數(shù)對數(shù)據(jù)包丟失的異常處理能力。

3 結(jié)束語

網(wǎng)絡(luò)通信系統(tǒng)中經(jīng)常需要對數(shù)據(jù)進行分片聚合處理，因此良好的分片算法能夠有效提升整個網(wǎng)絡(luò)系統(tǒng)的性能。本文根據(jù)常見網(wǎng)絡(luò)通信系統(tǒng)物理層的分片需求，提出了一種基于模糊二分查找的幀分片算法，并基于C語言對其進行了實現(xiàn)，并在最后對其進行了相應(yīng)的模擬測試。該分片算法在各類網(wǎng)絡(luò)通信系統(tǒng)數(shù)據(jù)分片過程中都具有良好的應(yīng)用前景。