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

下一节点路由选择表软件路由查找算法

软件路由查找算法主要有基于二分支的算法，基于多分支的算法，还有前缀维度上的二分搜索算法 、最差性能受限的近似最优路由查找算法 、多路前缀值范围搜索树算法等。基于二分法的算法有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的个人电脑），找不到到达目的地的路由时就会使用默认路由。

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

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

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

路由选择表目的地址

路由器可以到达的网络地址。路由器可能会有多条路径到达相同的地址/或是到达相同主网IP地址下的且等长或变长的子网。

路由选择表指向目的地的指针

就是将告诉路由器把数据包从哪个端口转发出去。（可以是路由器直接连接的网络或下一台路由器）也叫“下一跳”。指针不是指向路由器的直连目的网络就是直连网络内的另一个路由器地址。更接近目标网络的下一跳的路由器叫做下一跳(next hop)路由器。

路由选择就是构建网络节点路由表的过程，无论哪种分组网络，路由选择都是由网络提供的基本功能，但咋X.25建议中对路由选择并未作出明确规定，对不同的分组网允许有不同的路由选择算法，如何确立路由选择算法的好坏呢？分组的路由选择的基本原则如下：算法简单，易于实现，以减少额外开销；算法对所有用户都是公平的；应选择性能最佳的传输路径，使得端到端时延尽量小，个网络节点工作量均衡，最大限度提高网络资源利用率；网络出现故障时，在网络拓扑改变的情况下，算法仍能正常工作，自动选择迂回路由。

不同的分组交换网有可能采取不同的路由选择。路由选择可分为动态法和静态法两类。

路由选择器静态法

(1)扩散式路由法，分组从原始节点发往与之相邻的节点，接受该分组的节点检查它是否收到过该分组，如果已经收到过，则将它抛弃；如果未收到，只要该分组的目的节点不是该节点，就将此分组对相邻节点进行广播，最终该分组必将到达目的节点。其中，最早到达目的节点的分组所经历的过程必定是一条最佳路径。采用扩散式路由法，路由选择与网络拓扑无关，即使网络严重故障。只要有一条通路存在，分组也能到达终点，因此分组的传输的可靠性很高。但缺点是分组的无效传输量很大，网络的额外开销也大，网络中业务量的增加会导致排队时延的加大。

(2)固定路由表法，在每个节点交换机中设置一个包含路由目的节点地址和对应输出逻辑信道号的路由表，他指明从该节点到网络中的任何终点应当选择的路径。呼叫请求分组根据分组的目的地址查找该路由表，这样可以获得各转接节点的输出逻辑信号，从而形成一条端到端的虚电路。为防止网络故障或通路阻塞，路由表中可以规定主用路由和备用路由。

路由选择器动态法

(1)自适应路由选择网，自适应路由选择法是指路由选择根据网络情况的变化而变化。路由是由若干段链路串接而成的，自适应路由选择法是用迭代法逐段选取虚链路，从而形成一条端到端的虚电路。但在这种算法中，要求各节点存有全网络拓扑数据，而且每条链路的变化信息必须广播给网络所有的节点。自适应路由选择算法对减少网络时延、平滑网络负载、防止网络阻塞是有利的，但是路由表的频繁更换可能引起网络的不稳定，产生分组循环或者使分组在一对节点之间来回穿梭，自适应路由选择算法是X.25分组网中应用最为普遍的一种选路方式。

(2)集中式路由交换，网管中心负责全网状态信息的采集、路由计算以及路由表的下载。在分组交换网中，交换机之间一般有多条路由可选择。如何获得一条较好的路由，除了要有一个通过网络的平均时延较短和平衡网内业务量能力较强的路由算法外，同时还要考虑网内资源的利用和网络结构的适应能力。 2100433B

路由选择表更新过程

会聚是路由选择表更新过程的一部分。当某个链路失效或更改时，会在网络上发送描述网络拓扑结构更改的更新信息。然后每个路由器运行一个路由算法，基于该信息重新计算路由并生成新的路由选择表。一旦网络中的所有路由器更新了它们的路由选择表，会聚就完成了。

路由选择表选择过程

会聚是一个与静态路由选择相对立的动态路由选择过程。静态路由是指由网络管理员手工配置宽带路由器的路由信息。当网络的拓扑结构或链路的状态发生变化时，网络管理员需要手工去修改路由表中相关的静态路由信息。静态路由适用于小型网络或网络间存在专用链路的情况。

路由选择表捕获

宽带路由器常有的动态路由选择协议是RIP1、RIP2。由路由器捕获得的网络状况来计算最短的路径以传递数据报。这项功能使宽带路由器具有了传统企业路由器所有的路由选择协议功能，但当企业有接入两条以上宽带线路且固定公网IP才会起应有的作用。