[dpdk-dev] [RFC] Add RIB library

Vladimir Medvedkin medvedkinv at gmail.com
Tue Aug 15 12:49:28 CEST 2017


The advantage is in increasing control plane operations speed. I tested
with my fullview + internal routes. It had 650030 prefixes(shuffled) with
1000 specific (longer /24) prefixes within 73 /24 networks. Every prefix
had unique next hop. In this test the speed of inserting new routes was
increased 70 times against current LPM. This was achieved due to
1. keeping routes in a trie structure instead of array (no need to get free
room for rule)
2. avoid unnecessary reads in tbl24 (checking for .depth). Thanks to
rte_rib_v4_get_next_child() (that is reverse order traversal without
recursion) you can get all more specific prefixes inside your target prefix
(you want to add/del), so you can get all ranges between that more
specifics and write next hop unconditionally to tbl24 and tbl8.

2017-08-15 11:23 GMT+03:00 Bruce Richardson <bruce.richardson at intel.com>:

> On Tue, Aug 15, 2017 at 01:28:26AM +0300, Vladimir Medvedkin wrote:
> > 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).
> >
> >
> What is the advantage of using the rte_rib for control plane access over
> the existing rules table structure. Are not the basic operations needed
> for adding/removing/looking-up rules supported by both?
>
> /Bruce
>



-- 
Regards,
Vladimir


More information about the dev mailing list