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!)
... but the library is ready to use, comments and PR welcome.
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]) String() string
func (t *Table[V]) Fprint(w io.Writer) error
func (t *Table[V]) Dump(w io.Writer)
TODO
- try a simplest implementation with a hashmap for level compression (done, see branch hashmap)
- try multi level strides
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 Table
- func (t *Table[V]) Delete(pfx netip.Prefix)
- func (t *Table[V]) Dump(w io.Writer) error
- 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]) String() string
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
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]) Dump ¶
Dump the IPv4 and IPv6 tables to w. Needed during development and debugging, especially for the hierarchical tree in the String method, OMG. Will be removed when the API stabilizes.
Output: [FULL] depth: 0 path: [] / 0 indexs(#6): 1 66 128 133 266 383 prefxs(#6): 0/0 8/6 0/7 10/7 10/8 127/8 childs(#3): 10 127 192 .[IMED] depth: 1 path: [10] / 8 .childs(#1): 0 ..[LEAF] depth: 2 path: [10.0] / 16 ..indexs(#2): 256 257 ..prefxs(#2): 0/8 1/8 .[IMED] depth: 1 path: [127] / 8 .childs(#1): 0 ..[IMED] depth: 2 path: [127.0] / 16 ..childs(#1): 0 ...[LEAF] depth: 3 path: [127.0.0] / 24 ...indexs(#1): 257 ...prefxs(#1): 1/8
...
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 addr 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 addr 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"
)
func mustAddr(s string) netip.Addr {
return netip.MustParseAddr(s)
}
func mustPfx(s string) netip.Prefix {
return netip.MustParsePrefix(s)
}
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{mustPfx("fe80::/10"), mustAddr("::1%lo")},
{mustPfx("172.16.0.0/12"), mustAddr("8.8.8.8")},
{mustPfx("10.0.0.0/24"), mustAddr("8.8.8.8")},
{mustPfx("::1/128"), mustAddr("::1%eth0")},
{mustPfx("192.168.0.0/16"), mustAddr("9.9.9.9")},
{mustPfx("10.0.0.0/8"), mustAddr("9.9.9.9")},
{mustPfx("::/0"), mustAddr("2001:db8::1")},
{mustPfx("10.0.1.0/24"), mustAddr("10.0.0.0")},
{mustPfx("169.254.0.0/16"), mustAddr("10.0.0.0")},
{mustPfx("2000::/3"), mustAddr("2001:db8::1")},
{mustPfx("2001:db8::/32"), mustAddr("2001:db8::1")},
{mustPfx("127.0.0.0/8"), mustAddr("127.0.0.1")},
{mustPfx("127.0.0.1/32"), mustAddr("127.0.0.1")},
{mustPfx("192.168.1.0/24"), mustAddr("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 := mustAddr("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 = mustAddr("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 = mustAddr("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]) String ¶
String returns a hierarchical tree diagram of the ordered CIDRs as string, just a wrapper for Table.Fprint.
Source Files