/bestroutetb

Generating the most optimized route table for VPN users.

Primary LanguageJavaScript

Best Route Table

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 optimize it is?

For a example, a route table that route all IPs in China to default gateway, and US, GB, Japan, Hongkong and non-APNIC administered IPs to VPN gateway (based on 11/26/2012 data,) only need 1093 routing directives, while chnroutes needs 3563 routing directives.

Which is 70% smaller. And if route US address to VPN only, the route table has only 50 directives.

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: http://ashi009.tumblr.com/post/36581070478/vpn

Dependencies

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-writen in Batch (in furture.) But either way it needs wget to download the latest IP delegation file (I will put it in JavaScript.)

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.

Have some fun

node minifier.js [--local=specs] [--vpn=specs] [--onlyAPNIC=1]

Where

  • --local 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.
  • --onlyAPNIC is used ignore non-APNIC administered IPs. When not set, non-APNIC IPs will be routed by VPN gateway. Default not set.
  • specs is a list of country abbreviation names or IP subnet, seperated with comma(,). The abbreviation names can be found in countries.res.

This script will output directives to stdout, and statistic info to stderr, so please redirect stdout to a file. Recommend use generate.sh instead.

Example:

node minifier.js --local=CN --vpn=US,114.134.80.162/31 --onlyAPNIC=1

Outputs:

route 0.0.0.0 0.0.0.0 net_gateway
route 60.254.0.0 255.255.0.0 vpn_gateway
route 103.246.192.0 255.255.192.0 vpn_gateway
route 113.28.0.0 255.254.0.0 vpn_gateway
route 114.134.0.0 255.255.0.0 vpn_gateway
route 163.32.0.0 255.224.0.0 vpn_gateway
route 192.96.0.0 255.240.0.0 vpn_gateway
route 202.72.96.0 255.255.224.0 vpn_gateway
route 203.144.0.0 255.255.192.0 vpn_gateway
route 203.187.128.0 255.255.224.0 vpn_gateway
Total: 10 rules

Analysis a route table

node evaluator.js input [--verbose=1] [--default=default]

Where

  • input is the path to route table.
  • --verbose when set will output the route result for every block. Default not set.
  • --default is the default gateway for 0.0.0.0/0.

Note that, this script is not complete, as it only analysis the base IP of the block of each APNIC/nonAPNIC delegation. But some IPs in a block could be routed to other gateway than its base IP's (this only affects some nonAPNIC IP blocks, as it overlaps some APNIC IP blocks.)

Update IP delegation files

rm *.dat
./generate.sh