Best Route Table-一个类似于chnroutes的项目

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.
查看使用说明

Objective

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.

How efficient it is?

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.)

How it works

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.
For further detail.

Dependencies

This project is mainly written in JavaScript, and some in Bash. So you will need node.js to run the scripts.

• node.js

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.

• wget

How to use

Quick start

./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

• output is the path of output route table.
• options will be redirected to ./minifier.js and ./formatter.js.

Generating Rules

node minifier.js [--net=SPECS] [--vpn=SPECS]

Where

• --net is used to specify a list of country abbreviations and IP subnets to be routed to default gateway. Default to CN.
• --vpn is used to specify a list of country abbreviations and IP subnets to be routed to VPN gateway. Default to US,GB,JP,HK.
• SPECS is a list separated with comma(,) of country abbreviation names, IP subnets or the path to a file of SPECS. Note that, the abbreviation names can be found in res/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

Formatting a rules file

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

• input is the path to JSON format rule file, if omitted, stdin will be used.
• --profile chosen between openvpn, route_up, route_down, iproute_up, iproute_down, win_up, win_down, ppp_ip_up, custom. Default to openvpn.
• --header header of the output file.
• --footer footer of the output file.
• --format string used to format a rule when --profile=custom. You can use %prefix, %mask, %length, and %gw to correspond fields in a rule. You may also use other variables (%[a-zA-Z]\w*) which are passed in in arguments.
• --netgw %gw for "gw": "net" rules, when not using --profile=openvpn.
• --vpngw %gw for "gw": "vpn" rules, when not using --profile=openvpn.
• --nodefaultgw don't output directive for default route (0.0.0.0/0).
• --groupgw group rules by gateway. Useful when you want rules to be outputed in two parts, say two functions for each interface. Default to 1 when --profile=ppp_ip_up, otherwise 0.
• --netgroupname %name for "gw": "net" rules, when --groupgw=1.
• --vpngroupname %name for "gw": "vpn" rules, when --groupgw=1.
• --groupheader header of each group. Note that, which could include %name to identify group.
• --groupfooter footer of each group. Note that, which could include %name to identify group.
• arguments a group of arguments to be used in format (eg. add --var="value" to arugments, then use %var for value in --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
...

Analysing a rules file

node evaluator.js [input] [--verbose=1] [--defaultgw=DEFAULT]

Where

• input is the path to JSON format rule file, if omitted, stdin will be used.
• --verbose when set will output the route result for every block. Default not set.
• --defaultgw is the gateway for 0.0.0.0/0.

Updating IP delegation files

rm -f data/*
./generate.sh 

from https://github.com/ashi009/bestroutetb#best-route-table