Bugzilla – Bug 74
Redundant routing table lookup for setting src addr of outoging IP packets
Last modified: 2009-05-29 17:27:56 EDT
The problem and possible solution is described in the first point in http://mailman.isi.edu/pipermail/ns-developers/2007-September/003348.html I proposed to make the Ipv4RoutingProtocol responsible for setting the source address in Ipv4Header when it is 0.0.0.0. Tom proposed: """ I agree that we now have redundant searches in the routing tables, once in UDP and once in IP. I think the crux of the problem is already described in this comment in Ipv4L3Protocol::Send() // XXX Note here that in most ipv4 stacks in the world, // the route calculation for an outgoing packet is not // done in the ip layer. It is done within the application // socket when the first packet is sent to avoid this // costly lookup on a per-packet basis. // That would require us to get the route from the packet, // most likely with a packet tag. The higher layers do not // do this yet for us. I would suggest to perhaps fix along the lines suggested in this comment, because otherwise, if I understand correctly, the source address is incorrectly set down to the IP layer which can cause checksum issues when checksums are enabled. """ To which my reply would be, this technique won't work very well for very dynamic adhoc routing protocols, because this way you store the route in the socket based on the route discovered for the first packet sent, but then you never change it ever again, even if the underlying routing protocol discovers a new better route or the old one simply becomes invalid. IMHO it's better to keep it as it is, always go through the routing protocol. If we really want to speed up things along those lines it should be possible, for example let the Ipv4RoutingProtocol::RequestRoute receive an extra optional parameter containing the last route found, which would be stored in the socket as the source comment suggests. But in this case the routing protocol is given full control, and can ignore the route suggestion if it can find a better route. But that optimization goes another level. I am proposing something far simpler for now.
Gustavo, I agree with your point that a route cached from first packet can become stale. What about, though, just doing a per-packet lookup but doing it in UDP when the transport header needs to be created? I think source address selection needs to be done in the transport layer, particularly when things like IPsec can be inserted before the packet hits IP. Source address selection typically requires the destination to be determined. As a first step, one could have the transport layer do the pre-route step per packet and store the route in a packet tag. This would ensure per-packet lookups like you want. For optimizations, one could consider registering a callback with the routing layer that flushed cached routes at the transport layer when any routing protocol routes changed.
(In reply to comment #1) > Gustavo, I agree with your point that a route cached from first packet can > become stale. What about, though, just doing a per-packet lookup but doing it > in UDP when the transport header needs to be created? > > I think source address selection needs to be done in the transport layer, > particularly when things like IPsec can be inserted before the packet hits IP. > Source address selection typically requires the destination to be determined. Sounds like a good idea to me. > > As a first step, one could have the transport layer do the pre-route step per > packet and store the route in a packet tag. This would ensure per-packet > lookups like you want. Sure. > > For optimizations, one could consider registering a callback with the routing > layer that flushed cached routes at the transport layer when any routing > protocol routes changed. That's one possibilty. Another possibility is to add the previously found route to the RequestRoute API call, and also add a "creation timestamp" to Ipv4Route. Then the routing protocol can simply look at the timestamp and possibly return the previous route and not do any new lookup.
OK, some more comments. I was looking to quickly implement the RouteExpireCallback approach, but then I realized that a routing protocol will have a hard time implementing this interface. In order for a routing protocol to call RouteExpireCallback when route expires, it needs to keep a list of RouteExpireCallbacks associated with every Ipv4Route, and call them all. This adds a lot of complexity to the routing protocol, already complex enough. And also the caller needs to the define two separate callbacks... The other alternative appears simpler. The caller just stores the previous route along with a timestamp, then for each packet requests a new route but passing along the previous route and a timestamp. The routing protocol can simply do: if (Simulator::Now () - timestamp < Seconds(2)) { return previousRoute; // returns the cached result, very fast } // else the route has become stale and a new one needs to be looked up This second alternative seems much simpler to implement. What do you think?
As usual, the question is: how do they do this in real network stacks ? I suspect that a simple solution would be to just notify every layer of the network stack whenever there is a change in the routing table which might require some layers to re-lookup a cached route.
(In reply to comment #4) > As usual, the question is: how do they do this in real network stacks ? We cannot base our design purely on existing implementations of real network stacks, because real implementations take into consideration the userspace / kernelspace division between routing and forwarding, and associated context switching penalty. Here we have no context switching, thus we can achieve a simpler architecture because we don't have to work around the context switching bottleneck. > > I suspect that a simple solution would be to just notify every layer of the > network stack whenever there is a change in the routing table which might > require some layers to re-lookup a cached route. > That's a rather "course" solution. Besides, it doesn't work well for reactive routing protocols, which do not proactively modify the routing table at all, which means that notification will never happen for example in AODV.
> We cannot base our design purely on existing implementations of real network > stacks, because real implementations take into consideration the userspace / > kernelspace division between routing and forwarding, and associated context > switching penalty. Here we have no context switching, thus we can achieve a > simpler architecture because we don't have to work around the context switching > bottleneck. Sure, but if you knew how others solve the same problem, I am fairly certain that it would give you food for thought: it does not mean that you should do the same thing. It just means that trying to redesign something without a-priori knowledge of what others do does not sound like a great idea.
I never meant to mark this as blocker; blocker is just the default severity in this bugzilla instance...
change to P3 (not a blocker)
sliding to ns-3.5
fixed in changeset e20a31541404 The basic behavior now is that routes are queried with RouteOutput() in the transport layer, and the retrieved route is passed down the stack with the packet to the IP layer.