README
¶
package bart
package bart provides a Balanced-Routing-Table (BART).
BART is balanced in terms of memory consumption versus lookup time.
The lookup time is by a factor of <1.5 slower on average as the routing algorithms ART, SMART, CPE, ... but reduces the memory consumption by an order of magnitude in comparison.
BART is a multibit-trie, using the 'baseIndex' function from the ART algorithm to build the complete binary prefix tree (CBT) for each stride.
The second key factor is popcount level compression and backtracking along the CBT prefix tree in O(k).
The CBT is implemented as a bitvector, backtracking is just a matter of fast cache friendly bitmask operations.
Due to the cache locality of the popcount compressed CBT, the backtracking algorithm is as fast as possible.
API (not stable!)
... still under development, but the library is ready to use.
import "github.com/gaissmai/bart"
type Table[V any] struct {
// Has unexported fields.
}
Table is an IPv4 and IPv6 routing table with payload V. The zero value is
ready to use.
func (t *Table[V]) Insert(pfx netip.Prefix, val V)
func (t *Table[V]) Delete(pfx netip.Prefix)
func (t *Table[V]) Get(ip netip.Addr) (val V, ok bool)
func (t *Table[V]) Lookup(ip netip.Addr) (lpm netip.Prefix, val V, ok bool)
func (t *Table[V]) LookupShortest(ip netip.Addr) (spm netip.Prefix, val V, ok bool)
func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool
func (t *Table[V]) String() string
func (t *Table[V]) Fprint(w io.Writer) error
func (t *Table[V]) DumpList(is4 bool) []DumpListNode[V]
func (t *Table[V]) MarshalJSON() ([]byte, error)
func (t *Table[V]) MarshalText() ([]byte, error)
TODO
- implement Overlaps ...
CONTRIBUTION
Please open an issue for discussion before sending a pull request.
CREDIT
Credits for many inspirations go to the clever guys at tailscale, to Daniel Lemire for the super-fast bitset package and to Donald E. Knuth for the ART routing algorithm and all the rest of his Art and for keeping important algorithms in the public domain!
LICENSE
MIT
Documentation
¶
Index ¶
- type DumpListNode
- type Table
- func (t *Table[V]) Delete(pfx netip.Prefix)
- func (t *Table[V]) DumpList(is4 bool) []DumpListNode[V]
- func (t *Table[V]) Fprint(w io.Writer) error
- func (t *Table[V]) Get(ip netip.Addr) (val V, ok bool)
- func (t *Table[V]) Insert(pfx netip.Prefix, val V)
- func (t *Table[V]) Lookup(ip netip.Addr) (lpm netip.Prefix, val V, ok bool)
- func (t *Table[V]) LookupShortest(ip netip.Addr) (spm netip.Prefix, val V, ok bool)
- func (t *Table[V]) MarshalJSON() ([]byte, error)
- func (t *Table[V]) MarshalText() ([]byte, error)
- func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool
- func (t *Table[V]) String() string
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DumpListNode ¶ added in v0.1.6
type DumpListNode[V any] struct { CIDR netip.Prefix `json:"cidr"` Value V `json:"value"` Subnets []DumpListNode[V] `json:"subnets,omitempty"` }
DumpListNode contains CIDR, value and list of subnets (tree childrens).
type Table ¶
type Table[V any] struct { // contains filtered or unexported fields }
Table is an IPv4 and IPv6 routing table with payload V. The zero value is ready to use.
func (*Table[V]) DumpList ¶ added in v0.1.6
func (t *Table[V]) DumpList(is4 bool) []DumpListNode[V]
DumpList dumps ipv4 or ipv6 tree into list of roots and their subnets. It can be used to analyze tree or build custom json representation.
func (*Table[V]) Fprint ¶
Fprint writes a hierarchical tree diagram of the ordered CIDRs to w. If w is nil, Fprint panics.
The order from top to bottom is in ascending order of the prefix address and the subtree structure is determined by the CIDRs coverage.
▼ ├─ 10.0.0.0/8 (9.9.9.9) │ ├─ 10.0.0.0/24 (8.8.8.8) │ └─ 10.0.1.0/24 (10.0.0.0) ├─ 127.0.0.0/8 (127.0.0.1) │ └─ 127.0.0.1/32 (127.0.0.1) ├─ 169.254.0.0/16 (10.0.0.0) ├─ 172.16.0.0/12 (8.8.8.8) └─ 192.168.0.0/16 (9.9.9.9) └─ 192.168.1.0/24 (127.0.0.1) ▼ └─ ::/0 (2001:db8::1) ├─ ::1/128 (::1%eth0) ├─ 2000::/3 (2001:db8::1) │ └─ 2001:db8::/32 (2001:db8::1) └─ fe80::/10 (::1%lo)
func (*Table[V]) Get ¶
Get does a route lookup for IP and returns the associated value and true, or false if no route matched.
func (*Table[V]) Insert ¶
Insert adds pfx to the tree, with value val. If pfx is already present in the tree, its value is set to val.
func (*Table[V]) Lookup ¶
Lookup does a route lookup for IP and returns the longest prefix, the associated value and true for success, or false otherwise if no route matched.
Lookup is a bit slower than Get, so if you only need the payload V and not the matching longest-prefix back, you should use just Get.
Example ¶
package main
import (
"fmt"
"net/netip"
"os"
"github.com/gaissmai/bart"
)
var (
a = netip.MustParseAddr
p = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{p("fe80::/10"), a("::1%lo")},
{p("172.16.0.0/12"), a("8.8.8.8")},
{p("10.0.0.0/24"), a("8.8.8.8")},
{p("::1/128"), a("::1%eth0")},
{p("192.168.0.0/16"), a("9.9.9.9")},
{p("10.0.0.0/8"), a("9.9.9.9")},
{p("::/0"), a("2001:db8::1")},
{p("10.0.1.0/24"), a("10.0.0.0")},
{p("169.254.0.0/16"), a("10.0.0.0")},
{p("2000::/3"), a("2001:db8::1")},
{p("2001:db8::/32"), a("2001:db8::1")},
{p("127.0.0.0/8"), a("127.0.0.1")},
{p("127.0.0.1/32"), a("127.0.0.1")},
{p("192.168.1.0/24"), a("127.0.0.1")},
}
func main() {
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
rtbl.Insert(item.cidr, item.nextHop)
}
rtbl.Fprint(os.Stdout)
fmt.Println()
ip := a("42.0.0.0")
lpm, value, ok := rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v lpm: %-15v value: %11v, ok: %v\n", ip, lpm, value, ok)
ip = a("10.0.1.17")
lpm, value, ok = rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v lpm: %-15v value: %11v, ok: %v\n", ip, lpm, value, ok)
ip = a("2001:7c0:3100:1::111")
lpm, value, ok = rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v lpm: %-15v value: %11v, ok: %v\n", ip, lpm, value, ok)
}
Output: ▼ ├─ 10.0.0.0/8 (9.9.9.9) │ ├─ 10.0.0.0/24 (8.8.8.8) │ └─ 10.0.1.0/24 (10.0.0.0) ├─ 127.0.0.0/8 (127.0.0.1) │ └─ 127.0.0.1/32 (127.0.0.1) ├─ 169.254.0.0/16 (10.0.0.0) ├─ 172.16.0.0/12 (8.8.8.8) └─ 192.168.0.0/16 (9.9.9.9) └─ 192.168.1.0/24 (127.0.0.1) ▼ └─ ::/0 (2001:db8::1) ├─ ::1/128 (::1%eth0) ├─ 2000::/3 (2001:db8::1) │ └─ 2001:db8::/32 (2001:db8::1) └─ fe80::/10 (::1%lo) Lookup: 42.0.0.0 lpm: invalid Prefix value: invalid IP, ok: false Lookup: 10.0.1.17 lpm: 10.0.1.0/24 value: 10.0.0.0, ok: true Lookup: 2001:7c0:3100:1::111 lpm: 2000::/3 value: 2001:db8::1, ok: true
func (*Table[V]) LookupShortest ¶ added in v0.1.4
LookupShortest does a route lookup for IP and returns the shortest matching prefix, the associated value and true for success, or false otherwise if no route matched.
It is, so to speak, the opposite of lookup and is only required for very special cases.
func (*Table[V]) MarshalJSON ¶ added in v0.1.6
MarshalJSON dumps table into two sorted lists: for ipv4 and ipv6. Every root and subnet are array, not map, because the order matters.
func (*Table[V]) MarshalText ¶ added in v0.1.5
MarshalText implements the encoding.TextMarshaler interface, just a wrapper for Table.Fprint.
func (*Table[V]) OverlapsPrefix ¶ added in v0.1.5
OverlapsPrefix reports whether any IP in pfx matches a route in the table.
func (*Table[V]) String ¶
String returns a hierarchical tree diagram of the ordered CIDRs as string, just a wrapper for Table.Fprint. If Fprint returns an error, String panics.
Source Files