LC-Trie树和256-way-mtrie树..docVIP

LC-Trie树/256-way-mtrie树 分类： 系统设计 2011-07-10 16:10 810人阅读 评论(2) 收藏 举报 说明：本文没有源码分析的内容，然而我认为能理解本质比能看懂源码更有用，因为理解了本质之后，你也许就不用再看源码了，你甚至都可以写源码了。这就是Linux内核和Cisco的网站中包含大量文档的原因。引：路由是互联网的一个核心概念，广义的讲，它使分组交换网的每个节点彼此独立，通过路由耦合在一起，甚至在电路交换网中，虚电路的建立也依赖路由，路由就是网络中数据通路的指向标。狭义的讲，路由专指IP路由，它支撑着整个IP网络。???? 由于IP是数据报网络，它是不建立连接的，因此IP分组是一跳一跳被转发，通路是通过路由信息一跳一跳的被打通的，因此路由直接关系到整个基于IP的网络的连通性。由于IP协议没有方向，甚至它都没有会话的概念，因此路由必然要是双向的，否则数据就有去无回了(有人提倡用NAT来解决反向路由问题，实际上NAT在公共核心网络上口碑十分不咋地，它甚至破坏了IP协议的原则，记住，NAT一般只用于端点)。互联网如此之大，每个路由器上的路由信息会非常之多，路由器是怎么在海量的路由信息中用最快的速度-显然很重要-检索出自己需要的呢？另外如此海量的路由信息又是怎么生成的呢？本文着重回答第一个问题，关于第二个问题请参考《Internet路由结构(第二版)》(Cisco Press,想看就赶快买，不买就买不到了，Cisco有几本书真的很火爆，总是不好买) 1.基本概念 路由的概念：路由是一种指向标，因为网络是一跳一跳往前推进的，因此在每一跳都要有一系列的指向标。实际上不仅仅是分组交换网需要路由，电路交换网在创建虚电路的时候也需要路由，更实际的例子，我们日常生活中，路由无处不在。简单的说，路由由三元素组成：目标地址，掩码，下一跳。注意，路由项中其实没有输出端口-它是链路层概念，Linux操作系统将路由表和转发表混为一谈，而实际上它们应该是分开的(分开的好处之一使得MPLS更容易实现)。???? 路由项通过两种途径加入内核，一种是通过用户态路由协议进程或者用户静态配置配置加入，另一种是主机自动发现的路由。所谓自动发现的路由实际上是“发现了一个路由项和一个转发表”，其含义在主机某一个网卡启动的时候生效，比如eth0启动，那么系统生成下列路由表项/转发项：往eth0同一IP网段的包通过eth0发出。路由表：路由表包含了一系列的表项，包括上述的三元素。路由框架的层次：路由大致分为两个要素，也可以看成两个层次。第一个层次是路由表项的生成；第二个层次是主机对路由表项的查找。路由表项生成算法：生成路由表项的方式有两种，第一种是管理员手工配置，第二种为通过路由协议动态生成。路由查找算法：本文着重于主机层面上对路由表项的查询算法。毕竟这是一个纯技术活儿...相反的，路由协议的实现和配置更讲究人为的策略，如果你人为配置RIP或者OSPF只需要配几条命令就OK了，那么配一个BGP试试，它讲究大量的策略，不是纯技术能解决的。如果有时间，我会单独写一篇文章谈路由协议的，但是今天，只谈路由器/主机对路由表项的查找过程。???? 这个过程很重要，如果路由器的查找算法效率提高了，那么很显然，端到端的延迟就降低了，这是一定的。 2.Linux的哈希查找算法 这是Linux操作系统的经典的路由查找算法，直到现在还是默认的路由查找算法。然而它很简单。由于它的简单性，内核(kernel)开发组一直很推崇它，虽然它有这样那样的局限性，但由于Linux内核的哲学就是“够用即可”，因为Linux几乎从来不被用于专业的核心网络路由系统，因此哈希查找法一直都是默认的选择。 2.1.查找过程 查找结构如下图所示： 查找顺序如下图所示： 为了实现最长前缀匹配，从最长的掩码开始匹配，每一个掩码都有一个哈希表，目的IP地址哈希到这些哈希表的特定的桶中，然后遍历其冲突链表得到最终结果。 ???? 注意，哈希查找算法是基于掩码的遍历来实现严格的最长前缀匹配的，也就是说如果一条最终将要通过默认网关发出的数据报，它起码要匹配32次才能得到结果。这种方式十分类似于传统的Netfilter的filter表的过滤方式-一个一个尝试匹配，而不像HiPac的过滤方式，是基于查找的。接下来我们会看到，高性能的路由器在查找路由的时候使用的都是基于查找型数据结构的方式，最常用的就是查找树了。 2.2.局限性 我们知道，哈希算法的可扩展性一直都是一个问题，一个特定的哈希函数只适合一定数量的匹配项，几乎很难找到一个通用的哈希函数，能够适应从几个匹配项到几千万个匹配项的情形，一般而言，随着匹配项的增加，哈希碰撞也会随着增加，并且其时间复杂性不可控，这是一个很大