blob: 969dd6eb3d45ca85de22d72720f532025d737f08 [file] [log] [blame]
Alexander Afanasyev957a84a2013-01-23 10:21:06 -08001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Alexander Afanasyev60a7b622014-12-20 17:04:07 -08002/**
3 * Copyright (c) 2011-2015 Regents of the University of California.
Alexander Afanasyev957a84a2013-01-23 10:21:06 -08004 *
Alexander Afanasyev60a7b622014-12-20 17:04:07 -08005 * This file is part of ndnSIM. See AUTHORS for complete list of ndnSIM authors and
6 * contributors.
Alexander Afanasyev957a84a2013-01-23 10:21:06 -08007 *
Alexander Afanasyev60a7b622014-12-20 17:04:07 -08008 * ndnSIM is free software: you can redistribute it and/or modify it under the terms
9 * of the GNU General Public License as published by the Free Software Foundation,
10 * either version 3 of the License, or (at your option) any later version.
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080011 *
Alexander Afanasyev60a7b622014-12-20 17:04:07 -080012 * ndnSIM is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
13 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14 * PURPOSE. See the GNU General Public License for more details.
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080015 *
Alexander Afanasyev60a7b622014-12-20 17:04:07 -080016 * You should have received a copy of the GNU General Public License along with
17 * ndnSIM, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
18 **/
19
20// Based on the code by Hajime Tazaki <tazaki@sfc.wide.ad.jp>
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080021
Alexander Afanasyev0c395372014-12-20 15:54:02 -080022#include "rocketfuel-map-reader.hpp"
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080023
24#include "ns3/nstime.h"
25#include "ns3/log.h"
26#include "ns3/fatal-error.h"
27#include "ns3/assert.h"
28#include "ns3/names.h"
29#include "ns3/net-device-container.h"
30#include "ns3/point-to-point-helper.h"
31#include "ns3/point-to-point-net-device.h"
32#include "ns3/internet-stack-helper.h"
33#include "ns3/ipv4-address-helper.h"
34#include "ns3/ipv4-global-routing-helper.h"
35#include "ns3/drop-tail-queue.h"
36#include "ns3/ipv4-interface.h"
37#include "ns3/ipv4.h"
38#include "ns3/string.h"
39#include "ns3/pointer.h"
40#include "ns3/uinteger.h"
41#include "ns3/ipv4-address.h"
42#include "ns3/node-list.h"
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080043
44#include "ns3/mobility-model.h"
45
46#include <regex.h>
47
48#include <boost/foreach.hpp>
49#include <boost/lexical_cast.hpp>
50
51#include <boost/graph/graphviz.hpp>
52#include <boost/graph/connected_components.hpp>
53
54#include <iomanip>
55
56using namespace std;
57using namespace boost;
58
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080059NS_LOG_COMPONENT_DEFINE("RocketfuelMapReader");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080060
61namespace ns3 {
62
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080063RocketfuelMapReader::RocketfuelMapReader(const std::string& path /*=""*/, double scale /*=1.0*/,
64 const std::string& referenceOspfRate)
65 : AnnotatedTopologyReader(path, scale)
Alexander Afanasyevd6453cd2015-08-20 21:45:36 -070066 , m_randVar(CreateObject<UniformRandomVariable>())
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080067 , m_referenceOspfRate(boost::lexical_cast<DataRate>(referenceOspfRate))
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080068{
69}
70
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080071RocketfuelMapReader::~RocketfuelMapReader()
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080072{
73}
74
75NodeContainer
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080076RocketfuelMapReader::Read()
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080077{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080078 NS_FATAL_ERROR("Deprecated call. Use the other overloaded method instead");
79 return NodeContainer();
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080080}
81
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080082/* uid @loc [+] [bb] (num_neigh) [&ext] -> <nuid-1> <nuid-2> ... {-euid} ... =name[!] rn */
83
84#define REGMATCH_MAX 16
85
86#define START "^"
87#define END "$"
88#define SPACE "[ \t]+"
89#define MAYSPACE "[ \t]*"
90
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080091#define ROCKETFUEL_MAPS_LINE \
92 START "(-*[0-9]+)" SPACE "(@[?A-Za-z0-9,+]+)" SPACE "(\\+)*" MAYSPACE "(bb)*" MAYSPACE \
93 "\\(([0-9]+)\\)" SPACE "(&[0-9]+)*" MAYSPACE "->" MAYSPACE "(<[0-9 \t<>]+>)*" MAYSPACE \
94 "(\\{-[0-9\\{\\} \t-]+\\})*" SPACE "=([A-Za-z0-9.!-]+)" SPACE "r([0-9])" MAYSPACE END
Alexander Afanasyev957a84a2013-01-23 10:21:06 -080095
96void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080097RocketfuelMapReader::CreateLink(string nodeName1, string nodeName2, double averageRtt,
98 const string& minBw, const string& maxBw, const string& minDelay,
99 const string& maxDelay)
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800100{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800101 Ptr<Node> node1 = Names::Find<Node>(m_path, nodeName1);
102 Ptr<Node> node2 = Names::Find<Node>(m_path, nodeName2);
103 Link link(node1, nodeName1, node2, nodeName2);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800104
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800105 DataRate randBandwidth(
Alexander Afanasyevd6453cd2015-08-20 21:45:36 -0700106 m_randVar->GetInteger(static_cast<uint32_t>(lexical_cast<DataRate>(minBw).GetBitRate()),
107 static_cast<uint32_t>(lexical_cast<DataRate>(maxBw).GetBitRate())));
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800108
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800109 int32_t metric = std::max(1, static_cast<int32_t>(1.0 * m_referenceOspfRate.GetBitRate()
110 / randBandwidth.GetBitRate()));
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800111
112 Time randDelay =
Alexander Afanasyevd6453cd2015-08-20 21:45:36 -0700113 Time::FromDouble((m_randVar->GetValue(lexical_cast<Time>(minDelay).ToDouble(Time::US),
114 lexical_cast<Time>(maxDelay).ToDouble(Time::US))),
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800115 Time::US);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800116
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800117 uint32_t queue = ceil(averageRtt * (randBandwidth.GetBitRate() / 8.0 / 1100.0));
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800118
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800119 link.SetAttribute("DataRate", boost::lexical_cast<string>(randBandwidth));
120 link.SetAttribute("OSPF", boost::lexical_cast<string>(metric));
121 link.SetAttribute("Delay",
122 boost::lexical_cast<string>(ceil(randDelay.ToDouble(Time::US))) + "us");
123 link.SetAttribute("MaxPackets", boost::lexical_cast<string>(queue));
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800124
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800125 AddLink(link);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800126}
127
128// NodeContainer
129void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800130RocketfuelMapReader::GenerateFromMapsFile(int argc, char* argv[])
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800131{
132 string uid;
133 string loc;
134 string ptr;
135 string name;
136 string nuid;
Alexander Afanasyev29c10ed2013-01-23 18:26:07 -0800137 // bool dns = false;
138 // bool bb = false;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800139 int num_neigh_s = 0;
140 unsigned int num_neigh = 0;
141 int radius = 0;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800142 vector<string> neigh_list;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800143
144 uid = argv[0];
145 loc = argv[1];
146
Alexander Afanasyev29c10ed2013-01-23 18:26:07 -0800147 // if (argv[2])
148 // {
149 // dns = true;
150 // }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800151
Alexander Afanasyev29c10ed2013-01-23 18:26:07 -0800152 // if (argv[3])
153 // {
154 // bb = true;
155 // }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800156
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800157 num_neigh_s = ::atoi(argv[4]);
158 if (num_neigh_s < 0) {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800159 num_neigh = 0;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800160 NS_LOG_WARN("Negative number of neighbors given");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800161 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800162 else {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800163 num_neigh = num_neigh_s;
164 }
165
166 /* neighbors */
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800167 if (argv[6]) {
168 char* nbr;
169 char* stringp = argv[6];
170 while ((nbr = strsep(&stringp, " \t")) != NULL) {
171 nbr[strlen(nbr) - 1] = '\0';
172 neigh_list.push_back(nbr + 1);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800173 }
174 }
175
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800176 if (num_neigh != neigh_list.size()) {
177 NS_LOG_WARN("Given number of neighbors = " << num_neigh << " != size of neighbors list = "
178 << neigh_list.size());
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800179 }
180
181 /* externs */
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800182 if (argv[7]) {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800183 // euid = argv[7];
184 }
185
186 /* name */
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800187 if (argv[8]) {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800188 name = argv[8];
189 }
190
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800191 radius = ::atoi(&argv[9][1]);
192 if (radius > 0) {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800193 return;
194 }
195
196 // Create node and link
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800197 if (uid.empty())
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800198 return;
199
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800200 node_map_t::iterator node = m_graphNodes.find(uid);
201 if (node == m_graphNodes.end()) {
202 bool ok;
203 tie(node, ok) = m_graphNodes.insert(make_pair(uid, add_vertex(nodeProperty(uid), m_graph)));
204 NS_ASSERT(ok == true);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800205
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800206 put(vertex_index, m_graph, node->second, m_maxNodeId);
207 m_maxNodeId++;
208 }
209
210 for (uint32_t i = 0; i < neigh_list.size(); ++i) {
211 nuid = neigh_list[i];
212
213 if (nuid.empty()) {
214 continue;
215 }
216
217 node_map_t::iterator otherNode = m_graphNodes.find(nuid);
218 if (otherNode == m_graphNodes.end()) {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800219 bool ok;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800220 tie(otherNode, ok) =
221 m_graphNodes.insert(make_pair(nuid, add_vertex(nodeProperty(nuid), m_graph)));
222 NS_ASSERT(ok == true);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800223
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800224 put(vertex_index, m_graph, otherNode->second, m_maxNodeId);
225 m_maxNodeId++;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800226 }
227
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800228 // cout << node->second << " <-> " << otherNode->second << endl;
229 // parallel edges are disabled in the graph, so no need to worry
230 add_edge(node->second, otherNode->second, m_graph);
231 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800232}
233
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800234void
235RocketfuelMapReader::assignGw(Traits::vertex_descriptor vertex, uint32_t degree,
236 node_type_t nodeType)
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800237{
238 graph_traits<Graph>::adjacency_iterator u, endu;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800239 for (tie(u, endu) = adjacent_vertices(vertex, m_graph); u != endu; u++) {
240 if (get(vertex_rank, m_graph, *u) != UNKNOWN)
241 continue;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800242
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800243 put(vertex_rank, m_graph, *u, nodeType);
244 put(vertex_color, m_graph, *u, "green");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800245
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800246 uint32_t u_degree = out_degree(*u, m_graph);
247 if (u_degree < degree)
248 assignGw(*u, degree, BACKBONE);
249 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800250};
251
252void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800253RocketfuelMapReader::AssignClients(uint32_t clientDegree, uint32_t gwDegree)
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800254{
255 graph_traits<Graph>::vertex_iterator v, endv;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800256 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
257 uint32_t degree = out_degree(*v, m_graph);
258 if (degree == clientDegree) {
259 put(vertex_rank, m_graph, *v, CLIENT);
260 put(vertex_color, m_graph, *v, "red");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800261
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800262 assignGw(*v, gwDegree + 1, GATEWAY);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800263 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800264 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800265};
266
267NodeContainer
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800268RocketfuelMapReader::Read(RocketfuelParams params, bool keepOneComponent /*=true*/,
269 bool connectBackbones /*=true*/)
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800270{
271 m_maxNodeId = 0;
272
273 ifstream topgen;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800274 topgen.open(GetFileName().c_str());
275 // NodeContainer nodes;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800276
277 istringstream lineBuffer;
278 string line;
279 int lineNumber = 0;
280 char errbuf[512];
281
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800282 if (!topgen.is_open()) {
283 NS_LOG_WARN("Couldn't open the file " << GetFileName());
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800284 return m_nodes;
285 }
286
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800287 while (!topgen.eof()) {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800288 int ret;
289 int argc;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800290 char* argv[REGMATCH_MAX];
291 char* buf;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800292
293 lineNumber++;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800294 line.clear();
295 lineBuffer.clear();
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800296
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800297 getline(topgen, line);
298 buf = (char*)line.c_str();
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800299
300 regmatch_t regmatch[REGMATCH_MAX];
301 regex_t regex;
302
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800303 ret = regcomp(&regex, ROCKETFUEL_MAPS_LINE, REG_EXTENDED | REG_NEWLINE);
304 if (ret != 0) {
305 regerror(ret, &regex, errbuf, sizeof(errbuf));
306 regfree(&regex);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800307 continue;
308 }
309
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800310 ret = regexec(&regex, buf, REGMATCH_MAX, regmatch, 0);
311 if (ret == REG_NOMATCH) {
312 NS_LOG_WARN("match failed (maps file): %s" << buf);
313 regfree(&regex);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800314 continue;
315 }
316
317 line = buf;
318 argc = 0;
319
320 /* regmatch[0] is the entire strings that matched */
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800321 for (int i = 1; i < REGMATCH_MAX; i++) {
322 if (regmatch[i].rm_so == -1) {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800323 argv[i - 1] = NULL;
324 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800325 else {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800326 line[regmatch[i].rm_eo] = '\0';
327 argv[i - 1] = &line[regmatch[i].rm_so];
328 argc = i;
329 }
330 }
331
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800332 GenerateFromMapsFile(argc, argv);
333 regfree(&regex);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800334 }
335
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800336 if (keepOneComponent) {
337 NS_LOG_DEBUG("Before eliminating disconnected nodes: " << num_vertices(m_graph));
338 KeepOnlyBiggestConnectedComponent();
339 NS_LOG_DEBUG("After eliminating disconnected nodes: " << num_vertices(m_graph));
340 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800341
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800342 for (int clientDegree = 1; clientDegree <= params.clientNodeDegrees; clientDegree++) {
343 AssignClients(clientDegree, std::min(clientDegree, 3));
344 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800345
346 graph_traits<Graph>::vertex_iterator v, endv;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800347 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
348 node_type_t type = get(vertex_rank, m_graph, *v);
349 if (type == UNKNOWN) {
350 put(vertex_rank, m_graph, *v, BACKBONE);
351 put(vertex_color, m_graph, *v, "blue");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800352 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800353 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800354
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800355 if (connectBackbones) {
356 ConnectBackboneRouters();
357 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800358
359 graph_traits<Graph>::edge_iterator e, ende;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800360 for (tie(e, ende) = edges(m_graph); e != ende;) {
361 Traits::vertex_descriptor u = source(*e, m_graph), v = target(*e, m_graph);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800362
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800363 node_type_t u_type = get(vertex_rank, m_graph, u), v_type = get(vertex_rank, m_graph, v);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800364
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800365 if (u_type == BACKBONE && v_type == BACKBONE) {
366 // ok
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800367 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800368 else if ((u_type == GATEWAY && v_type == BACKBONE)
369 || (u_type == BACKBONE && v_type == GATEWAY)) {
370 // ok
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800371 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800372 else if (u_type == GATEWAY && v_type == GATEWAY) {
373 // ok
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800374 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800375 else if ((u_type == GATEWAY && v_type == CLIENT) || (u_type == CLIENT && v_type == GATEWAY)) {
376 // ok
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800377 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800378 else {
379 // not ok
380 NS_LOG_DEBUG("Wrong link type between nodes: " << u_type << " <-> " << v_type
381 << " (deleting the link)");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800382
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800383 graph_traits<Graph>::edge_iterator tmp = e;
384 tmp++;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800385
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800386 remove_edge(*e, m_graph);
387 e = tmp;
388 continue;
389 }
390 e++;
391 }
392
393 if (keepOneComponent) {
394 NS_LOG_DEBUG("Before 2 eliminating disconnected nodes: " << num_vertices(m_graph));
395 KeepOnlyBiggestConnectedComponent();
396 NS_LOG_DEBUG("After 2 eliminating disconnected nodes: " << num_vertices(m_graph));
397 }
398
399 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
400 string nodeName = get(vertex_name, m_graph, *v);
401 Ptr<Node> node = CreateNode(nodeName, 0);
402
403 node_type_t type = get(vertex_rank, m_graph, *v);
404 switch (type) {
405 case BACKBONE:
406 Names::Rename(nodeName, "bb-" + nodeName);
407 put(vertex_name, m_graph, *v, "bb-" + nodeName);
408 m_backboneRouters.Add(node);
409 break;
410 case CLIENT:
411 Names::Rename(nodeName, "leaf-" + nodeName);
412 put(vertex_name, m_graph, *v, "leaf-" + nodeName);
413 m_customerRouters.Add(node);
414 break;
415 case GATEWAY:
416 Names::Rename(nodeName, "gw-" + nodeName);
417 put(vertex_name, m_graph, *v, "gw-" + nodeName);
418 m_gatewayRouters.Add(node);
419 break;
420 case UNKNOWN:
421 NS_FATAL_ERROR("Should not happen");
422 break;
423 }
424 }
425
426 for (tie(e, ende) = edges(m_graph); e != ende; e++) {
427 Traits::vertex_descriptor u = source(*e, m_graph), v = target(*e, m_graph);
428
429 node_type_t u_type = get(vertex_rank, m_graph, u), v_type = get(vertex_rank, m_graph, v);
430
431 string u_name = get(vertex_name, m_graph, u), v_name = get(vertex_name, m_graph, v);
432
433 if (u_type == BACKBONE && v_type == BACKBONE) {
434 CreateLink(u_name, v_name, params.averageRtt, params.minb2bBandwidth, params.maxb2bBandwidth,
435 params.minb2bDelay, params.maxb2bDelay);
436 }
437 else if ((u_type == GATEWAY && v_type == BACKBONE)
438 || (u_type == BACKBONE && v_type == GATEWAY)) {
439 CreateLink(u_name, v_name, params.averageRtt, params.minb2gBandwidth, params.maxb2gBandwidth,
440 params.minb2gDelay, params.maxb2gDelay);
441 }
442 else if (u_type == GATEWAY && v_type == GATEWAY) {
443 CreateLink(u_name, v_name, params.averageRtt, params.minb2gBandwidth, params.maxb2gBandwidth,
444 params.minb2gDelay, params.maxb2gDelay);
445 }
446 else if ((u_type == GATEWAY && v_type == CLIENT) || (u_type == CLIENT && v_type == GATEWAY)) {
447 CreateLink(u_name, v_name, params.averageRtt, params.ming2cBandwidth, params.maxg2cBandwidth,
448 params.ming2cDelay, params.maxg2cDelay);
449 }
450 else {
451 NS_FATAL_ERROR("Wrong link type between nodes: " << u_type << " <-> " << v_type);
452 }
453 }
454
455 ApplySettings();
456
457 NS_LOG_INFO("Clients: " << m_customerRouters.GetN());
458 NS_LOG_INFO("Gateways: " << m_gatewayRouters.GetN());
459 NS_LOG_INFO("Backbones: " << m_backboneRouters.GetN());
460 NS_LOG_INFO("Links: " << GetLinks().size());
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800461
462 return m_nodes;
463}
464
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800465const NodeContainer&
466RocketfuelMapReader::GetBackboneRouters() const
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800467{
468 return m_backboneRouters;
469}
470
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800471const NodeContainer&
472RocketfuelMapReader::GetGatewayRouters() const
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800473{
474 return m_gatewayRouters;
475}
476
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800477const NodeContainer&
478RocketfuelMapReader::GetCustomerRouters() const
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800479{
480 return m_customerRouters;
481}
482
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800483static void
484nodeWriter(std::ostream& os, NodeContainer& m)
Alexander Afanasyev29c10ed2013-01-23 18:26:07 -0800485{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800486 for (NodeContainer::Iterator node = m.Begin(); node != m.End(); node++) {
487 std::string name = Names::FindName(*node);
Alexander Afanasyev29c10ed2013-01-23 18:26:07 -0800488
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800489 os << name << "\t"
490 << "NA"
491 << "\t" << 0 << "\t" << 0 << "\n";
492 }
Alexander Afanasyev29c10ed2013-01-23 18:26:07 -0800493};
494
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800495void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800496RocketfuelMapReader::SaveTopology(const std::string& file)
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800497{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800498 ofstream os(file.c_str(), ios::trunc);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800499 os << "# any empty lines and lines starting with '#' symbol is ignored\n"
500 << "\n"
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800501 << "# The file should contain exactly two sections: router and link, each starting with the "
502 "corresponding keyword\n"
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800503 << "\n"
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800504 << "# router section defines topology nodes and their relative positions (e.g., to use in "
505 "visualizer)\n"
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800506 << "router\n"
507 << "\n"
508 << "# each line in this section represents one router and should have the following data\n"
509 << "# node comment yPos xPos\n";
510
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800511 nodeWriter(os, m_backboneRouters);
512 nodeWriter(os, m_gatewayRouters);
513 nodeWriter(os, m_customerRouters);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800514
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800515 os << "# link section defines point-to-point links between nodes and characteristics of these "
516 "links\n"
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800517 << "\n"
518 << "link\n"
519 << "\n"
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800520 << "# Each line should be in the following format (only first two are required, the rest can "
521 "be omitted)\n"
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800522 << "# srcNode dstNode bandwidth metric delay queue\n"
523 << "# bandwidth: link bandwidth\n"
524 << "# metric: routing metric\n"
525 << "# delay: link delay\n"
526 << "# queue: MaxPackets for transmission queue on the link (both directions)\n";
527
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800528 for (std::list<Link>::iterator link = m_linksList.begin(); link != m_linksList.end(); link++) {
529 string src = Names::FindName(link->GetFromNode());
530 string dst = Names::FindName(link->GetToNode());
531 os << src << "\t";
532 os << dst << "\t";
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800533
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800534 string tmp;
535 if (link->GetAttributeFailSafe("DataRate", tmp))
536 os << link->GetAttribute("DataRate") << "\t";
537 else
538 NS_FATAL_ERROR("DataRate must be specified for the link");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800539
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800540 if (link->GetAttributeFailSafe("OSPF", tmp))
541 os << link->GetAttribute("OSPF") << "\t";
542 else {
543 DataRate rate = boost::lexical_cast<DataRate>(link->GetAttribute("DataRate"));
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800544
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800545 int32_t cost = std::max(1, static_cast<int32_t>(1.0 * m_referenceOspfRate.GetBitRate()
546 / rate.GetBitRate()));
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800547
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800548 os << cost << "\t";
Alexander Afanasyev29c10ed2013-01-23 18:26:07 -0800549 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800550
551 if (link->GetAttributeFailSafe("Delay", tmp)) {
552 os << link->GetAttribute("Delay") << "\t";
553
554 if (link->GetAttributeFailSafe("MaxPackets", tmp)) {
555 os << link->GetAttribute("MaxPackets") << "\t";
556 }
557 }
558 os << "\n";
559 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800560}
561
Spyridon Mastorakis460f57c2014-12-17 00:44:14 -0800562/// @cond include_hidden
563
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800564template<class Names, class Colors>
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800565class name_color_writer {
566public:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800567 name_color_writer(Names _names, Colors _colors)
568 : names(_names)
569 , colors(_colors)
570 {
571 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800572
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800573 template<class VertexOrEdge>
574 void
575 operator()(std::ostream& out, const VertexOrEdge& v) const
576 {
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800577 // out << "[label=\"" << names[v] << "\",style=filled,fillcolor=\"" << colors[v] << "\"]";
578 out << "[shape=\"circle\",width=0.1,label=\"\",style=filled,fillcolor=\"" << colors[v] << "\"]";
579 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800580
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800581private:
582 Names names;
583 Colors colors;
584};
585
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800586template<class Names, class Colors>
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800587inline name_color_writer<Names, Colors>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800588make_name_color_writer(Names n, Colors c)
589{
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800590 return name_color_writer<Names, Colors>(n, c);
591}
592
Spyridon Mastorakis460f57c2014-12-17 00:44:14 -0800593/// @endcond
594
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800595void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800596RocketfuelMapReader::SaveGraphviz(const std::string& file)
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800597{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800598 ofstream of(file.c_str());
599 property_map<Graph, vertex_name_t>::type names = get(vertex_name, m_graph);
600 property_map<Graph, vertex_color_t>::type colors = get(vertex_color, m_graph);
601 write_graphviz(of, m_graph, make_name_color_writer(names, colors));
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800602}
603
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800604void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800605RocketfuelMapReader::KeepOnlyBiggestConnectedComponent()
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800606{
607 std::map<graph_traits<Graph>::vertex_descriptor, int> temp;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800608 associative_property_map<std::map<graph_traits<Graph>::vertex_descriptor, int>> components(temp);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800609
610 // //check if topology has breaks in its structure and trim it if yes
611 // property_map<Graph, vertex_index1_t>::type components = get (vertex_index1, m_graph);
612
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800613 int num = connected_components(m_graph, components);
614 NS_LOG_DEBUG("Topology has " << num << " components");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800615
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800616 vector<int> sizes(num, 0);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800617
618 graph_traits<Graph>::vertex_iterator v, endv;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800619 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
620 sizes[get(components, *v)]++;
621 }
622 int largestComponent = max_element(sizes.begin(), sizes.end()) - sizes.begin();
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800623 // cout << "Largest: " << largestComponent << endl;
624
625 // for (int i =0 ; i < num; i++) cout << sizes[i] << " ";
626 // cout << endl;
627
628 ////////////////////////////////////////////////////
629 // remove nodes and edges from smaller components //
630 ////////////////////////////////////////////////////
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800631 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
632 if (get(components, *v) == largestComponent)
633 continue;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800634
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800635 clear_vertex(*v, m_graph);
636 }
637
638 // this works only if vertices are organized in listS or setS (iterator is not invalidated on
639 // remove)
640 for (tie(v, endv) = vertices(m_graph); v != endv;) {
641 if (get(components, *v) == largestComponent) {
642 v++;
643 continue;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800644 }
645
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800646 graph_traits<Graph>::vertex_iterator tmp = v;
647 tmp++;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800648
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800649 remove_vertex(*v, m_graph);
650 v = tmp;
651 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800652
653 int index = 0;
654 // renumber nodes
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800655 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
656 put(vertex_index, m_graph, *v, index++);
657 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800658}
659
660void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800661RocketfuelMapReader::ConnectBackboneRouters()
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800662{
663 // not the tricky part. we want backbone to be a fully connected component,
664 // so traffic doesn't bounce from backbone to gateway and back
665
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800666 typedef adjacency_list<setS, setS, boost::undirectedS,
667 property<vertex_name_t, Traits::vertex_descriptor,
668 property<vertex_index_t, int, property<vertex_index1_t, int>>>>
669 BbGraph;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800670 BbGraph bbGraph;
671 map<Traits::vertex_descriptor, graph_traits<BbGraph>::vertex_descriptor> nodeMap;
672
673 int index = 0;
674
675 graph_traits<Graph>::vertex_iterator v, endv;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800676 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
677 node_type_t type = get(vertex_rank, m_graph, *v);
678 if (type == BACKBONE) {
679 graph_traits<BbGraph>::vertex_descriptor newv = add_vertex(*v, bbGraph);
680 put(vertex_index, bbGraph, newv, index++);
681 nodeMap[*v] = newv;
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800682 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800683 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800684
685 graph_traits<BbGraph>::vertex_iterator bb, endBb;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800686 for (tie(bb, endBb) = vertices(bbGraph); bb != endBb; bb++) {
687 Traits::vertex_descriptor actualVertex = get(vertex_name, bbGraph, *bb);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800688
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800689 graph_traits<Graph>::adjacency_iterator u, endu;
690 for (tie(u, endu) = adjacent_vertices(actualVertex, m_graph); u != endu; u++) {
691 if (nodeMap.find(*u) != nodeMap.end()) {
692 add_edge(nodeMap[actualVertex], nodeMap[*u], bbGraph);
693 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800694 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800695 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800696
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800697 property_map<BbGraph, vertex_index1_t>::type components = get(vertex_index1, bbGraph);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800698
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800699 int num = connected_components(bbGraph, components);
700 NS_LOG_DEBUG("Backbone has " << num << " components");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800701 if (num == 1)
702 return; // nothing to do
703
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800704 vector<vector<graph_traits<BbGraph>::vertex_descriptor>> subgraphs(num);
705 for (tie(bb, endBb) = vertices(bbGraph); bb != endBb; bb++) {
706 int component = get(vertex_index1, bbGraph, *bb);
707 subgraphs[component].push_back(*bb);
708 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800709
Alexander Afanasyevd6453cd2015-08-20 21:45:36 -0700710 Ptr<UniformRandomVariable> randVar = CreateObject<UniformRandomVariable>();
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800711
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800712 for (int i = 1; i < num; i++) {
Alexander Afanasyevd6453cd2015-08-20 21:45:36 -0700713 int node1 = randVar->GetInteger(0, subgraphs[i - 1].size() - 1);
714 int node2 = randVar->GetInteger(0, subgraphs[i].size() - 1);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800715
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800716 Traits::vertex_descriptor v1 = get(vertex_name, bbGraph, subgraphs[i - 1][node1]),
717 v2 = get(vertex_name, bbGraph, subgraphs[i][node2]);
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800718
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800719 NS_LOG_DEBUG("Connecting " << get(vertex_name, m_graph, v1) << "[" << node1 << "] with "
720 << get(vertex_name, m_graph, v2) << "[" << node2 << "]");
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800721
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800722 add_edge(v1, v2, m_graph);
723 }
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800724}
725
Alexander Afanasyev957a84a2013-01-23 10:21:06 -0800726} /* namespace ns3 */