Bug 74

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.