Subject: works in progress: route cache invalidation, RADIX_MPATH
To: None <>
From: David Young <>
List: tech-net
Date: 11/16/2006 13:33:30
Patches for two networking features I have in progress are at
<>.  The first
feature is route-cache invalidation.  The second feature is RADIX_MPATH,
the multipath routing patches from KAME, with many of my own improvements.
Sorry the patches for both features are intermingled---anybody know a
good patch editor?

* Route-cache invalidation

        BSD uses struct route to cache the results of forwarding-table
        lookups.  BSD embeds struct route in PCBs, in the table of IP
        flows, in the IP forwarding cache (ipforward_rt), et cetera.
        The ro_rt member caches the results of forwarding-table lookups.
        BSD neither changes nor invalidates the caches when the forwarding
        table changes, and that leads the kernel to use a stale cache,
        which leads to broken routing.  See kern/3508 for an example of
        broken routing whose underlying cause is a stale cache.

        My patch adds callbacks to 'struct domain' both for invalidating
        a particular route cache (dom_rtflush), for adding a particular
        route cache to the set of active caches (dom_rtcache), and for
        invalidating all caches in the routing domain (dom_rtflushall).
        I provide helper routines rtcache(struct route *), rtflush(struct
        route *), and rtflushall(int family) for invoking the callbacks.
        I add a couple of calls to rtflushall() in rtrequest1().

        My patch only treats IPv4, but IPv6 and other networking domains
        deserve similar treatment.

        Christoph Badura discouraged me from my original plan for
        invalidating the route caches, and set me on the path of chaining
        all of the struct routes together, which ultimately proved a
        lot easier than what I'd planned.  Thanks, Christoph!

        Beware, I have only just begun to test these patches.  There may
        be serious bugs.


        The second feature is the RADIX_MPATH patches from KAME, with
        significant modifications by me.  RADIX_MPATH implements multipath
        routing according to "Modulo-N Hash," described in RFC2991.
        Beware: I have not run compiled or run my RADIX_MPATH patches
        in a long time.  I know there are bugs that cause crashes.

        My mods make RADIX_MPATH work sensibly in the event that you
        can reach the same destination both directly (i.e., it's on the
        same link), and through an IP router---this is not the least
        bit unusual on a wireless multihop network.

        I encapsulate each route's preferability in a macro,
        RADIX_MPATH_PREFERENCE().  Routes with greater preference
        numbers are chosen with greater likelihood.  Right now,
        RADIX_MPATH_PREFERENCE() always evaluates to 1.

        I also add a "wireless heuristic" to the code that selects
        nexthops: if a destination is on the same link, but there is
        a route through an IP router, the heuristic chooses the latter
        route.  The assumption is that a routing daemon has added the
        longer path, knowing full well what it is doing! :-) This is
        a pretty reasonable assumption in practice, but we need the
        capability to turn the heuristic on and off.

* Et cetera

        I retired a workaround in gif(4) for the old route-caching

        I removed gre(4)'s ability to configure the same remote inner
        IP as remote outer IP, per prior discussions on tech-net.

        I made many cosmetic changes throughout the networking stacks.


David Young             OJC Technologies      Urbana, IL * (217) 278-3933