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

鄭 昱 洪 偉 蔡曉磊

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

0 引言

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

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

1 幀分片算法

1.1 算法簡(jiǎn)介

下層數(shù)據(jù)幀最典型的為物理層幀，常見(jiàn)物理層數(shù)據(jù)幀的有效載荷長(zhǎng)度具有以下兩個(gè)特點(diǎn)：

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

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

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

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

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

1)分片長(zhǎng)度表

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

表1 分片長(zhǎng)度查找表

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

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

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

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

幀序號(hào)分片序號(hào)有效數(shù)據(jù)長(zhǎng)度更多分片指示

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

1.3 算法流程

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

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

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

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

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

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

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

1.4 算法性能分析

在分片長(zhǎng)度查找表中查找最合適的分片長(zhǎng)度時(shí)，最為常用的查找方法為順序查找，這里通過(guò)與順序查找方法進(jìn)行對(duì)比，來(lái)分析模糊二分查找算法的算法性能。

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

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

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

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

2.1 模塊實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 模塊測(cè)試

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

測(cè)試方法步驟如下：

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

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

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

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

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

3 結(jié)束語(yǔ)

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