Bug 1049

Created attachment 1031 [details]
diff -u olsr-routing-protocol.cc patched_olsr-routing-protocol.cc

This is a patch file that eliminates the bug occurring when multiple gateways send HNA messages.
Actually, this bug was existing because networks announced in HNA messages received from other gateways where taken into account in the "RoutingTableComputation()" method without checking whether or not the node itself announces them. In case a network is announced by the node itself, there is no need to add a route in its HNA routing table, assuming this network is installed in a static routing table (this IS the case for networks accessible through non-olsr interfaces, and this SHOULD BE the case for other networks, including a default route).

Modifications also include the following elements:
- when HNA association method 1 is used ("SetRoutingTableAssociation(Ptr<Ipv4StaticRouting>)", entries of the associated routing table with non-osrl outgoing interfaces are now added to the list of "local" (I mean, sent by this node) network associations using "AddHostNetworkAssociation(Ipv4Address networkAddr, Ipv4Mask netmask)". This way, the "m_state.GetAssociations()" method always returns all local network associations whatever the method used.
- so, the "SendHna()" method now just iterates over this list containing all local network associations
- the "HnaTimerExpire()" method now has a more simple test to do.

Finally, other details have changed:
- adding tabs and printing the HNA routing table (otherwise, there is no way to see how packets are forwarded) in the "PrintRoutingTable()" method
- LOG_INFO in the "AddHostNetworkAssociation(Ipv4Address networkAddr, Ipv4Mask netmask)" method.

I haven't tested your patch yet, but from my first glance through it, my main comment is that I'm not in favour of keeping SetRoutingTableAssociation() a one time call.

Instead, I would prefer a modification to GetAssociations() such that it returns the combined set of tuples from m_hnaRoutingTableAssociation and the local HNA entries. In short, move the duplicate entry check from RoutingProtocol::SendHna() into OlsrState::GetAssociations().

(In reply to comment #2)
> I haven't tested your patch yet, but from my first glance through it, my main
> comment is that I'm not in favour of keeping SetRoutingTableAssociation() a one
> time call.
> 
> Instead, I would prefer a modification to GetAssociations() such that it
> returns the combined set of tuples from m_hnaRoutingTableAssociation and the
> local HNA entries. In short, move the duplicate entry check from
> RoutingProtocol::SendHna() into OlsrState::GetAssociations().


I understand your point... You're right, something must be done to update local HNA entries if "OlsrRoutingProtocol::SetRoutingTableAssociation()" is called more than once.
However, I think the "GetAssociations()" method in the OlsrState class can not return the combined set of tuples like you suggest, because it is has no access to the (private) attribute "m_routingTableAssociation" of the OlsrRoutingProtocol class (this is conceptually good).

I think 2 solutions can be envisioned:

1. keep the 2 non-overlapping sets of local HNA entries (one for each association method, i.e. "m_routingTableAssociation" in the OlsrRoutingProtocol class and "m_associations" in the OlsrState class) and create a private method "GetLocalHnaAssociations()" in the OlsrRoutingProtocol class to return a set with all local HNA entries. This added method would perform the aggregation of entries stored in each set. This is what you suggest. However, I strongly believe that "m_associations" in class "OlsrState" should contain all local associations. With this solution, it would not be the case.

2. use the "m_associations" attribute of the OlsrState class to store ALL local HNA entries like I have proposed, but add a test in the "OlsrRoutingProtocol::SetRoutingTableAssociation()" method to check whether a routing table has already been associated. If not, add entries. If a routing table has already been associated, delete entries from the old association and add the new ones. This would be in accordance with the initial behavior: the new routing table association was simply set.

Which solution sounds best for you? Personally, I have a preference for solution 2...

(In reply to comment #3)
> (In reply to comment #2)
> 
> 
> 2. use the "m_associations" attribute of the OlsrState class to store ALL local
> HNA entries like I have proposed, but add a test in the
> "OlsrRoutingProtocol::SetRoutingTableAssociation()" method to check whether a
> routing table has already been associated. If not, add entries. If a routing
> table has already been associated, delete entries from the old association and
> add the new ones. This would be in accordance with the initial behavior: the
> new routing table association was simply set.
> 

+1 for solution 2. And in your next patch, please do remove the "ADDED SECTION" tags. :)

Created attachment 1032 [details]
diff -u olsr-routing-protocol.cc patched_olsr-routing-protocol.cc

This patch replaces the previous one (comment #1).
It solves the bug, allows "SetRoutingTableAssociation()" to be called multiple times, and includes all necessary verifications around the list of local HNA associations.
Two methods has been created:
- "RemoveHostNetworkAssociation (Ipv4Address networkAddr, Ipv4Mask netmask)", with the same visibility (public) than "AddHostNetworkAssociation()", allows to remove a (networkAddress, netmask) tuple from the list of local HNA associations
- "UsesNonOlsrOutgoingInterface(const Ipv4RoutingTableEntry &route)", with a private visibility, performs a test on whether or not the routing table entry given as a parameter uses a non-olsr outgoing interface. This method exists because I don't like writing the same piece of code twice! :)

This patch must be applied with the patch published in the next comment. It simply adds the two new methods declarations in file "olsr-routing-protocol.h".

All seems to work as expected. Do not hesitate to tell me about extended tests results.

Created attachment 1033 [details]
diff -u olsr-routing-protocol.h patched_olsr-routing-protocol.h

Patch adding the declarations of the two methods described in comment #5 to "olsr-routing-protocol.h".

Went through the patch. Looks good to me. Didn't test extensively, but olsr-hna.cc runs fine.

There is a coding style issue though. Function calls should have a space between the name and the braces (foo () and not foo()). The brace style is incoherent as well, i.e:

// Should be
if (foo)
 {
 
 }

// and not
if (foo) {
}

And lastly, you may make the changes to have GetAssociations() return an std::set if you feel it necessary. If not, do remove the comments in AddHostNetworkAssociation() because it's a method that's not going to be called too many times anyway.

If possible, do an hg clone of current ns-3-dev, apply your patches, fix the coding style and re-submit a single diff (you can do an "hg diff"). And you'll need an ACK from Gustavo before it can go in though. :)

Created attachment 1034 [details]
hg diff after applying changes on olsr-routing-protocol.cc and .h

This patch makes all others obsolete. It is a single "hg diff" file containing changes made on "olsr-routing-protocol.cc" and "olsr-routing-protocol.h" to overcome this bug.

Sorry for coding style, I used to work with Java. It should now be all right.

Thanks for letting me know if I can commit these changes.

(In reply to comment #0)
> As reported by Julien Boite on the users mailing list thread [0]:
> 
> 
> When multiple HNA gateways announce the same external routes, it tends to
> create a routing loop between the HNA gateways themselves. This is primarily
> because HNA gateways do not have routing table entries to their own local
> associations in their HNA routing table.
> 
> 
> [0]
> http://groups.google.com/group/ns-3-users/browse_thread/thread/ed70bebe14323b7d/ca2cc35e7fc28363?lnk=gst&q=HNA#ca2cc35e7fc28363

Just one question, what about making the "ipv4 static routing" object have higher priority in the mesh nodes than the OLSR routing?  It does seem like the logical solution to the problem, and one that would need no patch...

(In reply to comment #9)
> (In reply to comment #0)
> > As reported by Julien Boite on the users mailing list thread [0]:
> > 
> > 
> > When multiple HNA gateways announce the same external routes, it tends to
> > create a routing loop between the HNA gateways themselves. This is primarily
> > because HNA gateways do not have routing table entries to their own local
> > associations in their HNA routing table.
> > 
> > 
> > [0]
> > http://groups.google.com/group/ns-3-users/browse_thread/thread/ed70bebe14323b7d/ca2cc35e7fc28363?lnk=gst&q=HNA#ca2cc35e7fc28363
> 
> Just one question, what about making the "ipv4 static routing" object have
> higher priority in the mesh nodes than the OLSR routing?  It does seem like the
> logical solution to the problem, and one that would need no patch...

Hi,

From experiments I have made, what you propose is not sustainable.
A simple test I have made with priorities set like you mention is to ping a gateway from a mesh node at 2 hops or more. I you can reproduce this test, you will probably see that it does not work. Why? I do not exactly know, but the following might be an explanation.
Let's say a gateway is part of a mesh network with addresses in range 192.168.0.0/24.
- being directly connected to this network, the gateway's static routing table contains an entry for network "192.168.0.0" with next hop "0.0.0.0" and its wireless interface (wlan0) as the outgoing interface
- moreover, OLSR runs and maintains an OLSR routing table containing an entry for each node's address. For instance, the OLSR routing table entry that specifies how to reach a node at 3-hops contains:
"(dest) 192.168.0.x  (next hop) 192.168.0.y  (out interface) wlan0", with "192.168.0.y" representing the IP address of a neighbouring node (used here as a next hop).

1. If static routing is preferred over OLSR, packets for mesh nodes match the route "192.168.0.0" and sends the packet on its wireless interface... but without any next hop specified. What happens next??? I did not identified it.

2. If OLSR routing protocol is preferred, the entry used is "192.168.0.x" (good, this is the longest-match), that specifies which next hop node is supposed to deal with the packet and forward it towards its destination.

Case 1 does not work, but I think that even if it would work (then, what would OLSR be used for...?), it would not be a good choice.

Besides, all this makes me highlight a point important to me: setting priorities to routing protocols allow to define which routing table to look in during the routing process. But I think this functioning does not respect the longest-match used in real world. Are there any reasons why this choice has been made?

(In reply to comment #10)
> (In reply to comment #9)
> > (In reply to comment #0)
> > > As reported by Julien Boite on the users mailing list thread [0]:
> > > 
> > > 
> > > When multiple HNA gateways announce the same external routes, it tends to
> > > create a routing loop between the HNA gateways themselves. This is primarily
> > > because HNA gateways do not have routing table entries to their own local
> > > associations in their HNA routing table.
> > > 
> > > 
> > > [0]
> > > http://groups.google.com/group/ns-3-users/browse_thread/thread/ed70bebe14323b7d/ca2cc35e7fc28363?lnk=gst&q=HNA#ca2cc35e7fc28363
> > 
> > Just one question, what about making the "ipv4 static routing" object have
> > higher priority in the mesh nodes than the OLSR routing?  It does seem like the
> > logical solution to the problem, and one that would need no patch...
> 
> Hi,
> 
> From experiments I have made, what you propose is not sustainable.
> A simple test I have made with priorities set like you mention is to ping a
> gateway from a mesh node at 2 hops or more. I you can reproduce this test, you
> will probably see that it does not work. Why? I do not exactly know, but the
> following might be an explanation.
> Let's say a gateway is part of a mesh network with addresses in range
> 192.168.0.0/24.
> - being directly connected to this network, the gateway's static routing table
> contains an entry for network "192.168.0.0" with next hop "0.0.0.0" and its
> wireless interface (wlan0) as the outgoing interface
> - moreover, OLSR runs and maintains an OLSR routing table containing an entry
> for each node's address. For instance, the OLSR routing table entry that
> specifies how to reach a node at 3-hops contains:
> "(dest) 192.168.0.x  (next hop) 192.168.0.y  (out interface) wlan0", with
> "192.168.0.y" representing the IP address of a neighbouring node (used here as
> a next hop).
> 
> 1. If static routing is preferred over OLSR, packets for mesh nodes match the
> route "192.168.0.0" and sends the packet on its wireless interface... but
> without any next hop specified. What happens next??? I did not identified it.
> 
> 2. If OLSR routing protocol is preferred, the entry used is "192.168.0.x"
> (good, this is the longest-match), that specifies which next hop node is
> supposed to deal with the packet and forward it towards its destination.
> 
> Case 1 does not work, but I think that even if it would work (then, what would
> OLSR be used for...?), it would not be a good choice.

I thought Case 1 could be made to work if the route to network 192.168.0.0 was removed.  To do this, you need to configure /32 addresses in the network interfaces.  But then I realized OLSR protocol UDP broadcasts would not work with /32 addresses.

One thing that probably works is to have two different static routing tables, one before and one after the OLSR protocol, in the gateway nodes:

1. static routing with 0.0.0.0 route (to access internet)
2. OLSR routes
3. normal static routing with 192.168.1.0/24

But, well, I guess even if it works for most users figuring this out won't be easy, and so I won't oppose your patch. 

> Besides, all this makes me highlight a point important to me: setting
> priorities to routing protocols allow to define which routing table to look in
> during the routing process. But I think this functioning does not respect the
> longest-match used in real world. Are there any reasons why this choice has
> been made?

I don't think there's any reason.  Longest-prefix match would be a nice feature, but it would require that all routing protocols wrote into the same output routing table.  It's a more complex design.  But it sounds like a good feature have.  And it is implemented inside the ipv4 static routing, just not cross-routing-protocol.  Between routing protocols, the "priority" prevails.  For now...

(In reply to comment #11)
> 
> I thought Case 1 could be made to work if the route to network 192.168.0.0 was
> removed.  To do this, you need to configure /32 addresses in the network
> interfaces.  But then I realized OLSR protocol UDP broadcasts would not work
> with /32 addresses.

Using /32 network addresses does not make sense: this means all bits of the address are used to define the network part, and no address can be assigned to hosts. The minimum number of addresses necessary to ensure a communication is 2: in that case (a point to point network link between 2 hosts for instance), a /30 can be used... but I have never seen /32 addresses in concrete situations.

> One thing that probably works is to have two different static routing tables,
> one before and one after the OLSR protocol, in the gateway nodes:
> 
> 1. static routing with 0.0.0.0 route (to access internet)
> 2. OLSR routes
> 3. normal static routing with 192.168.1.0/24
> 
> But, well, I guess even if it works for most users figuring this out won't be
> easy, and so I won't oppose your patch.

Because priorities associated to routing tables currently prevails, I think that what you propose would not work because the route "0.0.0.0" in the first static routing table would match for every packet (no lookup for longest-prefix in other routing tables). We are back to the discussion on cross-routing-protocol longest-prefix match in ns-3...

> > Besides, all this makes me highlight a point important to me: setting
> > priorities to routing protocols allow to define which routing table to look in
> > during the routing process. But I think this functioning does not respect the
> > longest-match used in real world. Are there any reasons why this choice has
> > been made?
> 
> I don't think there's any reason.  Longest-prefix match would be a nice
> feature, but it would require that all routing protocols wrote into the same
> output routing table.  It's a more complex design.  But it sounds like a good
> feature have.  And it is implemented inside the ipv4 static routing, just not
> cross-routing-protocol.  Between routing protocols, the "priority" prevails. 
> For now...

The scenario I am working on will probably lead me to think about implementing such a functionality. I will let you know if it is the case.

Finally, can you tell me whether you deal with applying the patch I proposed yourself in the ns-3-dev repository or if I have to commit changes myself? Thanks.

(In reply to comment #12)
> Finally, can you tell me whether you deal with applying the patch I proposed
> yourself in the ns-3-dev repository or if I have to commit changes myself?
> Thanks.

Hi,

Can someone tell me what does the last step to apply my patch consist in?
Is Gustavo going to apply the patch to the ns-3-dev repo?
Am I expected to do this last step and commit changes to the ns-3-dev repo myself?

Thanks for your answer.

(In reply to comment #12)
> (In reply to comment #11)
> > 
> > I thought Case 1 could be made to work if the route to network 192.168.0.0 was
> > removed.  To do this, you need to configure /32 addresses in the network
> > interfaces.  But then I realized OLSR protocol UDP broadcasts would not work
> > with /32 addresses.
> 
> Using /32 network addresses does not make sense: this means all bits of the
> address are used to define the network part, and no address can be assigned to
> hosts. The minimum number of addresses necessary to ensure a communication is
> 2: in that case (a point to point network link between 2 hosts for instance), a
> /30 can be used... but I have never seen /32 addresses in concrete situations.
> 

Well, for me /32 address is one where the host and network address completely overlap, i.e. each host interface defines its own network and cannot communicate directly with any other host.  It means communication is possible, but through a gateway.  /32 addresses are used in the real world sometimes.

Anyway, I am trying to come up with alternatives, but they seem to not work or be more complex than they should.  It is a sign the patch is good idea.

> > One thing that probably works is to have two different static routing tables,
> > one before and one after the OLSR protocol, in the gateway nodes:
> > 
> > 1. static routing with 0.0.0.0 route (to access internet)
> > 2. OLSR routes
> > 3. normal static routing with 192.168.1.0/24
> > 
> > But, well, I guess even if it works for most users figuring this out won't be
> > easy, and so I won't oppose your patch.
> 
> Because priorities associated to routing tables currently prevails, I think
> that what you propose would not work because the route "0.0.0.0" in the first
> static routing table would match for every packet (no lookup for longest-prefix
> in other routing tables). We are back to the discussion on
> cross-routing-protocol longest-prefix match in ns-3...

OK.  So the "gateway" nodes would be unable to communicate directly with the remaining hosts in the adhoc network... Depending on the scenario, this may be problematic.

> 
> > > Besides, all this makes me highlight a point important to me: setting
> > > priorities to routing protocols allow to define which routing table to look in
> > > during the routing process. But I think this functioning does not respect the
> > > longest-match used in real world. Are there any reasons why this choice has
> > > been made?
> > 
> > I don't think there's any reason.  Longest-prefix match would be a nice
> > feature, but it would require that all routing protocols wrote into the same
> > output routing table.  It's a more complex design.  But it sounds like a good
> > feature have.  And it is implemented inside the ipv4 static routing, just not
> > cross-routing-protocol.  Between routing protocols, the "priority" prevails. 
> > For now...
> 
> The scenario I am working on will probably lead me to think about implementing
> such a functionality. I will let you know if it is the case.
> 
> Finally, can you tell me whether you deal with applying the patch I proposed
> yourself in the ns-3-dev repository or if I have to commit changes myself?
> Thanks.


(In reply to comment #13)
> (In reply to comment #12)
> > Finally, can you tell me whether you deal with applying the patch I proposed
> > yourself in the ns-3-dev repository or if I have to commit changes myself?
> > Thanks.
> 
> Hi,
> 
> Can someone tell me what does the last step to apply my patch consist in?
> Is Gustavo going to apply the patch to the ns-3-dev repo?
> Am I expected to do this last step and commit changes to the ns-3-dev repo
> myself?
> 
> Thanks for your answer.

Sorry, I missed your comment last week, you have reason to be impatient :P

Once the OLSR maintainer approves the patch, he can commit himself or you can do it if you have commit rights.  In this case, I'm the OLSR module maintainer, but I can trust Lalith, he even knows the HNA stuff better than me.

Regarding the patch itself, I think Lalith mentioned some style issues that still need to be fixed.  Style violations aside, I don't object to apply the patch.

(In reply to comment #14)
> OK.  So the "gateway" nodes would be unable to communicate directly with the
> remaining hosts in the adhoc network... Depending on the scenario, this may be
> problematic.

Correcting myself, communication from adhoc nodes to the internet happens, but back from the internet to the adhoc node it does not work.  Forget this part.

(In reply to comment #14)
> (In reply to comment #12)
> >
> > Using /32 network addresses does not make sense: this means all bits of the
> > address are used to define the network part, and no address can be assigned to
> > hosts. The minimum number of addresses necessary to ensure a communication is
> > 2: in that case (a point to point network link between 2 hosts for instance), a
> > /30 can be used... but I have never seen /32 addresses in concrete situations.
> > 
> 
> Well, for me /32 address is one where the host and network address completely
> overlap, i.e. each host interface defines its own network and cannot
> communicate directly with any other host.  It means communication is possible,
> but through a gateway.  /32 addresses are used in the real world sometimes.
> 
> Anyway, I am trying to come up with alternatives, but they seem to not work or
> be more complex than they should.  It is a sign the patch is good idea.

You're right, using /32 addresses is possible and it exists in some real situations. However, such an addressing scheme is deployed for very particular reasons. I don't think this is a suitable solution for my use case (among others) at all.

Anyway, I'm convinced that the patch I propose is necessary!

> > > One thing that probably works is to have two different static routing tables,
> > > one before and one after the OLSR protocol, in the gateway nodes:
> > > 
> > > 1. static routing with 0.0.0.0 route (to access internet)
> > > 2. OLSR routes
> > > 3. normal static routing with 192.168.1.0/24
> > > 
> > > But, well, I guess even if it works for most users figuring this out won't be
> > > easy, and so I won't oppose your patch.
> > 
> > Because priorities associated to routing tables currently prevails, I think
> > that what you propose would not work because the route "0.0.0.0" in the first
> > static routing table would match for every packet (no lookup for longest-prefix
> > in other routing tables). We are back to the discussion on
> > cross-routing-protocol longest-prefix match in ns-3...
> 
> OK.  So the "gateway" nodes would be unable to communicate directly with the
> remaining hosts in the adhoc network... Depending on the scenario, this may be
> problematic.
> 

(In reply to comment #15)
> > OK.  So the "gateway" nodes would be unable to communicate directly with the
> > remaining hosts in the adhoc network... Depending on the scenario, this may be
> > problematic.
> 
> Correcting myself, communication from adhoc nodes to the internet happens, but
> back from the internet to the adhoc node it does not work.  Forget this part.

Actually, what doesn't work is everything that requires one gateway to reach nodes in the mesh network, directly or not. This is clearly problematic:
- a gateway cannot reach a node inside the mesh network
- even if a node inside the mesh network can reach a gateway or an Internet node, the reverse path (from the gateway or Internet node to the mesh node) is not functional => as a communication necessitates a functional path in both directions, this means that nodes inside the mesh network cannot communicate with gateways or nodes outside the mesh.

> > 
> > Hi,
> > 
> > Can someone tell me what does the last step to apply my patch consist in?
> > Is Gustavo going to apply the patch to the ns-3-dev repo?
> > Am I expected to do this last step and commit changes to the ns-3-dev repo
> > myself?
> > 
> > Thanks for your answer.
> 
> Sorry, I missed your comment last week, you have reason to be impatient :P
> 
> Once the OLSR maintainer approves the patch, he can commit himself or you can
> do it if you have commit rights.  In this case, I'm the OLSR module maintainer,
> but I can trust Lalith, he even knows the HNA stuff better than me.
> 
> Regarding the patch itself, I think Lalith mentioned some style issues that
> still need to be fixed.  Style violations aside, I don't object to apply the
> patch.

The last patch I submitted includes coding style corrections that Lalith asked me to bring. You can check and tell me if there is still something wrong, but I think the patch is ready for commit!

I found:

+	  if (goToNextAssociationTuple) continue;

+  if (associations.size () == 0) return;

Plus a couple of code blocks incorrectly indented.

I save us both some time and fixed it myself, the committed.  Thanks for the patch.  Kudos to Lalith for the help.


changeset:   6814:17ff75a3dcbf
tag:         tip
user:        Julien Boite <juboite@gmail.com>
date:        Tue Feb 15 17:19:13 2011 +0000
summary:     Bug 1049 - Issues with OLSR HNA messages sent by multiple gateways

(In reply to comment #17)
> I found:
> 
> +      if (goToNextAssociationTuple) continue;
> 
> +  if (associations.size () == 0) return;
> 
> Plus a couple of code blocks incorrectly indented.
> 
> I save us both some time and fixed it myself, the committed.  Thanks for the
> patch.  Kudos to Lalith for the help.
> 
> 
> changeset:   6814:17ff75a3dcbf
> tag:         tip
> user:        Julien Boite <juboite@gmail.com>
> date:        Tue Feb 15 17:19:13 2011 +0000
> summary:     Bug 1049 - Issues with OLSR HNA messages sent by multiple gateways

I'm pleased with this contribution, as small as it probably is.
Thank you Gustavo for last corrections and commit.
Thanks to Lalith for the help on identifying the piece of code where the patch took place!

Julien