Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(929)

Unified Diff: src/pgbr/model/hop-count/ipv4-pgbr-floyd-warshall-hop-count-manager-impl.cc

Issue 15530043: New module pgbr (PGBR routing protocol) and extension of topology-read module
Patch Set: Created 10 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: src/pgbr/model/hop-count/ipv4-pgbr-floyd-warshall-hop-count-manager-impl.cc
===================================================================
new file mode 100644
--- /dev/null
+++ b/src/pgbr/model/hop-count/ipv4-pgbr-floyd-warshall-hop-count-manager-impl.cc
@@ -0,0 +1,289 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) Waterford Institute of Technology, 2013, Julien Mineraud, BioFINT.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Julien Mineraud <julien.mineraud@gmail.com>
+ * Inspired from the work of Craig Dowell (craigdo@ee.washington.edu)
+ * Tom Henderson (tomhend@u.washington.edu)
+ * on the global-route-manager.h/cc of global-routing protocol.
+ *
+ * Acknowledgements:
+ * This work has received support from Science Foundation Ireland via the
+ * "A Biologically inspired framework supporting network management for
+ * the Future Internet" starting investigator award (grant no. 09/SIRG/I1643).
+ */
+
+
+#include "ns3/node-list.h"
+#include "ns3/node.h"
+#include "ns3/channel.h"
+#include "ns3/mobility-model.h"
+#include "ipv4-pgbr-floyd-warshall-hop-count-manager-impl.h"
+#include <algorithm>
+#include <math.h>
+#include <limits>
+#include "ns3/ipv4.h"
+#include "ns3/wifi-net-device.h"
+#include "ns3/wifi-phy.h"
+#include "ns3/data-rate.h"
+
+
+namespace ns3 {
+namespace pgbr {
+
+Ipv4FloydWarshallHopCountManagerImpl::Ipv4FloydWarshallHopCountManagerImpl ()
+{
+ distances = 0;
+ worstDistances = 0;
+ next = 0;
+ hops = 0;
+ nbNodes = 0;
+}
+
+Ipv4FloydWarshallHopCountManagerImpl::~Ipv4FloydWarshallHopCountManagerImpl ()
+{
+ DeleteArrays ();
+}
+
+void
+Ipv4FloydWarshallHopCountManagerImpl::Initialise ()
+{
+ DeleteArrays ();
+ // Set the array of distance as a matrix N*N where N is the number of nodes
+ // Each value is set to infinity
+ nbNodes = NodeList::GetNNodes ();
+ distances = new double_t*[nbNodes];
+ hops = new uint32_t*[nbNodes];
+ next = new uint32_t*[nbNodes];
+
+ for (uint32_t i = 0; i < nbNodes; i++)
+ {
+ distances[i] = new double_t[nbNodes];
+ hops[i] = new uint32_t[nbNodes];
+ next[i] = new uint32_t[nbNodes];
+ for (uint32_t j = 0; j < nbNodes; j++)
+ {
+ if (i == j)
+ {
+ distances [i][j] = 0;
+ hops[i][j] = 0;
+ }
+ else
+ {
+ distances[i][j] = std::numeric_limits<double_t>::infinity ();
+ hops[i][j] = -1;
+ }
+ next[i][j] = nbNodes;
+ }
+ }
+ //Then we insert for each node, the smallest metric for each link
+ for (uint32_t i = 0; i < nbNodes; i++)
+ {
+ Ptr<Node> node = NodeList::GetNode (i);
+ uint32_t ndevices = node->GetNDevices ();
+
+ for (uint32_t j = 0; j < ndevices; j++)
+ {
+ Ptr<NetDevice> netDevice = node->GetDevice (j);
+ Ptr<WifiNetDevice> wifiNetDevice = DynamicCast<WifiNetDevice> (netDevice);
+ Ptr<Channel> channel = netDevice->GetChannel ();
+ if (!channel)
+ {
+ continue;
+ }
+ for (uint32_t k = 0; k < channel->GetNDevices(); k++)
+ {
+ Ptr<NetDevice> otherNetDevice = channel->GetDevice (k);
+ Ptr<WifiNetDevice> otherWifiNetDevice = DynamicCast<WifiNetDevice> (otherNetDevice);
+ if (!otherNetDevice || otherNetDevice == netDevice ||
+ (otherWifiNetDevice && wifiNetDevice &&
+ wifiNetDevice->GetPhy ()->GetChannelNumber () != otherWifiNetDevice->GetPhy ()->GetChannelNumber ()))
+ {
+ continue;
+ }
+ Ptr<Node> neighbour = otherNetDevice->GetNode ();
+ //There is no neighbour if the netDevice is not point to point, so we discard it
+ if (neighbour == 0)
+ {
+ continue;
+ }
+
+ //I'll have to see later on what metric to put in there.
+ double_t metric = 1.0;
+ if (netDevice->IsPointToPoint ())
+ {
+ DataRateValue dataRateAttr;
+ netDevice->GetAttribute("DataRate", dataRateAttr);
+ metric = pow (10.0, 8) / dataRateAttr.Get ().GetBitRate ();
+ }
+ uint32_t idNeighbour = neighbour->GetId ();
+ distances[i][idNeighbour] = metric;
+ hops[i][idNeighbour] = 1;
+ }
+ }
+ }
+
+ worstDistances = new double_t[nbNodes];
+ for (uint32_t i = 0; i < nbNodes; i++)
+ {
+ worstDistances[i] = std::numeric_limits<double_t>::infinity ();
+ }
+ FloydWarshall();
+}
+
+void
+Ipv4FloydWarshallHopCountManagerImpl::FloydWarshall (void)
+{
+ for(uint32_t k = 0; k < nbNodes; k++)
+ {
+ for(uint32_t i = 0; i < nbNodes; i++)
+ {
+ for(uint32_t j = 0; j < nbNodes; j++)
+ {
+ if (distances[i][k] + distances[k][j] < distances[i][j])
+ {
+ distances[i][j] = distances[i][k] + distances[k][j];
+ hops[i][j] = hops[i][k] + hops[k][j];
+ next[i][j] = k;
+ }
+ }
+ }
+ }
+ for(uint32_t j = 0; j < nbNodes; j++)
+ {
+ double_t worstDistance = -1;
+ for(uint32_t i = 0; i < nbNodes; i++)
+ {
+ if(worstDistance < distances[i][j])
+ {
+ worstDistance = distances[i][j];
+ }
+ }
+ worstDistances[j] = worstDistance;
+ }
+}
+
+void
+Ipv4FloydWarshallHopCountManagerImpl::DeleteArrays (void)
+{
+ if (distances != 0)
+ {
+ for(uint32_t i = 0; i < nbNodes; i++)
+ {
+ delete [] distances[i];
+ delete [] hops[i];
+ distances[i] = 0;
+ hops[i] = 0;
+ }
+ delete [] distances;
+ delete [] hops;
+ distances = 0;
+ hops = 0;
+ }
+
+ if (next != 0)
+ {
+ for(uint32_t i = 0; i < nbNodes; i++)
+ {
+ delete [] next[i];
+ next[i] = 0;
+ }
+ delete [] next;
+ next = 0;
+ }
+
+ if (worstDistances != 0)
+ {
+ delete [] worstDistances;
+ worstDistances = 0;
+ }
+}
+
+void
+Ipv4FloydWarshallHopCountManagerImpl::PrintArrays (void)
+{
+ if (distances != 0)
+ {
+ std::cout << "Distance array:\n";
+ }
+ for(uint32_t i = 0; i < nbNodes; i++)
+ {
+ for(uint32_t j = 0; j < nbNodes; j++)
+ {
+ std::cout << distances[i][j] << (j == (nbNodes - 1) ? "\n" : "\t");
+ }
+ }
+
+ if (worstDistances != 0)
+ {
+ std::cout << "Distance array:\n";
+ for(uint32_t i = 0; i < nbNodes; i++)
+ {
+ std::cout << worstDistances[i] << (i == (nbNodes - 1) ? "\n" : "\t");
+ }
+ }
+}
+
+std::vector<Ptr<Node> >
+Ipv4FloydWarshallHopCountManagerImpl::GetPath (Ptr<Node> n1, Ptr<Node> n2)
+{
+ std::vector<Ptr<Node> > path;
+ if (distances[n1->GetId ()][n2->GetId ()] == std::numeric_limits<double_t>::infinity ())
+ {
+ return path;
+ }
+ if (next[n1->GetId ()][n2->GetId ()] >= nbNodes)
+ {
+ path.push_back (n1);
+ path.push_back (n2);
+ }
+ else
+ {
+ std::vector<Ptr<Node> > pathBefore = GetPath (n1, NodeList::GetNode (next[n1->GetId ()][n2->GetId ()]));
+ std::vector<Ptr<Node> > pathAfter = GetPath (NodeList::GetNode (next[n1->GetId ()][n2->GetId ()]), n2);
+ if (!pathBefore.empty () && !pathAfter.empty ())
+ {
+ path.insert (path.begin (), pathBefore.begin (), pathBefore.end ());
+ if (pathAfter.front ()->GetId () == pathBefore.back ()->GetId ())
+ {
+ path.insert (path.end (), ++(pathAfter.begin ()), pathAfter.end ());
+ }
+ else
+ {
+ path.insert (path.end (), pathAfter.begin (), pathAfter.end ());
+ }
+ }
+ }
+ return path;
+}
+
+double_t
+Ipv4FloydWarshallHopCountManagerImpl::GetWeight (Ptr<Node> n1, Ptr<Node> n2)
+{
+ NS_ASSERT (n1 && n2);
+ return distances[n1->GetId ()][n2->GetId ()];
+}
+
+uint32_t
+Ipv4FloydWarshallHopCountManagerImpl::GetHopCount (Ptr<Node> n1, Ptr<Node> n2)
+{
+ NS_ASSERT (n1 && n2);
+ return hops[n1->GetId ()][n2->GetId ()];
+}
+
+
+}} // namespace pgbr, ns3
+

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b