On Thu, 30 Mar 2000, Jarno Lahteenmaki wrote:
> > Linux has a routing cache that caches routing table lookups. This
> > is called the destination cache. A destination cache entry is tied
> > to a specific destination, which means only a single neighbour
> > on a multipath route. To use multipath routing for load balancing
> > requires dropping the destination entry after every use, so that
> > another neighbour in the multipath could be looked up (the destination
> > cache knows nothing about multipaths, that is all encapsulated in the
> > FIB or routing table)
It must be even worse than that because to balance, I must be assured that
when I drop a route from the cache, the next lookup of that destination
gets the other route. I mean, if I simply scan the routing table and find
a route, what prevents me from finding the same route the next time I scan
the table? Doesn't the route I found last time need to be moved to the end
of the table so I find the alternative route the next time? Or does it
shomehow remember which route it found last time and skips it to search
for the other?
Maybe a way to do it is not to cache routes, but cache destinations that
point to a list of routes to that destination. In other words, instead of
a cache of destinations pointing to next hops, you have a cache of
destinations pointing to lists of potential next hops. Each route has a
current weight and "use factor". Two equal routes might start with a
weight of 0 and a factor of 1. Add the factor to the weight of each route
in the list and select either the highest weight or the last one if
weights are equal. Set the weight of the route you just used to 0.
This works for more than three routes too.
route 1 = 0
route 2 = 0
route 3 = 0
After first pass:
route 1 = 1
route 2 = 1
route 3 = 0
All routes were 1 after adding 1 so I selected the last one ... route 3
and then set it to 0.
Next pass:
route 1 = 2
route 2 = 0
route 3 = 1
Routes 1 and 2 were both 2 after adding 1 so I picked route 2.
Nest pass:
route 1 = 0
route 2 = 1
route 3 = 2
Picked route 1, route 3 will be next, then route 2 then route 1 again.
It works for asyemtrical routes too.
Imagine three routes start at 0. Two have a factor of 1, one has a factor
of 2.
First pass:
r1 = 1
r2 = 1
r3 = 0
r3 was at a weight of 2 so it was picked.
r1 = 2
r2 = 2
r3 = 0
r3 was equal to the others and the last one so it was chosen again.
one-time glitch.
Next pass
r1 = 3
r2 = 0
r3 = 2
r2 chosen ... last route at weight of 3.
r1 = 4
r2 = 1
r3 = 0
r3 chosen ... last route at 4
r1 = 0
r2 = 3
r3 = 2
r1 chosen.
r1 = 1
r2 = 4
r3 = 0
r3 chosen
Looks like .... r3, r3, r2, r3, r1, r3, r2, r3, r1, r3
SO you have a list that includes the next hop, current weight, and
weighting factor that is the ratio of the relative weights of the routes.
Add the weighting factor, take the last highest route and set it to 0
after use and do it over again.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Fri Mar 31 2000 - 21:00:26 EST