24 #include "ns3/nstime.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"
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"
44 #include "ns3/mobility-model.h"
48 #include <boost/foreach.hpp>
49 #include <boost/lexical_cast.hpp>
51 #include <boost/graph/graphviz.hpp>
52 #include <boost/graph/connected_components.hpp>
57 using namespace boost;
59 NS_LOG_COMPONENT_DEFINE(
"RocketfuelMapReader");
64 const std::string& referenceOspfRate)
66 , m_randVar(CreateObject<UniformRandomVariable>())
67 , m_referenceOspfRate(
boost::lexical_cast<DataRate>(referenceOspfRate))
78 NS_FATAL_ERROR(
"Deprecated call. Use the other overloaded method instead");
79 return NodeContainer();
84 #define REGMATCH_MAX 16
88 #define SPACE "[ \t]+"
89 #define MAYSPACE "[ \t]*"
91 #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
97 RocketfuelMapReader::CreateLink(
string nodeName1,
string nodeName2,
double averageRtt,
98 const string& minBw,
const string& maxBw,
const string& minDelay,
99 const string& maxDelay)
101 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);
105 DataRate randBandwidth(
106 m_randVar->GetInteger(
static_cast<uint32_t
>(lexical_cast<DataRate>(minBw).GetBitRate()),
107 static_cast<uint32_t
>(lexical_cast<DataRate>(maxBw).GetBitRate())));
109 int32_t metric = std::max(1,
static_cast<int32_t
>(1.0 * m_referenceOspfRate.GetBitRate()
110 / randBandwidth.GetBitRate()));
113 Time::FromDouble((m_randVar->GetValue(lexical_cast<Time>(minDelay).ToDouble(Time::US),
114 lexical_cast<Time>(maxDelay).ToDouble(Time::US))),
117 uint32_t queue = ceil(averageRtt * (randBandwidth.GetBitRate() / 8.0 / 1100.0));
119 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));
130 RocketfuelMapReader::GenerateFromMapsFile(
int argc,
char* argv[])
140 unsigned int num_neigh = 0;
142 vector<string> neigh_list;
157 num_neigh_s = ::atoi(argv[4]);
158 if (num_neigh_s < 0) {
160 NS_LOG_WARN(
"Negative number of neighbors given");
163 num_neigh = num_neigh_s;
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);
176 if (num_neigh != neigh_list.size()) {
177 NS_LOG_WARN(
"Given number of neighbors = " << num_neigh <<
" != size of neighbors list = "
178 << neigh_list.size());
191 radius = ::atoi(&argv[9][1]);
200 node_map_t::iterator node = m_graphNodes.find(uid);
201 if (node == m_graphNodes.end()) {
203 tie(node, ok) = m_graphNodes.insert(make_pair(uid, add_vertex(nodeProperty(uid), m_graph)));
204 NS_ASSERT(ok ==
true);
206 put(vertex_index, m_graph, node->second, m_maxNodeId);
210 for (uint32_t i = 0; i < neigh_list.size(); ++i) {
211 nuid = neigh_list[i];
217 node_map_t::iterator otherNode = m_graphNodes.find(nuid);
218 if (otherNode == m_graphNodes.end()) {
221 m_graphNodes.insert(make_pair(nuid, add_vertex(nodeProperty(nuid), m_graph)));
222 NS_ASSERT(ok ==
true);
224 put(vertex_index, m_graph, otherNode->second, m_maxNodeId);
230 add_edge(node->second, otherNode->second, m_graph);
235 RocketfuelMapReader::assignGw(Traits::vertex_descriptor vertex, uint32_t degree,
236 node_type_t nodeType)
238 graph_traits<Graph>::adjacency_iterator u, endu;
239 for (tie(u, endu) = adjacent_vertices(vertex, m_graph); u != endu; u++) {
240 if (
get(vertex_rank, m_graph, *u) != UNKNOWN)
243 put(vertex_rank, m_graph, *u, nodeType);
244 put(vertex_color, m_graph, *u,
"green");
246 uint32_t u_degree = out_degree(*u, m_graph);
247 if (u_degree < degree)
248 assignGw(*u, degree, BACKBONE);
253 RocketfuelMapReader::AssignClients(uint32_t clientDegree, uint32_t gwDegree)
255 graph_traits<Graph>::vertex_iterator v, endv;
256 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");
262 assignGw(*v, gwDegree + 1, GATEWAY);
269 bool connectBackbones )
274 topgen.open(GetFileName().c_str());
277 istringstream lineBuffer;
282 if (!topgen.is_open()) {
283 NS_LOG_WARN(
"Couldn't open the file " << GetFileName());
287 while (!topgen.eof()) {
297 getline(topgen, line);
298 buf = (
char*)line.c_str();
305 regerror(ret, ®ex, errbuf,
sizeof(errbuf));
311 if (ret == REG_NOMATCH) {
312 NS_LOG_WARN(
"match failed (maps file): %s" <<
buf);
322 if (regmatch[i].rm_so == -1) {
326 line[regmatch[i].rm_eo] =
'\0';
327 argv[i - 1] = &line[regmatch[i].rm_so];
332 GenerateFromMapsFile(argc, argv);
336 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));
342 for (
int clientDegree = 1; clientDegree <= params.
clientNodeDegrees; clientDegree++) {
343 AssignClients(clientDegree, std::min(clientDegree, 3));
346 graph_traits<Graph>::vertex_iterator v, endv;
347 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");
355 if (connectBackbones) {
356 ConnectBackboneRouters();
359 graph_traits<Graph>::edge_iterator e, ende;
360 for (tie(e, ende) = edges(m_graph); e != ende;) {
361 Traits::vertex_descriptor u = source(*e, m_graph), v = target(*e, m_graph);
363 node_type_t u_type =
get(vertex_rank, m_graph, u), v_type =
get(vertex_rank, m_graph, v);
365 if (u_type == BACKBONE && v_type == BACKBONE) {
368 else if ((u_type == GATEWAY && v_type == BACKBONE)
369 || (u_type == BACKBONE && v_type == GATEWAY)) {
372 else if (u_type == GATEWAY && v_type == GATEWAY) {
375 else if ((u_type == GATEWAY && v_type == CLIENT) || (u_type == CLIENT && v_type == GATEWAY)) {
380 NS_LOG_DEBUG(
"Wrong link type between nodes: " << u_type <<
" <-> " << v_type
381 <<
" (deleting the link)");
383 graph_traits<Graph>::edge_iterator tmp = e;
386 remove_edge(*e, m_graph);
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));
399 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
400 string nodeName =
get(vertex_name, m_graph, *v);
403 node_type_t type =
get(vertex_rank, m_graph, *v);
406 Names::Rename(nodeName,
"bb-" + nodeName);
407 put(vertex_name, m_graph, *v,
"bb-" + nodeName);
408 m_backboneRouters.Add(node);
411 Names::Rename(nodeName,
"leaf-" + nodeName);
412 put(vertex_name, m_graph, *v,
"leaf-" + nodeName);
413 m_customerRouters.Add(node);
416 Names::Rename(nodeName,
"gw-" + nodeName);
417 put(vertex_name, m_graph, *v,
"gw-" + nodeName);
418 m_gatewayRouters.Add(node);
421 NS_FATAL_ERROR(
"Should not happen");
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);
429 node_type_t u_type =
get(vertex_rank, m_graph, u), v_type =
get(vertex_rank, m_graph, v);
431 string u_name =
get(vertex_name, m_graph, u), v_name =
get(vertex_name, m_graph, v);
433 if (u_type == BACKBONE && v_type == BACKBONE) {
437 else if ((u_type == GATEWAY && v_type == BACKBONE)
438 || (u_type == BACKBONE && v_type == GATEWAY)) {
442 else if (u_type == GATEWAY && v_type == GATEWAY) {
446 else if ((u_type == GATEWAY && v_type == CLIENT) || (u_type == CLIENT && v_type == GATEWAY)) {
451 NS_FATAL_ERROR(
"Wrong link type between nodes: " << u_type <<
" <-> " << v_type);
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());
468 return m_backboneRouters;
474 return m_gatewayRouters;
480 return m_customerRouters;
486 for (NodeContainer::Iterator node = m.Begin(); node != m.End(); node++) {
487 std::string
name = Names::FindName(*node);
491 <<
"\t" << 0 <<
"\t" << 0 <<
"\n";
498 ofstream os(file.c_str(), ios::trunc);
499 os <<
"# any empty lines and lines starting with '#' symbol is ignored\n"
501 <<
"# The file should contain exactly two sections: router and link, each starting with the "
502 "corresponding keyword\n"
504 <<
"# router section defines topology nodes and their relative positions (e.g., to use in "
508 <<
"# each line in this section represents one router and should have the following data\n"
509 <<
"# node comment yPos xPos\n";
515 os <<
"# link section defines point-to-point links between nodes and characteristics of these "
520 <<
"# Each line should be in the following format (only first two are required, the rest can "
522 <<
"# 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";
528 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());
535 if (link->GetAttributeFailSafe(
"DataRate", tmp))
536 os << link->GetAttribute(
"DataRate") <<
"\t";
538 NS_FATAL_ERROR(
"DataRate must be specified for the link");
540 if (link->GetAttributeFailSafe(
"OSPF", tmp))
541 os << link->GetAttribute(
"OSPF") <<
"\t";
543 DataRate rate = boost::lexical_cast<DataRate>(link->GetAttribute(
"DataRate"));
545 int32_t cost = std::max(1,
static_cast<int32_t
>(1.0 * m_referenceOspfRate.GetBitRate()
546 / rate.GetBitRate()));
551 if (link->GetAttributeFailSafe(
"Delay", tmp)) {
552 os << link->GetAttribute(
"Delay") <<
"\t";
554 if (link->GetAttributeFailSafe(
"MaxPackets", tmp)) {
555 os << link->GetAttribute(
"MaxPackets") <<
"\t";
564 template<
class Names,
class Colors>
565 class name_color_writer {
567 name_color_writer(Names _names, Colors _colors)
573 template<
class VertexOrEdge>
575 operator()(std::ostream& out,
const VertexOrEdge& v)
const
578 out <<
"[shape=\"circle\",width=0.1,label=\"\",style=filled,fillcolor=\"" << colors[v] <<
"\"]";
586 template<
class Names,
class Colors>
587 inline name_color_writer<Names, Colors>
588 make_name_color_writer(Names n, Colors c)
590 return name_color_writer<Names, Colors>(n, c);
598 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));
605 RocketfuelMapReader::KeepOnlyBiggestConnectedComponent()
607 std::map<graph_traits<Graph>::vertex_descriptor,
int> temp;
608 associative_property_map<std::map<graph_traits<Graph>::vertex_descriptor,
int>> components(temp);
613 int num = connected_components(m_graph, components);
614 NS_LOG_DEBUG(
"Topology has " << num <<
" components");
616 vector<int> sizes(num, 0);
618 graph_traits<Graph>::vertex_iterator v, endv;
619 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
620 sizes[
get(components, *v)]++;
622 int largestComponent = max_element(sizes.begin(), sizes.end()) - sizes.begin();
631 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
632 if (
get(components, *v) == largestComponent)
635 clear_vertex(*v, m_graph);
640 for (tie(v, endv) = vertices(m_graph); v != endv;) {
641 if (
get(components, *v) == largestComponent) {
646 graph_traits<Graph>::vertex_iterator tmp = v;
649 remove_vertex(*v, m_graph);
655 for (tie(v, endv) = vertices(m_graph); v != endv; v++) {
656 put(vertex_index, m_graph, *v, index++);
661 RocketfuelMapReader::ConnectBackboneRouters()
666 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>>>>
671 map<Traits::vertex_descriptor, graph_traits<BbGraph>::vertex_descriptor> nodeMap;
675 graph_traits<Graph>::vertex_iterator v, endv;
676 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++);
685 graph_traits<BbGraph>::vertex_iterator bb, endBb;
686 for (tie(bb, endBb) = vertices(bbGraph); bb != endBb; bb++) {
687 Traits::vertex_descriptor actualVertex =
get(vertex_name, bbGraph, *bb);
689 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);
697 property_map<BbGraph, vertex_index1_t>::type components =
get(vertex_index1, bbGraph);
699 int num = connected_components(bbGraph, components);
700 NS_LOG_DEBUG(
"Backbone has " << num <<
" components");
704 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);
710 Ptr<UniformRandomVariable> randVar = CreateObject<UniformRandomVariable>();
712 for (
int i = 1; i < num; i++) {
713 int node1 = randVar->GetInteger(0, subgraphs[i - 1].size() - 1);
714 int node2 = randVar->GetInteger(0, subgraphs[i].size() - 1);
716 Traits::vertex_descriptor v1 =
get(vertex_name, bbGraph, subgraphs[i - 1][node1]),
717 v2 =
get(vertex_name, bbGraph, subgraphs[i][node2]);
719 NS_LOG_DEBUG(
"Connecting " <<
get(vertex_name, m_graph, v1) <<
"[" << node1 <<
"] with "
720 <<
get(vertex_name, m_graph, v2) <<
"[" << node2 <<
"]");
722 add_edge(v1, v2, m_graph);