使用布隆过滤器参数用于唯一地址计算的地址自动配置

摘要

本申请涉及使用布隆过滤器参数用于唯一地址计算的自动配置。在一个实施例中提供了一种方法，该方法包括通过网络设备基于将布隆过滤器参数应用到由网络设备自动配置的候选地址生成布隆过滤器比特向量；以及通过网络设备选择性地重复对候选地址的自动配置直到相应布隆过滤器比特向量包括在为网络设备保留的保留比特向量位置处被置位的比特，该保留比特向量位置提供在链路层域内的候选地址的唯一性。

说明书

技术领域

本公开一般涉及通过互联网协议(IP)数据网络中的主机网络设备进 行的地址自动配置，更具体地涉及使用布隆过滤器(BloomFilter)参数用 于唯一地址计算的自动配置。

背景技术

该部分描述了能够被使用的方法，但不必是先前已经被设想或使用的 方法。因此，除非特别指示，否则该部分描述的任何方法不是该申请的现 有技术，并且该部分描述的任何方法不被认为是该部分包括的现有技术。

现有的无状态自动配置技术使能IPv6设备(如主机设备)响应于接收 的指定由通告路由设备通告的链路前缀的路由通告消息，生成其自己的自 动配置的IPv6地址。IPv6设备能够基于将链路前缀与后缀(如扩展唯一标 识符(EUI-64)链路层设备地址、随机生成的数等)相连接来生成自动配 置的IPv6地址。

IPv6设备发起重复地址检测(DAD)过程以确定另一个IPv6设备是否 使用该自动配置的IPv6地址：IPv6设备可以基于广播/多播查询(如邻居请 求消息)到链路层域中的全部IPv6设备发起DAD过程；替换地，IPv6设备 可以发送单播地址注册消息到路由器并且等待路由器的未检测到任何重复 地址的通知。

发明内容

在一个实施例中，一种方法包括通过网络设备基于将布隆过滤器参数 应用到由网络设备自动配置的候选地址来生成布隆过滤器比特向量；以及 通过网络设备选择性地重复对候选地址的自动配置直到相应布隆过滤器比 特向量包括在为网络设备保留的保留比特向量位置处被置位的比特，保留 比特向量位置提供在链路层域内的候选地址的唯一性。

在另一实施例中，一种装置包括存储器电路和处理器电路。存储器电 路被配置为存储布隆过滤器参数和为装置保留的一个或多个保留比特向量 位置的标识。处理器电路被配置为基于将布隆过滤器参数应用到由处理器 电路自动配置的候选地址来生成布隆过滤器比特向量。处理器电路还被配 置为选择性地重复对候选地址的自动配置直到相应布隆过滤器比特向量包 括在至少一个保留比特向量位置处被置位的比特，至少一个保留比特向量 位置提供在链路层域内的候选地址的唯一性。

在另一实施例中，逻辑被编码在一个或多个非暂态有形介质中，该逻 辑用于由机器执行并且当被机器执行时能够操作用于：通过网络设备基于 将布隆过滤器参数应用到由网络设备自动配置的候选地址来生成布隆过滤 器比特向量；以及通过网络设备选择性地重复对候选地址的自动配置直到 相应布隆过滤器比特向量包括在为网络设备保留的保留比特向量位置处被 置位的比特，保留比特向量位置提供在链路层域内的候选地址的唯一性。

在另一实施例中，一种方法包括：通过第一网络设备分配一个或多个 保留比特向量位置给连接到第一网络设备的第二网络设备；以及第一网络 设备发送至少指定一个或多个保留比特向量位置的消息到第二网络设备， 使得第二网络设备能够自动配置出在第一网络设备的链路层域内是唯一的 地址，这是基于第二网络设备确定将布隆过滤器参数应用到地址产生了具 有在一个或多个保留比特向量位置处被置位的至少一个比特的布隆过滤器 比特向量。

在另一实施例中，一种装置包括存储器电路和处理器电路。处理器电 路被配置为分配一个或多个保留比特向量位置给连接到装置的网络设备。 设备接口电路被配置为发送至少指定一个或多个保留比特向量位置的消息 到网络设备，使得网络设备能够自动配置出在装置的链路层域内是唯一的 地址，这是基于网络设备确定将布隆过滤器参数应用到地址产生了具有在 一个或多个保留比特向量位置处被置位的至少一个比特的布隆过滤器比特 向量。

在另一实施例中，逻辑被编码在一个或多个非暂态有形介质中用于由 机器执行并且当被机器执行时能够操作用于：通过第一网络设备分配一个 或多个保留比特向量位置给连接到第一网络设备的第二网络设备；以及第 一网络设备发送至少指定一个或多个保留比特向量位置的消息到第二网络 设备，使得第二网络设备能够自动配置出在第一网络设备的链路层域内是 唯一的地址，这是基于第二网络设备确定将布隆过滤器参数应用到地址产 生了具有在一个或多个保留比特向量位置处被置位的至少一个比特的布隆 过滤器比特向量。

附图说明

参考附图，其中在附图中具有相同附图标记的元件表示相似的元件， 并且其中：

图1根据示例实施例图示说明具有用于提供布隆过滤器参数到网络设 备用于由网络设备进行唯一地址计算的装置的示例系统。

图2是根据示例实施例图示说明图1的设备的任何一个的简图。

图3根据示例实施例图示说明提供布隆过滤器参数到网络设备用于由 网络设备进行唯一地址计算的示例方法。

图4根据示例实施例图示说明对用于由网络设备进行地址计算的保留 布隆过滤器比特位置的示例分配。

图5根据示例实施例图示说明提供布隆过滤器参数到网络设备用于由 网络设备进行唯一地址计算的示例通告消息。

具体实施方式

具体实施例使能数据网络(如，IPv6网络)中的每个网络设备，基于 映射到布隆过滤器比特向量的自动配置的IPv6地址，保证其自动配置的设 备网络地址(如，IPv6地址)至少在链路层域内是唯一的，该布隆过滤器 比特向量包括在为网络设备保留的保留比特向量位置处设置的比特。

在大型IPv6网络中的重复地址检测(DAD)的传统部署能够使得在 IPv6网络中大量传播多播流量，尤其在具有成千上万或更多的传感器节点 的物联网(IoT)网络中。此外，现有邻居发现技术需要网络设备防卫其IP 地址，其在电池供电的、资源受限的设备(诸如在延长时间周期内维持空 闲状态(如，“休眠”)的传感器设备)中是不实际的。

布隆过滤器是空间效率概率数据结构，其被被实现为“N”位的比特 阵列以测试元素是否是一个集合的成员：测试结果是元素“可能在集合 中”或“明确不在集合中”；因此，在布隆过滤器中误报(falsepositive) 结果是可能的，但漏报(falsenegative)是不可能的。

根据示例实施例，布隆过滤器可以被用来使能网络设备自动配置候选 设备地址到唯一地址值。数据网络中的每个网络设备被分配相应的未被分 配给数据网络中的任何其它网络设备的一个或多个保留比特向量位置。网 络设备可以选择性地重复地址自动配置直到候选设备地址映射到具有在一 个或多个保留比特向量位置处被置位的比特的布隆过滤器比特向量；换句 话说，网络设备不被允许使用自动配置的网络地址，除非网络地址(根据 规定的用于生成布隆过滤器比特向量的哈希函数)映射到具有在保留比特 向量位置处被置位的比特的布隆过滤器比特向量。(一个或多个)保留比 特向量位置可以通过网络设备从第二网络设备接收以使能网络设备验证候 选网络地址的唯一性，第二网络设备被授权分配该(一个或多个)保留比 特向量位置；换句话说，该(一个或多个)保留比特向量位置不被分配给 至少在链路层域内或数据网络的规定域内(如，规定的自主系统内)的任 何其它网络设备。分配该(一个或多个)保留比特向量位置的设备可以是 提供接入链路到网络设备用于到达数据网络的交换设备，或与网络设备通 信的另一设备。分配该(一个或多个)保留比特向量位置的设备(如，交 换设备或路由设备)可以与其它网络设备合作以，例如基于网络设备分配 独有布隆过滤器比特向量范围，保证保留比特向量位置之间的唯一性。

因此，示例实施例完全地消除了对重复地址检测(DAD)消息的需 要，因为每个网络设备能够基于(一个或多个)保留比特向量位置自动配 置网络地址，该网络地址是唯一的。因此，示例实施例在使用大量主机网 络设备的大规模网络(诸如部署的具有传感器设备的物联网(IoT))内 提供可扩展地址自动配置，这基于一个或多个网络设备(即，“分配网络 设备”)分配(一个或多个)独有保留比特向量位置到连接到分配保留比 特向量位置的一个或多个分配网络设备的一个或多个网络设备，使能每个 网络设备自动配置IPv6地址，该IPv6地址至少在分配网络设备的链路层域 内是唯一的。

图1是根据示例实施例图示说明具有为网络10中的网络设备16提供 链路层连接14的一个或多个分配网络设备12的示例网络10的简图。该网 络可以被实现为局域网(LAN)和/或广域网(WAN)。每个分配网络设 备(例如被示为交换设备，如SW1、SW2、SW3、SW4和SW5)12可以 被配置为提供链路层连接14，该链路层连接14使能网络设备16根据规定 的链路层协议和/或路由协议附连到相应交换设备12。每个分配网络设备 12可以被实现为链路层(层2)接入设备(诸如有线或无线链路层接入设 备)、链路层交换机、无线LAN控制器和/或网络层(层3)路由设备 等。因此，分配网络设备12还可以被称为“第一跳(first-hop)”网络设 备或“接入设备”，其为网络设备16提供接入网络10的链路层。为了方 便，分配网络设备12将被称为“交换设备”12。

每个链路层连接14可以是有线链路(如，以太网/IEEE802 10/100/1000MB/s)14a或无线链路(如，WiFi、红外、蓝牙等)14b。因 此，每个网络设备16可以具有与一个或多个交换设备12的一个或多个有 线链路14a和/或一个或多个无线链路14b。示例网络设备可以是传感器设 备(如，IoT“智能尘埃”)，该传感器设备具有有线或无线设备接口电 路用于在网络10中有线或无线通信。

每个交换设备12还可以具有一个或多个内部交换链路18，该内部交 换链路18可以将交换设备12连接到另一交换设备12、路由设备、服务器 设备等用于在交换设备12之间传输数据分组。

如下面参考图3-5进一步详细地描述，交换设备12可以在彼此之间分 配在全网络布隆过滤器比特向量的范围内的规定保留空间。因此，每个交 换设备12可以发送来自规定的保留空间的一个或多个保留比特向量位置 到每个附连的网络设备16，其提供整个网络10内的候选IPv6地址的唯一 性。

图2根据示例实施例图示说明图1的设备12和/或16的任何一个的示 例实现。每个装置12和/或16是被配置为通过网络10实现与其它物理机 器12和/或16网络通信的物理机器(即，硬件设备)。此处关于指定操作 使用的术语“被配置为”或“被配置用于”指设备和/或机器被物理地构建 和布置以执行指定操作。因此，装置12和/或16是网络使能的(提供到网 络的用户接入的用户机器)/通过网络10实现网络通信的机器。

每个装置12和/或16可以包括设备接口电路40、处理器电路42和储 存器电路44。设备接口电路40可以包括一个或多个不同物理层收发器用 于与其它设备12和/或16的任何一个通信；设备接口电路40还可以包括 基于IEEE的以太网收发器用于通过链路14和/或18(如有线或无线链 路、光链路等)的任何一个与图1的设备通信。处理器电路42可以被配 置为执行此处描述的任何操作，并且存储器电路44可以被配置为存储此 处描述的任何数据或数据分组。

公开的设备12和/或16的电路(包括设备接口电路40、处理器电路 42、存储器电路44和它们相关联的组件)的任何一个可以以多种形式被 实现。公开的电路的示例实现包括硬件逻辑，该硬件逻辑以逻辑阵列(诸 如可编程逻辑阵列(PLA)、现场可编程门阵列(FPGA))被实现，或 通过掩膜编程集成电路(诸如专用集成电路(ASIC))被实现。这些电路 中的任何一个还可以使用基于软件的可执行资源被实现，该可执行资源通 过相应内部处理器电路(诸如微处理器电路(未示出))被执行；以及使 用一个或多个集成电路被实现，其中存储在内部存储器电路中(如，存储 器电路44内)的可执行代码的执行使得(一个或多个)集成电路：实现 处理器电路以将应用状态变量存储在处理器存储器中，生成执行此处描述 的电路操作的可执行应用资源(如，应用实例)。因此，在该说明书中使 用的术语“电路”指使用一个或多个集成电路实现的基于硬件的电路或基 于软件的电路二者，该基于硬件的电路包括逻辑用于执行所述的操作，该 基于软件的电路包括(使用一个或多个集成电路实现的)处理器电路，处 理器电路包括保留部分的处理器存储器用于存储通过由处理器电路对可执 行代码的执行而被修改的应用状态数据和应用变量。存储器电路44可以 例如使用非易失性存储器(诸如可编程只读存储器(PROM)或 EPROM)和/或易失性存储器(诸如DRAM等)被实现。

此外，对“输出消息”或“输出分组”(等)的任何引用可以基于生 成数据结构形式的消息/分组并且将该数据结构存储在所公开的装置(如， 发送缓冲器)中的非暂态有形存储器介质中被实现。对“输出消息”或 “输出分组”(等)的任何引用还可以包括通过通信介质(如，有线或无 线链路，视情况而定)将存储在非暂态有形存储器介质中的消息/分组电子 传输(也可以使用光传输，视情况而定)到另一网络节点。类似地，对 “接收消息”或“接收分组”(等)的任何引用可以基于公开的装置检测 消息/分组在通信介质上电子(或光)传输并且将检测的传输作为数据结构 存储在所公开的装置(如，接收缓冲器)中的非暂态有形存储器介质中被 实现。还应该注意存储器电路44可以例如基于存储器地址分配和处理器 电路42执行的分区，通过处理器电路42被动态地实现。

图3根据示例实施例图示说明提供布隆过滤器参数到网络设备用于由 网络设备进行唯一地址计算的示例方法。图4根据示例实施例图示说明了 对用于由网络设备进行唯一地址计算的保留布隆过滤器比特位置的示例分 配。图5根据示例实施例图示说明提供布隆过滤器参数到网络设备用于由 网络设备进行的唯一地址计算的示例通告消息。

关于任何附图描述的操作可以被实现为存储在计算机或机器可读非暂 态有形存储介质(如，软盘、硬盘、ROM、EEPROM、非易失性RAM、 CD-ROM等)中的可执行代码，该操作基于使用一个或多个集成电路实现 的处理器电路执行代码被完成；此处所述的操作还可以被实现为被编码在 一个或多个非暂态有形介质中用于执行的可执行逻辑(如，可编程逻辑阵 列或设备、现场可编程门阵列、可编程阵列逻辑、专用集成电路等)。

此外，关于任何附图描述的操作可以以任何顺序或至少一些操作并行 地被执行。此处所述的操作的执行仅是说明性的；同样地，操作不必需要 通过此处描述的基于机器的硬件组件被执行；相反地，其它基于机器的硬 件组件可以被用来以任何合适的顺序或至少一些操作并行地执行所公开的 操作。

参见图3，每个交换设备(如，SW1)的处理器电路42可以在操作 50中分配N位布隆过滤器比特向量20(图4)中专门为相应交换设备 (如，SW1)12保留的规定的布隆过滤器比特范围(如，22a)。如图4 中所示，每个布隆过滤器比特范围22是整个N位网络布隆过滤器比特向 量范围20的子集。布隆过滤器比特范围22a、22b、22c、22d和22e被专 门保留给交换设备SW1、SW2、SW3、SW4和SW5；因此，交换设备 SW112不允许任何附连的网络设备16使用被映射到具有在规定的布隆过 滤器比特范围22a之外被置位的比特的布隆过滤器比特向量的网络设备地 址；类似的，交换设备SW2、SW3、SW4和SW5不允许任何映射到各自 范围22b、22c、22d和22e之外被置位的比特的网络设备地址。范围22a 的大小可以基于在网络10的域内交换设备12的数目“J”与N位网络比 特向量20相比，其中每个比特范围22(Nsw)的大小可以等于位数N除 以交换设备12的数目(J)，即“Nsw＝N/J”。

交换设备“SW1”12的处理器电路42可以在操作52中例如响应于检 测到来自一个或多个连接的网络设备16的路由请求消息，检测已经连接 到交换设备的一个或多个网络设备16。响应于检测到网络设备16，交换 设备“SW1”的处理器电路42可以在操作54a中分配来自保留布隆过滤器 比特范围22a的一个或多个保留比特向量位置(图4中的24)用于由网络 设备16专门地使用。

交换设备“SW1”12的处理器电路42可以在操作56中生成包含专门 分配给该一个网络设备16的(一个或多个)保留比特向量位置24的路由 通告消息(图5中的26)；路由通告消息26被单播传播到网络设备16用 于仅由网络设备16使用。

图5图示说明由交换设备“SW1”生成的示例路由通告信息26，该路 由通告信息26包含使能由网络设备16进行唯一地址自动配置的布隆过滤 器参数36。布隆过滤器参数36可以包括专门分配给该一个网络设备16的 (一个或多个)保留比特向量位置24。布隆过滤器参数36还可以指定用 于生成布隆过滤器比特向量的哈希函数28。路由通告还可以指定要被用于 地址自动配置的网络地址前缀(如IPv6地址前缀)30。

如图5中所示的，路由通告消息26可以指定用来将候选自动配置的 地址映射到N位布隆过滤器比特向量中的相应一个或多个比特的一个或多 个哈希函数“Hx”、“Hy”。(一个或多个)保留比特向量位置24可以 指定要被设置在N位布隆过滤器比特向量中的特定比特32或指定的范围 34。具体地，保留比特向量位置24a说明特定比特“B(l，i，j)”32a要被 设置为N位布隆过滤器比特向量20中的“l”，其中“l”标识第一保留 比特分配。“i”标识网络设备(如“节点”)“i”，以及“j”标识交换 设备“j”。因此，特定比特“B(l，i，j)”32a标识专门为附连到交换设 备“j”12的节点“i”16保留的第一保留比特。类似地，该保留比特向量 位置24b说明特定比特“B(2，i，j)”32b(其是与“B(l，i，j)”32a不 同的位)是专门为附连到交换设备“j”12的节点“i”16保留的。其它的 保留比特向量位置可以被分配以增加满足唯一性需要的可用的保留比特向 量位置的数目。

因此，在节点“i”可以使用自动配置的地址之前，通过附连到交换设 备“j”12的节点“i”16自动配置的任何候选地址必须通过哈希函数 “Hx”或“Hy”的任意一个被映射到具有在保留比特向量位置“B(l，i， j)”、“B(2，i，j)”等的至少一个上(如，内)被置位的比特的布隆过 滤器比特向量。换句话说，候选地址可以被使用，只要哈希函数的任何一 个在一个或多个保留比特向量位置24上设置位。(一个或多个)保留比 特向量位置24还可以被表述为标识各个保留位置(如，位置“5”，“7”， “12”，“13”，“14”，“17”和“201”(十进制))的一系列整数值 (如，“5，7，12-14，17，201”)。

在路由通告消息26以独有保留范围34a和34b的形式指定保留比特向 量位置24c和24d的情况下，范围34a可以指定通过附连到交换设备“j” 12的节点“i”16自动配置的任何候选地址必须通过哈希函数“Hx”或 “Hy”被映射以范围“R(x，i，j)”34a或“R(y，i，j)”34b内设置一个 或多个比特。范围34可以是连续部分的比特，例如通过交换设备 “SW1”12专门保留的部分22a中的比特0-15。范围34的大小 (N_device)可以是基于通过交换设备12专门保留的部分22的大小 (Nsw)除以被允许加入交换机的设备的最大数目“I_max”，其中：

N_device＝Nsw/I_max

因此，每个网络设备16可以专门保留一个或多个保留比特向量位置 24，该一个或多个保留比特向量位置24在网络10的域内提供任意候选IPv6 地址的唯一性。

参考图3，请求网络设备16的设备接口电路在操作58中接收指定布隆 过滤器参数36的路由通告消息26，该布隆过滤器参数36例如包括一个或多 个保留比特向量位置24和哈希函数设置28以用来生成布隆过滤器比特向 量。

连接的网络设备16的处理器电路42在操作60中使用在路由通告消息26 中指定的IPv6地址前缀30生成自动配置的候选IPv6地址。连接的网络设备 16的处理器电路42在操作62中基于应用布隆过滤器参数36为候选IPv6地址 生成布隆过滤器比特向量(如，“候选IPv6布隆过滤器比特向量”或 “IPv6地址比特向量”)，该布隆过滤器参数36包括路由通告消息26的布 隆过滤器参数36中指定的哈希函数设置28。

连接的网络设备16的处理器电路42在操作64中确定IPv6地址比特向量 是否具有被设置在为网络设备16保留的一个或多个保留比特向量位置24上 的一个或多个比特。如果在操作64中，处理器电路42确定候选IPv6地址的 相应布隆过滤器比特向量不具有在为网络设备16保留的保留比特向量位置 处的至少一个置位比特，则处理器电路42重复操作60中的自动配置以再次 尝试获得该唯一IPv6地址。

如果在操作64中，候选IPv6地址的布隆过滤器比特向量具有在为网络 设备16保留的、提供唯一性的保留比特向量位置处被置位(set)的至少一 个比特，则已经确认自动配置的IPv6地址的唯一性的处理器电路42在操作 66中可以发送指定该唯一IPv6地址的邻居通告消息到交换设备12。邻居通 告消息还可以指定为网络设备16保留但未在候选IPv6地址的布隆过滤器比 特向量中被置位的一个或多个未使用的比特向量位置，使能交换设备12将 未使用的比特向量位置保留给另一网络设备16。

优选地，交换设备12还可以测试IPv6地址相对(一个或多个)保留的 比特位置24的唯一性，以例如确保唯一性需要和/或确保非法网络设备16未 使用不正确的IPv6地址：IPv6地址唯一性可以基于在交换设备12在操作68 中将唯一IPv6地址存储在本地地址表中之前，将路由通告消息存储在具有 规定的超时间隔(如，2分钟)的待定缓存中来进行测试。根据偏好，该 测试可以针对每个IPv6地址前缀被随机地或周期性地完成。

交换设备在操作70中还可以添加设备布隆过滤器比特向量到由交换机 维持的用于连接的网络设备16的本地交换专用比特向量，和/或到基于在许 多交换专用比特向量上执行按位或运算的全网络比特向量。

根据示例实施例，网络中的每个网络设备可以被分配独有布隆过滤器 比特位置，该独有比特位置使能网络设备自动配置地址，该地址在该网络 内是唯一的。网络设备自动配置在网络内是唯一的网络地址的要求消除了 重复地址检测的必要性，确保大规模网络可以在初始网络部署期间以最小 网络负载是扩展的。示例实施例在IoT网络中尤其有效，根据RFC6775实 现针对低功耗和有损网络(RPL)的路由协议，因为布隆过滤器比特位置 的范围可以通过路由器被委派给其子节点，使能子节点进一步转委派布隆 过滤器比特位置的委派的范围。

虽然本公开中的示例实施例结合当前被认为是执行所附权利要求中指 定的主题的最佳模式已经被描述，但是应当理解示例实施例仅是说明性 的，并且不限制所附权利要求中指定的主题。