Hi, Bill,
Thanks for your commits!
I have another question is that Tree Bitmap is a patent algorithm from
Cisco. The code is
developed independently with a lot of optimization skills.
I am not sure if I can submit it to an open source community.
Thank you again for reply.
> 在 2016年1月22日，上午7:32，Bill Fischofer <[email protected]> 写道：
>
> The main criteria for introducing new APIs into ODP is twofold:
> Does this represent an area of general interest for dataplane applications?
> Do these functions lend themselves to HW acceleration?
> For the case of IP lookup the answer to both of these questions is clearly
> yes, so on that basis they'd be worthwhile to consider. So I'd encourage you
> to submit your patches. They can be submitted as RFCs if they are incomplete
> and you'd simply like people to be able to review them in more detail to
> provide feedback.
>
> In terms of whether these functions would more naturally reside with ODP or
> with a higher level component like OFP, the acceleration question is key.
> One of the things ODP is designed to do is to provide application portability
> across variant approaches to HW acceleration of key APIs. For example,
> crypto acceleration is a common feature on many SoCs, however each SoC does
> this slightly differently. By having an ODP crypto API these differences can
> be abstracted into a common portable API that can be efficiently mapped to
> many different underlying implementations.
>
> You'd want IP lookup to follow the same model, meaning that the structures
> that are used to hold and search the tables should not be exposed as part of
> the API (since that's an aspect of how one might implement these functions)
> but instead focus on simply defining the functions as the application would
> see and use them. The structures themselves would then become the
> linux-generic SW reference implementation of these APIs, which of course
> could be done differently on platforms that have access to TCAMs or other HW
> features useful for accelerating these functions.
>
> While many ODP applications will want to take advantage of the additional
> capabilities offered by OFP, IP lookup seems to be a lower-level function
> that is needed by switching and routing functions that do not require access
> to a full stack. If OFP itself has various built-in lookup algorithms needed
> for its internal use, then it would be interesting to see if they can be
> folded into lower level ODP APIs that can front-end HW accelerated versions
> of them on different platforms. Again, the key distinction is that ODP is
> the natural place to hold low-level HW abstractions while higher-level
> components like OFP can abstract higher-level functions of interest to a
> wider range of applications.
>
> Bill
>
> On Thu, Jan 21, 2016 at 8:58 AM, Sorin Vultureanu <[email protected]
> <mailto:[email protected]>> wrote:
> Hi,
>
> I think this IP lookup fits better within OpenFastPath Project - OFP.
> www.openfastpath.org <http://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] <mailto:[email protected]>]
> > Sent: Thursday, January 21, 2016 4:40 AM
> > To: LNG ODP Mailman List <[email protected]
> > <mailto:[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] <mailto:[email protected]>
> https://lists.linaro.org/mailman/listinfo/lng-odp
> <https://lists.linaro.org/mailman/listinfo/lng-odp>
>
_______________________________________________
lng-odp mailing list
[email protected]
https://lists.linaro.org/mailman/listinfo/lng-odp
