路由器中的基于接收到的分组的样式来生成路由的配置

摘要

路由器(例如，IPv6移动路由器的归属代理)被配置用于基于访问具有多个路由条目的路由表，来确定接收到的分组的目的地路由器(例如，IPv6移动路由器)，其中每个路由条目包括路由关键字和路由字段，路由字段指定了规定地址之一和计算标签，该规定地址指定目的地路由器。计算标签指定计算目的地路由器的确定地址(例如，IPv6移动路由器的归属地址)时要执行的规定函数。对于每个接收到的分组，路由器基于对应的路由关键字识别匹配路由条目，并且响应于在路由字段中检测到计算标签，选择性地执行对应函数以计算目的地路由器的确定地址。

说明书

技术领域

本发明涉及因特网协议(IP)路由器基于将接收到的IP分组的目的地地址关联到路由表条目而路由分组的方法。更具体地说，本发明涉及在用于IPv6移动网络的移动路由器的IP路由器中的路由聚合。

背景技术

为了提供连续的基于因特网协议(IP)的连通性，因特网工程任务组(IETF)已提出了用于改进对基于因特网协议(IP)的移动设备(例如，膝上型计算机、IP电话、个人数字助理等)的移动性进行支持的建议。IETF有两个主要从事移动网络的工作组，移动自治网络(MANET)工作组和NEMO(移动网络)，MANET工作组从事开发标准化的MANET路由规范以由IETF所采纳。NEMO利用移动IP(MIP)来提供移动网络和基础设施(如因特网)之间的连通性。NEMO中的关键组件是移动路由器，其代表其服务的移动网络处理MIP。

根据MANET工作组，“移动自治网络”(MANET)是由无线链路连接的移动路由器(和关联主机)的自治系统，其联合形成了任意图。路由器可自由地随机移动并任意组织其自身；从而，网络的无线拓扑可能迅速地发生无法预测的变化。这种网络可以独立方式操作，也可以连接到更大的因特网。

在Johnson等人的题为“Mobility Support in IPv6”的因特网草案中公开了“移动IPv6”协议，该草案可从www网址：http：//www.ietf.org/internet-drafts/draft-ietf-mobileip-ipv6-20.txt获得(这里通过引用并入所公开的全部内容)。根据Johnson等人，移动IPv6协议能够使移动节点从一个链路移动到另一个，而无需改变移动节点的IP地址。具体地说，移动节点被分配了“归属地址”。“归属地址”是被分配给在其归属链路上的归属子网前缀内的移动节点的IP地址。在移动节点位于归属链路内时，分组的地址为其归属地址的分组被利用传统的因特网路由机制路由到移动节点的归属链路。

移动节点还被分配有归属代理，归属代理用于在移动节点远离其归属链路时，注册该移动节点在其附接到因特网的附接点处使用的任何转交地址。转交地址是与移动节点相关联的IP地址，该移动节点具有远离其归属链路的特定链路(如，外部链路)的子网前缀。归属代理是移动节点的归属链路上的路由器，移动节点利用归属代理注册其当前转交地址。在移动节点远离其归属链路时，归属代理拦截归属链路上的定向到移动节点的归属地址的分组；归属代理封装分组，并通过隧道将分组发送至移动节点的已注册转交地址。

因而，移动节点总可由其“归属地址”寻址：可以利用该地址将分组路由到移动节点，而无需考虑移动节点当前到因特网的附接点。在移动到新的链路后，移动节点还可以继续与其他节点(固定或移动的)通信。从而，移动节点远离其归属链路的移动对于传输层和更高层的协议以及应用来说是透明的。

网络移动性的一个具体问题是传统的路由聚合对于移动路由器来说是不可行的。具体地说，传统的基于因特网的网络拓扑中的路由器被配置为基于根据公共地址的层次对子网分组来聚合路由。例如，顶层路由器(一个组织的主路由器，被配置为所有因特网流量到该组织的入口点)向因特网中的其他路由器广播，告知具有目的地地址项层前缀(如，IPv4的127/8)的所有分组都应当被发送到顶层路由器。

顶层路由器包括路由表，路由表包括路由条目。每个路由条目包括对应的前缀关键字和下一跳字段。前缀关键字被用来匹配进入分组的目的地地址(一般将网络掩码应用到目的地地址)；因而，路由器识别出具有与掩码后的目的地地址匹配的对应前缀关键字的条目，并将该分组路由到在对应的下一跳字段中指定的路由器。因而，单个路由器可以聚合多个路由，以到达被配置用来向这样的子网提供服务的路由器，所述子网的子网地址前缀值在127/8聚合值范围内(例如，127.192/10、127.192/10、127.192/10和127.192/10等)。每个子网一般包括附加的路由器，该附加路由器被配置用于路由在对应的规定地址空间内的分组。

然而，在移动联网的情况下，利用传统的聚合技术无法实现聚合，这是因为所有的移动路由器都经由其本身的归属网络上的各自的归属地址来定址。具体地说，网络的归属子网前缀是标识因特网拓扑内的归属链路的IP地址中的最初一组比特(即，IP子网前缀对应于移动节点的归属地址)。然而，移动路由器的归属地址可以不同于附接到该移动路由器的移动网络的子网前缀。因而，对于每个充当对应移动网络的附接点的移动路，归属代理由器都需要路由表条目。

发明内容

需要一种配置，该配置能够使路由器生成能够将到各个移动网络的移动路由器路由聚合的路由表。

还需要一种配置，该配置能够使因特网协议(IP)路由器建立多个路由的通用表示，以减小路由表大小。

还需要使路由器能够建立可扩展的路由表，以将分组经由各个移动路由器路由到具有各移动子网前缀的目的地移动网络，其中移动路由器的归属地址值不同于移动子网前缀。

还需要一种配置，该配置使路由器能够基于确定的路由执行路由操作，其中所述确定的路由是基于单个通用路由表达式和所提供的参数而生成的。

本发明满足了这些和其他的需要，在本发明中，路由器被配置用于基于访问具有多个路由条目的路由表，来确定接收到的分组的目的地路由器，其中每个路由条目包括路由关键字和路由字段，路由字段指定了一个规定地址和计算标签，这个规定地址指定了目的地路由器。计算标签指定计算目的地路由器的确定地址时要执行的规定函数。对于每个接收到的分组，路由器基于对应的路由关键字识别匹配路由条目，并且响应于在路由字段中检测到计算标签，选择性地执行对应函数以计算目的地路由器的确定地址。因而，可以部署具有这样路由表的路由器，该路由表具有用于执行函数的计算标签，这减小了存储目的地路由器的规定地址值的必要性，并且能够基于样式确定目的地路由器的地址。

本发明的一个方面提供了一种基于因特网协议(IP)的路由器中的方法。该方法包括：接收指定了目的地地址的数据分组；并从具有多个路由条目的路由表中识别出匹配路由条目。每个路由条目指定对应的路由关键字并具有路由字段。该方法还包括在匹配路由条目的路由字段中检测计算标签，所述计算标签指定在计算目的地路由器的确定地址时要执行的规定函数。响应于检测到计算标签，基于执行规定函数来计算确定地址，并且将数据分组输出到该确定地址。

本发明的另一方面提供了一种基于因特网协议(IP)的路由器。该路由器包括：被配置用于接收指定了目的地地址的数据分组的IP接口、路由表和路由资源。路由表具有多个路由条目，每个路由条目指定对应的路由关键字并具有路由字段。路由字段中的至少一个指定了计算标签，所述计算标签指定计算目的地路由器的确定地址时要执行的规定函数。路由资源被配置用于基于目的地地址，从路由表中识别匹配路由条目。路由资源还被配置用于响应于在路由字段中检测到计算标签，执行对应的规定函数以计算确定地址。IP接口被配置用于将数据分组输出到确定地址。

本发明的其他优点和新的特征将部分在下面的描述中得到说明，部分在本领域技术人员阅读下面内容后变得清楚，或者可通过实施本发明而获知。利用所附权利要求中具体指出的手段和组合，可以实现本发明并获得本发明的优点。

附图说明

参考附图，其中，在所有的附图中具有相同标号的元件代表相似的元件，在附图中：

图1图示了根据本发明实施例被配置用于生成基于样式的自动路由的路由表。

图2图示了基于图1的路由表条目生成路由的方法。

图3图示了根据本发明实施例的广域网，该广域网包括移动网络，移动网络中具有与规定的归属代理通信的各个移动路由器，其中归属代理包括用于基于样式的自动路由的路由表。

图4详细图示了图3的归属代理。

图5图示了来自图4的路由字段的示例性函数，其用来计算图3的目的地移动路由器的归属地址。

图6图示了根据本发明实施例生成目的地路由器的地址的方法。

具体实施方式

所公开的实施例集中于一种路由器，该路由器被配置用于在路由接收到的分组时，其中，根据规定函数计算出的下一跳地址来确定下一跳路由器的下一跳地址。基于接收到的分组内的分组信息，例如基于在接收到的分组中指定的目的地地址，来计算下一跳路由器的下一跳地址(也称为目的地路由器的确定地址)。因而，目的地路由器的确定地址的计算能够将多个路由器地址聚合到单个路由表条目，该单个路由表条目指定了描述多个路由器地址的聚合的规定函数。

图1图示了根据本发明实施例被配置用于生成基于样式的自动路由的路由表102。路由表102包括指定前缀关键字P(也称为路由关键字)的前缀字段104、指定规则(例如，规定函数)R的路由字段106和指定参数(p)的参数字段108，以根据函数R(D、分组、P、p)执行规则R。如下所述，通过执行函数R(D、分组、P、p)来获得下一跳网关地址。

图2图示了基于图1的路由表条目生成路由的方法。响应于在步骤110接收到分组，具有路由表102的路由器在步骤112从接收到的分组中提取目的地地址D和规定参数列表L(例如，在接收到的分组中指定的显式头部值)。路由器在步骤114利用目的地地址D作为关键字，对路由表102执行最佳匹配算法搜索，以在步骤116定位匹配条目(条目“E”)118。

假定在步骤116中定位了匹配条目118，则路由器在步骤120从前缀字段104中取得对应的前缀P，从路由字段106中取得对应的规则R，从参数字段108中取得对应的参数列表p。路由器在步骤122基于目的地地址D、来自接收到的分组的参数P、来自前缀字段104的匹配地址前缀P和/或来自参数字段108的对应存储的参数p，来执行函数R，进而计算网关地址G。如果网关地址是不连接到路由器的网关的地址，则路由器在步骤124在路由表102中执行递归查找(例如，利用网关地址重复步骤114到122)，以获得到达该网关的下一跳路由器。然后，在步骤126将分组转发到下一跳路由器(NH)。

因而，基于存储用于计算目的地地址的规定函数，可以简化路由器条目。如下所述，所公开的配置(利用在路由表中指定的规则来计算目的地地址)对于移动IP尤为有益。

图3图示了根据本发明实施例具有路由器12的广域网10，其中路由器12被配置用于计算确定的地址，以将接收到的分组路由到目的地路由器(例如，14a、14b、14c等)。如图3所示，根据以上并入的Johnson等人的因特网草案，路由器12被实现为归属代理(HA)，而目的地路由器14a、14b和14c被实现为移动路由器，其充当各个移动网络16a、16b和16c到广域网10的附接点。还要注意，移动路由器14d当前位于其归属网络18，其中移动路由器14d在归属网络18内具有到归属代理12的归属链路20。

如图3所示，使用由IETF请求注解(RFC)1884(这里通过引用并入其全部内容)指定的地址表示，归属网络18具有值为“ABCD::/64”的IPv6归属子网前缀值28。具体地说，128比特的IPv6地址表示为具有由“:”符号隔开的8个16比特部分；因而，128比特地址值“1080:0:0:0:0:0:0:417A”指定了这样的地址，该地址的最前16比特是“1080”(十六进制)，最后16比特是“417A”。根据RFC 1884，该地址值可利用双冒号“::”简写为“1080::417A”，表示指定值之间的所有比特都是0。

如图3所示，移动网络16a、16b和16c的地址前缀值21分别为DE:AB:0:0/64、DE:AB:0:1/64和DE:AB:0:2/64。提供移动网络16a、16b和16c的附接点的各个附接路由器14a、14b和14c的归属地址值42分别为ABCD::0、ABCD::1和ABCD::2。另外，移动路由器14a、14b和14c的转交地址44分别为FBCD::10AA、FAEC::0211和F0A1::22。

现有的在移动主机22和对端节点(CN)24之间路由分组的方法涉及对应的移动路由器(如14c)经过对应的双向隧道(如26c)来经由归属代理12发送分组。一旦经由隧道(如26c)接收到分组，归属代理12就将分组路由到利用现有的路由协议识别出的因特网路由器(未示出)，以提供到达对端节点24的能力。对端节点通过输出分组向移动主机22发送回复，该分组在其目的地地址字段中指定了移动主机22的地址(例如，“DE:AB:0:2::FC0A”)。归属代理12还向因特网10内的路由器发送路由器广播消息，指出归属网络18(即，归属子网前缀为ABCD::/64的网络)被配置用于路由目的地网络前缀为“DE:AB::/32”的分组，其中128比特地址的前32比特等于“DE:AB”。因而，因特网路由器会将来自CN24并去往移动节点22的分组路由到归属代理12。

然而，由于移动路由器(例如，14a、14b、14c等)的归属地址42不能以各个移动网络16a、16b、16c的地址前缀21来聚合，因此传统的方法对于每个对应移动网络需要单独的路由表条目，其中移动网络地址前缀(例如，“DE:AB:0:2/64”)将指定对应移动路由器(例如14c)的归属地址(例如，“ABCD::2”)作为其网关地址。因此，传统的路由表会由于大量移动网络的存在而变得不堪重负，例如在车辆制造商制造的每个车辆中安装移动网络，这导致每年生成百万计的移动子网。

根据所公开实施例，归属代理12包括路由模块30，路由模块30被配置用于基于执行匹配的路由表条目内指定的规定函数f(D)，来计算目的地路由器的确定地址。如下所述，规定函数被用来定义移动路由器14和它们各自的移动网络16之间的映射特征，从而使所有移动网络16的路由信息都能由单个路由条目指定。

图4详细图示了根据本发明实施例的路由器12。路由器12包括被配置用于发送并接收数据分组的因特网协议接口32和路由模块30。路由模块30包括路由表34和路由资源36。在路由器12被实现为移动路由器14的归属代理的情况下，路由模块30还包括绑定缓存38，绑定缓存38包括指定归属地址42和转交地址44的绑定缓存条目40。

路由表34包括多个路由条目(例如，46a、46b、46c和46d)，每个条目指定了对应的路由关键字48和路由字段50。每个路由关键字48取决于现有的网络拓扑和聚合特性，指定了对应的IP子网前缀。例如，路由条目46a、46b和46c的路由关键字48指定了具有关联前缀值的各个子网(未示出)的地址前缀值“124::/32”、“125:125:500::/64”和“125:125::/48”。如图4所示，路由条目46a、46b和46c的路由字段50指定了连接到路由器12的下一跳路由器的显式地址。

路由表34还包括具有路由关键字48的路由条目46d，其中路由关键字48指定了聚合的移动网络16的地址前缀47(例如，“DE:AB::/32”)；换句话说，移动网络16共享被用作路由关键字46d的地址前缀。路由条目46d还包括指定计算标签52的路由字段50。计算标签52指出要执行至少一个函数(F)，以计算目的地路由器的确定地址。如图4所示，计算标签52的形式如下：

<地址类型><第一输入变量><第二输入变量><函数调用><开销声明>

<地址类型>参数指出该字段包括扩展条目，这种情况下用于利用所提供的参数计算IPv6通用路由。输入变量(“DE:AB:*::/32”和“ABCD::*/64”)指定了在执行指定函数“F1”和“F2”的函数调用期间要使用的变量，其受到在开销声明中指定的规定开销的限制。如下结合图5所示，字符“*”代表取决于指定函数要从参数中提取的/在参数中插入的变量。所图示的计算标签52只是用于指定路由字段50内的参数和函数的示例性图示。

如图4所示，路由资源36包括关键字索引资源54和地址计算资源56。关键字索引资源54被配置用于基于检测目的地地址和对应的路由关键字48之间的匹配，从路由表34中识别出接收的IP数据分组的匹配路由条目。如下所述，地址计算资源56被配置用来计算用于将数据分组转发到目的地路由器的地址；在路由器12被实现为归属代理的情况下，地址计算资源56被配置用于计算为目的地主机22提供服务的移动路由器14的归属地址。

图5图示了由地址计算资源56执行在路由条目46d中指定的函数的过程。具体地说，路由资源36响应于在匹配路由条目(例如46d)的路由字段50中检测到计算标签52，发出对地址计算资源56的函数调用。地址计算资源56解析计算标签52，并执行在计算标签52中指定的规定函数。

如图5所示，地址计算资源56包括其应用运行时环境内的上下文定义信息60，上下文定义信息60定义函数F1和F2：如图5所示，上下文定义信息60指出函数F1提取所提供的目的地地址的规定比特(这种情况下是参数的33-64比特)；上下文定义信息60还指出函数F2将第一参数(x)应用到第二参数(y)的97-128比特。在移动计算的上下文中，上下文定义信息60被用来提供函数操作62，其中函数F1(目的地地址)被用来确定移动路由器标识符(MR_ID)；然后移动路由器标识符被用作第二函数F2(MR_ID，通用下一跳)的参数，以确定下一跳地址(例如，归属地址)。

地址计算资源56对计算标签52的实际执行64基于确定移动路由器标识符68，从而计算出地址66。具体地说，地址计算资源56提取目的地地址“DE:AB:0:2::FC0A”的33-64比特，以获得移动路由器标识符(“MR_ID＝0:2”)68。注意33-64比特在归属子网前缀28的64比特地址前缀范围内。然后，地址计算资源56通过以移动路由器标识符68(“0:2”)取代规定地址前缀(例如，归属子网前缀“ABCD::*/64”)28的变量“*”，来执行函数F2，导致产生移动路由器14c的确定归属地址“ABCD::2”66，其中移动路由器14c充当目的地主机22的附接路由器。

图6图示了根据本发明实施例归属代理12计算归属地址以路由接收到的分组的方法。图2和图6中所描述的步骤可以实现为存储在计算机可读介质(例如，硬盘驱动器、软驱、随机存取存储器、只读存储器、EPROM、CD等)上或经由计算机可读介质(例如，传输线、光纤、利用电磁载波的无线传输介质等)传播的可执行代码。

该方法开始于步骤80，其中归属代理12经由广域网10接收来自对端节点24的分组。在步骤82，关键字索引资源54基于接收到的分组的目的地地址(例如“DE:AB:0:2::FC0A”)，识别匹配的路由条目(例如46d)。在步骤84，路由资源36检测出匹配路由条目46d的对应路由字段50指定了计算标签52，并且作为响应，在步骤86生成对地址计算资源56的函数调用。

在步骤88，地址计算资源56解析计算标签52，并且在步骤90从其应用运行时环境中获取相关参数，如函数F1和F2的定义。在步骤92，地址计算资源56基于规定函数F1和F2的执行，计算确定的地址66，如图5所示，并将确定的地址66(例如，“ABCD::2”)提供到路由资源36。

在步骤94，假定确定的地址66指定了移动路由器14的归属地址，则路由资源36在步骤96从绑定缓存40取得移动路由器14c的对应转交地址，并且在步骤98将数据分组经由其对应隧道26c输出到移动路由器14c。

在步骤94，假定确定的地址66不是用于移动路由器的地址，例如在路由器12被实现为通用路由器的情况下，则如果在步骤100确定地址并不标识直接连接到作为下一跳的当前讨论的路由器12的另一个路由器，那么路由资源36就利用确定地址作为地址关键字，重复地址查找，包括识别匹配路由条目。在确定的地址66标识了当前讨论的路由器12和目的地节点之间的中间路由器的情况下，执行地址查找的重复，从而使路由器12能识别用于转发分组的下一跳地址。

根据所公开实施例，基于根据匹配路由条目内的计算标签计算确定的地址，来确定下一跳路由器的地址，从而能够在接收分组时计算分组的目的地路由器。因而，路由器可以基于网络拓扑规则生成路由，从而能够在网络拓扑未能必要地提供二进制的路由聚合的情况下提供有效的路由聚合。所公开的配置尤其有益于优化被配置用于维护移动网络路由的路由表的情形，在该情形中，传统的聚合技术不能被用于移动路由器所建立的移动路由。另外，所公开的配置消除了路由表中手工条目的必要，减小了路由表的大小，并且通过使搜索路由表以识别匹配路由条目的工作量最小而简化了路由处理。

尽管已结合了迄今为止最实用和最优选的实施例描述了所公开实施例，但是应当理解，本发明并不限于所公开实施例，相反地，本发明试图覆盖包括在所附权利要求精神和范围内的各种修改和等同配置。