控制路由选择的方法

暂无

技术领域\n本发明涉及电信信号的路由选择。具体地说，本发明涉及一种把电信信号 路由选择到固定和移动电信介质的方法，使得用户可以在任何一种介质上以相 同方式使用类似的服务，并通过交换设备和其他基于网络的设备的更大的通用 性来允许系统运营商降低成本。本发明关注于基于分组的通信的路由选择(例 如使用所谓的“因特网协议”(IP)在“因特网”中使用的路由选择)。\n背景技术\n当前的移动介质系统的设计结构是，移动用户和相关的系统在网络接口(通 常是无线电基站)合作以使得一个移动节点能够从与一个基站通信改变为与另 一个基站通信，并使得网络能够更新该新位置的智能点。在蜂窝网络中，这些 智能点是本地位置寄存器和访问者位置寄存器(HLR和VLR)，而在“移动IP” 中这些位置被称为本地代理和外部代理。在两种情况下，“访问者”位置寄存器 或“外部”代理都保持一个只与那些正在与在它们的监管下的基站合作的用户 有关的记录，而它们对应的“本地”位置寄存器或“本地”代理则保持一个有 关它们的相关用户的永久记录，其中包括一个有关每个“本地”单元正与哪个 VLR或外部代理合作的记录。一个入局消息中的地址标识出相关的HLR/本地代 理，参考该信息来识别适当的VLR/外部代理以得到更具体的路由选择细节。这 允许在靠近用户当前位置的VLR/外部代理内实现微小的位置变化，而无需通知 距离较远的HLR/本地代理，从而显著减少了信令开销。\n移动性的其他成本是提供该本地代理/外部代理接口，尤其是对于分组系 统，还包括隧穿(把消息从一个地址转发到另一个地址)的成本，地址用尽(无 法重新使用一个正发生转发的地址)，和三角路由选择。\n在固定介质系统中，IP路由选择基于从潜在目的地到潜在发送者的IP地址 块或前缀的分配(具有相关的度量或路由成本)，使得发送者和中间路由器可以 确定到目的地的最好的下一个跳点(相邻路由器)。为网络中的所有目的地预先 计算这些路由，使得发送者可以在产生信息时立即发送。当源和目的地具有固 定位置，并且通信带宽足以满足路由的穷尽交换时，路由的预先计算和所配置 的路由选择交换技术是可能的。但是，随着漫游比例的增加，这种模型趋于失 败，需要一个更动态的路由选择方法。\nR.Ramjee，T.La Por，S.Thuel，K.Varadh在1999年2月19日公开了 一个作为因特网草案的称为“HAWAII”的提议，名称是“使用HAWAII的IP微 移动性支持”，刊登在因特网工程工作组网站 HTTP：//www.ietf.org/internet-drafts/draft-rimjee-micro-mobility-hawa ii-00.txt。HAWAII使用专门的路径建立方案，当在一个路由选择域中时在特定 的路由器中安装基于主机的转发记录，以支持域内微移动性，并且默认使用“移 动IP”用于域内微移动性。在HAWAII中，当移动主机在域内移动的同时其保留 自己的网络地址。HAWAII体系结构依赖于域中的一个网关路由器(称为域根路 由器)，该域中的默认路由被指向该域根路由器。基于每个移动主机的永久IP 地址为其分配一个本地域。路径建立方案更新一个域中的单个路由选择路径， 使得在无线链路层的越区切换之前和之后到移动主机的接续都是可能的。只有 那些沿着域根路由器和当前服务于移动主机的基站之间的单个路由选择路径设 置的路由器具有用于移动主机IP地址的路由选择表记录。该域中的其余路由器 把任何寻址到移动主机的分组沿着依赖于路由选择域的树型性质的默认路由 (以域根路由器为根)上行路由选择，以提供与沿着该单个路由选择路径(对 于该单个路由选择路径，路由器具有用于移动主机IP地址的单独主机记录)向 移动主机进行的下行路由选择的交叉。\n在HAWAII中，域之间的移动性由“移动IP机制”支持。本地域根路由器 被指定为本地代理，通过外部域根路由器转发被封装的IP分组。\nHAWAII提议的缺陷包括移动IP隧道集中在网络的核心中的很少几个节点 (域根路由器)中，使得任何这些节点的故障都可能导致由故障节点处理的所 有移动IP状态和相关话路的大规模故障。此外，由于从本地域外部到本地域内 以及相反方向的所有路由选择都必须通过本地域根路由器发生，因此本地域根 路由器的故障也可能导致大规模故障。\n发明内容\n根据本发明的一个方面，提供一种控制无连接路由选择协议网络中分组的 路由选择的方法，该无连接路由选择协议网络包括由分组传输链路互连的分组 交换节点的基础结构，和多个接入节点，在所述基础结构中可以为一个给定网 络地址把一个路由选择路径指向所述接入节点，其中该路由选择路径由沿着其 设置的分组交换节点中保持的数据定义，所述方法包括：\n为第一网络地址沿着第一路由选择路径对分组进行路由选择，该路由选择 路径被指向一个第一接入节点，该第一接入节点通过一通信链路使用所述第一 网络地址来服务于一个移动节点；\n指定一个不同于从第一接入节点到移动节点的通信链路的接口，在该接口 上用于把沿着所述第一路由选择路径到达的分组转发到第二接入节点；\n在指定所述接口之后，对移动节点的通信链路进行越区切换，使得第二接 入节点服务于所述移动节点；\n响应于通信链路的越区切换，为所述第一网络地址改变所述基础结构中的 路由选择，以创建一个指向所述第二接入地址的第二路由选择路径用于所述第 一网络地址；\n响应于所述第二路由选择路径的创建，为所述第一网络地址改变所述基础 结构中的路由选择，以除去所述第一路由选择路径；和\n通过所述第二路由选择路径把分组路由选择到所述第二接入节点。\n通过在第一接入节点指定一个不同于通信链路的转发接口，并改变路由选 择以不在创建第二路由选择路径之前除去第一路由选择路径，可以避免基础结 构中的分组丢失，即使在通信链路的丢失和基础结构中路由选择的改变之间存 在未知的定时差。\n附图说明\n本发明的其他方面和优点将从下面参考附图以示例方式描述的实施例中得 到更好的理解，其中：\n图1示意性表示根据本发明一个实施例的固定/移动拓扑结构的示例；\n图2到11示意性表示根据本发明一个实施例的基站间越区切换和伴随的路 由选择更新；\n图12到16表示根据本发明另一个实施例的基站间越区切换和伴随的路由 选择更新；\n图17到25表示根据本发明一个实施例把路由选择恢复到一个本地基站；\n图26示意性表示根据本发明一个实施例在路由选择节点中保持的一个路由 选择协议数据表；和\n图27表示根据本发明一个实施例在路由选择节点中保持的一个下一跳点转 发表。\n具体实施方式\n现在参见图1，示出了根据本发明一个实施例的固定/移动拓扑结构的示例。 举例来说，该拓扑结构包括形成了一个自主系统(AS)的三个分组交换网络2， 4，6，其范围由图1中的深阴影部分示意性表示。对术语“自主系统”的一个 定义是“在相同管理下的一组路由器和网络”(“因特网中的路由选择”， Christian Huitema，Prentice-Hall，1995，page 158)。此处，术语“自主系统” 还表示本领域中的一个路由选择域，并且还表示一个网络，或一组网络，该网络 具有运行相同路由选择协议的路由器。一个自主系统可以连接到其他自主系统， 形成一个全球互连网络，例如因特网(下面以此为例)。路由选择协议是内部 网关协议，并且与其他自主系统的通信是通过诸如边界网关协议(BGP)之类 的外部网关协议实现的。已知的内部网关协议的例子是路由选择信息协议 (RIP)和最短路径优先开放(OSPF)。\n形成自主系统的固定基础结构的网络2，4，6包括多个因特网协议(IP) 分组交换节点，其形式是在AS中把不同网络2，4，6互连的多个核心路由器 (CR)，多个边沿路由器(ER)和桥式路由器(BR)。所有这些分组交换节点 运行单个IP路由选择协议，在下面将更详细地描述其一个实施例。\n一个或多个外部网关路由器(EGR)把自主系统连接到全球因特网的其他 自主系统。\n图1所示的自主系统同时为移动主机和固定主机(即静止主机)执行路由 选择，对移动主机来说，根据移动主机的移动性的结果改变AS内的路由选择， 对固定主机来说，没有这种路由选择改变。\n可以通过无线链路把移动节点连接到边沿路由器，在所示例子中，无线链 路是一个使用由移动网络运营商提供的基站(BS)路由器的蜂窝无线电链路(另 一个可能类型的无线链路是红外链路)。蜂窝无线电链路可以是时分多址 (TDMA)系统链路，例如GSM，或码分多址(CDMA)系统链路，例如“CDMA 2000”。移动节点的形式是单独的移动主机14，和/或具有连接到其上的多个主 机的移动路由器16，它们在任何给定时间分别与一个或多个(例如，在CDMA “软越区切换”情况下)BS路由器进行无线电通信。BS路由器可以控制与无 线电天线同处一地的多个基地收发信台(BTS)，在无线电天线周围形成蜂窝系 统的各个“小区”。\n移动节点14，16在蜂窝无线电通信网络的小区间移动。如果一个BS路由 器服务于多个小区，一个在小区间越区切换的移动节点可以继续通过相同的BS 路由器接收分组数据。但是，一旦一个移动节点移动到它接收服务所用的BS 路由器的范围之外，越区切换到一个新小区可能需要改变AS内的路由选择。 从所述移动节点始发和指向所述移动节点的、并且在越区切换前通过一个给定 BS路由器使用该节点的IP地址的标识符进行路由选择的数据分组，可能需要 在越区切换后通过一个不同的BS路由器为相同的IP地址进行路由选择。一个 移动节点可以在从一个BS路由器到另一个BS路由器的越区切换期间通过AS 加入与一个不同的主机的通信话路。因为在传输层的连接(例如，在TCP/IP 连接中)是部分地由移动节点的IP地址定义的，当一个移动节点接收来自一个 不同BS路由器的服务时，希望这种路由选择中的变化能允许使用相同的IP地 址使这种连接继续。\n固定主机可以通过局域网(LAN)10连接到边沿路由器，局域网10运行 诸如以太网协议的局域网协议。固定主机也可以使用由因特网接入提供商提供 的网络接入服务器(NAS)20通过公共服务电话网络(PSTN)12连接到边沿 路由器。NAS 20使用诸如PPP或SLIP的协议，在拨号的基础上动态地把固定 IP地址分配给连接到NAS 20的固定主机，并通过一个相关的边沿路由器对从 每个固定主机始发或指向每个固定主机的IP分组进行路由选择。虽然NAS 20 在动态基础上分配IP地址，在一个接入话路期间或一个较长时段期间，为所分 配的IP地址对分组进行路由选择所用的边沿路由器并不改变。因此，除非是由 于AS内部的因素(例如链路故障或业务量管理)，在自主系统内的路由选择不 需要为每个固定主机改变。\n内部网关协议，即本发明的该实施例中在AS中使用的单个IP路由选择协 议，是时间定序路由选择算法(TORA)路由选择协议的修订版本，该协议在 以下参考文献中描述：Vincent D Park和M Scott Corson在INFOCOM’97会议 论文中发表的“用于移动无线网络的高度自适应分布式路由选择算法”，四月 7-11，Kobe，日本；Vincent D Park和M Scott Corson在ISCC’98会议论文中发 表的“时间定序路由选择算法和理想链路状态路由选择的性能比较”，1999年 6月30至7月2日，雅典，希腊。\nTORA路由选择算法分布地执行，提供无循环路由器(loop-free routers)， 提供多路由选择(以缓解拥塞)，快速建立路由(使得可以在拓扑结构改变前 使用该路由)，并通过在可能的情况下把算法对拓扑结构变化的反应局部化来 使通信开销最小(保存可用带宽并提高可升级性)。\n把算法分布在那些只需要有关邻近节点的维护信息(即，一个跳点知识) 的节点中。这确保所有路由是无循环的，并且通常为需要一个路由的任何源/目 的地对提供多径路由选择。由于通常建立多个路由，很多拓扑结构的变化不需 要AS内的路由选择更新，因为有单个路由就足够了。在需要反应的拓扑结构 的变化之后，协议重新建立有效的路由。\nTORA协议把一个网络建模为一个图形G＝(N，L)，其中N是一个有限的节 点集合，L是一个初始未定向链路的集合。每个节点i∈N具有一个唯一节点标 识符(ID)，并且每个链路(i，j)∈L允许双向通信(即，由一个链路连接的节点 可以在两个方向中任何一个方向相互通信)。可以随后对每个初始未定向的链 路(i，j)∈L指定下面三个状态之一：(1)未定向，(2)从节点i指向节点j，或 (3)从节点j指向节点i。如果链路(i，j)∈L从节点i指向节点j，可以说节点i 来自节点j的“上游”，而节点j来自节点i的“下游”。对于每个节点i，i的“邻 居”Ni∈N被定义为节点j的集合，使得(i，j)∈L。每个节点i总是知道集合Ni 中的它的邻居。\n为需要路由选择的每个目的地(例如，由一个主机IP地址标识)运行该协 议的一个逻辑上分离的版本。\nTORA协议可以分离为三个基本功能：产生路由，保持路由，和删除路由。 产生从一个给定节点到目的地的路由需要建立从该节点导向该目的地的定向链 路的序列。产生路由实质上对应于把方向指定给一个未定向网络或网络部分中 的链路。用于完成该任务的方法是一个询问/答复过程，其建立一个以该目的地 为根的定向非循环图形(DAG)(即，该目的地是唯一不具有下游链路的节点)。 这种DAG可以称为“面向目的地的”DAG。保持路由涉及到以一定方式对网 络中的拓扑结构变化作出反应，使得在一个有限时间内重新建立到该目的地的 路由。在检测到一个网络分区时，把(在已经与目的地分隔的网络部分中的) 所有链路标记为未定向以删除无效路由。\n该协议通过使用以下三个不同的控制分组来完成这三个功能：询问 (QRY)，更新(UPD)，和清除(CLR)。QRY分组用于产生路由，UPD分组 同时用于产生和保持路由，CLR分组用于删除路由。\n在任何给定时间，把一个称为“高度”Hi＝(τi，oidi，ri，δi，i)的定序五元组与 每个节点i∈N相关联。概念上，与每个节点相关联的五元组代表由以下两个参 数定义的节点高度：一个参考水平和一个相对于该参考水平的增量。参考水平 由五元组中的前三个值代表，而增量由后两个值代表。每当一个节点由于链路 故障丢失了它的最后一个下游链路时，定义一个新参考水平。代表参考水平的 第一个值τi，是一个被设置为该链路故障的“时间”的时间标记。第二个值oidi， 是始发者ID(即，定义该新参考水平的节点的唯一ID)。这确保可以完全按照 字典顺序对参考水平排序。第三个值ri，是一单个位，用于把每个唯一参考水平 划分为两个唯一子水平。该位用于区分原始的参考水平和它的对应的、较高反 射的参考水平。代表增量的第一个值δi，是一个整数，用于相对于一个公共参考 水平对节点排序。这个值有助于参考水平的传播。最后，代表增量的第二个值 i是该节点自身的唯一ID。这确保具有公共参考水平和相同δi值的节点(和实 际上所有节点)总可以完全按照字典顺序排序。\n每个节点i(除了目的地)保持它的高度Hi。最初，网络中每个节点(除 了目的地)的高度被设置为NULL，Hi＝(-，-，-，-，i)。随后，可以根据协议的规 则修改每个节点i的高度。除了它自己的高度外，每个节点在一个路由选择协 议数据表中保持有针对具有网络中的一个现有DAG的主机IP地址的记录，这 些记录包括一个高度阵列，其中每个邻居j∈Ni有一个记录HNij。\n每个节点i(除了目的地)还在路由选择协议数据表中保持一个链路状态 阵列，其中每个链路(i，j)∈L有一个记录LSij。链路的状态由高度Hi和HNij确 定，并从较高节点指向较低节点。如果一个邻居j高于节点i，那么把该链路标 记为上游。如果一个邻居j低于节点i，那么把该链路标记为下游。\nTORA协议最初被设计用于移动Ad-Hoc网络(MANET)，其中路由器是 移动的并且通过无线链路互连。但是，在本发明的该实施例中，在一个包括由 固定链路互连的固定路由器的固定基础结构的自主系统(例如图1所示系统) 中使用一个改进的TORA协议，以便在一个移动主机改变它到基础结构的连接 点时提供固定基础结构中的路由选择改变。\n图26示意性地表示根据该实施例可以在路由器中保持的一个路由选择协 议数据表的例子。\n对于具有网络中的DAG的每个主机IP地址(或者，在下面将要详细描述 的聚集DAG的情况下，对于每个地址前缀)IP1，IP2等等，存储该存储节点 Hi(IP1)，Hi(IP2)等等的高度。而且，存储每个邻近邻居(例如w，x，y，z)的身 份和该邻居的高度HNiw(IP1，IP2，...)，HNix(IP1，IP2，...)，HNiy(IP1，IP2，...)和 HNiz(IP1，IP2，...)。最后，可以针对对应于每个邻居的每个链路身份(L1，L2，L3， L4)把每个IP地址(或前缀)的链路状态阵列存储为多个标记的形式，这些 标记用于表示一个上游链路(U)，一个下游链路(D)，或一个未定向链路(-)。\n在路由选择协议数据表中保持的链路状态阵列允许在保持该数据的路由器 中本地地进行下一跳点转发判定。对于一个充分互连的网络，每个路由器应该 具有至少一个下游链路。如果只存在一个下游链路，则选择该链路作为下一跳 点转发链路。如果存在多于一个的下游链路，可以例如根据两个链路上的当前 业务量负载来选择一个最佳下游链路。在任何情况下，把所选择的链路输入到 按IP地址列出的下一跳点转发数据表中。例如图17所示的下一跳点转发表被 保持在高速缓存存储器中，以便在需要路由选择的IP分组到达该路由器时进行 快速访问。该表按每个IP地址(或前缀)IP1，IP2等等存储所选择的下一跳点 转发链路(L2，L1，...)。\n对路由器的固定基础结构以及下面将描述的本发明其他方面的使用可以允 许AS内的路由选择聚集，特别是对于移动主机的IP地址。下面将给出IP定 址的一个简单描述，特别是如何使用可变长度前缀来提供IP路由选择网络中的 路由选择聚集。\nIP地址目前由预定数量(32)的位组成。在过去，IP地址是在非结构化基 础上分配的(称为“平面”定址方案)。类定址通过把地址拆分为网络前缀和 主机字段引入了两级路由选择分层结构的概念。用户被分配A类，B类或C类 IP地址以简化路由选择和管理。\n在A类中，位0标识A类，位1-7标识网络(126个网络)，位8-31标识 主机(16百万个主机)。\n在B类中，位0-1标识B类，位2-15标识网络(16,382个网络)，位16-31 标识主机(64,000个主机)。\n在C类中，位0-2标识C类，位3-23标识网络(2,097,152个网络)，位24-31 标识主机(256个主机)。\n一个两级分层结构仍然在网络中的主机之间留下一个平面路由选择分层结 构。例如，A类地址块具有16百万个主机，这将导致网络中的所有路由器包 含16百万个路由选择表记录。已经开发了子网划分来允许一个主机地址块被 拆分为一个可变长度子网字段和主机字段。这允许AS中的路由器仅保持子网 的路由选择表记录(为每个子网上的所有主机提供路由选择聚集)。使用子网 掩码来使路由器能够识别地址的子网部分。\n根据本发明的该实施例，通过把一个主机IP地址块(即，共享一个或多个 前缀的IP地址的邻接序列)分配给一个接入节点(例如一个BS路由器)，并 在移动主机的接入话路期间动态地把来自该块内的IP地址分配给移动主机，可 以提供路由选择聚集。当一个移动主机在加电后向蜂窝网络登记时，该服务BS 路由器分配一个IP地址并高速缓存移动主机的无线链路标识符与所分配的IP 地址之间的绑定关系(binding)。一个聚集路由选择方案(在本实施例中的一 个聚集DAG)是在把移动主机要在它的接入话路期间使用的IP地址分配给它 之前在AS内预先计算的。在移动主机断电之后，IP地址被返回到其BS路由 器，该BS路由器可以把该IP地址分配给另一个移动主机。由一个BS路由器 分配的移动主机IP地址将具有一个聚集DAG，直到至少一个移动主机远离， 在此情况下，聚集DAG将保留在原位，但是在受一个移动性专用路由选择更 新程序影响的路由器上将产生一个主机特定异常(该更新仅改变已经远离的单 个移动主机的路由选择)。\n在AS中为由一个BS路由器拥有的地址前缀进行的路由预先计算是由注 入每个前缀的一个更新消息(此处称为“优化”(OPT)分组)并建立聚集DAG 的该拥有BS路由器实现的，该更新消息跨越AS溢出并有效地作为一个前缀 通告。OPT分组由拥有该IP地址前缀并控制聚集DAG的BS路由器发送。OPT 分组传播到网络中的所有其它节点(不管它们的当前高度(如果设置的话))， 并把这些高度设置(重新设置)为“全零”参考水平，即TORA高度的前三个 值(τi，oidi，ri)都被设置为零。第四个高度值δi，被设置为该OPT分组自BS路 由器发送开始所经历的跳点数目(这类似于已知的TORA源启动的DAG产生 机制中的UPD分组传播)。可以增加一个1的增量以表示从BS路由器到移动 节点的跳越。第五个高度值i被设置为节点ID。\n一旦AS中存在一个聚集DAG，AS中的每个分组交换节点具有用于所关 注的IP地址前缀的下一跳点转发表记录。当一个分组到达一个需要路由选择的 节点时，该节点在它的下一跳点转发表中搜索最长的匹配地址记录，下一个路 由选择判定就基于该最长匹配地址记录，如果使用该IP地址的移动节点还没有 远离该拥有BS路由器，那么该最长匹配地址记录就将是该IP地址前缀。通过 提供AS内的聚集DAG，可以使每个分组交换节点上的路由选择表大小和路由 选择处理最小。\n但是，当一个移动节点在无线电链路层从它首先接收网络中服务的BS路 由器越区切换时，在由移动节点的移动性造成的路由选择更新影响的(有限数 目的)分组交换节点中的路由选择协议数据表和下一跳点转发表中产生一个单 独的主机地址记录。这些节点继续存储对应的聚集地址记录，但是根据最长匹 配搜索、使用主机地址记录来把分组路由选择到移动节点的IP地址。\nTORA高度保持算法属于由E Gafni和D Bertsekas在1991年1月在IEEE 通信学报中发表的“用于在具有频繁改变的拓扑结构的网络中产生无循环路由 的分布式算法”中最初定义的相同算法类别。在该类别内，一个节点可以仅“增 加”它的高度；它可以从不降低它的高度。但是，在本发明的该实施例中，提 供一个算法改进以确保在一个BS路由器间的越区切换后，一个节点的转发行 为是：当存在相邻节点的多个路由选择接口时，它通过一个路由选择接口把分 组转发到一个相邻节点，其中从该相邻节点最后接收到了一个有关移动性的路 由选择更新。路由器的路由选择协议数据表中存储的高度五元组中(τi，oidi，ri，δi，i) 的τ时间值(作为一个按移动节点的IP地址和邻居列出的记录)被允许变成“负 的”，即小于零，以表示一个有关移动性的更新已经发生，并且负τ时间值的数 值随着一个给定IP地址的每个有关移动性的路由选择更新的发生而增加。因 此，最近的有关移动性的更新由较大的负τ时间值指示。应注意，虽然有关移 动性的路由选择更新由一个负τ时间值区分，也可以使用其它指示符，例如一 个一位标记来代替该负标记。\n当一个移动节点改变BS路由器联属时，它通过把τ时间值降低例如一个 整数来降低它的高度值，并且把该新值作为一个与移动节点的IP地址相关的 DAG的由移动站启动的更新的一部分传播到AS中的有限数量的节点，这将在 下面进一步描述。一个具有多个下游邻居的节点向最近激活的下游链路进行路 由选择。高度仍然被全部排序(因此保护了路由选择循环自由)。\n本发明的再一个方面是，在无线电链路层进行的移动节点的越区切换期 间，提供一个临时的短期隧穿机制，从而使到达移动节点所越区切换离开的BS 路由器的数据分组可以被转发到移动节点被越区切换到的BS路由器。IP分组 交换网络中的隧穿可以通过利用一个新IP首部(寻址到新BS路由器的IP地 址)封装该数据分组来实现，称为“IP-in-IP隧穿”。在新BS路由器，把分组 解封装并通过无线链路转发到该移动节点。隧道设置、信令和验证机制可以是 那些在C Perkins等人在1996年10月的1ETF RFC 2002中发表的“IP移动性 支持”中描述的“移动IP”中使用的机制。在利用“移动IP”使能所有BS路 由器的情况下，“移动IP”还可以用于允许把分组转发到移动到一个不同AS的 移动节点。其它可能的隧穿协议包括UDP隧穿(其中把一个UDP首部添加到 一个入局分组)，GRE隧穿(一个CISCO(TM)协议)，第二层隧穿协议(L2TP)， 和协商或配置IPSEC隧道模式。\n当一个移动节点要从一个BS路由器越区切换时，该BS路由器与该移动 节点被越区切换到的新BS路由器进行交互，以进行以下步骤：\n(a)准备一个到新BS路由器的单向隧道，使得可以在旧BS路由器和移 动节点之间的无线链路丢失后把分组转发到移动节点。可以通过映射到一个预 先存在的BS路由器间的隧道或一个主机专用隧道来准备隧道，并通过移动TP 机制动态地协商。\n(b)在无线电链路层对移动节点进行越区切换。\n(c)从新BS路由器注入一个用于移动节点的IP地址(或多个地址，在 移动路由器的情况下)的路由选择更新。\n(d)通过一个到新BS路由器的隧道链路转发指向移动节点的IP地址和 到达旧BS路由器的数据分组。\n(e)更新到旧BS路由器的无效路由选择。\n(f)如果是主机专用的，则解除该隧道，或者在路由选择的会聚之后，去 除一个预先存在的隧道中的主机专用状态。\n在越区切换前，通过在经过旧BS路由器的基础结构中的一个或多个路由 把所有分组直接路由选择到移动节点。在路由选择的会聚之后，通过经过新BS 路由器的基础结构中的一个或多个路由把所有分组直接路由选择到移动节点。\n当(或者作为隧道建立的一部分从旧BS路由器，或者通过一个移动站辅 助的越区切换从移动节点)把越区切换通知给新BS路由器时，新BS路由器 产生一个定向路由选择更新消息，该消息被单点传送到使用现有DAG的旧BS 路由器用于移动节点的IP地址(其仍保持指向旧BS路由器)。该更新沿着到 旧BS路由器的反向最低邻居路径(一个近似最短路径)选择性地修改移动站 的DAG。在该更新的结尾，在移动节点在无线电链路层越区切换后，旧BS路 由器将具有DAG中的一个新下游链路用于移动节点的IP地址。一个跨越路由 器将在更新过程期间接收单点传送的定向更新，此时一个现有数据流被重新定 向到移动节点的新BS路由器。\n该更新程序不依赖于拓扑结构，并且在使用时可以不考虑新和旧BS路由 器之间的拓扑距离(这可以根据BS路由器的相对位置而实质性变化)。\n在到旧BS路由器的无线链路丢失时没有建立到新BS路由器的路由选择， 和或者在旧BS路由器中没有进行有效数量的高速缓存的情况下，该短期隧道 避免了分组丢失。\n但是，短期隧道的使用不必总是必须的，这取决于以下两个事件的相对排 序：\n(i)在旧BS路由器的BS路由器到移动节点无线链路的丢失\n(ii)定向路由选择更新到达旧BS路由器。\n如果路由选择更新在旧无线链路丢失前到达，就无需隧道，因为由于重新 路由选择将不会有进一步的数据分组到达旧BS路由器(提供具有相同排队优 先级和处理的控制和数据分组；如果不是，那么已经排队的数据分组仍将在路 由选择更新之后到达)，并且所有过去的数据分组将通过旧无线链路被转发到 移动站。如果不需要隧道，通过在旧BS路由器标记一个虚拟下游链路直到路 由选择会聚，可以防止由于在丢失旧无线链路时所有下游链路的丢失而导致的 在旧BS路由器的一个TORA更新的过早触发。因此，仅仅通过信令就可以实 现在旧BS路由器的路由选择抑制。\n仅通过信令实现的路由选择抑制也可以在旧BS路由器用作一个高速缓存 (例如一个透明高速缓存)的情况下使用，允许旧BS路由器存储相对大量的 数据直到路由选择会聚，并且一旦路由选择会聚就重新发送该数据。\n如上所述，当一个移动节点结束它的接入话路时，该移动节点的IP地址的 路由选择可以被返回到始发该路由选择的BS路由器，即IP地址的本地BS路 由器。提供一种机制来有效地把DAG的目的地恢复到本地BS路由器，这仅需 要AS中有限数量的节点的加入。\n当一个移动节点结束它的接入话路时，当前BS路由器联系该IP地址的本 地BS路由器，并启动DAG的目的地到本地BS路由器的传送。同样，也可以 把一个隧道链路用作一个抑制机制来抑制在当前BS路由器的路由选择更新的 启动，或更简单地，如果不转发任何数据，可以使用一个虚拟链路(一个在当 前BS路由器标记的无作用的下游链路)。当前BS路由器建立一个指向本地BS 路由器的隧道链路或虚拟下游链路。作为响应，本地BS路由器产生一个定向 “恢复”更新，该更新被发送到使用现有DAG的当前BS路由器用于移动节点 的IP地址(其仍保持为指向当前BS路由器)。该更新删除了由移动节点的先 前移动性产生的所有主机专用路由选择协议数据表记录和下一跳点转发表记 录，以把预先计算的聚集DAG恢复为用于移动节点的IP地址的有效路由选择 方案。该更新行进经过由移动节点的过去移动性造成的路由选择更新先前所产 生的路径。因此，删除了移动性专用更新产生的负高度值的集合，并且具有“全 零”参考水平的聚集DAG(假设网络中没有造成新高度产生和反转的故障)被 重新激活。隧道链路或虚拟链路可以被保持直到在当前BS路由器接收到恢复 更新，此时把隧道解除或者把虚拟链路去除。\n周期性地，或者在检测到一个触发事件时，移动节点或一个用作移动节点 的BS路由器可以利用“全零”参考水平、使用TORA更新机制来为一个IP地 址重新初始化DAG，从而消除DAG的任何有关移动性的路由选择表记录。以 此方式传播的“全零”参考水平优先于所有其它高度值(正和负)，并可以在 整个AS中传播(一个全AS的DAG重新优化)。这提供了一个用于软状态路 由维护的机制，其越控于有关移动性的更新机制。\n下面参考图2到11对在无线电链路层的BS间越区切换和AS的固定基础 结构内的路由选择更新的一个详细示例进行说明。另一个示例参考图12到16 进行说明。最后，参考图17到25对在移动主机接入话路结束后把路由选择恢 复到本地BS的一个详细示例进行说明。在图2到25所示的每个TORA高度 五元组中，为简单起见，使用符号i表示节点ID。但是，应该理解，这个值对 于每个节点是不同的，以便唯一地标识AS内的节点。还应该注意，为简单起 见，只显示了AS的一部分。\n在所有下面的示例中，AS包括多个固定核心路由器(CR1，CR2...)，多 个固定中间路由器(IR1，IR2，...)，和多个固定边沿路由器(ER1，ER2，...)， 根据它们对固定基础结构的拓扑结构“边沿”的相对接近性来分类。核心路由 器适于处理比中间路由器更大量的业务量，中间路由器适于处理比边沿路由器 更大量的业务量。例如，核心路由器可以处理全国业务量，中间路由器可以处 理区域业务量，边沿路由器可以处理子区域业务量。\n分组交换路由器同处一地并在功能上与无线基站组合，该组合实体此处被 称为一个接入节点(BS1，BS2，...)，尽管可以理解，术语“接入节点”不是 为了限制为一个包括无线BS功能的路由选择节点。例如，可以在一个在拓扑 结构上远离一个BS的节点提供一个“接入节点”。\n在下面所述的所有示例的情况下，在接口处的逐跳点路由选择方向性由沿 着网络的节点之间和接入节点与移动节点之间的链路(这些链路包括无线链 路)标记的箭头表示。分布式路由选择方案的形式是一个指向单个接收移动主 机MH2的TORA DAG。在移动主机MH2开始一个接入话路并被动态分配一 个IP地址之前，AS内存在用于该IP地址的一个预先计算和聚集DAG，其是 作为一个全AS的更新从分配该IP地址的接入节点(节点BS2)注入的。在图 2到25中，涉及路由选择更新或分组转发的节点被标记了它们的TORA高度 五元组(τi，oidi，ri，δi，i)。如前所述，该TORA高度还被存储在每个相邻节点的路 由选择协议数据表中，已经从应用该高度的节点通告过来。\n当移动节点MH2向本地接入节点BS2登记时，本地接入节点按所分配的 IP地址在无线电链路层高速缓存移动主机的身份，因此在节点BS2中保持的一 个路由选择表中形成一个移动站专用记录。\n图2表示在移动节点MH2和另一个主机(在此情况下是一个移动主机 MH1)之间发生的示例通信话路(例如，一个TCP/IP连接)。在下面的示例中， 不发生对应移动主机MH1的移动性，尽管使用要关于节点MH2的移动性描述 的相同功能时这种移动性是可能的。也可以利用一个对应的固定主机进行类似 的通信话路。应注意，在AS中存在一个指向节点MH1的单独DAG，因而从 节点MH2始发的数据分组被路由选择到节点MH1。由于该指向节点MH1的 DAG不改变，并且存在从节点MH2所联属的每个接入节点到节点MH1的路 由选择，因此将不再提供到节点MH1的路由选择的进一步说明。\n如图2所示，从节点MH1始发并指向节点MH2的数据分组最初通过其聚 集DAG(例如，通过固定节点BS1，ER1，IR1和ER2)被路由选择到本地接 入节点BS2。\n现在参见图3，可以由节点MH2自己或节点BS2进行无线电链路层BS间 越区切换判定。在一个移动节点启动的越区切换的情况下，可以根据从节点BS2 和BS3接收的信号之间的无线链路质量的比较来进行该判定。在移动节点MH2 移动时，从接入节点BS3接收的信号可能改善，而从接入节点BS2接收的信 号变差，并且在一个阈值判定事件，移动主机通过启动节点BS2和BS3之间 的越区切换来响应。如果在节点BS2进行越区切换判定，可以根据其他因素(例 如业务量负载)来进行判定。在此情况下，接入节点BS2把越区切换指令发送 到节点MH2。\n不管BS间越区切换是由移动节点MH2还是本地接入节点BS2启动的， 移动节点MH2都选择一个新接入节点BS3并把一个隧道启动(TIN)分组发 送到本地接入节点BS2。该TIN分组包括新接入节点BS3的IP地址，该IP地 址是由移动节点从接入节点BS3所广播的一个信标信道读取的。移动节点MH2 还通过把其高度的τ时间值减小到一个负值，-1(表示远离本地接入节点BS2 的第一个有关移动性的路由选择更新)，来计算一个新高度，并将其包括在TIN 分组中。\n现在参见图4，当本地接入节点BS2接收到来自移动节点MH2的TIN分 组时，本地接入节点BS2建立一个到新接入节点BS3的短期IP-in-IP隧道链路。 本地接入节点BS2把到BS3的隧道接口输入到它的路由选择表中，新接入节 点BS3的TORA高度被设置为等于(-1，0，0，1，i)以确保隧道接口被标记为下游 链路以用于越区切换程序的剩余部分期间的数据分组转发。\n当已经从本地接入节点BS2到新接入节点BS3建立了短期隧道链路时， 本地接入节点BS2通过隧道接口把从移动节点MH2接收的TIN分组转发到新 接入节点BS3。\n在本示例中，所使用的无线链路系统的性质使得，移动节点MH2能够(如 同一个允许软越区切换的CDMA蜂窝无线电系统中一样)在越区切换期间通 过到每个接入节点BS2和BS3的两个无线链路进行通信。因此，接下来，移 动节点MH2建立与新接入节点BS3的一个第二无线链路，并在节点BS3中建 立一个路由选择表记录以表示一个到移动节点MH2的下游链路。\n新接入节点BS3产生一个单点传送定向更新(UUPD)分组并把该分组发 送到它在固定基础结构中的相邻节点，节点ER3。UUPD分组要沿着新接入节 点BS3和本地接入节点BS2之间的单点传送路径行进，更新沿着更新路径的 所有节点以及与沿着路径的节点紧邻的所有节点的路由选择协议数据表和至少 一些下一跳点转发表中的记录(沿着路径的节点把它们的新高度通告给每个紧 邻的节点，该通告的传播被限制为一个跳点)。\n现在参见图6，在移动主机MH2建立了与新接入节点BS3的新无线链路 后，到本地接入节点BS2的旧无线链路被取消。指向移动节点MH2的数据分 组在到达本地接入节点BS2后通过短期隧道被转发到新接入节点BS3，并通过 新无线链路向前转发到移动节点MH2。\n尽管旧无线链路现在丢失了，在本地接入节点BS2还没有触发路由选择更 新(而根据TORA协议，会发生触发)，这是因为沿着已经在本地接入节点BS2 和新接入节点BS3之间建立的隧道存在一个剩余的下游链路。因此，到本地接 入节点BS2的路由选择仍保留原位直到从新接入节点BS3启动的路由选择更 新到达本地接入节点BS2。如图6所示，从接收UUPD分组的第一节点ER3 把UUPD分组转发到节点IR2，第一节点ER3还路由一个与移动性更新相关联 的负τ时间值(-1)来更新它的高度。节点IR2进而利用与有关移动性的更新 相关的负τ时间值来更新它的高度。\n沿着该路由选择更新单点传送路由的每个节点还针对路由选择更新UUPD 分组的每一跳点把其TORA高度五元组中的δ值递增1，使得δ值代表通过新 接入节点BS3到移动节点的跳点数目，以代替先前的路由选择表记录的δ值(表 示通过本地接入节点BS2到移动节点的跳点数目)。因此，沿着单点传送定向 更新路由的每个链路依次被指向新接入节点BS3。\n现在参见图7，接着把UUPD分组转发到沿着单点传送更新路由的下一个 节点，节点ER2。节点ER2是一个路由器，它标记出从发送节点MH1到本地 接入节点BS2的路由选择路径与从节点MH1发送到新接入节点BS3的分组所 要经过的路由选择路径(当前建立的路由选择路径)之间的交叉点。如图8所 示，一旦在接收到UUPD分组时更新了节点ER2中的路由选择协议数据表记 录，交叉节点ER2就具有两个下游链路，一个下游链路指向本地接入节点ER2， 一个下游链路指向新接入节点BS3。但是，因为指向新接入节点BS3的下游链 路包括一个负τ时间值，该时间值表示一个(最近的)有关移动性的更新，因 此最好选择指向新接入节点BS3的下游链路作为下一跳点转发链路。沿着到新 接入节点BS3的路由选择路径，把到达节点ER2的、指向移动主机MH2的数 据分组转发到节点IR2。在交叉路由器ER2处路由选择路径的转向之后，不再 有数据分组被转发到BS2，并且不再通过节点BS2和节点BS3之间的隧道接口 转发数据分组。但是，隧道接口此时仍在本地接入节点BS2保留原位，以便确 保不(由于所有它的下游链路的丢失)从本地接入节点BS2产生路由选择更新， 直到UUPD分组到达本地接入节点BS2。在UUPD分组到达本地接入节点BS2 时，删除BS2的路由选择表中的隧道状态记录，从而解除MH2的隧道接口。\n现在参见图9，注意到，由于本地接入节点BS2形成了单点传送更新路径 的结尾，在接收到UUPD分组时不重新定义本地接入节点BS2的高度(但是， 因为节点ER2的高度中定义了负τ时间值，节点BS2和ER2之间的链路方向 被反转，因此允许其他通过BS2接收服务的移动主机把分组发送到MH2)。\n最后，在接收到UUPD消息时，本地接入节点BS2可以把一个更新完成 确认(UUPD-Ack)发送到新接入节点BS3。UUPD-Ack分组沿着DAG中建立 的单点传送更新路由选择路径到达新接入节点BS3。在发送UUPD-Ack分组时， 旧接入节点BS3放弃为它最初分配给移动节点MH2的IP地址而对DAG进行 的试验性控制。在接收到UUPD-Ack分组时，新接入节点BS3开始为移动节 点的IP地址对DAG进行试验性控制。\n现在完成了在无线电链路层进行的与移动站的BS间越区切换相关的路由 选择更新，涉及到沿着单点传送更新路径的仅有限数量节点(在图9所示例子 中，仅5个节点)的高度的重新定义。此外，也限制了路由选择协议数据表记 录的更新，这种更新仅在接收UUPD消息的节点及其每个紧邻节点(接收新高 度的通告并把新高度存储在它们的路由选择表中)中是需要的。在图9所示的 例子中，还在节点IR1，CR1，CR2，和CR3中进行路由选择协议数据表更新。\n图10和11显示在一个随后的有关移动性的更新之前和之后AS内的DAG 的状态。在此情况下，把移动节点MH2从接入节点BS3越区切换到另一个接 入节点BS4，移动节点之前是从接入节点BS2越区切换到接入节点BS3的。这 里所采用的程序与在关于由移动节点从接入节点BS2到接入节点BS3的第一 次越区切换造成的有关移动性的更新的描述中的程序基本相同，其差别在于， 由从新接入节点BS4发送的单点传送更新所产生的新高度包括负τ时间值中的 再一个增量(τ时间值被增加到-2)，以便把由移动性的第二次发生导致的有关 移动性的更新高度，移动性的第一次发生的有关移动性的更新高度(具有τ时 间值-1)，和在预先计算的DAG中指定的高度的有关移动性的更新高度(具有 τ时间值0)相区别。如图1所示，新更新中涉及的节点最初具有包括τ时间值 0的高度，表示高度与预先计算的DAG中定义的相同。\n下面参考图12到16说明有关移动性的路由选择更新的另一个示例，其中 移动节点(与GSM蜂窝无线电系统中一样)能够在任何特定时间仅通过单个 无线链路进行通信。在此情况下，在前面的例子中参考图2到4说明的步骤相 同。如图12所示，响应沿着隧道接口接收到的TIN分组，产生从新接入节点 BS3发送的UUPD分组。\n现在参见图13，移动节点MH2首先丢失它与本地接入节点BS2的无线链 路的该时间段期间，并且在经过一个短时间段后(以允许在无线电链路层与新 接入节点BS3重新同步，ETC)，可以建立与新接入节点BS3的新无线链路。 在移动节点MH2没有无线链路，到达本地接入节点BS2的分组被从本地接入 节点BS2的隧道接口转发，并在新接入节点BS3排队，直到建立新无线链路。 接着，建立新无线链路，或者是UUPD分组到达本地接入节点BS2。如果首先 建立了新无线链路，那么新接入节点BS3立即为移动节点的IP地址采取对DAG 的试验性控制。否则，新接入节点BS3将一直等待，直到它接收到来自本地接 入节点BS2的UUPD-Ack消息。在前面的例子中描述的其余步骤(隧道解除， 随后的移动性，等等)也适用于本示例。\n图17到25表示一个程序，当一个移动节点结束一个接入话路时，进行路 由选择更新以把具有移动节点的IP地址的DAG恢复到最初把IP地址分配给 移动节点之前DAG的状态。该路由选择更新程序涉及把路由选择更新仅发送 到AS中有限数量的节点(沿着先前单点传送有关移动性的更新的路径)，并且 仅在有限数量的节点(恢复的定向路由选择更新消息所经过的节点以及每个紧 邻节点)的路由选择协议数据表中需要更新。\n参见图17，当移动节点MH2结束接入话路时，当前接入节点BS4把一个 恢复请求(RR)发送到用于该IP地址的本地接入节点BS2。这可以通过在当 前接入节点获知用于该IP地址的“本地”接入节点的身份来实现。通过在使用 OPT分组更新机制产生聚集DAG时发送该拥有BS的身份，并把该身份作为 路由选择协议数据(除了接入节点中保持的其他路由选择协议数据以外)存储， 可以提供这种知识。另选地，通过移动节点在最初分配其IP地址时存储本地BS 的身份，并把该身份发送到每个接入节点(移动节点在其接入话路期间从接入 节点接收服务)以在其中临时存储，也可以提供这种知识。因此，当移动节点 MH2结束该接入话路时，当前接入节点BS4沿着到本地接入节点BS2的IP-in- IP隧道链路发送RR分组，该RR分组最初用移动节点的IP地址定址并用本地 接入节点BS2的IP地址封装。\n作为需要用于一个IP地址的本地BS的身份知识的替代，可以利用移动节 点的IP地址作为目的地地址来发送RR分组，但是，在其首部中有一个标识符， 用于向每个转发节点指示要沿着聚集DAG路由选择路径对该分组进行路由选 择，该聚集DAG路由选择路径在整个接入话路期间保持指向本地BS。\n响应RR分组的接收，本地接入节点BS2在它的路由选择表中标记一个到 移动主机MH2的下游链路。该下游链路是一个虚拟链路，这是因为该移动主 机当前并没有与任何接入节点进行无线通信并且实际上位于一个不同的接入节 点(接入节点BS4)的服务区中。任何在移动节点MH2结束它的接入话路之 后到达BS4的分组可以沿着到本地接入节点BS2的隧道被转发，并可以被存 储以在将来移动节点MH2开始一个新接入话路时被转发到移动节点MH2。\n如图18所示，在接收到RR分组时，本地接入节点BS2还把(目前虚拟 的)移动节点MH2的高度重置为“全零”参考水平，并通过AS的固定基础结 构把一个单点传送定向恢复更新(UDRU)分组发送到当前接入节点BS4。沿 着一个单点传送路由转发UDRU分组，该单点传送路由仅包括其高度由于有关 移动性的更新而在以前被重新定义的节点。在图18的示例中，这些节点是节 点ER2，IR2，ER3，IR3，CR4，IR4，ER4和BS4。\n当在沿着单点传送路径的每个节点接收到UDRU分组时，每个节点的 TORA高度被重置为“全零”参考水平，并且高度的δ值被重新定义以便代表 经过本地接入节点到达(现在虚拟的)移动节点的跳点数量，从而代替表示经 过当前接入节点到达移动节点的跳点数量的先前记录值。该过程在图18到22 的每个图中表示。\n除了沿着单点传送更新路由更新高度，还把更新的高度通告给每个紧邻节 点。任何在其自己的高度中具有负τ时间值的节点在接收到一个指示把负τ时 间值重置为0的通告时(如图20所示接入节点BS3的情况)，也把它自己的高 度重置为“全零”参考水平，定义它的δ值以指示经过本地接入节点到达(现 在虚拟的)移动站的跳点数量，并产生一个它自己的新高度的通告，并将其发 送到它所有的邻居。任何接收到一个通告的新高度并且不重置它们自己的高度 的邻居不进一步传播该通告。\n如图23所示，一旦在当前接入节点BS4接收到UDRU分组，当前接入节 点删除在它的路由选择表中与移动节点MH2相关的状态，并沿着刚刚由单点 传送更新产生的路由选择路径把一个UDRU-Ack消息发送到本地接入节点 BS2，从而放弃为移动节点MH2先前使用的IP地址而对DAG进行的试验性控 制。\n如图24所示，UDRU-Ack分组最终传播到本地接入节点BS2。在接收时， 本地接入节点BS2删除所有与移动节点MH2相关的状态，并为IP地址采取DAG 的控制。然后，如图25所示，可以再次把该IP地址动态地分配给一个不同的 移动节点MH3，该移动节点MH3在接入节点BS2的服务区中开始一个接入话 路。\n总之，对本发明提供的路由选择协议可以单独或以任何组合形式进行以下 改进：\n1.存储作为移动性的结果产生的不同路由选择协议数据(在TORA协议 的情况下，“负”高度参考水平)，从而把分组转发到最近指定的下游邻居。\n2.结合单点传送定向移动性更新，以便通过仅改变存储在AS的一个有限 节点集合中的路由选择协议数据来调节越区切换时的路由选择。\n3.结合单点传送定向恢复更新，以消除基于越区切换的移动性的影响(在 TORA的情况下，“负”高度参考水平)。\n应该理解，上述实施例不用于限制，本领域技术人员可以构想出改进和变 型。\n上述实施例描述了一个基于TORA路由选择协议的改进的路由选择协议。 但是，可以使用本发明的方面来改进其他已知的路由选择协议，例如OSPF，RIP 等等。\n此外，尽管在上述实施例中自主系统的基础结构是固定的，应该理解，基 础结构中的一个或多个路由器可以是移动路由器，例如在卫星通信领域和其他 系统(其中的基础结构中的一个或多个路由器表现出长期移动性)中使用的移 动路由器。此外，还可以通过一个可移动非无线通信链路(例如插入式电缆连 接)把移动节点连接到一个接入节点。