依據散列查找的分布式網絡數據分流算法

梁鑫龍，徐永貴，史 君

（淄博師范高等?？茖W校信息系，山東 淄博 255100）

近年來，在各項先進技術的大力推動下，互聯網規模和應用數據量呈直線上升趨勢， 越來越多的應用需要借助分布式網絡實現快速且精準的數據分流。例如，在通過路由器轉發網絡數據時， 需要在較短時間內快速找出分布式數據中的路由表，確保數據可以實現精準分流?？梢?，針對數據分流展開研究是十分必要的?，F階段，針對分布式網絡中的數據分流，一般使用專門的分流裝置，按照分流策略，將大流量網絡中的數據分成幾個小流量的數據。 但是，當前的分流算法有兩大問題，一是數據的完整性問題，二是負載平衡問題。

對此， 本文提出基于散列查找的分布式網絡數據分流算法。通過對網絡數據進行特征提取，根據數據不同的特性，將其劃分為多種不同的種類；通過不斷更新數據聚類中心，使數據具有高度動態變化特征，實現數據的分流處理。將本文方法與其他方法進行對比，結果表明，本文方法具有最佳的數據分流處理效果。

1 分布式網絡數據分流描述

1.1 “流”的局部性定義

“流” 可以被理解為具有相同目的和地址的數據包，顧名思義，分流［1-2］就是將具有相同地址和目的的數據包劃分為多個不同的流。 在網絡環境下，FTP （文件傳輸協議）文件和WEB（全球廣域網）界面［3］以及其他協議等具有相同的地址，需要對其分流后再傳輸。一旦FTP 文件首次發送成功， 那么在一定的時間范圍內，其他分組在同一數據流中的成功傳遞概率［4］將會顯著提高。這種現象稱為流的局部性特征，示意圖如圖1 所示。

圖1 “流”的局部性特征示意圖

1.2 分布式網絡數據分流約束條件

式中，w表示分布式網絡的大小，x表示網絡節點通道，b表示嵌入維數最小值。

對分布式網絡數據做歸一化處理［6］，得到

將數據分流問題近似地看作是具有約束特征的非線性問題，那么可得

通過上述計算， 可以得到數據分流的對偶函數［7］表達式

式中，α表示網絡節點的約束條件［8］。

式（4）的約束特性為

在高維空間中，通過式（5）的約束，計算對偶函數的二次函數，表達式為

1.3 能量消耗模型

當網絡節點發送和接收相同數量的數據時， 能耗計算公式為

式中，l表示分布式網絡節點接收和發送的數據總量。

對于接收數據的源節點來說， 由于其包含頭部信息，使得第k個獲取數據的源節點能量消耗為

式中，表示源節點接收數據的能耗，、分別表示數據量的大小。

將源節點接收的數據做壓縮處理后再進行傳輸分流，這個過程能耗計算公式為

通過上述分析計算可知， 分布式網絡數據傳輸分流能耗與數據量大小有著直接關系，數據量越大，傳輸和分流數據所產生的能耗就越高。

2 基于散列查找的分布式網絡數據分流實現

將同一個流中完成分流的數據進行緩存， 緩存可以減少算法計算時間，減少散列表的查找步驟，提高算法整體的運算效率。 散列查找中“流”的局部性原理［9］如圖2 所示。

圖2 散列查找中“流”的局部性原理圖

2.1 分布式網絡數據特征提取

完成對分布式網絡數據的能耗分析后， 從空間重建觀點出發，利用非線性映射方法［10］，建立數據分流過程的時間序列信息模型。利用指標數據的映射方法，建立一個具有高維映射矢量的非線性模型， 并對其進行分析，得出最優解和最大延遲特性，從而實現對網絡數據的特征提取。

式中，t0表示數據采集初始時刻， ?t表示數據采集間隔時間段，表示所有網絡數據在同一時間序列下的相似性特征度，?n表示數據相關性系數。

式中，si表示映射向量分量，g表示數據時間序列系數值。

構建分布式網絡數據目標查找函數， 將R定義為分流過程中數據特征矢量的關聯函數［12］，ug為數據交叉分布模型，用公式表示為

式中，a0表示網絡數據原始采樣幅值，ua?1表示分布式網絡數據均值與方差完全相同的標量序列，bi表示最佳分裂屬性。

接下來利用C均值聚類算法對目標函數進行求解，假設μik是目標函數的聚類最大值，表達式為

通過式（13）得到數據時延特征ξi，至此完成分布式網絡數據的特征提取。 計算過程為

2.2 分布式網絡數據分流實現

對分布式網絡數據的特征提取后， 根據數據自身特性的不同， 劃分為不同的種類， 完成數據的分流處理。 分流的第一步是確定分布式網絡數據的原始聚類中心，在分流過程中不斷更新該中心的內容，以此滿足環境變化帶來的數據高度動態變化特征。

用d表示網絡數據的初始聚類中心，將v定義為初始特征數量， 選出其中的κ個特征作為初始聚類核心Si，每個Si代表一種數據類型。 通過對數據特征的分析和計算后，得到v?κ個數據特征與Si之間的目標距離。 然后，將數據特征劃分到不同的聚類核心中，實現數據特征點的匹配。

通過上述描述將網絡數據特征區劃分為κ個不同特征

其中，zi表示分布式網絡數據特性，表示Si的均值化結果，DF表示網絡數據特征區劃分形式總數的類型特征。在分布式網絡數據分流的過程中，通過對數據特征分析和計算，將數據劃分為不同的類型，并根據特征點匹配的結果進行數據分流［13］，以達到提高數據處理效率和實現優化的目的。

將網絡數據特征區劃分為κ種特征后，數據特性集合為T j(j=1,2, …,κ)，簡化表示為T={DF}。 經過重復迭代計算后，確定分布式網絡數據的分流過程。

步驟一：確定分布式網絡數據的原始聚類中心d，將其劃分為κ個子聚類中心，劃分過程需在滿足

的基礎上進行。

步驟二：對數據特性做循環迭代計算，得到新的數據特征集合TFi+1。

步驟三：當g=0時，聚類中心為TF0。

步驟四：在此基礎上，分析數據分流過程中的誤差和方差。 當方差滿足預先設定的值后，停止計算，輸出結果即為最終的分流結果。

網絡數據的聚類中心不斷更新變化，可以更好地適應互聯網環境下的數據動態變化特性［14］，得到最佳分流函數

綜上所述， 基于散列查找的分布式網絡數據分流過程如圖3 所示。

圖3 基于散列查找的分布式網絡數據分流過程

3 仿真實驗

為了驗證本文方法在實際應用中是否同樣有效，與馬爾科夫決策過程和數據分區算法展開對比仿真實驗。實驗中，數據集選用的是Kddcup99 數據集，其中包含了實驗所需要的高速網絡流量數據。

3.1 所提方法性能測試

為了驗證所提方法在網絡數據分流方面的性能，以網絡擁塞率為指標對其進行測試，結果如圖4 所示。

圖4 所提方法平均時延結果

從圖4 中可以看出， 所提方法擁塞率始終都保持在較低的水平， 可保證數據分流時具有較高的傳輸效率。這是由于所提方法對數據進行聚類劃分，根據數據特性的不同將其劃分到不同的聚類中心中， 結合最佳分流函數， 即可保證數據在分流過程中避免出現擁塞的情況。

3.2 3 種算法負載平衡效果對比

計算機負載平衡效果可以通過計算丟包率與網絡數據流量得到。 3 種算法負載平衡效果如圖5 所示。

圖5 3 種算法負載平衡效果對比結果

通過觀察圖5 可以很明顯地看出： 在3 種算法中，本文方法的丟包率最低，且曲線整體波動較為平緩。 反觀其他兩種方法，丟包率相對較高，而且曲線波動幅度較大。

3.3 3 種算法分流效率對比

分流效率OEο就是分流得到的網絡數據流量與數據總流量之間的比率，計算公式為

分流效率可以更加清晰地反映分流算法的性能優劣。 分流效率值越接近100%，算法的分流性能就越優秀。 3 種算法分流效率對比結果如圖6 所示。

圖6 3 種算法分流效率對比結果

從圖6 中可以看出：隨著網絡數據流量的不斷增加，3 種算法展現出了不同的分流效率； 本文方法取得的分流效率最接近100%，數據分區算法次之，馬爾科夫決策過程最低。這是由于本文方法對網絡數據進行特征提取后， 通過映射的方式建立了非線性數據分流模型，在一定程度上提高了算法的分流效率。

4 結論

傳統算法在對網絡數據分流時常常存在分流效率低、耗時長、負載不平衡等情況，基于此，本文提出了基于散列查找的分布式網絡數據分流算法。對網絡數據分流能耗計算后，對散列查找中“流”的局域性展開分析；建立網絡數據分流的目標函數，通過求解計算后完成數據的特征提??；將數據特征區劃分為不同的類型，通過計算數據特性誤差方差完成數據分流。 仿真實驗結果表明，本文方法取得了最佳負載平衡效果和較高分流效率。