CVSROOT: /cvs
Module name: src
Changes by: m...@cvs.openbsd.org 2015/08/20 06:39:43
Modified files:
sys/net : route.c route.h rtable.c rtable.h
Added files:
sys/net : art.c art.h
Log message:
Import an alternative routing table backend based on Yoichi Hariguchi's
ART implementation.
ART (Allotment Routing Table) is a multibit-trie algorithm invented by
D. Knuth while reviewing Yoichi's SMART [0] (Smart Multi-Array Routing
Table) paper.
This implementation, unlike the one from the KAME project, supports
variable stride lengths which makes it easier to adapt the consumed
memory/speed trade-off. It also let you use a bigger first-level
table, what other algorithms such as POPTRIE [1] need to implement
separately.
Adaptation to the OpenBSD kernel has been done with two different data
structures. ART nodes and route entries are managed separately which
makes the algorithm implementation free of any MULTIPATH logic.
This implementation does not include Path Compression.
[0] http://www.hariguchi.org/art/smart.pdf
[1] http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p57.pdf
ok dlg@, reyk@
