cidranger

Fast IP to CIDR block(s) lookup using trie in Golang, inspired by IPv4 route lookup linux. Possible use cases include detecting if a IP address is from published cloud provider CIDR blocks (e.g. 52.95.110.1 is contained in published AWS Route53 CIDR 52.95.110.0/24), IP routing rules, etc.

This is visualization of a trie storing CIDR blocks 128.0.0.0/2192.0.0.0/2200.0.0.0/5 without path compression, the 0/1 number on the path indicates the bit value of the IP address at specified bit position, hence the path from root node to a child node represents a CIDR block that contains all IP ranges of its children, and children's children.

Visualization of trie storing same CIDR blocks with path compression, improving both lookup speed and memory footprint.

Getting Started

Configure imports.

import (
"net""github.com/yl2chen/cidranger"
)

Create a new ranger implemented using Path-Compressed prefix trie.

ranger:=NewPCTrieRanger()

Inserts CIDR blocks.

_, network1, _:=net.ParseCIDR("192.168.1.0/24")
_, network2, _:=net.ParseCIDR("128.168.1.0/24")
ranger.Insert(NewBasicRangerEntry(*network1))
ranger.Insert(NewBasicRangerEntry(*network2))

To attach any additional value(s) to the entry, simply create custom struct storing the desired value(s) that implements the RangerEntry interface:

typeRangerEntryinterface {
Network() net.IPNet
}

The prefix trie can be visualized as:

0.0.0.0/0 (target_pos:31:has_entry:false)
| 1--> 128.0.0.0/1 (target_pos:30:has_entry:false)
| | 0--> 128.168.1.0/24 (target_pos:7:has_entry:true)
| | 1--> 192.168.1.0/24 (target_pos:7:has_entry:true)

To test if given IP is contained in constructed ranger,

contains, err=ranger.Contains(net.ParseIP("128.168.1.0")) // returns true, nilcontains, err=ranger.Contains(net.ParseIP("192.168.2.0")) // returns false, nil

To get all the networks given is contained in,

containingNetworks, err=ranger.ContainingNetworks(net.ParseIP("128.168.1.0"))

To get all networks in ranger,

entries, err:=ranger.CoveredNetworks(*AllIPv4) // for IPv4entries, err:=ranger.CoveredNetworks(*AllIPv6) // for IPv6

Benchmark

Compare hit/miss case for IPv4/IPv6 using PC trie vs brute force implementation, Ranger is initialized with published AWS ip ranges (889 IPv4 CIDR blocks and 360 IPv6)

// Ipv4 lookup hit scenarioBenchmarkPCTrieHitIPv4UsingAWSRanges-45000000353ns/opBenchmarkBruteRangerHitIPv4UsingAWSRanges-410000013719ns/op// Ipv6 lookup hit scenario, counter-intuitively faster then IPv4 due to less IPv6 CIDR// blocks in the AWS dataset, hence the constructed trie has less path splits and depth.BenchmarkPCTrieHitIPv6UsingAWSRanges-410000000143ns/opBenchmarkBruteRangerHitIPv6UsingAWSRanges-43000005178ns/op// Ipv4 lookup miss scenarioBenchmarkPCTrieMissIPv4UsingAWSRanges-42000000096.5ns/opBenchmarkBruteRangerMissIPv4UsingAWSRanges-45000024781ns/op// Ipv6 lookup miss scenarioBenchmarkPCTrieHMissIPv6UsingAWSRanges-410000000115ns/opBenchmarkBruteRangerMissIPv6UsingAWSRanges-410000010824ns/op

Example of IPv6 trie:

::/0 (target_pos:127:has_entry:false)
| 0--> 2400::/14 (target_pos:113:has_entry:false)
| | 0--> 2400:6400::/22 (target_pos:105:has_entry:false)
| | | 0--> 2400:6500::/32 (target_pos:95:has_entry:false)
| | | | 0--> 2400:6500::/39 (target_pos:88:has_entry:false)
| | | | | 0--> 2400:6500:0:7000::/53 (target_pos:74:has_entry:false)
| | | | | | 0--> 2400:6500:0:7000::/54 (target_pos:73:has_entry:false)
| | | | | | | 0--> 2400:6500:0:7000::/55 (target_pos:72:has_entry:false)
| | | | | | | | 0--> 2400:6500:0:7000::/56 (target_pos:71:has_entry:true)
| | | | | | | | 1--> 2400:6500:0:7100::/56 (target_pos:71:has_entry:true)
| | | | | | | 1--> 2400:6500:0:7200::/56 (target_pos:71:has_entry:true)
| | | | | | 1--> 2400:6500:0:7400::/55 (target_pos:72:has_entry:false)
| | | | | | | 0--> 2400:6500:0:7400::/56 (target_pos:71:has_entry:true)
| | | | | | | 1--> 2400:6500:0:7500::/56 (target_pos:71:has_entry:true)
| | | | | 1--> 2400:6500:100:7000::/54 (target_pos:73:has_entry:false)
| | | | | | 0--> 2400:6500:100:7100::/56 (target_pos:71:has_entry:true)
| | | | | | 1--> 2400:6500:100:7200::/56 (target_pos:71:has_entry:true)
| | | | 1--> 2400:6500:ff00::/64 (target_pos:63:has_entry:true)
| | | 1--> 2400:6700:ff00::/64 (target_pos:63:has_entry:true)
| | 1--> 2403:b300:ff00::/64 (target_pos:63:has_entry:true)