ashi009 / bestroutetb

Generating the most optimized route table for VPN users.
MIT License
879 stars 99 forks source link

实现最小匹配标记 #3

Open ashi009 opened 11 years ago

ashi009 commented 11 years ago

当前产生路由表的回溯算法是最大匹配的,即假设存在变色点的前缀树:

R(N(N,B),N(B,N))

其中R/B/N分别表示节点值为红/蓝/无色

再产生路由规则时时会将值为蓝色的孙子节点提高到R的儿子高度:

R(B,B)

对于一些地址段,这样的策略可能并不是十分妥当:

  1. 希望从net_gateway的地址空间中去掉个别主机地址:x.y.z.w/32
  2. 希望尽可能多的地址使用net_gateway或vpn_gateway。

所以希望可以实现最小匹配标记,即修改minifier.js的输入参数--local=specs--vpn=specs接受如下格式的标记:

  1. -国家缩写-us,表示在APNIC分配表内的美国地址使用最小匹配。
  2. -IP/mask-123.123.15.30/30,表示123.123.15.30/30地址段使用最小匹配。

并在保持产生最少规则数的原则下,满足最小匹配的要求,(实际只有在父节点/子节点的值不同时,才可以应用这一规则。)