The thinking behind route lookup and ACL match

最近为我们的VPN添加访问控制功能，操作很简单，保存一个IP/MASK列表，到来的数据包的目标IP地址如果不在这个列表中，便丢弃。由于在逻辑上和路由查找很类似，在实现上我们移植了Linux内核的路由查找的整套算法，也是情理之中的事情。然而在根本上，访问控制和IP路由却是截然相反的两件事情。

IP路由：

完整体现IP层的原则，尽力而为地将数据包forwarding到next hop；
路由器的路由表长度和网络IP地址规划有很大关系，路由倾向于汇聚，即粒度越粗越好，更细粒度的区别由下一跳路由器负责；

ACL：

尽力将数据包drop在本地；
ACL长度完全由策略决定，访问控制倾向于区分不同的角色，即粒度越细越好，因此往往好的访问控制列表的每一条都是针对一个HOST甚至其上某个特定服务的；

理解了以上的区分，对于其实现而言，就不难理解了。对于ACL，也许条目数很多，但那很大程度上不是你的错，相反，它说明了管理员的负责，除非管理员是个菜鸟。但是对于路由表，条目很多的话，就要想是否可以重新规划一下网络。

       也许很多人纠结于net mask和wildcard mask的区别，在我看来，这只是一种写法上的区分，wildcard mask中的1可以不连续，难道net mask中的1必须连续吗？这里要插入一段历史，net mask和prefix等同起来是无类IP地址取代有类IP之后才成为常识的，随即路由查找算法也变成了最长前缀匹配算法，这个算法本身要求前缀表示的net mask中的1必须是连续的，否则面对1.1.1.1这个地址，1.2.0.4/255.255.0.255和1.1.0.0/255.255.0.0这两个到底哪个更优呢？？最初的IP地址的掩码是可以有不连续的1存在的，只是后来掩码在无类环境中等同于前缀，即prefix之后，才必须连续，事实上，这种连续1的net mask形式导致了“最长前缀匹配”算法的被采纳，反过来，前缀这个词本身也可以表明掩码的1是连续且在前面的。关于不连续的子网掩码的介绍详见
RFC 950，现摘一段：

      For example, the Internet address might be interpreted as:
         <network-number><subnet-number><host-number>
.....
      Since the bits that identify the subnet are specified by a
      bitmask, they need not be adjacent in the address.  However, we
      recommend that the subnet bits be contiguous and located as the
      most significant bits of the local address.

       作为通配符的wildcard mask则没有0，1必须连续这个限制，它比net mask或者说prefix更为宽松，没有指明网络段，主机这类概念，只是简单的标明有关位，无关位这些概念。如果不是用反过来的net mask作为wildcard mask，而是继续如同有类子网划分年代对net mask的定义，我相信很多的关于net mask和wildcard mask的区别的疑问就不复存在了。

       使用wildcard mask来匹配IP地址是极其方便的，比如匹配一个网段中所有的奇数IP地址或者偶数IP地址主机，显然它们是不能用无类时代的net mask的，因为net mask必须连续，且奇数IP地址和偶数IP地址没法汇聚，然而用有类时代的net mask或者现如今的wildcard mask就会很方便，比如：

1.1.1.0/24的奇数IP地址：1.1.1.1 0.0.0.254或者255.255.255.1

1.1.1.0/24的偶数IP地址：1.1.1.0 0.0.0.254或者255.255.255.1

我们知道Linux的iptables是支持wildcard mask的，因此你在，面对那些诸如“匹配奇数地址”之类需求的时候就不用配置超级多的规则。继续行文之前，有一个小tip，表达我对iptables的感觉，既然支持wildcard mask，在需要过滤类似奇数/偶数IP地址的时候，你就可以直接来用，但是Linux的iptables并不是采用Cisco之类的系统采用“反掩码”的形式表示wildcard mask的，而是正掩码：

iptables -A FORWARD -d 192.168.1.0/255.255.255.1 -j DROP

以上这条和下面这条代表相同的意思：

router(config)#access-list 10 deny 192.168.1.0 0.0.0.254

Linux的iptables还提供了另一种类似的wildcart mask机制，可以对数据包协议头的任意字段做mask运算而不仅仅是针对IP地址，事实证明玩好了比上述的针对IP地址的wildcard mask功能更强大。这就是使用iptables的u32 match：

   u32
       U32 tests whether quantities of up to 4 bytes extracted from a packet have specified values. The specification of what to
       extract is general enough to find data at given offsets from tcp headers or  payloads.

仔细一看，u32实际上就是一个mask机制的体现，只是它不仅仅可以mask IP地址，它可以mask协议头中的任意的东西。

       知道了wildcard mask的方便性后，我们再次回到IP路由，前述的IP路由基本原则只是基于基本的IP协议来说的，尽力而为，逐跳推送，然而考虑一下策略路由，所谓的策略路由关键是策略如何定义，显然它增加了一些IP路由本身并不具备的约束，和ACL类似，因此在策略路由中，也是适用wildcard mask的。

       最后值得注意的是，不管是net mask还是wildcard mask，在硬件实现上都是没有任何区别的，都是简单的位运算，我相信IOS也好，VRP也罢，最终肯定都是转成了一种运算。其区别更多的是表示方法上的区别，进入无类时代以后，不连续1的net mask已经不能使用了，如果你用这种类似0.0.255.13这样的mask的时候，请问系统怎么区分你是错误使用了net mask，还是正确使用了wildcard mask，系统将无法区分这二者，因此还是分开来比较好，也较简单，255和点分十进制的减法而已。所以不要纠结这两类mask的区别了吧。

       总结一下本文，IP路由尽可能的将数据包往前推，而ACL则尽可能将数据包往回拉然后drop掉，二者的理念是截然不同的，虽然算法可以很类似，但是IP路由查找算法有一个额外的假设，即它可以保证掩码的1是连续的，因此它可以用“最长前缀匹配”算法来进行精确匹配，而ACL虽然没有这个额外的假设，它完全基于用户配置的顺序以及优先级，在算法上，只能按此顺序遍历，效果上和IP路由的查找类似-IP路由查找是按照前缀长度从长到短这个顺序遍历的，算法层面都是使用按位AND操作后比较。看来，理念不同的背后，逻辑也能完全一致！

苛刻地发，宽容地收

Now let's map the ROUTING and ACL to HOST and ROUTER ！

网络在设计之初就有一个原则，那就是对待发送，极为苛刻，对待接收，极其宽容，我们可以把这个理念当成在那个资源匮乏年代不得以而为之的妥协，但是在如今资源丰盈的年代它还是体现着正确使用带宽的方式。网络，无疑是一种资源，但是却不能归为可再生或者不可再生这种分类的范畴，我们把它当成你使用的时候就稀缺，不使用的时候就丰盈的资源，不管技术多么成熟，都是这样，10年前上网卡，现在上网依然卡，10年后也一样，这绝对不可改变，因为网络资源丰富化的同时，会促使应用爆发式增长！因此，不管什么时候，都应该
苛刻地发，宽容地收！背后的思想就是，不要让不该存在于网络的数据存在于网络，让存在于网络的数据尽快离开网络！

       端到端系统采取了很多方式对将要发送的数据做检查，比如TCP的Nagle算法，比如流量控制，比如个人防火墙等，中间系统也依然这样。依照“The thinking behind  route lookup and ACL match”，IP路由的职责是尽快使网络上的数据离开网络，而ACL的职责则是尽量阻止不该存在于网络的数据发送到网络。对待网络这种如此特殊的资源类型，The thinking behind  route lookup and ACL match的宗旨就是苛刻地发，宽容地收！

注：最长前缀匹配背后的意义

当前，我们大可忽略掉有类编址的IP路由，集中于最长前缀匹配。我们知道IP是尽力转发的，落到实处就是IP路由器尽力将数据包发给下一跳，将转发责任推卸给下一跳，这个看似不负责任的动作看起来好像是越往后的路由器压力越大，实际上并非这样，不负责任行为是局部意义的，在全局意义上，路由器倾向于将数据包发往容量最小的网络，即最精确表达目的IP所处位置的下一跳。我们再次揣摩这个“最长前缀匹配”短语，其中“最长前缀”的另外一个意思就是“最短主机位”，或者说最小网络，因此IP路由器总是把数据包发往满足可达性要求的容纳主机最少的网络！如果IP地址规划的良好，那么这种转发行为带来的是流量的均衡和路径的最优。