Hi, I think this IP lookup fits better within OpenFastPath Project - OFP. www.openfastpath.org
OFP has DIR 1688 (lockless, multicore with linear scalability, very low overhead) and Radix Tree(read/write locks). TBM algorithm and Front-End /Back-End architecture are interesting for OFP project L3 forwarding functionality, but we might need to check some details to see if it fits: - multicore, hopefully lockless - the front-end should be available in ODP shared memory - an API between Front-End and Back-End, so that we can have it as SPMC on the shared memory. - ... Can you share more light into these details? It would be great if you can contribute/integrate this as patches to OFP. Kind Regards, Sorin > -----Original Message----- > From: HePeng [mailto:[email protected]] > Sent: Thursday, January 21, 2016 4:40 AM > To: LNG ODP Mailman List <[email protected]> > Subject: [lng-odp] Contribute IP lookup code to ODP > > Hi, > I plan to submit an IP lookup code to ODP. However, this code is a little > bit > complex. > So I am here asking for some suggestions. (Please view this email using the > monospaced font.) > > The code is actually an IP lookup architecture, including a "backend" of > all > IP lookup algorithms and the "frontend" for each IP lookup algorithm. I > made this design because normally the data structure for IP lookup is usually > highly optimized, compressed, containing minimall information for fast > lookup. However, a full functional IP lookup engine should support many > extra functions rather than just lookup (prefix exist, print all prefix, > ...). One > way to do this is to design a "control plane" (large data structure containing > most of query information and can help to incremental update the lookup > tree in "dataplane") to do this. The control plane is the backend, while the > highly optimized data structure is the dataplane, the front end. > > > +------+ +-----+ +-----+ > | 1688 | --> | lib | <-- | TBM | > +------+ +-----+ +-----+ > > > So the code includes a lib/ for backend, and two algorithms in total > (Tree > Bitmap (TBM) and DIR-16-8-8). > I am now finishing the lib/ and TBM. I am not sure is that: > > 1. Is ODP community willing to accept this? or you guys just want a very > simple implementation? > 2. Should this code including the IP lookup APIs go to helper/ or main > thread? > > > I've tested the code using 350K prefixes from the core router's FIB. The > backend uses 11MB memory and the front end uses 5MB memory. The TBM > algorithms achieves 25MLPS (million lookups for second, 16.9Gbps for 64B > packets) on Intel(R) Xeon(R) CPU E5-2609 0 @ 2.40GHz CPU and a very low > locality trace dedicated for the FIB. On Random traffic, the code achieves > 55MLPS. > > Thanks. > > > _______________________________________________ lng-odp mailing list [email protected] https://lists.linaro.org/mailman/listinfo/lng-odp
