iGFW

其实我最初没想优化这个路由表的，但是我的OpenVPN服务商会推送“ping-reset 60”到客户端，以至于chnroutes提供的路由表还没加载完，OpenVPN就被重置了。

另一方面，我实在不太想单独写两个up/down脚本来执行路由配置，因为OpenVPN的route选项就能解决路由的配置，速度更快，配置文件更小，路由项也会在VPN断开时自动删除。

所以就萌生了优化路由表的想法，在不影响使用的前提下将路由表的项目数量减至最小。

chnroutes工作原理

chnroutes产生的路由基于APNIC的最新IP地址分配表，将其中IPv4的中国部分提取出来。并将取出的部分标记为使用默认网关（net_gateway）。虽然OpenVPN一般会设置默认路由（0.0.0.0/0或0.0.0.0/1及128.0.0.0/1）使用vpn_gateway，但是根据路由表的匹配规则，这些地址段比默认路由具有更高的优先级，所以就会被优先选择，从而避免使用VPN访问国内资源。

但是这货产生了3536条规则啊，尼玛，就算中国的网段再碎也不能这么欺负人吧。。。所以我决定稍微研究一下这些地址段。

APNIC地址段的研究

APNIC是主管亚太地区的地址分配机构，其划分的地址块非常分散，每个国家的地址都有几百个独立的小块。但是也有些情况比较特殊，假如有几个中国地址段有相同的前缀（这只是个例子，实际的掩码大多在16位以上：）

101100/6 CN —> 本地
101101/6 CN —> 本地
10111/5 CN —> 本地

而同样前缀的另一个地址段是分配给其他国家的：

101111/6 JP

直觉上，使用3个路由项来表示这几个路有项有点太奢侈了，那何不把1011这整块地址都匹配给中国制定它使用本地路由，然后再指定剩下的用VPN路由？

1011/4 CN —> 本地
101111/6 JP —> VPN

这样在路由算法来看，第二个匹配规则的掩码更长（6>4）所以有更高的优先级。当地址既匹配本地规则又匹配VPN规则时就会选择VPN线路。这样就减少了一个路由项。

事实证明这个逻辑是有效果的，按照地址段的前缀排序APNIC的地址表，得到了这样的结果：

000000010000000100000000|CN|256
000000010000000100000001|AU|256
00000001000000010000001|CN|512
0000000100000001000001|CN|1024
000000010000000100001|CN|2048
00000001000000010001|CN|4096
0000000100000001001|CN|8192
000000010000000101|JP|16384
00000001000000011|TH|32768

其中第一部分为IP地址段的前缀，已经按照其掩码长度（a.b.c.d/x里的x）补充了足够多的0，之后的部分为国别码，最后的部分是这个地址段中的地址数量。

这让人十分欣喜，如果把以000000010000000100开头的地址（上面划线的部分）都分配给本地路由，单独把AU的地址分制定为使用 VPN，那么我们就把原来所需要的6个路由项减少到了两个。如果更极端一点儿，直接忽略掉AU的地址（毕竟只有256个，而且平时也不用AU的网站，）那 么就直接把条目数减少到了1个。

利用这样的策略就可以极大限度的减少路由条目的数量了。

实现优化算法（1）

根据上面的例子可以得到一个简单的递推公式。

设f(p)表示对p开始地址段实施本地路由所需要的最少路由项数量，g(p)表示以p开始的非中国地区地址段数量。

那么显然有如下的递推：

其中 p0 和 p1 表示在 p 后连接一个新的字符。

如此就可以计算一个相对优化的版本，显然前缀树就可以满足需求，计算时使用dfs即可。时间复杂度为O(n)。这时我们只需要2447个路由项即可实现本地路由，而非最初的3536个。

那么还可以继续优化么？当然，考虑到其他地区并非都是那么容易被墙，所以我们可以把它们划入本地路由区间，即减少了g(p)的数值。

如果我们在路由中仅把美国当作需要独立处理的国家，那么我们只需要9个路由项（如果仅考虑APNIC的话，实际情况还需要将ARNIC的地址块都划入进来；）当包括美英港的时候，我们需要577个路由项；当包括美英港日时需要1232个路由项。这样，我们就减少了65%的路由项。

那么还能更优化么？必须可以。

实现优化算法（2）

在实现上述算法的时候，g(p)并非最优。因为我们在计算g(p)时排斥了除去中国和选定国家外的地址段。实际上我们对于那些并不明确路由归属的国家应该让他们动态的归属到某一个网关，也就是说，我们希望找到识别以p开始的地址段中，包括某些国家，但是又不包括中国的最小路由项目数量。

重新定义这个问题，以方便实现算法。设存在一颗二叉树，节点值有红/蓝/空三种。要求，对任意一个值不为空的节点N，都有从根R出发到节点N的简单路径上，最后一个着色的节点的颜色与N的值相同。求最少的着色数。

设dp(N,c)表示，从根到节点N的最后一个着色节点的颜色是c时，其子树所需要的最小着色数。

其中L表示左子树，R表示右子树，c表示相反的颜色（red<->blue），公式未标记边界情况。

显然最小的着色数是min{dp(根, red), dp(根, blue)}。

我们可以理解树中的从根开始的路径即为某一个IP块的前缀，如RLL即100/3。最后将中国IP段的节点值都标记为red，非APNIC、美国、 英国、日本、香港的IP段的节点值都设为blue。则最后的染色点既路由规则，染为红色的使用本地网关，染为蓝色的使用VPN网关。剩下的节点不产生规 则。

根据这一方法，按照上述的约定，得到的路由表仅包含1093项，相比于chnroutes的方法，路由表减小了约70%。

哪里下载？

我已经把这个项目托管在github上，欢迎fork！

原文：http://ashi009.tumblr.com/post/36581070478/vpn