I published a golang library that provides IP routing table implementation.
https://github.com/moznion/go-iprtb
When I googled by a query like "Golang routing table", then there were libraries that provide the function to manipulate OS-level routing table but I couldn't find out a library to implement/process the IP routing table on the user-level. That user-level one was my needed thing so I wrote this library.
In fact, it is easy to write a simple IP routing table in Golang. Just writing like the following code would satisfy the features of the routing table.
type RouteEntry struct {
Destination net.IPNet
Gateway net.IP
NwInterface string
Metric int
}
routes := map[string]RouteEntry{}
// Register routes here
// Following loops check whether the `target net.IP` matches with the 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)
Bur this code has a problem: when it respects the longest match, it has to scan all registered routes as linear, so the computation cost increases according to the number of entries in a table.
So once these routes have been able to transform into a prefix tree data structure, it can determine whether the target address matches the routing table by only traversing paths of that tree only one time (i.e. without backtracking).
For example, when there are three subnets 10.0.0.0/8, 192.0.0.0/8, and 192.128.0.0/9 in a routing table, each binary expression is like the following. And this table contains the gateway that associates with the subnet.
| 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 |
The bold section is the address that is applied subnet mask. And the trie-tree becomes like the following by building according to the masked addresses:
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
and then it derives the following result by matching the binary target addresses to this tree as much as longer (the digit surrounded by [ ] describes a terminal node):
| 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-iprtb implements the tree-based algorithm, then it succeeds to improve the performance:
$ 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
Yay 🎉
Top comments (0)