一种基于IPV6的高维大规模包匹配方法

摘要

本发明公开了一种基于IPV6的高维大规模包匹配方法，把基于实数编码的差分演化算法与传统的包匹配算法相融合，在适应值设计上引入变异系数的思想，从而使问题的处理更具有客观性。通过引入分布性特征，自适应调整变异的剧烈程度，从而动态权衡种群的多样性和收敛性之间的矛盾。数值实验表明与传统算法相比，在速度、存储空间等综合性能上得到有效改善，另外本方法还有一个显著特点：包匹配的时间性能与规则数目之间具有很弱的相关性，从而本方法适合处理高维和大规模包匹配问题。

主权项

1.一种基于IPV6的高维大规模包匹配方法，其特征是：数据包采用包括源IP地址、目的IP地址、源端口、目的端口、协议的五元组来确定一个分组；在IPV6协议里IP地址以××××︰××××︰××××︰××××︰××××︰××××︰××××︰××××的形式存在；源IP和目的IP地址从高位到低位，把每一段分别标识为x_ij，i∈{1,2},j∈$\left\{\mathrm{1,2,3,4,5,6,7,8}\right\}{X}_i=\mathrm{Extract}\left(\mathrm{IP}\right)=\underset{j=1}{\overset{8}{\Sigma }}\left(x_{\mathrm{ij}}\mathrm{mod}1024\lambda \right)i\in \left\{\mathrm{1,2}\right\}---\left(1\right)$其中λ参数的值根据网络规模进行设计，在处理x_i1时，只考虑单播的情况，最高三位的值固定为001，故x_i1不考虑最高三维的值；源端口和目的端口都是以十六位二进制表示，以相应的十进制Y₃、Y₄标识；X_i=Y_imod1024λ，i∈(3,4)，上层传输层协议用八位的二进制表示，以相应的十进制X₅标识,设X表示向量(X₁，X₂，X₃，X₄，X₅)；$F\left(X\right)=(\underset{i=1}{\overset{5}{\Sigma }}{\alpha }_i{X}_i+\mathrm{\lambda \beta })\mathrm{mod}1024\lambda ---\left(2\right)$F(X)∈(0,1024λ)，并且F(X)为整数，0≦α_i≦1,0≦β≦1024；依据公式(1)、(2)，F(X)函数把X映射到一维空间(0,1024λ)；F(X)函数的目的就是把无规则的规则库映射到一个区间；在映射函数F(X)，X域空间和F(X)映射空间已知的条件下，识别α_i和β的参数值，定义向量A为(α_1，α_2，α_3，α_4，α₅)，运用差分演化算法来搜索使适应值最小的A和β的组合；采用实数进行编码，以便引入与问题领域相关的启发式信息以增加演化算法的搜索能力；在采用实数编码时考虑下面两个问题：（a）群体个体的描述：个体是一个实数向量，向量中的每个元素都是一个连续的变量；个体用向量为S_i(s_i1…s_ij…s_in)，n是问题的维数，S_i表示第i个个体，s_ij表示第i个个体的第j个分量，s_ij是一个浮点数，范围在[l(j),u(j)]；（b）在对个体进行变异操作时，如s_ij的值超出[l(j),u(j)]，要进行相应的操作,采用下列公式进行:$S_{\mathrm{ij}}=\left\{\begin{array}{cc}l\left(j\right)& S_{\mathrm{ij}}<l\left(j\right)\mathrm{andr}<0.5\\ 2l\left(j\right)-S_{\mathrm{ij}}& S_{\mathrm{ij}}<l\left(j\right)\mathrm{andr}>=0.5\\ u\left(j\right)& S_{\mathrm{ij}}>u\left(j\right)\mathrm{andr}<0.5\\ 2u\left(i\right)-S_{\mathrm{ij}}& S_{\mathrm{ij}}>u\left(i\right)\mathrm{andr}<0.5\end{array}\right.---\left(5\right)$其中r是一个范围在[0，1]之间的随机数；所述基本差分演化算法为：父代两个相异随机个体进行差操作得到的差分矢量加到随机选择的第三个相异个体上,生成一变异个体，接着按照一定的概率,父代个体与变异个体之间进行交叉操作,生成一新个体,在父代个体与新个体之间根据适应值的大小进行选择操作,选择适应值较优的个体作为子代；变异时依据下列公式(6)进行操作。ν_m(t+1)=S_gbest(t)+Δ(t,S_r2(t)-S_r3(t))        (6)其中m≠gbest≠r₂≠r₃其中t为当前演化代数，而函数Δ(t,x)的值域为[0,x]或[x,0],并使得当t增大时，Δ(t,x)接近于0的概率大增，即t的值越大，Δ(t,x)取值接近于0的概率越大，从而可以做到演化初期更多的考虑全局搜索，而在后期偏向于局部搜索；Δ(t,x)=x(1-τ^β),其中β=(1-t/T)^η     (7)其中τ是[0，1]上的一个随机数，T表示最大代数，η是决定变异激烈程度的一个参数，起着调整局部搜索区域的作用，其取值一般为{2，3，4，5}；当ν_mj(t+1)超出[l(j),u(j)]，根据公式（5）进行处理；S_r2(t)，S_r3(t)是父代随机选择的两对个体，进行锦标赛选择得到的两个相异个体，S_gbest(t)是父种群最优个体；交叉时依据下列公式(8)进行操作：${\mu }_{\mathrm{mj}}(t+1)=\left\{\begin{array}{cc}{v}_{\mathrm{mj}}(t+1)& \mathrm{rand}\left(\right)\le C_R\\ S_{\mathrm{mj}}\left(t\right)& \mathrm{rand}\left(\right)>C_R\end{array}\right.j=\mathrm{1,2},...N.---\left(8\right)$C_R=RED_N/(64λ)        (9)其中RED_N定义为：如X域中数目超过M阀值，且这些点从X域映射到F(X)域同一个点，F(X)域中这样的点定义为冗余点，F(X)域中冗余点的数目定义为RED_N，而λ值根据网络规模进行设置，λ的值的设置确保C_R大于1为小概率事件；选择操作依据下列公式(10)进行操作：设计适应性度量：F(X)域中冗余点的数目越少，即RED_N点越小，种群个体就越优；统计F(X)域中被X域映射到的点，这些点的平均值记为再计算出标准差S,根据计算出变异系数C_V，-C_V值越小，种群个体就越优；RED_N和C_V都是从F(X)域中被映射到的点的分布性能来考虑问题，利用统计学原理来保证点的分布性，分布性越好，内存空间占用就越少，而且包的匹配速度与F(X)域中被映射到的点的分布性有很大关系，分布性性越好，包的匹配速度相应提高；设x域映射到F(X)中同一个点i的数目定义为H(i)；V为x域所有映射点的总和，定义如公式(12)$V=\underset{i=1}{\overset{n}{\Sigma }}H\left(i\right)---\left(11\right)$其中if H(i)=0then H(i)=ω，ω可以调节，F(X)中如存在点没有被映射到会带来内存的浪费，适当把ω动态增加，得到的A，β组合会减少内存消耗；令$T\left(i\right)=\left\{\begin{array}{cc}1& \mathrm{ifH}\left(i\right)\ne 0\\ 0& \mathrm{otherwise}\end{array}\right.---\left(12\right)$令V_AVE=V/T     (13)由公式(11)、(12)、(13)得到的V_AVE这个指标可以用来分析F(X)域中点被映射的密集度，通过它观察包匹配的时间效率随规则数增长的变化情况，它的值越小意味着被映射的点分布越均匀，分布性能越好；令f(A,β)=φRED_N-ψC_V+□V_AVE       (14)φ，ψ，□是用来调节RED_N、G以及□对适应值的贡献大小，φ、ψ、□的值在0和1之间，和为1；衡量种群个体的指标就是f(A,β)，它的值越小，个体就越优，寻找A,和β的最优组合，就是搜索使f(A,β)的值最小的A，β组合；由公式(9)中RED_N的描述知F(X)域中的点可能有多个X映射，这样就可能有多个规则存放在同一个点，可以借助传统方法设计一个指针链表串联多个规则，以保证包匹配顺利进行；当防火墙或者路由器收到数据包时，分析数据包的协议头，提取出IP地址，根据Extract(IP)和F(X)两函数计算出此数据包映射的点，如此点存在多个规则，依据指针链表进行顺序查找。