前往顾页

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

时候:2018-04-16 23:52来源:知行网www.zhixing123.cn 编辑:麦田守望者

本文提出了一种合用于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路由查找算法
------分开线----------------------------
颁发评论
请自发遵循互联网相关的政策法规,严禁公布色情、暴力、革命的谈吐。
评价:
神色:
考证码:点击我更换图片
猜你感兴趣