go-iprtb: Pure Go IP Routing Table Implementation
Tags: go, routingtable
Published: 2022-11-14 08:25:39

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.

```go
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 1**0000000 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 :tada: