kingpop / art Goto Github PK
View Code? Open in Web Editor NEWThis project forked from hariguchi/art
Allotment Routing Table
This project forked from hariguchi/art
Allotment Routing Table
ART Allotment Routing Table Yoichi Hariguchi 1. Contents This package includes two ART implementations: o ipArt: supports arbitrary address length and arbitrary stride length distribution. `ipArt' uses simple multibit trie. o ipArt-PC supports arbitrary address length and arbitrary stride length distribution. `ipArt-PC' uses path-compressed trie. `ipArt' and `ipArt-PC' are stored in the same library (libipart.a.) You can choose which one is used when instantiating a routing table. 2. Files Makefile Makefile README This file test.sh Runs addition, longest prefix match, exact match, and deletion tests as follows: 1. Simple trie with 569,770 IPv4 prefixes 2. Path-compressed trie with 569,770 IPv4 prefixes 3. Simple trie with 24,470 IPv6 prefixes 4. Path-compressed trie with 24,470 IPv6 prefixes Types.h Local type definitions ipArt.c An `ipArt' ART implementation (simple trie) ipArtPathComp.c An `ipArt-PC' ART implementation (path-compressed trie) ipArt.h Header file of `ipArt' and `ipArt-PC' util.c utility functions (obsolete) data/ v4routes-random1.txt 569,770 IPv4 prefixes in random order for the route insertion test v4routes-random2.txt 569,770 IPv4 prefixes in random order for the route search test v4routes-random3.txt 569,770 IPv4 prefixes in the random order for the route deletion test v6routes-random1.txt 24,470 IPv6 prefixes in random order for the route insertion and search test v6routes-random2.txt 24,470 IPv6 prefixes in random order for the route deletion and search test Note: v{4,6}routes-random*.txt are created from the Jul 7, 2015 output of 'ip route' and 'ipv6 route' respectively at telnet://route-views.routeviews.org. 3. Installation Type `make' and a test command `rtLoookup' and library `libipart.a' are built. 4. Interactive Simulation - IPv4 simple trie: ./rtLookup 4 simple - IPv4 path-compressed trie: ./rtLookup 4 pc - IPv6 simple trie: ./rtLookup 6 simple - IPv6 path-compressed trie: ./rtLookup 6 pc 5. Data Structures 5.1. rtTable: Routing Table `rtTable' is used to represent a routing table. It is not necessary for users to access the members of `rtTable'. 5.2. routeEnt: Route Entry The definition of `routeEnt' in `ipArt' and `ipArt-PC' is as follows: typedef struct routeEnt { u8 dest[16]; /* upto IPv6 */ int plen; /* prefix length */ int level; /* for performance */ /* * Your stuff */ } routeEnt, *pRouteEnt; `dest' must represent the destination address of the route. `plen' must represent the corresponding prefix length. The destination address must be stored in the network byte order. 6. API functions 6.1. Routing Table Creation rtTable * rtArtInit (int nLevels, s8* psl, int alen, trieType type) @name rtArtInit @brief API Function. Creates and initializes a routing table. Example usage: - IPv4 routing table - The stride lengths are: level 0: 16 bits level 1: 8 bits level 2: 8 bits - Use a path-compressed trie s8 sl[3] = { 16, 8, 8 }; rtTable pt = rtArtInit(3, sl, 32, pathCompTrie) @param[in] nLevels The number of trie node levels (or the number of stride lengths) @param[in] psl Pointer to an array of stride lengths @param[in] alen Bit length of IP addresses (32 or 128) @param[in] type simpleTrie (0) or pathCompTrie (1). @retval rtTable* Pointer to the allocated routing table @retval NULL Failed to allocate a new routing table Hereafter, let the routing table pointer be: rtTable* pt; /* Pointer to the routing table */ 6.2. Memory Allocation for a New Route routeEnt* rtArtNewRoute(rtTable* pt) @brief API function. Allocates memory for a new route entry. @param[in] pt Pointer to the routing table @retval routeEnt* Pointer to the newly allocated route. @retval NULL There was no memory for a new route. 6.3. Insertion routeEnt* pt->insert(rtTable pt, routeEnt* pEnt) @brief API function. Add a route represented by `pEnt' to the routing table `pt' @param[in] pt Pointer to the routing table @param[in] pEnt Pointer to the route added to `pt'. `pEnt' must NOT point to a local variable. @retval routeEnt* `pEnt' is successfully inserted. pEnt There is an existing route that has the same IP prefix (address and prefix length). `pEnt' must be freed in this case. 6.4. Deletion bool pt->delete(rtTable pt, u8* dest, int plen) @brief API function. Deletes a route represented by an IP prefix ( (address and its prefix length) from the routing table. The matched route entry is freed in this function. @param[in] pt Pointer to the routing table @param[in] pDest Pointer to the IP address to be deleted from `pt' @param[in] plen Prefix length associated with `pDest' @retval ture If the matching route is deleted from `pt'. The route entry is freed in this function. @retval false If there is no matching route in `pt'. 6.5. Longest Prefix Match routeEnt* pt->findMatch(rtTable* pt, u8* pDest) @brief API function. Perform the longest prefix match. @param[in] pt Pointer to the routing table @param[in] pDest Pointer to the destination IP address @retval routeEnt* Pointer to the longest prefix matching route. @retval NULL There was no matching route for `pDest' 6.6. Exact Route Match routeEnt * pt->findExactMatch(rtTable* pt, u8* pDest, int plen) @brief API Function. Performs the exact match (address + prefix length.) @param[in] pt Pointer to the routing table @param[in] pDest Pointer to the IP address to be searched for @param[in] plen prefix length of `pDest' @retval routeEnt* Pointer to the found route entry (success) @retval NULL Failed to find a matching route entry 6.7. Delete All Routes pt->flush(rtTable* pt) @brief API Function. Delete all the route entries in the routing table. @param[in] pt Pointer to the routing table 6.8. Delete the Routing Table void pt->deleteTable(rtTable** p) @brief API Function. Delete all the route entries in the routing table, then Free the routing table itself. @param[in,out] p Pointer to the pointer to `rtTable'. `*p' is set to NULL at the end of this function. 7. Notes ART is the default FIB in OpenBSD (>=6.0.) http://www.grenadille.net/post/2016/06/17/ART-single-thread-performances
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.