Sorry, I'm retarded, corrections to my bug report...

TOPOLOGY:

     WIRED CSMA             WIRELESS CHANNEL
   ______________
   O            O  ))          (( O ))           (( O
   N3           N0                N1                N2  


Running the UdpEcho application, the packets make it to the
destination N3 (172.16.0.1), but for some reason, N3 cannot echo the packet
back to N2. Looking at the pcap file, it seems that N3 is asking (ARP) for the
MAC
address of 192.168.0.1 (the gateway N0 on Wifi interface) and it should be
asking for 172.16.0.2 (the gateway N0 on CSMA interface).

(In reply to comment #1)
> Sorry, I'm retarded, corrections to my bug report...
> 
> TOPOLOGY:
> 
>      WIRED CSMA             WIRELESS CHANNEL
>    ______________
>    O            O  ))          (( O ))           (( O
>    N3           N0                N1                N2  
> 
> 
> Running the UdpEcho application, the packets make it to the
> destination N3 (172.16.0.1), but for some reason, N3 cannot echo the packet
> back to N2. Looking at the pcap file, it seems that N3 is asking (ARP) for the
> MAC
> address of 192.168.0.1 (the gateway N0 on Wifi interface) and it should be
> asking for 172.16.0.2 (the gateway N0 on CSMA interface).
> 

I've been looking at this off and on for the past week or so.  Here is what
I've found.

1) here are the routes that N3 OLSR builds:

dest: 192.168.0.1 next: 192.168.0.1 iface: 172.16.0.1 dist: 1
dest: 172.16.0.2 next: 172.16.0.2 iface: 172.16.0.1 dist: 1
dest: 192.168.0.2 next: 192.168.0.1 iface: 172.16.0.1 dist: 2
dest: 192.168.0.3 next: 192.168.0.1 iface: 172.16.0.1 dist: 3

What I think is missing is the following entry 
dest: 192.168.0.1 next: 172.16.0.2 iface 172.16.0.1 dist: 1

my read of step 4 of section 10 of RFC 3626 suggests that the above entry
should be added, because N3 does have a mid message from N0.  It looks like
step 4 of RFC 3626 is implemented in the ns-3 code, but I haven't debugged yet
why it adds no routes at this step.

2) however, even if the above entry is added, I don't think it will route
correctly.  OLSR will still return 192.168.0.1 to the caller for destination
192.168.0.3.  There needs to be some intelligence somewhere (either in the
caller or in OLSR) to know that 192.168.0.1 is not on-link, and that 172.16.0.2
is the next hop for 192.168.0.1.  So, either OLSR would need to add those
routes (which seem to be outside of what the RFC specifies) or Ipv4L3Protocol
would need to know to recurse, ask again for next hop to 192.168.0.1, and OLSR
would then have to return 172.16.0.2 instead of 192.168.0.1.

So, I'm doubtful there is an easy, purely OLSR fix for this.

I would like to move this to a suggested ns-3.4 resolution.  What is needed is
to finish off the HNA (associated networks and hosts) support for OLSR.  Here
is a comment in the current code:

 *  - HNA (Host/Network Association) messages are almost-but-not-quite
supported in this version.


     WIRED CSMA             WIRELESS CHANNEL
   ______________
   O            O  ))          (( O ))           (( O
   N3           N0                N1                N2  


I suggest that the proper configuration would be to run OLSR on nodes N0, N1,
and N2, with node N0 advertising the N0N3 CSMA subnet in an HNA (so that N1 and
N2 can route to it).   Then, put a static route to 192.168.0/24 at N3, or else
configure a stub prefix interface on N0 and run global routing.

Stop priority oscillations.

Created an attachment (id=737) [details]
hna.patch

Adds HNA support to OLSR.

(In reply to comment #5)
> Created an attachment (id=737) [details] [details]
> hna.patch
> 
> Adds HNA support to OLSR.

This method highlights a bit of naming inconsistency that I found:

+OlsrState::EraseHostNetAssociation (const Association &tuple)

Make up your mind, either call the HNA state "Association" or
"HostNetAssociation", or "AssociationTuple".  Get/Set/Insert/Erase/Find methods
should be named in accordance to the information they manipulate.

I'll finish my review later...

I am looking at RFC 3626, 12.6.  Routing Table Calculation, and,

     1    If there is no entry in the routing table with:

               R_dest_addr     == A_network_addr/A_netmask

The corresponding code is:

+      bool have_entry1 = Lookup (tuple.networkAddr.CombineMask
(tuple.netmask), entry1);
[...]
+      if (!have_entry1)
+        {
+          to_add = true;
+        }
[...]
+      if(to_add == true)
+        {
+          AddEntry (tuple.networkAddr.CombineMask (tuple.netmask),
+                    entry2.nextAddr,
+                    entry2.interface,
+                    entry2.distance);
+        }

At this point, one code path leads to entry2 being uninitialized
(have_entry1=true and have_entry2=false), but being used.  Not correct.

Now the other condition:

    2    If a new routing entry was created at the previous step, or
          else if there existed one with:

               R_dest_addr     == A_network_addr/A_netmask


               R_dist          >  dist to A_gateway_addr of
                                  current association set tuple,

And the code:

+      bool have_entry1 = Lookup (tuple.networkAddr.CombineMask
(tuple.netmask), entry1);
+      bool have_entry2 = Lookup (tuple.gatewayAddr, entry2);
[...]
+      else if(have_entry2 && entry1.distance > entry2.distance)
+        {
+           RemoveEntry(tuple.networkAddr.CombineMask (tuple.netmask));
+           to_add = true;           
+        }

Check.  It seems to be what is intended.  Although:

+          AddEntry (tuple.networkAddr.CombineMask (tuple.netmask),
+                    entry2.nextAddr,
+                    entry2.interface,
+                    entry2.distance);

This is not your fault, it is RFC 3626's fault (see introductory text in "10. 
Routing Table Calculation", explaining the exact routing table format), but it
seems like there is some loss of information going on here, since the routing
table does not record the network mask; it is only prepared to accept host
entries.  I would expect a HNA entry like 192.168.0.0/16 to match an address
like 192.168.1.1.  However, when the routing table is formed it will only
receive a 192.168.0.0 address, and so a packet to destination 192.168.1.1 will
not be matched.

In conclusion, it sounds to me like this HNA implementation will only work for
host entries, not network entries.  But it's a good start.

For the non-OLSR interface problem, I suppose we need to add a method like:

olsr::RoutingProtocol::SetInterfaceNonOlsr (uint32_t interface);

We add that interface to a std::set<uint32_t>, and in DoStart () exclude that
interface when creating the sockets.  Just a suggestion..

Thanks for the review, will work on the flaws.

Regarding the naming convention, here's what I'd tried:

Suppose a node A has an association named (networkAddr, netmask), it sends this
association in an HNA message, which is received by a node B.

(gatewayAddr, networkAddr, netmask, expirationTime) is saved by node B as an
AssociationTuple. The list of AssociationTuple's make an AssociationSet. (This
is in accordance with RFC 3626).

Now here's the part where I tried to come up with my own names, was and am
still confused, and would like some help:

(networkAddr, netmask) is an 'Association', used by A. I used the same name as
was already used in olsr-message-header.h.

In the Get/Insert/Erase methods, I used HostNetAssociation to refer to
'Association' set of a node, which is what the node shares with the rest of the
network through HNA messages.

Should I keep (networkAddr, netmask) as 'HostNetAssociation' rather than
'Assocation'? That will divide things into HostNetAssociation - HostNetAssocSet
and AssociationTuple - AssociationSet ? Else can you please suggest what names
I can use here? 

And after the discussion I had with Tom, I think it would be better if
RoutingProtocol::InjectRoute() is renamed to
RoutingProtocol::AddHostNetAssociation(). What do you think?

Let me know so that I can fix this first and then work on the remaining
problems with the patch. Thanks again!

(In reply to comment #8)
> Thanks for the review, will work on the flaws.
> 
> Regarding the naming convention, here's what I'd tried:
> 
> Suppose a node A has an association named (networkAddr, netmask), it sends this
> association in an HNA message, which is received by a node B.
> 
> (gatewayAddr, networkAddr, netmask, expirationTime) is saved by node B as an
> AssociationTuple. The list of AssociationTuple's make an AssociationSet. (This
> is in accordance with RFC 3626).
OK

> 
> Now here's the part where I tried to come up with my own names, was and am
> still confused, and would like some help:
> 
> (networkAddr, netmask) is an 'Association', used by A. I used the same name as
> was already used in olsr-message-header.h.

It's not the same thing.  In olsr-header.h the struct Association {} is
namespaced inside the Hna struct, which is inside olsr::Message.  So the full
C++ identifier is actually ns3::olsr::Message::Hna::Association :-)

> 
> In the Get/Insert/Erase methods, I used HostNetAssociation to refer to
> 'Association' set of a node, which is what the node shares with the rest of the
> network through HNA messages.
> 
> Should I keep (networkAddr, netmask) as 'HostNetAssociation' rather than
> 'Assocation'? That will divide things into HostNetAssociation - HostNetAssocSet
> and AssociationTuple - AssociationSet ? Else can you please suggest what names
> I can use here? 

To remain consistent with the rfc, I think it should be InsertAssociationTuple,
EraseAssociation, etc.  Although I don't agree with the rfc (I think
"association tuple" is too vague), at least it's a documented naming.

> 
> And after the discussion I had with Tom, I think it would be better if
> RoutingProtocol::InjectRoute() is renamed to
> RoutingProtocol::AddHostNetAssociation(). What do you think?

I think the naming conventions in NS3 forbid abbreviated names like 'Net'.

Perhaps two separate methods could be added:

  1. AddHostAssociation(Ipv4Address)

  2. AddNetworkAssociation(Ipv4Address, Ipv4Mask)

_however_, I normally like code that is more intelligent.  In OLSR you don't
have have AddOlsrInterface; it just uses all the available interfaces in the
node.  Likewise, perhaps an automatic approach could be used here as well?  It
would require the code to:
  1. Go to the Ipv4 interface of the node;
  2. Get the list of routing protocols;
  3. Iterate over the list and, for each "static ipv4 routing protocol":
    3a. Iterate over the static routing entries and generate Hna message(s)
based on them.

(In reply to comment #9)


> 
> To remain consistent with the rfc, I think it should be InsertAssociationTuple,
> EraseAssociation, etc.  Although I don't agree with the rfc (I think
> "association tuple" is too vague), at least it's a documented naming.
> 

So I'll drop all the -HostNet- namings and keep it Association, Associations
and [Get/Insert/Erase]Association() for the methods. Will make the changes as
soon as you signal. :)


> > 
> > And after the discussion I had with Tom, I think it would be better if
> > RoutingProtocol::InjectRoute() is renamed to
> > RoutingProtocol::AddHostNetAssociation(). What do you think?
> 
> I think the naming conventions in NS3 forbid abbreviated names like 'Net'.
> 

How's RoutingProtocol::AddAssociation ()? :)

> Perhaps two separate methods could be added:
> 
>   1. AddHostAssociation(Ipv4Address)
> 
>   2. AddNetworkAssociation(Ipv4Address, Ipv4Mask)
> 
> _however_, I normally like code that is more intelligent.  In OLSR you don't
> have have AddOlsrInterface; it just uses all the available interfaces in the
> node.  Likewise, perhaps an automatic approach could be used here as well?  It
> would require the code to:
>   1. Go to the Ipv4 interface of the node;
>   2. Get the list of routing protocols;
>   3. Iterate over the list and, for each "static ipv4 routing protocol":
>     3a. Iterate over the static routing entries and generate Hna message(s)
> based on them.

Just wondering, wouldn't it make things easier if we add a netmask field to the
RoutingTableEntry? Anything coming in from a TC message is automatically given
a netmask of /32 whereas for the HNA messages, we specify the netmasks
separately?

And looking at the olsrd implementation
(http://www.olsr.org/docs/olsrd.conf.5.html), it seems like they expect the
user to mention the associations themselves.

(In reply to comment #10)
> (In reply to comment #9)
> 
> 
> > 
> > To remain consistent with the rfc, I think it should be InsertAssociationTuple,
> > EraseAssociation, etc.  Although I don't agree with the rfc (I think
> > "association tuple" is too vague), at least it's a documented naming.
> > 
> 
> So I'll drop all the -HostNet- namings and keep it Association, Associations
> and [Get/Insert/Erase]Association() for the methods. Will make the changes as
> soon as you signal. :)

OK, fine by me.  Just be consistent.

> 
> 
> > > 
> > > And after the discussion I had with Tom, I think it would be better if
> > > RoutingProtocol::InjectRoute() is renamed to
> > > RoutingProtocol::AddHostNetAssociation(). What do you think?
> > 
> > I think the naming conventions in NS3 forbid abbreviated names like 'Net'.
> > 
> 
> How's RoutingProtocol::AddAssociation ()? :)
> 
> > Perhaps two separate methods could be added:
> > 
> >   1. AddHostAssociation(Ipv4Address)
> > 
> >   2. AddNetworkAssociation(Ipv4Address, Ipv4Mask)
> > 
> > _however_, I normally like code that is more intelligent.  In OLSR you don't
> > have have AddOlsrInterface; it just uses all the available interfaces in the
> > node.  Likewise, perhaps an automatic approach could be used here as well?  It
> > would require the code to:
> >   1. Go to the Ipv4 interface of the node;
> >   2. Get the list of routing protocols;
> >   3. Iterate over the list and, for each "static ipv4 routing protocol":
> >     3a. Iterate over the static routing entries and generate Hna message(s)
> > based on them.
> 
> Just wondering, wouldn't it make things easier if we add a netmask field to the
> RoutingTableEntry? Anything coming in from a TC message is automatically given
> a netmask of /32 whereas for the HNA messages, we specify the netmasks
> separately?

The main problem will be speed. Right now:

  std::map<Ipv4Address, RoutingTableEntry> m_table; ///< Data structure for the
routing table.

A lookup is a simple std::map::find() operation.  If you change the key
matching algorithm (to network/mask matching), can you still use std::map at
all?

The problem is similar as with static routing.  I see static routing iterates
simply over a std::list.  It is normally not a problem with static routing if
the number of entries is low.  But OLSR has lots of /32 routes for every other
node in  the network (could be hundreds); it is not a good idea to make it a
list.

A better solution would be to have two tables, one for OLSR nodes, and a
separate table for HNA routes.  We lookup in one table first, if the lookup
fails we then try the other table.

OR..... we could just add a new Ipv4StaticRouting protocol to the list of the
protocols of the node and configure OLSR to inject HNA routes into that special
routing table.  Problem solved ;-)

> 
> And looking at the olsrd implementation
> (http://www.olsr.org/docs/olsrd.conf.5.html), it seems like they expect the
> user to mention the associations themselves.

I won't object to manual configuration.  Not a big deal.  It's your call.

(> 
> Perhaps two separate methods could be added:
> 
>   1. AddHostAssociation(Ipv4Address)
> 
>   2. AddNetworkAssociation(Ipv4Address, Ipv4Mask)

I would probably lean towards one method, because 1) can be supported by
passing an all ones mask to method 2), and because the RFC tends to deprecate
using HNA to advertise hosts (Sec 12.2):

   In HNA-messages, announcing
   reachability to an address sequence through a network- and netmask
   address is typically preferred over announcing reachability to
   individual host addresses
> 
> _however_, I normally like code that is more intelligent.  In OLSR you don't
> have have AddOlsrInterface; it just uses all the available interfaces in the
> node.  Likewise, perhaps an automatic approach could be used here as well?  It
> would require the code to:
>   1. Go to the Ipv4 interface of the node;
>   2. Get the list of routing protocols;
>   3. Iterate over the list and, for each "static ipv4 routing protocol":
>     3a. Iterate over the static routing entries and generate Hna message(s)
> based on them.

That would tend to generate HNAs for all interfaces, including OLSR active
ones.  Is that what you want?

It seems from the RFC that HNA is intended for the non-OLSR interfaces.  If we
were to add the suggested SetInterfaceNonOlsr() method, we could perhaps do it
with a flag argument
SetInterfaceNonOlsr (bool generateHna) // default true

and then have the code auto-generate HNA only for all non-OLSR configured
interfaces unless disabled by the above argument.  

Then, we could keep the AddAssociation(address/mask) for an additional manual
injection of an HNA.

(In reply to comment #12)
> (> 
> > Perhaps two separate methods could be added:
> > 
> >   1. AddHostAssociation(Ipv4Address)
> > 
> >   2. AddNetworkAssociation(Ipv4Address, Ipv4Mask)
> 
> I would probably lean towards one method, because 1) can be supported by
> passing an all ones mask to method 2), and because the RFC tends to deprecate
> using HNA to advertise hosts (Sec 12.2):
> 
>    In HNA-messages, announcing
>    reachability to an address sequence through a network- and netmask
>    address is typically preferred over announcing reachability to
>    individual host addresses

I think you're right.

> > 
> > _however_, I normally like code that is more intelligent.  In OLSR you don't
> > have have AddOlsrInterface; it just uses all the available interfaces in the
> > node.  Likewise, perhaps an automatic approach could be used here as well?  It
> > would require the code to:
> >   1. Go to the Ipv4 interface of the node;
> >   2. Get the list of routing protocols;
> >   3. Iterate over the list and, for each "static ipv4 routing protocol":
> >     3a. Iterate over the static routing entries and generate Hna message(s)
> > based on them.
> 
> That would tend to generate HNAs for all interfaces, including OLSR active
> ones.  Is that what you want?
> 
> It seems from the RFC that HNA is intended for the non-OLSR interfaces.  If we
> were to add the suggested SetInterfaceNonOlsr() method, we could perhaps do it
> with a flag argument
> SetInterfaceNonOlsr (bool generateHna) // default true
> 
> and then have the code auto-generate HNA only for all non-OLSR configured
> interfaces unless disabled by the above argument.  
> 
> Then, we could keep the AddAssociation(address/mask) for an additional manual
> injection of an HNA.

Yes, my idea by default was to inject routing entries only if those entries are
associated with a non-OLSR interface.  I wouldn't even make it configurable.

(In reply to comment #13)


> > 
> > That would tend to generate HNAs for all interfaces, including OLSR active
> > ones.  Is that what you want?
> > 
> > It seems from the RFC that HNA is intended for the non-OLSR interfaces.  If we
> > were to add the suggested SetInterfaceNonOlsr() method, we could perhaps do it
> > with a flag argument
> > SetInterfaceNonOlsr (bool generateHna) // default true
> > 
> > and then have the code auto-generate HNA only for all non-OLSR configured
> > interfaces unless disabled by the above argument.  
> > 
> > Then, we could keep the AddAssociation(address/mask) for an additional manual
> > injection of an HNA.
> 
> Yes, my idea by default was to inject routing entries only if those entries are
> associated with a non-OLSR interface.  I wouldn't even make it configurable.

So the idea is to generate HNA messages for all routing table entries which
have a non-OLSR interface as the interface field?

For example, take the following scenario:

  172.16.1.0/24   172.16.2.0/24   172.16.3.0/24
A<------------->B<------------->C<------------>D
     OLSR            non-OLSR        non-OLSR


So B should announce 172.16.2.0/24 and 172.16.3.0/24 automatically right?

Anyhow, I'll update the patch with the naming corrections and the other fixes
and show it to you before proceeding with the
mixed-interfaces/hna-auto-generation problem.

> So the idea is to generate HNA messages for all routing table entries which
> have a non-OLSR interface as the interface field?
> 
> For example, take the following scenario:
> 
>   172.16.1.0/24   172.16.2.0/24   172.16.3.0/24
> A<------------->B<------------->C<------------>D
>      OLSR            non-OLSR        non-OLSR
> 
> 
> So B should announce 172.16.2.0/24 and 172.16.3.0/24 automatically right?
> 

I don't know how B knows about 172.16.3.0/24 automatically.  I would assume
that in this case, B would automatically associate 172.16.2.0/24 and the user
would have to specify 172.16.3.0/24 as an additional associated network to B. 
I would probably not make it a programming error for the user to also manually
specify 172.16.2.0/24 despite it being autogenerated.

(In reply to comment #15)
> > So the idea is to generate HNA messages for all routing table entries which
> > have a non-OLSR interface as the interface field?
> > 
> > For example, take the following scenario:
> > 
> >   172.16.1.0/24   172.16.2.0/24   172.16.3.0/24
> > A<------------->B<------------->C<------------>D
> >      OLSR            non-OLSR        non-OLSR
> > 
> > 
> > So B should announce 172.16.2.0/24 and 172.16.3.0/24 automatically right?
> > 
> 
> I don't know how B knows about 172.16.3.0/24 automatically.  I would assume
> that in this case, B would automatically associate 172.16.2.0/24 and the user
> would have to specify 172.16.3.0/24 as an additional associated network to B. 
> I would probably not make it a programming error for the user to also manually
> specify 172.16.2.0/24 despite it being autogenerated.

I was wondering if B eventually learns about 172.16.3.0/24, should it announce
172.16.3.0/24 automatically?

But I think it's safer if we ensure that the user himself specify all the
associations (no auto-generation of HNA messages) using a method like
AddAssociation(). If required, we could later add another method that would
autmoatically add associations using AddAssociation() itself? Let me know so I
can update the patch. :)

And thanks for your time!

(In reply to comment #16)
> (In reply to comment #15)
> > > So the idea is to generate HNA messages for all routing table entries which
> > > have a non-OLSR interface as the interface field?
> > > 
> > > For example, take the following scenario:
> > > 
> > >   172.16.1.0/24   172.16.2.0/24   172.16.3.0/24
> > > A<------------->B<------------->C<------------>D
> > >      OLSR            non-OLSR        non-OLSR
> > > 
> > > 
> > > So B should announce 172.16.2.0/24 and 172.16.3.0/24 automatically right?
> > > 
> > 
> > I don't know how B knows about 172.16.3.0/24 automatically.  I would assume
> > that in this case, B would automatically associate 172.16.2.0/24 and the user
> > would have to specify 172.16.3.0/24 as an additional associated network to B. 
> > I would probably not make it a programming error for the user to also manually
> > specify 172.16.2.0/24 despite it being autogenerated.
> 
> I was wondering if B eventually learns about 172.16.3.0/24, should it announce
> 172.16.3.0/24 automatically?
> 
> But I think it's safer if we ensure that the user himself specify all the
> associations (no auto-generation of HNA messages) using a method like
> AddAssociation(). If required, we could later add another method that would
> autmoatically add associations using AddAssociation() itself? Let me know so I
> can update the patch. :)
> 
> And thanks for your time!

My opinion is that OLSR should announce routing entries of a static routing
table, filtered to include only routing entries that reference the non-OLSR
interfaces.  In this example, should the 172.16.3.0/24 network be learned by B,
won't it end up in a different routing table or routing protocol?  And can't
you have multiple static routing tables in a single node?

How about a couple of methods like these could make things clearer:

 1. AddHostNetworkAssociation (Ipv4Address, Ipv4Mask);

 2. AddRoutingTableAssociation (Ptr<Ipv4StaticRouting>);

The case 2 could be more efficient in case you have a static routing table with
high number of entries, because you avoid copying the data from the table into
the olsr agent; instead, you just copy a pointer to the table and OLSR picks
the entries from there at HNA generation time.

> 
> My opinion is that OLSR should announce routing entries of a static routing
> table, filtered to include only routing entries that reference the non-OLSR
> interfaces.  In this example, should the 172.16.3.0/24 network be learned by B,
> won't it end up in a different routing table or routing protocol?  And can't
> you have multiple static routing tables in a single node?
> 
> How about a couple of methods like these could make things clearer:
> 
>  1. AddHostNetworkAssociation (Ipv4Address, Ipv4Mask);
> 
>  2. AddRoutingTableAssociation (Ptr<Ipv4StaticRouting>);
> 
> The case 2 could be more efficient in case you have a static routing table with
> high number of entries, because you avoid copying the data from the table into
> the olsr agent; instead, you just copy a pointer to the table and OLSR picks
> the entries from there at HNA generation time.

+1

Great! I'll work on it and post on the list if I have any doubts. :)