为了解决现有的名字查找方法假阳性概率较大的的问题，本发明提供一种ICN网络中基于名字拆分的信息查找方法，包括以下步骤：A：建立哈希表；B.建立拆分模型；C.建立名字查找框架；D.进行名字查找。本发明利用ICN网络信息名字固有的特性，以拆分为基准进行名字查找，提高信息名字的查找的效率；针对现有计数布隆过滤器查找存在的假阳性问题，特别增加了动态参数u，获得单个组件的验证值，降低了潜在的假阳性的问题。同时针对ICN名字的变长特性，结合树结构本身具有的灵活性，引入树结构进行名字变长部分的查找，使查找的准确率更高。
1.一种ICN网络中基于名字拆分的信息查找方法，其特征是：包括以下步骤：
A：建立哈希表：哈希表中包括检验值和转发端口以及树位图根节点位置；
B.建立拆分模型：对路由器中的转发表以字符“\”的为准进行拆分，设转发表第M个字符“\”处作为拆分位置，将转发表拆分成FIB1和FIB2；将待查找名字前缀在拆分位置处拆分成Basis部分和Suffix部分，满足 则待查找的名字最长前缀匹配prefix表示为：
名字的前缀，t1和t2分别表示在M处分离后的第一部分前缀和第二部分前缀；
C.建立名字查找框架：B步骤中的FIB1中存储拆分成组件Ci的Basis部分并将组件Ci分别存储于计数布隆过滤器中；FIB2中存储名字的Suffix部分，并用树位图表述；所述的计数布隆过滤器能够并行查找；其中，i＝1，2,3……；
D1.将C过程中的Basis部分的组件Ci分别进行哈希计算，如果出现哈希计算结果为0的组件，则记录哈希计算结果为0的最小组件标号y；否则，利用加权方式得到组件Ci对应的计数布隆过滤器中的验证值，将得到的验证值存储在对应的数组b中；
具体的，设计数布隆过滤器有M个，每个计数布隆过滤器大小为mi，哈希函数为ki个，名字为n个，hi,j(x)，为哈希函数， 其服从均匀分布，增加动态参数u；其中，u为Basis部分占整个名字的比例，则Basis部分的第i个组件的检验值为：则Basis部分总的检验值为：
D2.将D1步骤中得到的数组b中的前s个组件Ci的验证值分别依次累加求和并依次从小到大的进栈，将待查找的名字最长前缀匹配prefix的验证值位于最顶层，对应A步骤中的哈希表获得路由器转发端口或者suffix部分的根节点；其中，s＜y；
D3.查找D2步骤中的栈，如果栈为空，则从路由器默认端口转发名字信息；
D4.如果D2步骤中的栈非空，则判断D2步骤中最长前缀匹配prefix中前缀组件个数是否小于拆分位置；
D5.若最长前缀匹配prefix中组件的个数小于拆分位置成立，取出D2步骤中的栈的栈顶元素，对照A步骤所述的哈希表，在哈希表中查找栈中栈顶元素；
D6.若步骤D5步骤中的栈顶元素在哈希表中存在，则从栈顶元素对应的转发端口发送数据；若不成立，则继续步骤D5；
D7.若最长前缀匹配prefix中组件的个数小于拆分位置不成立，则取出D2步骤中的栈的栈顶元素，并查询A步骤中的哈希表，得到Suffix部分的树位图根节点位置，并从对应的路由器转发端口发送数据，实现名字查找。
2.根据权利要求1所述的一种ICN网络中基于名字拆分的信息查找方法，其特征是：所述C步骤中Basis部分的拆分成组件Ci的方法是：以字符“\”为界线，发现一个字符“\”就将该字符“\”后的组件定义为一个组件；所述的树位图表述Suffix部分，包括内部位图和外部位图，其中，内部位图用于表示名字的前缀，外部位图用于指示是否存在孩子节点。
3.根据权利要求1所述的一种ICN网络中基于名字拆分的信息查找方法，其特征是：所述的B步骤中还可以进行名字插入，其过程如下：B1.判断插入名字后的最长前缀匹配prefix,与设定的拆分位置的关系：B101.若插入名字后的最长前缀匹配prefix,小于拆分位置成立，利用字符“\”为界线，发现一个字符“\”就将该字符“\”后的组件定义为一个组件的方法对插入部分进行分组得到插入组件；将插入组件进行哈希计算得到关于计数布隆过滤器的位置数值，对照C步骤的计数布隆过滤器，将相对应的计数布隆过滤器的位置计数加1，实现名字插入；
B102.插入名字后的最长前缀匹配prefix,小于拆分位置不成立，则对Suffix进行处理，将插入部分通过树位图表述，该树位图的叶节点对应的内部位图与外部位图置1，实现名字插入。
4.根据权利要求1所述的一种ICN网络中基于名字拆分的信息查找方法，其特征是：所述的B步骤中还可以进行名字删除过程：B2.判断删除名字后的最长前缀匹配prefix,,与设定的拆分位置的关系：
B201.若删除名字后的最长前缀匹配prefix,,小于拆分位置成立，利用字符“\”为界线，发现一个字符“\”就将该字符“\”后的组件定义为一个组件的方法对名字删除部分进行分组得到删除组件；将删除组件进行哈希计算得到关于计数布隆过滤器的位置数值，对照C步骤的计数布隆过滤器，将相对应的计数布隆过滤器的位置计数减1，实现名字删除；
B202.若删除名字后的最长前缀匹配prefix,,小于拆分位置不成立，将删除部分通过树位图表述，并将树位图中内部位图与外部位图相应的位置修改为0；再判断suffix部分是否为空：若为空，则将计数布隆过滤器对应的suffix部分的计数器减1，实现名字删除。
一种ICN网络中基于名字拆分的信息查找方法
技术领域
[0001] 本发明涉及信息中心网络技术领域，具体涉及一种ICN网络中基于名字拆分的信息查找方法。
背景技术
[0002] 随着互联网的广泛普及与应用，当前的网络体系出现诸多不足，严重影响互联网的进一步发展。目前，网络应用的主体已经转为文字信息、图像和视频，内容服务已经成为网络服务的主体。用户关注的不再是内容存储在哪里，而是内容本身，以及内容检索与传输速度、质量和安全性。这种基于主机的通信模型已经不适合当前网络发展的需要。
[0003] 近年来，将内容与主机分离的改进方法引起了广泛关注，以内容为中心的网络成为未来网络的一种重要模式和发展趋势。信息中心网络(Information Centric Networking，ICN)直接把内容作为网络处理的基本对象，将数据的存储地址，安全性和可访问性与内容本身分离开来，并且以名字作为数据索引的唯一依据，其优势在于极大地提高了网络资源的共享率，提升了网络的性能，减少了资源的浪费。
[0004] 对ICN来说，其中流动的都是有名字的信息，整个网络以及终端就在各种信息的驱动下运行起来了。因此，如何从海量信息名字中找到所需要的信息，是ICN中一个关键的问题。由于ICN中信息名字具有可变，数量巨大等特性，所以对ICN信息名字的查找效率要求更高。现有的，基于布隆过滤器的名字查找多是基于名字长度分组进行查找的方法，其按照名字的长度存储于不同的布隆过滤器中。这种查询方法假阳性概率较大，影响查询准确度。
发明内容
[0005] 为了解决上述的技术问题，本发明提供一种ICN网络中基于名字拆分的信息查找方法，该方法利用ICN网络信息名字固有的特性，以拆分为基准进行名字查找，提高信息名字的查找的效率，为名字路由快速转发提供技术支持。
[0006] 所述的一种ICN中基于名字拆分的信息查找方法，其技术方案是：包括以下步骤：
[0007] A：建立哈希表：哈希表中包括检验值和转发端口以及树位图根节点位置；
[0008] B.建立拆分模型：对路由器中的转发表以字符”\”的为准进行拆分，设转发表第M个字符”\”处作为拆分位置，将转发表拆分成FIB1和FIB2；将待查找名字前缀在拆分位置处拆分成Basis部分和Suffix部分，满足 则待查找的名字最长前缀匹配prefix表示为：
[0009] 其中，，t为名
字的前缀，t1和t2分别表示在M处分离后的第一部分前缀和第二部分前缀；
[0010] C.建立名字查找框架：B步骤中的FIB1中存储拆分成组件Ci的Basis部分并将组件Ci分别存储于计数布隆过滤器中；FIB2中存储名字的Suffix部分，并用树位图表述；所述的计数布隆过滤器能够并行查找；其中，i＝1，2,3……；
[0011] D.名字查找过程：
[0012] D1.将C过程中的Basis部分的组件Ci分别进行哈希计算，如果出现哈希计算结果为0的组件，则记录哈希计算结果为0的最小组件标号y；否则，利用加权方式得到组件Ci对应的计数布隆过滤器中的验证值，将得到的验证值存储在对应的数组b中；
[0013] 具体的，设计数布隆过滤器有M个，每个计数布隆过滤器大小为mi，哈希函数为ki个，名字为n个，hi，j(x)，为哈希函数， 其服从均匀分布，增加动态参数u；其中，u为Basis部分占整个名字的比例，
[0014] 则Basis部分的第i个组件的检验值为：
[0015]
[0016] 则Basis部分总的检验值为：
[0017]
[0018] D2.将D1步骤中得到的数组b中的前s个组件Ci的验证值分别求和并依次从小到大的进栈，将待查找的名字最长前缀匹配prefix的验证值位于最顶层，对应A步骤中的哈希表获得路由器转发端口或者suffix部分的根节点；其中，s＜y；
[0019] D3.查找D2步骤中的栈，如果栈为空，则从路由器默认端口转发名字信息；
[0020] D4.如果D2步骤中的栈非空，则判断D2步骤中最长前缀匹配prefix中前缀组件个数是否小于拆分位置；
[0021] D5.若最长前缀匹配prefix中组件的个数小于拆分位置成立，取出D2步骤中的栈的栈顶元素，对照A步骤所述的哈希表，在哈希表中查找栈中栈顶元素；
[0022] D6.若步骤D5步骤中的栈顶元素在哈希表中存在，则从栈顶元素对应的转发端口发送数据；若不成立，则继续步骤D5；
[0023] D7.若最长前缀匹配prefix中组件的个数小于拆分位置不成立，则取出D2步骤中的栈的栈顶元素，并查询A步骤中的哈希表，得到Suffix部分的树位图根节点位置，并从对应的路由器转发端口发送数据，实现名字查找。
[0024] 进一步的，所述的C步骤中Basis部分的拆分成组件Ci的方法是：以字符”\”为界线，发现一个字符”\”就将该字符”\”后的组件定义为一个组件；所述的树位图表述Suffix部分，包括内部位图和外部位图，其中，内部位图用于表示名字的前缀，外部位图用于指示是否存在孩子节点。
[0025] 进一步的，所述的B步骤中还可以进行名字插入，其过程如下：
[0026] B1.判断插入名字后的最长前缀匹配prefix与设定的拆分位置的关系：
[0027] B101.若插入名字后的最长前缀匹配prefix小于拆分位置成立，利用字符”\”为界线，发现一个字符”\”就将该字符”\”后的组件定义为一个组件的方法对插入部分进行分组得到插入组件；将插入组件进行哈希计算得到关于计数布隆过滤器的位置数值，对照C步骤的计数布隆过滤器，将相对应的计数布隆过滤器的位置计数加1，实现名字插入；
[0028] B102.插入名字后的最长前缀匹配prefix小于拆分位置不成立，则对Suffix进行处理，将插入部分通过树位图表述，该树位图的叶节点对应的内部位图与外部位图置1，实现名字插入。
[0029] 进一步的，所述的B步骤中还可以进行名字删除过程：
[0030] B2.判断删除名字后的最长前缀匹配prefix与设定的拆分位置的关系：
[0031] B201.若删除名字后的最长前缀匹配prefix小于拆分位置成立，利用字符”\”为界线，发现一个字符”\”就将该字符”\”后的组件定义为一个组件的方法对名字删除部分进行分组得到删除组件；将删除组件进行哈希计算得到关于计数布隆过滤器的位置数值，对照C步骤的计数布隆过滤器，将相对应的计数布隆过滤器的位置计数减1，实现名字删除；
[0032] B202.若删除名字后的最长前缀匹配prefix小于拆分位置不成立，将删除部分通过树位图表述，并将树位图中内部位图与外部位图相应的位置修改为0；再判断suffix部分是否为空：若为空，则将计数布隆过滤器对应的suffix部分的计数器减1，实现名字删除。
[0033] 本发明的有益效果是：本发明利用ICN网络信息名字固有的特性，以拆分为基准进行名字查找，提高信息名字的查找的效率；针对现有计数布隆过滤器查找存在的假阳性问题，特别增加了动态参数u，获得单个组件的验证值，降低了潜在的假阳性的问题。同时针对ICN名字的变长特性，结合树结构本身具有的灵活性，引入树结构进行名字变长部分的查找，使查找的准确率更高。
附图说明
[0034] 图1为本发明流程图。
[0035] 图2为本发明的结构示意图。
[0036] 图3为查找框架示意图。
[0037] 图4为匹配过程示意图。
[0038] 图5为名字插入流程图。
[0039] 图6a为插入前的计数布隆过滤器。
[0040] 图6b为插入后的计数布隆过滤器。
[0041] 图7为名字删除流程图。
[0042] 图8a为删除前的计数布隆过滤器。
[0043] 图8b为删除后的计数布隆过滤器。
[0044] 图9为树位图节点图。
[0045] 图10为删除名字/cn/edu/course/history后的图9的变化图。
具体实施方式
[0046] 如图1～4所示，一种ICN网络中基于名字拆分的信息查找方法，其技术方案是：包括以下步骤：
[0047] A：建立哈希表：哈希表中包括检验值和转发端口以及树位图根节点位置；
[0048] B.建立拆分模型：对路由器中的转发表以字符”\”的为准进行拆分，设转发表第M个字符”\”处作为拆分位置，将转发表拆分成FIB1和FIB2；将待查找名字前缀在拆分位置处拆分成Basis部分和Suffix部分，满足 则待查找的名字最长前缀匹配prefix表示为：
[0049] 其中，，t为名
字的前缀，t1和t2分别表示在M处分离后的第一部分前缀和第二部分前缀；
[0050] C.建立名字查找框架：B步骤中的FIB1中存储拆分成组件Ci的Basis部分并将组件Ci分别存储于计数布隆过滤器中；FIB2中存储名字的Suffix部分，并用树位图表述；所述的计数布隆过滤器能够并行查找；其中，i＝1，2,3……；
[0051] 需要明确的是：所述的Suffix部分转化为树位图时，以步长基准划分为一个内部位图，剩下的名字部分如果超过设定步长，则确定有孩子节点，外部位图为1；反之，则无孩子节点，外部位图为0。如果外部位图为1，存在孩子节点的情况下，通过偏移量计算得到孩子节点的位置信息，配合内部位图，得到名字的前缀信息；
[0052] D.名字查找过程：
[0053] D1.将C过程中的Basis部分的组件Ci分别进行哈希计算，如果出现哈希计算结果为0的组件，则记录哈希计算结果为0的最小组件标号y；否则，利用加权方式得到组件Ci对应的计数布隆过滤器中的验证值，将得到的验证值存储在对应的数组b中；
[0054] 具体的，设计数布隆过滤器有M个，每个计数布隆过滤器大小为mi，哈希函数为ki个，名字为n个，hi，j(x)，为哈希函数， 其服从均匀分布，增加动态参数u；其中，u为Basis部分占整个名字的比例，则Basis部分的第i个组件的检验值为：
[0055]
[0056] 则Basis部分总的检验值为：
[0057]
[0058] 需要明确的是：所述的最小标号是指一个名字中组件的前后位置关系，如名字/cn/com/baidu/movie中组件com的标记为2；
[0059] D2.将D1步骤中得到的数组b中的前s个组件Ci的验证值分别求和并依次从小到大的进栈，将待查找的名字最长前缀匹配prefix的验证值位于最顶层，对应A步骤中的哈希表获得路由器转发端口或者suffix部分的根节点；其中，s＜y；
[0060] D3.查找D2步骤中的栈，如果栈为空，则从路由器默认端口转发名字信息；
[0061] D4.如果D2步骤中的栈非空，则判断D2步骤中最长前缀匹配prefix中前缀组件个数是否小于拆分位置；
[0062] D5.若最长前缀匹配prefix中组件的个数小于拆分位置成立，取出D2步骤中的栈的栈顶元素，对照A步骤所述的哈希表，在哈希表中查找栈中栈顶元素；
[0063] D6.若步骤D5步骤中的栈顶元素在哈希表中存在，则从栈顶元素对应的转发端口发送数据；若不成立，则继续步骤D5；
[0064] D7.若最长前缀匹配prefix中组件的个数小于拆分位置不成立，则取出D2步骤中的栈的栈顶元素，并查询A步骤中的哈希表，得到Suffix部分的树位图根节点位置，并从对应的路由器转发端口发送数据，实现名字查找。
[0065] 需要明确的是：本文所述的树位图表述方式为现有技术，见论文W Eatherton，G Varghese，Ditta Z，“Tree Bitmap：Hardware/Software IP Lookups with Incremental Updates，”ACM Sigcom Computer Communication Review，vol.34，no.2，pp.97-122，April 2004。
[0066] 例如，路由器中转发表如表I所示，其采用计数布隆过滤器和树位图进行存储，其对应的结构图如图2所示。图2中，拆分位置M＝2.树位图的步长为2，假设计数布隆过滤器中哈希函数个数为3。则图2中对应的内部位图与外部位图如表II所示，黑色节点表示FIB表中有效的前缀。计数布隆过滤器1中存储了com以及cn，计数布隆过滤器2中存储了baidu、edu、yahoo组件。
[0067] 表I:名字前缀表FIB
[0068]
[0069]
[0070] 表II：节点位图情况根节点为S1的树
[0071] 节点名字 内部位图 外部位图节点1 100 1110
节点2 100 0000
节点3 100 0000
节点4 100 0000
[0072] 节点位图情况根节点为S2的树
[0073] 节点名字 内部位图 外部位图节点1 100 1110
节点2 010 0000
节点3 100 0000
节点4 100 0000
[0074] 进一步的，所述的B步骤中还可以如图5步骤进行名字插入，例如：第二个计数布隆过滤器表述为计数布隆过滤器2，其中插入/qq的表述：如图6a为插入前的计数布隆过滤器中存储位置，图6b为增加插入名字/qq后的计数布隆过滤器中的存储位置。哈希/qq所在组件，找到在计数布隆过滤器中相应的位置，并在相应的位置1、3、6加1。
[0075] 进一步的，所述的B步骤中还可以如图7步骤进行名字删除。例如：如图8a所示，删除前的计数布隆过滤器中存储的位置信息，在删除/qq时，如图8b，哈希/qq所在组件，找到在计数布隆过滤器中对应的位置，并在相应的位置1、3、6减1。
[0076] 如图9，对于树位图操作的说明：假设插入的名字/cn/edu/culture/art/period，此时由于计数布隆过滤器中存在该名字的最长前缀匹配，所以计数布隆过滤器中不做任何改变，只需将节点4的内部位图和外部位图进行修改，此时图2中根节点S1变为图9所示，只需将节点4的内部位图修改为110，而外部位图不需要改变。同理删除/cn/edu/course/chinese/period时，只需要将节点2中内部位图变为100，原本没有孩子节点，所以外部位图不变。上述即为树位图的置1与置0操作。所谓的将树位图相应的内部位图与外部位图进行置1操作是指：假设删除名字/cn/edu/course/history，此时最长前缀匹配prefix大于拆分位置M，所以需要将根节点为S1的树位图中节点1的外部位图改为1010，节点3的内部位图改为000。由于删除名字后，树位图不为空，所以不需要计数布隆过滤器进行改变，如图9删除名字后，树位图如图10所示。
[0077] 假阳性分析：基于现有布隆过滤器的名字查找多是基于名字长度分组进行查找的方法，其按照名字的长度存储于不同的布隆过滤器中。本发明Basis部分采用的是基于单个组件Ci进行的存储，每个组件的存储可采用不同大小的计数布隆过滤器。
[0078] 假设查找框架中第i个计数布隆过滤器的假阳性概率为fi，一个组件产生的验证值为Ci，M个组件对应的总检验值为Ci，Fci是一个名字的Basis级检验值的冲突概率。现有的基于名字长度分组的查找方法中，当ki＝(mi/ni)ln2时，计数布隆过滤器所对应的假阳性[0079] 在本发明中，长度为i的Basis级每次匹配的假阳性概率 为：则每次匹配为零的概率为
[0080] Basis部分中每个组件对应的布隆过滤器中一个哈希函数j产生的分值ci的数学期望为：
[0081] Basis中每个组件对应的布隆过滤器产生的分值ci的方差为：
[0082] 则整个Basis组件对应的总相关性验证值Ci服从正态分布(Φ)，其中i≤M：
[0083]
[0084] 则 的上界为：
[0085]
[0086] 对于Basis部分的最长前缀匹配，查询框架中Basis部分所对应的假阳性概率：
[0087]
[0088] 而现有的ICN名字查询方法中布隆过滤器存在的假阳性概率则为：
[0089]
[0090] 对比查询框架中Basis所对应的假阳性概率和现有的ICN名字查询方法中布隆过滤器假阳性概率，可以发现，当存储空间和集合元素个数相同时，本发明的假阳性概率界限是小于现有的ICN名字查询方法。
[0091] 本发明在D1步骤引入了动态参数u，改善了以往ICN名字查询方法假阳性概率较高的缺陷，具有现实意义。
[0092] 以上所述仅为发明的较佳实施例而己，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
