Ns-3 Nix-vector Routing

src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc

+/* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2009 The Georgia Institute of Technology 
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Authors: Josh Pelkey <jpelkey@gatech.edu>
+ */
+
+#include <queue>
+
+#include "ns3/log.h"
+
+#include "ipv4-nix-vector-routing.h"
+
+NS_LOG_COMPONENT_DEFINE ("Ipv4NixVectorRouting");
+
+namespace ns3 {
+
+NS_OBJECT_ENSURE_REGISTERED (Ipv4NixVectorRouting);
+
+TypeId 
+Ipv4NixVectorRouting::GetTypeId (void)
+{
+  static TypeId tid = TypeId ("ns3::Ipv4NixVectorRouting")
+    .SetParent<Ipv4RoutingProtocol> ()
+    .AddConstructor<Ipv4NixVectorRouting> ()
+    ;
+  return tid;
+}
+
+Ipv4NixVectorRouting::Ipv4NixVectorRouting ()
+:m_totalNeighbors (0)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+}
+
+Ipv4NixVectorRouting::~Ipv4NixVectorRouting ()
+{
+  NS_LOG_FUNCTION_NOARGS ();
+}
+
+void
+Ipv4NixVectorRouting::SetIpv4 (Ptr<Ipv4> ipv4)
+{
+  NS_ASSERT (ipv4 != 0);
+  NS_ASSERT (m_ipv4 == 0);
+  NS_LOG_DEBUG ("Created Ipv4NixVectorProtocol");
+
+  m_ipv4 = ipv4;
+}
+
+void 
+Ipv4NixVectorRouting::DoDispose ()
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  m_node = 0;
+  m_ipv4 = 0;
+
+  Ipv4RoutingProtocol::DoDispose ();
+}
+
+
+void
+Ipv4NixVectorRouting::SetNode (Ptr<Node> node)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  m_node = node;
+}
+
+Ptr<NixVector>
+Ipv4NixVectorRouting::GetNixVector (Ptr<Node> source, Ipv4Address dest)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  Ptr<NixVector> nixVector = CreateObject<NixVector> ();
+
+  // not in cache, must build the nix vector
+  // First, we have to figure out the nodes 
+  // associated with these IPs
+  Ptr<Node> destNode = GetNodeByIp (dest);
+  if (destNode == 0)
+  {
+    NS_LOG_ERROR ("No routing path exists");
+    return 0;
+  }
+
+  // if source == dest, then we have a special case
+  // because the node is sending to itself.  have to
+  // build the nix vector a little differently
+  if (source == destNode)
+  {
+    BuildNixVectorLocal(nixVector);
+    return nixVector;
+  }
+  else
+  {
+    // otherwise proceed as normal 
+    // and build the nix vector
+    std::vector< Ptr<Node> > parentVector;
+    BFS (NodeList::GetNNodes (), source, destNode, parentVector);
+
+    if (BuildNixVector (parentVector, source->GetId (), destNode->GetId (), nixVector))

[craigdo, 2009/09/11 22:38:17]

Coding standard says use {}

Other instances below.

[jpelkey, 2009/09/12 18:34:14]

On 2009/09/11 22:38:17, craigdo wrote:
> Coding standard says use {}
> 
> Other instances below.

Done.

[Tom Henderson, 2009/09/14 03:59:44]

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;
  }

[jpelkey, 2009/09/15 04:12:54]

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.

+      return nixVector;
+    else
+    {
+      NS_LOG_ERROR ("No routing path exists");
+      return 0;
+    }
+  }
+}
+
+Ptr<NixVector>
+Ipv4NixVectorRouting::GetNixVectorInCache (Ipv4Address address)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  NixMap_t::iterator iter = m_nixCache.find (address);
+    if (iter != m_nixCache.end ())
+    {
+      NS_LOG_LOGIC ("Found Nix-vector in cache.");
+      return iter->second;
+    }
+
+  // not in cache
+  return 0;
+}
+
+Ptr<Ipv4Route>
+Ipv4NixVectorRouting::GetIpv4RouteInCache (Ipv4Address address)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  Ipv4RouteMap_t::iterator iter = m_ipv4RouteCache.find (address);
+    if (iter != m_ipv4RouteCache.end ())
+    {
+      NS_LOG_LOGIC ("Found Ipv4Route in cache.");
+      return iter->second;
+    }
+
+  // not in cache
+  return 0;
+}
+
+bool
+Ipv4NixVectorRouting::BuildNixVectorLocal (Ptr<NixVector> nixVector)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  uint32_t numberOfDevices = m_node->GetNDevices ();
+
+  // here we are building a nix vector to 
+  // ourself, so we need to find the loopback 
+  // interface and add that to the nix vector
+  Ipv4Address loopback ("127.0.0.1");
+  for (uint32_t i = 0; i < numberOfDevices; i++)
+  {
+    uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(i));
+    Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
+    if (ifAddr.GetLocal() == loopback)
+    {
+      NS_LOG_LOGIC ("Adding loopback to nix.");
+      NS_LOG_LOGIC ("Adding Nix: " << i << " with " << nixVector->BitCount (numberOfDevices) << " bits, for node " << m_node->GetId());
+      nixVector->AddNeighborIndex (i, nixVector->BitCount (numberOfDevices));
+      return true;
+    }
+  }
+  return false;
+}
+
+bool
+Ipv4NixVectorRouting::BuildNixVector (const std::vector< Ptr<Node> > & parentVector, uint32_t source, uint32_t dest, Ptr<NixVector> nixVector)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  if (source == dest)
+    return true;
+
+  if (parentVector.at(dest) == 0)

[Tom Henderson, 2009/09/14 03:59:44]

at (dest)

[jpelkey, 2009/09/15 04:12:54]

On 2009/09/14 03:59:44, Tom H. wrote:
> at (dest)

Done.

+    return false;
+
+  Ptr<Node> parentNode = parentVector.at (dest);
+
+  uint32_t numberOfDevices = parentNode->GetNDevices ();
+  uint32_t destId = 0;
+  uint32_t totalNeighbors = 0;
+
+  // scan through the net devices on the parent node
+  // and then look at the nodes adjacent to them
+  for (uint32_t i = 0; i < numberOfDevices; i++)
+  {
+    // Get a net device from the node
+    // as well as the channel, and figure
+    // out the adjacent net devices
+    Ptr<NetDevice> localNetDevice = parentNode->GetDevice (i);
+    Ptr<Channel> channel = localNetDevice->GetChannel ();
+    if (channel == 0)
+    {
+      continue;
+    }
+
+    // this function takes in the local net dev, and channnel, and
+    // writes to the netDeviceContainer the adjacent net devs
+    NetDeviceContainer netDeviceContainer;
+    GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
+
+    // Finally we can get the adjacent nodes
+    // and scan through them.  If we find the 
+    // node that matches "dest" then we can add 
+    // the index  to the nix vector.
+    // the index corresponds to the neighbor index
+    uint32_t offset = 0;
+    for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
+    {
+      Ptr<Node> remoteNode = (*iter)->GetNode ();
+
+      if (remoteNode->GetId () == dest)
+      {
+        destId = totalNeighbors + offset;
+        break;
+      }
+      offset += 1;
+    }
+
+    totalNeighbors += netDeviceContainer.GetN ();
+  }
+  m_totalNeighbors = totalNeighbors;
+  NS_LOG_LOGIC ("Adding Nix: " << destId << " with " << nixVector->BitCount (totalNeighbors) << " bits, for node " << parentNode->GetId());
+  nixVector->AddNeighborIndex (destId, nixVector->BitCount (totalNeighbors));
+
+  // recurse through parent vector, grabbin the path 

[Tom Henderson, 2009/09/14 03:59:44]

grabbing

[jpelkey, 2009/09/15 04:12:54]

On 2009/09/14 03:59:44, Tom H. wrote:
> grabbing

Done.

+  // and building the nix vector
+  BuildNixVector (parentVector, source, (parentVector.at (dest))->GetId (), nixVector);
+  return true;
+}
+
+void
+Ipv4NixVectorRouting::GetAdjacentNetDevices (Ptr<NetDevice> netDevice, Ptr<Channel> channel, NetDeviceContainer & netDeviceContainer)
+{
+  //NS_LOG_FUNCTION_NOARGS ();

[Tom Henderson, 2009/09/14 03:59:44]

why commented out?

[jpelkey, 2009/09/15 04:12:54]

On 2009/09/14 03:59:44, Tom H. wrote:
> why commented out?

Done.

+
+  for (uint32_t i = 0; i < channel->GetNDevices (); i++)
+    if (channel->GetDevice (i) != netDevice)
+      netDeviceContainer.Add(channel->GetDevice (i));

[Tom Henderson, 2009/09/14 03:59:44]

Add (channel...)

[jpelkey, 2009/09/15 04:12:54]

On 2009/09/14 03:59:44, Tom H. wrote:
> Add (channel...)

Done.

+}
+
+Ptr<Node>
+Ipv4NixVectorRouting::GetNodeByIp (Ipv4Address dest)
+{ 
+  NS_LOG_FUNCTION_NOARGS ();
+
+  NodeContainer allNodes = NodeContainer::GetGlobal ();
+  Ptr<Node> destNode;
+
+  for (NodeContainer::Iterator i = allNodes.Begin (); i != allNodes.End (); ++i)
+  {
+    Ptr<Node> node = *i;
+    Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
+    if (ipv4->GetInterfaceForAddress (dest) != -1)
+    {
+      destNode = node;
+      break;
+    }
+  }
+
+  if (!destNode)
+  {
+    NS_LOG_ERROR ("Couldn't find dest node given the IP" << dest);
+    return 0;
+  }
+
+  return destNode;
+}
+
+uint32_t
+Ipv4NixVectorRouting::FindTotalNeighbors ()
+{
+  uint32_t numberOfDevices = m_node->GetNDevices ();
+  uint32_t totalNeighbors = 0;
+
+  // scan through the net devices on the parent node
+  // and then look at the nodes adjacent to them
+  for (uint32_t i = 0; i < numberOfDevices; i++)
+  {
+    // Get a net device from the node
+    // as well as the channel, and figure
+    // out the adjacent net devices
+    Ptr<NetDevice> localNetDevice = m_node->GetDevice (i);
+    Ptr<Channel> channel = localNetDevice->GetChannel ();
+    if (channel == 0)
+    {
+      continue;
+    }
+
+    // this function takes in the local net dev, and channnel, and
+    // writes to the netDeviceContainer the adjacent net devs
+    NetDeviceContainer netDeviceContainer;
+    GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
+
+    totalNeighbors += netDeviceContainer.GetN ();
+  }
+
+  return totalNeighbors;
+}
+
+uint32_t
+Ipv4NixVectorRouting::FindNetDeviceForNixIndex (uint32_t nodeIndex, Ipv4Address & gatewayIp)
+{
+  uint32_t numberOfDevices = m_node->GetNDevices ();
+  uint32_t index = 0;
+  uint32_t totalNeighbors = 0;
+
+  // scan through the net devices on the parent node
+  // and then look at the nodes adjacent to them
+  for (uint32_t i = 0; i < numberOfDevices; i++)
+  {
+    // Get a net device from the node
+    // as well as the channel, and figure
+    // out the adjacent net devices
+    Ptr<NetDevice> localNetDevice = m_node->GetDevice (i);
+    Ptr<Channel> channel = localNetDevice->GetChannel ();
+    if (channel == 0)
+    {
+      continue;
+    }
+
+    // this function takes in the local net dev, and channnel, and
+    // writes to the netDeviceContainer the adjacent net devs
+    NetDeviceContainer netDeviceContainer;
+    GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
+
+    // check how many neighbors we have
+    if (nodeIndex < (totalNeighbors + netDeviceContainer.GetN ()))
+    {
+      // found the proper net device
+      index = i;
+      Ptr<NetDevice> gatewayDevice = netDeviceContainer.Get (nodeIndex-totalNeighbors);
+      Ptr<Node> gatewayNode = gatewayDevice->GetNode ();
+      Ptr<Ipv4> ipv4 = gatewayNode->GetObject<Ipv4> ();
+
+      uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice(gatewayDevice);
+      Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, 0);
+      gatewayIp = ifAddr.GetLocal ();
+      break;
+    }
+    totalNeighbors += netDeviceContainer.GetN ();
+  }
+
+  return index;
+}
+
+Ptr<Ipv4Route> 
+Ipv4NixVectorRouting::RouteOutput (Ptr<Packet> p, const Ipv4Header &header, uint32_t oif, Socket::SocketErrno &sockerr)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+  Ptr<Ipv4Route> rtentry;
+  Ptr<NixVector> nixVectorInCache;
+  Ptr<NixVector> nixVectorForPacket;
+
+  NS_LOG_DEBUG ("Dest IP from header: " << header.GetDestination());
+  // check if cache
+  nixVectorInCache = GetNixVectorInCache(header.GetDestination());

[Tom Henderson, 2009/09/14 03:59:44]

Destination ()  (multiple places in this file)

[jpelkey, 2009/09/15 04:12:54]

On 2009/09/14 03:59:44, Tom H. wrote:
> Destination ()  (multiple places in this file)

Done.

+
+  // not in cache
+  if (!nixVectorInCache)
+  {
+    NS_LOG_LOGIC ("Nix-vector not in cache, build: ");
+    // Build the nix-vector, given this node and the
+    // dest IP address
+    nixVectorInCache = GetNixVector (m_node, header.GetDestination());
+
+    // cache it
+    m_nixCache.insert(NixMap_t::value_type(header.GetDestination(), nixVectorInCache));

[Tom Henderson, 2009/09/14 03:59:44]

insert (NixMap_t...

[jpelkey, 2009/09/15 04:12:54]

On 2009/09/14 03:59:44, Tom H. wrote:
> insert (NixMap_t...

Done.

+  }
+
+  // path exists
+  if (nixVectorInCache)
+  {
+    NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache);
+
+    // create a new nix vector to be used, 
+    // we want to keep the cached version clean
+    nixVectorForPacket = CreateObject<NixVector> ();
+    nixVectorForPacket = nixVectorInCache->Copy(); 
+
+  
+    // Get the interface number that we go out of, by extracting
+    // from the nix-vector
+    uint32_t numberOfBits = nixVectorForPacket->BitCount (m_totalNeighbors);
+    uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
+
+    // Possibly search here in a cache for this node index 
+    // and look for a Ipv4Route.  If we have it, don't 
+    // need to do the next 3 lines.
+    rtentry = GetIpv4RouteInCache (header.GetDestination ());
+    // not in cache
+    if (!rtentry)
+    {
+      NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
+      Ipv4Address gatewayIp;
+      uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
+
+      uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
+      Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
+
+      // start filling in the Ipv4Route info
+      rtentry = Create<Ipv4Route> ();
+      rtentry->SetSource (ifAddr.GetLocal ());
+
+      // Have to set a gateway here (defaulting to zero)
+      // otherwise RouteOutput gets called twice
+      rtentry->SetGateway (gatewayIp);
+      rtentry->SetDestination (header.GetDestination ());
+      rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
+
+      sockerr = Socket::ERROR_NOTERROR;
+
+      // add rtentry to cache
+      m_ipv4RouteCache.insert(Ipv4RouteMap_t::value_type(header.GetDestination(), rtentry));
+    }
+
+    NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache << " : Remaining bits: " << nixVectorForPacket->GetRemainingBits());
+
+    // Add  nix-vector in the packet class 
+    // make sure the packet exists first
+    if (p)
+    {
+      NS_LOG_LOGIC ("Adding Nix-vector to packet: " << *nixVectorForPacket);
+      p->SetNixVector(nixVectorForPacket);

[Tom Henderson, 2009/09/14 03:59:44]

SetNixVector (...)

[jpelkey, 2009/09/15 04:12:54]

On 2009/09/14 03:59:44, Tom H. wrote:
> SetNixVector (...)

Done.

+    }
+  }
+  else // path doesn't exist
+  {
+    NS_LOG_ERROR ("No path to the dest: " << header.GetDestination());
+    sockerr = Socket::ERROR_NOROUTETOHOST;
+  }
+
+  return rtentry;
+}
+
+bool 
+Ipv4NixVectorRouting::RouteInput (Ptr<const Packet> p, const Ipv4Header &header, Ptr<const NetDevice> idev,
+                             UnicastForwardCallback ucb, MulticastForwardCallback mcb,
+                             LocalDeliverCallback lcb, ErrorCallback ecb)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  Ptr<Ipv4Route> rtentry;
+
+  // Get the nix-vector from the packet
+  Ptr<NixVector> nixVector = p->GetNixVector();
+
+  // make sure it exists, if not something
+  // went wrong
+  if (!nixVector)
+  {
+    NS_LOG_ERROR ("Nix-vector wasn't in the packet! Rebuild.");
+
+    Ptr<NixVector> nixVectorInCache;
+
+    NS_LOG_DEBUG ("Dest IP from header: " << header.GetDestination());
+
+    // check if cache
+    nixVectorInCache = GetNixVectorInCache(header.GetDestination());
+
+    // not in cache
+    if (!nixVectorInCache)
+    {
+      NS_LOG_LOGIC ("RouteInput(): Nix-vector not in cache, build: ");
+
+      // Build the nix-vector, given this node and the
+      // dest IP address
+      nixVectorInCache = GetNixVector (m_node, header.GetDestination());
+    }
+
+    // path exists
+    if (nixVectorInCache)
+    {
+      NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache);
+
+      // cache it
+      m_nixCache.insert(NixMap_t::value_type(header.GetDestination(), nixVectorInCache));
+
+      // create a new nix vector to be used, 
+      // we want to keep the cached version clean
+      Ptr<NixVector> nixVectorForPacket;
+      nixVectorForPacket = CreateObject<NixVector> ();
+      nixVectorForPacket = nixVectorInCache->Copy(); 
+
+      // Get the interface number that we go out of, by extracting
+      // from the nix-vector
+      if (m_totalNeighbors == 0)
+      {
+        m_totalNeighbors = FindTotalNeighbors ();
+      }
+      uint32_t numberOfBits = nixVectorForPacket->BitCount (m_totalNeighbors);
+      uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
+
+      rtentry = GetIpv4RouteInCache (header.GetDestination ());
+      // not in cache
+      if (!rtentry)
+      {
+        NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
+        Ipv4Address gatewayIp;
+        uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
+
+        uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
+        Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
+
+        // start filling in the Ipv4Route info
+        rtentry = Create<Ipv4Route> ();
+        rtentry->SetSource (ifAddr.GetLocal ());
+
+        // Have to set a gateway here (defaulting to zero)
+        // otherwise RouteOutput gets called twice
+        rtentry->SetGateway (Ipv4Address((uint32_t)0));
+        rtentry->SetDestination (header.GetDestination ());
+        rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
+
+        // add rtentry to cache
+        m_ipv4RouteCache.insert(Ipv4RouteMap_t::value_type(header.GetDestination(), rtentry));
+      }
+
+      NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache << " : Remaining bits: " << nixVectorForPacket->GetRemainingBits());
+
+      // Add  nix-vector in the packet class 
+      // have to copy the packet first b/c 
+      // it is const
+      Ptr<Packet> newPacket = Create<Packet> ();
+      newPacket = p->Copy();
+
+      NS_LOG_LOGIC ("Adding Nix-vector to packet: " << *nixVectorForPacket);
+      newPacket->SetNixVector(nixVectorForPacket);
+
+      // call the unicast callback
+      // local deliver is handled by Ipv4StaticRoutingImpl
+      // so this code is never even called if the packet is
+      // destined for this node.
+      ucb (rtentry, newPacket, header);
+      return true;
+    }
+    else // path doesn't exist
+    {
+      NS_LOG_ERROR ("No path to the dest: " << header.GetDestination());
+      return false;
+    }
+  }
+  else
+  {
+    // Get the interface number that we go out of, by extracting
+    // from the nix-vector
+    // TOTAL NEIGHBORS HASN'T BEEN DETERMINED YET
+    if (m_totalNeighbors == 0)
+    {
+      m_totalNeighbors = FindTotalNeighbors ();
+    }
+    uint32_t numberOfBits = nixVector->BitCount (m_totalNeighbors);
+    uint32_t nodeIndex = nixVector->ExtractNeighborIndex (numberOfBits);
+
+    rtentry = GetIpv4RouteInCache (header.GetDestination ());
+    // not in cache
+    if (!rtentry)
+    {
+      NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
+      Ipv4Address gatewayIp;
+      uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
+      uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
+      Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
+
+      // start filling in the Ipv4Route info
+      rtentry = Create<Ipv4Route> ();
+      rtentry->SetSource (ifAddr.GetLocal ());
+
+      // Have to set a gateway here (defaulting to zero)
+      // otherwise RouteOutput gets called twice
+      rtentry->SetGateway (gatewayIp);
+      rtentry->SetDestination (header.GetDestination());
+      rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
+
+      // add rtentry to cache
+      m_ipv4RouteCache.insert(Ipv4RouteMap_t::value_type(header.GetDestination(), rtentry));
+    }
+
+    NS_LOG_LOGIC ("At Node " << m_node->GetId() << ", Extracting " << numberOfBits << 
+                         " bits from Nix-vector: " << nixVector << " : " << *nixVector);
+
+    // call the unicast callback
+    // local deliver is handled by Ipv4StaticRoutingImpl
+    // so this code is never even called if the packet is
+    // destined for this node.
+    ucb (rtentry, p, header);
+
+    return true;
+  }
+}
+
+// virtual functions from Ipv4RoutingProtocol 
+void
+Ipv4NixVectorRouting::NotifyInterfaceUp (uint32_t i)
+{}
+void
+Ipv4NixVectorRouting::NotifyInterfaceDown (uint32_t i)
+{}

[Tom Henderson, 2009/09/14 03:59:44]

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?

[jpelkey, 2009/09/15 04:12:54]

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.

[Tom Henderson, 2009/09/15 04:20:52]

 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.

+void
+Ipv4NixVectorRouting::NotifyAddAddress (uint32_t interface, Ipv4InterfaceAddress address)
+{}
+void
+Ipv4NixVectorRouting::NotifyRemoveAddress (uint32_t interface, Ipv4InterfaceAddress address)
+{}
+
+bool
+Ipv4NixVectorRouting::BFS (uint32_t numberOfNodes, Ptr<Node> source, Ptr<Node> dest, std::vector< Ptr<Node> > & parentVector)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  NS_LOG_LOGIC ("Going from Node " << source->GetId() << " to Node " << dest->GetId());
+  std::queue< Ptr<Node> > greyNodeList;  // discovered nodes with unexplored children
+
+  // reset the parent vector
+  parentVector.clear ();
+  parentVector.reserve (sizeof (Ptr<Node>)*numberOfNodes);
+  parentVector.insert (parentVector.begin (), sizeof (Ptr<Node>)*numberOfNodes, 0); // initialize to 0
+
+  // Add the source node to the queue, set its parent to itself 
+  greyNodeList.push (source);
+  parentVector.at (source->GetId()) = source;
+
+  // BFS loop
+  while (greyNodeList.size () != 0)
+  {
+    Ptr<Node> currNode = greyNodeList.front ();
+ 
+    if (currNode == dest) 
+    {
+      NS_LOG_LOGIC ("Made it to Node " << currNode->GetId()); 
+      return true;
+    }
+
+
+    // Iterate over the current node's adjacent vertices
+    // and push them into the queue
+    for (uint32_t i = 0; i < (currNode->GetNDevices ()); i++)
+    {
+      // Get a net device from the node
+      // as well as the channel, and figure
+      // out the adjacent net device
+      Ptr<NetDevice> localNetDevice = currNode->GetDevice (i);
+      Ptr<Channel> channel = localNetDevice->GetChannel ();
+      if (channel == 0)
+      { 
+        continue;
+      }
+
+      // this function takes in the local net dev, and channnel, and
+      // writes to the netDeviceContainer the adjacent net devs
+      NetDeviceContainer netDeviceContainer;
+      GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
+
+      // Finally we can get the adjacent nodes
+      // and scan through them.  We push them
+      // to the greyNode queue, if they aren't 
+      // already there.
+      for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
+      {
+        Ptr<Node> remoteNode = (*iter)->GetNode ();
+
+        // check to see if this node has been pushed before
+        // by checking to see if it has a parent
+        // if it doesn't (null or 0), then set its parent and 
+        // push to the queue
+        if (parentVector.at (remoteNode->GetId ()) == 0)
+        {
+          parentVector.at (remoteNode->GetId ()) = currNode;
+          greyNodeList.push (remoteNode);
+        }
+      }
+    }
+
+    // Pop off the head grey node.  We have all its children.
+    // It is now black.
+    greyNodeList.pop ();
+
+  }
+  
+  // Didn't find the dest...
+  return false;
+}
+} // namespace ns3