[科普中国]-下一节点路由选择表

简介

下一节点路由选择表即在路由表中选择下一个路由节点。下一节点路由选择表与计算机网络中很多因素都有关，例如节点可达性、节点所属路由域、传输代价、路由算法等。

IP路由IP协议的路由功能是由路由器实现的的，当路由器接收到一个报文，它抽出报文中的目的地址，然后，从目的地址中找出目的地的网络号查找路由选择表寻找与目的地址中网络相匹配的项。每个路由选择表项包含了用来转发报文的接口信息，也就是到目的地路径中的下一个路由器的地址。路由器的第二个工作，是维持路由选择表。这些表是由网络管理者创建的，或通过与其它路由器交换路由信息创建。当一个路由器初始引导时，它只知道与它直接相连的接口，如果网络中的路由器正在运行路由选择协议，当路由器知道与它相邻接的路由器相连的网络时，新的路由表表项将被创建每个路由选择表表项都被标识一个字符，该字符表示路由信息的源端。

路由查找整个路由过程中，查表算法的优劣直接影响了当前和未来因特网网络的整体性能。当前，因特网的规模、链路速度、带宽、流量等都呈指数级增长 ，这对路由器中IP路由查找算法对大容量路由表处理的适应性以及报文转发查表的能力提出了更高要求。路由器是构成因特网的中间节点，其转发性能决定了因特网的整体性能。因此，IP路由查找操作已经成为了当前路由器转发性能的瓶颈之一 。其实路由查找问题本身很简单，但由于其对性能要求很高，因此有很大的难度。通常评价IP路由查表算法的标准主要有高速查找、内存需求小、更新时间短、实现的灵活性强、能够处理真实的大容量路由表以及预处理时间短等。IP 路由查找方案可以分为以下几类：（1）基于精确匹配的改进方案：这种方案一般效率不高，为了找到最佳结果，一般需要log2N步（N 为路由表项的数目）；（2）层次方案：这是普遍采用的一种查找方案，在 BSD内核中得到实现 。它最坏情况下的复杂度为O（W），而且需要 32或 128 次（分别对应IPv4 和IPv6）存储访问，效率也不高；（3）硬件实现:这种方法需要昂贵的内容寻址存储器，而且扩展性不好；（4）基于协议的解决方案：现在的IP交换和标记交换技术就属于这种方式；这种方案也无法完全避免搜索，特别是边界路由器仍然需要执行繁重的路由决策1。

软件路由查找算法软件路由查找算法主要有基于二分支的算法，基于多分支的算法，还有前缀维度上的二分搜索算法 、最差性能受限的近似最优路由查找算法 、多路前缀值范围搜索树算法等。基于二分法的算法有Redix Rrie、Patricia、Multiway 和Multicolumn等。这些算法的基本思想是根据前缀值的二进制位构建二叉树，在检索时用目标地址作为索引，在二叉树中遍历；当找到一个匹配的前缀时，将其作为到目前为止所发现的最长前缀，继续搜索更长的匹配前缀，直到再没有分支可以搜索时，搜索结束，此时所记录的最长前缀就是所要寻找的最长前缀匹配。在基于多分支的算法二叉树算法中，每个搜索步骤能够将第一步开始的整个232搜索空间减少一半，而多叉树可以令每个搜索步骤减少更多的搜索空间。此类算法的典型有 LC Trie树算法 、受控前缀扩展算法 。可变分支数目的多分支Trie树结构，其搜索过程与二叉树类似，只是由一位比较变成了多位比较以决定下一步搜索的子树。Srinivasan对分支数目和层次数目的选取做了详细的分析，并提出了多分支树的一般结构，所有基于Trie树的算法都可以看作是该一般结构的特例或变形。此外他还提出了前缀扩展技术，以耗费更多内存为代价来避免最长前缀匹配所带来的回溯问题。其它软件算法有前缀维度上的二分搜索算法 、最差性能受限的近似最优路由查找算法 、多路前缀值范围搜索树算法等。这些算法并不是对整个 前缀地址空间进行搜索，因此对于地址宽度的敏感性较低。前者的搜索时间复杂度是O(log2w)，而后两个算法的搜索时间复杂度与地址宽度无关。因此，这几个算法能够用于 IPv6的路由查找。

硬件路由查找算法硬件路由查找算法有24-8 DIR算法、基于TCAM（三值 TCAM）的算法。24-8 DIR算法实际是一种用硬件实现的多分支前缀扩展算法。该算法基于对于前缀长度分布的统计数据长度大于24的前缀非常少，因此该算法将所有前缀全部展开为24位前缀。所以，它 只 有 两级：第一级224个分支，若有第二级节点，则该第一级节点有28个二级子节点。在一般情况下只需一次访存即可找到目标路由，而对于长度大于24的前缀则最多只需要进行两次访存。因此，这是一种“以存储器速度进行路由查找”的算法，也是典型的用空间换时间的算法。

路由表在计算机网络中，路由表（routing table）或称路由择域信息库（RIB, Routing Information Base），是一个存储在路由器或者联网计算机中的电子表格（文件）或类数据库。路由表存储着指向特定网络地址的路径（在有些情况下，还记录有路径的路由度量值）。路由表中含有网络周边的拓扑信息。路由表建立的主要目标是为了实现路由协议和静态路由选择。在现代路由器构造中，路由表不直接参与数据包的传输，而是用于生成一个小型指向表，这个指向表仅仅包含由路由算法选择的数据包传输优先路径，这个表格通常为了优化硬件存储和查找而被压缩或提前编译。本文将忽略这个执行的详细情况而选择整个路径选择/传输信息子系统作为路由表来说明。

在路径选择的过程中，主机和路由器的决策是由一个叫路由表的路径数据库辅助决定的。路由表在路由器内部。根据路由协议，主机也可以拥有用于选择最佳路径的路由表。主机路由表是互联网协议中可选的，像已经过时了的IPX协议。各种路由表：网络路由：一个在网络中有特定网络ID的路由（路径）主机路由：一个有特定网络地址（网络ID和主机ID）的路由。主机路由允许智能化的路由选择。主机路由通常用于创建用于控制和优化特定网络通信的定制路由。默认路由：一个当别的路由在路由表中未被找到的时候使用的路由。如果一个路由器或终端系统（如装有Microsoft Windows和Linux的个人电脑），找不到到达目的地的路由时就会使用默认路由。

路由算法路由算法，又名选路算法，可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径（即具有最低费用的路径）2。算法设计者的特定目标影响了该路由协议的操作；具体来说存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；由于路由算法使用多种度量标准（metric），从而影响到最佳路径的计算。路由算法通常具有下列设计目标的一个或多个：优化、简单、低耗、健壮、稳定、快速聚合、灵活性。（1）最优化：指路由算法选择最佳路径的能力。根据metric的值和权值来计算。（2）简洁性：算法设计必须简洁。路由协议在网络中必须高效地提供其功能，尽量减少软件和应用的开销。这在当实现路由算法的软件必须运行在物理资源有限的计算机上时尤其重要。（3）坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行。由于路由器分布在网络联接点上，所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的。（4）快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。（5）灵活性：路由算法要求可以快速、准确地适应各种网络环境。例如，某个网段发生故障，路由算法要能很快发现故障，并为使用该网段的所有路由选择另一条最佳路径。