CN115515202A - 用于混合自组织路由协议的设备 - Google Patents

Abstract

本发明涉及用于混合自组织路由协议的设备。描述了一种用于在数据网络中转发数据分组的路由设备。该路由设备与实施相同功能的多个其他这样的路由设备建立通信连接。数据网络包括如本文所述的多个路由设备。在该数据网络中，每个路由设备在该数据网络的稳定部分中利用路由表实施并应用主动式方法并且在该数据网络的不稳定部分中实施并应用反应式方法。当分组从该数据网络的稳定部分传输到该数据网络的不稳定部分(或反之亦然)时，转发方法会沿着该分组的路径改变。因此，该路由设备和该数据网络减轻了主动式路由方法的开销和反应式路由方法的等待时间的影响。

Description

用于混合自组织路由协议的设备

技术领域

本说明书涉及数据网络领域，并且特别是涉及一种用于在数据网络中路由数据分组的路由设备。特别地，本说明书涉及一种路由设备，该路由设备被配置为应用混合自组织路由协议来通过数据网络转发分组，该数据网络具有动态变化的网络拓扑结构以及数据网络的节点之间的无线链路的未知或变化的稳定性。

背景技术

数据网络通常用于在数据生产者与数据消费者之间传输数据。数据网络通常具有先验已知的拓扑结构。基于数据网络的已知拓扑结构，数据分组经由一个或多个路由器从一个终端设备路由到另一终端设备。出于冗余原因，可能会提供多条不同的路线，并且路由器选择这些路线中的一条或多条来传输数据。

例如，在大规模飞行自组织网络中，路由是一项具有挑战性的任务。比如移动自组织网络(MANET)或容延迟网络(DTN)等无线动态网络涵盖可以使用无线链路相互通信的移动主机。在这样的环境中，任何一对主机(即，像数据消费者和数据生产者这样的终端设备)之间的路线可以包括通过一个或多个节点(即，像路由设备这样的网络节点)的无线跳。这样的网络中的一个重要方面是，考虑到网络中的任何节点都是移动的并且无线信道条件也随时间变化，找到在任何一对节点之间转发数据的最佳策略。假设在一些情况下，可以找到并维持一些节点之间的路线，而在其他情况下，即使没有端到端路径，也需要逐跳进行转发。

发明内容

本发明的目的可以看作是开发一种用于数据网络的能够适应具有不同动态、传输特性和/或行为的网段的路由方法。该目的通过独立权利要求的主题来解决。

提供了根据独立权利要求的特征的路由设备。可以从从属权利要求和以下描述中得出本发明的进一步发展。

根据一个方面，提供了一种用于在数据网络中路由数据分组的路由设备。该路由设备包括具有路由信息库(RIB)的路由引擎、具有邻域信息库(NIB)的邻域引擎以及具有转发信息库(FIB)的转发引擎。NIB被配置为包含路由设备的邻居节点的至少一个条目。FIB被配置为包含目的地的至少一个条目。该路由设备被配置为从第一数据分组中提取目的地值，在FIB中搜索所提取的目的地值。该路由设备进一步被配置为，当FIB包含该目的地值的条目时，根据FIB中的该条目转发第一数据分组，否则，当FIB不包含该目的地值的条目时，从NIB中选择第一组至少两个邻居节点并且以喷洒操作模式将第一数据分组转发到所选择的第一组至少两个邻居节点，其中，在该喷洒操作模式中，转发引擎将第一数据分组转发到所选择的第一组至少两个邻居节点，该至少两个邻居节点具有一定的概率与所提取的目的地接触。该路由设备进一步被配置为在以喷洒操作模式转发第一数据分组之后，接收来自所选择的第一组至少两个邻居节点的反馈分组并且基于来自所选择的第一组至少两个邻居节点的反馈在FIB中为所提取的目的地生成条目，并且使用在FIB中所生成的条目来以聚焦操作模式转发第二数据分组，其中，在该聚焦操作模式中，转发引擎根据FIB中的条目将第二数据分组转发到邻居节点。

典型的路由机制实施主动式方法或反应式方法。在主动式方法中，路由协议交换消息，以创建网络的状态并创建定义可以通过哪个路由器到达哪个网络或终端设备的路由表。在反应式方法中，当要传输数据时，识别用于传输数据的路径。网络的状态没有被预先传达。与主动式方法相比，并且一般来说，反应式方法具有较低的开销(在传输数据之前不创建路由表)，但是具有较高的等待时间(因为在传输数据时需要找到合适的路径)。

本文描述的路由设备不是实施主动式方法或反应式方法，而是实施混合方法，根据该混合方法，在稳定的网段中利用主动式机制，而在不稳定的网段中利用反应式机制。

该路由设备被配置为当FIB不包含目的地值的条目时，基于路由设备与一组邻居节点之间的连接性特性从NIB中选择第一组至少两个邻居节点。

以喷洒操作模式发送第一数据分组以探测最佳路径。然后，根据FIB中的相应条目以聚焦操作模式发送第二数据分组和任何后续数据分组。

该路由设备被配置为应用两种转发模式：当FIB中存在目的地的条目时，该条目被用于转发分组(聚焦模式，路径或至少下一跳从FIB是已知的)，否则，当FIB中不存在条目时，喷洒操作模式被用于转发分组。在喷洒操作模式中，路由设备向从NIB中检索到的至少两个邻居节点发送消息，收集来自这至少两个邻居节点的反馈，选择这两个邻居节点中的一个在FIB中创建条目，并且然后使用该条目以聚焦模式将分组转发到所指示的目的地。

根据实施例，路由设备被配置为从多个邻居路由设备接收目的地状态信息DSI，并且进一步被配置为确定到每个邻居路由设备的连接稳定性值，并且进一步被配置为忽略从连接稳定性值低于预定稳定性阈值的邻居路由设备接收的DSI。

在该实施例中，路由设备对从邻居路由设备接收的目的地状态信息DSI进行过滤并且仅使用经由稳定链路(即，链路的稳定性值高于预定稳定性阈值)连接到当前路由设备的那些邻居路由设备。具有稳定链路的被过滤的路由设备的这个子集用于由当前路由设备通告给其他邻居路由设备。换句话说，路由设备实施选择性路由通告方案，其中，只有当接收到的DSI的稳定性满足某个稳定性标准(即，稳定性值高于阈值稳定性值)时，才由当前路由设备向其他(邻居)路由设备通告路线(到邻居路由设备的链路)。在一个实施例中，路由设备被配置为主动丢弃连接稳定性值低于预定稳定性阈值的DSI。

根据进一步的实施例，路由设备被配置为在FIB中为所提取的目的地生成该条目，使得该条目至少包含该目的地值和经由其能够到达对应目的地的邻居节点。

因此，FIB中的条目可以用于将去往某个目的地的数据分组转发到FIB条目中指示的下一跳。换句话说，在聚焦模式中，数据分组以确定的方式被转发到某个(单个)邻居节点(通往目的地的下一跳)。

根据进一步的实施例，路由设备被配置为监测路由设备与第一数据分组的提取的目的地之间的数据传输过程的性能度量值。当性能度量值增加时，路由设备被配置为根据FIB中的条目继续将数据分组转发到所提取的目的地，并且另外基于路由设备与该组邻居节点之间的连接性特性从NIB中选择第二组至少两个邻居节点并且以喷洒操作模式将第一数据分组转发到所选择的第二组至少两个邻居节点。

因此，当聚焦模式下的数据传输的性能度量值增加时，路由设备对两个其他邻居节点使用喷洒模式以便识别到目的地的替代路由器。性能度量值可以是传输等待时间、信噪比(SNR)、分组丢失、延迟、吞吐量等中的一个，或其组合。

根据进一步的实施例，路由设备被配置为从来自第二组的至少两个邻居节点接收反馈分组，并且被配置为基于来自第二组的邻居节点的反馈在FIB中为所提取的目的地生成条目。

根据进一步的实施例，路由设备被配置为以聚焦操作模式将第一数据分组转发到来自第一组的一个邻居节点和来自第二组的一个邻居节点。

在该实施例中，路由设备在聚焦操作模式下经由两个不同的邻居节点将数据分组转发到同一目的地。

根据进一步的实施例，路由设备被配置为当FIB中的特定条目的数据传输的性能度量与同一目的地的至少一个其他条目的性能度量相比更高时，基于路由设备与第一数据分组的提取的目的地之间的数据传输过程的性能度量从FIB中移除条目。

在该实施例中，FIB中性能不佳的条目的路线被移除，即，通过将条目的性能度量与其他条目的性能度量进行比较。

根据进一步的实施例，路由设备被配置为：除非FIB被填充了与从第一数据分组中提取的目的地值相对应的条目，或者当路由设备到第一组的邻居节点的连接被中断时，存储第一数据分组。

因此，路由设备实施了存储-转发机制。当通往最合适的下一跳的接口关闭时，或者除非FIB被填充了条目，否则分组会被路由设备缓存。分组被存储，直到合适的下一跳可用或者直到分组有效性期满。

根据进一步的实施例，路由引擎被配置为确定能够以预定成本到达预定目的地的一组下一跳。

成本是指目的地状态信息的成本。成本用作衡量路径相对于一组定义的度量(传输等待时间、信噪比(SNR)、分组丢失、延迟、吞吐量等、或其组合)的重要性的权重。

根据进一步的实施例，路由引擎被配置为从与路由设备直接互连的每个邻居节点接收目的地状态信息DSI的列表，向每个邻居节点通告自己的DSI的列表，并确定要包括在RIB中的邻居节点的子集。

因此，该路由引擎操作基于稳定邻居之间交换的可达性信息。接收到的DSI会基于通告邻居的稳定性进行过滤，即，不稳定邻居发送的DSI将被忽略。

根据进一步的实施例，DSI包括关于经由某个邻居节点到达目的地的成本的信息。

根据进一步的实施例，目的地值是目的节点或子网的地址，或者目的地值是数据名称。

路由引擎与目的地的类型(基于主机或基于名称)无关。

根据进一步的实施例，邻域引擎被配置为收集关于路由设备的邻居节点中的每一个的状态的信息。收集的信息包括以下参数：邻居节点的可用性；邻居节点的容量；路由设备与邻居节点之间的连接性；以及路由设备与邻居节点之间的链路质量。

根据进一步的实施例，路由设备被配置为重复发送消息以便确定这些参数中的至少一个参数的值。

因此，邻域引擎周期性地接收关于邻居路由设备的状态的信息，从而重复更新链路质量。

根据进一步的实施例，邻域引擎被配置为基于可用性、容量以及链路质量来确定每个邻居节点的稳定性。邻域引擎被配置为向路由引擎和转发引擎提供每个邻居节点的稳定性。

总之，本文描述的路由设备被配置为与实施相同功能的多个其他这样的路由设备建立数据网络。数据网络包括如本文所述的多个路由设备。在该数据网络中，在稳定部分中使用利用路由表的主动式方法并且在不稳定部分中使用反应式方法。当分组从数据网络的稳定部分传输到数据网络的不稳定部分(或反之亦然)时，转发方法会沿着该分组的路径改变。

数据网络可以在动态环境中的路由设备之间建立，例如，路由设备位于移动单元上，如车辆、船只、飞行器、卫星等。

路由设备可以位于飞行器上。路由设备被配置为与位于同一飞行器中的一个或多个终端设备建立数据连接以向这些终端设备提供数据服务(数据生产者和数据消费者、上传或下载数据等)。由多个路由器建立的数据网络实施上述路由方法以在位于不同飞行器上或不同位置的两个终端设备之间传输数据分组。

在一个示例中，提供了具有路由设备和与该路由设备通信连接的一个或多个终端设备的飞行器。该路由设备连接到其他飞行器上的其他路由设备。

附图说明

下文将结合以下附图来描述主题，其中，相同的标记表示相同的要素，在附图中：

图1是数据网络的示意性表示；

图2是数据分组转发机制的示意性表示；

图3是路由设备的部件的示意性表示；

图4是当实施图2的方法时执行的步骤的示意性表示；

图5是具有不同路由操作段的数据网络的示意性表示；

具体实施方式

下面的详细描述本质上仅仅是示例性的，并不旨在限制本发明和本发明的用途。此外，本发明无意受前述背景技术或以下具体实施方式中提出的任何理论的约束。

附图中的表示和图示是示意性的而不是按比例绘制的。相同的标记表示相同的要素。

通过对图示的回顾以及对随后的具体实施方式的回顾，可以更好地理解所描述的主题。

图1示出了数据网络10的示例性实施例。数据网络10特别可以是包括至少一些移动组件的网络，例如，在飞行设备(例如，商用飞行器、军用飞行器、卫星等)之间建立的机载移动自组织网络中，其中一些飞行设备具有到地面网络基础设施的连接。

机载移动自组织网络通常涵盖飞行设备之间以及飞行设备与地面之间的间歇性无线链路、射频(RF)链路以及自由空间光系统(FSO)链路：无线链路是间歇性可用的，因为飞行设备仅在特定的时隙并置，这些时隙可能是预先已知的，也可能是未知的。假设在机载移动自组织网络中，飞行设备可以通过经由RF链路的本地操作或基于离线数据(比如地理位置(由比如广播式自动相关监视ADS-B等系统提供)、飞行任务和轨道)来动态地发现彼此，从而形成具有扁平层次结构的网络。

上面提到的机载移动自组织网络的情景通常涵盖具有不同动态级别的多跳无线网络。一方面，军用飞行器多跳无线网络是高度动态的，包括编队阶段和飞行阶段，在这些阶段，飞行器具有更随机的移动(例如，在战斗情况下)。另一方面，涵盖商用飞行器或空间设备(例如，低地球轨道卫星)的多跳无线网络具有更可预测的行为，因为飞行器移动性是基于预定义的路线定义的，而卫星在轨道上移动。然而，由于集群效应、链路的条件(例如，由于通信节点之间的距离)以及链路的间歇性可用性(例如，卫星间链路可能在任何一对卫星之间间歇性地存在)，一些动态行为是可以预期的。

取决于这样的网络的动态性质，通常应用MANET或DTN路由。在前一种情况下，路由的目的是找到并维持任何一对节点之间的端到端路径。这种目标可以通过反应式或主动式方法来实现。主动式路由协议(例如，优化链路状态路由协议OLSR、基于反向路径转发的拓扑传播TBRPF、以及目的地排序距离矢量路由DSDV)旨在通过以固定的时间间隔传播路由更新来保持网络中每一对节点之间的一致且最新的路由信息。每个节点必须在路由信息表中维持该信息。反应式协议只有在应用程序提交业务请求时才会了解如何在网络中转发业务。由于主动式路由算法在任何传输请求到达之前就维持了关于端到端连接性的知识，因此这样的请求比在反应式方法中更快地得到服务，这意味着主动式协议通常比反应式协议具有更低的等待时间。然而，由于所了解到的网络拓扑结构会随着时间的推移而变化，因此主动式协议也会导致更高的开销来维持拓扑结构的最新情况。

另一方面，反应式路由协议(例如，自组织按需距离矢量路由AODV、动态源路由DSR、以及临时有序路由算法TORA)仅在节点通过发起路线发现过程进行请求时才建立到给定目的地的路线。一旦建立了路线，节点就会保持它，直到目的地不再可访问或路线过期。在控制开销和功耗方面，反应式协议往往比主动式协议更高效，因为路线仅在需要时创建。

然而，如果链路间歇性导致在每个时刻都不存在端到端路径的情况，从而导致频繁的分区和高排队延迟，则任何类型的MANET协议都将失败。这种情况可能是由于节点移动性、省电方案、物理障碍以及黑暗区域(即，在重叠信道中操作的接入点过度拥挤或根本没有基础设施)造成的。对于这些高度动态的情景，已经提出了几种机会路由协议，利用相同消息的副本来对抗节点之间未来通信机会的固有不确定性。为了谨慎使用可用资源并达到较短的延迟，许多协议使用本地收集的关于节点行为的知识进行转发决策，以预测哪些节点可能递送内容或使其更接近目的地。为此，节点必须有足够的处理能力和存储空间来保持数据，直到找到另一个好的中间载体节点或目的地，遵循存储-携带-转发(SCF)范式。

所提出的机会路由方法的范围从使用节点移动性来泛洪网络以实现快速递送(例如，传染路由)到基于以下因素来控制这种泛洪以实现相同的结果：相遇历史(例如，使用相遇历史和传递性的概率路由协议PROPHET)、优化的递送概率(例如，喷洒和等待)、优先化、或推断不同的社会互动水平。在任何情况下，所有机会路由协议都遵循反应式方法，因为关于考虑转发/复制分组的最佳邻居集合的路由决策只有在接收到分组时才会进行。进行这样的本地决策的需要加上当分组到达时最佳下一跳可能不可用的事实导致较差的转发(当分组被传递到次优邻居时)或长时间延迟(为了等待最佳邻居可用)。这种性能限制可以通过允许节点了解邻居节点的访问模式以及每个节点在短时间内到达期望目的地的概率来减轻。后者可能需要在邻居节点之间交换关于可达性的信息，这只有在网络动态得到调节的情况下才可行。

与现有的区域路由协议相比，本文描述的路由方案并不假定将网络固定划分为稳定区域(例如，区域的大小由长度为ρ的半径确定，其中ρ是到区域周界的跳数而不是物理距离)。本文描述的路由设备的优选用例是具有动态变化的网络拓扑结构的移动实体，因此将数据网络静态分割为稳定和不稳定区域(或段)可能不足以提高路由的性能。

而是，数据网络10实施这样的路由协议，即，该协议能够基于其推断网络在不同网段中的动态的能力而在这样的段中具有不同的行为(分组复制、反应式路由、主动式路由)。

图1示出了数据网络10。多个终端设备11至15充当数据生产者和/或数据消费者并且经由路由设备101至106交换数据。每个终端设备11至15中经由数据链路连接到至少一个路由设备。路由设备经由数据链路111至120间歇性地相互连接。终端设备与路由设备之间的数据链路可以是无线或有线连接。路由设备之间的数据链路优选是无线连接。

所提出的协议旨在减轻反应式、主动式以及机会路由协议的局限性，即：i)避免反应式协议的探测阶段的开销；ii)减少主动式路由协议的链路状态信息传播的开销；以及iii)降低机会路由协议的成本(复制)。

所提出的协议允许部署不同类型的网络，从非常动态的网络(例如，军用飞行器)到不太动态的网络(卫星星座)，再到可预测的网络(多跳商用飞行器)，而无需开发和维护不同的路由协议。

在每个提到的用例中，所提出的协议旨在通过结合主动式方法的较低等待时间、反应式方法的较高适应性以及机会协议的较高鲁棒性来提供更高的性能。

在现有的网络范式中，所提出的路由协议旨在支持互联网中所使用的基于主机的传统通信模型，比如新的以信息为中心的范式，比如命名数据网络(NDN)。这意味着所提出的协议能够找到将分组(IP数据分组或NDN兴趣分组)递送到其目的地的最佳方式，在前一种情况下，目的地是接收者主机，并且在后一种情况下是数据源。

本文参考数据网络10描述的路由设备特别实施了以下三个方面：支持基于主机和基于名称的通信，从而在路由设备之间存在间歇性连接的情况下操作；将反应式机制与主动式机制相结合，旨在提高以低延迟递送分组的概率。

图2总体上描述了存储-喷洒-聚焦转发方法以及邻居节点(路由设备)之间的相关通信。参考由大写字母A到E指示的五个阶段对该方法进行了描述。

图2展示了不稳定邻域中的转发操作：在该示例中，转发引擎在阶段A以喷洒模式启动，因为路由引擎100的FIB没有目的地的条目。基于路由设备100与三个邻居路由设备101、102和103(从路由设备100的NIB收集的)之间朝向期望目的地的连接性，仅选择两个邻居路由设备101、102并进一步考虑用于数据转发。路由设备100向路由设备101、102发送消息。在阶段A，路由设备100以喷洒模式操作并向路由设备101、102发送消息。在阶段B，路由设备100对到邻居路由设备的链路进行监测并从邻居路由设备101、102接收反馈。从这两个邻居路由设备接收的反馈导致新条目被添加到路由设备100的FIB。该条目用于下一组分组(转发引擎以聚焦模式操作)，如阶段C所示，并且路由设备100将数据分组直接传输到路由设备101，即，路由设备100在阶段C以聚焦模式操作。现在假设在一些传输之后，路由设备100、101之间的链路的等待时间开始增加。然后，该协议通过仍然在聚焦模式下使用FIB中的当前邻居(即，路由设备101)，但也在喷洒模式下从NIB中选择一组邻居(即，路由设备104、105)来使用聚焦操作和喷洒操作的组合，如阶段D所示，并且目的是提高以低等待时间递送的概率。在接收到新的传输的反馈(来自路由设备104、105)之后，新邻居被添加到路由设备100的FIB，并且性能不佳的邻居被从FIB中移除(在本示例中，路由设备105被移除)。此后，转发引擎再次进入对两个邻居路由设备101、104的聚焦操作模式，如阶段E所示。

图3示意性地示出了路由设备100的结构。

路由设备100包括具有相关联的路由信息库RIB 145的路由引擎140、具有相关联的邻居信息库155的邻域引擎150以及具有相关联的转发信息库165的转发引擎160。

路由引擎140从一个或多个邻居路由设备101接收具有目的地状态信息DSI的列表，并且向一个或多个邻居路由设备101发送具有其自己的DSI的列表。DSI存储在RIB中。邻域引擎150向路由引擎140和转发引擎160提供稳定邻居路由设备的列表，并且向转发引擎160提供包括邻居路由设备的连接性的列表。转发引擎接收数据分组和/或确认分组(当应用IP技术时)或者兴趣分组和/或数据分组(当应用NDN技术时)。接收到的消息基于FIB中的条目被转发。在将消息传输到邻居路由设备101、102之前，可以将其存储在队列中。如图3所示，可以将一个队列(例如，实施为高速缓存)分配给到邻居路由设备的每个传出链路。

图4示出了图3的转发引擎140的操作过程。

转发引擎实施存储-喷洒-聚焦(SSF)策略(如参考图2所描述的)，该策略利用所收集的关于目的地的可达性的信息和本地上下文信息，目的是减少等待时间并提高递送概率。存储-转发意味着当通往最合适的下一跳的接口关闭时，数据分组被缓存。在这种情况下，分组被存储，直到合适的下一跳可用(例如，无线接口启动)或者直到分组有效性期满。分组有效性参数由应用程序设置。聚焦意味着只通过这样的一组邻居到达目的地，即，当前节点具有关于如何通过该组邻居到达目的地的信息(成本、等待时间)。喷洒意味着当前节点旨在通过与目的地有高概率接触的一组节点到达目的地。

转发决策(喷洒-聚焦)基于两种数据结构：转发引擎保持的转发信息库(FIB)和邻域引擎保持的邻居信息库(NIB)。前者用于聚焦操作模式，而NIB用于喷洒操作模式。FIB中的每个条目都与特定的目的地ID相关，并且具有以下格式：

FIB条目：{目的地ID；{邻居ID，等待时间}的列表}。

当路由信息库(RIB)中存在该目的地的条目时，或者作为喷洒操作的结果，可以创建FIB中的条目。在前一种情况下，等待时间字段被设置为等于RIB中对应条目的距离字段。作为喷洒操作模式的结果，FIB中的一些条目也可以看到它们的邻居列表被改变，从而改变了聚焦操作中要考虑的邻居集合。每个条目中的等待时间值是基于往返时间(RTT)或双向等待时间更新的，双向等待时间测量为转发分组与接收响应(在IP数据分组的情况下为ack，或者在NDN兴趣分组的情况下为数据分组)之间经过的时间。处于不稳定区域的目的地或由UDP业务提供服务的目的地将不在FIB中表示，这意味着去往这些目的地的分组将始终以喷洒操作模式转发。

FIB中的条目可以由表示目的地的哈希值来索引。因此，转发引擎能够处理去往由IP地址定义的特定目的地的数据分组(基于主机的方法)以及去往由数据名称定义的特定数据源的兴趣分组(命名定义网络)。为了支持IP和NDN两种范式，在接收到IP数据分组或兴趣分组时的第一个操作是计算分组中携带的目的地ID的哈希值，该哈希值用于在FIB中查找最佳条目集(图4中流程图中的步骤1和2)。换句话说，从空闲状态开始，路由设备在步骤1中接收数据IP分组或兴趣NDN分组并在步骤2中创建分组目的地的哈希值。

转发机制的目的是减少开销(副本的数量)，同时确保递送的低等待时间。为了实现这种目标，转发机制的目的是通过对FIB中的信息比NIB中的信息给予更多的优先权来尽可能地以聚焦操作模式处置每个目的地。在步骤3中，转发引擎在FIB中搜索与要转发的分组的目的地相关的条目。这提供了一组下一跳，在步骤4中，基于这些下一跳将分组副本转发到(多个)下一跳。当新的分组到达时，从FIB中提取一组合适的下一跳，目的是保持成功的概率接近1(以低延迟达到高递送概率)。如果这是不可能的(在FIB中没有该目的地的条目，或者现有条目不足以确保低等待时间的高递送概率)，则可以从NIB中提取一组合适的下一跳(步骤5)，其概率取决于邻居的连接性(邻居遇到目的地的概率)以及邻居必须转发分组的概率。随着在步骤5中从NIB读取该组下一跳，在步骤6中存储分组并且在步骤7中将分组副本转发到下一跳。从NIB中提取一组合适的下一跳意味着转发引擎基于邻居稳定性和邻居连接性选择邻居子集：

邻居稳定性＝f(可用性，容量，链路质量)

在步骤4或7中转发分组之后，转发节点可以接收反馈分组(对于TCP/IP数据分组的ack和对于兴趣分组的数据分组)(步骤8)，这些反馈分组被用来估计朝向目的地的延迟(步骤9)。基于这些反馈分组和估计的延迟，转发节点(即，当前路由设备)在步骤10中更新对应FIB条目的值或从FIB中添加/移除条目。添加新的FIB条目(或在已经存在的FIB条目中添加新的邻居)可能发生在作为喷洒操作的结果接收到反馈时。从FIB条目中移除FIB条目或特定邻居可能发生在在聚焦模式下从该邻居接收到的反馈显示等待时间增加时(步骤8至10)。

除非另有规定，接收到的反馈分组(对于TCP/IP数据分组的ack和对于NDN兴趣分组的数据分组)也基于它们的目的地ID被转发。例如，NDN中的数据分组可以遵循存储在未决兴趣表(PIT)中的信息。

再次参考图3，路由引擎140负责计算能够以特定成本到达特定目的地的一组下一跳。这种计算是基于稳定邻居之间交换的可达性信息来完成的。节点的稳定性由邻域引擎150规定。该路由引擎操作由三个主要状态定义：从每个邻居节点接收目的地状态信息(DSI)列表(来自路由设备101的传入列表)；计算要包括在路由信息库(RIB)中的邻居子集；以及向邻居节点通告DSI(去往路由设备102的传出列表)。

该路由引擎操作基于稳定邻居之间交换的可达性信息。因此，DSI的接收会基于通告邻居的稳定性进行过滤，这意味着不稳定邻居发送的DSI将被忽略。

每个DSI提供关于经由某个邻居节点到达目的地的成本的信息以及关于DSI被创建的时间的信息。DSI基于以下格式：

DSI格式：{目的地ID，邻居ID，成本，时间戳}

DSI时间戳允许节点推断它们到目的地的距离。如果去往目的地的业务基于不提供反馈信息的传输协议/方法(比如UDP)，则该信息非常有用。

为了允许节点使用DSI时间戳来推断它们到目的地的距离，所有网络设备必须在时间上同步，以防它们具有不同的系统时间。我们可以假设，在许多用例中，所有节点将具有相同的系统时间。但即使在这种情况下，时钟也可能会漂移。因此，我们可以假设存在允许节点同步它们的时钟的过程。第一种假设是使用网络时间协议(NTP)。然而，NTP需要客户端-服务器操作，这意味着所有节点在开始其操作之前都应该同步其时钟，并且同时还要与NTP服务器连接。第二种假设是，节点具有基于GNSS(全球导航卫星系统)的单元，该单元可以被查询时间，使得节点中的每一个都是Stratum 1时钟。对于室外网络来说，这是可行的解决方案，许多自组织网络就是如此。第三种假设是使用能够以足够的性能同步N个时钟的替代协议。

目的地可以是标识主机或子网的IP地址，或者是数据名称(例如，如NDN中所定义的)，这意味着该路由引擎操作与目的地的类型(基于主机或基于名称)无关。出于这个原因，当路由引擎(从本地服务)获得本地通告时，它的第一个操作是计算与数字向量相对应的哈希值来表示目的地(IP地址或名称)。这意味着目的地ID具有以下格式：

目的地ID＝[数字，……]＝哈希(目的地)

一些被接受的DSI可以提供关于到达同一目的地ID的替代邻居的信息。在这种情况下，路由引擎基于以下各项来选择通告邻居的子集：邻居稳定性，如邻域引擎所提供的；DSI的成本；以及DSI的时间戳。

选择机制是通过过滤掉具有低稳定性的邻居并通告具有高成本和旧时间戳的DSI(例如，基于配置度量的算法或能够推断成本、时间戳以及稳定性模式的神经网络)来完成的。所选择的邻居子集与基于所通告的DSI而计算的信息一起被放置在RIB中。RIB上的条目具有以下格式：

RIB条目：{目的地ID；{邻居ID，成本，时间戳，距离}的列表}

根据DSI中传输的信息，成本和时间戳存储在RIB中。基于时间戳，节点计算出距离，作为时间戳和DSI接收时间的函数。虽然时间戳和成本将被用于进一步通告该DSI，但距离将被传递给转发引擎。

关于DSI的通告，路由引擎利用存储在RIB中的信息来为每个存储的目的地定义DSI。在每个DSI中，所通告的成本等于存储在RIB中的成本加上表示由节点本身引起的成本的数字。如前所述，由此产生的DSI可以基于以下格式在“Hello”消息中广播给所有邻居：

所通告的DSI：{目的地ID，邻居ID，成本(接收成本+本地成本)，时间戳}

如图5所示，所提出的协议可能导致在网络中创建不同的行为区域。在稳定的区域/邻域中(图5的左侧)，节点基于所交换的DSI构建RIB，从而允许它们基于关于如何以一定成本到达有效目的地的知识做出更准确的转发决策。在不稳定的区域/邻域中(图5的右侧)，节点不交换DSI，并且因此需要利用所有可用的传输机会来转发分组：复制的分组旨在提高以低延迟递送分组的概率。所提出的转发引擎旨在通过保持尽可能低的复制数量并将其限制在数据网络的不稳定邻域或段来降低成本。在不稳定段中，数据分组和ack分组(TCP/IP技术)或兴趣分组和数据分组(NDN技术)在邻居节点之间交换。

再次参考图3，邻域引擎150基于关于每个邻居的以下信息集来收集关于节点的邻域的状态的信息：

可用性(例如，每次无线接触之间的时间，以及每次接触的持续时间)；

容量(例如，电池电量)；

连接性(例如，与网络中的任何其他节点的接触间时间和接触持续时间)；

链路质量(例如，平均吞吐量、误码率、接收信号强度指示)。

可用性为节点提供了关于到邻居的链路的有用性的信息。可用性由节点本身来推断。另一方面，连接性为节点提供了关于其邻居的连接程度的信息。该节点经由邻居发送的Hello消息获得关于连接性水平的信息。可用性和连接性两者都是基于类似的度量(比如接触间时间)来推断的。接触间时间度量(在可用性参数和连接性参数中)可以用于推断通过邻居的传输的等待时间，因为这种度量提供了关于邻居将分组传输到某个目的地所引起的延迟的信息。

测量活动通过节点广播的生存时间为一(1)的周期性Hello消息来执行。测量活动的结果被放置在由邻居ID索引的邻居信息库(NIB)中。每个条目包含一个元组，该元组具有以如下形式收集的关于邻居的所有信息：

NIB条目：{邻居ID，可用性，容量，连接性，链路质量}

邻域引擎使用NIB上的信息来推断每个邻居节点的稳定性。稳定性效用函数如下：

稳定性＝f(可用性、容量以及链路质量)

关于邻居的稳定性的信息被传递给路由引擎和转发引擎。后者还从邻域引擎接收关于每个邻居的连接性的信息。

虽然在前面的详细描述中已经介绍了至少一个示例性实施例，但是应该理解，存在大量的变化。还应当理解的是，一个或多个示例性实施例仅仅是示例，并不旨在以任何方式限制本发明的范围、适用性或配置。而是，前述详细描述将为本领域的技术人员提供用于实施本发明的示例性实施例的方便路线图。应当理解，在不脱离权利要求的范围的情况下，可以对示例性实施例中描述的要素的功能和布置进行各种改变。

此外，应当注意，“包括(comprising)”或“包括(including)”不排除任何其他要素或步骤，并且“一个(a)”或“一个(an)”不排除多个或复数个。进一步地，应当注意，参考上述示例性实施例之一描述的特征或步骤也可以与上述其他示例性实施例的其他特征或步骤结合使用。权利要求中的附图标记不应当被解释为限制。

附图标记清单

10 数据网络

11-15 终端设备

100-110 路由设备

111-120 数据链路

140 路由引擎

145 路由信息库

150 邻域引擎

155 邻域信息库

160 转发引擎

165 转发信息库

Claims (15)

1.一种用于在数据网络中路由数据分组的路由设备(100)，所述路由设备包括：

具有路由信息库(145)RIB的路由引擎(140)；

具有邻域信息库(155)NIB的邻域引擎(150)，其中，所述NIB被配置为包含所述路由设备(100)的邻居节点的至少一个条目；以及

具有转发信息库(165)FIB的转发引擎(160)，其中，所述FIB被配置为包含目的地的至少一个条目；

其中，所述路由设备(100)被配置为：

从第一数据分组中提取目的地值；

在所述FIB(165)中搜索所提取的目的地值；

当所述FIB(165)包含所述目的地值的条目时，根据所述FIB(165)中的所述条目转发所述第一数据分组；

否则，当所述FIB(165)不包含所述目的地值的条目时，从所述NIB(155)中选择第一组至少两个邻居节点并且以喷洒操作模式将所述第一数据分组转发到所选择的第一组至少两个邻居节点，其中，在所述喷洒操作模式中，所述转发引擎将所述第一数据分组转发到所选择的第一组至少两个邻居节点，所述至少两个邻居节点具有一定的概率与所提取的目的地接触；

在以所述喷洒操作模式转发所述第一数据分组之后，接收来自所选择的第一组至少两个邻居节点的反馈分组，并且基于来自所选择的第一组至少两个邻居节点的反馈来在所述FIB(165)中为所提取的目的地生成条目；

使用所述FIB(165)中所生成的条目来以聚焦操作模式转发第二数据分组，其中，在所述聚焦操作模式中，所述转发引擎根据所述FIB(165)中的条目将所述第二数据分组转发到邻居节点。

2.如权利要求1所述的路由设备(100)，

其中，所述路由设备(100)被配置为从多个邻居路由设备接收目的地状态信息DSI，并且进一步被配置为确定到每个邻居路由设备的连接稳定性值，并且进一步被配置为忽略从连接稳定性值低于预定稳定性阈值的邻居路由设备接收的DSI。

3.如权利要求1或2所述的路由设备(100)，

其中，所述路由设备被配置为在所述FIB(165)中为所提取的目的地生成所述条目，使得所述条目至少包含所述目的地值和经由其能够到达对应目的地的所述邻居节点。

4.如前述权利要求中任一项所述的路由设备(100)，

其中，所述路由设备(100)被配置为监测所述路由设备(100)与所述第一数据分组的所提取的目的地之间的数据传输过程的性能度量值；

其中，当所述性能度量值增加时，所述路由设备(100)被配置为根据所述FIB(165)中的条目继续将数据分组转发到所提取的目的地，并且另外基于所述路由设备(100)与邻居节点组之间的连接性特性从所述NIB(155)中选择第二组至少两个邻居节点并且以喷洒操作模式将所述第一数据分组转发到所选择的第二组至少两个邻居节点。

5.如权利要求4所述的路由设备(100)，

其中，所述路由设备(100)被配置为从来自所述第二组的所述至少两个邻居节点接收反馈分组，并且被配置为基于来自所述第二组的所述邻居节点的所述反馈在所述FIB(165)中为所提取的目的地生成条目。

6.如权利要求5所述的路由设备(100)，

其中，所述路由设备(100)被配置为以聚焦操作模式将所述第一数据分组转发到来自所述第一组的一个邻居节点和来自所述第二组的一个邻居节点。

7.如权利要求4至6中任一项所述的路由设备(100)，

其中，所述路由设备(100)被配置为当所述FIB(165)中的特定条目的数据传输的性能度量与同一目的地的至少一个其他条目的性能度量相比更高时，基于所述路由设备(100)与所述第一数据分组的所提取的目的地之间的数据传输过程的性能度量从所述FIB(165)中移除条目。

8.如前述权利要求中任一项所述的路由设备(100)，

其中，所述路由设备(100)被配置为：除非所述FIB(165)被填充了与从所述第一数据分组中提取的所述目的地值相对应的条目，或者当所述路由设备到所述第一组的所述邻居节点的连接被中断时，存储所述第一数据分组。

9.如前述权利要求中任一项所述的路由设备(100)，

其中，所述路由引擎(140)被配置为确定能够以预定成本到达预定目的地的一组下一跳。

10.如权利要求9所述的路由设备(100)，

其中，所述路由引擎(140)被配置为从与所述路由设备(100)直接互连的每个邻居节点接收目的地状态信息DSI的列表，向每个邻居节点通告自己的DSI的列表，并确定要包括在所述RIB中的邻居节点的子集。

11.如权利要求10所述的路由设备(100)，

其中，DSI包括关于经由某个邻居节点到达目的地的成本的信息。

12.如前述权利要求中任一项所述的路由设备(100)，

其中，所述目的地值是目的地节点或子网的地址；或者

其中，所述目的地值是数据名称。

13.如前述权利要求中任一项所述的路由设备(100)，

其中，所述邻域引擎(150)被配置为收集关于所述路由设备(100)的所述邻居节点中的每一个的状态的信息；

其中，所收集的信息包括以下参数：

所述邻居节点的可用性；

所述邻居节点的容量；

所述路由设备(100)与所述邻居节点之间的连接性；以及

所述路由设备(100)与所述邻居节点之间的链路质量。

14.如权利要求13所述的路由设备(100)，

其中，所述路由设备(100)被配置为重复发送消息以便确定所述参数中的至少一个参数的值。

15.如权利要求13或14所述的路由设备(100)，

其中，所述邻域引擎(150)被配置为基于所述可用性、所述容量以及所述链路质量来确定每个邻居节点的稳定性；

其中，所述邻域引擎(150)被配置为向所述路由引擎(140)和所述转发引擎(160)提供每个邻居节点的稳定性。

Images