Messages in this thread | | | Date | Thu, 30 Mar 2000 01:46:58 -0800 (PST) | From | George Bonser <> | Subject | Re: iproute and 2.3 question |
| |
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/
| |