GoのIP Routing Tableの実装について調べてみたところ、だいたいOSのRouting Tableを操作する系のライブラリがヒットし *1、そうではなくユーザー側コードでRouting Table相当の実装・処理をしたい時に使えそうなライブラリがパッと見当たらなかったのでそれを書いたという次第です。
さて、GoでシンプルなRouting Table実装を書くのは実に簡単で、以下のように書くだけでほぼ期待通りに動くと思います。
type RouteEntry struct { Destination net.IPNet Gateway net.IP NwInterface string Metric int } routes := map[string]RouteEntry{} // ここでroutesにrouteを登録する // `target net.IP` がrouting tableに含まれているかどうかをチェックする var matched RouteEntry var everMatched bool for _, r := range routes { if r.Destination.Contains(target) { if !everMatched { matched = r everMatched = true continue } matchedMaskLen, _ := matched.Destination.Mask.Size() newRouteMaskLen, _ := r.Destination.Mask.Size() if newRouteMaskLen > matchedMaskLen { // for longest match matched = r } } } fmt.Println(matched)
この実装の問題としてはlongest matchを考慮するためにはRouting Tableのエントリをすべて線形に走査する必要があるため、Routing Table中のエントリ数が増えれば増えるほど計算量が増える、ということが挙げられます。
したがってTable中のroutes全てを1つのPrefix Treeに落としこんでやることで、対象のアドレスについてその木のパスを1回走査するだけで対象アドレスがRouting Tableにマッチしているかどうかを判断することができ、これにより計算量を減らすことができるという狙いがあります。
例えば 10.0.0.0/8, 192.0.0.0/8, そして 192.128.0.0/9 という3つのサブネットを考えたとき、それぞれの2進数表記は以下のようになります。表にはサブネットに属するゲートウェイについても記載しています。
| Subnet | Subnet Binary | Gateway |
|---|---|---|
| 10.0.0.0/8 | 00001010 00000000 00000000 00000000 | GW1 |
| 192.0.0.0/8 | 11000000 00000000 00000000 00000000 | GW2 |
| 192.128.0.0/9 | 11000000 10000000 00000000 00000000 | GW3 |
太字はサブネットマスクを適用した後のアドレスを表わしています。このアドレスビット列についてTrie木を構築していくと以下のようになります。
R
/ \
/ \
0 1
/ \
0 1
/ /
0 0
/ /
0 0
\ /
1 0
/ /
0 0
\ /
1 0
/ /
GW1 [0] [0] GW2
\
[1] GW3
† R: Root Node
†† [n]: Terminal Nodeそして対象アドレスを2進数にしてこの木に対して最長マッチをさせていくと以下のような結果が得られます ([ ]で囲われた箇所は終端ノードを表わしています):
| Target IP | Target IP Binary | Found Gateway |
|---|---|---|
| 10.10.10.10 | 0000101[0] 00001010 00001010 00001010 | GW1 |
| 192.10.10.10 | 1100000[0] 00001010 00001010 00001010 | GW2 |
| 192.192.10.10 | 11000000 [1]1000000 00001010 00001010 | GW3 |
| 127.0.0.1 | 01111111 00000000 00000000 00000001 | N/A |
今回書いたライブラリでは上記で挙げたような木構造による実装をしたところ、以下のような性能改善を実現できました。
$ go test -bench=. -benchmem goos: linux goarch: amd64 pkg: github.com/moznion/go-iprtb cpu: 12th Gen Intel(R) Core(TM) i7-1280P Benchmark_PrefixTreeAlgorithm-20 18535410 81.68 ns/op 64 B/op 1 allocs/op Benchmark_LinearSearch-20 6148155 192.1 ns/op 96 B/op 1 allocs/op PASS ok github.com/moznion/go-iprtb 2.968s
速い！ 良かったですね。
なお他にもroute消去時の枝刈りなど細々としたパフォーマンスのチューニングが入っていたりもします。
ぜひご利用ください。
