From 7f00a19d0cc487d4dc2da05315669e8e80b790cc Mon Sep 17 00:00:00 2001 From: Martin Pieuchot Date: Thu, 20 Aug 2015 12:39:44 +0000 Subject: 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@ --- sys/net/route.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'sys/net/route.c') diff --git a/sys/net/route.c b/sys/net/route.c index c8d75fee77e..56adb555ec9 100644 --- a/sys/net/route.c +++ b/sys/net/route.c @@ -1,4 +1,4 @@ -/* $OpenBSD: route.c,v 1.223 2015/08/19 13:27:38 bluhm Exp $ */ +/* $OpenBSD: route.c,v 1.224 2015/08/20 12:39:43 mpi Exp $ */ /* $NetBSD: route.c,v 1.14 1996/02/13 22:00:46 christos Exp $ */ /* @@ -1238,6 +1238,7 @@ rt_ifa_del(struct ifaddr *ifa, int flags, struct sockaddr *dst) } if ((rt = rtalloc(dst, 0, rtableid)) != NULL) { rt->rt_refcnt--; +#ifndef ART /* try to find the right route */ while (rt && rt->rt_ifa != ifa) rt = (struct rtentry *) @@ -1248,6 +1249,7 @@ rt_ifa_del(struct ifaddr *ifa, int flags, struct sockaddr *dst) return (flags & RTF_HOST ? EHOSTUNREACH : ENETUNREACH); } +#endif } memset(&info, 0, sizeof(info)); -- cgit v1.2.3