俄罗斯VS沙特直播

这个类是一个静态变量的例子:包括变量Math.PI和Math.E,它们的值是数学常量π和e。成长之时:前瞻行业趋势虽然那场政策的暴风雨已过,但袁军意识到,公司经营如果像以前一样,过分依赖向电视台销售器材,那么总有一天会被挤在市场外。比如枚举,虽然EffectiveJava中推荐使用,但是在Android平台上却是不被推荐的。2.3.1内置子程序和函数回想一下,子程序是组织在一起给定名称的一组程序指令。这个方法会一直阻塞到某个注册的通道有事件就绪。
返回首页

基于改进Bloom Filter与BP神经网络的IPv6路由查找算法

时间:2018-04-16 23:52来源:知行网www.youyuan-chem.com 编辑:麦田守望者

本文提出了一种适用于IPv6,提高路由器报文转发效率的一种IBFBP神经网络算法,将一个大的神经网络分解成多个小的神经网络使得每个神经网络学习的路有条目相应减少,从而提高了学习的效率。

  0 引言

  随着因特网的快速发展,IPv4地址日益紧张,虽然提出了CIDR无类域间路由,私有地址等解决方案,但终究是治标不治本,终究会消失殆尽,IP地址相关管理组织于2011年2月3日宣布分配完毕,一方面是地址资源数量的限制,另一方面是随着电子技术及网络技术的发展,计算机网络将进入人们的日常生活,可能身边的每一样东西都需要连入全球因特网。地址的不足严重地制约了中国及其他国家互联网的应用和发展。所以我们提出了IPv6,相比IPv4,IPv6采用了128位二进制数编址,具有巨大的地址空间[1-3]。再者路由器是构成因特网的骨架。它的处理速度是网络通信的主要瓶颈之一,随着互联网用户的大量增加,用户网络要求的提高,网络带宽越来越大,相应的路由有条目就越来越多,这就对路由器产生了巨大的挑战,提高路由器的硬件配置可以提高他的运行速度,但这不是长久之计,而且昂贵。所以一个好的算法也是提高路由器性能的关键。本文就提出了一种适用于IPv6,提高路由器报文转发效率的一种IBFBP神经网络算法,将一个大的神经网络分解成多个小的神经网络使得每个神经网络学习的路有条目相应减少,从而提高了学习的效率[4-6]。

  1 问题描述

  IPv6路由查找要求最长匹配的路由查找地址,相比精确匹配更为复杂。利用BF算法与BP神经网络相结合,通过BF算法将IPv6地址前缀进行分类产生不同的集合,每个集合对应一个BP神经网络,将多对一的问题转化成一对一的问题,能够快速查找路由[7,8]。但是标准的BF算法存在当插入的元素越多,错判在集合内的概率就会增大,容易产生误判,而误判率的大小将会影响搜索过滤的成本。本文对BF算法进行改进,使其减少误判率的发生,降低搜索过滤成本,从而提高IPv6路由查找效率[9]。

  2 改进Bloom Filter算法

  2.1 标准Bloom Filter算法

  在哈希算法中存在一个冲突(碰撞)的问题,用同一个哈希函数得到的两个结果值有可能相同。为了减少冲突,应更多的引入哈希函数,如果通过其中的一个哈希值我们得出某元素不在集合中,那么该元素肯定不在集合中。只有在所有的哈希函数告诉我们该元素在集合中时,才能确定该元素存在于集合中,这就是Bloom-Filter算法。

  如图1所示,首先,Bloom Filter是一个m位的位数组,且全为0。同时,需要定义k个不同的hash函数,每一个hash函数都随机的将每一个输入元素映射到位数组中的一个位上。那么对于一个确定的输入,我们会得到个索引。

  插入元素:经过k个hash函数的映射,我们会得到k个索引,我们把位数组中这k个位置全部置1(不管其中的位之前是0还是1)

  查询元素:输入元素经过k个hash函数的映射会得到k个索引,如果位数组中这k个索引任意一处是0,那么就说明这个元素不在集合之中;如果元素处于集合之中,那么当插入元素的时候这k个位都是1。

  图1 Bloom Filter工作过程

  2.2 改进的Bloom Filter算法

  在传统的Bloom Filter算法中:

  1、存在误判,图一中,当插入x、y、z这三个元素之后,再来查询w,会发现w不在集合之中,而如果w经过三个hash函数计算得出的结果所得索引处的位全是1,那么Bloom Filter就会告诉你,w在集合之中,实际上这里是误报,w并不在集合之中。

  2、标准的Bloom Filter算法,只支持插入和查找。当表达的集合是静态集合时,标准的Bloom Filter可以正常工作,但是如果要表达的集合是变动的,标准Bloom Filter的弊端就显现出来了,无法从Bloom Filter集合中删除一个元素。因为该元素对应的位会牵动到其他的元素。

  对于标准的Bloom Filter算法存在的不足,提出改进的Bloom Filter算法,IBF是在标准的BF算法的基础上,以哈希函数关键字的特征建立一个标志库且以关键字的最小值作为标志来区分,在搜索过程中只需将查询数与标志的位置一起做查询,来判别测试值是否存在,不仅能达到过滤的基本要求并且能大幅减少通过搜索过滤器后需比对的关键字的数量,降低整个过滤器搜索所需要花费的搜索成本,让搜索过滤器有更好的性能。从而提高了效率。空间的节省和查询的高效是通过一定的错误率来换取的IBF虽然不能完全消除误判,但是相比BF大大降低了误判的发生。对于标准BF不能进行删除操作IBF做出的改进是将位数组用counter数组来代替,在插入元素时给对应的k个counter的值分别加1,删除元素时给对应的k个counter的值分别减1。

  如图2,假设有一集合S={n1,n2,n3,n4,n5,n }有六个元素,h1,h2,h3(k=3)三个哈希函数,用LB来代表建立的标志库,用来存放标志。

  图2 counter数组

  图3 LB标志库

 

如图2所示,在插入元素时给对应的k个counter的值分别加1,删除元素时给对应的k个counter的值分别减1,从而实现对元素的删除。

  在图3中,假设检测两个数,一个为n1(1)它的标志为1,一个为n10(20)它的标志位为20,首先检测时,先将两个数的标志位与LB标志库做匹配,发现LB标志库中没有n10,继而判断出n10属于误判直接丢弃,对于n1检测到LB标志库中有它的值,就会接受n1通过过滤阶段,在以后的搜索中直接进入1的位置。通过这种方法提前判断出误判的发生,从而大大降低了误判率,而且避免了无用的检测过滤,从而降低了检测成本,节约了检测时间。

  建立过滤器

  {

  定义过滤器filter

  声明( 集合A,hash函数h ,整数 m,counter V)

  返回 过滤器filter

  初始化 counter V= 0

  Foreach 集合A中元素 a

  Foreach hash 哈希函数 h

  counter V[hash h(a)]=1+1

  结束 foreach

  结束 foreach

  返回 过滤器 filter

  }

  建立标志库LB

  {

  声明标志库LB (集合B,hash函数,LB)

  返回LB

  Foreach 集合B中元素b

  Foreach hash 哈希函数h

  分配每一个min[h(b)]于LB,

  所有b产生相同的min[h(b)]放在LB相同的区间

  结束foreach

  结束foreach

  返回 LB

  }

  新集合比对阶段

  产生测试Test

  {

  声明(测试值T,filter,LB,hash h,counter V)

  返回值Yes or Misdiagnosis or mismatching

  Foreach hash h

  If counter V[h(T)]=0 returns mismatching

  If counter V[h(T)]!=0

  after finding B

  If min[h(T)]!=B returns Misdiagnosis

  If min[h(T)]=B returns Yes

  结束foreach

  }

  3IBFBP算法描述

  3.1 BP神经网络

  BP网络能学习和存贮大量的输入-输出模式映射关系,而无需事前揭示描述这种映射关系的数学方程[10]。它的学习规则是使用梯度下降法,通过反向传播来不断调整网络的权值和阈值,使网络的误差平方和最小。BP神经网络模型拓扑结构包括输入层、隐层和输出层[11]。如图4所示,采用3层BP神经网络结构。

  图4 BP神经网络

  64位IPv6前缀BP神经网络如图四。输入层在学习阶段为路由条目,在查询时为从目的IP提取的网络前缀,输出层为下一跳的索引号,路由器根据索引号,对数据分组进行转发。

  将一个大的神网络分为64个小的神经网络,从而简化神经网络的复杂性,减少每个网络的学习条目,加速学习过程。

3.2 IBFBP算法

  IBF-BP算法流程图如图5所示:

  图5 IBF-BP算法

顶一下
(0)
0%
踩一下
(0)
0%
标签(Tag):BP神经网络 IPv6路由查找算法
------分隔线----------------------------
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:点击我更换图片
猜你感兴趣