Add radix trie to HashMapDb for fast IP LPM 29/40129/5
authorFlorin Coras <fcoras@cisco.com>
Fri, 3 Jun 2016 07:37:31 +0000 (10:37 +0300)
committerFlorin Coras <fcoras@cisco.com>
Fri, 17 Jun 2016 21:47:54 +0000 (23:47 +0200)
commitab93b0a494019299f423ca936132608d0ea71f3a
tree7f13a34c272a79a6033a38e8572af92e982ab324
parentdf254de41030589506a30a57a37518bf7076ae94
Add radix trie to HashMapDb for fast IP LPM

This adds a radix trie implementation for fast IP longest prefix
matching leveraged for now in HashMapDb to speed up mappings lookup. The
change is not fully transparent as it introduces a number of ILispDAO
API and map-cache implementation updates.

An important caveat to consider is that authkey lookup logic in map-caches
cannot be changed to use the tries because keys are not always found
under the longest prefix match. This is a consequence of the fact that
we now accept generic auth keys for aggregate prefixes, i.e., we don't
have one-to-one matching between mapping and auth entries, and we store
both auth keys and mappings in the same map-cache.

Change-Id: I4e7d2badce3b3cd31030fbea87f7366ea6b41035
Signed-off-by: Florin Coras <fcoras@cisco.com>
18 files changed:
mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/dao/ILispDAO.java
mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/IMapCache.java
mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/IMappingSystem.java
mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mappingservice/IMappingService.java
mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingService.java
mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingSystem.java
mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/lisp/MapResolver.java
mappingservice/implementation/src/test/java/org/opendaylight/lispflowmapping/implementation/lisp/MapResolverTest.java
mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java
mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/radixtrie/RadixTrie.java [new file with mode: 0644]
mappingservice/inmemorydb/src/test/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDbTest.java
mappingservice/inmemorydb/src/test/java/org/opendaylight/lispflowmapping/inmemorydb/radixtrie/RadixTrieTest.java [new file with mode: 0644]
mappingservice/lisp-proto/src/main/java/org/opendaylight/lispflowmapping/lisp/util/LispAddressUtil.java
mappingservice/mapcache/src/main/java/org/opendaylight/lispflowmapping/mapcache/FlatMapCache.java
mappingservice/mapcache/src/main/java/org/opendaylight/lispflowmapping/mapcache/MultiTableMapCache.java
mappingservice/mapcache/src/main/java/org/opendaylight/lispflowmapping/mapcache/SimpleMapCache.java
mappingservice/mapcache/src/test/java/org/opendaylight/lispflowmapping/mapcache/MultiTableMapCacheTest.java
mappingservice/mapcache/src/test/java/org/opendaylight/lispflowmapping/mapcache/SimpleMapCacheTest.java