Created attachment 503 [details]
Example to show how Injection is used.

Note that nC -> nB traffic doesn't work, I didn't bother to add a defaultgw to nC.

(In reply to comment #0)
> copypastecoded some of the stuff in SPFAddASExternal, but anyway, it first
> checks what's the advertising router ID for the external route, then tries to
> find *any* interface that actually HAS an SPF, and then sets nexthop to that. 

  Looks like my intuition went wrong here - the recursive lookup doesn't work here since it should actually be performed for the *entire* routing stack. The thing breaks at penultimate hop where the next (last) hop is directly connected (shows in static routing table). 

  When GlobalLookup does the recursion, it naturally does not find the (directlyconnected) nexthop, but fails completely, or, even worse, (in e.g. case of three routers in a triangle) sends the packet the long way around. Anyway, result is a packet going ping-pong.

  Beyond the penultimate hop no problems.

  Technically I could amend the Ipv4Route class to include some kind of flag that would tell requester to perform a recursive lookup throughout the entire ListRouting stack...but seems a bit of a band-aid.

  I guess this means that making that ListRouting variant which maintains a real, aggregated routing table instead of querying each protocol separately is in order..

(In reply to comment #2)
> (In reply to comment #0)
> > copypastecoded some of the stuff in SPFAddASExternal, but anyway, it first
> > checks what's the advertising router ID for the external route, then tries to
> > find *any* interface that actually HAS an SPF, and then sets nexthop to that. 
> 
>   Looks like my intuition went wrong here - the recursive lookup doesn't work
> here since it should actually be performed for the *entire* routing stack. The
> thing breaks at penultimate hop where the next (last) hop is directly connected
> (shows in static routing table). 

Since the global routing code is just a port of quagga's ospfd SPF code, can't we just follow how ospf does it?  We didn't add that phase of the algorithm when we first did this port, but section 16.4 of RFC 2328 describes the algorithm and it is implemented in quagga (requires finishing the port).

(In reply to comment #3)
> Since the global routing code is just a port of quagga's ospfd SPF code, can't
> we just follow how ospf does it?  We didn't add that phase of the algorithm
> when we first did this port, but section 16.4 of RFC 2328 describes the
> algorithm and it is implemented in quagga (requires finishing the port).

  I have, to a degree. The beef is in quagga's ospf_ase_calculate_asbr_route() function is ospf_ase.c. (ASBR router is any router which injects external routes.). I tried to ignore some of the stuff in there that shouldn't matter to GlobalRouting as long as it would work, such as NSSA-related things. 

  Anyway, one of the key points in processing externals is ospf_ase_calculate_asbr_route() which, right at start, does a lookup for finding a path to the advertising router itself.

  Seems pretty straightforward, that I'd need to be able to replicate the functionality of ospf_find_asbr_route(), especially the part where
/* Now find the route with least cost. */. However, the process seems to utilize the already calculated routing table - so I guess I'd need to actually call RouteOutput from within the implementation(?). 

  Slightly problematic for me is that this seems to require getting info on *all* possible routes and choosing the best path..

Thanks for this quite detailed description and the patch; I agree this would be a useful addition; a few comments below

(In reply to comment #0)
> Created an attachment (id=502) [details]
> Patch to add InjectRoute support
> 
> Attached is the patch I mentioned in bug #611 (and mailing list). It allows you
> to inject arbitrary routing information to GlobalRouting.
> 
> With static routing, this can be used for redistributing static routes. For
> dynamic routing protocols, some kind of framework to inject/withdraw routes
> after each routing update needs to be designed.
> 
> The user API is changed so that GlobalRouting object now has a new method, 
> 
> inject (Ipv4Addr, Ipv4Mask)

How about calling this Redistribute instead of Inject, to align with typical terminology?

This could also be extended, or a version provided, with metric and metric type, to align better with quagga API:

redistribute (kernel|connected|static|rip|bgp) metric-type (1|2) metric <0-16777214> route-map word

> 
> LookupGlobal has been changed so that if requesting a destination for an
> external network, the function performs a recursive lookup towards the router
> which advertised the network in the first place. 

If I understand correctly, this does a dynamic recursive lookup-- what about just installing the route like any other, to begin with?


> ForwardingAddress (as per RFC
> 2328) is not supported yet, although I guess it could be included as an
> alternative call for Inject().

I am not sure it is going to be needed for the basic route redistribution that you are seeking.


> 
> I've attached a test script, which is an amalgam of global-routing-slash32 and
> static version of the same. In this scenario, nA and nB are running global
> routing and nC is not running anything. At nB we inject the host route for the
> interface behind nC to the GlobalRouting Cloud, and also put in a static route
> to reach it via nC.
> 
> So what happens is that nA sees destination for network C, with nexthop as nD.
> When sending packet, nA first performs lookup for network C, and then recurses
> it for nexthop towards nB. At nB the ListRouting is processed in order where
> StaticRouting gets checked first, and packet is forwarded to nC.

  // Populate routing tables for nodes nA and nB
  Ipv4GlobalRoutingHelper::PopulateRoutingTables ();
  // Inject global routes from Node B, including transit network...
  Ptr<Ipv4GlobalRouting> globalRoutingB = GetGlobalRouting(ipv4B);
  globalRoutingB->InjectRoute ("10.1.1.4", "255.255.255.252");
  // ...and the host in network "C"
  globalRoutingB->InjectRoute ("192.168.1.1", "255.255.255.255");
  
  Ipv4GlobalRoutingHelper::RecomputeRoutingTables();

The above looks a little strange but I understand why you did it like that, because of the limited API in the helper.  I would think that you would not prefer to have to call PopulateRoutingTables() before injecting; we can probably fix the helper API to avoid this.

> 
> TODO:
>   ForwardingAddressSupport
>   Somehow implement E1 vs E2 routes - any ideas on how to do that?

Like forwarding address, E2 is probably a refinement most users won't use, but OTOH, if there is easily ported support from quagga for this, I don't see a problem to support it.

>   Generic redistribution framework(if there's interest... :))
> 

I assume you mean route maps, redistribution of routes learned from e.g. OLSR, etc.  

I do not have interest in building up a separate version of OSPF in the simulator; we have plans to support quagga in the near future so I think for users that want to do real routing work, they will not use global routing in the future.

(In reply to comment #4)
> (In reply to comment #3)
> > Since the global routing code is just a port of quagga's ospfd SPF code, can't
> > we just follow how ospf does it?  We didn't add that phase of the algorithm
> > when we first did this port, but section 16.4 of RFC 2328 describes the
> > algorithm and it is implemented in quagga (requires finishing the port).
> 
>   I have, to a degree. The beef is in quagga's ospf_ase_calculate_asbr_route()
> function is ospf_ase.c. (ASBR router is any router which injects external
> routes.). I tried to ignore some of the stuff in there that shouldn't matter to
> GlobalRouting as long as it would work, such as NSSA-related things. 
> 
>   Anyway, one of the key points in processing externals is
> ospf_ase_calculate_asbr_route() which, right at start, does a lookup for
> finding a path to the advertising router itself.

OK, I understand-- maybe we need to keep more state around in the global
routing from the first phase to be able to do this.

> 
>   Seems pretty straightforward, that I'd need to be able to replicate the
> functionality of ospf_find_asbr_route(), especially the part where
> /* Now find the route with least cost. */. However, the process seems to
> utilize the already calculated routing table - so I guess I'd need to actually
> call RouteOutput from within the implementation(?). 

I would lean towards trying to solve this internally rather than rely on
calling out to previously installed routes.

(In reply to comment #6)

> >   Seems pretty straightforward, that I'd need to be able to replicate the
> > functionality of ospf_find_asbr_route(), especially the part where
> > /* Now find the route with least cost. */. However, the process seems to
> > utilize the already calculated routing table - so I guess I'd need to actually
> > call RouteOutput from within the implementation(?). 
> 
> I would lean towards trying to solve this internally rather than rely on
> calling out to previously installed routes.

  Something that is implemented in quagga and also specified in the RFC that I don't think is implemented in existing globalrouting - it's the part of the RFC (right at start of chapter 16), where ABR/ASBR's are put into routing table with destination type "Router". This is implemented in quagga with a separate routing table (called rtr). 

  So right now I'm just going for a random link, but I'd really need to traverse the path to all the advertising router's interfaces (all mentioned in it's RouterLSA) and check which one is cheapest. 

I still haven't quite grasped the data structure of SPFVertex - is the tree constructed separately for *each* router? If yes, then it seems all I have to do is

  Find out the interfaces of advertising router (already done in SPFDistance - basically take all links in RouterLSA and ignore stubs),
  for each of these interfaces,
  traverse the SPF tree from the root (current router) until you find the current interface (basically just go for (i=0;i<GetNChildren();i++), recurse), make note of the distance
  check which if had least distance, record it to routing table as next hop...

  If the above is accurate, then this should be quite doable..

(In reply to comment #5)
> > The user API is changed so that GlobalRouting object now has a new method, 
> > inject (Ipv4Addr, Ipv4Mask)
> How about calling this Redistribute instead of Inject, to align with typical
> terminology?

  I called it Inject since, well, redistribution *is* injecting routes except that they aren't completely arbitrary. A complete redistribution schema would
  - Get a handle on the static routing (or whatever source) object
  - Read all active routes (GetNNRoutes())
  - For each route, call Inject on target protocol.

  For static stuff this is easy, but I'm not sure how this could be implemented in a generic case. Need some sort of approach where a dynamic routing protocol calls some callback (perhaps in Ipv4ListRouting?) that checks if anything should be redistributed to others and performs the functions above.

  An addition that is probably needed is going to be a Withdraw-method which allows to remove routes. 

> This could also be extended, or a version provided, with metric and metric
> type, to align better with quagga API:
> 
> redistribute (kernel|connected|static|rip|bgp) metric-type (1|2) metric
> <0-16777214> route-map word

  I think that in context of ns-3, I'd implement this in ListRouting, with some sort of matrix, basically 2-dimensional array of from -> to, something like this:

X   |Stat|Glob|OLSR|
Stat| x     0    0 
Glob| 1     x    1
OLSR| 0     1    x

  which would mean that Static gets redistributed to global, global gets redistrubted to OLSR and vice versa. I'd probably set up some sort of RoutingChangeStatusNotification() method that all of these protocols could call whenever they get a routing update. Maybe the changes (or pointer to changes) could be sent as a parameter. Anyway, this method would then check if these changes need to be redistributed to anything and call appropriate target protocols Inject/Withdraw functions.

  In Static Routing's case, this callback would be executed when user calls AddNetworkRouteTo() or AddHostRouteTo(). 

  Note that this is more of a "This is how I would do it in a general case"-thinking, and something that I might get back to if I have time :) 

> > LookupGlobal has been changed so that if requesting a destination for an
> > external network, the function performs a recursive lookup towards the > If > I understand correctly, this does a dynamic recursive lookup-- what about
> just installing the route like any other, to begin with?

  See the previous comment - I'll see if I can do this.

> > it for nexthop towards nB. At nB the ListRouting is processed in order where
> > StaticRouting gets checked first, and packet is forwarded to nC.
> 
>   // Populate routing tables for nodes nA and nB
>   Ipv4GlobalRoutingHelper::PopulateRoutingTables ();
>   // Inject global routes from Node B, including transit network...
>   Ptr<Ipv4GlobalRouting> globalRoutingB = GetGlobalRouting(ipv4B);
>   globalRoutingB->InjectRoute ("10.1.1.4", "255.255.255.252");
>   // ...and the host in network "C"
>   globalRoutingB->InjectRoute ("192.168.1.1", "255.255.255.255");
> 
>   Ipv4GlobalRoutingHelper::RecomputeRoutingTables();
> 
> The above looks a little strange but I understand why you did it like that,
> because of the limited API in the helper.  I would think that you would not
> prefer to have to call PopulateRoutingTables() before injecting; we can
> probably fix the helper API to avoid this.

  Aye - PopulateRoutingTables is needed because it installs the GlobalRouting interfaces in the first place, so I can't call GetGlobalRouting until after.

> >   Generic redistribution framework(if there's interest... :))
> I assume you mean route maps, redistribution of routes learned from e.g. OLSR,
> etc.  
> 
> I do not have interest in building up a separate version of OSPF in the
> simulator; we have plans to support quagga in the near future so I think for
> users that want to do real routing work, they will not use global routing in
> the future.

  Yes, this is the part where I'm wondering if I'm trundling on anyones toes - if a full-fledged OSPF (or the whole quagga including e.g. BGP) is coming soon then I'm willing to wait. However, if the timescale here is more than a few months (I'm on limited grant money here and need to write some papers :)), I'll go with this for now.

Created attachment 509 [details]
Patch to add InjectRoute support

Ok, I've done some progress. Now this works pretty well - no need to do recursion, it's just a normal routing entry. I'm still maintaining a separate table so that they get checked last (externals should always be checked only after you can't find an internal route).

Anyway, this works well for point-to-point links. However, if there's a broadcast network in between (With NetworkLSA), only the first external route considered gets propagated to other networks. Still hunting for what I'm doing wrong here..

(In reply to comment #9)
> Anyway, this works well for point-to-point links. However, if there's a
> broadcast network in between (With NetworkLSA), only the first external route
> considered gets propagated to other networks. Still hunting for what I'm doing
> wrong here..

  ...except on further investigation, it seems this applied to *all* networks, not just external ones. I have used a switch (Set up via bridgehelper) to set up such LAN, and it failed on that. Using just csmaHelper directly to connect all the nodes to same segment fixed the issue, so I think it might be a separate bug or I'm just using bridging wrong. 

  As such, my patch seems to work fine now.

  (I used a switch since I don't want to see collisions or any similar Ethernet level stuff - Basically I want to have a LAN switch and all nodes running Full Duplex at 100Mbps or 1Gbps, and installing a shared LAN segment like a hub might induce some additional anomalies to my results). 

I support this addition, once it is finished off and tested more.  Here are some open issues:

- the example program shows a method called GetGlobalRouting () that should really be part of the helper API.  For instance, something like 
  static void Ipv4GlobalRoutingHelper::InjectRoute (Ptr<Node> n, Ipv4Address addr, Ipv4Mask mask);

- ./waf --valgrind --run global-injection-slash32 displays memory leaks

- coding style:  please include space between function name and opening parentheses of arguments

(In reply to comment #11)
> I support this addition, once it is finished off and tested more.  Here are
> some open issues:
> - ./waf --valgrind --run global-injection-slash32 displays memory leaks

  Valgrind was easy enough to fix - I just had forgotten to clean up the InjectedRoutes and ASExternalRoutes at the ipv4-global-routing's DoDispose(). (I thought the Ptr<> smart pointers included garbage collection as well, as soon as all references are gone the object would be killed as well, but guess not)

  Will check coding style too. 

  The GetGlobalRouting one - it's something that is present in same format in static helper (that's basically copypasted from there). 
  If included in global routing helper, should it be public or private function (will there be cases for end-users to access it directly, or should it just be something that a Helper-Inject uses internally?)

Created attachment 528 [details]
Updated patch

Coding style fixes, memory leak fix. Also fixes bug which manifested when calling RecomputeRoutingTables more than once.

Helper has the GetGlobalRouting function as public (and I guess it should remain as public since to inject stuff you need to find the GlobalRouting object anyway.

Created attachment 529 [details]
Updated example

Updated example (now uses Helper's GetGlobalRouting() instead of built-in).

(In reply to comment #12)

> 
>   The GetGlobalRouting one - it's something that is present in same format in
> static helper (that's basically copypasted from there). 
>   If included in global routing helper, should it be public or private function
> (will there be cases for end-users to access it directly, or should it just be
> something that a Helper-Inject uses internally?)
> 

I think that the way you have added it in the latest patch (as public) is fine.  I was thinking of just making this a non-ptr-based helper method such as in my previous comment, but I see that you have aligned it with the static routing helper API which I think is preferable.

I'll test it a bit more and apply it if no other issues arise.

(In reply to comment #14)
> Created an attachment (id=529) [details]
> Updated example
> 
> Updated example (now uses Helper's GetGlobalRouting() instead of built-in).
> 

I went to check this in and decided to change the API a bit (and revised some doxygen).  The main change I made was to move the InjectRoute() API from class Ipv4GlobalRouting to class GlobalRouter.  This latter class makes more sense IMO to store these routes; then, they do not have to be passed in from the Ipv4GlobalRouting class (which is really intended to store the forwarding table entries), and the helper API does not need to be changed anymore.  The example program can obtain a pointer to GlobalRouter via GetObject<GlobalRouter> ().  See updated example.

Please review these revisions before I check them in.

Created attachment 573 [details]
Updated patch

Created attachment 574 [details]
Updated example

(In reply to comment #16)
> I went to check this in and decided to change the API a bit (and revised some
> doxygen).  The main change I made was to move the InjectRoute() API from class
> Ipv4GlobalRouting to class GlobalRouter.  This latter class makes more sense
> IMO to store these routes; then, they do not have to be passed in from the
> Ipv4GlobalRouting class (which is really intended to store the forwarding table
> entries), and the helper API does not need to be changed anymore.  The example
> program can obtain a pointer to GlobalRouter via GetObject<GlobalRouter> (). 
> See updated example.

  Makes sense to me. After all, GlobalRouter is a special case in the sense that there *does* exist an aggregated object that you can find directly from Node level. Should be more efficient this way instead of having to go through all the objects in ListRouting.

  Probably should create that WithdrawRoute(uint32_t) function too..should be simple enough, just copypaste GetRoute and change the "return *j" to "m_injectedRoutes.erase(j)".

>   Probably should create that WithdrawRoute(uint32_t) function too..should be
> simple enough, just copypaste GetRoute and change the "return *j" to
> "m_injectedRoutes.erase(j)".
> 

How about aligning the WithdrawRoute method with InjectRoute, and namely just allow users to specify Network/Mask rather than a route index?  The function could search for the route and erase it if found, and assert if not found. Users would have to explicitly call RecomputeRoutingTables to flush out the ExternalLSA.

 

(In reply to comment #20)
> >   Probably should create that WithdrawRoute(uint32_t) function too..should be
> > simple enough, just copypaste GetRoute and change the "return *j" to
> > "m_injectedRoutes.erase(j)".
> > 
> 
> How about aligning the WithdrawRoute method with InjectRoute, and namely just
> allow users to specify Network/Mask rather than a route index?  The function
> could search for the route and erase it if found, and assert if not found.
> Users would have to explicitly call RecomputeRoutingTables to flush out the
> ExternalLSA.

  Well, I was going with the alignment to StaticRouting's RemoveRoute()-method since no such possibility exists there, either.

  I wouldn't do an assert on not finding it though - maybe return a boolean on whether it succeeded.

  Anyway, thanks for improving my patch..

Created attachment 575 [details]
add WithdrawRoute() and RemoveInjectedRoute() methods

New api in this version
+  bool WithdrawRoute (Ipv4Address network, Ipv4Mask networkMask);
+  void RemoveInjectedRoute (uint32_t i);

checked in as changeset a0e27af57c8d