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

80,379
16
167
136

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

How to sort IP addresses in a trie table?

1 Answers1

Linked