IPRouteTable

IPRouteTable Element Documentation

NAME

IPRouteTable — Click element; IP routing table superclass

SYNOPSIS

IPRouteTable

DESCRIPTION

IPRouteTable defines an interface useful for implementing IPv4 route lookup elements. It parses configuration strings -- see LinearIPLookup for an example -- and calls virtual functions to add the resulting routes. A default push function uses those virtual functions to look up routes and output packets accordingly. There are also some functions useful for implementing handlers.

PERFORMANCE

Click provides several elements that implement all or part of the IPRouteTable interface. Marko Zec has compared their performance, in terms of lookup speed and memory size, for full BGP feeds; here are the results.

Methodology: 2.8GHz Pentium P4 CPU, 521K L2 cache, FreeBSD 4.10, userspace Click. RangeIPLookup has two lookup tables, the larger of which is used only at update time. The "warm cache" numbers perform the same lookup several times in a loop to populate the cache; only the last lookup's performance is reported.

              ICSI BGP dump, 150700 routes, 2 next-hops
 
         Element      | cycles  | lookups | setup | lookup
                      | /lookup | /sec    | time  | tbl. size
     -----------------+---------+---------+-------+----------------
     RadixIPLookup    |   1025  |  2.73M  | 0.59s |  5.8 MB
     DirectIPLookup   |    432  |  6.48M  | 0.74s | 33   MB
     RangeIPLookup    |    279  | 10.0 M  | 0.83s |  0.21MB (+33MB)
       " (warm cache) |     44  | 63.6 M  |   "   |    "       "
 
           routeviews.org dump, 167000 routes, 52 nexthops
 
         Element      | cycles  | lookups | setup | lookup
                      | /lookup | /sec    | time  | tbl. size
     -----------------+---------+---------+-------+----------------
     RadixIPLookup    |   1095  |  2.55M  | 0.67s |  6.6 MB
     DirectIPLookup   |    434  |  6.45M  | 0.77s | 33   MB
     RangeIPLookup    |    508  |  5.51M  | 0.88s |  0.51MB (+33MB)
       " (warm cache) |     61  | 45.9 M  |   "   |    "       "

The RadixIPLookup, DirectIPLookup, and RangeIPLookup elements are well suited for implementing large tables. We also provide the LinearIPLookup, StaticIPLookup, and SortedIPLookup elements; they are simple, but their O(N) lookup speed is orders of magnitude slower. RadixIPLookup or DirectIPLookup should be preferred for almost all purposes.

           1500-entry fraction of the ICSI BGP dump
 
         Method     | cycles  | lookups | setup | lookup
                    | /lookup | /sec    | time  | tbl. size
     ---------------+---------+---------+-------+----------
     LinearIPLookup |  12000  |  233K   |  10s  |   29 KB
     StaticIPLookup |  12000  |  233K   |  10s  |   29 KB
     SortedIPLookup |  12500  |  224K   |  38s  |   29 KB

A Click script containing the 167000-route dump is available at https://github.com/kohler/click/wiki/files/routetabletest-167k.click.gz

INTERFACE

These four IPRouteTable virtual functions should generally be overridden by particular routing table elements.

• int add_route(const IPRoute& r, bool set, IPRoute* old_route, ErrorHandler *errh)

  Add a route sending packets with destination addresses matching r.addr/r.mask to gateway r.gw, via output port r.port. If a route for this exact prefix already exists, then the behavior depends on set. If set is true, then any existing route is silently overwritten (after possibly being stored in *old_route); if set is false, the function should return -EEXIST. Report errors to errh. Should return 0 on success and negative on failure. The default implementation reports an error "cannot add routes to this routing table".

• int remove_route(const IPRoute& r, IPRoute* old_route, ErrorHandler *errh)

  Removes the route sending packets with destination addresses matching r.addr/r.mask to gateway r.gw, via the element's output port r.port. All four fields must match, unless r.port is less than 0, in which case only r.addr/r.mask must match. If no route for that prefix exists, the function should return -ENOENT; otherwise, the old route should be stored in *old_route (assuming it's not null). Any errors are reported to errh. Should return 0 on success and negative on failure. The default implementation reports an error "cannot delete routes from this routing table".

• int lookup_route(IPAddress dst, IPAddress &gw_return) const

  Looks up the route associated with address dst. Should set gw_return to the resulting gateway and return the relevant output port (or negative if there is no route). The default implementation returns -1.

• String dump_routes() — Returns a textual description of the current routing table. The default implementation returns an empty string.

The following functions, overridden by IPRouteTable, are available for use by subclasses.

• int configure(Vector\xFFString> &conf, ErrorHandler *)

  The default implementation of configure parses conf as a list of routes, where each route is the space-separated list `address/mask [gateway] output'. The routes are successively added to the element with add_route.

• void push(int port, Packet *p) — The default implementation of push uses lookup_route to perform IP routing lookup. Normally, subclasses implement their own push methods, avoiding virtual function call overhead.

• static int add_route_handler(const String &, Element *, void *, ErrorHandler *)

  This write handler callback parses its input as an add-route request and calls add_route with the results. Normally hooked up to the `add' handler.

• static int remove_route_handler(const String &, Element *, void *, ErrorHandler *)

  This write handler callback parses its input as a remove-route request and calls remove_route with the results. Normally hooked up to the `remove' handler.

• static int ctrl_handler(const String &, Element *, void *, ErrorHandler *)

  This write handler callback function parses its input as a route control request and calls add_route or remove_route as directed. Normally hooked up to the `ctrl' handler.

• static String table_handler(Element *, void *)

  This read handler callback function returns the element's routing table via the dump_routes function. Normally hooked up to the `table' handler.

SEE ALSO

RadixIPLookup, DirectIPLookup, RangeIPLookup, StaticIPLookup, LinearIPLookup, SortedIPLookup, LinuxIPLookup

Generated by click-elem2man from ../elements/ip/iproutetable.hh:8 on 2017/10/17.