[dpdk-dev] [RFC] Add RIB library
Vladimir Medvedkin
medvedkinv at gmail.com
Tue Aug 15 00:28:26 CEST 2017
2017-08-14 13:51 GMT+03:00 Bruce Richardson <bruce.richardson at intel.com>:
> On Tue, Jul 11, 2017 at 07:33:04PM +0000, Medvedkin Vladimir wrote:
> > Hi,
> >
> > I want to introduce new library for ip routing lookup that have some
> advantages
> > over current LPM library. In short:
> > - Increases the speed of control plane operations against lpm such
> as
> > adding/deleting routes
> > - Adds abstraction from dataplane algorythms, so it is possible to
> add
> > different ip route lookup algorythms such as
> DXR/poptrie/lpc-trie/etc
> > in addition to current dir24_8
> > - It is possible to keep user defined application specific
> additional
> > information in struct rte_rib_v4_node which represents route
> entry.
> > It can be next hop/set of next hops (i.e. active and feasible),
> > pointers to link rte_rib_v4_node based on some criteria (i.e.
> next_hop),
> > plenty of additional control plane information.
> > - For dir24_8 implementation it is possible to remove
> rte_lpm_tbl_entry.depth
> > field that helps to save 6 bits.
> > - Also new dir24_8 implementation supports different next_hop sizes
> > (1/2/4/8 bytes per next hop)
> >
> > It would be nice to hear your opinion. The draft is below.
> >
> > Medvedkin Vladimir (1):
> > lib/rib: Add Routing Information Base library
> >
>
> On reading this patch and then having discussion with you offline, it
> appears there are two major new elements in this patchset:
>
> 1. a re-implementation of LPM, with the major advantage of having a
> flexible data-size
> 2. a separate control plane structure that is designed to fit on top off
> possibly multiple lookup structures for the data plane
>
> Is this correct?
>
Correct
>
> For the first part, I don't think we should carry about two separate LPM
> implementations, but rather look to take the improvements in your
> version back into the existing lib. [Or else replace the existing one,
> but I prefer pulling the new stuff into it, so as to keep backward
> compatibility]
>
> For the second part, perhaps you could expand a bit more on the thought
> here, and explain what all different data plane implementations would
> fit under it. Would, for instance a hash-lookup work? In that case, what
> would the data plane APIs be, and the control plane ones.
>
I'm not sure for _all_ data plane implementations, but from my point of
view compressed prefix trie (rte_rib structure) could be useful at least
for dir24_8, dxr, bitmap handling. Concerning to hash lookup, it depends on
algorithm (array of hash tables indexed by mask length, unrolling prefix to
number of /32).
Perhaps it is better to waive the abstraction and make LPM as primary
struct that keeps rte_rib inside (instead of rules_tbl[ ]).
In that case rte_rib becomes side structure and it's API only for working
with a trie. LPM's API remains the same (except next_hop size and LPM
creation).
> Thanks,
> /Bruce
>
--
Regards,
Vladimir
More information about the dev
mailing list