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 
30 
31 namespace ns3 {
32 
33 NS_LOG_COMPONENT_DEFINE ("Ipv4NixVectorRouting");
34 
35 NS_OBJECT_ENSURE_REGISTERED (Ipv4NixVectorRouting);
36 
38 
39 TypeId
41 {
42  static TypeId tid = TypeId ("ns3::Ipv4NixVectorRouting")
44  .AddConstructor<Ipv4NixVectorRouting> ()
45  ;
46  return tid;
47 }
48 
50  : m_totalNeighbors (0)
51 {
53 }
54 
56 {
58 }
59 
60 void
62 {
63  NS_ASSERT (ipv4 != 0);
64  NS_ASSERT (m_ipv4 == 0);
65  NS_LOG_DEBUG ("Created Ipv4NixVectorProtocol");
66 
67  m_ipv4 = ipv4;
68 }
69 
70 void
72 {
74 
75  m_node = 0;
76  m_ipv4 = 0;
77 
79 }
80 
81 
82 void
84 {
86 
87  m_node = node;
88 }
89 
90 void
92 {
94  NodeList::Iterator listEnd = NodeList::End ();
95  for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++)
96  {
97  Ptr<Node> node = *i;
99  if (!rp)
100  {
101  continue;
102  }
103  NS_LOG_LOGIC ("Flushing Nix caches.");
104  rp->FlushNixCache ();
105  rp->FlushIpv4RouteCache ();
106  }
107 }
108 
109 void
111 {
113  m_nixCache.clear ();
114 }
115 
116 void
118 {
120  m_ipv4RouteCache.clear ();
121 }
122 
125 {
127 
128  Ptr<NixVector> nixVector = Create<NixVector> ();
129 
130  // not in cache, must build the nix vector
131  // First, we have to figure out the nodes
132  // associated with these IPs
133  Ptr<Node> destNode = GetNodeByIp (dest);
134  if (destNode == 0)
135  {
136  NS_LOG_ERROR ("No routing path exists");
137  return 0;
138  }
139 
140  // if source == dest, then we have a special case
143  if (source == destNode)
144  {
145  NS_LOG_DEBUG ("Do not processs packets to self");
146  return 0;
147  }
148  else
149  {
150  // otherwise proceed as normal
151  // and build the nix vector
152  std::vector< Ptr<Node> > parentVector;
153 
154  BFS (NodeList::GetNNodes (), source, destNode, parentVector, oif);
155 
156  if (BuildNixVector (parentVector, source->GetId (), destNode->GetId (), nixVector))
157  {
158  return nixVector;
159  }
160  else
161  {
162  NS_LOG_ERROR ("No routing path exists");
163  return 0;
164  }
165  }
166 }
167 
170 {
172 
174 
175  NixMap_t::iterator iter = m_nixCache.find (address);
176  if (iter != m_nixCache.end ())
177  {
178  NS_LOG_LOGIC ("Found Nix-vector in cache.");
179  return iter->second;
180  }
181 
182  // not in cache
183  return 0;
184 }
185 
188 {
190 
192 
193  Ipv4RouteMap_t::iterator iter = m_ipv4RouteCache.find (address);
194  if (iter != m_ipv4RouteCache.end ())
195  {
196  NS_LOG_LOGIC ("Found Ipv4Route in cache.");
197  return iter->second;
198  }
199 
200  // not in cache
201  return 0;
202 }
203 
204 bool
206 {
208 
209  uint32_t numberOfDevices = m_node->GetNDevices ();
210 
211  // here we are building a nix vector to
212  // ourself, so we need to find the loopback
213  // interface and add that to the nix vector
214  Ipv4Address loopback ("127.0.0.1");
215  for (uint32_t i = 0; i < numberOfDevices; i++)
216  {
217  uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->GetDevice (i));
218  Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
219  if (ifAddr.GetLocal () == loopback)
220  {
221  NS_LOG_LOGIC ("Adding loopback to nix.");
222  NS_LOG_LOGIC ("Adding Nix: " << i << " with " << nixVector->BitCount (numberOfDevices)
223  << " bits, for node " << m_node->GetId ());
224  nixVector->AddNeighborIndex (i, nixVector->BitCount (numberOfDevices));
225  return true;
226  }
227  }
228  return false;
229 }
230 
231 bool
232 Ipv4NixVectorRouting::BuildNixVector (const std::vector< Ptr<Node> > & parentVector, uint32_t source, uint32_t dest, Ptr<NixVector> nixVector)
233 {
235 
236  if (source == dest)
237  {
238  return true;
239  }
240 
241  if (parentVector.at (dest) == 0)
242  {
243  return false;
244  }
245 
246  Ptr<Node> parentNode = parentVector.at (dest);
247 
248  uint32_t numberOfDevices = parentNode->GetNDevices ();
249  uint32_t destId = 0;
250  uint32_t totalNeighbors = 0;
251 
252  // scan through the net devices on the parent node
253  // and then look at the nodes adjacent to them
254  for (uint32_t i = 0; i < numberOfDevices; i++)
255  {
256  // Get a net device from the node
257  // as well as the channel, and figure
258  // out the adjacent net devices
259  Ptr<NetDevice> localNetDevice = parentNode->GetDevice (i);
260  if (localNetDevice->IsBridge ())
261  {
262  continue;
263  }
264  Ptr<Channel> channel = localNetDevice->GetChannel ();
265  if (channel == 0)
266  {
267  continue;
268  }
269 
270  // this function takes in the local net dev, and channnel, and
271  // writes to the netDeviceContainer the adjacent net devs
272  NetDeviceContainer netDeviceContainer;
273  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
274 
275  // Finally we can get the adjacent nodes
276  // and scan through them. If we find the
277  // node that matches "dest" then we can add
278  // the index to the nix vector.
279  // the index corresponds to the neighbor index
280  uint32_t offset = 0;
281  for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
282  {
283  Ptr<Node> remoteNode = (*iter)->GetNode ();
284 
285  if (remoteNode->GetId () == dest)
286  {
287  destId = totalNeighbors + offset;
288  }
289  offset += 1;
290  }
291 
292  totalNeighbors += netDeviceContainer.GetN ();
293  }
294  NS_LOG_LOGIC ("Adding Nix: " << destId << " with "
295  << nixVector->BitCount (totalNeighbors) << " bits, for node " << parentNode->GetId ());
296  nixVector->AddNeighborIndex (destId, nixVector->BitCount (totalNeighbors));
297 
298  // recurse through parent vector, grabbing the path
299  // and building the nix vector
300  BuildNixVector (parentVector, source, (parentVector.at (dest))->GetId (), nixVector);
301  return true;
302 }
303 
304 void
306 {
308 
309  for (uint32_t i = 0; i < channel->GetNDevices (); i++)
310  {
311  Ptr<NetDevice> remoteDevice = channel->GetDevice (i);
312  if (remoteDevice != netDevice)
313  {
314  Ptr<BridgeNetDevice> bd = NetDeviceIsBridged (remoteDevice);
315  // we have a bridged device, we need to add all
316  // bridged devices
317  if (bd)
318  {
319  NS_LOG_LOGIC ("Looking through bridge ports of bridge net device " << bd);
320  for (uint32_t j = 0; j < bd->GetNBridgePorts (); ++j)
321  {
322  Ptr<NetDevice> ndBridged = bd->GetBridgePort (j);
323  if (ndBridged == remoteDevice)
324  {
325  NS_LOG_LOGIC ("That bridge port is me, don't walk backward");
326  continue;
327  }
328  Ptr<Channel> chBridged = ndBridged->GetChannel ();
329  if (chBridged == 0)
330  {
331  continue;
332  }
333  GetAdjacentNetDevices (ndBridged, chBridged, netDeviceContainer);
334  }
335  }
336  else
337  {
338  netDeviceContainer.Add (channel->GetDevice (i));
339  }
340  }
341  }
342 }
343 
344 Ptr<Node>
346 {
348 
350  Ptr<Node> destNode;
351 
352  for (NodeContainer::Iterator i = allNodes.Begin (); i != allNodes.End (); ++i)
353  {
354  Ptr<Node> node = *i;
355  Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
356  if (ipv4->GetInterfaceForAddress (dest) != -1)
357  {
358  destNode = node;
359  break;
360  }
361  }
362 
363  if (!destNode)
364  {
365  NS_LOG_ERROR ("Couldn't find dest node given the IP" << dest);
366  return 0;
367  }
368 
369  return destNode;
370 }
371 
372 uint32_t
374 {
375  uint32_t numberOfDevices = m_node->GetNDevices ();
376  uint32_t totalNeighbors = 0;
377 
378  // scan through the net devices on the parent node
379  // and then look at the nodes adjacent to them
380  for (uint32_t i = 0; i < numberOfDevices; i++)
381  {
382  // Get a net device from the node
383  // as well as the channel, and figure
384  // out the adjacent net devices
385  Ptr<NetDevice> localNetDevice = m_node->GetDevice (i);
386  Ptr<Channel> channel = localNetDevice->GetChannel ();
387  if (channel == 0)
388  {
389  continue;
390  }
391 
392  // this function takes in the local net dev, and channnel, and
393  // writes to the netDeviceContainer the adjacent net devs
394  NetDeviceContainer netDeviceContainer;
395  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
396 
397  totalNeighbors += netDeviceContainer.GetN ();
398  }
399 
400  return totalNeighbors;
401 }
402 
405 {
406  NS_LOG_FUNCTION (nd);
407 
408  Ptr<Node> node = nd->GetNode ();
409  uint32_t nDevices = node->GetNDevices ();
410 
411  //
412  // There is no bit on a net device that says it is being bridged, so we have
413  // to look for bridges on the node to which the device is attached. If we
414  // find a bridge, we need to look through its bridge ports (the devices it
415  // bridges) to see if we find the device in question.
416  //
417  for (uint32_t i = 0; i < nDevices; ++i)
418  {
419  Ptr<NetDevice> ndTest = node->GetDevice (i);
420  NS_LOG_LOGIC ("Examine device " << i << " " << ndTest);
421 
422  if (ndTest->IsBridge ())
423  {
424  NS_LOG_LOGIC ("device " << i << " is a bridge net device");
425  Ptr<BridgeNetDevice> bnd = ndTest->GetObject<BridgeNetDevice> ();
426  NS_ABORT_MSG_UNLESS (bnd, "Ipv4NixVectorRouting::NetDeviceIsBridged (): GetObject for <BridgeNetDevice> failed");
427 
428  for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
429  {
430  NS_LOG_LOGIC ("Examine bridge port " << j << " " << bnd->GetBridgePort (j));
431  if (bnd->GetBridgePort (j) == nd)
432  {
433  NS_LOG_LOGIC ("Net device " << nd << " is bridged by " << bnd);
434  return bnd;
435  }
436  }
437  }
438  }
439  NS_LOG_LOGIC ("Net device " << nd << " is not bridged");
440  return 0;
441 }
442 
443 uint32_t
445 {
446  uint32_t numberOfDevices = m_node->GetNDevices ();
447  uint32_t index = 0;
448  uint32_t totalNeighbors = 0;
449 
450  // scan through the net devices on the parent node
451  // and then look at the nodes adjacent to them
452  for (uint32_t i = 0; i < numberOfDevices; i++)
453  {
454  // Get a net device from the node
455  // as well as the channel, and figure
456  // out the adjacent net devices
457  Ptr<NetDevice> localNetDevice = m_node->GetDevice (i);
458  Ptr<Channel> channel = localNetDevice->GetChannel ();
459  if (channel == 0)
460  {
461  continue;
462  }
463 
464  // this function takes in the local net dev, and channnel, and
465  // writes to the netDeviceContainer the adjacent net devs
466  NetDeviceContainer netDeviceContainer;
467  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
468 
469  // check how many neighbors we have
470  if (nodeIndex < (totalNeighbors + netDeviceContainer.GetN ()))
471  {
472  // found the proper net device
473  index = i;
474  Ptr<NetDevice> gatewayDevice = netDeviceContainer.Get (nodeIndex-totalNeighbors);
475  Ptr<Node> gatewayNode = gatewayDevice->GetNode ();
476  Ptr<Ipv4> ipv4 = gatewayNode->GetObject<Ipv4> ();
477 
478  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (gatewayDevice);
479  Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, 0);
480  gatewayIp = ifAddr.GetLocal ();
481  break;
482  }
483  totalNeighbors += netDeviceContainer.GetN ();
484  }
485 
486  return index;
487 }
488 
491 {
493  Ptr<Ipv4Route> rtentry;
494  Ptr<NixVector> nixVectorInCache;
495  Ptr<NixVector> nixVectorForPacket;
496 
498 
499  NS_LOG_DEBUG ("Dest IP from header: " << header.GetDestination ());
500  // check if cache
501  nixVectorInCache = GetNixVectorInCache (header.GetDestination ());
502 
503  // not in cache
504  if (!nixVectorInCache)
505  {
506  NS_LOG_LOGIC ("Nix-vector not in cache, build: ");
507  // Build the nix-vector, given this node and the
508  // dest IP address
509  nixVectorInCache = GetNixVector (m_node, header.GetDestination (), oif);
510 
511  // cache it
512  m_nixCache.insert (NixMap_t::value_type (header.GetDestination (), nixVectorInCache));
513  }
514 
515  // path exists
516  if (nixVectorInCache)
517  {
518  NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache);
519 
520  // create a new nix vector to be used,
521  // we want to keep the cached version clean
522  nixVectorForPacket = Create<NixVector> ();
523  nixVectorForPacket = nixVectorInCache->Copy ();
524 
525  // Get the interface number that we go out of, by extracting
526  // from the nix-vector
527  if (m_totalNeighbors == 0)
528  {
530  }
531 
532  // Get the interface number that we go out of, by extracting
533  // from the nix-vector
534  uint32_t numberOfBits = nixVectorForPacket->BitCount (m_totalNeighbors);
535  uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
536 
537  // Search here in a cache for this node index
538  // and look for a Ipv4Route
539  rtentry = GetIpv4RouteInCache (header.GetDestination ());
540 
541  if (!rtentry || !(rtentry->GetOutputDevice () == oif))
542  {
543  // not in cache or a different specified output
544  // device is to be used
545 
546  // first, make sure we erase existing (incorrect)
547  // rtentry from the map
548  if (rtentry)
549  {
550  m_ipv4RouteCache.erase (header.GetDestination ());
551  }
552 
553  NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
554  Ipv4Address gatewayIp;
555  uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
556  int32_t interfaceIndex = 0;
557 
558  if (!oif)
559  {
560  interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->GetDevice (index));
561  }
562  else
563  {
564  interfaceIndex = (m_ipv4)->GetInterfaceForDevice (oif);
565  }
566 
567  NS_ASSERT_MSG (interfaceIndex != -1, "Interface index not found for device");
568 
569  Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
570 
571  // start filling in the Ipv4Route info
572  rtentry = Create<Ipv4Route> ();
573  rtentry->SetSource (ifAddr.GetLocal ());
574 
575  rtentry->SetGateway (gatewayIp);
576  rtentry->SetDestination (header.GetDestination ());
577 
578  if (!oif)
579  {
580  rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
581  }
582  else
583  {
584  rtentry->SetOutputDevice (oif);
585  }
586 
587  sockerr = Socket::ERROR_NOTERROR;
588 
589  // add rtentry to cache
590  m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.GetDestination (), rtentry));
591  }
592 
593  NS_LOG_LOGIC ("Nix-vector contents: " << *nixVectorInCache << " : Remaining bits: " << nixVectorForPacket->GetRemainingBits ());
594 
595  // Add nix-vector in the packet class
596  // make sure the packet exists first
597  if (p)
598  {
599  NS_LOG_LOGIC ("Adding Nix-vector to packet: " << *nixVectorForPacket);
600  p->SetNixVector (nixVectorForPacket);
601  }
602  }
603  else // path doesn't exist
604  {
605  NS_LOG_ERROR ("No path to the dest: " << header.GetDestination ());
606  sockerr = Socket::ERROR_NOROUTETOHOST;
607  }
608 
609  return rtentry;
610 }
611 
612 bool
616 {
618 
620 
621  Ptr<Ipv4Route> rtentry;
622 
623  // Get the nix-vector from the packet
624  Ptr<NixVector> nixVector = p->GetNixVector ();
625 
626  // If nixVector isn't in packet, something went wrong
627  NS_ASSERT (nixVector);
628 
629  // Get the interface number that we go out of, by extracting
630  // from the nix-vector
631  if (m_totalNeighbors == 0)
632  {
634  }
635  uint32_t numberOfBits = nixVector->BitCount (m_totalNeighbors);
636  uint32_t nodeIndex = nixVector->ExtractNeighborIndex (numberOfBits);
637 
638  rtentry = GetIpv4RouteInCache (header.GetDestination ());
639  // not in cache
640  if (!rtentry)
641  {
642  NS_LOG_LOGIC ("Ipv4Route not in cache, build: ");
643  Ipv4Address gatewayIp;
644  uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
645  uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->GetDevice (index));
646  Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
647 
648  // start filling in the Ipv4Route info
649  rtentry = Create<Ipv4Route> ();
650  rtentry->SetSource (ifAddr.GetLocal ());
651 
652  rtentry->SetGateway (gatewayIp);
653  rtentry->SetDestination (header.GetDestination ());
654  rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIndex));
655 
656  // add rtentry to cache
657  m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.GetDestination (), rtentry));
658  }
659 
660  NS_LOG_LOGIC ("At Node " << m_node->GetId () << ", Extracting " << numberOfBits <<
661  " bits from Nix-vector: " << nixVector << " : " << *nixVector);
662 
663  // call the unicast callback
664  // local deliver is handled by Ipv4StaticRoutingImpl
665  // so this code is never even called if the packet is
666  // destined for this node.
667  ucb (rtentry, p, header);
668 
669  return true;
670 }
671 
672 void
674 {
675 
677 
678  std::ostream* os = stream->GetStream ();
679  *os << "NixCache:" << std::endl;
680  if (m_nixCache.size () > 0)
681  {
682  *os << "Destination NixVector" << std::endl;
683  for (NixMap_t::const_iterator it = m_nixCache.begin (); it != m_nixCache.end (); it++)
684  {
685  std::ostringstream dest;
686  dest << it->first;
687  *os << std::setiosflags (std::ios::left) << std::setw (16) << dest.str ();
688  *os << *(it->second) << std::endl;
689  }
690  }
691  *os << "Ipv4RouteCache:" << std::endl;
692  if (m_ipv4RouteCache.size () > 0)
693  {
694  *os << "Destination Gateway Source OutputDevice" << std::endl;
695  for (Ipv4RouteMap_t::const_iterator it = m_ipv4RouteCache.begin (); it != m_ipv4RouteCache.end (); it++)
696  {
697  std::ostringstream dest, gw, src;
698  dest << it->second->GetDestination ();
699  *os << std::setiosflags (std::ios::left) << std::setw (16) << dest.str ();
700  gw << it->second->GetGateway ();
701  *os << std::setiosflags (std::ios::left) << std::setw (16) << gw.str ();
702  src << it->second->GetSource ();
703  *os << std::setiosflags (std::ios::left) << std::setw (16) << src.str ();
704  *os << " ";
705  if (Names::FindName (it->second->GetOutputDevice ()) != "")
706  {
707  *os << Names::FindName (it->second->GetOutputDevice ());
708  }
709  else
710  {
711  *os << it->second->GetOutputDevice ()->GetIfIndex ();
712  }
713  *os << std::endl;
714  }
715  }
716 }
717 
718 // virtual functions from Ipv4RoutingProtocol
719 void
721 {
722  g_isCacheDirty = true;
723 }
724 void
726 {
727  g_isCacheDirty = true;
728 }
729 void
731 {
732  g_isCacheDirty = true;
733 }
734 void
736 {
737  g_isCacheDirty = true;
738 }
739 
740 bool
741 Ipv4NixVectorRouting::BFS (uint32_t numberOfNodes, Ptr<Node> source,
742  Ptr<Node> dest, std::vector< Ptr<Node> > & parentVector,
743  Ptr<NetDevice> oif)
744 {
746 
747  NS_LOG_LOGIC ("Going from Node " << source->GetId () << " to Node " << dest->GetId ());
748  std::queue< Ptr<Node> > greyNodeList; // discovered nodes with unexplored children
749 
750  // reset the parent vector
751  parentVector.clear ();
752  parentVector.reserve (sizeof (Ptr<Node>)*numberOfNodes);
753  parentVector.insert (parentVector.begin (), sizeof (Ptr<Node>)*numberOfNodes, 0); // initialize to 0
754 
755  // Add the source node to the queue, set its parent to itself
756  greyNodeList.push (source);
757  parentVector.at (source->GetId ()) = source;
758 
759  // BFS loop
760  while (greyNodeList.size () != 0)
761  {
762  Ptr<Node> currNode = greyNodeList.front ();
763  Ptr<Ipv4> ipv4 = currNode->GetObject<Ipv4> ();
764 
765  if (currNode == dest)
766  {
767  NS_LOG_LOGIC ("Made it to Node " << currNode->GetId ());
768  return true;
769  }
770 
771  // if this is the first iteration of the loop and a
772  // specific output interface was given, make sure
773  // we go this way
774  if (currNode == source && oif)
775  {
776  // make sure that we can go this way
777  if (ipv4)
778  {
779  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (oif);
780  if (!(ipv4->IsUp (interfaceIndex)))
781  {
782  NS_LOG_LOGIC ("Ipv4Interface is down");
783  return false;
784  }
785  }
786  if (!(oif->IsLinkUp ()))
787  {
788  NS_LOG_LOGIC ("Link is down.");
789  return false;
790  }
791  Ptr<Channel> channel = oif->GetChannel ();
792  if (channel == 0)
793  {
794  return false;
795  }
796 
797  // this function takes in the local net dev, and channnel, and
798  // writes to the netDeviceContainer the adjacent net devs
799  NetDeviceContainer netDeviceContainer;
800  GetAdjacentNetDevices (oif, channel, netDeviceContainer);
801 
802  // Finally we can get the adjacent nodes
803  // and scan through them. We push them
804  // to the greyNode queue, if they aren't
805  // already there.
806  for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
807  {
808  Ptr<Node> remoteNode = (*iter)->GetNode ();
809 
810  // check to see if this node has been pushed before
811  // by checking to see if it has a parent
812  // if it doesn't (null or 0), then set its parent and
813  // push to the queue
814  if (parentVector.at (remoteNode->GetId ()) == 0)
815  {
816  parentVector.at (remoteNode->GetId ()) = currNode;
817  greyNodeList.push (remoteNode);
818  }
819  }
820  }
821  else
822  {
823  // Iterate over the current node's adjacent vertices
824  // and push them into the queue
825  for (uint32_t i = 0; i < (currNode->GetNDevices ()); i++)
826  {
827  // Get a net device from the node
828  // as well as the channel, and figure
829  // out the adjacent net device
830  Ptr<NetDevice> localNetDevice = currNode->GetDevice (i);
831 
832  // make sure that we can go this way
833  if (ipv4)
834  {
835  uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (currNode->GetDevice (i));
836  if (!(ipv4->IsUp (interfaceIndex)))
837  {
838  NS_LOG_LOGIC ("Ipv4Interface is down");
839  continue;
840  }
841  }
842  if (!(localNetDevice->IsLinkUp ()))
843  {
844  NS_LOG_LOGIC ("Link is down.");
845  continue;
846  }
847  Ptr<Channel> channel = localNetDevice->GetChannel ();
848  if (channel == 0)
849  {
850  continue;
851  }
852 
853  // this function takes in the local net dev, and channnel, and
854  // writes to the netDeviceContainer the adjacent net devs
855  NetDeviceContainer netDeviceContainer;
856  GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
857 
858  // Finally we can get the adjacent nodes
859  // and scan through them. We push them
860  // to the greyNode queue, if they aren't
861  // already there.
862  for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
863  {
864  Ptr<Node> remoteNode = (*iter)->GetNode ();
865 
866  // check to see if this node has been pushed before
867  // by checking to see if it has a parent
868  // if it doesn't (null or 0), then set its parent and
869  // push to the queue
870  if (parentVector.at (remoteNode->GetId ()) == 0)
871  {
872  parentVector.at (remoteNode->GetId ()) = currNode;
873  greyNodeList.push (remoteNode);
874  }
875  }
876  }
877  }
878 
879  // Pop off the head grey node. We have all its children.
880  // It is now black.
881  greyNodeList.pop ();
882  }
883 
884  // Didn't find the dest...
885  return false;
886 }
887 
888 void
890 {
891  if (g_isCacheDirty)
892  {
894  g_isCacheDirty = false;
895  }
896 }
897 
898 } // namespace ns3
void FlushGlobalNixRoutingCache(void) const
Called when run-time link topology change occurs which iterates through the node list and flushes any...
Iterator Begin(void) const
Get an iterator which refers to the first NetDevice in the container.
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 "...
SocketErrno
Enumeration of the possible errors returned by a socket.
Definition: socket.h:82
static uint32_t GetNNodes(void)
Definition: node-list.cc:246
Callback template class.
Definition: callback.h:978
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:44
std::vector< Ptr< Node > >::const_iterator Iterator
Node container iterator.
Ipv4Address GetLocal(void) const
Get the local address.
Ptr< NetDevice > Get(uint32_t i) const
Get the Ptr stored in this container at a given index.
bool BuildNixVectorLocal(Ptr< NixVector > nixVector)
Ptr< NixVector > Copy(void) const
Definition: nix-vector.cc:71
Ipv4Address GetDestination(void) const
Definition: ipv4-header.cc:304
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file...
Definition: assert.h:61
void DoDispose(void)
Destructor implementation.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:201
Iterator End(void) const
Get an iterator which indicates past-the-last Node in the container.
virtual void DoDispose(void)
Destructor implementation.
Definition: object.cc:338
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
a virtual net device that bridges multiple LAN segments
Ptr< NixVector > GetNixVector(void) const
Get the packet nix-vector.
Definition: packet.cc:247
uint32_t FindNetDeviceForNixIndex(uint32_t nodeIndex, Ipv4Address &gatewayIp)
Ptr< NixVector > GetNixVector(Ptr< Node >, Ipv4Address, Ptr< NetDevice >)
void SetSource(Ipv4Address src)
Definition: ipv4-route.cc:49
uint32_t GetN(void) const
Get the number of Ptr stored in this container.
Ptr< NetDevice > GetOutputDevice(void) const
Definition: ipv4-route.cc:84
Ptr< NixVector > GetNixVectorInCache(Ipv4Address)
Packet header for IPv4.
Definition: ipv4-header.h:31
uint32_t ExtractNeighborIndex(uint32_t numberOfBits)
Definition: nix-vector.cc:160
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:241
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:234
Nix-vector routing protocol.
Ptr< Node > GetNodeByIp(Ipv4Address)
holds a vector of ns3::NetDevice pointers
Ptr< NetDevice > GetDevice(uint32_t index) const
Retrieve the index-th NetDevice associated to this node.
Definition: node.cc:134
Ptr< BridgeNetDevice > NetDeviceIsBridged(Ptr< NetDevice > nd) const
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:252
virtual void NotifyInterfaceDown(uint32_t interface)
Access to the Ipv4 forwarding table, interfaces, and configuration.
Definition: ipv4.h:76
uint32_t GetNDevices(void) const
Definition: node.cc:142
virtual void NotifyInterfaceUp(uint32_t interface)
Every class exported by the ns3 library is enclosed in the ns3 namespace.
keep track of a set of node pointers.
std::vector< Ptr< Node > >::const_iterator Iterator
Node container iterator.
Definition: node-list.h:44
Iterator Begin(void) const
Get an iterator which refers to the first Node in the container.
void SetOutputDevice(Ptr< NetDevice > outputDevice)
Equivalent in Linux to dst_entry.dev.
Definition: ipv4-route.cc:77
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)
void GetAdjacentNetDevices(Ptr< NetDevice >, Ptr< Channel >, NetDeviceContainer &)
#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:84
static NodeContainer GetGlobal(void)
Create a NodeContainer that contains a list of all nodes created through NodeContainer::Create() and ...
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)
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:40
#define NS_ABORT_MSG_UNLESS(cond, msg)
Abnormal program termination if a condition is false, with a message.
Definition: abort.h:144
uint32_t GetId(void) const
Definition: node.cc:106
a class to store IPv4 address information on an interface
static Iterator Begin(void)
Definition: node-list.cc:228
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:236
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)
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:664
Abstract base class for IPv4 routing protocols.
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:220
void AddNeighborIndex(uint32_t newBits, uint32_t numberOfBits)
Definition: nix-vector.cc:88
tuple address
Definition: first.py:37
Iterator End(void) const
Get an iterator which indicates past-the-last NetDevice in the container.
virtual void NotifyAddAddress(uint32_t interface, Ipv4InterfaceAddress address)
Ptr< T > GetObject(void) const
Get a pointer to the requested aggregated Object.
Definition: object.h:455
a unique identifier for an interface.
Definition: type-id.h:51
TypeId SetParent(TypeId tid)
Definition: type-id.cc:631
virtual void PrintRoutingTable(Ptr< OutputStreamWrapper > stream) const
Print the Routing Table entries.
uint32_t BitCount(uint32_t numberOfNeighbors) const
Definition: nix-vector.cc:365
Ptr< Ipv4Route > GetIpv4RouteInCache(Ipv4Address)
std::ostream * GetStream(void)
Return a pointer to an ostream previously set in the wrapper.
void SetDestination(Ipv4Address dest)
Definition: ipv4-route.cc:35
bool BFS(uint32_t numberOfNodes, Ptr< Node > source, Ptr< Node > dest, std::vector< Ptr< Node > > &parentVector, Ptr< NetDevice > oif)