Building a High-Performance IP Prefix Map in Go

When working at scale with network devices and BGP peers, efficiently managing and querying IP address information becomes crucial. In this post, I’ll share how we built a high-performance IP prefix map using a Trie data structure in Go, and how it solved real-world problems.

The Problem: BGP Peer to Interface Mapping

While working at a previous company, we faced an interesting challenge: we needed to quickly determine which interface a BGP peer was associated with. Each network device had multiple interfaces, each with its own subnet, and BGP peers could connect from any of these ranges. Traditional IP lookup methods were either too slow or memory-intensive for our needs.

Here’s what a typical network device configuration looked like:

interface Ethernet1
  ip address 10.1.1.0/24
  description "peer-rack-1"

interface Ethernet2
  ip address 10.1.2.0/24
  description "peer-rack-2"

router bgp 65000
  neighbor 10.1.1.100 remote-as 65001
  neighbor 10.1.2.100 remote-as 65002

The challenge was to quickly answer questions like: “Which interface is BGP peer 10.1.1.100 connected to?”

The Solution: IP Trie

We implemented a Trie-based prefix map that could efficiently store and query IP addresses while maintaining metadata about each prefix. A Trie (also known as a prefix tree) is perfect for this use case because:

  1. It provides O(k) lookup time, where k is the length of the IP address
  2. It naturally handles IP prefix matching
  3. It’s memory-efficient for storing large numbers of prefixes
  4. It can store metadata with each prefix

Here’s how we use it:

package main

import (
    "fmt"
    "github.com/metajar/trie-network"
)

func main() {
    // Create a new IP Trie
    prefixMap := iptrie.NewIPTrie()

    // Insert interface information
    eth1Meta := map[string]interface{}{
        "interface": "Ethernet1",
        "description": "peer-rack-1",
        "speed": "100G",
    }
    prefixMap.Insert("10.1.1.0/24", eth1Meta)

    eth2Meta := map[string]interface{}{
        "interface": "Ethernet2",
        "description": "peer-rack-2",
        "speed": "100G",
    }
    prefixMap.Insert("10.1.2.0/24", eth2Meta)

    // Look up a BGP peer's interface
    peer := "10.1.1.100"
    cidr, metadata, err := prefixMap.Find(peer)
    if err != nil {
        fmt.Printf("Error finding peer: %v\n", err)
        return
    }

    fmt.Printf("BGP peer %s is on interface %s (%s)\n",
        peer,
        metadata["interface"],
        metadata["description"])
}

Output:

BGP peer 10.1.1.100 is on interface Ethernet1 (peer-rack-1)

Performance

The implementation is highly efficient:

BenchmarkIPv4Find-8         5000000      242 ns/op       0 B/op      0 allocs/op
BenchmarkIPv6Find-8         2000000      645 ns/op       0 B/op      0 allocs/op
  • IPv4 lookups complete in under 250 nanoseconds
  • Zero allocations during lookups
  • Scales linearly with prefix length
  • Memory usage grows sublinearly with the number of prefixes

Key Features

  1. Dual Stack Support: Handles both IPv4 and IPv6 addresses
  2. CIDR Notation: Uses standard CIDR notation for prefix ranges
  3. Metadata Storage: Attach arbitrary metadata to each prefix
  4. Overlapping Ranges: Can find all matching prefixes for an IP
  5. Memory Efficient: Compact storage of prefixes
  6. Thread Safe: Safe for concurrent use (with proper synchronization)

Implementation Details

The core of the implementation uses a binary trie where:

  • Each node represents a bit in the IP address
  • Each path from root to leaf represents a prefix
  • Metadata is stored at leaf nodes
  • The trie automatically compresses paths when possible
type Node struct {
    children map[byte]*Node
    isEnd    bool
    metadata map[string]interface{}
    cidr     string
}

Real-World Impact

This implementation allowed us to:

  1. Quickly map thousands of BGP peers to their interfaces
  2. Reduce lookup latency by 90% compared to our previous solution
  3. Better handle network events by quickly identifying affected interfaces
  4. Improve troubleshooting by having immediate access to interface metadata

Best Practices

When using this IP Trie implementation:

  1. Pre-populate the trie during initialization to avoid runtime insertions
  2. Use meaningful metadata keys that are consistent across your application
  3. Consider adding mutex locks if you need concurrent access
  4. Keep metadata size reasonable to maintain memory efficiency

Conclusion

Building a custom IP prefix map using a Trie data structure solved our specific needs for mapping BGP peers to interfaces. The implementation is efficient, maintainable, and can be adapted for various IP management needs.

The complete implementation is available on GitHub: IP Trie Implementation

Future Improvements

Some potential enhancements we’re considering:

  1. PATRICIA trie optimization for even better memory usage
  2. Built-in concurrent access support
  3. Serialization support for persistence
  4. Real-time prefix updates with minimal lock contention