A Discrete-Event Network Simulator
API
ipv4-nix-vector-routing.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2009 The Georgia Institute of Technology
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Authors: Josh Pelkey <jpelkey@gatech.edu>
19  */
20 
21 #include <queue>
22 #include <iomanip>
23 
24 #include "ns3/log.h"
25 #include "ns3/abort.h"
26 #include "ns3/names.h"
27 #include "ns3/ipv4-list-routing.h"
28 #include "ns3/loopback-net-device.h"
29 
31 
32 namespace ns3 {
33 
34 NS_LOG_COMPONENT_DEFINE ("Ipv4NixVectorRouting");
35 
36 NS_OBJECT_ENSURE_REGISTERED (Ipv4NixVectorRouting);
37 
40 
41 TypeId
43 {
44  static TypeId tid = TypeId ("ns3::Ipv4NixVectorRouting")
46  .SetGroupName ("NixVectorRouting")
47  .AddConstructor<Ipv4NixVectorRouting> ()
48  ;
49  return tid;
50 }
51 
53  : m_totalNeighbors (0)
54 {
56 }
57 
59 {
61 }
62 
63 void
65 {
66  NS_ASSERT (ipv4 != 0);
67  NS_ASSERT (m_ipv4 == 0);
68  NS_LOG_DEBUG ("Created Ipv4NixVectorProtocol");
69 
70  m_ipv4 = ipv4;
71 }
72 
73 void
75 {
77 
78  m_node = 0;
79  m_ipv4 = 0;
80 
82 }
83 
84 
85 void
87 {
89 
90  m_node = node;
91 }
92 
93 void
95 {
97  NodeList::Iterator listEnd = NodeList::End ();
98  for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++)
99  {
100  Ptr<Node> node = *i;
102  if (!rp)
103  {
104  continue;
105  }
106  NS_LOG_LOGIC ("Flushing Nix caches.");
107  rp->FlushNixCache ();
108  rp->FlushIpv4RouteCache ();
109  }
110 
111  // IPv4 address to node mapping is potentially invalid so clear it.
112  // Will be repopulated in lazy evaluation when mapping is needed.
113  g_ipv4AddressToNodeMap.clear ();
114 }
115 
116 void
118 {
120  m_nixCache.clear ();
121 }
122 
123 void
125 {
127  m_ipv4RouteCache.clear ();
128 }
129 
132 {
134 
135  Ptr<NixVector> nixVector = Create<NixVector> ();
136 
137  // not in cache, must build the nix vector
138  // First, we have to figure out the nodes
139  // associated with these IPs
140  Ptr<Node> destNode = GetNodeByIp (dest);
141  if (destNode == 0)
142  {
143  NS_LOG_ERROR ("No routing path exists");
144  return 0;
145  }
146 
147  // if source == dest, then we have a special case
150  if (source == destNode)
151  {
152  NS_LOG_DEBUG ("Do not process packets to self");
153  return 0;
154  }
155  else
156  {
157  // otherwise proceed as normal
158  // and build the nix vector
159  std::vector< Ptr<Node> > parentVector;
160 
161  BFS (NodeList::GetNNodes (), source, destNode, parentVector, oif);
162 
163  if (BuildNixVector (parentVector, source->GetId (), destNode->GetId (), nixVector))
164  {
165  return nixVector;
166  }
167  else
168  {
169  NS_LOG_ERROR ("No routing path exists");
170  return 0;
171  }
172  }
173 }
174 
177 {
179 
181 
182  NixMap_t::iterator iter = m_nixCache.find (address);
183  if (iter != m_nixCache.end ())
184  {
185  NS_LOG_LOGIC ("Found Nix-vector in cache.");
186  return iter->second;
187  }
188 
189  // not in cache
190  return 0;
191 }
192 
195 {
197 
199 
200  Ipv4RouteMap_t::iterator iter = m_ipv4RouteCache.find (address);
201  if (iter != m_ipv4RouteCache.end ())
202  {
203  NS_LOG_LOGIC ("Found Ipv4Route in cache.");
204  return iter->second;
205  }
206 
207  // not in cache
208  return 0;
209 }
210 
211 bool
213 {
215 
216  uint32_t numberOfDevices = m_node->GetNDevices ();
217 
218  // here we are building a nix vector to
219  // ourself, so we need to find the loopback
220  // interface and add that to the nix vector
221  Ipv4Address loopback ("127.0.0.1");
222  for (uint32_t i = 0; i < numberOfDevices; i++)
223  {
224  uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->GetDevice (i));
225  Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
226  if (ifAddr.GetLocal () == loopback)
227  {
228  NS_LOG_LOGIC ("Adding loopback to nix.");
229  NS_LOG_LOGIC ("Adding Nix: " << i << " with " << nixVector->BitCount (numberOfDevices)
230  << " bits, for node " << m_node->GetId ());
231  nixVector->AddNeighborIndex (i, nixVector->BitCount (numberOfDevices));
232  return true;
233  }
234  }
235  return false;
236 }
237 
238 bool
239 Ipv4NixVectorRouting::BuildNixVector (const std::vector< Ptr<Node> > & parentVector, uint32_t source, uint32_t dest, Ptr<NixVector> nixVector) const
240 {
242 
243  if (source == dest)
244  {
245  return true;
246  }
247 
248  if (parentVector.at (dest) == 0)
249  {
250  return false;
251  }
252 
253  Ptr<Node> parentNode = parentVector.at (dest);
254 
255  uint32_t numberOfDevices = parentNode->GetNDevices ();
256  uint32_t destId = 0;
257  uint32_t totalNeighbors = 0;
258 
259  // scan through the net devices on the parent node
260  // and then look at the nodes adjacent to them
261  for (uint32_t i = 0; i < numberOfDevices; i++)
262  {
263  // Get a net device from the node
264  // as well as the channel, and figure
265  // out the adjacent net devices
266  Ptr<NetDevice> localNetDevice = parentNode->GetDevice (i);
267  if (localNetDevice->IsBridge ())
268  {
269  continue;
270  }
271  Ptr<Channel> channel = localNetDevice->GetChannel ();
272  if (channel == 0)
273  {
274  continue;
275  }
276 
277  // this function takes in the local net dev, and channel, and
278  // writes to the netDeviceContainer the adjacent net devs
279  NetDeviceContainer netDeviceContainer;
280  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
281 
282  // Finally we can get the adjacent nodes
283  // and scan through them. If we find the
284  // node that matches "dest" then we can add
285  // the index to the nix vector.
286  // the index corresponds to the neighbor index
287  uint32_t offset = 0;
288  for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
289  {
290  Ptr<Node> remoteNode = (*iter)->GetNode ();
291 
292  if (remoteNode->GetId () == dest)
293  {
294  destId = totalNeighbors + offset;
295  }
296  offset += 1;
297  }
298 
299  totalNeighbors += netDeviceContainer.GetN ();
300  }
301  NS_LOG_LOGIC ("Adding Nix: " << destId << " with "
302  << nixVector->BitCount (totalNeighbors) << " bits, for node " << parentNode->GetId ());
303  nixVector->AddNeighborIndex (destId, nixVector->BitCount (totalNeighbors));
304 
305  // recurse through parent vector, grabbing the path
306  // and building the nix vector
307  BuildNixVector (parentVector, source, (parentVector.at (dest))->GetId (), nixVector);
308  return true;
309 }
310 
311 void
313 {
315 
316  for (std::size_t i = 0; i < channel->GetNDevices (); i++)
317  {
318  Ptr<NetDevice> remoteDevice = channel->GetDevice (i);
319  if (remoteDevice != netDevice)
320  {
321  Ptr<BridgeNetDevice> bd = NetDeviceIsBridged (remoteDevice);
322  // we have a bridged device, we need to add all
323  // bridged devices
324  if (bd)
325  {
326  NS_LOG_LOGIC ("Looking through bridge ports of bridge net device " << bd);
327  for (uint32_t j = 0; j < bd->GetNBridgePorts (); ++j)
328  {
329  Ptr<NetDevice> ndBridged = bd->GetBridgePort (j);
330  if (ndBridged == remoteDevice)
331  {
332  NS_LOG_LOGIC ("That bridge port is me, don't walk backward");
333  continue;
334  }
335  Ptr<Channel> chBridged = ndBridged->GetChannel ();
336  if (chBridged == 0)
337  {
338  continue;
339  }
340  GetAdjacentNetDevices (ndBridged, chBridged, netDeviceContainer);
341  }
342  }
343  else
344  {
345  netDeviceContainer.Add (channel->GetDevice (i));
346  }
347  }
348  }
349 }
350 
351 void
353 {
355 
356  for (NodeList::Iterator it = NodeList::Begin (); it != NodeList::End (); ++it)
357  {
358  Ptr<Node> node = *it;
359  Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
360 
361  if(ipv4)
362  {
363  uint32_t numberOfDevices = node->GetNDevices ();
364 
365  for (uint32_t deviceId = 0; deviceId < numberOfDevices; deviceId++)
366  {
367  Ptr<NetDevice> device = node->GetDevice (deviceId);
368 
369  // If this is not a loopback device add the IPv4 address to the map
370  if ( !DynamicCast<LoopbackNetDevice>(device) )
371  {
372  int32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (node->GetDevice (deviceId));
373  if (interfaceIndex != -1)
374  {
375  uint32_t numberOfAddresses = ipv4->GetNAddresses (interfaceIndex);
376  for (uint32_t addressIndex = 0; addressIndex < numberOfAddresses; addressIndex++)
377  {
378  Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, addressIndex);
379  Ipv4Address addr = ifAddr.GetLocal ();
380 
382  "Duplicate IPv4 address (" << addr << ") found during NIX Vector map construction for node " << node->GetId ());
383 
384  NS_LOG_LOGIC ("Adding IPv4 address " << addr << " for node " << node->GetId () << " to NIX Vector IPv4 address to node map");
385  g_ipv4AddressToNodeMap[addr] = node;
386  }
387  }
388  }
389  }
390  }
391  }
392 }
393 
394 Ptr<Node>
396 {
398 
399  // Populate lookup table if is empty.
400  if ( g_ipv4AddressToNodeMap.empty () )
401  {
403  }
404 
405  Ptr<Node> destNode;
406 
407  Ipv4AddressToNodeMap::iterator iter = g_ipv4AddressToNodeMap.find(dest);
408 
409  if(iter == g_ipv4AddressToNodeMap.end ())
410  {
411  NS_LOG_ERROR ("Couldn't find dest node given the IP" << dest);
412  destNode = 0;
413  }
414  else
415  {
416  destNode = iter -> second;
417  }
418 
419  return destNode;
420 }
421 
422 uint32_t
424 {
425  uint32_t numberOfDevices = node->GetNDevices ();
426  uint32_t totalNeighbors = 0;
427 
428  // scan through the net devices on the parent node
429  // and then look at the nodes adjacent to them
430  for (uint32_t i = 0; i < numberOfDevices; i++)
431  {
432  // Get a net device from the node
433  // as well as the channel, and figure
434  // out the adjacent net devices
435  Ptr<NetDevice> localNetDevice = node->GetDevice (i);
436  Ptr<Channel> channel = localNetDevice->GetChannel ();
437  if (channel == 0)
438  {
439  continue;
440  }
441 
442  // this function takes in the local net dev, and channel, and
443  // writes to the netDeviceContainer the adjacent net devs
444  NetDeviceContainer netDeviceContainer;
445  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
446 
447  totalNeighbors += netDeviceContainer.GetN ();
448  }
449 
450  return totalNeighbors;
451 }
452 
455 {
456  NS_LOG_FUNCTION (nd);
457 
458  Ptr<Node> node = nd->GetNode ();
459  uint32_t nDevices = node->GetNDevices ();
460 
461  //
462  // There is no bit on a net device that says it is being bridged, so we have
463  // to look for bridges on the node to which the device is attached. If we
464  // find a bridge, we need to look through its bridge ports (the devices it
465  // bridges) to see if we find the device in question.
466  //
467  for (uint32_t i = 0; i < nDevices; ++i)
468  {
469  Ptr<NetDevice> ndTest = node->GetDevice (i);
470  NS_LOG_LOGIC ("Examine device " << i << " " << ndTest);
471 
472  if (ndTest->IsBridge ())
473  {
474  NS_LOG_LOGIC ("device " << i << " is a bridge net device");
475  Ptr<BridgeNetDevice> bnd = ndTest->GetObject<BridgeNetDevice> ();
476  NS_ABORT_MSG_UNLESS (bnd, "Ipv4NixVectorRouting::NetDeviceIsBridged (): GetObject for <BridgeNetDevice> failed");
477 
478  for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
479  {
480  NS_LOG_LOGIC ("Examine bridge port " << j << " " << bnd->GetBridgePort (j));
481  if (bnd->GetBridgePort (j) == nd)
482  {
483  NS_LOG_LOGIC ("Net device " << nd << " is bridged by " << bnd);
484  return bnd;
485  }
486  }
487  }
488  }
489  NS_LOG_LOGIC ("Net device " << nd << " is not bridged");
490  return 0;
491 }
492 
493 uint32_t
494 Ipv4NixVectorRouting::FindNetDeviceForNixIndex (Ptr<Node> node, uint32_t nodeIndex, Ipv4Address & gatewayIp) const
495 {
496  uint32_t numberOfDevices = node->GetNDevices ();
497  uint32_t index = 0;
498  uint32_t totalNeighbors = 0;
499 
500  // scan through the net devices on the parent node
501  // and then look at the nodes adjacent to them
502  for (uint32_t i = 0; i < numberOfDevices; i++)
503  {
504  // Get a net device from the node
505  // as well as the channel, and figure
506  // out the adjacent net devices
507  Ptr<NetDevice> localNetDevice = node->GetDevice (i);
508  Ptr<Channel> channel = localNetDevice->GetChannel ();
509  if (channel == 0)
510  {
511  continue;
512  }
513 
514  // this function takes in the local net dev, and channel, and
515  // writes to the netDeviceContainer the adjacent net devs
516  NetDeviceContainer netDeviceContainer;
517  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
518 
519  // check how many neighbors we have
520  if (nodeIndex < (totalNeighbors + netDeviceContainer.GetN ()))
521  {
522  // found the proper net device
523  index = i;
524  Ptr<NetDevice> gatewayDevice = netDeviceContainer.Get (nodeIndex-totalNeighbors);
525  Ptr<Node> gatewayNode = gatewayDevice->GetNode ();
526  Ptr<Ipv4> ipv4 = gatewayNode->GetObject<Ipv4> ();
527 
528  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (gatewayDevice);
529  Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, 0);
530  gatewayIp = ifAddr.GetLocal ();
531  break;
532  }
533  totalNeighbors += netDeviceContainer.GetN ();
534  }
535 
536  return index;
537 }
538 
541 {
543  Ptr<Ipv4Route> rtentry;
544  Ptr<NixVector> nixVectorInCache;
545  Ptr<NixVector> nixVectorForPacket;
546 
548 
549  NS_LOG_DEBUG ("Dest IP from header: " << header.GetDestination ());
550  // check if cache
551  nixVectorInCache = GetNixVectorInCache (header.GetDestination ());
552 
553  // not in cache
554  if (!nixVectorInCache)
555  {
556  NS_LOG_LOGIC ("Nix-vector not in cache, build: ");
557  // Build the nix-vector, given this node and the
558  // dest IP address
559  nixVectorInCache = GetNixVector (m_node, header.GetDestination (), oif);
560 
561  // cache it
562  m_nixCache.insert (NixMap_t::value_type (header.GetDestination (), nixVectorInCache));
563  }
564 
565  // path exists
566  if (nixVectorInCache)
567  {
568  NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache);
569 
570  // create a new nix vector to be used,
571  // we want to keep the cached version clean
572  nixVectorForPacket = nixVectorInCache->Copy ();
573 
574  // Get the interface number that we go out of, by extracting
575  // from the nix-vector
576  if (m_totalNeighbors == 0)
577  {
579  }
580 
581  // Get the interface number that we go out of, by extracting
582  // from the nix-vector
583  uint32_t numberOfBits = nixVectorForPacket->BitCount (m_totalNeighbors);
584  uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
585 
586  // Search here in a cache for this node index
587  // and look for a Ipv4Route
588  rtentry = GetIpv4RouteInCache (header.GetDestination ());
589 
590  if (!rtentry || !(rtentry->GetOutputDevice () == oif))
591  {
592  // not in cache or a different specified output
593  // device is to be used
594 
595  // first, make sure we erase existing (incorrect)
596  // rtentry from the map
597  if (rtentry)
598  {
599  m_ipv4RouteCache.erase (header.GetDestination ());
600  }
601 
602  NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
603  Ipv4Address gatewayIp;
604  uint32_t index = FindNetDeviceForNixIndex (m_node, nodeIndex, gatewayIp);
605  int32_t interfaceIndex = 0;
606 
607  if (!oif)
608  {
609  interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->GetDevice (index));
610  }
611  else
612  {
613  interfaceIndex = (m_ipv4)->GetInterfaceForDevice (oif);
614  }
615 
616  NS_ASSERT_MSG (interfaceIndex != -1, "Interface index not found for device");
617 
618  Ipv4Address sourceIPAddr = m_ipv4->SourceAddressSelection (interfaceIndex, header.GetDestination ());
619 
620  // start filling in the Ipv4Route info
621  rtentry = Create<Ipv4Route> ();
622  rtentry->SetSource (sourceIPAddr);
623 
624  rtentry->SetGateway (gatewayIp);
625  rtentry->SetDestination (header.GetDestination ());
626 
627  if (!oif)
628  {
629  rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
630  }
631  else
632  {
633  rtentry->SetOutputDevice (oif);
634  }
635 
636  sockerr = Socket::ERROR_NOTERROR;
637 
638  // add rtentry to cache
639  m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.GetDestination (), rtentry));
640  }
641 
642  NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache << " : Remaining bits: " << nixVectorForPacket->GetRemainingBits ());
643 
644  // Add nix-vector in the packet class
645  // make sure the packet exists first
646  if (p)
647  {
648  NS_LOG_LOGIC ("Adding Nix-vector to packet: " << *nixVectorForPacket);
649  p->SetNixVector (nixVectorForPacket);
650  }
651  }
652  else // path doesn't exist
653  {
654  NS_LOG_ERROR ("No path to the dest: " << header.GetDestination ());
655  sockerr = Socket::ERROR_NOROUTETOHOST;
656  }
657 
658  return rtentry;
659 }
660 
661 bool
665 {
667 
669 
670  NS_ASSERT (m_ipv4 != 0);
671  // Check if input device supports IP
672  NS_ASSERT (m_ipv4->GetInterfaceForDevice (idev) >= 0);
673  uint32_t iif = m_ipv4->GetInterfaceForDevice (idev);
674 
675  // Local delivery
676  if (m_ipv4->IsDestinationAddress (header.GetDestination (), iif))
677  {
678  if (!lcb.IsNull ())
679  {
680  NS_LOG_LOGIC ("Local delivery to " << header.GetDestination ());
681  lcb (p, header, iif);
682  return true;
683  }
684  else
685  {
686  // The local delivery callback is null. This may be a multicast
687  // or broadcast packet, so return false so that another
688  // multicast routing protocol can handle it. It should be possible
689  // to extend this to explicitly check whether it is a unicast
690  // packet, and invoke the error callback if so
691  return false;
692  }
693  }
694 
695  Ptr<Ipv4Route> rtentry;
696 
697  // Get the nix-vector from the packet
698  Ptr<NixVector> nixVector = p->GetNixVector ();
699 
700  // If nixVector isn't in packet, something went wrong
701  NS_ASSERT (nixVector);
702 
703  // Get the interface number that we go out of, by extracting
704  // from the nix-vector
705  if (m_totalNeighbors == 0)
706  {
708  }
709  uint32_t numberOfBits = nixVector->BitCount (m_totalNeighbors);
710  uint32_t nodeIndex = nixVector->ExtractNeighborIndex (numberOfBits);
711 
712  rtentry = GetIpv4RouteInCache (header.GetDestination ());
713  // not in cache
714  if (!rtentry)
715  {
716  NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
717  Ipv4Address gatewayIp;
718  uint32_t index = FindNetDeviceForNixIndex (m_node, nodeIndex, gatewayIp);
719  uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->GetDevice (index));
720  Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
721 
722  // start filling in the Ipv4Route info
723  rtentry = Create<Ipv4Route> ();
724  rtentry->SetSource (ifAddr.GetLocal ());
725 
726  rtentry->SetGateway (gatewayIp);
727  rtentry->SetDestination (header.GetDestination ());
728  rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
729 
730  // add rtentry to cache
731  m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.GetDestination (), rtentry));
732  }
733 
734  NS_LOG_LOGIC ("At Node " << m_node->GetId () << ", Extracting " << numberOfBits <<
735  " bits from Nix-vector: " << nixVector << " : " << *nixVector);
736 
737  // call the unicast callback
738  // local deliver is handled by Ipv4StaticRoutingImpl
739  // so this code is never even called if the packet is
740  // destined for this node.
741  ucb (rtentry, p, header);
742 
743  return true;
744 }
745 
746 void
748 {
749 
751 
752  std::ostream* os = stream->GetStream ();
753  // Copy the current ostream state
754  std::ios oldState (nullptr);
755  oldState.copyfmt (*os);
756 
757  *os << std::resetiosflags (std::ios::adjustfield) << std::setiosflags (std::ios::left);
758 
759  *os << "Node: " << m_ipv4->GetObject<Node> ()->GetId ()
760  << ", Time: " << Now().As (unit)
761  << ", Local time: " << m_ipv4->GetObject<Node> ()->GetLocalTime ().As (unit)
762  << ", Nix Routing" << std::endl;
763 
764  *os << "NixCache:" << std::endl;
765  if (m_nixCache.size () > 0)
766  {
767  *os << "Destination NixVector" << std::endl;
768  for (NixMap_t::const_iterator it = m_nixCache.begin (); it != m_nixCache.end (); it++)
769  {
770  std::ostringstream dest;
771  dest << it->first;
772  *os << std::setw (16) << dest.str ();
773  *os << *(it->second) << std::endl;
774  }
775  }
776  *os << "Ipv4RouteCache:" << std::endl;
777  if (m_ipv4RouteCache.size () > 0)
778  {
779  *os << "Destination Gateway Source OutputDevice" << std::endl;
780  for (Ipv4RouteMap_t::const_iterator it = m_ipv4RouteCache.begin (); it != m_ipv4RouteCache.end (); it++)
781  {
782  std::ostringstream dest, gw, src;
783  dest << it->second->GetDestination ();
784  *os << std::setw (16) << dest.str ();
785  gw << it->second->GetGateway ();
786  *os << std::setw (16) << gw.str ();
787  src << it->second->GetSource ();
788  *os << std::setw (16) << src.str ();
789  *os << " ";
790  if (Names::FindName (it->second->GetOutputDevice ()) != "")
791  {
792  *os << Names::FindName (it->second->GetOutputDevice ());
793  }
794  else
795  {
796  *os << it->second->GetOutputDevice ()->GetIfIndex ();
797  }
798  *os << std::endl;
799  }
800  }
801  *os << std::endl;
802  // Restore the previous ostream state
803  (*os).copyfmt (oldState);
804 }
805 
806 // virtual functions from Ipv4RoutingProtocol
807 void
809 {
810  g_isCacheDirty = true;
811 }
812 void
814 {
815  g_isCacheDirty = true;
816 }
817 void
819 {
820  g_isCacheDirty = true;
821 }
822 void
824 {
825  g_isCacheDirty = true;
826 }
827 
828 bool
829 Ipv4NixVectorRouting::BFS (uint32_t numberOfNodes, Ptr<Node> source,
830  Ptr<Node> dest, std::vector< Ptr<Node> > & parentVector,
831  Ptr<NetDevice> oif) const
832 {
834 
835  NS_LOG_LOGIC ("Going from Node " << source->GetId () << " to Node " << dest->GetId ());
836  std::queue< Ptr<Node> > greyNodeList; // discovered nodes with unexplored children
837 
838  // reset the parent vector
839  parentVector.assign (numberOfNodes, 0); // initialize to 0
840 
841  // Add the source node to the queue, set its parent to itself
842  greyNodeList.push (source);
843  parentVector.at (source->GetId ()) = source;
844 
845  // BFS loop
846  while (greyNodeList.size () != 0)
847  {
848  Ptr<Node> currNode = greyNodeList.front ();
849  Ptr<Ipv4> ipv4 = currNode->GetObject<Ipv4> ();
850 
851  if (currNode == dest)
852  {
853  NS_LOG_LOGIC ("Made it to Node " << currNode->GetId ());
854  return true;
855  }
856 
857  // if this is the first iteration of the loop and a
858  // specific output interface was given, make sure
859  // we go this way
860  if (currNode == source && oif)
861  {
862  // make sure that we can go this way
863  if (ipv4)
864  {
865  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (oif);
866  if (!(ipv4->IsUp (interfaceIndex)))
867  {
868  NS_LOG_LOGIC ("Ipv4Interface is down");
869  return false;
870  }
871  }
872  if (!(oif->IsLinkUp ()))
873  {
874  NS_LOG_LOGIC ("Link is down.");
875  return false;
876  }
877  Ptr<Channel> channel = oif->GetChannel ();
878  if (channel == 0)
879  {
880  return false;
881  }
882 
883  // this function takes in the local net dev, and channel, and
884  // writes to the netDeviceContainer the adjacent net devs
885  NetDeviceContainer netDeviceContainer;
886  GetAdjacentNetDevices (oif, channel, netDeviceContainer);
887 
888  // Finally we can get the adjacent nodes
889  // and scan through them. We push them
890  // to the greyNode queue, if they aren't
891  // already there.
892  for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
893  {
894  Ptr<Node> remoteNode = (*iter)->GetNode ();
895 
896  // check to see if this node has been pushed before
897  // by checking to see if it has a parent
898  // if it doesn't (null or 0), then set its parent and
899  // push to the queue
900  if (parentVector.at (remoteNode->GetId ()) == 0)
901  {
902  parentVector.at (remoteNode->GetId ()) = currNode;
903  greyNodeList.push (remoteNode);
904  }
905  }
906  }
907  else
908  {
909  // Iterate over the current node's adjacent vertices
910  // and push them into the queue
911  for (uint32_t i = 0; i < (currNode->GetNDevices ()); i++)
912  {
913  // Get a net device from the node
914  // as well as the channel, and figure
915  // out the adjacent net device
916  Ptr<NetDevice> localNetDevice = currNode->GetDevice (i);
917 
918  // make sure that we can go this way
919  if (ipv4)
920  {
921  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (currNode->GetDevice (i));
922  if (!(ipv4->IsUp (interfaceIndex)))
923  {
924  NS_LOG_LOGIC ("Ipv4Interface is down");
925  continue;
926  }
927  }
928  if (!(localNetDevice->IsLinkUp ()))
929  {
930  NS_LOG_LOGIC ("Link is down.");
931  continue;
932  }
933  Ptr<Channel> channel = localNetDevice->GetChannel ();
934  if (channel == 0)
935  {
936  continue;
937  }
938 
939  // this function takes in the local net dev, and channel, and
940  // writes to the netDeviceContainer the adjacent net devs
941  NetDeviceContainer netDeviceContainer;
942  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
943 
944  // Finally we can get the adjacent nodes
945  // and scan through them. We push them
946  // to the greyNode queue, if they aren't
947  // already there.
948  for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
949  {
950  Ptr<Node> remoteNode = (*iter)->GetNode ();
951 
952  // check to see if this node has been pushed before
953  // by checking to see if it has a parent
954  // if it doesn't (null or 0), then set its parent and
955  // push to the queue
956  if (parentVector.at (remoteNode->GetId ()) == 0)
957  {
958  parentVector.at (remoteNode->GetId ()) = currNode;
959  greyNodeList.push (remoteNode);
960  }
961  }
962  }
963  }
964 
965  // Pop off the head grey node. We have all its children.
966  // It is now black.
967  greyNodeList.pop ();
968  }
969 
970  // Didn't find the dest...
971  return false;
972 }
973 
974 void
976  Ptr<OutputStreamWrapper> stream, Time::Unit unit) const
977 {
978  NS_LOG_FUNCTION (this << source << dest);
979  Ptr<NixVector> nixVectorInCache;
980  Ptr<NixVector> nixVector;
981  Ptr<Ipv4Route> rtentry;
982 
984 
985  Ptr<Node> destNode = GetNodeByIp (dest);
986  if (destNode == 0)
987  {
988  NS_LOG_ERROR ("No routing path exists");
989  return;
990  }
991 
992  std::ostream* os = stream->GetStream ();
993  // Copy the current ostream state
994  std::ios oldState (nullptr);
995  oldState.copyfmt (*os);
996 
997  *os << std::resetiosflags (std::ios::adjustfield) << std::setiosflags (std::ios::left);
998  *os << "Time: " << Now().As (unit)
999  << ", Nix Routing" << std::endl;
1000  *os << "Route Path: ";
1001  *os << "(Node " << source->GetId () << " to Node " << destNode->GetId () << ", ";
1002  *os << "Nix Vector: ";
1003 
1004  nixVectorInCache = GetNixVectorInCache (dest);
1005 
1006  // not in cache
1007  if (!nixVectorInCache)
1008  {
1009  NS_LOG_LOGIC ("Nix-vector not in cache, build: ");
1010  // Build the nix-vector, given the source node and the
1011  // dest IP address
1012  nixVectorInCache = GetNixVector (source, dest, nullptr);
1013  }
1014 
1015  if (nixVectorInCache || (!nixVectorInCache && source == destNode))
1016  {
1017  Ptr<Node> curr = source;
1018  uint32_t totalNeighbors = 0;
1019 
1020  if (nixVectorInCache)
1021  {
1022  // cache it
1023  m_nixCache.insert (NixMap_t::value_type (dest, nixVectorInCache));
1024  // Make a NixVector copy to work with. This is because
1025  // we don't want to extract the bits from nixVectorInCache
1026  // which is stored in the m_nixCache.
1027  nixVector = nixVectorInCache->Copy ();
1028 
1029  *os << *nixVector;
1030  }
1031  *os << ")" << std::endl;
1032 
1033  if (source == destNode)
1034  {
1035  std::ostringstream src, dst;
1036  src << dest << " (Node " << destNode->GetId () << ")";
1037  *os << std::setw (20) << src.str ();
1038  dst << "----> " << dest << " (Node " << destNode->GetId () << ")";
1039  *os << dst.str () << std::endl;
1040  }
1041 
1042  while (curr != destNode)
1043  {
1044  totalNeighbors = FindTotalNeighbors (curr);
1045  // Get the number of bits required
1046  // to represent all the neighbors
1047  uint32_t numberOfBits = nixVector->BitCount (totalNeighbors);
1048  // Get the nixIndex
1049  uint32_t nixIndex = nixVector->ExtractNeighborIndex (numberOfBits);
1050  // gatewayIP is the IP of next
1051  // node on channel found from nixIndex
1052  Ipv4Address gatewayIp;
1053  // Get the Net Device index from the nixIndex
1054  uint32_t NetDeviceIndex = FindNetDeviceForNixIndex (curr, nixIndex, gatewayIp);
1055  // Get the interfaceIndex with the help of NetDeviceIndex.
1056  // It will be used to get the IP address on interfaceIndex
1057  // interface of 'curr' node.
1058  Ptr<Ipv4> ipv4 = curr->GetObject<Ipv4> ();
1059  Ptr<NetDevice> outDevice = curr->GetDevice (NetDeviceIndex);
1060  uint32_t interfaceIndex = ipv4->GetInterfaceForDevice (outDevice);
1061  Ipv4Address sourceIPAddr;
1062  if (curr == source)
1063  {
1064  sourceIPAddr = ipv4->SourceAddressSelection (interfaceIndex, dest);
1065  }
1066  else
1067  {
1068  // We use the first address because it's indifferent which one
1069  // we use to identify intermediate routers
1070  sourceIPAddr = ipv4->GetAddress (interfaceIndex, 0).GetLocal ();
1071  }
1072 
1073  std::ostringstream currNode, nextNode;
1074  currNode << sourceIPAddr << " (Node " << curr->GetId () << ")";
1075  *os << std::setw (20) << currNode.str ();
1076  // Replace curr with the next node
1077  curr = GetNodeByIp (gatewayIp);
1078  nextNode << "----> " << ((curr == destNode) ? dest : gatewayIp) << " (Node " << curr->GetId () << ")";
1079  *os << nextNode.str () << std::endl;
1080  }
1081  *os << std::endl;
1082  }
1083  else
1084  {
1085  *os << ")" << std::endl;
1086  // No Route exists
1087  *os << "There does not exist a path from Node " << source->GetId ()
1088  << " to Node " << destNode->GetId () << "." << std::endl;
1089  }
1090  // Restore the previous ostream state
1091  (*os).copyfmt (oldState);
1092 }
1093 
1094 void
1096 {
1097  if (g_isCacheDirty)
1098  {
1100  g_isCacheDirty = false;
1101  }
1102 }
1103 
1104 } // namespace ns3
void FlushGlobalNixRoutingCache(void) const
Called when run-time link topology change occurs which iterates through the node list and flushes any...
TimeWithUnit As(const enum Unit unit=Time::AUTO) const
Attach a unit to a Time, to facilitate output in a specific unit.
Definition: time.cc:429
void BuildIpv4AddressToNodeMap(void) const
Build map from IPv4 Address to Node for faster lookup.
Ptr< NetDevice > Get(uint32_t i) const
Get the Ptr<NetDevice> stored in this container at a given index.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:73
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
static uint32_t GetNNodes(void)
Definition: node-list.cc:247
Callback template class.
Definition: callback.h:1278
Definition: second.py:1
uint32_t GetId(void) const
Definition: node.cc:109
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
Iterator End(void) const
Get an iterator which indicates past-the-last NetDevice in the container.
bool BuildNixVectorLocal(Ptr< NixVector > nixVector)
Special variation of BuildNixVector for when a node is sending to itself.
Ptr< NetDevice > GetDevice(uint32_t index) const
Retrieve the index-th NetDevice associated to this node.
Definition: node.cc:144
Ptr< Node > GetNodeByIp(Ipv4Address dest) const
Iterates through the node list and finds the one corresponding to the given Ipv4Address.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file...
Definition: assert.h:67
virtual void PrintRoutingTable(Ptr< OutputStreamWrapper > stream, Time::Unit unit=Time::S) const
Print the Routing Table entries.
void DoDispose(void)
Destructor implementation.
Ptr< Ipv4 > m_ipv4
IPv4 object.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
void FlushIpv4RouteCache(void) const
Flushes the cache which stores the Ipv4 route based on the destination IP.
Ptr< NixVector > GetNixVector(Ptr< Node > source, Ipv4Address dest, Ptr< NetDevice > oif) const
Takes in the source node and dest IP and calls GetNodeByIp, BFS, accounting for any output interface ...
virtual void DoDispose(void)
Destructor implementation.
Definition: object.cc:346
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
uint32_t FindTotalNeighbors(Ptr< Node > node) const
Simply iterates through the nodes net-devices and determines how many neighbors the node has...
a virtual net device that bridges multiple LAN segments
SocketErrno
Enumeration of the possible errors returned by a socket.
Definition: socket.h:82
bool BuildNixVector(const std::vector< Ptr< Node > > &parentVector, uint32_t source, uint32_t dest, Ptr< NixVector > nixVector) const
Recurses the parent vector, created by BFS and actually builds the nixvector.
bool BFS(uint32_t numberOfNodes, Ptr< Node > source, Ptr< Node > dest, std::vector< Ptr< Node > > &parentVector, Ptr< NetDevice > oif) const
Breadth first search algorithm.
channel
Definition: third.py:92
void FlushNixCache(void) const
Flushes the cache which stores nix-vector based on destination IP.
void SetSource(Ipv4Address src)
Definition: ipv4-route.cc:49
uint32_t GetRemainingBits(void)
Definition: nix-vector.cc:357
Packet header for IPv4.
Definition: ipv4-header.h:33
uint32_t ExtractNeighborIndex(uint32_t numberOfBits)
Definition: nix-vector.cc:160
Ptr< Node > m_node
Node object.
void SetNode(Ptr< Node > node)
Set the Node pointer of the node for which this routing protocol is to be placed. ...
void SetNixVector(Ptr< NixVector > nixVector)
Set the packet nix-vector.
Definition: packet.cc:244
Iterator Begin(void) const
Get an iterator which refers to the first NetDevice in the container.
void Add(NetDeviceContainer other)
Append the contents of another NetDeviceContainer to the end of this container.
void SetGateway(Ipv4Address gw)
Definition: ipv4-route.cc:63
static Iterator End(void)
Definition: node-list.cc:235
Nix-vector routing protocol.
Unit
The unit to use to interpret a number representing time.
Definition: nstime.h:109
holds a vector of ns3::NetDevice pointers
void GetAdjacentNetDevices(Ptr< NetDevice > netDevice, Ptr< Channel > channel, NetDeviceContainer &netDeviceContainer) const
Given a net-device returns all the adjacent net-devices, essentially getting the neighbors on that ch...
std::unordered_map< Ipv4Address, ns3::Ptr< ns3::Node >, Ipv4AddressHash > Ipv4AddressToNodeMap
Mapping of IPv4 address to ns-3 node.
Ptr< Ipv4Route > GetIpv4RouteInCache(Ipv4Address address)
Checks the cache based on dest IP for the Ipv4Route.
static TypeId GetTypeId(void)
The Interface ID of the Global Router interface.
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
Ptr< BridgeNetDevice > NetDeviceIsBridged(Ptr< NetDevice > nd) const
Determine if the NetDevice is bridged.
virtual void NotifyInterfaceDown(uint32_t interface)
Access to the IPv4 forwarding table, interfaces, and configuration.
Definition: ipv4.h:76
Ptr< T > GetObject(void) const
Get a pointer to the requested aggregated Object.
Definition: object.h:470
virtual void NotifyInterfaceUp(uint32_t interface)
Ptr< NetDevice > GetOutputDevice(void) const
Definition: ipv4-route.cc:84
Every class exported by the ns3 library is enclosed in the ns3 namespace.
address
Definition: first.py:44
std::vector< Ptr< Node > >::const_iterator Iterator
Node container iterator.
Definition: node-list.h:44
Ptr< NixVector > GetNixVectorInCache(Ipv4Address address) const
Checks the cache based on dest IP for the nix-vector.
NixMap_t m_nixCache
Cache stores nix-vectors based on destination ip.
static bool g_isCacheDirty
Flag to mark when caches are dirty and need to be flushed.
Ptr< NixVector > Copy(void) const
Definition: nix-vector.cc:71
void SetOutputDevice(Ptr< NetDevice > outputDevice)
Equivalent in Linux to dst_entry.dev.
Definition: ipv4-route.cc:77
void PrintRoutingPath(Ptr< Node > source, Ipv4Address dest, Ptr< OutputStreamWrapper > stream, Time::Unit unit) const
Print the Routing Path according to Nix Routing.
uint32_t BitCount(uint32_t numberOfNeighbors) const
Definition: nix-vector.cc:365
virtual void NotifyRemoveAddress(uint32_t interface, Ipv4InterfaceAddress address)
Ipv4Address GetDestination(void) const
Definition: ipv4-header.cc:304
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition: assert.h:88
virtual Ptr< Ipv4Route > RouteOutput(Ptr< Packet > p, const Ipv4Header &header, Ptr< NetDevice > oif, Socket::SocketErrno &sockerr)
Query routing cache for an existing route, for an outbound packet.
virtual void SetIpv4(Ptr< Ipv4 > ipv4)
uint32_t m_totalNeighbors
Total neighbors used for nix-vector to determine number of bits.
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:41
#define NS_ABORT_MSG_UNLESS(cond, msg)
Abnormal program termination if a condition is false, with a message.
Definition: abort.h:144
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if a condition is true, with a message.
Definition: abort.h:108
a class to store IPv4 address information on an interface
static Iterator Begin(void)
Definition: node-list.cc:229
A network Node.
Definition: node.h:56
std::vector< Ptr< NetDevice > >::const_iterator Iterator
NetDevice container iterator.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
uint32_t GetN(void) const
Get the number of Ptr<NetDevice> stored in this container.
Ipv4RouteMap_t m_ipv4RouteCache
Cache stores Ipv4Routes based on destination ip.
virtual bool RouteInput(Ptr< const Packet > p, const Ipv4Header &header, Ptr< const NetDevice > idev, UnicastForwardCallback ucb, MulticastForwardCallback mcb, LocalDeliverCallback lcb, ErrorCallback ecb)
Route an input packet (to be forwarded or locally delivered)
Ptr< NixVector > GetNixVector(void) const
Get the packet nix-vector.
Definition: packet.cc:250
static std::string FindName(Ptr< Object > object)
Given a pointer to an object, look to see if that object has a name associated with it and...
Definition: names.cc:817
Ipv4Address GetLocal(void) const
Get the local address.
Abstract base class for IPv4 routing protocols.
Time Now(void)
create an ns3::Time instance which contains the current simulation time.
Definition: simulator.cc:287
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:257
void AddNeighborIndex(uint32_t newBits, uint32_t numberOfBits)
Definition: nix-vector.cc:88
void CheckCacheStateAndFlush(void) const
Flushes routing caches if required.
bool IsNull(void) const
Check for null implementation.
Definition: callback.h:1386
virtual void NotifyAddAddress(uint32_t interface, Ipv4InterfaceAddress address)
uint32_t FindNetDeviceForNixIndex(Ptr< Node > node, uint32_t nodeIndex, Ipv4Address &gatewayIp) const
Nix index is with respect to the neighbors.
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:923
std::ostream * GetStream(void)
Return a pointer to an ostream previously set in the wrapper.
void SetDestination(Ipv4Address dest)
Definition: ipv4-route.cc:35
uint32_t GetNDevices(void) const
Definition: node.cc:152
static Ipv4AddressToNodeMap g_ipv4AddressToNodeMap
Address to node map.