基于模糊二分查找的幀分片算法設計與實現

鄭 昱 洪 偉 蔡曉磊

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

0 引言

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

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

1 幀分片算法

1.1 算法簡介

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

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

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

根據上文可分析得出，當上層數據幀長度大于下層最長有效載荷長度時，需要將上層數據幀分片，切分成下層有效載荷能夠承載的數據長度。考慮數據傳輸的效率，在對上層數據幀進行分片時，分片數量應該越少越好，所以優先考慮使用當前發送參數條件下的最大分片長度對上層數據幀進行分片，當上層數據幀剩余長度不足最大分片長度時，再考慮使用能夠承載上層數據幀剩余長度且最接近的分片長度進行分片。

如何快速地找出當前發送參數條件下能夠承載最后一個分片的最小有效載荷長度是分片算法的關鍵。

1.2 數據結構

1)分片長度表

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

表1 分片長度查找表

分片序號發送參數 12345……發送參數11010101010發送參數2263474106138發送參數34258138202266…………

2)幀結構

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

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

幀序號分片序號有效數據長度更多分片指示

圖1分片幀頭結構

1.3 算法流程

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

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

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

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

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

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

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

1.4 算法性能分析

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

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

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

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

2 分片軟件模塊實現與測試

2.1 模塊實現

依據上文基于模糊二分查找的分片算法，實現標準C語言軟件模塊[5]，該模塊具有以下特點：

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

2)分片長度可根據下層需求進行動態調整；

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

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

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

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

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

1)開始，更新幀序號，確定當前數據的幀序號，并進入步驟2；

2)初始化數據分片的幀頭，填入當前數據的幀序號，并進入步驟3；

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

4)初始化循環計數變量i為0，并進入步驟5；

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

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

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

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

9)將發送緩沖區中的分片數據發送出去，并進入步驟10；

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

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

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

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

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

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

16)將發送緩沖區中的分片數據發送出去，結束分片處理。

2.2 模塊測試

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

測試方法步驟如下：

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

2)調用分片函數對其進行分片，并在每片分片結束后調用模擬傳輸函數模擬數據傳輸的過程；

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

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

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

3 結束語

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