Longest Prefix Match algorithm in Go part 1

One of the lookups a router/switch has to do is a longest prefix match (LPM), which is normally done in hardware with some sophisticated algorithms. But since I’m no ASIC designer, I thought I’d play around with doing it in software. If everything had fixed prefix sizes (i.e. no VLSM), things would be easier. We could do a direct lookup for the prefix in question and get an answer. Since we have varying masks, we can no longer just do a lookup, we have to find the best match based on what matches the most bits.

As a programming exercise for learning Go, I decided to try out a couple different methods of doing LPM:
1) Naive approach : search through every route and find the best LPM. Worst case for this would be O(n) where n = the number of routing table entries. This is fine for a very small routing table, but grows linearly with the size of the routing table. Essentially this means if we add 10x more routes, it will take roughly 10x longer. It also requires O(n) storage for all the routes.

2) Use a trie data structure : Using this for LPM would max out at 32 steps for an IPv4 address, and would be less for a shorter prefixes. This builds a trie that maps each bit to a branch. By doing so, the worst case scenario is to go all the way to a host route of /32, which is our worst case. No matter how large our routing table gets, we will never do more than 32 lookups. In addition, there is some space savings for overlapping prefixes (i.e. if you have 10.1.1.0/24 and 10.1.0.0/16, they would share common branches). This could be further compressed using a Radix Tree.

Given what I’ve outlined above, what I expect to see is #1 to outperform #2 for small tables (< 30 routes). But as the table size grows, #2 should stay the same, and #1 should take longer and longer. Current Internet BGP tables are at 500,000k+ routes http://etherealmind.com/wont-get-better-internet-old-one-broken-500k-bgp-routes-good-start/ so we definitely want efficiency when doing these lookups.

For this project I went with a Test Driven Development (TDD) methodology where I wrote the unit tests first, then created the code to make it work. Then I created some benchmark tests (an awesome feature of Go testing) to see if using the trie performed like I hoped.

Test file

Here’s the beginning of the test file:

package trie

import (
	"fmt"
	"math/rand"
	"testing"
)

This puts the test file in the trie package and imports the libraries that I’ll be using for the tests.

Helper Functions

First I wrote a couple helper functions to convert IP addresses to a string of binary digits. There are two functions here, one for converting a single byte/octet and another to do the entire dotted decimal IP address/mask. Here are the tests for those functions:

func TestConvertOctet(t *testing.T) {
	if ConvertOctet("10") != "00001010" {
		t.Errorf("want %v", "00001010")
	}
	if ConvertOctet("0") != "00000000" {
		t.Errorf("want %v", "00000000")
	}
	if ConvertOctet("255") != "11111111" {
		t.Errorf("want %v", "11111111")
	}
	if ConvertOctet("255") == "00000000" {
		t.Errorf("want %v", "11111111")
	}
}

func TestConvert(t *testing.T) {
	if Convert("10.1.1.1/8") != "00001010" {
		t.Errorf("want %v", "00001010")
	}
	if Convert("10.1.1.1/16") != "0000101000000001" {
		t.Errorf("Got %v, want %v", Convert("10.1.1.1/16"), "0000101000000001")
	}
	if Convert("210.112.153.10/20") != "11010010011100001001" {
		t.Errorf("Got %v, want %v", Convert("210.112.153.10/20"), "11010010011100001001")
	}
	if Convert("255.255.255.255/32") != "11111111111111111111111111111111" {
		t.Errorf("Got wrong binary")
	}
}

You’ll see for each testing function we pass a pointer to a test variable that handles the state and logs of the testing. Also every function begins with Test… that will trigger these functions to be called when you do a go test. Initially these tests will fail of course, then its up to me to make them work. The cool thing is that as the code develops, these will always get tested to make sure I don’t break anything later. Now let’s write the code to do these conversions. First converting a single octet:

// Converts an IP octet (0-255) to binary with 8 bits
func ConvertOctet(oct string) string {
        i, err := strconv.ParseInt(oct, 10, 64)
        if err != nil {
                fmt.Println(err)
        }
        j := strconv.FormatInt(i, 2)
        pad := strings.Repeat("0", 8-len(j))
        return strings.Join([]string{pad, j}, "")
}

There is probably a better way to do this, but I took the octet that is passed as a string, and converted it to an integer. Then I take that integer and reformat it as a string of binary digits. Finally I create some padding to put zeros in front if its not 8-bits long, and join the padding to the binary string. Now we can use this to convert an IP address:

// Converts a / address to binary
func Convert(addrMask string) string {
        parts := strings.Split(addrMask, "/")
        ip := strings.Split(parts[0], ".")
        var buffer bytes.Buffer
        mask, err := strconv.Atoi(parts[1])
        if err != nil {
                fmt.Println(err)
        }
        for i := 0; i < 4; i++ {
                buffer.WriteString(ConvertOctet(ip[i]))
        }
        return buffer.String()[:mask]
}

For this function I take the IP address which will be in the form of “x.x.x.x/24”, and split off the mask. Then I split the individual octets into a slice. I convert the mask (i.e. 24) into an integer to be used later. Then I go through each octet, converting them to binary values using the ConvertOctet function, appending each binary value to the buffer. Finally I return the buffer, converted to a string, and slicing off the host part using the mask as an index to the slice.

In the next part I’ll go into the naive implementation.

Advertisements

2 thoughts on “Longest Prefix Match algorithm in Go part 1

  1. I read a lot of interesting content here. Probably you spend a lot of time writing, i know how to save
    you a lot of work, there is an online tool that creates unique, SEO
    friendly articles in seconds, just type in google – masagaltas free content

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