IP地址聚合算法的研究與分析

阮曉龍， 路景鑫

(河南中醫藥大學 網絡信息中心，鄭州 450008)

IP地址聚合算法的研究與分析

阮曉龍， 路景鑫

(河南中醫藥大學 網絡信息中心，鄭州 450008)

數據聚合是當今信息化應用中常見技術之一，結合數據聚合思想，針對龐大的IP地址信息進行多種聚合算法的研究與實現，并通過可視化的數據分析，對聚合算法進行性能評估。

IP地址； 聚合算法； 性能分析

0 引言

隨著計算機網絡的迅猛發展，基于IP地址的安全管理和訪問控制的應用方式愈加常態化，IP地址的聚合應用也逐漸趨于多元化、復雜化，如IP地址查詢、路由優化、IP黑名單管理等，都將用到聚合算法。

IP地址聚合是將一組IP地址聚合成一個或多個不能再次聚合的IP地址塊的過程。進行IP地址聚合，主要起到減少地址條目數，提高應用效率的作用。本文將提出三種IP地址聚合算法，通過不同算法的實現以及對算法的性能評估，進而充分了解IP地址聚合的基本原理和算法之間的差異性。

1 聚合算法概述

1.1 聚合定義

不是所有的IP地址或網絡段地址都可以聚合，只有當網絡前綴相同且連續的地址才能被聚合，形成新的聚合地址塊。IP地址進行聚合的主要思想及判斷依據如下所述。

給定兩個IP地址p1=addr1/len1,p2=addr2/len2，其中addr表示IP地址，len表示掩碼長度,令len1≤len2，則有：

a)如果len1

b)如果len1=len2且addr1/(len1-1)=addr2/(len2-1)，則稱p1和p2是可聚合的, 聚合結果為p3=addr1/(len1-1)。

1.2 聚合算法的實際應用

在網絡環境或實際應用中，經常會見到聚合算法在不同場景下的應用。常見的應用場景如下。

(1)在網絡設備中的應用

在網絡設備中的應用主要體現在路由器/路由交換機上。當網絡中業務量增加時，設備路由表數目也逐漸增多，路由表的增長嚴重影響路由性能。為減輕設備的負擔和提高路由效率，需通過聚合算法將路由匯聚成更少條目的路由，這就是所謂的“路由聚合”。路由聚合最明顯的好處是縮小路由表的“尺寸”，通過路由聚合，將大大減輕網絡設備的負擔以及提高設備的路由效率。

(2)在業務系統中的應用

由于其安全性問題，目前許多業務系統上都配置了訪問控制列表。訪問控制列表機制是針對每一個IP地址設定具體的規則權限，當訪問控制列表需要配置的條目數增加時，可通過聚合算法將多地址聚合成較少數量的地址塊，從而減少訪問控制列表的條目數。

(3)在安全設備中的應用

在安全設備中的應用主要體現在防火墻上。防火墻作為一種內部與外部網絡之間的網絡安全設備，其添加的策略規則是針對單一地址增加的訪問權限。當防火墻中添加的策略規則增多時，可根據相同規則對其作用的IP地址進行聚合，以起到減少策略規則數，降低防火墻設備壓力的作用。

2 聚合算法的實現

本文采用“除二階乘”、“除二階乘優化”和“二進制比對”3種算法進行IP地址聚合。

2.1 “除二階乘”聚合算法

(1)算法思想

“除二階乘”聚合算法是將IP地址轉換為整數類型，根據相同的網絡前綴，對整數類型的IP地址進行位移運算，判斷IP地址能否聚合。當兩個IP地址能夠聚合時，然后對聚合后的IP地址塊進行輸出，得到聚合結果。該算法主要思想是用整數在程序中進行直接運算。

(2)具體實現

使用“除二階乘”聚合算法進行地址聚合時，主要的實現過程，如圖1所示。

圖1 “除二階乘”聚合算法過程

“除二階乘”聚合算法主要分為4個步驟。

第一步：原始數組整理。程序中獲取一組需要聚合的IP地址，在進行聚合前首先要“洗數據”，將原始數組中的數據進行排序后并去除包含關系。

“排序”的主要算法邏輯如下：

①將點分式加前綴表示的IP地址(如：192.168.1.2/32)以“/”進行分割，從左到右得到兩個數值ip和prefix，這兩個數值分別代表IP地址和網絡前綴，將得到的ip值轉換成整數類型，存入數組中；

②“排序”算法主要滿足以下兩點規則：

a)ip數值越小的數據排序越靠前；

b)ip數值相同的數據，prefix數值越小排序越靠前。

③本過程中使用的排序方法為快速排序法，具體的排序流程，如圖2所示。

第二步：數據重新組合。由于上步操作中，已經去除數組的包含關系，所以能夠聚合的地址，其網絡前綴也必相等。本步驟將整理后的數組重新調整，將相同網絡前綴的地址放在一起，并將網絡前綴作為“鍵值”，最終形成以“網絡前綴”為鍵值的數組A4。

第三步：地址聚合計算。相同網絡前綴的地址進行聚合時主要的聚合算法邏輯如下所述。

①將地址進行從小到大排序，排序結束后，依次取出一個地址，與上個地址進行聚合比對，若可以聚合則進行聚合運算，否則將該地址添加到輸出數組中，具體的聚合算法過程如下：

a)取出ip數值，將ip數值除以2的(33-prefix)次方，并將結果進行“向下取整”運算，計算方法為：

quotient=floor(ip/pow(2,(33- prefix))); //獲取子網掩碼前所有數值

b)如果與上個數值的quotient相等，則說明兩個地址能夠聚合，并將網絡前綴數減1，取上個地址的ip與網絡前綴數減1的值，作為聚合后的結果，將結果添加到數組A5中；

c)如果與上個數值的quotient不相等，則說明兩個地址不能聚合，將該地址添加到數組A6中；

d)判斷數組A5是否為空，若為空，則輸出數組A6，A6則為聚合后的結果；若不為空,則將A5按照上述方法繼續進行聚合計算。

第四步：遞歸聚合計算。當獲取到聚合后數組時，還需要再次做聚合計算，判斷輸出的數組能否再進行聚合。當再次聚合計算完成后，判斷兩次數組的地址塊數量是否發生變化。

如果地址塊數量發生變化，則說明本次計算進行了地址聚合，并將聚合后的結果再次做遞歸計算；如果地址塊數量沒有發生變化，則說明本次計算沒有進行地址聚合，將結果數據進行輸出，輸出的聚合結果最終滿足“形成一個或多個不能再次聚合的IP地址塊”的聚合定義。

(3)實現代碼

“除二階乘”聚合算法中根據相同網絡前綴數進行聚合計算，具體實現代碼如下所示。

圖2 排序流程

//相同網絡前綴數的地址聚合計算

function getTempArray(arr){

$tempArray=array();

$outputArray=array();

$tempquotient=0;

$len = count(arr);

for($i = 0; $i

//遍歷獲取數組中數據，并進行計算

$quotient=floor($arr[$i]/pow(2,(33- prefix)));

//對上個地址的“商”進行比較，判讀兩個地址能否合并

if ($quotient == $tempquotient) {

array_pop(outputArray);

//取上個地址，并將網絡前綴數減1作為聚合后結果

$tempArray[] = ($outputArray[$i-1][0], prefix-1);

}

else {

//如果比較不相等，則對該地址的“商”以及網絡前綴數進行賦值

$tempquotient = quotient;

$netmask = prefix;

//將不能合并的地址添加到輸出數組中

$outputArray[]=array(arr[i],netmask);

}

}

return tempArray;

}

2.2 “除二階乘優化”聚合算法

(1)算法思想

“除二階乘優化”聚合算法是將3.1中的聚合算法進行優化，其主要優化之處是將IP地址按網絡前綴數從高到低進行聚合，在聚合計算過程中，網絡前綴數高的IP地址聚合完成后，將形成“聚合后”數組和“不能聚合”數組。

“聚合后”數組將聚合結果與網絡前綴數低的IP地址數組進行數組合并，并做聚合計算；“不能聚合”數組中的IP地址在后續的聚合過程中也不會發生聚合，所以將這些地址直接作為輸出數組進行輸出。

根據該聚合算法與“除二階乘”聚合算法的邏輯思想對比，可以看出該算法在每次聚合過程中參與計算的IP地址塊數量將逐漸減少，從而減少程序的計算量，提高計算效率。

(2)具體實現

使用“除二階乘優化”聚合算法對IP地址進行聚合，主要的實現過程，如圖3所示。

“除二階乘優化”聚合算法主要分為三個步驟，分別是原始數組整理、數據重新組合和地址聚合計算。

在“原始數組整理”和“數據重新組合”兩個過程中與“除二階乘”聚合算法保持一致，“地址聚合計算”將通過網絡前綴從高到低優化的聚合算法，將大大減少數據的聚合計算時間。

(3)實現代碼

“除二階乘優化”聚合算法的實現過程中，將網絡前綴從高到低依次進行聚合的具體實現代碼如下。

圖3 “除二階乘優化”聚合過程

//遞歸進行聚合計算

function recursion(){

//按網絡前綴數從高到低依次進行地址聚合

for($i=32;$i>=0;$i--){

//判斷是否存在該網絡前綴數的數組

if(isset(this->allArray[i])

&&!empty(this->allArray[i])){

//獲取到該數組中的數據

$array=$this->allArray[i];

sort($array);

//獲取聚合后的結果

$result=$this->getTempArray($array,$i);

//判斷網絡前綴數減1的數組是否存在

if(!isset($this->allArray[$i-1])){

//如果不存在，初始化一個數組

$this->allArray[i-1]=[];

}

//將聚合后的結果添加到網絡前綴數減1的數組中

$this->allArray[$i-1]=array_merge(this->allArray[$i-1],result)

}

}

}

2.3 “二進制比對”聚合算法

(1)算法思想

“二進制比對”聚合算法，主要是將IP地址轉換成二進制字符串，根據相同的網絡前綴，對轉換的二進制IP地址進行比較，從而判斷IP地址能否聚合。當IP地址能夠聚合時，將網絡前綴數減1，并結合聚合后IP地址進行輸出，得到最終聚合結果。

該算法采用了換算二進制的方法，雖然該算法過程較為復雜，但算法的邏輯思想較為簡單，能夠讓人們更易理解聚合計算原理。

(2)具體實現

使用“二進制比對”聚合算法對IP地址進行聚合，主要的實現過程，如圖4所示?！岸M制比對”聚合算法與“除二階乘”聚合算法具體實現過程基本一致，在運算的過程中將數據進行二進制比對處理，最終活動聚合結果。

(3)實現代碼

“二進制比對”聚合算法中去除包含關系，需計算每個地址塊的范圍，具體實現代碼如下。

//獲取地址塊范圍方法

function getRange(ip,net){

//定義最大值字符串

$max="11111111111111111111111111111111";

//定義最小值字符串

$min="00000000000000000000000000000000";

//根據網絡前綴數計算地址二進制數

$ipstr=getNetString($ip,$net);

$max1=substr($max,$net,(32-$net));

$min1=substr($min,$net,(32-$net));

//獲得地址最小值的字符串

$minbit=$bit1.$min1;

//根據二進制計算最小IP地址

$minIP=getBitToIP(minbit);

//獲得地址最大值的字符串

$maxbit=$bit1.$max1;

圖4 “二進制比對”聚合算法過程

//根據二進制計算最大IP地址

$maxIP=GetBitToIP($maxbit);

//添加地址范圍數組

$result=array($minbit, $maxbit);

return result;

}

3 聚合算法的性能分析

為了評估不同算法的計算性能，本文對不同算法進行了多指標點的性能分析，具體分析指標點的詳細介紹，如表1所示。

在測試分析過程中，受測試條件約束，本文在測試千萬數量級時，不再進行“二進制比對”聚合算法的測試且其他兩種算法僅進行1至5千萬數據量的分析。

(1)時間復雜度分析

對萬數量級、十萬數量級、百萬數量級、千萬數量級的IP地址進行聚合，不同算法聚合計算所消耗的時間對比，如圖5、圖6、圖7、圖8所示。

通過對時間復雜度的對比分析，可得出以下幾點結論：

①數量級增大時，聚合算法所消耗的時間也將線性增加；

②算法優化，可以提升計算效率，無論什么級別數量的地址進行聚合時，“除二階乘優化”聚合算法所消耗的時間相比“除二階乘”聚合算法消耗的時間明顯縮短。

(2)CPU頻率使用量分析

對萬數量級、十萬數量級、百萬數量級、千萬數量級的IP地址進行聚合，不同算法聚合計算所消耗的CPU頻率使用量對比，如圖9所示。

通過對CPU頻率使用量對比圖進行分析，可得出CPU頻率使用量在增加到最大頻率之前時，3種算法占用服務器資源的大小關系為：“二進制比對”>“除二階乘”>“除二階乘優化”。

(3)CPU使用率分析

對CPU使用率進行分析主要為了查看不同算法隨著時間的增長，CPU使用率的增長速率變化情況。本次實驗將取100萬作為基本數量級，并獲取服務器在開始計算后，前20 s的監控數據進行分析，分析結果，如圖10所示。 通過對CPU使用率對比圖進行分析，可得出“除二階乘”聚合算法的CPU使用率增長速度大于其他兩種算法，但是總體上三種聚合算法的CPU使用率增長速度基本保持一致。

表1 性能分析指標點詳細介紹

圖5 萬數量級地址聚合時間對比圖

圖6 十萬數量級地址聚合時間對比圖

圖7 百萬數量級地址聚合時間對比圖

圖8 千萬數量級地址聚合時間對比圖

圖9 消耗CPU頻率使用量對比圖

圖10 消耗CPU使用量對比圖

(4)內存使用量分析

對萬數量級、十萬數量級、百萬數量級、千萬數量級的IP地址進行聚合計算，不同算法所消耗的內存使用量對比，如圖11所示。

圖11 IP地址聚合所消耗內存使用量對比圖

通過內存使用量對比圖可得出服務器內存的使用量會隨著聚合地址的數量增大而增大，當聚合地址的數量增加到100萬以后，服務器內存使用量的增率明顯提高。

(5)內存使用率分析

對內存使用率進行分析主要為了查看不同算法隨著時間的增長，內存使用率的增長速率變化情況。本次實驗將取100萬作為基本數量級，并獲取服務器在開始計算后，前20 s的監控數據進行分析，分析結果，如圖12所示。

圖12 不同算法所消耗內存使用率隨時間變化趨勢圖

通過對內存使用率對比圖進行分析，可得出“二進制比對”聚合算法的內存使用率增長速度大于其他兩種算法，說明了“二進制比對”聚合算法在計算過程中消耗大量的服務器內存資源。

4 總結

本文主要論述了IP地址聚合算法的基本原理及應用模式，并通過三種不同算法對不同級別數量的IP地址進行對比分析。通過本文不僅能夠充分的了解IP地址聚合算法的實現原理，而且通過不同級別數據量的測試對比分析結果，能夠充分體現出算法對大數據量計算性能的重要性。

[1] 查普爾(Chappell,L.A),蒂特爾(Tittel, E.).TCP/IP 協議 原理與應用[M]. 馬海軍,吳華，譯.北京：清華大學出版社,2005.

[2] 謝希仁.計算機網絡[M].電子工業出版社,2003.6.

[3] 陳秀莉.淺論無類域間路由與可變長子網掩碼技術[J].安徽電氣工程職業技術學院學報, 2004(3):90-92.

Research and Analysis of IP Address Aggregation Algorithms

Ruan Xiaolong, Lu Jingxin

(Network Information Center, HACTCM, Zhengzhou 450008, China)

Data aggregation is one of common technologies in today's information technology application. Based on the idea of data aggregation, this paper does a variety of research and implementation of aggregation algorithm for the IP addrese of the vast information, and through the visualization of data analysis, it makes performance evaluation for the aggregation algorithms.

IP addresses; Aggregation algorithms; Performance analysis

河南省教育廳自然科學研究(15B520013)

阮曉龍(1981-)，男，講師，研究方向：計算機網絡、計算機軟件、Web技術。

1007-757X(2017)06-0011-06

TP311

A

2010.00.00)