Inspired by 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 as a result of the huge route table generated by chnroutes didn't fit into my router.
The route table took almost 4 minutes to load up, and it cannot be
put into OpenVPN's configuration file, due to my service
ping-reset 60 to the client, reseted
OpenVPN before route table being loaded up.
Therefore I decided to minimize the route table.
How efficient it is?
For an example, a route table that route all IPs in China to default gateway, and US, GB, Japan, Hong kong administered IPs to VPN gateway, only need 1546 routing directives, while chnroutes needs 4953 routing directives (based on 11/21/2014 data).
Which is almost 70% smaller. And if route US address to VPN only, the route table has only 105 directives, which is about only 2% of original size.
On Linux system, which usese TRASH structure to store route table, a route lookup operation expected to access memory O(loglog n) times. Using bestroutetb instead of chnroutes, will reduce route table look up at least 0.01 times expectedly. However, this solution does reduce the route table size for 70% by assuming TRASH structure is implemented with a small overhead hash implementation. It is therefore that a perfect approach for those routers with low free memory.
How it works
Unlike chnroutes which will generate a route table that route all subnets of China to ISP gateway, while other route 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 this goal, this project using dynamic programming algorithm to find the most optimized route table.
We can prove that, the generated route table is the smallest one based on the given restrictions.
How to use
This project requires node.js to run.
If you are using OS X, install node.js with homebrew:
$ brew install nodejs
From NPM for use as a command line app:
$ npm install -g bestroutetb
From NPM for programmatic use:
$ npm install bestroutetb
$ git clone https://github.com/ashi009/bestroutetb.git $ cd bestroutetb $ npm link .
$ bestroutetb [options]
Subnets that should be routed to ISP or VPN gateway.
spec should be a list of two-letter country initials (eg. US), subnet (eg.
188.8.131.52/8), and host (eg.
184.108.40.206), concatenated with comma (
NOTE: You could also use multiple
--route.* arguments to construct the list.
-p <profile>, --profile=<profile>
Built-in profiles are
-o <path>, --output=<path>
Output file path.
NOTE: Some profiles may generate multiple files. In which case you need to
specify path to a directory (eg.
-o output/), and you may also specify the
prefix and the desired extension for the output file (eg.
Force to overwrite existing files.
-r <path>, --report=<path>
Generate a report in CSV format and save to given path. Here's an example:
NOTE: These formats applies when
--profile=custom, or in case you want
to override default settings in profile.
All strings will be outputted without adding new line (
Thus, it would be favorable for you to add them in the string. For zsh, bash
and some other shells, you could use
$'line\n' to include a escaped character.
Header and Footer of the output file.
String used to format a rule.
You may use
%gw in the string.
%prefixis the prefix of the subnet (eg.
%maskis the mask of the subnet (eg.
%lengthis the length of the mask (eg.
%gatewayis the routing destination of the subnet (eg.
%gwis the customized destination (eg.
tun0), which is set with
Define substitutes for
%gw in rule format.
Whether to output directive for default route (
0.0.0.0/0), which would be
outputted by default.
Whether to group rules by gateway.
Header and Footer of each group.
You may include
%name in the string.
%nameis the customized group name (eg.
vpn), which is set with
Define substitutes for
%name in group header and group footer.
Force update delegation data, or force to use stale data.
-c <path>, --config=<path>
Configuration file path.
Verbose output level. Use
-vvvv for debug.
Silent mode, which will suppress any output.
Show version number.
$ bestroutetb --route.vpn=us -p json -o routes.json