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