24 #include "rocketfuel-map-reader.h"
26 #include "ns3/nstime.h"
28 #include "ns3/fatal-error.h"
29 #include "ns3/assert.h"
30 #include "ns3/names.h"
31 #include "ns3/net-device-container.h"
32 #include "ns3/point-to-point-helper.h"
33 #include "ns3/point-to-point-net-device.h"
34 #include "ns3/internet-stack-helper.h"
35 #include "ns3/ipv4-address-helper.h"
36 #include "ns3/ipv4-global-routing-helper.h"
37 #include "ns3/drop-tail-queue.h"
38 #include "ns3/ipv4-interface.h"
40 #include "ns3/string.h"
41 #include "ns3/pointer.h"
42 #include "ns3/uinteger.h"
43 #include "ns3/ipv4-address.h"
44 #include "ns3/node-list.h"
45 #include "ns3/random-variable.h"
47 #include "ns3/mobility-model.h"
51 #include <boost/foreach.hpp>
52 #include <boost/lexical_cast.hpp>
54 #include <boost/graph/graphviz.hpp>
55 #include <boost/graph/connected_components.hpp>
60 using namespace boost;
62 NS_LOG_COMPONENT_DEFINE (
"RocketfuelMapReader");
66 RocketfuelMapReader::RocketfuelMapReader (
const std::string &path,
double scale,
const std::string &referenceOspfRate)
67 : AnnotatedTopologyReader (path, scale)
68 , m_referenceOspfRate (boost::lexical_cast<DataRate> (referenceOspfRate))
72 RocketfuelMapReader::~RocketfuelMapReader ()
79 NS_FATAL_ERROR (
"Deprecated call. Use the other overloaded method instead");
80 return NodeContainer ();
86 #define REGMATCH_MAX 16
90 #define SPACE "[ \t]+"
91 #define MAYSPACE "[ \t]*"
93 #define ROCKETFUEL_MAPS_LINE \
94 START "(-*[0-9]+)" SPACE "(@[?A-Za-z0-9,+]+)" SPACE \
95 "(\\+)*" MAYSPACE "(bb)*" MAYSPACE \
96 "\\(([0-9]+)\\)" SPACE "(&[0-9]+)*" MAYSPACE \
97 "->" MAYSPACE "(<[0-9 \t<>]+>)*" MAYSPACE \
98 "(\\{-[0-9\\{\\} \t-]+\\})*" SPACE \
99 "=([A-Za-z0-9.!-]+)" SPACE "r([0-9])" \
103 RocketfuelMapReader::CreateLink (
string nodeName1,
string nodeName2,
105 const string &minBw,
const string &maxBw,
106 const string &minDelay,
const string &maxDelay)
108 Ptr<Node> node1 = Names::Find<Node> (m_path, nodeName1);
109 Ptr<Node> node2 = Names::Find<Node> (m_path, nodeName2);
110 Link link (node1, nodeName1, node2, nodeName2);
112 DataRate randBandwidth
113 (m_randVar.GetInteger (static_cast<uint32_t> (lexical_cast<DataRate> (minBw).GetBitRate ()),
114 static_cast<uint32_t> (lexical_cast<DataRate> (maxBw).GetBitRate ())));
116 int32_t metric = std::max (1, static_cast<int32_t> (1.0 * m_referenceOspfRate.GetBitRate () / randBandwidth.GetBitRate ()));
119 Time::FromDouble ((m_randVar.GetValue (lexical_cast<Time> (minDelay).ToDouble (Time::US),
120 lexical_cast<Time> (maxDelay).ToDouble (Time::US))),
123 uint32_t queue = ceil (averageRtt * (randBandwidth.GetBitRate () / 8.0 / 1100.0));
125 link.SetAttribute (
"DataRate", boost::lexical_cast<string> (randBandwidth));
126 link.SetAttribute (
"OSPF", boost::lexical_cast<string> (metric));
127 link.SetAttribute (
"Delay", boost::lexical_cast<string> (ceil (randDelay.ToDouble (Time::US)))+
"us");
128 link.SetAttribute (
"MaxPackets", boost::lexical_cast<string> (queue));
135 RocketfuelMapReader::GenerateFromMapsFile (
int argc,
char *argv[])
145 unsigned int num_neigh = 0;
147 vector <string> neigh_list;
162 num_neigh_s = ::atoi (argv[4]);
166 NS_LOG_WARN (
"Negative number of neighbors given");
170 num_neigh = num_neigh_s;
177 char *stringp = argv[6];
178 while ((nbr = strsep (&stringp,
" \t")) != NULL)
180 nbr[strlen (nbr) - 1] =
'\0';
181 neigh_list.push_back (nbr + 1);
185 if (num_neigh != neigh_list.size ())
187 NS_LOG_WARN (
"Given number of neighbors = " << num_neigh <<
" != size of neighbors list = " << neigh_list.size ());
202 radius = ::atoi (&argv[9][1]);
213 node_map_t::iterator node = m_graphNodes.find (uid);
214 if (node == m_graphNodes.end ())
217 tie (node, ok) = m_graphNodes.insert (make_pair (uid, add_vertex (nodeProperty (uid), m_graph)));
218 NS_ASSERT (ok ==
true);
220 put (vertex_index, m_graph, node->second, m_maxNodeId);
224 for (uint32_t i = 0; i < neigh_list.size (); ++i)
226 nuid = neigh_list[i];
233 node_map_t::iterator otherNode = m_graphNodes.find (nuid);
234 if (otherNode == m_graphNodes.end ())
237 tie (otherNode, ok) = m_graphNodes.insert (make_pair (nuid, add_vertex(nodeProperty (nuid), m_graph)));
238 NS_ASSERT (ok ==
true);
240 put (vertex_index, m_graph, otherNode->second, m_maxNodeId);
246 add_edge (node->second, otherNode->second, m_graph);
250 void RocketfuelMapReader::assignGw (Traits::vertex_descriptor vertex, uint32_t degree, node_type_t nodeType)
252 graph_traits<Graph>::adjacency_iterator u, endu;
253 for (tie (u, endu) = adjacent_vertices (vertex, m_graph); u != endu; u++)
255 if (
get (vertex_rank, m_graph, *u) != UNKNOWN)
258 put (vertex_rank, m_graph, *u, nodeType);
259 put (vertex_color, m_graph, *u,
"green");
261 uint32_t u_degree = out_degree (*u, m_graph);
262 if (u_degree < degree)
263 assignGw (*u, degree, BACKBONE);
268 RocketfuelMapReader::AssignClients (uint32_t clientDegree, uint32_t gwDegree)
270 graph_traits<Graph>::vertex_iterator v, endv;
271 for (tie(v, endv) = vertices(m_graph); v != endv; v++)
273 uint32_t degree = out_degree (*v, m_graph);
274 if (degree == clientDegree)
276 put (vertex_rank, m_graph, *v, CLIENT);
277 put (vertex_color, m_graph, *v,
"red");
279 assignGw (*v, gwDegree+1, GATEWAY);
290 topgen.open (GetFileName ().c_str ());
294 istringstream lineBuffer;
299 if (!topgen.is_open ())
301 NS_LOG_WARN (
"Couldn't open the file " << GetFileName ());
305 while (!topgen.eof ())
309 char *argv[REGMATCH_MAX];
316 getline (topgen, line);
317 buf = (
char *)line.c_str ();
319 regmatch_t regmatch[REGMATCH_MAX];
322 ret = regcomp (®ex, ROCKETFUEL_MAPS_LINE, REG_EXTENDED | REG_NEWLINE);
325 regerror (ret, ®ex, errbuf,
sizeof (errbuf));
330 ret = regexec (®ex, buf, REGMATCH_MAX, regmatch, 0);
331 if (ret == REG_NOMATCH)
333 NS_LOG_WARN (
"match failed (maps file): %s" << buf);
342 for (
int i = 1; i < REGMATCH_MAX; i++)
344 if (regmatch[i].rm_so == -1)
350 line[regmatch[i].rm_eo] =
'\0';
351 argv[i - 1] = &line[regmatch[i].rm_so];
356 GenerateFromMapsFile (argc, argv);
360 if (keepOneComponent)
362 NS_LOG_DEBUG (
"Before eliminating disconnected nodes: " << num_vertices(m_graph));
363 KeepOnlyBiggestConnectedComponent ();
364 NS_LOG_DEBUG (
"After eliminating disconnected nodes: " << num_vertices(m_graph));
367 for (
int clientDegree = 1; clientDegree <= params.clientNodeDegrees; clientDegree++)
369 AssignClients (clientDegree, std::min (clientDegree, 3));
372 graph_traits<Graph>::vertex_iterator v, endv;
373 for (tie(v, endv) = vertices(m_graph); v != endv; v++)
375 node_type_t type =
get (vertex_rank, m_graph, *v);
378 put (vertex_rank, m_graph, *v, BACKBONE);
379 put (vertex_color, m_graph, *v,
"blue");
383 if (connectBackbones)
385 ConnectBackboneRouters ();
388 graph_traits<Graph>::edge_iterator e, ende;
389 for (tie (e, ende) = edges (m_graph); e != ende; )
391 Traits::vertex_descriptor
392 u = source (*e, m_graph),
393 v = target (*e, m_graph);
396 u_type =
get (vertex_rank, m_graph, u),
397 v_type =
get (vertex_rank, m_graph, v);
399 if (u_type == BACKBONE && v_type == BACKBONE)
403 else if ((u_type == GATEWAY && v_type == BACKBONE) ||
404 (u_type == BACKBONE && v_type == GATEWAY ))
408 else if (u_type == GATEWAY && v_type == GATEWAY)
412 else if ((u_type == GATEWAY && v_type == CLIENT) ||
413 (u_type == CLIENT && v_type == GATEWAY ))
420 NS_LOG_DEBUG (
"Wrong link type between nodes: " << u_type <<
" <-> " << v_type <<
" (deleting the link)");
422 graph_traits<Graph>::edge_iterator tmp = e;
425 remove_edge (*e, m_graph);
432 if (keepOneComponent)
434 NS_LOG_DEBUG (
"Before 2 eliminating disconnected nodes: " << num_vertices(m_graph));
435 KeepOnlyBiggestConnectedComponent ();
436 NS_LOG_DEBUG (
"After 2 eliminating disconnected nodes: " << num_vertices(m_graph));
439 for (tie(v, endv) = vertices(m_graph); v != endv; v++)
441 string nodeName =
get (vertex_name, m_graph, *v);
442 Ptr<Node> node = CreateNode (nodeName, 0);
444 node_type_t type =
get (vertex_rank, m_graph, *v);
448 Names::Rename (nodeName,
"bb-" + nodeName);
449 put (vertex_name, m_graph, *v,
"bb-" + nodeName);
450 m_backboneRouters.Add (node);
453 Names::Rename (nodeName,
"leaf-" + nodeName);
454 put (vertex_name, m_graph, *v,
"leaf-" + nodeName);
455 m_customerRouters.Add (node);
458 Names::Rename (nodeName,
"gw-" + nodeName);
459 put (vertex_name, m_graph, *v,
"gw-" + nodeName);
460 m_gatewayRouters.Add (node);
463 NS_FATAL_ERROR (
"Should not happen");
468 for (tie (e, ende) = edges (m_graph); e != ende; e++)
470 Traits::vertex_descriptor
471 u = source (*e, m_graph),
472 v = target (*e, m_graph);
475 u_type =
get (vertex_rank, m_graph, u),
476 v_type =
get (vertex_rank, m_graph, v);
479 u_name =
get (vertex_name, m_graph, u),
480 v_name =
get (vertex_name, m_graph, v);
482 if (u_type == BACKBONE && v_type == BACKBONE)
484 CreateLink (u_name, v_name,
486 params.minb2bBandwidth, params.maxb2bBandwidth,
487 params.minb2bDelay, params.maxb2bDelay);
489 else if ((u_type == GATEWAY && v_type == BACKBONE) ||
490 (u_type == BACKBONE && v_type == GATEWAY ))
492 CreateLink (u_name, v_name,
494 params.minb2gBandwidth, params.maxb2gBandwidth,
495 params.minb2gDelay, params.maxb2gDelay);
497 else if (u_type == GATEWAY && v_type == GATEWAY)
499 CreateLink (u_name, v_name,
501 params.minb2gBandwidth, params.maxb2gBandwidth,
502 params.minb2gDelay, params.maxb2gDelay);
504 else if ((u_type == GATEWAY && v_type == CLIENT) ||
505 (u_type == CLIENT && v_type == GATEWAY ))
507 CreateLink (u_name, v_name,
509 params.ming2cBandwidth, params.maxg2cBandwidth,
510 params.ming2cDelay, params.maxg2cDelay);
514 NS_FATAL_ERROR (
"Wrong link type between nodes: " << u_type <<
" <-> " << v_type);
520 NS_LOG_INFO (
"Clients: " << m_customerRouters.GetN ());
521 NS_LOG_INFO (
"Gateways: " << m_gatewayRouters.GetN ());
522 NS_LOG_INFO (
"Backbones: " << m_backboneRouters.GetN ());
523 NS_LOG_INFO (
"Links: " <<
GetLinks ().size ());
528 const NodeContainer &
529 RocketfuelMapReader::GetBackboneRouters ()
const
531 return m_backboneRouters;
534 const NodeContainer &
535 RocketfuelMapReader::GetGatewayRouters ()
const
537 return m_gatewayRouters;
540 const NodeContainer &
541 RocketfuelMapReader::GetCustomerRouters ()
const
543 return m_customerRouters;
548 void nodeWriter (std::ostream &os, NodeContainer& m)
550 for (NodeContainer::Iterator node = m.Begin ();
554 std::string name = Names::FindName (*node);
556 os << name <<
"\t" <<
"NA" <<
"\t" << 0 <<
"\t" << 0 <<
"\n";
563 ofstream os (file.c_str (), ios::trunc);
564 os <<
"# any empty lines and lines starting with '#' symbol is ignored\n"
566 <<
"# The file should contain exactly two sections: router and link, each starting with the corresponding keyword\n"
568 <<
"# router section defines topology nodes and their relative positions (e.g., to use in visualizer)\n"
571 <<
"# each line in this section represents one router and should have the following data\n"
572 <<
"# node comment yPos xPos\n";
574 nodeWriter (os, m_backboneRouters);
575 nodeWriter (os, m_gatewayRouters);
576 nodeWriter (os, m_customerRouters);
578 os <<
"# link section defines point-to-point links between nodes and characteristics of these links\n"
582 <<
"# Each line should be in the following format (only first two are required, the rest can be omitted)\n"
583 <<
"# srcNode dstNode bandwidth metric delay queue\n"
584 <<
"# bandwidth: link bandwidth\n"
585 <<
"# metric: routing metric\n"
586 <<
"# delay: link delay\n"
587 <<
"# queue: MaxPackets for transmission queue on the link (both directions)\n";
589 for (std::list<Link>::iterator link = m_linksList.begin ();
590 link != m_linksList.end ();
593 string src = Names::FindName (link->GetFromNode ());
594 string dst = Names::FindName (link->GetToNode ());
599 if (link->GetAttributeFailSafe (
"DataRate", tmp))
600 os << link->GetAttribute(
"DataRate") <<
"\t";
602 NS_FATAL_ERROR (
"DataRate must be specified for the link");
604 if (link->GetAttributeFailSafe (
"OSPF", tmp))
605 os << link->GetAttribute(
"OSPF") <<
"\t";
608 DataRate rate = boost::lexical_cast<DataRate> (link->GetAttribute(
"DataRate"));
610 int32_t cost = std::max (1, static_cast<int32_t> (1.0 * m_referenceOspfRate.GetBitRate () / rate.GetBitRate ()));
615 if (link->GetAttributeFailSafe (
"Delay", tmp))
617 os << link->GetAttribute(
"Delay") <<
"\t";
619 if (link->GetAttributeFailSafe (
"MaxPackets", tmp))
621 os << link->GetAttribute(
"MaxPackets") <<
"\t";
629 template <
class Names,
class Colors>
632 name_color_writer(Names _names, Colors _colors) : names(_names), colors(_colors) {}
634 template <
class VertexOrEdge>
635 void operator()(std::ostream& out,
const VertexOrEdge& v)
const {
637 out <<
"[shape=\"circle\",width=0.1,label=\"\",style=filled,fillcolor=\"" << colors[v] <<
"\"]";
644 template <
class Names,
class Colors>
646 make_name_color_writer(Names n, Colors c) {
654 ofstream of (file.c_str ());
655 property_map<Graph, vertex_name_t>::type names =
get (vertex_name, m_graph);
656 property_map<Graph, vertex_color_t>::type colors =
get (vertex_color, m_graph);
657 write_graphviz(of, m_graph, make_name_color_writer (names, colors));
662 RocketfuelMapReader::KeepOnlyBiggestConnectedComponent ()
664 std::map<graph_traits<Graph>::vertex_descriptor,
int> temp;
665 associative_property_map< std::map<graph_traits<Graph>::vertex_descriptor,
int> > components (temp);
670 int num = connected_components (m_graph, components);
671 NS_LOG_DEBUG (
"Topology has " << num <<
" components");
673 vector<int> sizes (num, 0);
675 graph_traits<Graph>::vertex_iterator v, endv;
676 for (tie(v, endv) = vertices(m_graph); v != endv; v++)
678 sizes[
get (components, *v) ] ++;
680 int largestComponent = max_element (sizes.begin (), sizes.end ()) - sizes.begin ();
689 for (tie(v, endv) = vertices(m_graph); v != endv; v++)
691 if (
get (components, *v) == largestComponent)
694 clear_vertex (*v, m_graph);
698 for (tie(v, endv) = vertices(m_graph); v != endv; )
700 if (
get (components, *v) == largestComponent)
706 graph_traits<Graph>::vertex_iterator tmp = v;
709 remove_vertex (*v, m_graph);
715 for (tie(v, endv) = vertices(m_graph); v != endv; v++)
717 put (vertex_index, m_graph, *v, index++);
722 RocketfuelMapReader::ConnectBackboneRouters ()
727 typedef adjacency_list< setS, setS, boost::undirectedS,
728 property<vertex_name_t, Traits::vertex_descriptor,
property
729 < vertex_index_t, int,
property
730 < vertex_index1_t,
int > > > > BbGraph;
732 map<Traits::vertex_descriptor, graph_traits<BbGraph>::vertex_descriptor> nodeMap;
736 graph_traits<Graph>::vertex_iterator v, endv;
737 for (tie(v, endv) = vertices(m_graph); v != endv; v++)
739 node_type_t type =
get (vertex_rank, m_graph, *v);
740 if (type == BACKBONE)
742 graph_traits<BbGraph>::vertex_descriptor newv = add_vertex (*v, bbGraph);
743 put (vertex_index, bbGraph, newv, index++);
748 graph_traits<BbGraph>::vertex_iterator bb, endBb;
749 for (tie (bb, endBb) = vertices (bbGraph); bb != endBb; bb++)
751 Traits::vertex_descriptor actualVertex =
get (vertex_name, bbGraph, *bb);
753 graph_traits<Graph>::adjacency_iterator u, endu;
754 for (tie (u, endu) = adjacent_vertices (actualVertex, m_graph); u != endu; u++)
756 if (nodeMap.find (*u) != nodeMap.end ())
758 add_edge (nodeMap [actualVertex], nodeMap[*u], bbGraph);
763 property_map<BbGraph, vertex_index1_t>::type components =
get (vertex_index1, bbGraph);
765 int num = connected_components (bbGraph, components);
766 NS_LOG_DEBUG (
"Backbone has " << num <<
" components");
770 vector< vector<graph_traits<BbGraph>::vertex_descriptor> > subgraphs (num);
771 for (tie (bb, endBb) = vertices (bbGraph); bb != endBb; bb++)
773 int component =
get (vertex_index1, bbGraph, *bb);
774 subgraphs [component].push_back (*bb);
777 UniformVariable randVar;
779 for (
int i = 1; i < num; i++)
781 int node1 = randVar.GetInteger (0, subgraphs[i-1].size ()-1);
782 int node2 = randVar.GetInteger (0, subgraphs[i].size ()-1);
784 Traits::vertex_descriptor
785 v1 =
get (vertex_name, bbGraph, subgraphs[i-1][node1]),
786 v2 =
get (vertex_name, bbGraph, subgraphs[i ][node2]);
788 NS_LOG_DEBUG (
"Connecting " <<
get (vertex_name, m_graph, v1) <<
"[" << node1 <<
"] with "
789 <<
get (vertex_name, m_graph, v2) <<
"[" << node2 <<
"]");
791 add_edge (v1, v2, m_graph);
virtual const std::list< Link > & GetLinks() const
Get links read by the reader.
virtual void SaveGraphviz(const std::string &file)
Save topology in graphviz format (.dot file)
void ApplySettings()
This method applies setting to corresponding nodes and links NetDeviceContainer must be allocated Nod...
virtual void SaveTopology(const std::string &file)
Save positions (e.g., after manual modification using visualizer)
virtual NodeContainer Read()
Deprecated call.