Ns-3 Nix-vector Routing

[craigdo]

Took a quick look at this before starting other business.

http://codereview.appspot.com/117046/diff/1/5
File examples/nix-simple.cc (right):

http://codereview.appspot.com/117046/diff/1/5#newcode67
Line 67: Ipv4StaticRoutingHelper staticRouting;
Why have nixHelper, and staticRouting?  It seems clearer to list.Add
staticRouting and nixRouting.

http://codereview.appspot.com/117046/diff/1/8
File src/common/nix-vector.cc (right):

http://codereview.appspot.com/117046/diff/1/8#newcode168
Line 168: if (numberOfBits > 32)
Coding standard says to add braces even if single statement

http://codereview.appspot.com/117046/diff/1/8#newcode306
Line 306: do
I'm curious why this isn't a for loop.  That would seem more natural.  What
happens if this list is empty?  Can it ever be?

http://codereview.appspot.com/117046/diff/1/8#newcode312
Line 312: if (m_totalBitSize == 32)
Coding standard says use {}.  Many more instances follow this one.

http://codereview.appspot.com/117046/diff/1/8#newcode342
Line 342: // of bits needed (essentailly, log2(numberOfNeighbors-1)
essentially

http://codereview.appspot.com/117046/diff/1/8#newcode404
Line 404: }
It would be nice to see some unit tests for this.

http://codereview.appspot.com/117046/diff/1/10
File src/common/packet-metadata.cc (right):

http://codereview.appspot.com/117046/diff/1/10#newcode1201
Line 1201: PacketMetadata::SetNixVector (Ptr<NixVector> nixVector)
I'm a bit concerned about this.  PacketMetadata is generic.  We are adding a
strongly typed pointer to this generic object to support Nix vectors.  What
happens if I want to do something a little different.  Do I add a NickVector
pointer to PacketMetadata?  How about a NackVector to the PacketMetadata later
on.  Why isn't this generic?  Does this point to a weakness in PacketMetadata
that needs to be addressed?

http://codereview.appspot.com/117046/diff/1/12
File src/common/packet.cc (right):

http://codereview.appspot.com/117046/diff/1/12#newcode214
Line 214: Packet::SetNixVector (Ptr<NixVector> nixVector)
Again, I'm concerned about this kind of specific method in a generic packet. 
What happens if I want to add other things like this?  Packet explodes with
methods to SetNickVector or SetNackVector, etc?  Won't this lead to the dreaded
fragile base class?

http://codereview.appspot.com/117046/diff/1/18
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc (right):

http://codereview.appspot.com/117046/diff/1/18#newcode116
Line 116: if (BuildNixVector (parentVector, source->GetId (), destNode->GetId
(), nixVector))
Coding standard says use {}

Other instances below.

http://codereview.appspot.com/117046/diff/1/19
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.h (right):

http://codereview.appspot.com/117046/diff/1/19#newcode41
Line 41: Ipv4NixVectorRouting ();
Needs Doxygen

[jpelkey]

Cleanup after Craig's initial review.  Patch set 2 posted.

http://codereview.appspot.com/117046/diff/1/5
File examples/nix-simple.cc (right):

http://codereview.appspot.com/117046/diff/1/5#newcode67
Line 67: Ipv4StaticRoutingHelper staticRouting;
On 2009/09/11 22:38:17, craigdo wrote:
> Why have nixHelper, and staticRouting?  It seems clearer to list.Add
> staticRouting and nixRouting.

Done.

http://codereview.appspot.com/117046/diff/1/8
File src/common/nix-vector.cc (right):

http://codereview.appspot.com/117046/diff/1/8#newcode168
Line 168: if (numberOfBits > 32)
On 2009/09/11 22:38:17, craigdo wrote:
> Coding standard says to add braces even if single statement

Done.

http://codereview.appspot.com/117046/diff/1/8#newcode306
Line 306: do
On 2009/09/11 22:38:17, craigdo wrote:
> I'm curious why this isn't a for loop.  That would seem more natural.  What
> happens if this list is empty?  Can it ever be?

I was iterating in reverse and "do, while" was just the first thing that came to
my mind.  I changed this to a for loop with a reverse iterator.  Not an issue
now, but to answer your question, the list can't be empty, NixVector constructor
pushes back an entry.

http://codereview.appspot.com/117046/diff/1/8#newcode312
Line 312: if (m_totalBitSize == 32)
On 2009/09/11 22:38:17, craigdo wrote:
> Coding standard says use {}.  Many more instances follow this one.

Done.

http://codereview.appspot.com/117046/diff/1/8#newcode342
Line 342: // of bits needed (essentailly, log2(numberOfNeighbors-1)
On 2009/09/11 22:38:17, craigdo wrote:
> essentially

Done.

http://codereview.appspot.com/117046/diff/1/8#newcode404
Line 404: }
On 2009/09/11 22:38:17, craigdo wrote:
> It would be nice to see some unit tests for this.

I will start putting some together.

http://codereview.appspot.com/117046/diff/1/10
File src/common/packet-metadata.cc (right):

http://codereview.appspot.com/117046/diff/1/10#newcode1201
Line 1201: PacketMetadata::SetNixVector (Ptr<NixVector> nixVector)
On 2009/09/11 22:38:17, craigdo wrote:
> I'm a bit concerned about this.  PacketMetadata is generic.  We are adding a
> strongly typed pointer to this generic object to support Nix vectors.  What
> happens if I want to do something a little different.  Do I add a NickVector
> pointer to PacketMetadata?  How about a NackVector to the PacketMetadata later
> on.  Why isn't this generic?  Does this point to a weakness in PacketMetadata
> that needs to be addressed?

I understand the concern.  It is my understanding the packet-metadata is for
things such as unique ID, which is useful for the simulation but doesn't belong
inside the packet.  The main issue is the nix-vector is something that must
travel along with the packet (much like the unique id).  To me, packet-metadata
was the appropriate place for this.  I am open to other suggestions.  We tried
packet tags a while back, but we were unable to use them because of a limiting
tag size.

http://codereview.appspot.com/117046/diff/1/12
File src/common/packet.cc (right):

http://codereview.appspot.com/117046/diff/1/12#newcode214
Line 214: Packet::SetNixVector (Ptr<NixVector> nixVector)
On 2009/09/11 22:38:17, craigdo wrote:
> Again, I'm concerned about this kind of specific method in a generic packet. 
> What happens if I want to add other things like this?  Packet explodes with
> methods to SetNickVector or SetNackVector, etc?  Won't this lead to the
dreaded
> fragile base class?

These functions only exist because there wasn't a way to return the metadata
within Packet.  So in order to get and set the nix vector in packet-metadata, I
had to add these functions in packet in order to access the packet-metadata
functions, get/set nix-vector.  I was following the same structure as GetUid in
Packet.

http://codereview.appspot.com/117046/diff/1/18
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc (right):

http://codereview.appspot.com/117046/diff/1/18#newcode116
Line 116: if (BuildNixVector (parentVector, source->GetId (), destNode->GetId
(), nixVector))
On 2009/09/11 22:38:17, craigdo wrote:
> Coding standard says use {}
> 
> Other instances below.

Done.

http://codereview.appspot.com/117046/diff/1/19
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.h (right):

http://codereview.appspot.com/117046/diff/1/19#newcode41
Line 41: Ipv4NixVectorRouting ();
On 2009/09/11 22:38:17, craigdo wrote:
> Needs Doxygen

I moved most of these to private, as they should be.  Documented GetTypeId and
SetNode.

[Tom Henderson]

Summary of main open issues I found:
1) does not correctly handle bridge devices.
2) does not take any actions for interface up/down or address
deletion/insertion.  I think that it should, conservatively, cause a flush of
all caches globally, but I am not sure how to do that.

http://codereview.appspot.com/117046/diff/1/18
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc (right):

http://codereview.appspot.com/117046/diff/1/18#newcode116
Line 116: if (BuildNixVector (parentVector, source->GetId (), destNode->GetId
(), nixVector))
On 2009/09/11 22:38:17, craigdo wrote:
> Coding standard says use {}
> 
> Other instances below.

Coding style document, and GNU style, permits this (single statement blocks
without braces), but the prevailing ns-3 style is to always use braces.  

What is not followed here, however, is the indentation on braces, according to
GNU style.  

if (test)
  {
    statement;
  }

http://codereview.appspot.com/117046/diff/1/18#newcode192
Line 192: if (parentVector.at(dest) == 0)
at (dest)

http://codereview.appspot.com/117046/diff/1/18#newcode244
Line 244: // recurse through parent vector, grabbin the path
grabbing

http://codereview.appspot.com/117046/diff/1/18#newcode253
Line 253: //NS_LOG_FUNCTION_NOARGS ();
why commented out?

http://codereview.appspot.com/117046/diff/1/18#newcode257
Line 257: netDeviceContainer.Add(channel->GetDevice (i));
Add (channel...)

http://codereview.appspot.com/117046/diff/1/18#newcode375
Line 375: nixVectorInCache = GetNixVectorInCache(header.GetDestination());
Destination ()  (multiple places in this file)

http://codereview.appspot.com/117046/diff/1/18#newcode386
Line 386: m_nixCache.insert(NixMap_t::value_type(header.GetDestination(),
nixVectorInCache));
insert (NixMap_t...

http://codereview.appspot.com/117046/diff/1/18#newcode442
Line 442: p->SetNixVector(nixVectorForPacket);
SetNixVector (...)

http://codereview.appspot.com/117046/diff/1/18#newcode616
Line 616: {}
Shouldn't these events flush any caches?

What happens in general when a run-time topology change happens-- shouldn't
Nix-vector data be flushed globally?

http://codereview.appspot.com/117046/diff/1/20
File src/routing/nix-vector-routing/nix-vector-routing.h (right):

http://codereview.appspot.com/117046/diff/1/20#newcode35
Line 35: * adaptation to link failures.
Add comment that it does not apply to IPv6

http://codereview.appspot.com/117046/diff/49/1021
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc (right):

http://codereview.appspot.com/117046/diff/49/1021#newcode664
Line 664: // and push them into the queue
This does not correctly handle bridge devices.  I double checked this with
csma-bridge.cc.  There is code in the global routing code that probably could be
ported over.

[jpelkey]

http://codereview.appspot.com/117046/diff/1/18
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc (right):

http://codereview.appspot.com/117046/diff/1/18#newcode116
Line 116: if (BuildNixVector (parentVector, source->GetId (), destNode->GetId
(), nixVector))
On 2009/09/14 03:59:44, Tom H. wrote:
> On 2009/09/11 22:38:17, craigdo wrote:
> > Coding standard says use {}
> > 
> > Other instances below.
> 
> Coding style document, and GNU style, permits this (single statement blocks
> without braces), but the prevailing ns-3 style is to always use braces.  
> 
> What is not followed here, however, is the indentation on braces, according to
> GNU style.  
> 
> if (test)
>   {
>     statement;
>   }
> 

Hopefully I fixed all these indention issues.

http://codereview.appspot.com/117046/diff/1/18#newcode192
Line 192: if (parentVector.at(dest) == 0)
On 2009/09/14 03:59:44, Tom H. wrote:
> at (dest)

Done.

http://codereview.appspot.com/117046/diff/1/18#newcode244
Line 244: // recurse through parent vector, grabbin the path
On 2009/09/14 03:59:44, Tom H. wrote:
> grabbing

Done.

http://codereview.appspot.com/117046/diff/1/18#newcode253
Line 253: //NS_LOG_FUNCTION_NOARGS ();
On 2009/09/14 03:59:44, Tom H. wrote:
> why commented out?

Done.

http://codereview.appspot.com/117046/diff/1/18#newcode257
Line 257: netDeviceContainer.Add(channel->GetDevice (i));
On 2009/09/14 03:59:44, Tom H. wrote:
> Add (channel...)

Done.

http://codereview.appspot.com/117046/diff/1/18#newcode375
Line 375: nixVectorInCache = GetNixVectorInCache(header.GetDestination());
On 2009/09/14 03:59:44, Tom H. wrote:
> Destination ()  (multiple places in this file)

Done.

http://codereview.appspot.com/117046/diff/1/18#newcode386
Line 386: m_nixCache.insert(NixMap_t::value_type(header.GetDestination(),
nixVectorInCache));
On 2009/09/14 03:59:44, Tom H. wrote:
> insert (NixMap_t...

Done.

http://codereview.appspot.com/117046/diff/1/18#newcode442
Line 442: p->SetNixVector(nixVectorForPacket);
On 2009/09/14 03:59:44, Tom H. wrote:
> SetNixVector (...)

Done.

http://codereview.appspot.com/117046/diff/1/18#newcode616
Line 616: {}
On 2009/09/14 03:59:44, Tom H. wrote:
> Shouldn't these events flush any caches?
> 
> What happens in general when a run-time topology change happens-- shouldn't
> Nix-vector data be flushed globally?

Agreed.  I'll simply flush the caches for now.  I'm using the
NotifyInterfaceUp/Down/AddAddress/RemoveAddress to trigger the flush.  The only
problem with this is it will call flush when the topology is being built.  Also,
I tested this with dynamic-global-routing (changed to use nix-vectors).  Based
on the log and the trace, it seems to function correctly; though, for some
reason with nix, 8 more packets are received by node 6.  Could this be due to
nix-vector taking zero simulation time to flush and build the vectors?  I wasn't
sure if global routing also took zero time or not.

http://codereview.appspot.com/117046/diff/1/20
File src/routing/nix-vector-routing/nix-vector-routing.h (right):

http://codereview.appspot.com/117046/diff/1/20#newcode35
Line 35: * adaptation to link failures.
On 2009/09/14 03:59:44, Tom H. wrote:
> Add comment that it does not apply to IPv6

Done.

http://codereview.appspot.com/117046/diff/49/1021
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc (right):

http://codereview.appspot.com/117046/diff/49/1021#newcode664
Line 664: // and push them into the queue
On 2009/09/14 03:59:46, Tom H. wrote:
> This does not correctly handle bridge devices.  I double checked this with
> csma-bridge.cc.  There is code in the global routing code that probably could
be
> ported over.

It took me a while to get this figured out, but I just tested with
bridge-one-hop and it works.  I actually had to add the logic in
GetAdjacentNetDevices, which is called in quite a few functions, including this
one.

[Tom Henderson]

http://codereview.appspot.com/117046/diff/1/18
File src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc (right):

http://codereview.appspot.com/117046/diff/1/18#newcode616
Line 616: {}
 Could this be due to
> nix-vector taking zero simulation time to flush and build the vectors?  I
wasn't
> sure if global routing also took zero time or not.

If you look at the sequence of events in dynamic-global-routing.cc, there are
some periods of time during which there may be packets lost because there is a
delay to ask the code to recompute routes.  This is intentional, to show that
you need to explicitly call Recompute() to get packets flowing again.  So, I am
not surprised that NixVector has some more packets because it responds
instantaneously.

[Mathieu Lacage]

I am not sure why you have put this in the packet metadata class. This class
records information about the type of the headers and trailers which are present
in a packet so, logically, it does not have much to do with a nix vector.
Instead, it probably makes much more sense to move this to the Packet class
itself.

I think I had pointed this out to you before but I don't believe your current
implementation is correct with regard to packet copies. i.e., if I call
Packet::Copy, both packets will share the same underlying nix vector and if  you
modify the content of the nix vector in a node, the other nodes who still have a
copy of that packet in their  outgoing queues will see the modified nix vector,
hence resulting in really weird results. 

The easiest way to avoid this problem would be to create a deep copy of the nix
vector in Packet::Copy. That could be a potential performance problem: if you
can come up with a more efficient way to making it robust, it is fine with me
but if I am right about the potential problem, the current implementation cannot
go in as-is.

http://codereview.appspot.com/117046/diff/1030/1038
File src/common/nix-vector.h (right):

http://codereview.appspot.com/117046/diff/1030/1038#newcode103
Line 103: NixBits_t GetNixVector (void);
appears to be unused. Kill ? If so, you can make NixBits_t private

[jpelkey]

On 2009/09/15 10:56:11, Mathieu Lacage wrote:
> I am not sure why you have put this in the packet metadata class. This class
> records information about the type of the headers and trailers which are
present
> in a packet so, logically, it does not have much to do with a nix vector.
> Instead, it probably makes much more sense to move this to the Packet class
> itself.
> 

Alright, I moved it over to Packet.

> I think I had pointed this out to you before but I don't believe your current
> implementation is correct with regard to packet copies. i.e., if I call
> Packet::Copy, both packets will share the same underlying nix vector and if 
you
> modify the content of the nix vector in a node, the other nodes who still have
a
> copy of that packet in their  outgoing queues will see the modified nix
vector,
> hence resulting in really weird results. 
> 
> The easiest way to avoid this problem would be to create a deep copy of the
nix
> vector in Packet::Copy. That could be a potential performance problem: if you
> can come up with a more efficient way to making it robust, it is fine with me
> but if I am right about the potential problem, the current implementation
cannot
> go in as-is.
> 

I've modified it to do a deep copy of the nix-vector when the packet is copied. 
Thanks for catching this, could have caused some headaches for me in the future.

> http://codereview.appspot.com/117046/diff/1030/1038
> File src/common/nix-vector.h (right):
> 
> http://codereview.appspot.com/117046/diff/1030/1038#newcode103
> Line 103: NixBits_t GetNixVector (void);
> appears to be unused. Kill ? If so, you can make NixBits_t private

Done.

[Mathieu Lacage]

The patch looks good for merging.

+1

http://codereview.appspot.com/117046/diff/116/1132
File src/common/packet.h (right):

http://codereview.appspot.com/117046/diff/116/1132#newcode31
Line 31: #include "nix-vector.h"
you don't need the include because you have a Ptr<> only. Just add a forward
declaration of NixVector below

http://codereview.appspot.com/117046/diff/116/1132#newcode38
Line 38: 
here, add:
class NixVector;
and it should still work if you include nix-vector.h from packet.cc