How to sort IP addresses in a trie table?

Question

I want to make a bit of code to have a small "routing table" in my Go program.

I'm using left-leaning red-black trees with the http://github.com/petar/GoLLRB package and basically it seems to work after fussing with it for a bit, however I suspect that I'm not sorting the IP prefixes correctly when I create the tree. The "lessThan" function I used experimentally is

func lessRoute(a, b interface{}) bool {
    aNet := a.(Route).Net
    bNet := b.(Route).Net

    for i, a := range aNet.IP {
        if a < bNet.IP[i] {
            return true
        }
        if a > bNet.IP[i] {
            return false
        }
    }
    return false
}

(the full code is at https://gist.github.com/4283789 )

This seems to give me the correct results, but not very efficiently.

In my test I'm adding routes for

AddRouteString(tree, "10.0.0.0/8", 10)
AddRouteString(tree, "10.20.0.0/16", 20)
AddRouteString(tree, "10.21.0.0/16", 21)

and then when looking up a route for 10.22.0.1 it will look through 10.21.0.0/16 and 10.20.0.0/16 before finding the right result.

How should I order my tree to find the right results faster?

Update: @jnml has an excellent suggestion of how to make the IP comparison faster (and maybe that's the best I can do), but it seems to me like there'd be a way to make advantage of the prefix length to order the tree so matches can be found in less steps. That's what I am looking for.

zzzz · Answer 1 · 2012-12-14T09:21:51.667

1

I would probably write:

if bytes.Compare([]byte(a), []byte(b)) < 0 {
        // ... whatever to do when address a < b (lexicographically)
}

Or for the tree comparator:

func lessRoute(a, b interface{}) bool {
        return bytes.Compare([]byte(a.(Route).Net.IP), []byte(b.(Route).Net.IP)) < 0
}

bytes.Compare() documented here.

edited Dec 14 '12 at 09:21

answered Dec 14 '12 at 09:16

zzzz

87,403
16
175
139

Ah, yes – that'll make the comparison much faster. My concern though is how to order the tree; it seems like there's something to do taking advantage of the prefix-lenghts, too. – Ask Bjørn Hansen Dec 14 '12 at 16:31
Modern processors will pull the entire IP address into L1 cache and process the common prefix faster than you can calculate where the common prefix starts. – TomOnTime Oct 18 '17 at 04:21

Sean F · Answer 2 · 2022-07-05T04:45:59.780

"there'd be a way to take advantage of the prefix length to order the tree so matches can be found in less steps"

What you are describing sounds a lot like a prefix trie, aka a radix tree or radix trie. This is different from a left-leaning red-black tree, and is commonly used for routing, such as within the Linux kernel. It orders the routes in the tree by prefix. The lookup operation you are describing is typically called "longest prefix match".

Following the link to your gist, I can see that you eventually realized that yourself, as you are now using a binary trie implementation in the gist.

The ipaddress-go Go library has an address binary trie implementation that works with either IPv4 or IPv6.

The following code is equivalent to the code in your gist.

package main

import (
    "fmt"
    "github.com/seancfoley/ipaddress-go/ipaddr"
)

func main() {
    trie := ipaddr.AssociativeAddressTrie{} 

    cidrMappings := []struct {
        cidr string
        asn  int
    }{
        {"10.0.0.2/8", 10},
        {"10.20.0.0/14", 20},
        {"10.21.0.0/16", 21},
        {"192.168.0.0/16", 192},
        {"192.168.2.0/24", 1922},
    }
    for _, mapping := range cidrMappings {
        cidr := ipaddr.NewIPAddressString(mapping.cidr).GetAddress().
            ToPrefixBlock().ToAddressBase()
        trie.Put(cidr, mapping.asn)
    }
    fmt.Println("trie is", trie)
    lookup(trie, "10.20.1.2")
    lookup(trie, "10.22.1.2")
    lookup(trie, "10.19.0.1")
    lookup(trie, "10.21.0.1")
    lookup(trie, "192.168.2.3")
    lookup(trie, "230.0.0.1")
}

func lookup(trie ipaddr.AssociativeAddressTrie, addrStr string) {
    addr := ipaddr.NewIPAddressString(addrStr).GetAddress().
        ToAddressBase()
    matchedNode := trie.LongestPrefixMatchNode(addr)
    mappedVal := matchedNode.GetValue()
    var mappedAsn int
    if mappedVal != nil {
        mappedAsn = mappedVal.(int)
    }
    fmt.Printf("%s lookup is %d\n", addr, mappedAsn)
}

Output:

trie is 
○ 0.0.0.0/0 (5)
├─● 10.0.0.0/8 = 10 (3)
│ └─● 10.20.0.0/14 = 20 (2)
│   └─● 10.21.0.0/16 = 21 (1)
└─● 192.168.0.0/16 = 192 (2)
  └─● 192.168.2.0/24 = 1922 (1)

10.20.1.2 lookup is 20
10.22.1.2 lookup is 20
10.19.0.1 lookup is 10
10.21.0.1 lookup is 21
192.168.2.3 lookup is 1922
230.0.0.1 lookup is 0

How to sort IP addresses in a trie table?

2 Answers2

Linked