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)
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  Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, 0);
376  Ipv4Address addr = ifAddr.GetLocal ();
377 
379  "Duplicate IPv4 address (" << addr << ") found during NIX Vector map construction for node " << node->GetId ());
380 
381  NS_LOG_LOGIC ("Adding IPv4 address " << addr << " for node " << node->GetId () << " to NIX Vector IPv4 address to node map");
382  g_ipv4AddressToNodeMap[addr] = node;
383  }
384  }
385  }
386  }
387  }
388 }
389 
390 Ptr<Node>
392 {
394 
395  // Populate lookup table if is empty.
396  if ( g_ipv4AddressToNodeMap.empty () )
397  {
399  }
400 
401  Ptr<Node> destNode;
402 
403  Ipv4AddressToNodeMap::iterator iter = g_ipv4AddressToNodeMap.find(dest);
404 
405  if(iter == g_ipv4AddressToNodeMap.end ())
406  {
407  NS_LOG_ERROR ("Couldn't find dest node given the IP" << dest);
408  destNode = 0;
409  }
410  else
411  {
412  destNode = iter -> second;
413  }
414 
415  return destNode;
416 }
417 
418 uint32_t
420 {
421  uint32_t numberOfDevices = m_node->GetNDevices ();
422  uint32_t totalNeighbors = 0;
423 
424  // scan through the net devices on the parent node
425  // and then look at the nodes adjacent to them
426  for (uint32_t i = 0; i < numberOfDevices; i++)
427  {
428  // Get a net device from the node
429  // as well as the channel, and figure
430  // out the adjacent net devices
431  Ptr<NetDevice> localNetDevice = m_node->GetDevice (i);
432  Ptr<Channel> channel = localNetDevice->GetChannel ();
433  if (channel == 0)
434  {
435  continue;
436  }
437 
438  // this function takes in the local net dev, and channel, and
439  // writes to the netDeviceContainer the adjacent net devs
440  NetDeviceContainer netDeviceContainer;
441  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
442 
443  totalNeighbors += netDeviceContainer.GetN ();
444  }
445 
446  return totalNeighbors;
447 }
448 
451 {
452  NS_LOG_FUNCTION (nd);
453 
454  Ptr<Node> node = nd->GetNode ();
455  uint32_t nDevices = node->GetNDevices ();
456 
457  //
458  // There is no bit on a net device that says it is being bridged, so we have
459  // to look for bridges on the node to which the device is attached. If we
460  // find a bridge, we need to look through its bridge ports (the devices it
461  // bridges) to see if we find the device in question.
462  //
463  for (uint32_t i = 0; i < nDevices; ++i)
464  {
465  Ptr<NetDevice> ndTest = node->GetDevice (i);
466  NS_LOG_LOGIC ("Examine device " << i << " " << ndTest);
467 
468  if (ndTest->IsBridge ())
469  {
470  NS_LOG_LOGIC ("device " << i << " is a bridge net device");
471  Ptr<BridgeNetDevice> bnd = ndTest->GetObject<BridgeNetDevice> ();
472  NS_ABORT_MSG_UNLESS (bnd, "Ipv4NixVectorRouting::NetDeviceIsBridged (): GetObject for <BridgeNetDevice> failed");
473 
474  for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
475  {
476  NS_LOG_LOGIC ("Examine bridge port " << j << " " << bnd->GetBridgePort (j));
477  if (bnd->GetBridgePort (j) == nd)
478  {
479  NS_LOG_LOGIC ("Net device " << nd << " is bridged by " << bnd);
480  return bnd;
481  }
482  }
483  }
484  }
485  NS_LOG_LOGIC ("Net device " << nd << " is not bridged");
486  return 0;
487 }
488 
489 uint32_t
491 {
492  uint32_t numberOfDevices = m_node->GetNDevices ();
493  uint32_t index = 0;
494  uint32_t totalNeighbors = 0;
495 
496  // scan through the net devices on the parent node
497  // and then look at the nodes adjacent to them
498  for (uint32_t i = 0; i < numberOfDevices; i++)
499  {
500  // Get a net device from the node
501  // as well as the channel, and figure
502  // out the adjacent net devices
503  Ptr<NetDevice> localNetDevice = m_node->GetDevice (i);
504  Ptr<Channel> channel = localNetDevice->GetChannel ();
505  if (channel == 0)
506  {
507  continue;
508  }
509 
510  // this function takes in the local net dev, and channel, and
511  // writes to the netDeviceContainer the adjacent net devs
512  NetDeviceContainer netDeviceContainer;
513  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
514 
515  // check how many neighbors we have
516  if (nodeIndex < (totalNeighbors + netDeviceContainer.GetN ()))
517  {
518  // found the proper net device
519  index = i;
520  Ptr<NetDevice> gatewayDevice = netDeviceContainer.Get (nodeIndex-totalNeighbors);
521  Ptr<Node> gatewayNode = gatewayDevice->GetNode ();
522  Ptr<Ipv4> ipv4 = gatewayNode->GetObject<Ipv4> ();
523 
524  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (gatewayDevice);
525  Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, 0);
526  gatewayIp = ifAddr.GetLocal ();
527  break;
528  }
529  totalNeighbors += netDeviceContainer.GetN ();
530  }
531 
532  return index;
533 }
534 
537 {
539  Ptr<Ipv4Route> rtentry;
540  Ptr<NixVector> nixVectorInCache;
541  Ptr<NixVector> nixVectorForPacket;
542 
544 
545  NS_LOG_DEBUG ("Dest IP from header: " << header.GetDestination ());
546  // check if cache
547  nixVectorInCache = GetNixVectorInCache (header.GetDestination ());
548 
549  // not in cache
550  if (!nixVectorInCache)
551  {
552  NS_LOG_LOGIC ("Nix-vector not in cache, build: ");
553  // Build the nix-vector, given this node and the
554  // dest IP address
555  nixVectorInCache = GetNixVector (m_node, header.GetDestination (), oif);
556 
557  // cache it
558  m_nixCache.insert (NixMap_t::value_type (header.GetDestination (), nixVectorInCache));
559  }
560 
561  // path exists
562  if (nixVectorInCache)
563  {
564  NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache);
565 
566  // create a new nix vector to be used,
567  // we want to keep the cached version clean
568  nixVectorForPacket = Create<NixVector> ();
569  nixVectorForPacket = nixVectorInCache->Copy ();
570 
571  // Get the interface number that we go out of, by extracting
572  // from the nix-vector
573  if (m_totalNeighbors == 0)
574  {
576  }
577 
578  // Get the interface number that we go out of, by extracting
579  // from the nix-vector
580  uint32_t numberOfBits = nixVectorForPacket->BitCount (m_totalNeighbors);
581  uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
582 
583  // Search here in a cache for this node index
584  // and look for a Ipv4Route
585  rtentry = GetIpv4RouteInCache (header.GetDestination ());
586 
587  if (!rtentry || !(rtentry->GetOutputDevice () == oif))
588  {
589  // not in cache or a different specified output
590  // device is to be used
591 
592  // first, make sure we erase existing (incorrect)
593  // rtentry from the map
594  if (rtentry)
595  {
596  m_ipv4RouteCache.erase (header.GetDestination ());
597  }
598 
599  NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
600  Ipv4Address gatewayIp;
601  uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
602  int32_t interfaceIndex = 0;
603 
604  if (!oif)
605  {
606  interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->GetDevice (index));
607  }
608  else
609  {
610  interfaceIndex = (m_ipv4)->GetInterfaceForDevice (oif);
611  }
612 
613  NS_ASSERT_MSG (interfaceIndex != -1, "Interface index not found for device");
614 
615  Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
616 
617  // start filling in the Ipv4Route info
618  rtentry = Create<Ipv4Route> ();
619  rtentry->SetSource (ifAddr.GetLocal ());
620 
621  rtentry->SetGateway (gatewayIp);
622  rtentry->SetDestination (header.GetDestination ());
623 
624  if (!oif)
625  {
626  rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
627  }
628  else
629  {
630  rtentry->SetOutputDevice (oif);
631  }
632 
633  sockerr = Socket::ERROR_NOTERROR;
634 
635  // add rtentry to cache
636  m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.GetDestination (), rtentry));
637  }
638 
639  NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache << " : Remaining bits: " << nixVectorForPacket->GetRemainingBits ());
640 
641  // Add nix-vector in the packet class
642  // make sure the packet exists first
643  if (p)
644  {
645  NS_LOG_LOGIC ("Adding Nix-vector to packet: " << *nixVectorForPacket);
646  p->SetNixVector (nixVectorForPacket);
647  }
648  }
649  else // path doesn't exist
650  {
651  NS_LOG_ERROR ("No path to the dest: " << header.GetDestination ());
652  sockerr = Socket::ERROR_NOROUTETOHOST;
653  }
654 
655  return rtentry;
656 }
657 
658 bool
662 {
664 
666 
667  NS_ASSERT (m_ipv4 != 0);
668  // Check if input device supports IP
669  NS_ASSERT (m_ipv4->GetInterfaceForDevice (idev) >= 0);
670  uint32_t iif = m_ipv4->GetInterfaceForDevice (idev);
671 
672  // Local delivery
673  if (m_ipv4->IsDestinationAddress (header.GetDestination (), iif))
674  {
675  if (!lcb.IsNull ())
676  {
677  NS_LOG_LOGIC ("Local delivery to " << header.GetDestination ());
678  lcb (p, header, iif);
679  return true;
680  }
681  else
682  {
683  // The local delivery callback is null. This may be a multicast
684  // or broadcast packet, so return false so that another
685  // multicast routing protocol can handle it. It should be possible
686  // to extend this to explicitly check whether it is a unicast
687  // packet, and invoke the error callback if so
688  return false;
689  }
690  }
691 
692  Ptr<Ipv4Route> rtentry;
693 
694  // Get the nix-vector from the packet
695  Ptr<NixVector> nixVector = p->GetNixVector ();
696 
697  // If nixVector isn't in packet, something went wrong
698  NS_ASSERT (nixVector);
699 
700  // Get the interface number that we go out of, by extracting
701  // from the nix-vector
702  if (m_totalNeighbors == 0)
703  {
705  }
706  uint32_t numberOfBits = nixVector->BitCount (m_totalNeighbors);
707  uint32_t nodeIndex = nixVector->ExtractNeighborIndex (numberOfBits);
708 
709  rtentry = GetIpv4RouteInCache (header.GetDestination ());
710  // not in cache
711  if (!rtentry)
712  {
713  NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
714  Ipv4Address gatewayIp;
715  uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
716  uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->GetDevice (index));
717  Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
718 
719  // start filling in the Ipv4Route info
720  rtentry = Create<Ipv4Route> ();
721  rtentry->SetSource (ifAddr.GetLocal ());
722 
723  rtentry->SetGateway (gatewayIp);
724  rtentry->SetDestination (header.GetDestination ());
725  rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
726 
727  // add rtentry to cache
728  m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.GetDestination (), rtentry));
729  }
730 
731  NS_LOG_LOGIC ("At Node " << m_node->GetId () << ", Extracting " << numberOfBits <<
732  " bits from Nix-vector: " << nixVector << " : " << *nixVector);
733 
734  // call the unicast callback
735  // local deliver is handled by Ipv4StaticRoutingImpl
736  // so this code is never even called if the packet is
737  // destined for this node.
738  ucb (rtentry, p, header);
739 
740  return true;
741 }
742 
743 void
745 {
746 
748 
749  std::ostream* os = stream->GetStream ();
750  // Copy the current ostream state
751  std::ios oldState (nullptr);
752  oldState.copyfmt (*os);
753 
754  *os << std::resetiosflags (std::ios::adjustfield) << std::setiosflags (std::ios::left);
755 
756  *os << "Node: " << m_ipv4->GetObject<Node> ()->GetId ()
757  << ", Time: " << Now().As (unit)
758  << ", Local time: " << m_ipv4->GetObject<Node> ()->GetLocalTime ().As (unit)
759  << ", Nix Routing" << std::endl;
760 
761  *os << "NixCache:" << std::endl;
762  if (m_nixCache.size () > 0)
763  {
764  *os << "Destination NixVector" << std::endl;
765  for (NixMap_t::const_iterator it = m_nixCache.begin (); it != m_nixCache.end (); it++)
766  {
767  std::ostringstream dest;
768  dest << it->first;
769  *os << std::setw (16) << dest.str ();
770  *os << *(it->second) << std::endl;
771  }
772  }
773  *os << "Ipv4RouteCache:" << std::endl;
774  if (m_ipv4RouteCache.size () > 0)
775  {
776  *os << "Destination Gateway Source OutputDevice" << std::endl;
777  for (Ipv4RouteMap_t::const_iterator it = m_ipv4RouteCache.begin (); it != m_ipv4RouteCache.end (); it++)
778  {
779  std::ostringstream dest, gw, src;
780  dest << it->second->GetDestination ();
781  *os << std::setw (16) << dest.str ();
782  gw << it->second->GetGateway ();
783  *os << std::setw (16) << gw.str ();
784  src << it->second->GetSource ();
785  *os << std::setw (16) << src.str ();
786  *os << " ";
787  if (Names::FindName (it->second->GetOutputDevice ()) != "")
788  {
789  *os << Names::FindName (it->second->GetOutputDevice ());
790  }
791  else
792  {
793  *os << it->second->GetOutputDevice ()->GetIfIndex ();
794  }
795  *os << std::endl;
796  }
797  }
798  *os << std::endl;
799  // Restore the previous ostream state
800  (*os).copyfmt (oldState);
801 }
802 
803 // virtual functions from Ipv4RoutingProtocol
804 void
806 {
807  g_isCacheDirty = true;
808 }
809 void
811 {
812  g_isCacheDirty = true;
813 }
814 void
816 {
817  g_isCacheDirty = true;
818 }
819 void
821 {
822  g_isCacheDirty = true;
823 }
824 
825 bool
826 Ipv4NixVectorRouting::BFS (uint32_t numberOfNodes, Ptr<Node> source,
827  Ptr<Node> dest, std::vector< Ptr<Node> > & parentVector,
828  Ptr<NetDevice> oif)
829 {
831 
832  NS_LOG_LOGIC ("Going from Node " << source->GetId () << " to Node " << dest->GetId ());
833  std::queue< Ptr<Node> > greyNodeList; // discovered nodes with unexplored children
834 
835  // reset the parent vector
836  parentVector.assign (numberOfNodes, 0); // initialize to 0
837 
838  // Add the source node to the queue, set its parent to itself
839  greyNodeList.push (source);
840  parentVector.at (source->GetId ()) = source;
841 
842  // BFS loop
843  while (greyNodeList.size () != 0)
844  {
845  Ptr<Node> currNode = greyNodeList.front ();
846  Ptr<Ipv4> ipv4 = currNode->GetObject<Ipv4> ();
847 
848  if (currNode == dest)
849  {
850  NS_LOG_LOGIC ("Made it to Node " << currNode->GetId ());
851  return true;
852  }
853 
854  // if this is the first iteration of the loop and a
855  // specific output interface was given, make sure
856  // we go this way
857  if (currNode == source && oif)
858  {
859  // make sure that we can go this way
860  if (ipv4)
861  {
862  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (oif);
863  if (!(ipv4->IsUp (interfaceIndex)))
864  {
865  NS_LOG_LOGIC ("Ipv4Interface is down");
866  return false;
867  }
868  }
869  if (!(oif->IsLinkUp ()))
870  {
871  NS_LOG_LOGIC ("Link is down.");
872  return false;
873  }
874  Ptr<Channel> channel = oif->GetChannel ();
875  if (channel == 0)
876  {
877  return false;
878  }
879 
880  // this function takes in the local net dev, and channel, and
881  // writes to the netDeviceContainer the adjacent net devs
882  NetDeviceContainer netDeviceContainer;
883  GetAdjacentNetDevices (oif, channel, netDeviceContainer);
884 
885  // Finally we can get the adjacent nodes
886  // and scan through them. We push them
887  // to the greyNode queue, if they aren't
888  // already there.
889  for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
890  {
891  Ptr<Node> remoteNode = (*iter)->GetNode ();
892 
893  // check to see if this node has been pushed before
894  // by checking to see if it has a parent
895  // if it doesn't (null or 0), then set its parent and
896  // push to the queue
897  if (parentVector.at (remoteNode->GetId ()) == 0)
898  {
899  parentVector.at (remoteNode->GetId ()) = currNode;
900  greyNodeList.push (remoteNode);
901  }
902  }
903  }
904  else
905  {
906  // Iterate over the current node's adjacent vertices
907  // and push them into the queue
908  for (uint32_t i = 0; i < (currNode->GetNDevices ()); i++)
909  {
910  // Get a net device from the node
911  // as well as the channel, and figure
912  // out the adjacent net device
913  Ptr<NetDevice> localNetDevice = currNode->GetDevice (i);
914 
915  // make sure that we can go this way
916  if (ipv4)
917  {
918  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (currNode->GetDevice (i));
919  if (!(ipv4->IsUp (interfaceIndex)))
920  {
921  NS_LOG_LOGIC ("Ipv4Interface is down");
922  continue;
923  }
924  }
925  if (!(localNetDevice->IsLinkUp ()))
926  {
927  NS_LOG_LOGIC ("Link is down.");
928  continue;
929  }
930  Ptr<Channel> channel = localNetDevice->GetChannel ();
931  if (channel == 0)
932  {
933  continue;
934  }
935 
936  // this function takes in the local net dev, and channel, and
937  // writes to the netDeviceContainer the adjacent net devs
938  NetDeviceContainer netDeviceContainer;
939  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
940 
941  // Finally we can get the adjacent nodes
942  // and scan through them. We push them
943  // to the greyNode queue, if they aren't
944  // already there.
945  for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
946  {
947  Ptr<Node> remoteNode = (*iter)->GetNode ();
948 
949  // check to see if this node has been pushed before
950  // by checking to see if it has a parent
951  // if it doesn't (null or 0), then set its parent and
952  // push to the queue
953  if (parentVector.at (remoteNode->GetId ()) == 0)
954  {
955  parentVector.at (remoteNode->GetId ()) = currNode;
956  greyNodeList.push (remoteNode);
957  }
958  }
959  }
960  }
961 
962  // Pop off the head grey node. We have all its children.
963  // It is now black.
964  greyNodeList.pop ();
965  }
966 
967  // Didn't find the dest...
968  return false;
969 }
970 
971 void
974 {
975  NS_LOG_FUNCTION (this << source << dest);
976  Ptr<NixVector> nixVectorInCache;
977  Ptr<NixVector> nixVector;
978  Ptr<Ipv4Route> rtentry;
979 
980  Ptr<Node> destNode = GetNodeByIp (dest);
981 
982  std::ostream* os = stream->GetStream ();
983  // Copy the current ostream state
984  std::ios oldState (nullptr);
985  oldState.copyfmt (*os);
986 
987  *os << std::resetiosflags (std::ios::adjustfield) << std::setiosflags (std::ios::left);
988  *os << "Time: " << Now().As (unit)
989  << ", Nix Routing" << std::endl;
990  *os << "Route Path: ";
991  *os << "(Node " << source->GetId () << " to Node " << destNode->GetId () << ", ";
992  *os << "Nix Vector: ";
993 
994  nixVectorInCache = GetNixVectorInCache (dest);
995 
996  // not in cache
997  if (!nixVectorInCache)
998  {
999  NS_LOG_LOGIC ("Nix-vector not in cache, build: ");
1000  // Build the nix-vector, given the source node and the
1001  // dest IP address
1002  nixVectorInCache = GetNixVector (source, dest, nullptr);
1003  }
1004 
1005  if (nixVectorInCache || (!nixVectorInCache && source == destNode))
1006  {
1007  Ptr<Node> curr = source;
1008 
1009  if (nixVectorInCache)
1010  {
1011  // cache it
1012  m_nixCache.insert (NixMap_t::value_type (dest, nixVectorInCache));
1013  // Make a NixVector copy to work with. This is because
1014  // we don't want to extract the bits from nixVectorInCache
1015  // which is stored in the m_nixCache.
1016  nixVector = Create<NixVector> ();
1017  nixVector = nixVectorInCache->Copy ();
1018 
1019  *os << *nixVector;
1020  }
1021  *os << ")" << std::endl;
1022 
1023  if (source == destNode)
1024  {
1025  std::ostringstream src, dst;
1026  src << dest << " (Node " << destNode->GetId () << ")";
1027  *os << std::setw (20) << src.str ();
1028  dst << "----> " << dest << " (Node " << destNode->GetId () << ")";
1029  *os << dst.str () << std::endl;
1030  }
1031 
1032  while (curr != destNode)
1033  {
1034  // set m_node as current node
1035  // and find the total neighbors
1036  SetNode (curr);
1038  // Get the number of bits required
1039  // to represent all the neighbors
1040  uint32_t numberOfBits = nixVector->BitCount (m_totalNeighbors);
1041  // Get the nixIndex
1042  uint32_t nixIndex = nixVector->ExtractNeighborIndex (numberOfBits);
1043  // gatewayIP is the IP of next
1044  // node on channel found from nixIndex
1045  Ipv4Address gatewayIp;
1046  // Get the Net Device index from the nixIndex
1047  uint32_t NetDeviceIndex = FindNetDeviceForNixIndex (nixIndex, gatewayIp);
1048  // Get the interfaceIndex with the help of NetDeviceIndex.
1049  // It will be used to get the IP address on interfaceIndex
1050  // interface of 'curr' node.
1051  Ptr<Ipv4> ipv4 = curr->GetObject<Ipv4> ();
1052  Ptr<NetDevice> outDevice = curr->GetDevice (NetDeviceIndex);
1053  uint32_t interfaceIndex = ipv4->GetInterfaceForDevice (outDevice);
1054  Ipv4Address sourceIPAddr = ipv4->GetAddress (interfaceIndex, 0).GetLocal ();
1055 
1056  rtentry = GetIpv4RouteInCache (dest);
1057  if (!rtentry)
1058  {
1059  NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
1060  // start filling in the Ipv4Route info
1061  rtentry = Create<Ipv4Route> ();
1062  rtentry->SetSource (sourceIPAddr);
1063 
1064  rtentry->SetGateway (gatewayIp);
1065  rtentry->SetDestination (dest);
1066  rtentry->SetOutputDevice (outDevice);
1067  // add rtentry to cache
1068  m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (dest, rtentry));
1069  }
1070 
1071  std::ostringstream currNode, nextNode;
1072  currNode << sourceIPAddr << " (Node " << curr->GetId () << ")";
1073  *os << std::setw (20) << currNode.str ();
1074  // Replace curr with the next node
1075  curr = GetNodeByIp (gatewayIp);
1076  nextNode << "----> " << gatewayIp << " (Node " << curr->GetId () << ")";
1077  *os << nextNode.str () << std::endl;
1078  }
1079  *os << std::endl;
1080  }
1081  else
1082  {
1083  *os << ")" << std::endl;
1084  // No Route exists
1085  *os << "There does not exist a path from Node " << source->GetId ()
1086  << " to Node " << destNode->GetId () << "." << std::endl;
1087  }
1088  // Restore the previous ostream state
1089  (*os).copyfmt (oldState);
1090 }
1091 
1092 void
1094 {
1095  if (g_isCacheDirty)
1096  {
1098  g_isCacheDirty = false;
1099  }
1100 }
1101 
1102 } // 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
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
#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.
virtual void DoDispose(void)
Destructor implementation.
Definition: object.cc:346
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
a virtual net device that bridges multiple LAN segments
SocketErrno
Enumeration of the possible errors returned by a socket.
Definition: socket.h:82
uint32_t FindNetDeviceForNixIndex(uint32_t nodeIndex, Ipv4Address &gatewayIp)
Nix index is with respect to the neighbors.
uint32_t FindTotalNeighbors(void)
Simple iterates through the nodes net-devices and determines how many neighbors it has...
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
void GetAdjacentNetDevices(Ptr< NetDevice > netDevice, Ptr< Channel > channel, NetDeviceContainer &netDeviceContainer)
Given a net-device returns all the adjacent net-devices, essentially getting the neighbors on that ch...
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
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)
void PrintRoutingPath(Ptr< Node > source, Ipv4Address dest, Ptr< OutputStreamWrapper > stream, Time::Unit unit)
Print the Routing Path according to Nix Routing.
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
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
uint32_t BitCount(uint32_t numberOfNeighbors) const
Definition: nix-vector.cc:365
virtual void NotifyRemoveAddress(uint32_t interface, Ipv4InterfaceAddress address)
bool BuildNixVector(const std::vector< Ptr< Node > > &parentVector, uint32_t source, uint32_t dest, Ptr< NixVector > nixVector)
Recurses the parent vector, created by BFS and actually builds the nixvector.
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
Ptr< NixVector > GetNixVectorInCache(Ipv4Address address)
Checks the cache based on dest IP for the nix-vector.
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
void BuildIpv4AddressToNodeMap(void)
Build map from IPv4 Address to Node for faster lookup.
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
Ptr< NixVector > GetNixVector(Ptr< Node > source, Ipv4Address dest, Ptr< NetDevice > oif)
Takes in the source node and dest IP and calls GetNodeByIp, BFS, accounting for any output interface ...
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)
a unique identifier for an interface.
Definition: type-id.h:58
Ptr< Node > GetNodeByIp(Ipv4Address dest)
Iterates through the node list and finds the one corresponding to the given Ipv4Address.
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
bool BFS(uint32_t numberOfNodes, Ptr< Node > source, Ptr< Node > dest, std::vector< Ptr< Node > > &parentVector, Ptr< NetDevice > oif)
Breadth first search algorithm.
static Ipv4AddressToNodeMap g_ipv4AddressToNodeMap