Inspired by https://github.com/fivesheep/chnroutes.
This project aimed to generate the smallest route table, while preserves the minimalist requirements that IPs of specified countries or subnets will be routed to a specified gateway (default or VPN).
Generally speaking, the generated route table is at least 70% smaller than chnroutes's.
查看使用说明
I started this project due to the huge route table generated by chnroutes doesn't fit into my router.
Which takes almost 4 minutes to load up, and it cannot be
put into OpenVPN"s configuration file for my service
provider pushed ping-reset 60 to the client, reseted
OpenVPN before route table being loaded up.
So I decided to minimize the route table.
For a example, a route table that route all IPs in China to default gateway, and US, GB, Japan, Hong kong administered IPs to VPN gateway (based on 4/8/2013 data,) only need 1164 routing directives, while chnroutes needs 3589 routing directives.
Which is 70% smaller. And if route US address to VPN only, the route table has only 99 directives, which is less than 2% of original size.
On Linux system, which usese TRASH structure to store routing table, a route lookup operation expected to access memory O(loglog n) times. Using bestroutetb over chnroutes, will reduce at least 0.01 accesses expectedly. (This is joking! But it does reduce the route table size in memory for 70% by assuming TRASH structure is using a very small overhead hash implementation, which is significant. So this solution works especially well on those routers don't have lots of free memory.)
Unlike chnroutes, which will generate a route table that route all IPs of china to default gateway, while other IPs to VPN gateway. This project divides IPs in three groups. First group is guaranteed to be routed to default gateway, Second group is guaranteed to be routed to VPN gateway. And the last group will be dynamically assigned to one of the gateways, in a manner that will generate the smallest route table.
To achieve the goal, this project using dynamic programming algorithm to find out the most optimized route table.
We can prove that, the generated route table is the smallest one based on the given restrictions.
This project is mainly written in JavaScript, and some in Bash. So you will need node.js to run the scripts.
Bash code is relatively simple, and could be re-written in Batch (in future.) But either way it needs wget to download the latest IP delegation file for now.
./generate.sh route_table > analysis_result
Which will output the routing directives (OpenVPN syntax) to
route_table and a summarized evaluation report to analysis_result.
The syntax for this script is:
./generate.sh output [options]
Where
outputis the path of output route table.optionswill be redirected to./minifier.jsand./formatter.js.
node minifier.js [--net=SPECS] [--vpn=SPECS]
Where
--netis used to specify a list of country abbreviations and IP subnets to be routed to default gateway. Default toCN.--vpnis used to specify a list of country abbreviations and IP subnets to be routed to VPN gateway. Default toUS,GB,JP,HK.SPECSis a list separated with comma(,) of country abbreviation names, IP subnets or the path to a file ofSPECS. Note that, the abbreviation names can be found inres/countrynames, and paths in file won't be followed.
This script will output rules in JSON to stdout, and statistic
info to stderr, so please redirect stdout to a file. Recommend
use generate.sh instead.
JSON structure:
[
Rule,
...
]
Rule structure:
{
"prefix": "dest",
"mask": "netmask",
"length", netmaskLength,
"gw": "net|vpn"
}
Example:
node minifier.js --net=128.8.0.0/16 --vpn=specs
Where specs contains:
# Country list
GB
# IP list
8.0.0.0/8
123.4.5.6 # this is a host
Outputs:
[{
"prefix": "0.0.0.0",
"mask": "0.0.0.0",
"length": 0,
"gw": "vpn"
}, {
"prefix": "128.0.0.0",
"mask": "255.240.0.0",
"length": 12,
"gw": "net"
}]
Total: 2 rules
node formatter.js [input] [--profile=PROFILE]
[--header=HEADER] [--footer=FOOTER]
[--format=FORMAT] [--netgw=NETGW] [--vpngw=VPNGW]
[--nodefaultgw=1]
[--groupgw=GROUPGW]
[--groupheader=GROUPHEADER] [--groupfooter=GROUPFOOTER]
[arguments]
Where
inputis the path to JSON format rule file, if omitted,stdinwill be used.--profilechosen betweenopenvpn,route_up,route_down,iproute_up,iproute_down,win_up,win_down,ppp_ip_up,custom. Default toopenvpn.--headerheader of the output file.--footerfooter of the output file.--formatstring used to format a rule when--profile=custom. You can use%prefix,%mask,%length, and%gwto correspond fields in a rule. You may also use other variables (%[a-zA-Z]\w*) which are passed in inarguments.--netgw%gwfor"gw": "net"rules, when not using--profile=openvpn.--vpngw%gwfor"gw": "vpn"rules, when not using--profile=openvpn.--nodefaultgwdon't output directive for default route (0.0.0.0/0).--groupgwgroup rules by gateway. Useful when you want rules to be outputed in two parts, say two functions for each interface. Default to1when--profile=ppp_ip_up, otherwise0.--netgroupname%namefor"gw": "net"rules, when--groupgw=1.--vpngroupname%namefor"gw": "vpn"rules, when--groupgw=1.--groupheaderheader of each group. Note that, which could include%nameto identify group.--groupfooterfooter of each group. Note that, which could include%nameto identify group.argumentsa group of arguments to be used informat(eg. add--var="value"toarugments, then use%varforvaluein--format.)
Example:
node formatter.js rules.json
# or node minifier.js --vpn=us | node formatter.js
Outputs:
Total: 99 rules
route 0.0.0.0 0.0.0.0 vpn_gateway
route 0.0.0.0 254.0.0.0 net_gateway
route 1.0.16.0 255.255.240.0 vpn_gateway
route 1.0.64.0 255.255.192.0 vpn_gateway
route 1.1.64.0 255.255.192.0 vpn_gateway
route 1.5.0.0 255.255.0.0 vpn_gateway
route 1.16.0.0 255.248.0.0 vpn_gateway
route 1.32.0.0 255.248.0.0 vpn_gateway
route 1.64.0.0 255.252.0.0 vpn_gateway
route 1.72.0.0 255.248.0.0 vpn_gateway
route 1.112.0.0 255.252.0.0 vpn_gateway
...
node evaluator.js [input] [--verbose=1] [--defaultgw=DEFAULT]
Where
inputis the path to JSON format rule file, if omitted,stdinwill be used.--verbosewhen set will output the route result for every block. Default not set.--defaultgwis the gateway for 0.0.0.0/0.
rm -f data/*
./generate.sh