CN102210126A - 使用聚集路由器密钥转发数据分组的方法和设备 - Google Patents

Abstract

用于支持分组交换网络的路由器(402，702)中转发接收的数据分组的方法和设备。基于从密钥管理器(400，700)收到的聚集路由器密钥和相关联的聚集有关的指令，在路由器中配置转发表(706a)。每个聚集路由器密钥表示目的地的集合。在收到包括从发送方密钥或路由器密钥所推导的入口标记的数据分组(P)时，匹配入口标记和转发表中的条目。根据还包括相关联的聚集有关的指令的找到的匹配表条目，为分组选择外出端口。随后，根据聚集有关的指令来创建出口标记，并且将附加有创建的出口标记的分组从选定外出端口发送到下一跳路由器。

Description

使用聚集路由器密钥转发数据分组的方法和设备

技术领域

本发明一般涉及用于支持诸如因特网等公共分组交换网络中数据分组的转发过程以使得能够避免不想要的数据分组的方法和设备。

背景技术

数字编码信息在各方之间通过IP(因特网协议)网络的基于分组的传送用于各种通信服务，如电子邮件消息传递、因特网浏览、话音和视频电话、内容流传送、游戏等。数字编码信息在发送方布置到数据分组中，分组随后通过传送路径向目标接收方传送。发送方与接收方之间的传送路径可包括各种网络、交换机、网关、路由器和接口。通信方经常称为“端主机”，可以是能够进行基于分组的IP通信的任何类型的设备，如固定和移动电话、计算机、服务器、游戏机等。在本描述中，术语端主机将概括表示任何此类通信设备。

连接到因特网或其它IP网络的端主机一般已被指派有IP地址形式中的转发身份，需要该身份用于路由沿传送路径引导到该端主机的任何数据分组。一般情况下，端主机也已指派有文本串形式中或多或少可理解的名称，例如，常规电子邮件地址或网址，如

其与实际用户/端主机或代表用户接收消息的另一主机的指派的IP地址相关联。包括DNS(域名服务器)服务器的层次结构的DNS系统用于检索特定主机名称的当前IP地址。因此，端主机能通过与其通信的主机名称来查询DNS系统，并且DNS随后将通过提供对应端主机的当前IP地址来回复。此类查询有时称为目的地查询、身份查询或地址查询，后者贯穿于本描述使用。

数据分组基本上配置有包含有效负载数据的数据字段和报头字段，发送端主机在报头字段中插入目标端主机的目的地地址，即，从DNS系统获得的IP地址。因此，基于分组报头字段中的目的地地址，每个数据分组沿适合传送路径，通过通常称为IP路由器的多个网络节点来路由。

除简单地接收和转发数据分组外，IP路由器也可能够执行其它功能，如安全性功能、分组调度和地址与协议的转换。此外，端主机可具有过滤器/防火墙功能性，用于例如根据一般由与端主机相关联的用户或管理员所做的设置来确定应接受还是丢弃进入的数据分组。

IP网络中的每个路由器一般情况下包括充当分别用于接收和发送数据分组的接口的入口和出口单元。路由器还包括用于基于路由器中定义的转发表来确定应将进入的数据分组发送到作为朝向最终目的地的“下一跳”的哪个路由器的路由选择或转发功能。如本领域中公知的，根据网络拓扑和当前业务负载，数据分组经常能沿多个备用路径来路由。

借助于对应的端口，在每个路由器中提供到“最近”相邻路由器的链路，并且基于拓扑信息和链路信息的分发，还在路由器中配置转发架构。每个端口能具有在其接口上配置的IP地址和IP掩码，并且路由选择协议用于在配置过程中在网络中的路由器之间分发此信息。随后，每个路由器从分发的拓扑信息来计算其自己的转发表，包含多个目的地IP地址和相关联的外出端口。由于每个进入的数据分组在其报头中具有目的地IP地址，因此，转发表用于从该IP地址查找转发表中的适合条目。转发表的主要功能因此是为每个进入分组确定适当的外出端口，从而引导到下一跳路由器。

在图1中，示出了位于IP网络中时常规IP路由器100的基本结构。除其它之外，IP路由器100包括入口部分100a、出口部分100b和此处示意表示为转发表100c的转发功能。出口部分100b包括分别通向路由器100直接连接到的不同相邻路由器A、B、C…的多个外出端口P_A、P_B、P_C…。任何进入的数据分组102具有有效负载字段PL和报头H，后者包含用于分组的目的地地址。

转发表100c由多个条目组成，每个条目包含IP掩码、IP地址和外出端口号。IP掩码可根据诸如FF.FF.FF.0或FF.FF.8.0等十六进制编码的串来定义。简要地说，通过应用逻辑“与”操作，合并报头H中的目的地地址和转发表100c中的IP掩码以便检测带有相同IP地址的匹配条目。此掩蔽机制的目的是聚集朝向几个不同目的地的业务，并且为聚集简化外出端口的识别。实际上，在比较和匹配目的地地址与条目时，比特掩码的工作类似于“通配符”。一旦找到匹配条目，便能根据该条目的端口号在外出端口上发出分组。

可能已从前一路由器(未示出)转发到路由器100的进入数据分组102因此先在入口单元100a中接收。随后，基于报头H中的目的地地址并使用转发表100c和上述逻辑“与”操作，确定应将分组发送到哪个下一路由器。在此示例中，进入分组102具有目的地IP地址，该地址在与掩码合并时，匹配转发表100c中具有端口号Pc的条目的IP地址。分组102因此在连接到路由器C的对应端口上发出，路由器C在此情况下是下一跳路由器。

如上所述，路由选择协议用于在IP网络中的路由器之间分发拓扑和链路信息。当前使用的路由选择协议配置成获得“弹性”，即，在原始路径中链路或节点故障的情况下，分组必须在不同的路径中重新被路由。路由选择协议还配置成方便路由器管理，因为配置路由器一般情况下是烦琐的任务，该任务通常最好是得以简化。因此，在链路或节点中检测到故障的情况下，路由选择协议将重新配置受影响的路由器中的转发表，并且同时将信息分发到路由器，由此简化管理。为获得伸缩性(其在其它情况下在路由选择架构中是固有问题)，路由选择过程能使用基于上面分层的比特屏蔽方案的路由的聚集，这在本领域是公知的，因此不必在此进一步描述。

然而，如下所述，IP网络和因特网的一个主要问题是安全性支持通常不充分。从某种意义上说，上述弹性有时能够使通过网络传播分组变得“太容易”。这是因为当前路由选择架构和协议最初设计用于“友好”环境，即，假设在IP网络中没有“非法”或“不道德”用户在通信，并且数据分组的传送无需保护。不过，人们发现将各种安全性解决方案添加到IP架构以便保护传递的数据是必需或合乎需要的，如在低层上的IP-sec及在更高层上的TLS(传输层安全性)。这些协议能够提供数据分组的认证和加密。此外，MPLS(多协议标签交换)也是用于构建第3层VPN(虚拟专用网络)以确保安全通信的解决方案。在VPN的情况下，当使用内部网时，要求专用寻址，并且稍微将网络与公共因特网隔离，使得外部未经授权的主机不允许到达并与附连到内部网的主机通信。

在路由选择协议中提供安全性的其它以前解决方案包括：在路由器之间的安全通信，使得恶意实体不能偷听、操纵或模仿路由器；路由器端口之间建立IP-sec隧道以保护路由器之间的分组传输；以及第2层上的链路安全性，例如，根据IEEE 802.1AE或IEEE 802.10。也能使用各种使用密码密钥的认证过程以增强安全性，如根据DNSSec(DNS安全性)、HIP(主机身份协议)及CGA(密码生成的地址)。然而，虽然针对不想要的业务的保护被用于某些应用(例如，对电子邮件的垃圾邮件过滤)，但在公共IP基础设施中通常未提供对抗侵害性的端主机和不想要的数据分组的基本保护。

由于内部转发身份(即IP地址)以上述方式公开端对端分发，任何端主机基本上能够通过因特网将消息和数据分组发送到任何其它端主机，导致泛洪、垃圾邮件、病毒、欺诈和所谓的“拒绝服务”(DoS)威胁的公知问题。因此，通常具有的问题是任何端主机能在接收端实体完全失控下传播数据分组，并且诸如因特网等公共分组交换网络在IP基础设施中没有防止来自可能恶意或不道德的最终用户的数据分组被路由到接收器的机制。

但是，在端主机或链路层中能够添加或多或少复杂的功能性以便限制连接，如过滤器/防火墙或诸如此类。然而，这些解决方案是“最后的防线”解决方案，意味着不想要的数据分组的传输仍能沿整个发送器-接收器路径占用网络资源，而分组却无论如何总是在接收器被丢弃。

在带有许多端主机和多个路由器的通信系统中另一个问题是如果使用的安全性解决方案既不能采用上述IP地址的比特掩蔽、也不能采用其等效物来实现路由的聚集，则路由器中的转发表将包括数量巨大的条目。此类大转发表处理能够变得极其复杂，要求大量的资源用于存储、处理和通信，这一般可导致不希望有的成本和延迟。特别是，如果在路由器中引入密码安全性机制，开销将例如由于密码密钥的管理和/或密码处理而甚至变得更大，由此使得路由器中的复杂性降低变得更加合乎需要。

发明内容

本发明的目的是解决上面概述的问题的至少一些。还有一个目的是获得避免分组交换网络中传送不想要的数据分组、同时能够使用路由器中方便大小的转发表的机制。这些目的和其它目的能通过提供如随附独立权利要求中定义的方法和设备而实现。

根据一方面，提供了一种用于支持分组交换网络的路由器中接收的数据分组的转发的方法。在此方法中，基于从密钥管理器接收的聚集路由器密钥和相关联的聚集有关的指令，在路由器中配置转发表。每个聚集路由器密钥表示目的地或路由器的集合。在收到包括从发送方密钥或路由器密钥所推导的入口标记的数据分组时，应用匹配函数到入口标记和转发表中的至少一个条目以便查找匹配的表条目，所述条目包括候选入口密钥和外出端口指示。根据还包括相关联的聚集有关的指令的找到的匹配表条目，为分组选择外出端口。随后，根据匹配的表条目中的聚集有关的指令来创建出口标记，并且将附加有创建的出口标记的分组从选定外出端口发送到下一跳路由器。

根据另一方面，提供了一种分组交换网络的路由器中的设备，用于支持接收的数据分组的转发。路由器包括转发单元，该单元适用于基于从密钥管理器接收的聚集路由器密钥和相关联的聚集有关的指令来配置转发表，每个聚集路由器密钥表示目的地的集合。路由器还包括入口单元和出口单元，入口单元适用于接收包括从发送方密钥或路由器密钥所推导的入口标记的数据分组，出口单元用于将数据分组发送到下一跳节点。

转发单元包括标记匹配单元，标记匹配单元适用于将匹配函数应用到接收的入口标记和转发表中包括候选入口密钥和外出端口指示的至少一个条目以便查找匹配的表条目。标记匹配单元还适用于根据还包括相关联的聚集有关的指令的找到的匹配表条目，为分组选择外出端口。转发表还包括标记创建单元，该单元适用于根据匹配表条目中的聚集有关的指令来创建出口标记，以及将出口标记附加到分组，分组要由出口单元从选定外出端口发送到下一跳路由器。

路由器中的上述方法和设备能够根据不同实施例进行配置。在一个实施例中，匹配函数包括应用标记推导函数TDF到表条目中的候选入口密钥以推导候选入口标记。随后，如果候选入口标记满足与分组中接收的入口标记的预定关系，则认为找到匹配。预定关系可以是相等，即，如果候选入口标记等于分组中的入口标记，则认为找到匹配。

在另一个实施例中，通过应用另一标记推导函数TDF′到匹配表条目中的出口密钥，创建出口标记。接收的数据分组可还包含与转发表中条目或条目集合相关联的密钥索引，并且密钥索引用于查找适当的一个条目/多个条目以便应用匹配函数。

在进一步的实施例中，通过将从匹配表条目中一个或多个出口密钥所推导的一个或多个另外的子标记并靠着接收的入口标记附加到分组以执行聚集，或者通过从分组删除一个或多个另外的子标记以执行解聚集，可创建出口标记。还可通过在执行聚集时应用预定的合并函数到接收的入口标记和一个或多个另外的子标记来创建出口标记。例如，合并函数可以是串连或XOR函数。

目的地密钥和路由器密钥的分层方案也可用于执行路由的聚集。在该情况下，通过将接收的入口标记换成从匹配表条目中出口密钥所推导的新标记、以及还添加相关联的聚集信息到出口标记，可创建出口标记，其中聚集信息能够用于确定原始目的地。

上面的分层路由器密钥方案可借助于函数f(p，q)从根值(x)生成，其中p是当前树层次上方节点位置的路由器密钥值，以及q是指示当前树层次内节点位置的整数。端主机的目的地密钥对应于树结构的叶，以及叶上方在一个或多个树层次上的任何f值能够用作聚集路由器密钥。结果的密钥方案可由能够沿从根(x)向下的路径、根据以下链：(x，f(x)，f(f(x))，…，f(f(…f(x)…)))所计算的密钥值来组成。

根据仍有的另一方面，在密钥管理器中提供了一种用于支持分组交换网络中在路由器转发数据分组的方法。在此方法中，为连接到网络中接入路由器的端主机登记目的地密钥，并且确定分别能够执行路由聚集和解聚集的路由器的位置。还创建聚集路由器密钥和相关联的聚集指令，每个聚集路由器密钥表示目的地的集合。随后，分发聚集路由器密钥和相关联的聚集指令到路由器以便执行路由聚集和解聚集，由此使得路由器能够基于分发的信息来配置它们自己的转发表。

根据仍有的另一方面，在密钥管理器中提供了一种用于支持分组交换网络中在路由器转发数据分组的设备。此设备包括网络控制单元，该单元适用于为连接到所述网络中接入路由器的端主机登记目的地密钥，并且还适用于确定分别能够执行路由聚集和解聚集的路由器的位置。密钥管理器设备还包括密钥分发器，密钥分发器适用于创建聚集路由器密钥和相关联的聚集指令，每个聚集路由器密钥表示目的地的集合。密钥分发器还适用于分发聚集路由器密钥和相关联的聚集指令到能够执行路由聚集和解聚集的路由器，由此使得这些路由器能够基于分发的信息来配置它们自己的转发表。

密钥管理器设备可还包括地址查询管理器，地址查询管理器适用于从查询端主机接收有关目标端主机的地址查询。地址查询管理器还适用于通过应用密钥推导函数KDF至少到与目标端主机相关联的目的地密钥来创建发送方密钥，以及将创建的发送方密钥发送到查询端主机以响应地址查询。由此，查询端主机能够通过将从发送方密钥生成的发送方标记附加到传送的数据分组，将数据分组传播到目标端主机，发送方标记将传送的数据分组引导到目标端主机。

从下面的详细描述，本发明的另外的可能特征和优点将变得明白。

附图说明

下面将通过示范实施例并参照附图更详细地描述本发明，其中：

-图1是示出根据现有技术的IP网络中常规路由器的示意框图。

-图2示出从发送端主机A到接收端主机B路由数据分组的典型传送路径情形，其中能够利用本发明。

-图2a示出根据一个实施例的示范转发表的一部分。

-图3示出一示范网络拓扑和传送情形，其中聚集路由器密钥用于支持分组的转发过程。

-图3a和3b-c分别示出图3的传送情形的分组中能如何保留接收端主机的最终目的地地址的两个不同实施例。

-图4是根据进一步的实施例示出在转发从端主机A发送的数据分组时能够如何在路由器中使用聚集的框图。

-图5是根据仍有的另一个实施例的流程图，带有密钥管理器支持分组交换网络的路由器中数据分组的转发过程而执行的过程中的步骤。

-图6是根据仍有的另一个实施例的流程图，带有在分组交换网络中路由器为执行数据分组的转发过程而执行的过程中的步骤。

-图7是根据进一步的实施例更详细示出分组交换网络中路由器和密钥管理器的示意框图。

具体实施方式

本发明提供一种分组转发方案，该方案在通过转发架构中的安全性解决方案来保护端主机免于接收不想要的数据分组的同时允许路由的聚集，所述解决方案避免使用传送的分组的地址字段中的常规IP地址。相反，与目标端主机相关联的目的地密钥和与目的地密钥及网络拓扑相关联的预配置路由器密钥用于通过IP网络来路由数据分组。从上述目的地密钥和路由器密钥推导的标记被插入传送的分组的报头中，例如，在地址字段中，并且路由器随后能够从分组中的标记来确定目的地密钥或路由器密钥以执行转发操作。

在使用此类方案时，能够将分组路由到正确目的地且同时使得端主机能够保护自身免于不想要的分组的要求将自然暗示使用与所有路由器中各个端主机相关联的目的地密钥和转发表中的对应条目。因此，路由的聚集不能如在使用常规IP寻址方案时一样以常规方式获得。

相反，通过在传送的分组中附加从表示多个路由或目的地的集合的特殊聚集路由器密钥所推导的标记，获得路由的聚集。随后，路由器能够根据路由器的转发表中匹配条目中的聚集有关的指令，从分组更改、添加或删除此类标记以分别在该路由器中执行聚集或解聚集。由此，与其中提供表条目以用于网络中每个端主机的路由器中不采用路由聚集相比，通过包括此类聚集路由器密钥，能够降低路由器中转发表的大小。在此描述中，“聚集”暗示朝向增加数量的目的地的路由选择，并且“解聚集”暗示朝向减少数量的目的地的路由选择。

图2中根据下述实施例示意示出一示范传送情形，在通过带有路由器R的网络传送数据分组时基本上涉及了以下节点：连接到接入路由器R1的发送端主机A、可能可在传送路径中使用的多个中间路由器R及接收端主机B连接到的接入路由器Rx，接入路由器R1由此是网络中的“第一跳路由器”，并且接入路由器Rx是“最后一跳路由器”。还使用DNS服务器系统来处理地址查询Q和一般将路由选择信息I分发到路由器。在下面的描述中，术语“密钥管理器”用于概括表示DNS系统或任何其它类似功能单元或系统。

根据下面要描述的实施例，安全性解决方案能够构建到网络中路由器使用的转发架构的核心协议中。通常，例如如上所述，通过公共分组交换通信网络传送的任何分组必须通过传送路径中路由器的转发平面中的转发机制。通过要在下面描述的在路由器的转发平面内嵌入分组转发控制机制，结果安全性将在IP基础结构中有效地实施以控制通过该路由器的任何分组的路由选择。

简单地说，使用与目标端主机相关联的预定义隐式目的地密钥和与目的地密钥和网络拓扑中路由器位置相关联的预配置路由器密钥，而不使用显式IP地址通过IP网络来路由数据分组。密钥管理器因此登记作为数据分组的可能接收器的端主机的此类目的地密钥。在此过程中，视实现而定，目的地密钥可由密钥管理器来指派，或者由端主机来选择。

密钥管理器随后将提供对应发送方密钥而不是IP地址以响应来自查询端主机对目标端主机的“地址查询”或诸如此类。在此描述中，术语“地址查询”应理解为对能够用于授权传递数据分组到目标端主机的信息的任何查询。

通过至少应用“密钥推导函数KDF”到目标端主机的目的地密钥，并且也可选择性地应用到查询端主机的身份，密钥管理器创建发送方密钥，这将在下面更详细描述。备选的是，通过应用KDF到与目的地密钥有关并且可能也与其它端主机的目的地密钥有关的另一密钥以获得多个路由或目的地的聚集，可创建发送方密钥。目标端主机的目的地密钥因此实际上在提供到查询端主机的发送方密钥中被“隐藏”。这能够通过使用单向函数或哈希函数作为KDF来获得。

随后，查询端主机还通过应用“标记推导函数TDF”到发送方密钥从获得的发送方密钥来推导发送方标记，并在与接收目标端主机的至少正在进行的数据流或会话的每个传送的数据分组的报头中附加发送方标记。发送方标记因此隐式编码目标端主机的目的地密钥。备选的是，密钥管理器可推导发送方标记并将它直接输送到发送方。TDF可同样地是单向函数或哈希函数。

此外，密钥管理器基于登记的目的地密钥和网络拓扑来创建不同路由器密钥，并且将路由器密钥分发到IP网络中的路由器以形成在路由器中创建转发表的基础。还根据网络拓扑中的路由器位置，确定哪些路由器分别能执行路由聚集或解聚集。不同的准则能够用于决定应在网络拓扑中何处执行聚集/解聚集。一种方式是使用表大小作为执行聚集的需要的指示符。然而，也能够应用各种其它方法以确定聚集/解聚集的放置，这在本描述的范围之外。在一些情况下可确定路由器网络的分层树状拓扑，使得路由器定位在拓扑中不同的分层级别。

通过具有能够在哪些路由器执行聚集或解聚集的详细知识，并且还具有已登记目的地密钥的每个端主机的网络位置，密钥管理器能够创建“聚集路由器密钥”，即，表示多个目的地的集合并且能够用于网络拓扑中不同分层层次的路由器中路由选择的密钥。这些聚集路由器密钥由此例如在配置过程中分发到适当路由器。

路由器随后能借助于分发的路由器密钥来配置其自己的转发表。如上所指出的，基于其中能够执行聚集或解聚集的网络中路由器的位置，创建路由器密钥以降低或限制路由器的转发表中的条目数量，其中，至少一些分发的路由器密钥是与网络中多个目的地或路由器的组相关联的聚集路由器密钥。

密钥管理器还定义和分发与每个聚集路由器密钥相关联的、要包括在包含聚集路由器密钥的任何转发表条目的策略字段或诸如此类中的聚集有关的指令。此指令基本上告诉路由器是否及如何执行聚集或解聚集(例如，通过更改分组中现有路由器标记，或者通过分别对/从分组添加或删除一个或多个路由器标记，根据下面将更详细描述的不同可能实施例)。

可选的是，密钥管理器也可分发密钥索引以包括在转发表中，每个密钥索引与带有不同路由器密钥的表中的一行或多行相关联，以便以下面要描述的方式有利于转发操作。实际上，密钥管理器基本上能够将密钥索引指派到每个路由器密钥。

因此，路由器中的转发表具有带有路由器密钥、对应外出端口和可选密钥索引的条目。带有聚集路由器密钥的表条目也在策略字段或诸如此类中包含相关联的聚集有关的指令，如上所述，其基本上规定路由器应执行聚集或解聚集。

在此描述中，外出或转发的分组中的标记通常称为从“出口密钥”推导的“出口标记”，而进入或接收分组中的标记称为“入口标记”。此外，“入口密钥”是已从其推导收到的入口标记的密钥。

在已收到包含入口标记的数据分组的路由器执行的转发操作中，通过例如逐条目使用预定TDF，匹配入口标记和转发表中的入口密钥，以及在找到匹配条目时，选择该条目中的对应外出端口用于发送分组。路由器还检查匹配表条目是否包含聚集有关的指令，例如，规定路由器应更改收到的路由器标记，或者对/从分组添加或删除一个或多个路由器标记，这将在下面描述。在外出端口上将分组发送到下一跳路由器前，将例如从匹配的表条目中显式出口密钥所推导的或者根据相关联聚集有关的指令所推导的出口标记由此附加到分组报头。

如果在表中未找到匹配条目，则可根据预定义的“默认策略”来处理分组，例如，规定丢弃且不再转发分组。在不知道适当密钥的某一未经授权发送端主机试图传播插入了“虚假”标记的数据分组时，路由器一般情况下将采用此类策略。

在下一跳路由器收到分组时，上述过程基本上将重复进行。如果使用密钥索引，则接收的分组的入口标记中的密钥索引将直接指向转发表中的一个条目或有限的条目集，由此识别所述条目/多个条目中的入口密钥。随后，路由器能够将上述匹配操作限于密钥索引识别的入口密钥。

以此方式，通过不向未经授权方显露目的地/发送方/路由器密钥，截获能够由他人用于传播数据分组的显式端主机地址或身份是不可行的。因此，除非未经授权方正确“猜测”到有效的密钥或标记(这是极其不可能的)，否则，基本上能够避免未经请求的数据分组到那些端主机。因此在传送路径中以下面参照特定示范实施例更详细描述的方式由路由器执行的转发操作中，发送方和路由器密钥及可选的密钥索引是有用的。此外，通过为转发表填充表示目的地组的聚集路由器密钥和相关联的聚集有关的指令，转发操作能够更有效地进行，并且转发表将具有受限大小且不会太大，特别是在带有许多端主机和路由器的网络中。

基本上，在聚集路由器密钥已用于在某个路由器生成出口标记时，后续路由器的路由选择任务得以简化。然而，在分组更靠近其目的地传输时，聚集可能在某一点不再可能进行。另一方面，在该点潜在目的地/路由的数量也将开始减少，保持了路由选择的效力。

图2a示出能够在本文解决方案中使用的转发表，其中，示范条目或表行示为“x”。表具有多个列200-210，包括带有入口密钥索引“IKi”的第一列200，该索引能用于查找一个或多个适当条目以便执行匹配操作，即，匹配附加到进入分组的入口标记和表中第二列202中存在的入口密钥“IK”。单个入口密钥索引可指向表中多个条目的集合，而匹配操作能够限制到这些条目。

第三列204可包含一个或多个出口密钥“EK”，一旦找到匹配条目，便要从这些出口密钥来创建一个或多个新出口标记以便在分组转发到下一跳路由器时包括在分组中。可选的第四列206包含要附加到外出数据分组的出口密钥索引“EKi”，该索引实际上将用作由下一跳路由器接收时的入口密钥索引。第五列208包含端口号“P”，指示收到的和匹配的分组在朝下一跳路由器发送时要使用的端口。

最后，如果聚集路由器密钥用作入口或出口密钥，则第六列210包含与聚集路由器密钥相关联的聚集有关的指令“Agg”，其基本上规定路由器应执行聚集或解聚集，并且还规定应如何创建新出口标记，这将在下面描述。列210可称为“策略字段”，它也可包含各种其它数据，如策略规则或诸如此类，例如，“丢掉分组”、“使用默认端口”、“从DNS检索新路由器密钥”、“请求前一跳路由器明确对自身认证”等等。如果未使用密钥索引，则自然将忽略可选列200和206。

图3中示意示出一示范网络拓扑和传送情形，其中，聚集路由器密钥用于支持转发过程。多个路由器根据已知网络拓扑互连，在此情况下极大简化，并且多个端主机连接到网络中的接入路由器。

在此图中，只示出一些路由器R1-R7和端主机A-G，但实际网络一般具有比此处所示数量大得多的端主机和路由器。如上所述，从为端主机A-G定义的网络拓扑和目的地密钥所确定的以前分发的路由器密钥和聚集有关的指令等，路由器R1-R7已配置了其自己的转发表。

在此示例中，连接到接入路由器R1的第一端主机A在第一跳3:1中将目的地为连接到接入路由器R5的另一端主机B的数据分组发送到R1。端主机A已将发送方标记附加到分组，该标记已以上述方式从与目的地端主机B相关联的获得的发送方密钥来推导，因而专门与端主机B相关联。随后，接收路由器R1匹配分组中的路由器标记和其转发表中的条目以确定引导到作为下一跳路由器的路由器R2的外出端口。

从此图的网络拓扑中能够看到，目的地为端主机B-E的任何端主机的所有分组能够在路由器R2中通过与作为下一跳的路由器R3相关联的聚集路由器密钥来转发，因为R3能够将分组转发到B-E的所有。另一方面，目的地为端主机F和G的分组应在路由器R2中通过转而与路由器R4相关联的另一聚集路由器密钥来转发。在此描述中，认为是与特定路由器“相关联”的路由器密钥要概括理解为是匹配具有提供到该路由器的路径的外出端口号的转发表条目的密钥。

然而，应注意，在转发表中，不一定在哪个出口密钥与要使用的端口之间存在一对一对应关系。实际上，多个下一跳路由器可用于向目的地的某个集合“S”转发分组。例如，在图3的示例中，路由器R2能够经R3或R4将分组转发到D或E。因此，不止一个端口可在路由器R2中用于转发包含从与集合S中目的地相关联的同一出口密钥所推导的出口标记的任何分组。例如，本地拥塞状况可规定使用特定外出端口而不考虑出口密钥值。

在此示例中，匹配当前收到的分组中发送方标记的R1中的表条目包含规定朝向R3的聚集应由路由器R1来执行的聚集有关的指令。然而，聚集能够以其它方式进行，例如，由发送端主机A在密钥管理器帮助下进行或由传送路径中的另一路由器进行。因此，在路由器R1的匹配表条目中的聚集有关的指令规定应该通过将已从只与路由器R3相关联而不与端主机B的更详细目的地(且因此与聚集)相关联的聚集路由器密钥来推导的新出口标记附加到分组来执行聚集。然而，端主机B的详细目的地必须以某种方式保留在分组中以供以后使用，这如下面以后所述的能够以不同方式进行。路由器R1随后将附加有新标记的分组在第二跳3:2中发送到确定的下一跳路由器R2。

在从路由器R1接收分组时，路由器R2能够将附加的标记与其转发表中的条目进行匹配以确定相应地引导到路由器R3的外出端口。在将分组进一步发送到路由器R3前，路由器R2应执行解聚集，即，根据在路由器R2的匹配表条目中找到的聚集有关的指令，通过更改分组中的标记，使得下一路由器R3用于转发分组的标记从与路由器R5相关联的路由器密钥来推导。随后，路由器R2在第三跳3:3中将附加有更改的标记的分组发送到路由器R3。

备选的是，路由器R2可将分组发送到路由器R3而不更改分组中的标记，其中，路由器R3能从附加的标记推断分组应发送到路由器R5。仍有的另一备选是R2通过简单地删除指向R3的标记、并且只留下直接与目的地B相关联的原始标记来执行解聚集。

在从路由器R2接收分组时，路由器R3将附加的标记与其转发表中的条目进行匹配以确定相应地引导到路由器R5的外出端口。另外，根据匹配表条目中找到的聚集有关的指令，通过更改分组中的标记，使得下一路由器R5用于转发分组的标记从最终与最终用户B相关联的路由器密钥来推导，路由器R3执行进一步的解聚集。

随后，路由器R3在第四跳3:4中将附加有更改的标记的分组发送到路由器R5。由于分组中的标记从现在与最终用户B的最终详细目的地地址相关联的路由器密钥来推导，因此，解聚集已完成，并且分组因此在最终第五跳3:5中最终从路由器R5发送到端主机B。

在上述示例中，通过附加从只与路由器R3相关联的密钥来推导的标记，在路由器R1执行两层聚集，并且通过附加从分别与路由器R5和端主机B相关联的密钥来推导的标记，在每个路由器R2和R3中执行一层解聚集。由此，至少在路由器R2和R3中能够减少表条目的数量，以便基于以上述方式从聚集路由器密钥推导的标记来提供转发操作。

在此上下文中，“两层聚集(two-level aggregation)”基本上暗示使用与多个目的地组相关联的路由器密钥，而一层解聚集暗示将该路由器密钥更改为与单个目的地组相关联的路由器密钥。此外，在不进行聚集、即“零层聚集”时，使用与例如端主机等某个独特目的地相关联的路由器密钥。概括而言，“k层聚集”暗示使用与多个(k-1)层聚集的目的地的组相关联的路由器密钥。术语“k层聚集动作(k-level aggregating)”暗示将路由器密钥更改为与k层聚集的目的地集合相关联的路由器密钥。

减少表条目的数量应相对于其中每个路由器为该路由器处理的所有可能目的地保持密钥的备选方案来理解。例如，路由器R3将只需要使用分别与R5和R6相关联的路由选择的2个聚集密钥，而不是包括所有4个可能目的地B-E的4个密钥。

然而，视发送和接收端主机的网络拓扑和位置而定，能够使用任何其它聚集和解聚集方案。例如，传送路径可包括发送和接收端主机之间任何数量的中间路由器，并且任何层的聚集可在沿路径的多个连续路由器中逐步执行，或者优选通过在单个路由器引入多层的聚集来执行。此外，在路径中的一些路由器中可能不必执行聚集或解聚集，这如上所述由匹配表条目中的聚集有关的指令来控制。在使用分层网络拓扑的情况下，“早期”在传送路径中首先为分组执行层次结构中“向上”聚集，然后“以后”在路径中执行层次结构中的“向下”解聚集。

所有这些聚集方案共同之处是路由的聚集是为了减少转发表大小，而解聚集必须为传送的分组进行以使得能够识别其最终目的地。本领域技术人员将认识到，能够应用许多不同方法以识别网络拓扑中的哪些路由器位置“最适合”用于执行聚集/解聚集，但这在此描述的范围之外。

上面曾提及，在执行聚集时，接收端主机的最终目的地地址必须保留在分组中。如果从例如与目的地集合相关联的聚集路由器密钥生成的标记在其它情况下要简单地替代从专门与单个目的地相关联的密钥生成的标记，则从此点开始，正确的目的地将无法识别。

现在将分别参照图3a和图3b及3c，更详细地描述图3的传送情形中能如何进行此操作的两个不同实施例。即使这些实施例特别参照图3的传送示例和网络拓扑，但本领域技术人员将容易理解如何在其它传送情形和网络拓扑中概括应用所述机制和方案。

在借助于图3a所示的实施例中，通过合并发送端主机A附加到分组的原始标记和从聚集路由器密钥推导的各种添加标记来执行路由聚集，每个聚集路由器密钥实际上与在不同层次的多个端主机相关联。在此实施例中，在以前路由器已经进行了一个或多个层次的聚集时接收的分组的入口标记可因此由多个“子标记”组成，而原始标记在分组中保持为“最内的”标记。随后，每个分组接收路由器优选要使用“最新”或“最外的”标记来确定下一跳，即，将该标记与转发表中的候选入口密钥进行匹配。如果未找到对于最外的标记的匹配，则路由器可尝试下一标记，并以此类推。如果未找到对于任何子标记的匹配，则可根据默认路由选择策略来丢弃或路由分组。

在多个标记以此方式用于组成总入口或出口标记时，应指示在分组内何处找到每个单独的子标记。例如，每个子标记可以用“比特偏移”或诸如此类来开始，以指示能够在何处找到下一标记，并且最后标记随后可具有零偏移以指示“无另外标记”或类似内容。另一可能性是为子标记使用路由器事先已知的预定固定大小。在任何情况下，标记能在分组的报头中添加，或者如在图中所例示的一样，在分组的“尾部”或“报尾”中添加。

图3a示出带有有效负载字段和图3的传送情形中在不同跳附加的不同标记的分组。因此，在端主机A在跳3:1中将分组发送到第一跳路由器R1时，只有表示为“TAG 1”的从专门与最终用户B相关联的目的地密钥推导的原始标记附加到其。

当路由器R1在跳3:2中将分组发送到下一路由器R2时，表示为“TAG 2”和“TAG 3”的两个另外子标记已与原始标记一起附加到分组，其中，TAG 2位于TAG 1的旁边，TAG 3位于TAG 2的旁边。路由器R1已根据匹配表条目中聚集有关的指令从相应聚集路由器密钥来推导TAG 2和TAG 3。TAG 3是分组的最新或最外的子标记，表示相对于聚集的最高层次路由器密钥，在此情况下与路由器R3相关联，并且因此应由分组接收路由器R2用于查找下一跳路由器R3。

当路由器R2基于TAG 3找到路由器R3时，通过从分组删除最外的子标记TAG 3来执行解聚集，留下TAG 2作为在跳3:3中将分组发送到R3时与路由器R5相关联的最外子标记。类似地，在路由器R3基于TAG 2找到路由器R5时，通过从分组删除最外的子标记TAG 2来执行解聚集，留下原始TAG 1作为在跳3:4中将分组发送到R5时专门与端主机B相关联的原始TAG 1。

通常，在此实施例中通过将从匹配表条目中一个或多个出口密钥推导的一个或多个另外子标记附加到分组来更改接收分组的入口标记以执行聚集，而通过从分组中逐一删除另外子标记来更改总入口标记以执行解聚集。

在上面对图3a的描述中，假设添加的TAG 2和TAG3只与原始TAG 1连续串连以创建新出口标记。然而，可能以更集成的方式添加这些子标记，使得通过原始TAG 1和添加的TAG 2和TAG 3的合并来形成新出口标记。通常，预定的合并函数“C”能够应用到接收的入口标记和从匹配表条目的一个或多个出口密钥推导的一个或多个标记。函数C可以是如上所述的串连，或另一函数，例如，已知的逻辑“XOR”函数。如果在匹配表条目中找到n个出口密钥，则这通常能够表示为：

新出口标记＝C(入口标记，TDF(出口密钥₁)，TDF(出口密钥₂)…，TDF(出口密钥_n))    (1)

应注意，虽然此方案能够用于节省通信带宽，但它也使匹配操作更复杂。例如，在带有N个入口密钥的转发表中，要处理由3个经XOR运算的标记合并的入口标记，可能需要考虑大致N^3种可能的入口密钥合并。同时，对带宽的需要大致减少3倍。

如上所述，在找到匹配表条目时，根据匹配表条目中的聚集有关的指令为分组创建新出口标记。例如，此指令可规定执行以下任何操作：

-即使已经为最外的标记找到匹配，也将匹配函数应用到“下一”标记，

-使用匹配表条目中的一个或多个出口密钥来生成分组的一个或多个另外子标记以执行聚集，

-在将新出口标记作为最外的子标记附加前删除零或更多子标记以执行解聚集。

-应用合并函数C(例如，串连、逻辑XOR运算等)到分组中的接收的入口标记和匹配表条目中的一个或多个出口密钥以执行聚集或解聚集。

当使用(1)的标记合并函数时，视用于产生添加的子标记的密钥表示目的地的更大或更小集合而定，添加标记实际上可能能够表示“聚集”或“解聚集”。因此，聚集/解聚集可隐含于使用的出口密钥的“类型”。此外，有时能够假设路径中的真正第一个路由器对一次性执行所有聚集层次有充足的知识，如上述示例中的路由器R1，使得在随后路由器中将只发生解聚集。

在图3a例示的上述实施例中，一旦网络拓扑和聚集/解聚集点已确定，则每个目的地或目的地组能够在技术上指派有随机、独立的目的地和路由器密钥以便分发到适当路由器。然而，可能减少需要显式分发和管理的密钥的数量，这在借助于图3b和3c联合示出的另一实施例中示出。在此实施例中，通过将发送端主机A附加到分组的原始标记换成从聚集路由器密钥推导的新标记，路由器密钥和目的地密钥的分层方案用于执行在不同层次路由的聚集。一条能用于确定原始目的地的相关联聚集信息也添加到标记。

图3b示出如何借助于函数f(p，q)能从根值x生成带有在树结构的不同层的节点的此类分层密钥方案的示例，其中，p是树中上方节点位置的路由器密钥值，并且q是指示当前树层次内节点位置的整数。随后，结果密钥方案将由能够沿从根向下的路径、根据以下链而计算的密钥值来组成：

(x，f(x)，f(f(x))，…，f(f(…f(x)…)))，等等。

网络中各个端主机的目的地密钥在正好在此树结构的底部形成树上的“叶”的节点具有密钥值。

应注意，树结构不应理解为反映物理网络拓扑，而是应通常视为物理网络上的逻辑覆盖。具体而言，所有叶不一定由某个物理端主机“占据”。另外，虽然更高层次(非叶)密钥直观上对应于网络中的中间节点，即路由器，但所有中间节点不一定确实与物理路由器相关联。例如，某个路由器R能够处理例如对应于树的子集等的密钥的子集。

从此树结构中任何节点的f(p，q)的值，能够轻松生成该节点下f值的整个子树。假设端主机的目的地密钥对应于树结构的叶，在叶上方在一个或多个树层次上的任何f值能够用作聚集路由器密钥。由此密钥的密码树结构能够叠加在任何分层路由器拓扑上。在一个可能实施例中，函数f可以是单向函数，易于“向前”计算，但难以“向后”计算，即“逆转”函数。虽然图3b所示树结构是二进制，但使用任何“n进制(n-ary)“或其它树结构生成路由器和目的地密钥是可能的，并且本发明在此方面并无限制。

因此，通过将单个密钥值分发到路由器，在该密钥值下的整个(子)树能够由路由器在本地重新构建，而无需明确分发任何另外的密钥。另一方面，一个安全性优点可能是无法从与“最低层次”路由器或端主机相关联的密钥来推断与“更高层次”路由器(其在概念上可以是更“重要的”路由器)相关联的密钥。

通过在树结构中“向上”移动以选择分组的新出口密钥来执行聚集，同时通过在树中“向下”移动以选择新出口密钥来进行解聚集。因此，在通过附加从前一密钥上方一个或多个树层次的新密钥而推导的标记为分组执行聚集时，添加的聚集信息应基本上指示前一密钥位于哪个分支。在使用二进制密钥树结构的情况下，此信息可只是每个聚集层次的“左边”或“右边”。在使用n进制密钥树结构的一般情况下，此信息对于每个聚集层次将包括1与n之间的整数。

例如，如果路由器在其转发表中找到密钥k＝f(x，1)的匹配，并且根据转发表中相关联的聚集有关的指令，应通过在树中从节点f(x，1)向下移动来向目的地解聚集，则必须确定解聚集应向f(f(x，1)，a)还是向f(f(x，1)，b)进行，因为f(x，1)是两者的共同根。这能够通过如上所示在每个聚集步骤添加相关联聚集信息来解决。

因此，如果在传送路径中更早的聚集路由器将f(f(x，1)，a)生成的标记换成f(x，1)生成的一个标记，则路由器能够将“a”作为聚集信息添加到标记。此信息“a”将使得传送路径中以后的解聚集路由器能够从f(x，1)向f(f(x，1)，a)而不是向f(f(x，1)，b)解聚集。通常，每个聚集步骤因此将通过一条聚集信息来扩展标记大小。

如上所述，如果函数f是单向函数，则不可能在树结构中“向上”计算以执行聚集，但在树结构中较容易“向下”计算以执行解聚集。这能够如下解决。假设网络中的路由器具有它应执行的某一“最高”层次的聚集，密钥能够分发到位于树中足够高节点位置的那个路由器以使得该路由器能够计算该最高节点位置之下的子树中的任何节点值，以产生聚集路由器密钥。因此，如果路由器被赋予对应于某个子树的根的密钥，并且也知道函数f，则它能为对应目的地的聚集来计算该给定根密钥之下整个子树中的所有节点值。

图3c示出带有有效负载字段和在图3的传送情形中在不同跳附加的不同标记的分组，在此情况下，使用图3b的分层路由器密钥方案。在此示例中，也如下所述将接收分组中的标记换成从聚集或解聚集路由器密钥推导的新标记。如图3a的实施例中一样，仅有从专门与端主机B相关联的目的地密钥而推导的表示为“TAG o”的原始标记附加到在跳3:1中从端主机A发送到第一跳路由器R1的分组。

当路由器R1在跳3:2中将分组发送到下一路由器R2时，根据匹配表条目中的聚集有关的指令，将从两层聚集路由器密钥所推导的新标记“TAG ij”附加到分组。“TAG ij”从与路由器R3相关联的路由器密钥来推导，因而能够由分组接收路由器R2用于找到下一跳路由器R3。另外的聚集信息“Agg-info ij”也并靠着“TAG ij”附加到分组，指示分别为两个层次i和j如何进行聚集，由此能够实现向传送路径进一步向下的路由器中的正确密钥的解聚集。

如上所述，聚集信息“a”通常能够添加到新标记，以使得能够从f(x，1)向f(f(x，1)，a)解聚集。在此情况下，“Agg-info ij”指示两层聚集，使得解聚集能够分别在层次i和j的两个随后路由器中执行。具体而言，“Agg-info ij”将指示从与R3相关联的密钥开始的路径经R5引导到B。在此二进制树示例中，在根据“Agg-info ij”执行解聚集时，应沿从R2的两个“左边”分支行进。

在路由器R2基于“TAG ij”找到路由器R3时，通过将“TAG ij”在跳3:3中将分组发送到R3时换成与路由器R5相关联的新标记“TAG i”，执行解聚集。此外，与新标记相关联的新聚集信息”Agg-info i”也并靠着“TAG i”添加到分组，指示如何为层次i进行聚集，即，在下一跳3:4中应沿“左边”分支行进。类似地，在路由器R3基于“TAG i”找到路由器R5时，通过将以前的“TAG i”在跳3:4中将分组发送到R5时换成专门与端主机B相关联的原始“TAG o”，执行进一步的解聚集步骤。

通常，在此实施例中通过根据聚集指令将接收分组中的标记换成从聚集路由器密钥推导的新标记，并且还附加指示如何进行聚集的另外相关联聚集信息，从而执行聚集。另一方面，通过将接收分组中的标记换成基于分组中的另外聚集信息而确定的新标记，执行解聚集。

虽然上面的图3b-c的实施例基于分层密钥结构，但在图3a的实施例中使用带有或多或少随机生成的密钥值的“平坦”密钥结构或如上所述的分层密钥结构是可能的。此外，这两个实施例也能够单独或结合使用。

如果为接收的入口标记找到匹配表条目，则根据匹配表条目中聚集有关的指令为分组创建新出口标记。假设密钥树中的某个密钥值k导致了匹配，则此指令可规定任何以下操作：

-通过使用在树中k“上方”的某个层次的密钥以产生新出口标记来执行聚集。这一般也暗示在分层密钥结构的情况下添加聚集信息。

-根据分组中的另外聚集信息，使用在k“下方”某个层次的密钥以产生出口标记来执行解聚集。

-既不执行聚集也不执行解聚集。在此情况下，新出口标记可使用相同密钥k或匹配表条目中的显式出口密钥来生成。此密钥可以是另一密钥树的一部分，作为另一密钥树的一部分来生成，例如，以用于不同管理域之间的路由选择，其中，每个域一般将具有独特的密钥树。

通过根据上述密钥分层结构，简单地为路由器中的转发表配置适当的出口密钥，使用的聚集/解聚集方案也能够是隐式的。

通过考虑从普通邮寄进行的实体信函的传送的模拟，也能够进一步理解上述聚集机制。详细的目的地地址最初在信函上显示，一般包括街道地址、城市和国家，这有效地形成分层寻址方案。例如，信函可从美国德克萨斯州发送到瑞典斯德哥尔摩17大街。德克萨斯州的接收邮局将立即明白信函发送到瑞典，但将不需要读取街道地址和城市的更多详细信息。这能够意味着信函先发送到纽约的国际邮政大楼，由其将目的地为瑞典的所有外出邮件发送到在瑞典哥德堡的国际邮政大楼。

最初，通过分别只读取地址中的国家以确定信函的“下一跳”，丢弃城市和街道两者的层次，因此已进行了两个层次的聚集。参照图3，路由器R1可因此相当于在德克萨斯州的邮局，路由器R2可相当于在纽约的邮政大楼，而路由器R3可相当于在瑞典哥德堡的邮政大楼等等。作为逐渐解聚集的结果，信函的地址中更详细的信息随后将分别在哥德堡和斯德哥尔摩读取。在此上下文中，对密钥树中多个标记和/或路径信息的需要也能够理解如下。对于不使用多个标记的模拟将是只关注目的地的国家的在德克萨斯州的邮局将在该情况下在转发该信函前从地址中擦除街道/城市，并且只保持“瑞典”。虽然信函将到达瑞典，但向目的地进一步“路由”信函将是不可能的。

图4是一个框图，根据一些其它示范实施例示出在分组交换网络中能够如何支持从端主机A向未示出的目标端主机发送的数据分组的转发。此过程示为一系列的动作或步骤，主要涉及端主机A、密钥管理器400和在端主机A与目标端主机之间传送路径中某处的路由器402。在此示例中，路由器402采用如下所述的路由的聚集。

在第一步骤4:1中，与各个端主机B、C、D、…相关联的目的地密钥被登记并存储在密钥管理器400中，其中，每个独特的目的地密钥实际上识别或“定义”对应的目的地，即端主机。在此过程中，可在端主机与密钥管理器400之间的协定中决定目的地密钥，优选在对端主机认证后。实际上，此步骤能够替代根据现有技术向端主机指派IP地址。

密钥管理器400还在步骤4:2中确定分别能够执行聚集和解聚集的路由器的位置。能够设想各种不同方式以确定网络拓扑中聚集和解聚集的位置，例如，根据转发表大小和/或通过确定分层网络结构、端主机的位置等，然而，这不必在此处进一步描述。密钥管理器400还在下一步骤4:3中从上面登记的目的地密钥来创建聚集路由器密钥和相关联的聚集有关的指令。如上在描述图2a时所提及的，还可为每个创建的路由器密钥来定义密钥索引。目的地密钥和路由器密钥可在分层或“平坦”密钥结构中布置，然而，这可利用不同聚集方案，如上所述。

随后，密钥管理器400在进一步步骤4:4中通常将创建的聚集路由器密钥和相关联的聚集有关的指令及可选的密钥索引一起分发到网络中能够采用聚集的路由器，包括此处所示的路由器402。密钥管理器400也可将非聚集路由器密钥和目的地密钥分发到一些路由器，但这在本描述中不予考虑。随后，路由器能够相应地配置其自己的转发表，包括分发的聚集路由器密钥和可选的密钥索引，这些将用于转发进入的数据分组，由此创建网络中有用的转发架构。通过使用聚集路由器密钥，因此能够如上所述避免过大的转发表。下面将更详细地描述路由器中基于聚集路由器密钥的转发操作。

路由器密钥、相关联的聚集有关的指令和可选的密钥索引的分发可在配置过程中执行，或者否则例如使用路由选择协议来执行，如在路由器域中配置常规转发架构时，如上所述。路由器随后能够基于分发的信息，为其转发表配置包括不同入口和出口密钥和外出端口的条目。分发的路由器密钥可实际上包括一对入口和出口密钥。

端主机A想要与目标端主机通信，并且在某个点，在下一步骤4:5中，相应地发送地址查询或类似内容到密钥管理器400，例如，如上所述以常规方式查找目标端主机的电子邮件地址或web地址。随后，密钥管理器400可应用为目标端主机定义的策略，确定查询端主机是否被授权发送数据分组到目标端主机。

假设端主机A被授权，并且能够被允许将分组发送到目标端主机，则密钥管理器400检索与目标端主机相关联的目的地密钥，并通过应用密钥推导函数KDF到至少该目的地密钥，并且可选地也应用到其它数据，如查询端主机的身份、时间戳和/或经常称为“RAND”或“NONCE”的用于随机化的随机数，从目的地密钥来创建发送方密钥。这能够表示为：

发送方密钥＝KDF(目的地密钥，<其它数据>)(2)

如果查询端主机的身份用作(2)中的“其它数据”，则发送方密钥将与该端主机独特地相关联。KDF可优选是密码函数或诸如此类。

在进一步步骤4:6中，密钥管理器400随后将发送方密钥提供到端主机A以响应步骤4:5的查询，使得端主机A能够从其推导发送方标记，并且将数据分组和附加为入口标记的发送方标记一起发送到目标端主机。端主机A连接到的接入路由器也应能够访问相同的发送方密钥以便在入口标记上执行匹配操作，但这在本描述中不予考虑。

端主机A因此在下一步骤4:7中应用预定义的第一标记推导函数TDF到至少接收的发送方密钥，以创建作为出口标记而插入发送的分组中的发送方标记“TAG”。就像目的地IP地址通常根据现有技术一样，出口标记能在分组报头中的目的地字段中插入。

视实现而定，TDF也可应用到“其它数据”，如要发送的分组中包含的有效负载数据、时间戳和/或用于随机化的RAND或NONCE。这能够表示为：

发送方标记＝TDF(发送方密钥，<其它数据>)  (3)

如果分组中的有效负载包括在“其它数据”中，则发送方标记将对于仅仅该分组是独特的。TDF可以是密码函数或诸如此类。端主机A可已预配置成在传送数据分组时使用TDF，或者TDF可在步骤4:6中与发送方密钥一起提交到端主机A。此外，TDF也在网络中是已知的，至少对端主机A的接入路由器是已知的。

将发送方标记附加到传送的数据分组，这将实际上授权该分组通过网络向其目的地路由。如果路由器检测到接收的数据分组未包含任何有效标记，则分组不能被授权并且可简单地丢弃。因此，如果TDF是“强”密码函数，则将虚假发送方标记附加到分组的尝试将极可能不成功，并且附加有非有效标记的任何分组将实际上在转发过程中被停止。

在进一步步骤4:8中，最初从端主机A发送的数据分组在路由器402由入口部分402a接收。入口标记“TAG”附加到接收的分组，并且可选地还附加了入口密钥索引(如果使用的话)。分组可从未示出的前一路由器接收，或者直接从端主机A接收(如果路由器402是A的接入路由器)。在路由器402的转发单元402b通常配置成借助于转发单元402b中示意示出的转发表以便找到出口单元402c中的外出端口，为每个进入的数据分组执行转发操作。

在进一步步骤4:9中，转发单元402b使用已知的TDF，为附加的“TAG”和转发表中不同的入口密钥IK执行匹配操作以便找到表中的匹配条目。换而言之，转发单元300b尝试一次为表中的一个条目匹配接收的入口标记和入口密钥IK。

更详细地说，匹配操作可包括路由器应用TDF到转发表的行中的“候选”入口密钥以推导候选入口标记。如果候选入口标记满足与分组中接收的入口标记的预定关系，则认为找到匹配。预定关系可以是相等，即，如果候选入口标记与分组中的入口标记相同，则认为找到匹配。如果两个标记不匹配，则尝试表中的下一候选密钥等等。

如果入口密钥索引IKi包括在接收分组中，则只需执行对表中包含入口密钥索引IKi的一个或多个条目的匹配。使用入口密钥索引IKi将因此实际上通过限制表中可能候选入口标记的数量而加快每个接收的数据分组的匹配操作。也可能只使用包括的入口密钥索引IKi来查找适当的端口，即，为了安全而不执行匹配操作。

应注意，在使用聚集的路由器密钥而不是密钥索引时，可能有用的是，以路由器在表中为匹配而执行有序搜索的相同顺序，为路由器的表条目填充对应于高(或更高)层次的聚集的密钥。由此，能够尽早找到匹配表条目。

如果在步骤4:9中找到匹配条目，则在随后的步骤4:10中该条目中的端口(在此情况下是端口P(x))被确定为用于分组的适当外出端口。如果在步骤4:9中未找到匹配条目，则在步骤4:10中分组不被授权且因此将丢弃，由此停止在此路由器中转发任何此类分组。步骤4:9的匹配操作将因此授权分组进行进一步路由选择。

由于路由器402采用多个目的地的聚集，因此，其转发表包括与表中每个聚集路由器密钥相关联的聚集有关的指令，该指令从表中的策略字段读取，如在图2a中的列210中。在此情况下，匹配表条目包含聚集有关的指令，并且转发单元402b因此基于该指令在下一步骤4:11中为分组创建新出口标记。这能够根据上面参照图3a-c所述的任何实施例来进行，因此在使用分层密钥方案时将接收的标记换成新标记及相关联的聚集信息，或者在使用合并的标记时对/从接收的标记添加/删除另外标记。

另一标记推导函数TDF′也可应用到匹配条目中找到的出口密钥EK以获得另外或交换的标记。TDF′应为下一跳路由器已知以使得能够在其中进行匹配操作。TDF和TDF′可以是不同或相等的函数。新出口标记TAG′因此能表示为：

出口标记＝TDF′(出口路由器密钥，<其它数据>)  (4)

(4)中的“其它数据”可以是分组中包含的有效负载数据和/或用于随机化的RAND或NONCE。新合并或交换的出口标记在进一步步骤4:12中附加到分组。

如果使用密钥索引，则在步骤4:11中在匹配条目中找到的出口密钥索引EKi也附加到分组。附加的EKi随后将在下一跳路由器中用作查找其转发表中相关行的入口密钥索引IKi以便执行匹配操作等。

根据匹配表条目，随后在下一步骤4:13中将分组转发到出口单元402c的端口P(x)。最后，作为下一跳，在端口P(x)上，在最后步骤4:14中发出附加有新出口标记TAG′的分组。随后，基本上以如上所述相同的方式，下一跳路由器将能够匹配新入口标记TAG′和其转发表中的条目以确定下一跳。

图5是流程图，带有支持分组交换网络的路由器中数据分组的转发过程的示范过程中的步骤，如由例如图4中的密钥管理器400的密钥管理器来执行。在第一步骤500中，例如，如上面对于图4的步骤4:1所述，为连接到网络中接入路由器的不同端主机登记目的地密钥。在下一步骤502中，例如，如图4的步骤4:2中一样，确定网络中能够分别执行路由聚集和解聚集的路由器的位置。

在进一步步骤504中，例如，如图4的步骤4:3中一样，基于确定的聚集和解聚集的放置，创建聚集路由器密钥和相关联的聚集有关的指令，每个聚集路由器密钥一般表示多个目的地的集合。在下一步骤506中，例如，如图4的步骤4:4中一样，将上述聚集路由器密钥和相关联的聚集有关的指令分发到分别能够执行路由聚集和解聚集的路由器。由此，这些路由器能够从分发的信息配置其自己的转发表。也可将非聚集路由器密钥和目的地密钥分发到一些路由器，但这在本描述中不予考虑。步骤500-506能够在配置过程中或其它情况下执行。

在进一步步骤508中，在某一点从查询端主机接收地址查询，基本上请求目标端主机的目的地地址或类似内容。地址查询能以如上述的常规方式进行，例如，涉及目标端主机的电子邮件地址或网址。在下一步骤510中，通过应用密钥推导函数KDF至少到与目标端主机相关联的目的地密钥，或应用到与所述目的地密钥有关的密钥，创建发送方密钥。

在最终步骤512中，密钥管理器将发送方密钥提供到查询端主机，所述发送方密钥从与目标端主机相关联的目的地密钥来推导。还可检查查询端主机是否被授权发送数据分组到目标端主机。如果无授权，则可简单地拒绝查询。由此，基本上以上面对于步骤4:7所述的方式，查询端主机能够通过将从接收的发送方密钥所推导的发送方标记附加到每个传送的分组，将数据分组传播到目标端主机。

图6是流程图，带有用于分组交换网络的路由器(例如图4中的路由器402)中支持接收数据分组的转发过程的示范过程中的步骤。在第一步骤600中，如图4的步骤4:4中一样，由从例如DNS系统的密钥管理器接收的聚集路由器密钥和相关联的聚集有关的指令来配置转发表。

在下一步骤602中，由路由器接收数据分组。分组可能已从相邻路由器传送，或者作为第一跳从发送端主机传送(如果路由器是用于发送端主机的接入路由器，例如，如图4中的跳3:1中一样)。在可选的下一步骤604中，可检查分组是否包含从密钥管理器已提供的密钥推导的入口标记。如果未找到此类入口标记，则在此点在进一步步骤606中能够丢弃分组。

另一方面，如果分组包含入口标记，则在随后的步骤608中，例如如上面对于图4中步骤4:9所述的，使用已知的TDF，应用匹配操作到接收的入口标记和转发表中的不同候选入口标记以便在表中查找匹配条目。如果在转发表中使用密钥索引，并且密钥索引也附加到接收的分组，则在此步骤中能够使用密钥索引将匹配操作限制到一个条目或只是几个条目以便在表中快速查找匹配条目。

在下一步骤610中，确定是否借助于匹配操作在转发表中找到匹配条目。如果未找到，则在步骤612中丢弃分组。如果找到匹配条目，则在进一步步骤614中根据匹配条目为分组选择外出端口。

在随后的步骤616中，还检查匹配表条目中是否存在聚集有关的指令，该指令因此与匹配表条目中的入口密钥相关联，基本上指令路由器执行聚集或解聚集。如果存在，则根据上面对于图3a-c所述的任何实施例，聚集有关的指令可因此规定应更改接收的标记，或者应分别对/从分组添加或删除一个或多个路由器标记。

如果在条目中未找到此类聚集有关的指令，则在可选的步骤618中通过应用标记推导函数到匹配表条目中的出口密钥，可推导新出口标记。备选的是，在发送分组到下一跳路由器时，接收的标记可再使用为出口标记。

另一方面，如果在匹配表条目中存在聚集有关的指令，则根据该指令，在进一步步骤620中创建新出口标记。最终，在最后示出的步骤622中，在附加有新出口标记的情况下，分组从确定的端口发送到下一跳路由器。如果使用密钥索引，则也可将匹配表条目中的出口密钥索引附加到分组。随后，接收下一跳节点能够基本上重复根据上述步骤600-622的该过程。

图7是逻辑框图，根据另外的示范实施例更详细地示出密钥管理器700中的设备和分组交换网络中的路由器702中的布置，其用于支持网络中数据分组的转发。

密钥管理器700包括网络控制单元700b，该单元适用于登记连接到网络中接入路由器的端主机的目的地密钥。网络控制单元700b还适用于例如基于转发表大小、分层网络结构、端主机的位置等来确定网络中分别能够执行路由聚集和解聚集的路由器的位置。

密钥管理器700也包括密钥分发器700c，该密钥分发器适用于创建聚集路由器密钥和相关联的聚集指令，每个聚集路由器密钥表示多个目的地的集合。密钥分发器700c还适用于分发聚集路由器密钥和相关联的聚集指令到能够执行路由聚集和解聚集的路由器，由此使得这些路由器能够配置其自己的转发表。

网络控制单元700b也可保留指示哪些端主机被授权发送分组到每个登记的端主机的信息。此信息可包括为登记的端主机定义的并确定查询端主机是否被授权发送数据分组到特定目的地的策略。

密钥管理器700还包括地址查询管理器700a，该地址查询管理器适用于从查询端主机A接收有关未示出的目标端主机的地址查询。地址查询管理器700a也适用于通过应用密钥推导函数KDF至少到与目标端主机相关联的目的地密钥或到与所述目的地密钥有关的密钥来创建发送方密钥，并且将创建的发送方密钥发送到查询端主机以响应地址查询。由此，查询端主机能够通过将从发送方密钥生成的发送方标记附加到传送的数据分组，将数据分组传播到目标端主机，发送方标记将传送的数据分组引导到目标端主机。

路由器702包括入口部分704，该部分适用于从例如网络中的另一路由器的相邻节点或者直接从发送端主机接收数据分组P。入口部分704还可适用于在有效入口标记附加到分组时接受分组，以及在其它情况下在未包括有效入口标记时丢弃分组。

路由器702还包括转发单元706，该转发单元适用于由从密钥管理器700中密钥分发器700c接收的聚集路由器密钥和相关联的聚集有关的指令来配置转发表。转发单元706还包括转发表706a和标记匹配单元706b，该标记匹配单元用于匹配接收的入口标记和转发表706a的条目中的入口密钥，以例如分别对于图4中步骤4:9-4:10和图6中步骤608-614所述的方式从匹配表条目来确定分组的外出端口。

转发单元706还包括标记创建单元706c，该标记创建单元适用于根据匹配表条目中存在的聚集有关的指令为分组创建出口标记。路由器702还包括出口部分708，该部分适用于在创建的新出口标记附加到分组的情况下，将分组从确定的外出端口发送到下一跳节点，例如，另一相邻路由器。

应注意，图7只在逻辑意义上示出分别在密钥管理器700和路由器702中的各种功能单元。然而，技术人员实际上可使用任何合适的软件和硬件部件自由地实现这些功能。因此，本发明通常不限于密钥管理器700和路由器702的所示结构。

在此解决方案中，路由器因此能够以上述方式将接收的数据分组中包括的入口标记与转发表中的路由选择或入口密钥进行匹配，以验证分组并同时查找正确的外出端口。如果在转发表的条目中找到匹配，则将该条目中的端口号确定为用于分组的正确外出端口。

所述实施例能够实现转发架构，其中，在路由器中能够使用可伸缩的转发表。数据分组的路由选择也能够受到控制以避免泛洪、垃圾邮件、病毒、欺诈、DoS攻击及通常的未经请求的业务。虽然本发明已参照特定示范实施例来描述，但该描述一般仅旨在示出发明的概念，并且不应视为限制本发明的范围。本发明由随附权利要求来定义。

Claims (25)

1.一种支持分组交换网络的路由器(402，702)中接收的数据分组的转发的方法，包括以下步骤：

-基于从密钥管理器接收的聚集路由器密钥和相关联的聚集有关的指令来配置转发表，每个聚集路由器密钥表示目的地的集合，

-接收包括从发送方密钥或路由器密钥来推导的入口标记的数据分组，

-应用匹配函数到所接收的入口标记和所述转发表中的至少一个条目以便查找匹配的表条目，所述条目包括候选入口密钥和外出端口指示，

-根据还包括相关联的聚集有关的指令的找到的匹配表条目，为所述分组选择外出端口，

-根据所述匹配表条目中的所述聚集有关的指令，创建出口标记，以及

-将附加有所创建的出口标记的所述分组从所选择的外出端口发送到下一跳路由器。

2.如权利要求1所述的方法，其中所述匹配函数包括应用标记推导函数TDF到表条目中的所述候选入口密钥以推导候选入口标记，并且如果所述候选入口标记满足与所述分组中所接收的入口标记的预定关系，则认为找到匹配。

3.如权利要求2所述的方法，其中所述预定关系是相等，即，如果所述候选入口标记等于所述分组中的所述入口标记，则认为找到匹配。

4.如权利要求1-3的任一项所述的方法，其中通过应用另一标记推导函数TDF′到所述匹配表条目中的出口密钥来创建所述出口标记。

5.如权利要求1-4的任一项所述的方法，其中所接收的数据分组还包含与所述转发表中条目或条目集合相关联的密钥索引，并且所述密钥索引用于查找适当的一个条目/多个条目以便应用所述匹配函数。

6.如权利要求1-5的任一项所述的方法，其中通过将从所述匹配表条目中一个或多个出口密钥所推导的一个或多个另外的子标记并靠着所接收的入口标记附加到所述分组以执行聚集，或者通过从所述分组删除一个或多个另外的子标记以执行解聚集，创建所述出口标记。

7.如权利要求6所述的方法，其中通过在执行聚集时应用预定合并函数(C)到所接收的入口标记和所述一个或多个另外的子标记，创建所述出口标记。

8.如权利要求7所述的方法，其中所述合并函数是串连或XOR函数。

9.如权利要求1-5的任一项所述的方法，其中目的地密钥和路由器密钥的分层方案用于执行路由的聚集，并且通过将所接收的入口标记换成从所述匹配表条目中的出口密钥所推导的新标记、以及还添加相关联的聚集信息到所述出口标记，创建所述出口标记，其中所述聚集信息能够用于确定原始目的地。

10.如权利要求9所述的方法，其中所述分层路由器密钥方案借助于函数f(p，q)从根值(x)生成，其中p是当前树层次上方节点位置的路由器密钥值，以及q是指示所述当前树层次内节点位置的整数，其中端主机的目的地密钥对应于所述树结构的叶，以及所述叶上方在一个或多个树层次上的任何f值能够用作聚集路由器密钥。

11.如权利要求10所述的方法，其中结果的密钥方案由能够沿从所述根(x)向下的路径、根据以下链：(x，f(x)，f(f(x))，…，f(f(…f(x)…)))所计算的密钥值来组成。

12.一种分组交换网络的路由器(402，702)中的设备，用于支持所述路由器中接收的数据分组的转发，所述设备包括：

-转发单元(402b，706)，适用于基于从密钥管理器(400，700)接收的聚集路由器密钥和相关联的聚集有关的指令来配置转发表，每个聚集路由器密钥表示目的地的集合，

-入口单元(704)，适用于接收包括从发送方密钥或路由器密钥所推导的入口标记的数据分组(P)，以及

-出口单元(708)，用于发送所述数据分组(P′)到下一跳节点，

其中所述转发单元包括：

-标记匹配单元(706b)，适用于应用匹配函数到所接收的入口标记和所述转发表中至少一个条目以便查找匹配的表条目，所述条目包括候选入口密钥和外出端口指示，并且还适用于根据还包括相关联的聚集有关的指令的找到的匹配表条目，为所述分组选择外出端口，以及

-标记创建单元(706c)，适用于根据所述匹配表条目中的所述聚集有关的指令来创建出口标记，以及将所述出口标记附加到所述分组，所述分组要由所述出口单元从所选择的外出端口发送到下一跳路由器。

13.如权利要求12所述的设备，其中所述标记匹配单元还适用于应用标记推导函数TDF到每个表条目中的所述候选入口密钥以推导候选入口标记，其中如果所述候选入口标记满足与所述分组中所接收的入口标记的预定关系，则认为找到匹配。

14.如权利要求13所述的设备，其中所述预定关系是相等，即，如果所述候选入口标记等于所述分组中的所述入口标记，则认为找到匹配。

15.如权利要求12-14的任一项所述的设备，其中所述标记创建单元(706c)还适用于通过应用另一标记推导函数TDF′到所述匹配表条目中的出口密钥来创建所述出口标记。

16.如权利要求12-15的任一项所述的设备，其中所述标记创建单元(706c)还适用于通过将从所述匹配表条目中一个或多个出口密钥所推导的一个或多个另外的子标记并靠着所接收的入口标记附加到所述分组以执行聚集，或者通过从所述分组删除一个或多个另外的子标记以执行解聚集，创建所述出口标记。

17.如权利要求16所述的设备，其中所述标记创建单元(706c)还适用于通过在执行聚集时应用预定合并函数(C)到所接收的入口标记和所述一个或多个另外的子标记来创建所述出口。

18.如权利要求17所述的设备，其中所述合并函数是串连或XOR函数。

19.如权利要求12-15的任一项所述的设备，其中目的地密钥和路由器密钥的分层方案用于执行路由的聚集，并且所述标记创建单元(706c)还适用于通过将所接收的入口标记换成从所述匹配表条目中的出口密钥所推导的新标记、以及还添加相关联的聚集信息到所述出口标记，创建所述出口标记，其中所述聚集信息能够用于确定原始目的地。

20.如权利要求19所述的设备，其中所述分层路由器密钥方案借助于函数f(p，q)从根值(x)生成，其中p是当前树层次上方节点位置的路由器密钥值，以及q是指示所述当前树层次内节点位置的整数，其中端主机的目的地密钥对应于所述树结构的叶，以及所述叶上方在一个或多个树层次上的任何f值能够用作聚集路由器密钥。

21.如权利要求20所述的设备，其中结果的密钥方案由能够沿从所述根(x)向下的路径、根据以下链：(x，f(x)，f(f(x))，…，f(f(…f(x)…)))所计算的密钥值来组成。

22.一种支持分组交换网络中在路由器转发数据分组的方法，包括由密钥管理器(400，700)执行的以下步骤：

-(500)为连接到所述网络中接入路由器的端主机(B，C，D，…)登记目的地密钥，

-(502)确定分别能够执行路由聚集和解聚集的路由器的位置，

-(504)创建聚集路由器密钥和相关联的聚集指令，每个聚集路由器密钥表示目的地的集合，以及

-(506)分发所述聚集路由器密钥和相关联的聚集指令到所述路由器以用于执行路由聚集和解聚集，由此使得所述路由器能够基于所分发的信息来配置它们自己的转发表。

23.如权利要求22所述的方法，还包括以下另外的步骤：

-从查询端主机(A)接收有关目标端主机的地址查询，

-通过应用密钥推导函数KDF至少到与所述目标端主机相关联目的地密钥，创建发送方密钥，以及

-将所创建的发送方密钥发送到所述查询端主机以响应所述地址查询，由此使得所述查询端主机能够通过将从所述发送方密钥生成的发送方标记附加到要传送的数据分组，将数据分组传播到所述目标端主机，所述发送方标记将所述数据分组引导到所述目标端主机。

24.一种在密钥管理器(400，700)中用于支持分组交换网络中在路由器转发数据分组的设备，包括：

-网络控制单元(700b)，适用于为连接到所述网络中接入路由器的端主机登记目的地密钥，并且还适用于确定分别能够执行路由聚集和解聚集的路由器的位置，以及

-密钥分发器(700c)，适用于创建聚集路由器密钥和相关联的聚集指令，每个聚集路由器密钥表示目的地的集合，以及还适用于分发所述聚集路由器密钥和相关联的聚集指令到能够执行路由聚集和解聚集的路由器，由此使得所述路由器能够基于所分发的信息来配置它们自己的转发表。

25.如权利要求24所述的设备，还包括地址查询管理器(700a)，所述地址查询管理器适用于从查询端主机(A)接收有关目标端主机的地址查询，通过应用密钥推导函数KDF至少到与所述目标端主机相关联的目的地密钥来创建发送方密钥，以及将所创建的发送方密钥发送到所述查询端主机以响应所述地址查询，由此使得所述查询端主机能够通过将从所述发送方密钥生成的发送方标记附加到传送的数据分组，将数据分组传播到所述目标端主机，所述发送方标记将所述传送的数据分组引导到所述目标端主机。

Images