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 |
+ |