plugins+tools: Adding experimental RocketfuelMapReader and tool to convert topology from .cch format into annotated topology format
diff --git a/plugins/topology/rocketfuel-map-reader.cc b/plugins/topology/rocketfuel-map-reader.cc
new file mode 100644
index 0000000..bc44f14
--- /dev/null
+++ b/plugins/topology/rocketfuel-map-reader.cc
@@ -0,0 +1,788 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013 University of California, Los Angeles
+ *
+ * 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: Ilya Moiseenko <iliamo@cs.ucla.edu>
+ * Hajime Tazaki (tazaki@sfc.wide.ad.jp)
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ *
+ */
+
+#include "rocketfuel-map-reader.h"
+
+#include "ns3/nstime.h"
+#include "ns3/log.h"
+#include "ns3/fatal-error.h"
+#include "ns3/assert.h"
+#include "ns3/names.h"
+#include "ns3/net-device-container.h"
+#include "ns3/point-to-point-helper.h"
+#include "ns3/point-to-point-net-device.h"
+#include "ns3/internet-stack-helper.h"
+#include "ns3/ipv4-address-helper.h"
+#include "ns3/ipv4-global-routing-helper.h"
+#include "ns3/drop-tail-queue.h"
+#include "ns3/ipv4-interface.h"
+#include "ns3/ipv4.h"
+#include "ns3/string.h"
+#include "ns3/pointer.h"
+#include "ns3/uinteger.h"
+#include "ns3/ipv4-address.h"
+#include "ns3/node-list.h"
+#include "ns3/random-variable.h"
+
+#include "ns3/mobility-model.h"
+
+#include <regex.h>
+
+#include <boost/foreach.hpp>
+#include <boost/lexical_cast.hpp>
+
+#include <boost/graph/graphviz.hpp>
+#include <boost/graph/connected_components.hpp>
+
+#include <iomanip>
+
+using namespace std;
+using namespace boost;
+
+NS_LOG_COMPONENT_DEFINE ("RocketfuelMapReader");
+
+namespace ns3 {
+
+RocketfuelMapReader::RocketfuelMapReader (const std::string &path/*=""*/, double scale/*=1.0*/, const std::string &referenceOspfRate)
+ : AnnotatedTopologyReader (path, scale)
+ , m_referenceOspfRate (boost::lexical_cast<DataRate> (referenceOspfRate))
+{
+}
+
+RocketfuelMapReader::~RocketfuelMapReader ()
+{
+}
+
+NodeContainer
+RocketfuelMapReader::Read ()
+{
+ NS_FATAL_ERROR ("Deprecated call. Use the other overloaded method instead");
+ return NodeContainer ();
+}
+
+
+/* uid @loc [+] [bb] (num_neigh) [&ext] -> <nuid-1> <nuid-2> ... {-euid} ... =name[!] rn */
+
+#define REGMATCH_MAX 16
+
+#define START "^"
+#define END "$"
+#define SPACE "[ \t]+"
+#define MAYSPACE "[ \t]*"
+
+#define ROCKETFUEL_MAPS_LINE \
+START "(-*[0-9]+)" SPACE "(@[?A-Za-z0-9,+]+)" SPACE \
+"(\\+)*" MAYSPACE "(bb)*" MAYSPACE \
+"\\(([0-9]+)\\)" SPACE "(&[0-9]+)*" MAYSPACE \
+"->" MAYSPACE "(<[0-9 \t<>]+>)*" MAYSPACE \
+"(\\{-[0-9\\{\\} \t-]+\\})*" SPACE \
+"=([A-Za-z0-9.!-]+)" SPACE "r([0-9])" \
+MAYSPACE END
+
+void
+RocketfuelMapReader::CreateLink (string nodeName1, string nodeName2,
+ double averageRtt,
+ const string &minBw, const string &maxBw,
+ const string &minDelay, const string &maxDelay)
+{
+ Ptr<Node> node1 = Names::Find<Node> (m_path, nodeName1);
+ Ptr<Node> node2 = Names::Find<Node> (m_path, nodeName2);
+ Link link (node1, nodeName1, node2, nodeName2);
+
+ DataRate randBandwidth
+ (m_randVar.GetInteger (static_cast<uint32_t> (lexical_cast<DataRate> (minBw).GetBitRate ()),
+ static_cast<uint32_t> (lexical_cast<DataRate> (maxBw).GetBitRate ())));
+
+ int32_t metric = std::max (1, static_cast<int32_t> (1.0 * m_referenceOspfRate.GetBitRate () / randBandwidth.GetBitRate ()));
+
+ Time randDelay =
+ Time::FromDouble ((m_randVar.GetValue (lexical_cast<Time> (minDelay).ToDouble (Time::US),
+ lexical_cast<Time> (maxDelay).ToDouble (Time::US))),
+ Time::US);
+
+ uint32_t queue = ceil (averageRtt * (randBandwidth.GetBitRate () / 8.0 / 1100.0));
+
+ link.SetAttribute ("DataRate", boost::lexical_cast<string> (randBandwidth));
+ link.SetAttribute ("OSPF", boost::lexical_cast<string> (metric));
+ link.SetAttribute ("Delay", boost::lexical_cast<string> (ceil (randDelay.ToDouble (Time::US)))+"us");
+ link.SetAttribute ("MaxPackets", boost::lexical_cast<string> (queue));
+
+ AddLink (link);
+}
+
+// NodeContainer
+void
+RocketfuelMapReader::GenerateFromMapsFile (int argc, char *argv[])
+{
+ string uid;
+ string loc;
+ string ptr;
+ string name;
+ string nuid;
+ bool dns = false;
+ bool bb = false;
+ int num_neigh_s = 0;
+ unsigned int num_neigh = 0;
+ int radius = 0;
+ vector <string> neigh_list;
+
+ uid = argv[0];
+ loc = argv[1];
+
+ if (argv[2])
+ {
+ dns = true;
+ }
+
+ if (argv[3])
+ {
+ bb = true;
+ }
+
+ num_neigh_s = ::atoi (argv[4]);
+ if (num_neigh_s < 0)
+ {
+ num_neigh = 0;
+ NS_LOG_WARN ("Negative number of neighbors given");
+ }
+ else
+ {
+ num_neigh = num_neigh_s;
+ }
+
+ /* neighbors */
+ if (argv[6])
+ {
+ char *nbr;
+ char *stringp = argv[6];
+ while ((nbr = strsep (&stringp, " \t")) != NULL)
+ {
+ nbr[strlen (nbr) - 1] = '\0';
+ neigh_list.push_back (nbr + 1);
+ }
+ }
+
+ if (num_neigh != neigh_list.size ())
+ {
+ NS_LOG_WARN ("Given number of neighbors = " << num_neigh << " != size of neighbors list = " << neigh_list.size ());
+ }
+
+ /* externs */
+ if (argv[7])
+ {
+ // euid = argv[7];
+ }
+
+ /* name */
+ if (argv[8])
+ {
+ name = argv[8];
+ }
+
+ radius = ::atoi (&argv[9][1]);
+ if (radius > 0)
+ {
+ return;
+ }
+
+ // Create node and link
+ if (uid.empty ())
+ return;
+
+
+ node_map_t::iterator node = m_graphNodes.find (uid);
+ if (node == m_graphNodes.end ())
+ {
+ bool ok;
+ tie (node, ok) = m_graphNodes.insert (make_pair (uid, add_vertex (nodeProperty (uid), m_graph)));
+ NS_ASSERT (ok == true);
+
+ put (vertex_index, m_graph, node->second, m_maxNodeId);
+ m_maxNodeId ++;
+ }
+
+ for (uint32_t i = 0; i < neigh_list.size (); ++i)
+ {
+ nuid = neigh_list[i];
+
+ if (nuid.empty ())
+ {
+ continue;
+ }
+
+ node_map_t::iterator otherNode = m_graphNodes.find (nuid);
+ if (otherNode == m_graphNodes.end ())
+ {
+ bool ok;
+ tie (otherNode, ok) = m_graphNodes.insert (make_pair (nuid, add_vertex(nodeProperty (nuid), m_graph)));
+ NS_ASSERT (ok == true);
+
+ put (vertex_index, m_graph, otherNode->second, m_maxNodeId);
+ m_maxNodeId ++;
+ }
+
+ // cout << node->second << " <-> " << otherNode->second << endl;
+ // parallel edges are disabled in the graph, so no need to worry
+ add_edge (node->second, otherNode->second, m_graph);
+ }
+}
+
+void RocketfuelMapReader::assignGw (Traits::vertex_descriptor vertex, uint32_t degree, node_type_t nodeType)
+{
+ graph_traits<Graph>::adjacency_iterator u, endu;
+ for (tie (u, endu) = adjacent_vertices (vertex, m_graph); u != endu; u++)
+ {
+ if (get (vertex_rank, m_graph, *u) != UNKNOWN)
+ continue;
+
+ put (vertex_rank, m_graph, *u, nodeType);
+ put (vertex_color, m_graph, *u, "green");
+
+ uint32_t u_degree = out_degree (*u, m_graph);
+ if (u_degree < degree)
+ assignGw (*u, degree, BACKBONE);
+ }
+};
+
+void
+RocketfuelMapReader::AssignClients (uint32_t clientDegree, uint32_t gwDegree)
+{
+ graph_traits<Graph>::vertex_iterator v, endv;
+ for (tie(v, endv) = vertices(m_graph); v != endv; v++)
+ {
+ uint32_t degree = out_degree (*v, m_graph);
+ if (degree == clientDegree)
+ {
+ put (vertex_rank, m_graph, *v, CLIENT);
+ put (vertex_color, m_graph, *v, "red");
+
+ assignGw (*v, gwDegree+1, GATEWAY);
+ }
+ }
+};
+
+NodeContainer
+RocketfuelMapReader::Read (RocketfuelParams params, bool keepOneComponent/*=true*/, bool connectBackbones/*=true*/)
+{
+ m_maxNodeId = 0;
+
+ ifstream topgen;
+ topgen.open (GetFileName ().c_str ());
+ //NodeContainer nodes;
+ UniformVariable var;
+
+ istringstream lineBuffer;
+ string line;
+ int lineNumber = 0;
+ char errbuf[512];
+
+ if (!topgen.is_open ())
+ {
+ NS_LOG_WARN ("Couldn't open the file " << GetFileName ());
+ return m_nodes;
+ }
+
+ while (!topgen.eof ())
+ {
+ int ret;
+ int argc;
+ char *argv[REGMATCH_MAX];
+ char *buf;
+
+ lineNumber++;
+ line.clear ();
+ lineBuffer.clear ();
+
+ getline (topgen, line);
+ buf = (char *)line.c_str ();
+
+ regmatch_t regmatch[REGMATCH_MAX];
+ regex_t regex;
+
+ ret = regcomp (®ex, ROCKETFUEL_MAPS_LINE, REG_EXTENDED | REG_NEWLINE);
+ if (ret != 0)
+ {
+ regerror (ret, ®ex, errbuf, sizeof (errbuf));
+ regfree (®ex);
+ continue;
+ }
+
+ ret = regexec (®ex, buf, REGMATCH_MAX, regmatch, 0);
+ if (ret == REG_NOMATCH)
+ {
+ NS_LOG_WARN ("match failed (maps file): %s" << buf);
+ regfree (®ex);
+ continue;
+ }
+
+ line = buf;
+ argc = 0;
+
+ /* regmatch[0] is the entire strings that matched */
+ for (int i = 1; i < REGMATCH_MAX; i++)
+ {
+ if (regmatch[i].rm_so == -1)
+ {
+ argv[i - 1] = NULL;
+ }
+ else
+ {
+ line[regmatch[i].rm_eo] = '\0';
+ argv[i - 1] = &line[regmatch[i].rm_so];
+ argc = i;
+ }
+ }
+
+ GenerateFromMapsFile (argc, argv);
+ regfree (®ex);
+ }
+
+ if (keepOneComponent)
+ {
+ NS_LOG_DEBUG ("Before eliminating disconnected nodes: " << num_vertices(m_graph));
+ KeepOnlyBiggestConnectedComponent ();
+ NS_LOG_DEBUG ("After eliminating disconnected nodes: " << num_vertices(m_graph));
+ }
+
+ for (int clientDegree = 1; clientDegree <= params.clientNodeDegrees; clientDegree++)
+ {
+ AssignClients (clientDegree, std::min (clientDegree, 3));
+ }
+
+ graph_traits<Graph>::vertex_iterator v, endv;
+ for (tie(v, endv) = vertices(m_graph); v != endv; v++)
+ {
+ node_type_t type = get (vertex_rank, m_graph, *v);
+ if (type == UNKNOWN)
+ {
+ put (vertex_rank, m_graph, *v, BACKBONE);
+ put (vertex_color, m_graph, *v, "blue");
+ }
+ }
+
+ if (connectBackbones)
+ {
+ ConnectBackboneRouters ();
+ }
+
+ graph_traits<Graph>::edge_iterator e, ende;
+ for (tie (e, ende) = edges (m_graph); e != ende; )
+ {
+ Traits::vertex_descriptor
+ u = source (*e, m_graph),
+ v = target (*e, m_graph);
+
+ node_type_t
+ u_type = get (vertex_rank, m_graph, u),
+ v_type = get (vertex_rank, m_graph, v);
+
+ if (u_type == BACKBONE && v_type == BACKBONE)
+ {
+ // ok
+ }
+ else if ((u_type == GATEWAY && v_type == BACKBONE) ||
+ (u_type == BACKBONE && v_type == GATEWAY ))
+ {
+ // ok
+ }
+ else if (u_type == GATEWAY && v_type == GATEWAY)
+ {
+ // ok
+ }
+ else if ((u_type == GATEWAY && v_type == CLIENT) ||
+ (u_type == CLIENT && v_type == GATEWAY ))
+ {
+ // ok
+ }
+ else
+ {
+ // not ok
+ NS_LOG_DEBUG ("Wrong link type between nodes: " << u_type << " <-> " << v_type << " (deleting the link)");
+
+ graph_traits<Graph>::edge_iterator tmp = e;
+ tmp++;
+
+ remove_edge (*e, m_graph);
+ e = tmp;
+ continue;
+ }
+ e++;
+ }
+
+ if (keepOneComponent)
+ {
+ NS_LOG_DEBUG ("Before 2 eliminating disconnected nodes: " << num_vertices(m_graph));
+ KeepOnlyBiggestConnectedComponent ();
+ NS_LOG_DEBUG ("After 2 eliminating disconnected nodes: " << num_vertices(m_graph));
+ }
+
+ for (tie(v, endv) = vertices(m_graph); v != endv; v++)
+ {
+ string nodeName = get (vertex_name, m_graph, *v);
+ Ptr<Node> node = CreateNode (nodeName, 0);
+
+ node_type_t type = get (vertex_rank, m_graph, *v);
+ switch (type)
+ {
+ case BACKBONE:
+ Names::Rename (nodeName, "bb-" + nodeName);
+ put (vertex_name, m_graph, *v, "bb-" + nodeName);
+ m_backboneRouters.Add (node);
+ break;
+ case CLIENT:
+ Names::Rename (nodeName, "leaf-" + nodeName);
+ put (vertex_name, m_graph, *v, "leaf-" + nodeName);
+ m_customerRouters.Add (node);
+ break;
+ case GATEWAY:
+ Names::Rename (nodeName, "gw-" + nodeName);
+ put (vertex_name, m_graph, *v, "gw-" + nodeName);
+ m_gatewayRouters.Add (node);
+ break;
+ case UNKNOWN:
+ NS_FATAL_ERROR ("Should not happen");
+ break;
+ }
+ }
+
+ for (tie (e, ende) = edges (m_graph); e != ende; e++)
+ {
+ Traits::vertex_descriptor
+ u = source (*e, m_graph),
+ v = target (*e, m_graph);
+
+ node_type_t
+ u_type = get (vertex_rank, m_graph, u),
+ v_type = get (vertex_rank, m_graph, v);
+
+ string
+ u_name = get (vertex_name, m_graph, u),
+ v_name = get (vertex_name, m_graph, v);
+
+ if (u_type == BACKBONE && v_type == BACKBONE)
+ {
+ CreateLink (u_name, v_name,
+ params.averageRtt,
+ params.minb2bBandwidth, params.maxb2bBandwidth,
+ params.minb2bDelay, params.maxb2bDelay);
+ }
+ else if ((u_type == GATEWAY && v_type == BACKBONE) ||
+ (u_type == BACKBONE && v_type == GATEWAY ))
+ {
+ CreateLink (u_name, v_name,
+ params.averageRtt,
+ params.minb2gBandwidth, params.maxb2gBandwidth,
+ params.minb2gDelay, params.maxb2gDelay);
+ }
+ else if (u_type == GATEWAY && v_type == GATEWAY)
+ {
+ CreateLink (u_name, v_name,
+ params.averageRtt,
+ params.minb2gBandwidth, params.maxb2gBandwidth,
+ params.minb2gDelay, params.maxb2gDelay);
+ }
+ else if ((u_type == GATEWAY && v_type == CLIENT) ||
+ (u_type == CLIENT && v_type == GATEWAY ))
+ {
+ CreateLink (u_name, v_name,
+ params.averageRtt,
+ params.ming2cBandwidth, params.maxg2cBandwidth,
+ params.ming2cDelay, params.maxg2cDelay);
+ }
+ else
+ {
+ NS_FATAL_ERROR ("Wrong link type between nodes: " << u_type << " <-> " << v_type);
+ }
+ }
+
+ ApplySettings ();
+
+ NS_LOG_INFO ("Clients: " << m_customerRouters.GetN ());
+ NS_LOG_INFO ("Gateways: " << m_gatewayRouters.GetN ());
+ NS_LOG_INFO ("Backbones: " << m_backboneRouters.GetN ());
+ NS_LOG_INFO ("Links: " << GetLinks ().size ());
+
+ return m_nodes;
+}
+
+const NodeContainer &
+RocketfuelMapReader::GetBackboneRouters () const
+{
+ return m_backboneRouters;
+}
+
+const NodeContainer &
+RocketfuelMapReader::GetGatewayRouters () const
+{
+ return m_gatewayRouters;
+}
+
+const NodeContainer &
+RocketfuelMapReader::GetCustomerRouters () const
+{
+ return m_customerRouters;
+}
+
+void
+RocketfuelMapReader::SaveTopology (const std::string &file)
+{
+ ofstream os (file.c_str (), ios::trunc);
+ os << "# any empty lines and lines starting with '#' symbol is ignored\n"
+ << "\n"
+ << "# The file should contain exactly two sections: router and link, each starting with the corresponding keyword\n"
+ << "\n"
+ << "# router section defines topology nodes and their relative positions (e.g., to use in visualizer)\n"
+ << "router\n"
+ << "\n"
+ << "# each line in this section represents one router and should have the following data\n"
+ << "# node comment yPos xPos\n";
+
+ auto nodeWriter = [&os](NodeContainer& m) {
+ for_each (m.Begin (), m.End (), [&os](Ptr<Node> node)
+ {
+ std::string name = Names::FindName (node);
+
+ os << name << "\t" << "NA" << "\t" << 0 << "\t" << 0 << "\n";
+ });
+ };
+
+ nodeWriter (m_backboneRouters);
+ nodeWriter (m_gatewayRouters);
+ nodeWriter (m_customerRouters);
+
+ os << "# link section defines point-to-point links between nodes and characteristics of these links\n"
+ << "\n"
+ << "link\n"
+ << "\n"
+ << "# Each line should be in the following format (only first two are required, the rest can be omitted)\n"
+ << "# srcNode dstNode bandwidth metric delay queue\n"
+ << "# bandwidth: link bandwidth\n"
+ << "# metric: routing metric\n"
+ << "# delay: link delay\n"
+ << "# queue: MaxPackets for transmission queue on the link (both directions)\n";
+
+ for_each (m_linksList.begin (), m_linksList.end (), [&](const Link &link) {
+ string src = Names::FindName (link.GetFromNode ());
+ string dst = Names::FindName (link.GetToNode ());
+ os << src << "\t";
+ os << dst << "\t";
+
+ string tmp;
+ if (link.GetAttributeFailSafe ("DataRate", tmp))
+ os << link.GetAttribute("DataRate") << "\t";
+ else
+ NS_FATAL_ERROR ("DataRate must be specified for the link");
+
+ if (link.GetAttributeFailSafe ("OSPF", tmp))
+ os << link.GetAttribute("OSPF") << "\t";
+ else
+ {
+ DataRate rate = boost::lexical_cast<DataRate> (link.GetAttribute("DataRate"));
+
+ int32_t cost = std::max (1, static_cast<int32_t> (1.0 * m_referenceOspfRate.GetBitRate () / rate.GetBitRate ()));
+
+ os << cost << "\t";
+ }
+
+ if (link.GetAttributeFailSafe ("Delay", tmp))
+ {
+ os << link.GetAttribute("Delay") << "\t";
+
+ if (link.GetAttributeFailSafe ("MaxPackets", tmp))
+ {
+ os << link.GetAttribute("MaxPackets") << "\t";
+ }
+ }
+ os << "\n";
+ });
+}
+
+
+template <class Names, class Colors>
+class name_color_writer {
+public:
+ name_color_writer(Names _names, Colors _colors) : names(_names), colors(_colors) {}
+
+ template <class VertexOrEdge>
+ void operator()(std::ostream& out, const VertexOrEdge& v) const {
+ // out << "[label=\"" << names[v] << "\",style=filled,fillcolor=\"" << colors[v] << "\"]";
+ out << "[shape=\"circle\",width=0.1,label=\"\",style=filled,fillcolor=\"" << colors[v] << "\"]";
+ }
+private:
+ Names names;
+ Colors colors;
+};
+
+template <class Names, class Colors>
+inline name_color_writer<Names, Colors>
+make_name_color_writer(Names n, Colors c) {
+ return name_color_writer<Names, Colors>(n, c);
+}
+
+
+void
+RocketfuelMapReader::SaveGraphviz (const std::string &file)
+{
+ ofstream of (file.c_str ());
+ property_map<Graph, vertex_name_t>::type names = get (vertex_name, m_graph);
+ property_map<Graph, vertex_color_t>::type colors = get (vertex_color, m_graph);
+ write_graphviz(of, m_graph, make_name_color_writer (names, colors));
+}
+
+
+void
+RocketfuelMapReader::KeepOnlyBiggestConnectedComponent ()
+{
+ std::map<graph_traits<Graph>::vertex_descriptor, int> temp;
+ associative_property_map< std::map<graph_traits<Graph>::vertex_descriptor, int> > components (temp);
+
+ // //check if topology has breaks in its structure and trim it if yes
+ // property_map<Graph, vertex_index1_t>::type components = get (vertex_index1, m_graph);
+
+ int num = connected_components (m_graph, components);
+ NS_LOG_DEBUG ("Topology has " << num << " components");
+
+ vector<int> sizes (num, 0);
+
+ graph_traits<Graph>::vertex_iterator v, endv;
+ for (tie(v, endv) = vertices(m_graph); v != endv; v++)
+ {
+ sizes[ get (components, *v) ] ++;
+ }
+ int largestComponent = max_element (sizes.begin (), sizes.end ()) - sizes.begin ();
+ // cout << "Largest: " << largestComponent << endl;
+
+ // for (int i =0 ; i < num; i++) cout << sizes[i] << " ";
+ // cout << endl;
+
+ ////////////////////////////////////////////////////
+ // remove nodes and edges from smaller components //
+ ////////////////////////////////////////////////////
+ for (tie(v, endv) = vertices(m_graph); v != endv; v++)
+ {
+ if (get (components, *v) == largestComponent)
+ continue;
+
+ clear_vertex (*v, m_graph);
+ }
+
+ // this works only if vertices are organized in listS or setS (iterator is not invalidated on remove)
+ for (tie(v, endv) = vertices(m_graph); v != endv; )
+ {
+ if (get (components, *v) == largestComponent)
+ {
+ v++;
+ continue;
+ }
+
+ graph_traits<Graph>::vertex_iterator tmp = v;
+ tmp++;
+
+ remove_vertex (*v, m_graph);
+ v = tmp;
+ }
+
+ int index = 0;
+ // renumber nodes
+ for (tie(v, endv) = vertices(m_graph); v != endv; v++)
+ {
+ put (vertex_index, m_graph, *v, index++);
+ }
+}
+
+void
+RocketfuelMapReader::ConnectBackboneRouters ()
+{
+ // not the tricky part. we want backbone to be a fully connected component,
+ // so traffic doesn't bounce from backbone to gateway and back
+
+ typedef adjacency_list< setS, setS, boost::undirectedS,
+ property<vertex_name_t, Traits::vertex_descriptor, property
+ < vertex_index_t, int, property
+ < vertex_index1_t, int > > > > BbGraph;
+ BbGraph bbGraph;
+ map<Traits::vertex_descriptor, graph_traits<BbGraph>::vertex_descriptor> nodeMap;
+
+ int index = 0;
+
+ graph_traits<Graph>::vertex_iterator v, endv;
+ for (tie(v, endv) = vertices(m_graph); v != endv; v++)
+ {
+ node_type_t type = get (vertex_rank, m_graph, *v);
+ if (type == BACKBONE)
+ {
+ graph_traits<BbGraph>::vertex_descriptor newv = add_vertex (*v, bbGraph);
+ put (vertex_index, bbGraph, newv, index++);
+ nodeMap[*v] = newv;
+ }
+ }
+
+ graph_traits<BbGraph>::vertex_iterator bb, endBb;
+ for (tie (bb, endBb) = vertices (bbGraph); bb != endBb; bb++)
+ {
+ Traits::vertex_descriptor actualVertex = get (vertex_name, bbGraph, *bb);
+
+ graph_traits<Graph>::adjacency_iterator u, endu;
+ for (tie (u, endu) = adjacent_vertices (actualVertex, m_graph); u != endu; u++)
+ {
+ if (nodeMap.find (*u) != nodeMap.end ())
+ {
+ add_edge (nodeMap [actualVertex], nodeMap[*u], bbGraph);
+ }
+ }
+ }
+
+ property_map<BbGraph, vertex_index1_t>::type components = get (vertex_index1, bbGraph);
+
+ int num = connected_components (bbGraph, components);
+ NS_LOG_DEBUG ("Backbone has " << num << " components");
+ if (num == 1)
+ return; // nothing to do
+
+ vector< vector<graph_traits<BbGraph>::vertex_descriptor> > subgraphs (num);
+ for (tie (bb, endBb) = vertices (bbGraph); bb != endBb; bb++)
+ {
+ int component = get (vertex_index1, bbGraph, *bb);
+ subgraphs [component].push_back (*bb);
+ }
+
+ UniformVariable randVar;
+
+ for (int i = 1; i < num; i++)
+ {
+ int node1 = randVar.GetInteger (0, subgraphs[i-1].size ()-1);
+ int node2 = randVar.GetInteger (0, subgraphs[i].size ()-1);
+
+ Traits::vertex_descriptor
+ v1 = get (vertex_name, bbGraph, subgraphs[i-1][node1]),
+ v2 = get (vertex_name, bbGraph, subgraphs[i ][node2]);
+
+ NS_LOG_DEBUG ("Connecting " << get (vertex_name, m_graph, v1) << "[" << node1 << "] with "
+ << get (vertex_name, m_graph, v2) << "[" << node2 << "]");
+
+ add_edge (v1, v2, m_graph);
+ }
+}
+
+
+} /* namespace ns3 */
diff --git a/plugins/topology/rocketfuel-map-reader.h b/plugins/topology/rocketfuel-map-reader.h
new file mode 100644
index 0000000..34677d2
--- /dev/null
+++ b/plugins/topology/rocketfuel-map-reader.h
@@ -0,0 +1,184 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013 University of California, Los Angeles
+ *
+ * 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: Ilya Moiseenko <iliamo@cs.ucla.edu>
+ * Hajime Tazaki (tazaki@sfc.wide.ad.jp)
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef ROCKETFUEL_MAP_READER_H
+#define ROCKETFUEL_MAP_READER_H
+
+#include "ns3/annotated-topology-reader.h"
+#include "ns3/net-device-container.h"
+#include "ns3/random-variable.h"
+#include <set>
+#include "ns3/data-rate.h"
+
+#include <boost/graph/adjacency_list.hpp>
+
+using namespace std;
+
+namespace ns3 {
+
+struct RocketfuelParams
+{
+ double averageRtt;
+ int clientNodeDegrees;
+
+ //parameters for links Backbone <->Backbone
+ string minb2bBandwidth;
+ string minb2bDelay;
+
+ string maxb2bBandwidth;
+ string maxb2bDelay;
+
+ //parameters for links Backbone<->Gateway and Gateway <-> Gateway
+ string minb2gBandwidth;
+ string minb2gDelay;
+
+ string maxb2gBandwidth;
+ string maxb2gDelay;
+
+ //parameters for links Gateway <-> Customer
+ string ming2cBandwidth;
+ string ming2cDelay;
+
+ string maxg2cBandwidth;
+ string maxg2cDelay;
+};
+
+/**
+ * \brief Topology file reader and topology estimator (extension of Rocketfuel-format type).
+ *
+ * http://www.cs.washington.edu/research/networking/rocketfuel/
+ *
+ * Only map file (.cch) is supported
+ *
+ * In addition to reading specified topology from the .cch file, this class divides nodes into three categories:
+ * - client nodes (nodes with degrees less or equal to RocketfuelParams.clientNodeDegrees
+ * - gateway nodes (nodes that directly connected to client nodes)
+ * - backbone nodes (all the rest)
+ *
+ * As some of the .cch files do not give a connected network graph, this reader also allows to keep only the largest connected
+ * network graph component.
+ */
+class RocketfuelMapReader : public AnnotatedTopologyReader
+{
+public:
+ RocketfuelMapReader (const std::string &path="", double scale=1.0, const string &referenceOspfRate="100Mbps");
+ virtual ~RocketfuelMapReader ();
+
+ /**
+ * @brief Deprecated call. Read (RocketfuelParams params, bool keepOneComponent=true, bool connectBackbones=true) should be used instead
+ */
+ virtual
+ NodeContainer
+ Read ();
+
+ /**
+ * \brief Main topology reading function.
+ *
+ * @param params parameters specifying range from which link bandwidths and delays should be assigned
+ * @param keepOneComponent if true, then only the largest connected component will be kept
+ * @param connectBackbones if true, then extra links will be added to ensure connectivity of estimated backbone
+ *
+ * This method opens an input stream and reads the Rocketfuel-format file.
+ * Every row represents a topology link (the ids of a couple of nodes),
+ * so the input file is read line by line to figure out how many links
+ * and nodes are in the topology.
+ *
+ * \return the container of the nodes created (or empty container if there was an error)
+ */
+ virtual NodeContainer
+ Read (RocketfuelParams params, bool keepOneComponent=true, bool connectBackbones=true);
+
+ const NodeContainer&
+ GetBackboneRouters() const;
+
+ const NodeContainer&
+ GetGatewayRouters() const;
+
+ const NodeContainer&
+ GetCustomerRouters() const;
+
+ void
+ SaveTopology (const std::string &file);
+
+ void
+ SaveGraphviz (const std::string &file);
+
+private:
+ RocketfuelMapReader (const RocketfuelMapReader&);
+ RocketfuelMapReader& operator= (const RocketfuelMapReader&);
+
+ // NodeContainer
+ void
+ GenerateFromMapsFile (int argc, char *argv[]);
+
+ void
+ CreateLink (string nodeName1, string nodeName2,
+ double averageRtt,
+ const string &minBw, const string &maxBw,
+ const string &minDelay, const string &maxDelay);
+ void
+ KeepOnlyBiggestConnectedComponent ();
+
+ void AssignClients(uint32_t clientDegree, uint32_t gwDegree);
+
+ void
+ ConnectBackboneRouters ();
+
+private:
+ UniformVariable m_randVar;
+
+ NodeContainer m_backboneRouters;
+ NodeContainer m_gatewayRouters;
+ NodeContainer m_customerRouters;
+
+ typedef boost::adjacency_list_traits<boost::setS, boost::setS, boost::undirectedS> Traits;
+
+ enum node_type_t {UNKNOWN = 0, CLIENT = 1, GATEWAY = 2, BACKBONE = 3};
+
+ typedef boost::property< boost::vertex_name_t, std::string, boost::property
+ < boost::vertex_index_t, uint32_t, boost::property
+ < boost::vertex_rank_t, node_type_t, boost::property
+ < boost::vertex_color_t, std::string > > > > nodeProperty;
+
+ typedef boost::no_property edgeProperty;
+
+ typedef boost::adjacency_list< boost::setS, boost::setS, boost::undirectedS,
+ nodeProperty, edgeProperty > Graph;
+
+ typedef map<string, Traits::vertex_descriptor> node_map_t;
+ node_map_t m_graphNodes;
+
+ Graph m_graph;
+ uint32_t m_maxNodeId;
+
+ const DataRate m_referenceOspfRate; // reference rate of OSPF metric calculation
+
+
+private:
+ void
+ assignGw (Traits::vertex_descriptor vertex, uint32_t degree, node_type_t nodeType);
+}; // end class RocketfuelMapReader
+
+}; // end namespace ns3
+
+
+#endif /* ROCKETFUEL_MAP_READER_H */
diff --git a/tools/rocketfuel-maps-cch-to-annotaded.cc b/tools/rocketfuel-maps-cch-to-annotaded.cc
new file mode 100644
index 0000000..d9fa17e
--- /dev/null
+++ b/tools/rocketfuel-maps-cch-to-annotaded.cc
@@ -0,0 +1,161 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ * Ilya Moiseenko <iliamo@ucla.edu>
+ */
+
+#include "ns3/core-module.h"
+#include "ns3/log.h"
+#include "ns3/ndnSIM-module.h"
+#include "ns3/point-to-point-module.h"
+#include "ns3/random-variable.h"
+
+#include <boost/foreach.hpp>
+
+#include "ns3/ndnSIM/plugins/topology/rocketfuel-map-reader.h"
+
+using namespace ns3;
+using namespace std;
+
+int main (int argc, char**argv)
+{
+ string topology = "";
+ string output_prefix = "";
+ uint32_t run = 0;
+ int clientNodeDegrees = -1;
+ bool buildGraphvizGraph = false;
+ bool keepLargestComponent = false;
+ bool connectBackbones = false;
+
+ CommandLine cmd;
+ cmd.AddValue ("topology", "Topology filename (.ccn)", topology);
+ cmd.AddValue ("output", "Prefix for output files", output_prefix);
+ cmd.AddValue ("run", "Run for ranged parameter randomization", run);
+ cmd.AddValue ("clients", "Maximum degree of client nodes", clientNodeDegrees);
+ cmd.AddValue ("buildGraph", "Whether or not build a graphviz graph (using neato)", buildGraphvizGraph);
+ cmd.AddValue ("keepLargestComponent", "Keep only largest connected component of the network graph", keepLargestComponent);
+ cmd.AddValue ("connectBackbones", "Make sure that ``backbone'' nodes are connected (adding extra links)", connectBackbones);
+ cmd.Parse (argc, argv);
+
+ /**
+ * @todo Make range parameters as command line arguments
+ */
+
+ if (topology == "")
+ {
+ cerr << "ERROR: topology needs to be specified" << endl;
+ cerr << endl;
+
+ cerr << cmd;
+ return 1;
+ }
+
+ if (output_prefix == "")
+ {
+ cerr << "ERROR: output needs to be specified" << endl;
+ cerr << endl;
+
+ cerr << cmd;
+ return 1;
+ }
+
+ if (run == 0)
+ {
+ cerr << "ERROR: run needs to be specified" << endl;
+ cerr << endl;
+
+ cerr << cmd;
+ return 1;
+ }
+
+ if (clientNodeDegrees < 0)
+ {
+ cerr << "ERROR: clients needs to be specified" << endl;
+ cerr << endl;
+
+ cerr << cmd;
+ return 1;
+ }
+
+ Config::SetGlobal ("RngRun", IntegerValue (run));
+ GlobalValue::Bind ("SimulatorImplementationType", StringValue ("ns3::VisualSimulatorImpl"));
+
+ string input = topology;
+ string output = output_prefix+"-conv-annotated.txt";
+ string graph = output_prefix+"-conv-annotated.dot";
+ string graph_pdf = output_prefix+"-conv-annotated.pdf";
+
+ RocketfuelParams params;
+ params.clientNodeDegrees = clientNodeDegrees;
+ params.averageRtt = 0.25; // 250ms
+ //parameters for links Backbone<->Backbone
+ params.minb2bBandwidth = "40Mbps";
+ params.minb2bDelay = "5ms";
+
+ params.maxb2bBandwidth = "100Mbps";
+ params.maxb2bDelay = "10ms";
+
+ //parameters for links Backbone<->Gateway and Gateway <-> Gateway
+ params.minb2gBandwidth = "10Mbps";
+ params.minb2gDelay = "5ms";
+
+ params.maxb2gBandwidth = "20Mbps";
+ params.maxb2gDelay = "10ms";
+
+ //parameters for links Gateway <-> Customer
+ params.ming2cBandwidth ="1Mbps";
+ params.ming2cDelay = "70ms";
+
+ params.maxg2cBandwidth ="3Mbps";
+ params.maxg2cDelay = "10ms";
+
+ RocketfuelMapReader topologyReader ("/", 1.0);
+ topologyReader.SetFileName (input);
+ NodeContainer nodes = topologyReader.Read (params, keepLargestComponent, connectBackbones);
+ NodeContainer backboneRouters = topologyReader.GetBackboneRouters();
+ NodeContainer gatewayRouters = topologyReader.GetGatewayRouters();
+ NodeContainer customerRouters = topologyReader.GetCustomerRouters();
+ list<TopologyReader::Link> links = topologyReader.GetLinks();
+
+ topologyReader.SaveGraphviz (graph);
+ if (buildGraphvizGraph)
+ {
+ system (("neato -Tpdf \"" + graph + "\" > \"" + graph_pdf + "\"").c_str ());
+ }
+
+ topologyReader.SaveTopology (output);
+
+ // Names::Clear ();
+ // Simulator::Destroy ();
+
+ // // assign weights
+ // AnnotatedTopologyReader topologyReader2 ("", 1.0);
+ // topologyReader2.SetFileName (output);
+ // topologyReader2.Read ();
+
+ // char env[] = "NS_VIS_ASSIGN=1";
+ // putenv (env);
+
+ // Simulator::Stop (Seconds (0.0));
+ // Simulator::Run ();
+
+ // topologyReader2.SaveTopology (output);
+
+ // Simulator::Destroy ();
+ return 0;
+}
diff --git a/tools/wscript b/tools/wscript
new file mode 100644
index 0000000..6ebf98e
--- /dev/null
+++ b/tools/wscript
@@ -0,0 +1,6 @@
+# -*- Mode: python; py-indent-offset: 4; indent-tabs-mode: nil; coding: utf-8; -*-
+
+def build(bld):
+ if 'topology' in bld.env['NDN_plugins']:
+ obj = bld.create_ns3_program('rocketfuel-maps-cch-to-annotaded', ['ndnSIM'])
+ obj.source = 'rocketfuel-maps-cch-to-annotaded.cc'
diff --git a/wscript b/wscript
index a48ff80..2460084 100644
--- a/wscript
+++ b/wscript
@@ -52,7 +52,7 @@
if Options.options.disable_ndn_plugins:
conf.env['NDN_plugins'] = conf.env['NDN_plugins'] - Options.options.disable_ndn_plugins.split(',')
-
+
conf.env['ENABLE_NDNSIM']=True;
conf.env['MODULES_BUILT'].append('ndnSIM')
@@ -82,7 +82,7 @@
if not bld.env['ENABLE_NDNSIM']:
bld.env['MODULES_NOT_BUILT'].append('ndnSIM')
return
-
+
module.source = bld.path.ant_glob(['model/**/*.cc',
'apps/*.cc',
'utils/**/*.cc',
@@ -116,12 +116,12 @@
"model/fib/ndn-fib.h",
"model/fib/ndn-fib-entry.h",
-
+
"model/pit/ndn-pit.h",
"model/pit/ndn-pit-entry.h",
"model/pit/ndn-pit-entry-incoming-face.h",
"model/pit/ndn-pit-entry-outgoing-face.h",
-
+
"model/fw/ndn-forwarding-strategy.h",
"model/fw/ndn-fw-tag.h",
@@ -137,6 +137,7 @@
"plugins/topology/annotated-topology-reader.h",
])
module.source.extend (bld.path.ant_glob(['plugins/topology/*.cc']))
+ module.full_headers.extend ([p.path_from(bld.path) for p in bld.path.ant_glob(['plugins/topology/**/*.h'])])
if 'mobility' in bld.env['NDN_plugins']:
headers.source.extend ([
@@ -144,16 +145,19 @@
"plugins/mobility/spring-mobility-helper.h",
])
module.source.extend (bld.path.ant_glob(['plugins/mobility/*.cc']))
+ module.full_headers.extend ([p.path_from(bld.path) for p in bld.path.ant_glob(['plugins/mobility/**/*.h'])])
# bld.install_files('${INCLUDEDIR}/%s%s/ns3/ndnSIM' % (wutils.APPNAME, wutils.VERSION), ndnSIM_headers, relative_trick=True)
# bld.install_files('$PREFIX/include', ndnSIM_headers)
-
+
tests = bld.create_ns3_module_test_library('ndnSIM')
tests.source = bld.path.ant_glob('test/*.cc')
if bld.env.ENABLE_EXAMPLES:
bld.add_subdirs('examples')
+ bld.add_subdirs('tools')
+
bld.ns3_python_bindings()
@@ -177,7 +181,7 @@
task = self.create_task('ns3header')
task.mode = getattr(self, 'mode', 'install')
if task.mode == 'install':
- self.bld.install_files('${INCLUDEDIR}/%s%s/ns3/%s' % (wutils.APPNAME, wutils.VERSION, relpath),
+ self.bld.install_files('${INCLUDEDIR}/%s%s/ns3/%s' % (wutils.APPNAME, wutils.VERSION, relpath),
[src_node])
task.set_inputs([src_node])
task.set_outputs([dst_node])