Longest Prefix Match in Go part 2

In case you’re interested here is part 1: Part 1

Now that I can convert IP subnets to binary, its time to do some prefix matching.

Naive Implementation

As a benchmark to be used later I started with a really simple naive implementation of LPM that just does a search through a list of prefixes (represented as string) to find the longest match:

func routeMatch(r, p string) bool {
    return strings.HasPrefix(r, p)
}

func NaiveFind(r string, routes []string) string {
    best := ""
    for _, elem := range routes {
       if routeMatch(r, elem) && len(r) > len(best) {
           best = r
       }
    }
    return best
}

The routeMatch function just wraps the string.HasPrefix function to determine if a particular route we’re looking up matches the prefix we’re currently looking at. In the NaiveFind function I go through every route in the routes slice, checking if the route matches a prefix. Since we’re doing LPM, I also check to see if the length of the prefix is longer than the best prefix match so far. If so, I set the current prefix to be the best. Then at the end I return the best prefix. This simple lookup will grow linearly with the size of the prefix list, since we have to go through every prefix in the list to do a lookup. I could probably do some form of sorting to help, but due to the varying prefix lengths it could get messy. Next I’ll implement the Trie and show how much better it works for this lookup.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s