怎样才能快速搜索路由表？有哪些著名的搜索算法

有三个路由器，a，b和c。路由器a的两个网络接口f0和s0
分别连接在
10.1.0.0和10.2.0.0网段上；路由器b的两个网络接口s0和s1
分别连接在
10.2.0.0和10.3.0.0网段上；路由器c的两个网络接口s0和e0
分别连接在
10.3.0.0和10.4.0.0网段上；
如上图中各路由表的前两行所示，通过路由表的网络接口到与之直接相连的网
络的网络连接，其向量距离设置为0。这即是最初的路由表。
当路由器b和a以及b和c之间相互交换路由信息后，它们会更新各自的路由表。
例如，路由器b通过网络端口s1收到路由器c的路由信息（10.3.0.0,s0,0）和(10.4.0.0,e0,0)后，在自己的路由表中增加一条(10.4.0.0,s1,1)路由信息。该信息表示：通过路由器b的网络接
口s1可以访问到10.4.0.0网段，其向量距离为1,该向量距离是在路由器c的基础上加1获得的。
同样道理，路由器b还会产生一条(10.1.0.0,s0,1)路由，这条路由是通过网络端口s0从路由器a
获得的。如此反复，直到最终收敛，形成图中所示的路由表。
概括地说，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路由
器。路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离。当一个路
由器从它的相邻处收到更新信息时，它会将更新信息与本身的路由表相比较。如果该路由器比较出一条
新路由或是找到一条比当前路由更好的路由时，它会对路由表进行更新：将从该路由器到邻居之间的
向量距离与更新信息中的向量距离相加作为新路由的向量距离。

路由的概念：路由是一种指向标，因为网络是一跳一跳往前推进的，因此在每一跳都要有一系列的指向标。实际上不仅仅是分组交换网需要路由，电路交换网在创建虚电路的时候也需要路由，更实际的例子，我们日常生活中，路由无处不在。简单的说，路由由三元素组成：目标地址，掩码，下一跳。注意，路由项中其实没有输出端口-它是链路层概念，Linux操作系统将路由表和转发表混为一谈，而实际上它们应该是分开的(分开的好处之一使得MPLS更容易实现)。
路由项通过两种途径加入内核，一种是通过用户态路由协议进程或者用户静态配置配置加入，另一种是主机自动发现的路由。所谓自动发现的路由实际上是“发现了一个路由项和一个转发表”，其含义在主机某一个网卡启动的时候生效，比如eth0启动，那么系统生成下列路由表项/转发项：往eth0同一IP网段的包通过eth0发出。
路由表：路由表包含了一系列的表项，包括上述的三元素。
路由框架的层次：路由大致分为两个要素，也可以看成两个层次。第一个层次是路由表项的生成；第二个层次是主机对路由表项的查找。
路由表项生成算法：生成路由表项的方式有两种，第一种是管理员手工配置，第二种为通过路由协议动态生成。
路由查找算法：本文着重于主机层面上对路由表项的查询算法。毕竟这是一个纯技术活儿...相反的，路由协议的实现和配置更讲究人为的策略，如果你人为配置RIP或者OSPF只需要配几条命令就OK了，那么配一个BGP试试，它讲究大量的策略，不是纯技术能解决的。如果有时间，我会单独写一篇文章谈路由协议的，但是今天，只谈路由器/主机对路由表项的查找过程。
这个过程很重要，如果路由器的查找算法效率提高了，那么很显然，端到端的延迟就降低了，这是一定的。