go-iprtb: Pure Go IP Routing Table Implementation

I published a golang library that provides IP routing table implementation.

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 🎉

Blog

go-iprtb: Pure Go IP Routing Table Implementation

moznion

Join Our Newsletter. No Spam, Only the good stuff.

Related