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

阮曉龍， 路景鑫

(河南中醫(yī)藥大學 網(wǎng)絡信息中心，鄭州 450008)

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

阮曉龍， 路景鑫

(河南中醫(yī)藥大學 網(wǎng)絡信息中心，鄭州 450008)

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

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

0 引言

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

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

1 聚合算法概述

1.1 聚合定義

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

給定兩個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 聚合算法的實際應用

在網(wǎng)絡環(huán)境或實際應用中，經(jīng)常會見到聚合算法在不同場景下的應用。常見的應用場景如下。

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

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

(2)在業(yè)務系統(tǒng)中的應用

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

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

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

2 聚合算法的實現(xiàn)

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

2.1 “除二階乘”聚合算法

(1)算法思想

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

(2)具體實現(xiàn)

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

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

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

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

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

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

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

a)ip數(shù)值越小的數(shù)據(jù)排序越靠前；

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

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

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

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

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

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

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

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

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

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

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

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

(3)實現(xiàn)代碼

“除二階乘”聚合算法中根據(jù)相同網(wǎng)絡前綴數(shù)進行聚合計算，具體實現(xiàn)代碼如下所示。

圖2 排序流程

//相同網(wǎng)絡前綴數(shù)的地址聚合計算

function getTempArray(arr){

$tempArray=array();

$outputArray=array();

$tempquotient=0;

$len = count(arr);

for($i = 0; $i

//遍歷獲取數(shù)組中數(shù)據(jù)，并進行計算

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

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

if ($quotient == $tempquotient) {

array_pop(outputArray);

//取上個地址，并將網(wǎng)絡前綴數(shù)減1作為聚合后結果

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

}

else {

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

$tempquotient = quotient;

$netmask = prefix;

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

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

}

}

return tempArray;

}

2.2 “除二階乘優(yōu)化”聚合算法

(1)算法思想

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

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

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

(2)具體實現(xiàn)

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

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

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

(3)實現(xiàn)代碼

“除二階乘優(yōu)化”聚合算法的實現(xiàn)過程中，將網(wǎng)絡前綴從高到低依次進行聚合的具體實現(xiàn)代碼如下。

圖3 “除二階乘優(yōu)化”聚合過程

//遞歸進行聚合計算

function recursion(){

//按網(wǎng)絡前綴數(shù)從高到低依次進行地址聚合

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

//判斷是否存在該網(wǎng)絡前綴數(shù)的數(shù)組

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

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

//獲取到該數(shù)組中的數(shù)據(jù)

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

sort($array);

//獲取聚合后的結果

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

//判斷網(wǎng)絡前綴數(shù)減1的數(shù)組是否存在

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

//如果不存在，初始化一個數(shù)組

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

}

//將聚合后的結果添加到網(wǎng)絡前綴數(shù)減1的數(shù)組中

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

}

}

}

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

(1)算法思想

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

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

(2)具體實現(xiàn)

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

(3)實現(xiàn)代碼

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

//獲取地址塊范圍方法

function getRange(ip,net){

//定義最大值字符串

$max="11111111111111111111111111111111";

//定義最小值字符串

$min="00000000000000000000000000000000";

//根據(jù)網(wǎng)絡前綴數(shù)計算地址二進制數(shù)

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

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

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

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

$minbit=$bit1.$min1;

//根據(jù)二進制計算最小IP地址

$minIP=getBitToIP(minbit);

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

$maxbit=$bit1.$max1;

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

//根據(jù)二進制計算最大IP地址

$maxIP=GetBitToIP($maxbit);

//添加地址范圍數(shù)組

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

return result;

}

3 聚合算法的性能分析

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

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

(1)時間復雜度分析

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

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

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

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

(2)CPU頻率使用量分析

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

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

(3)CPU使用率分析

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

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

圖5 萬數(shù)量級地址聚合時間對比圖

圖6 十萬數(shù)量級地址聚合時間對比圖

圖7 百萬數(shù)量級地址聚合時間對比圖

圖8 千萬數(shù)量級地址聚合時間對比圖

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

圖10 消耗CPU使用量對比圖

(4)內(nèi)存使用量分析

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

圖11 IP地址聚合所消耗內(nèi)存使用量對比圖

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

(5)內(nèi)存使用率分析

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

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

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

4 總結

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

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

[2] 謝希仁.計算機網(wǎng)絡[M].電子工業(yè)出版社,2003.6.

[3] 陳秀莉.淺論無類域間路由與可變長子網(wǎng)掩碼技術[J].安徽電氣工程職業(yè)技術學院學報, 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-)，男，講師，研究方向：計算機網(wǎng)絡、計算機軟件、Web技術。

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

TP311

A

2010.00.00)