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所示。“二进制比对”聚合算法与“除二阶乘”聚合算法具体实现过程基本一致，在运算的过程中将数据进行二进制比对处理，最终活动聚合结果。

(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)