Hi, Sorin,
Thanks for your comments!
I did some code investigation on your DIR 1688 and OFP project.
I guess currently the IP lookup code in OFP is complete. OFP seems to have
already the backend and
front-end together, I have seen the code for DIR1688 and also the code for a
binary trie.
The responses list below：
> 在 2016年1月21日，下午10:58，Sorin Vultureanu <sorin.vulture...@enea.com> 写道：
>
> 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
I have not yet consider the lock issues, will consider it in the code
> - the front-end should be available in ODP shared memory
Now the back-end and front-end has their own memory management
sub-system.
To submit the code, I need to change it to use ODP memory management
system.
> - an API between Front-End and Back-End, so that we can have it as SPMC
> on the shared memory.
The back-end is also a trie, it provides:
*Print all the prefixes;
*Test if a prefix exist;
*Detect if a prefix overlaps with an existing prefix,
and the length of the existing prefix is smaller than a pre-set length;
This is useful for prefix delete in many multi-trie algorithms.
*Traverse all the prefixes;
> - ...
>
> 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:xnhp0...@icloud.com]
>> Sent: Thursday, January 21, 2016 4:40 AM
>> To: LNG ODP Mailman List <lng-odp@lists.linaro.org>
>> 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
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp
