cidranger

package module
v1.0.4 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 28, 2022 License: MIT Imports: 5 Imported by: 2

README

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.

GoDoc Reference Build Status Coverage Status Go Report Card

This is visualization of a trie storing CIDR blocks 128.0.0.0/2 192.0.0.0/2 200.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:

type RangerEntry interface {
	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, nil
contains, 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 IPv4
entries, 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 scenario
BenchmarkPCTrieHitIPv4UsingAWSRanges-4         	 5000000	       353   ns/op
BenchmarkBruteRangerHitIPv4UsingAWSRanges-4    	  100000	     13719   ns/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-4         	10000000	       143   ns/op
BenchmarkBruteRangerHitIPv6UsingAWSRanges-4    	  300000	      5178   ns/op

// Ipv4 lookup miss scenario
BenchmarkPCTrieMissIPv4UsingAWSRanges-4        	20000000	        96.5 ns/op
BenchmarkBruteRangerMissIPv4UsingAWSRanges-4   	   50000	     24781   ns/op

// Ipv6 lookup miss scenario
BenchmarkPCTrieHMissIPv6UsingAWSRanges-4       	10000000	       115   ns/op
BenchmarkBruteRangerMissIPv6UsingAWSRanges-4   	  100000	     10824   ns/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)

Documentation

Overview

Package cidranger provides utility to store CIDR blocks and perform ip inclusion tests against it.

To create a new instance of the path-compressed trie:

ranger := NewPCTrieRanger()

To insert or remove an entry (any object that satisfies the RangerEntry interface):

_, network, _ := net.ParseCIDR("192.168.0.0/24")
ranger.Insert(NewBasicRangerEntry(*network))
ranger.Remove(network)

If you desire for any value to be attached to the entry, simply create custom struct that satisfies the RangerEntry interface:

type RangerEntry interface {
	Network() net.IPNet
}

To test whether an IP is contained in the constructed networks ranger:

// returns bool, error
containsBool, err := ranger.Contains(net.ParseIP("192.168.0.1"))

To get a list of CIDR blocks in constructed ranger that contains IP:

// returns []RangerEntry, error
entries, err := ranger.ContainingNetworks(net.ParseIP("192.168.0.1"))

To get a list of all IPv4/IPv6 rangers respectively:

// returns []RangerEntry, error
entries, err := ranger.CoveredNetworks(*AllIPv4)
entries, err := ranger.CoveredNetworks(*AllIPv6)

Index

Constants

This section is empty.

Variables

View Source
var AllIPv4 = parseCIDRUnsafe("0.0.0.0/0")

AllIPv4 is a IPv4 CIDR that contains all networks

View Source
var AllIPv6 = parseCIDRUnsafe("0::0/0")

AllIPv6 is a IPv6 CIDR that contains all networks

View Source
var ErrInvalidNetworkInput = fmt.Errorf("invalid network input")

ErrInvalidNetworkInput is returned upon invalid network input.

View Source
var ErrInvalidNetworkNumberInput = fmt.Errorf("invalid network number input")

ErrInvalidNetworkNumberInput is returned upon invalid network input.

Functions

This section is empty.

Types

type Ranger

type Ranger interface {
	Insert(entry RangerEntry) error
	Remove(network netip.Prefix) (RangerEntry, error)
	Contains(ip netip.Addr) (bool, error)
	ContainingNetworks(ip netip.Addr) ([]RangerEntry, error)
	CoveredNetworks(network netip.Prefix) ([]RangerEntry, error)
	CoveringNetworks(network netip.Prefix) ([]RangerEntry, error)
	Adjacent(network netip.Prefix) (RangerEntry, error)
	Len() int
}

Ranger is an interface for cidr block containment lookups.

func NewPCTrieRanger

func NewPCTrieRanger() Ranger

NewPCTrieRanger returns a versionedRanger that supports both IPv4 and IPv6 using the path compressed trie implemention.

type RangerEntry

type RangerEntry interface {
	Network() netip.Prefix
}

RangerEntry is an interface for insertable entry into a Ranger.

func NewBasicRangerEntry

func NewBasicRangerEntry(ipNet netip.Prefix) RangerEntry

NewBasicRangerEntry returns a basic RangerEntry that only stores the network itself.

Directories

Path Synopsis
Example of how to extend github.com/yl2chen/cidranger
Example of how to extend github.com/yl2chen/cidranger
Package net provides utility functions for working with IPs (net.IP).
Package net provides utility functions for working with IPs (net.IP).

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL