1.1 --- a/src/common/nix-vector.cc Tue Sep 01 09:58:55 2009 -0400
1.2 +++ b/src/common/nix-vector.cc Thu Sep 03 16:02:47 2009 -0400
1.3 @@ -300,6 +300,7 @@
1.4 void
1.5 NixVector::DumpNixVector (std::ostream &os) const
1.6 {
1.7 + NS_LOG_FUNCTION_NOARGS ();
1.8 uint32_t i = m_nixVector.size ();
1.9 std::vector<uint32_t>::const_iterator iter = m_nixVector.end ();
1.10 do
2.1 --- a/src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc Tue Sep 01 09:58:55 2009 -0400
2.2 +++ b/src/routing/nix-vector-routing/ipv4-nix-vector-routing.cc Thu Sep 03 16:02:47 2009 -0400
2.3 @@ -41,6 +41,7 @@
2.4 }
2.5
2.6 Ipv4NixVectorRouting::Ipv4NixVectorRouting ()
2.7 +:m_totalNeighbors (0)
2.8 {
2.9 NS_LOG_FUNCTION_NOARGS ();
2.10 }
2.11 @@ -127,8 +128,8 @@
2.12 {
2.13 NS_LOG_FUNCTION_NOARGS ();
2.14
2.15 - NixMap_t::iterator iter = m_cache.find (address);
2.16 - if (iter != m_cache.end ())
2.17 + NixMap_t::iterator iter = m_nixCache.find (address);
2.18 + if (iter != m_nixCache.end ())
2.19 {
2.20 NS_LOG_LOGIC ("Found Nix-vector in cache.");
2.21 return iter->second;
2.22 @@ -138,6 +139,22 @@
2.23 return 0;
2.24 }
2.25
2.26 +Ptr<Ipv4Route>
2.27 +Ipv4NixVectorRouting::GetIpv4RouteInCache (Ipv4Address address)
2.28 +{
2.29 + NS_LOG_FUNCTION_NOARGS ();
2.30 +
2.31 + Ipv4RouteMap_t::iterator iter = m_ipv4RouteCache.find (address);
2.32 + if (iter != m_ipv4RouteCache.end ())
2.33 + {
2.34 + NS_LOG_LOGIC ("Found Ipv4Route in cache.");
2.35 + return iter->second;
2.36 + }
2.37 +
2.38 + // not in cache
2.39 + return 0;
2.40 +}
2.41 +
2.42 bool
2.43 Ipv4NixVectorRouting::BuildNixVectorLocal (Ptr<NixVector> nixVector)
2.44 {
2.45 @@ -169,8 +186,6 @@
2.46 {
2.47 NS_LOG_FUNCTION_NOARGS ();
2.48
2.49 - bool added = false;
2.50 -
2.51 if (source == dest)
2.52 return true;
2.53
2.54 @@ -180,6 +195,8 @@
2.55 Ptr<Node> parentNode = parentVector.at (dest);
2.56
2.57 uint32_t numberOfDevices = parentNode->GetNDevices ();
2.58 + uint32_t destId = 0;
2.59 + uint32_t totalNeighbors = 0;
2.60
2.61 // scan through the net devices on the parent node
2.62 // and then look at the nodes adjacent to them
2.63 @@ -204,25 +221,26 @@
2.64 // Finally we can get the adjacent nodes
2.65 // and scan through them. If we find the
2.66 // node that matches "dest" then we can add
2.67 - // the index of the parent net device to the nix vector
2.68 + // the index to the nix vector.
2.69 + // the index corresponds to the neighbor index
2.70 + uint32_t offset = 0;
2.71 for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
2.72 {
2.73 Ptr<Node> remoteNode = (*iter)->GetNode ();
2.74
2.75 if (remoteNode->GetId () == dest)
2.76 {
2.77 - NS_LOG_LOGIC ("Adding Nix: " << i << " with " << nixVector->BitCount (numberOfDevices) << " bits, for node " << parentNode->GetId());
2.78 - nixVector->AddNeighborIndex (i, nixVector->BitCount (numberOfDevices));
2.79 - added = true;
2.80 + destId = totalNeighbors + offset;
2.81 break;
2.82 }
2.83 + offset += 1;
2.84 }
2.85
2.86 - // if we already added a nix for
2.87 - // this node, can stop looping
2.88 - if (added)
2.89 - break;
2.90 + totalNeighbors += netDeviceContainer.GetN ();
2.91 }
2.92 + m_totalNeighbors = totalNeighbors;
2.93 + NS_LOG_LOGIC ("Adding Nix: " << destId << " with " << nixVector->BitCount (totalNeighbors) << " bits, for node " << parentNode->GetId());
2.94 + nixVector->AddNeighborIndex (destId, nixVector->BitCount (totalNeighbors));
2.95
2.96 // recurse through parent vector, grabbin the path
2.97 // and building the nix vector
2.98 @@ -268,6 +286,85 @@
2.99 return destNode;
2.100 }
2.101
2.102 +uint32_t
2.103 +Ipv4NixVectorRouting::FindTotalNeighbors ()
2.104 +{
2.105 + uint32_t numberOfDevices = m_node->GetNDevices ();
2.106 + uint32_t totalNeighbors = 0;
2.107 +
2.108 + // scan through the net devices on the parent node
2.109 + // and then look at the nodes adjacent to them
2.110 + for (uint32_t i = 0; i < numberOfDevices; i++)
2.111 + {
2.112 + // Get a net device from the node
2.113 + // as well as the channel, and figure
2.114 + // out the adjacent net devices
2.115 + Ptr<NetDevice> localNetDevice = m_node->GetDevice (i);
2.116 + Ptr<Channel> channel = localNetDevice->GetChannel ();
2.117 + if (channel == 0)
2.118 + {
2.119 + //NS_LOG_WARN ("GetChannel () of device " << i << " of node " << parentNode->GetId () << " returned zero.");
2.120 + continue;
2.121 + }
2.122 +
2.123 + // this function takes in the local net dev, and channnel, and
2.124 + // writes to the netDeviceContainer the adjacent net devs
2.125 + NetDeviceContainer netDeviceContainer;
2.126 + GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
2.127 +
2.128 + totalNeighbors += netDeviceContainer.GetN ();
2.129 + }
2.130 +
2.131 + return totalNeighbors;
2.132 +}
2.133 +
2.134 +uint32_t
2.135 +Ipv4NixVectorRouting::FindNetDeviceForNixIndex (uint32_t nodeIndex, Ipv4Address & gatewayIp)
2.136 +{
2.137 + uint32_t numberOfDevices = m_node->GetNDevices ();
2.138 + uint32_t index = 0;
2.139 + uint32_t totalNeighbors = 0;
2.140 +
2.141 + // scan through the net devices on the parent node
2.142 + // and then look at the nodes adjacent to them
2.143 + for (uint32_t i = 0; i < numberOfDevices; i++)
2.144 + {
2.145 + // Get a net device from the node
2.146 + // as well as the channel, and figure
2.147 + // out the adjacent net devices
2.148 + Ptr<NetDevice> localNetDevice = m_node->GetDevice (i);
2.149 + Ptr<Channel> channel = localNetDevice->GetChannel ();
2.150 + if (channel == 0)
2.151 + {
2.152 + //NS_LOG_WARN ("GetChannel () of device " << i << " of node " << parentNode->GetId () << " returned zero.");
2.153 + continue;
2.154 + }
2.155 +
2.156 + // this function takes in the local net dev, and channnel, and
2.157 + // writes to the netDeviceContainer the adjacent net devs
2.158 + NetDeviceContainer netDeviceContainer;
2.159 + GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
2.160 +
2.161 + // check how many neighbors we have
2.162 + if (nodeIndex < (totalNeighbors + netDeviceContainer.GetN ()))
2.163 + {
2.164 + // found the proper net device
2.165 + index = i;
2.166 + Ptr<NetDevice> gatewayDevice = netDeviceContainer.Get (nodeIndex-totalNeighbors);
2.167 + Ptr<Node> gatewayNode = gatewayDevice->GetNode ();
2.168 + Ptr<Ipv4> ipv4 = gatewayNode->GetObject<Ipv4> ();
2.169 +
2.170 + uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice(gatewayDevice);
2.171 + Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, 0);
2.172 + gatewayIp = ifAddr.GetLocal ();
2.173 + break;
2.174 + }
2.175 + totalNeighbors += netDeviceContainer.GetN ();
2.176 + }
2.177 +
2.178 + return index;
2.179 +}
2.180 +
2.181 Ptr<Ipv4Route>
2.182 Ipv4NixVectorRouting::RouteOutput (Ptr<Packet> p, const Ipv4Header &header, uint32_t oif, Socket::SocketErrno &sockerr)
2.183 {
2.184 @@ -289,7 +386,7 @@
2.185 nixVectorInCache = GetNixVector (m_node, header.GetDestination());
2.186
2.187 // cache it
2.188 - m_cache.insert(NixMap_t::value_type(header.GetDestination(), nixVectorInCache));
2.189 + m_nixCache.insert(NixMap_t::value_type(header.GetDestination(), nixVectorInCache));
2.190 }
2.191
2.192 // path exists
2.193 @@ -305,25 +402,41 @@
2.194
2.195 // Get the interface number that we go out of, by extracting
2.196 // from the nix-vector
2.197 - uint32_t numberOfBits = nixVectorForPacket->BitCount (m_node->GetNDevices ());
2.198 - uint32_t index = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
2.199 - uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
2.200 + uint32_t numberOfBits = nixVectorForPacket->BitCount (m_totalNeighbors);
2.201 + uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
2.202 +
2.203 + // Possibly search here in a cache for this node index
2.204 + // and look for a Ipv4Route. If we have it, don't
2.205 + // need to do the next 3 lines.
2.206 + rtentry = GetIpv4RouteInCache (header.GetDestination ());
2.207 + // not in cache
2.208 + if (!rtentry)
2.209 + {
2.210 + NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
2.211 + Ipv4Address gatewayIp;
2.212 + uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
2.213 +
2.214 + uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
2.215 + Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
2.216 +
2.217 + // start filling in the Ipv4Route info
2.218 + rtentry = Create<Ipv4Route> ();
2.219 + rtentry->SetSource (ifAddr.GetLocal ());
2.220 +
2.221 + // Have to set a gateway here (defaulting to zero)
2.222 + // otherwise RouteOutput gets called twice
2.223 + rtentry->SetGateway (gatewayIp);
2.224 + rtentry->SetDestination (header.GetDestination ());
2.225 + rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
2.226 +
2.227 + sockerr = Socket::ERROR_NOTERROR;
2.228 +
2.229 + // add rtentry to cache
2.230 + m_ipv4RouteCache.insert(Ipv4RouteMap_t::value_type(header.GetDestination(), rtentry));
2.231 + }
2.232 +
2.233 NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache << " : Remaining bits: " << nixVectorForPacket->GetRemainingBits());
2.234
2.235 - Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
2.236 -
2.237 - // start filling in the Ipv4Route info
2.238 - rtentry = Create<Ipv4Route> ();
2.239 - rtentry->SetSource (ifAddr.GetLocal ());
2.240 -
2.241 - // Have to set a gateway here (defaulting to zero)
2.242 - // otherwise RouteOutput gets called twice
2.243 - rtentry->SetGateway (Ipv4Address((uint32_t)0));
2.244 - rtentry->SetDestination (header.GetDestination ());
2.245 - rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
2.246 -
2.247 - sockerr = Socket::ERROR_NOTERROR;
2.248 -
2.249 // Add nix-vector in the packet class
2.250 // make sure the packet exists first
2.251 if (p)
2.252 @@ -387,7 +500,7 @@
2.253 NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache);
2.254
2.255 // cache it
2.256 - m_cache.insert(NixMap_t::value_type(header.GetDestination(), nixVectorInCache));
2.257 + m_nixCache.insert(NixMap_t::value_type(header.GetDestination(), nixVectorInCache));
2.258
2.259 // create a new nix vector to be used,
2.260 // we want to keep the cached version clean
2.261 @@ -397,23 +510,40 @@
2.262
2.263 // Get the interface number that we go out of, by extracting
2.264 // from the nix-vector
2.265 - uint32_t numberOfBits = nixVectorForPacket->BitCount (m_node->GetNDevices ());
2.266 - uint32_t index = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
2.267 - uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
2.268 + if (m_totalNeighbors == 0)
2.269 + {
2.270 + m_totalNeighbors = FindTotalNeighbors ();
2.271 + }
2.272 + uint32_t numberOfBits = nixVectorForPacket->BitCount (m_totalNeighbors);
2.273 + uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
2.274 +
2.275 + rtentry = GetIpv4RouteInCache (header.GetDestination ());
2.276 + // not in cache
2.277 + if (!rtentry)
2.278 + {
2.279 + NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
2.280 + Ipv4Address gatewayIp;
2.281 + uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
2.282 +
2.283 + uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
2.284 + Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
2.285 +
2.286 + // start filling in the Ipv4Route info
2.287 + rtentry = Create<Ipv4Route> ();
2.288 + rtentry->SetSource (ifAddr.GetLocal ());
2.289 +
2.290 + // Have to set a gateway here (defaulting to zero)
2.291 + // otherwise RouteOutput gets called twice
2.292 + rtentry->SetGateway (Ipv4Address((uint32_t)0));
2.293 + rtentry->SetDestination (header.GetDestination ());
2.294 + rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
2.295 +
2.296 + // add rtentry to cache
2.297 + m_ipv4RouteCache.insert(Ipv4RouteMap_t::value_type(header.GetDestination(), rtentry));
2.298 + }
2.299 +
2.300 NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache << " : Remaining bits: " << nixVectorForPacket->GetRemainingBits());
2.301
2.302 - Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
2.303 -
2.304 - // start filling in the Ipv4Route info
2.305 - rtentry = Create<Ipv4Route> ();
2.306 - rtentry->SetSource (ifAddr.GetLocal ());
2.307 -
2.308 - // Have to set a gateway here (defaulting to zero)
2.309 - // otherwise RouteOutput gets called twice
2.310 - rtentry->SetGateway (Ipv4Address((uint32_t)0));
2.311 - rtentry->SetDestination (header.GetDestination ());
2.312 - rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
2.313 -
2.314 // Add nix-vector in the packet class
2.315 // have to copy the packet first b/c
2.316 // it is const
2.317 @@ -440,24 +570,40 @@
2.318 {
2.319 // Get the interface number that we go out of, by extracting
2.320 // from the nix-vector
2.321 - uint32_t numberOfBits = nixVector->BitCount (m_node->GetNDevices ());
2.322 - uint32_t index = nixVector->ExtractNeighborIndex (numberOfBits);
2.323 - uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
2.324 + // TOTAL NEIGHBORS HASN'T BEEN DETERMINED YET
2.325 + if (m_totalNeighbors == 0)
2.326 + {
2.327 + m_totalNeighbors = FindTotalNeighbors ();
2.328 + }
2.329 + uint32_t numberOfBits = nixVector->BitCount (m_totalNeighbors);
2.330 + uint32_t nodeIndex = nixVector->ExtractNeighborIndex (numberOfBits);
2.331 +
2.332 + rtentry = GetIpv4RouteInCache (header.GetDestination ());
2.333 + // not in cache
2.334 + if (!rtentry)
2.335 + {
2.336 + NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
2.337 + Ipv4Address gatewayIp;
2.338 + uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
2.339 + uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice(m_node->GetDevice(index));
2.340 + Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
2.341 +
2.342 + // start filling in the Ipv4Route info
2.343 + rtentry = Create<Ipv4Route> ();
2.344 + rtentry->SetSource (ifAddr.GetLocal ());
2.345 +
2.346 + // Have to set a gateway here (defaulting to zero)
2.347 + // otherwise RouteOutput gets called twice
2.348 + rtentry->SetGateway (gatewayIp);
2.349 + rtentry->SetDestination (header.GetDestination());
2.350 + rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
2.351 +
2.352 + // add rtentry to cache
2.353 + m_ipv4RouteCache.insert(Ipv4RouteMap_t::value_type(header.GetDestination(), rtentry));
2.354 + }
2.355 +
2.356 NS_LOG_LOGIC ("At Node " << m_node->GetId() << ", Extracting " << numberOfBits <<
2.357 - " bits from Nix-vector: " << nixVector << " : " << *nixVector << " : index: " << index);
2.358 - NS_LOG_LOGIC ("Number of bits remaining in nix-vector: " << nixVector->GetRemainingBits());
2.359 -
2.360 - Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
2.361 -
2.362 - // start filling in the Ipv4Route info
2.363 - rtentry = Create<Ipv4Route> ();
2.364 - rtentry->SetSource (ifAddr.GetLocal ());
2.365 -
2.366 - // Have to set a gateway here (defaulting to zero)
2.367 - // otherwise RouteOutput gets called twice
2.368 - rtentry->SetGateway (Ipv4Address((uint32_t)0));
2.369 - rtentry->SetDestination (header.GetDestination());
2.370 - rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
2.371 + " bits from Nix-vector: " << nixVector << " : " << *nixVector);
2.372
2.373 // call the unicast callback
2.374 // local deliver is handled by Ipv4StaticRoutingImpl
3.1 --- a/src/routing/nix-vector-routing/ipv4-nix-vector-routing.h Tue Sep 01 09:58:55 2009 -0400
3.2 +++ b/src/routing/nix-vector-routing/ipv4-nix-vector-routing.h Thu Sep 03 16:02:47 2009 -0400
3.3 @@ -33,6 +33,7 @@
3.4 namespace ns3 {
3.5
3.6 typedef std::map<Ipv4Address, Ptr<NixVector> > NixMap_t;
3.7 +typedef std::map<Ipv4Address, Ptr<Ipv4Route> > Ipv4RouteMap_t;
3.8
3.9 class Ipv4NixVectorRouting : public Ipv4RoutingProtocol
3.10 {
3.11 @@ -42,6 +43,7 @@
3.12 static TypeId GetTypeId (void);
3.13 Ptr<NixVector> GetNixVector (Ptr<Node>, Ipv4Address);
3.14 Ptr<NixVector> GetNixVectorInCache (Ipv4Address);
3.15 + Ptr<Ipv4Route> GetIpv4RouteInCache (Ipv4Address);
3.16 void GetAdjacentNetDevices (Ptr<NetDevice>, Ptr<Channel>, NetDeviceContainer &);
3.17 Ptr<Node> GetNodeByIp (Ipv4Address);
3.18 void SetNode (Ptr<Node>);
3.19 @@ -49,6 +51,8 @@
3.20 private:
3.21 bool BuildNixVectorLocal (Ptr<NixVector> nixVector);
3.22 bool BuildNixVector (const std::vector< Ptr<Node> > & parentVector, uint32_t source, uint32_t dest, Ptr<NixVector> nixVector);
3.23 + uint32_t FindTotalNeighbors (void);
3.24 + uint32_t FindNetDeviceForNixIndex (uint32_t nodeIndex, Ipv4Address & gatewayIp);
3.25
3.26 // Breadth first search algorithm
3.27 // Param1: Vector containing all nodes in the graph
3.28 @@ -75,9 +79,11 @@
3.29 virtual void SetIpv4 (Ptr<Ipv4> ipv4);
3.30
3.31
3.32 - NixMap_t m_cache;
3.33 + NixMap_t m_nixCache;
3.34 + Ipv4RouteMap_t m_ipv4RouteCache;
3.35 Ptr<Ipv4> m_ipv4;
3.36 Ptr<Node> m_node;
3.37 + uint32_t m_totalNeighbors;
3.38 };
3.39 } // namepace ns3
3.40 #endif