NS-3 based Named Data Networking (NDN) simulator
ndnSIM: NDN, CCN, CCNx, content centric networks
API Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
rocketfuel-map-reader.cc
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2013 University of California, Los Angeles
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Ilya Moiseenko <iliamo@cs.ucla.edu>
19  * Hajime Tazaki (tazaki@sfc.wide.ad.jp)
20  * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
21  *
22  */
23 
24 #include "rocketfuel-map-reader.h"
25 
26 #include "ns3/nstime.h"
27 #include "ns3/log.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"
39 #include "ns3/ipv4.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"
46 
47 #include "ns3/mobility-model.h"
48 
49 #include <regex.h>
50 
51 #include <boost/foreach.hpp>
52 #include <boost/lexical_cast.hpp>
53 
54 #include <boost/graph/graphviz.hpp>
55 #include <boost/graph/connected_components.hpp>
56 
57 #include <iomanip>
58 
59 using namespace std;
60 using namespace boost;
61 
62 NS_LOG_COMPONENT_DEFINE ("RocketfuelMapReader");
63 
64 namespace ns3 {
65 
66 RocketfuelMapReader::RocketfuelMapReader (const std::string &path/*=""*/, double scale/*=1.0*/, const std::string &referenceOspfRate)
67  : AnnotatedTopologyReader (path, scale)
68  , m_referenceOspfRate (boost::lexical_cast<DataRate> (referenceOspfRate))
69 {
70 }
71 
72 RocketfuelMapReader::~RocketfuelMapReader ()
73 {
74 }
75 
76 NodeContainer
78 {
79  NS_FATAL_ERROR ("Deprecated call. Use the other overloaded method instead");
80  return NodeContainer ();
81 }
82 
83 
84 /* uid @loc [+] [bb] (num_neigh) [&ext] -> <nuid-1> <nuid-2> ... {-euid} ... =name[!] rn */
85 
86 #define REGMATCH_MAX 16
87 
88 #define START "^"
89 #define END "$"
90 #define SPACE "[ \t]+"
91 #define MAYSPACE "[ \t]*"
92 
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])" \
100 MAYSPACE END
101 
102 void
103 RocketfuelMapReader::CreateLink (string nodeName1, string nodeName2,
104  double averageRtt,
105  const string &minBw, const string &maxBw,
106  const string &minDelay, const string &maxDelay)
107 {
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);
111 
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 ())));
115 
116  int32_t metric = std::max (1, static_cast<int32_t> (1.0 * m_referenceOspfRate.GetBitRate () / randBandwidth.GetBitRate ()));
117 
118  Time randDelay =
119  Time::FromDouble ((m_randVar.GetValue (lexical_cast<Time> (minDelay).ToDouble (Time::US),
120  lexical_cast<Time> (maxDelay).ToDouble (Time::US))),
121  Time::US);
122 
123  uint32_t queue = ceil (averageRtt * (randBandwidth.GetBitRate () / 8.0 / 1100.0));
124 
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));
129 
130  AddLink (link);
131 }
132 
133 // NodeContainer
134 void
135 RocketfuelMapReader::GenerateFromMapsFile (int argc, char *argv[])
136 {
137  string uid;
138  string loc;
139  string ptr;
140  string name;
141  string nuid;
142  // bool dns = false;
143  // bool bb = false;
144  int num_neigh_s = 0;
145  unsigned int num_neigh = 0;
146  int radius = 0;
147  vector <string> neigh_list;
148 
149  uid = argv[0];
150  loc = argv[1];
151 
152  // if (argv[2])
153  // {
154  // dns = true;
155  // }
156 
157  // if (argv[3])
158  // {
159  // bb = true;
160  // }
161 
162  num_neigh_s = ::atoi (argv[4]);
163  if (num_neigh_s < 0)
164  {
165  num_neigh = 0;
166  NS_LOG_WARN ("Negative number of neighbors given");
167  }
168  else
169  {
170  num_neigh = num_neigh_s;
171  }
172 
173  /* neighbors */
174  if (argv[6])
175  {
176  char *nbr;
177  char *stringp = argv[6];
178  while ((nbr = strsep (&stringp, " \t")) != NULL)
179  {
180  nbr[strlen (nbr) - 1] = '\0';
181  neigh_list.push_back (nbr + 1);
182  }
183  }
184 
185  if (num_neigh != neigh_list.size ())
186  {
187  NS_LOG_WARN ("Given number of neighbors = " << num_neigh << " != size of neighbors list = " << neigh_list.size ());
188  }
189 
190  /* externs */
191  if (argv[7])
192  {
193  // euid = argv[7];
194  }
195 
196  /* name */
197  if (argv[8])
198  {
199  name = argv[8];
200  }
201 
202  radius = ::atoi (&argv[9][1]);
203  if (radius > 0)
204  {
205  return;
206  }
207 
208  // Create node and link
209  if (uid.empty ())
210  return;
211 
212 
213  node_map_t::iterator node = m_graphNodes.find (uid);
214  if (node == m_graphNodes.end ())
215  {
216  bool ok;
217  tie (node, ok) = m_graphNodes.insert (make_pair (uid, add_vertex (nodeProperty (uid), m_graph)));
218  NS_ASSERT (ok == true);
219 
220  put (vertex_index, m_graph, node->second, m_maxNodeId);
221  m_maxNodeId ++;
222  }
223 
224  for (uint32_t i = 0; i < neigh_list.size (); ++i)
225  {
226  nuid = neigh_list[i];
227 
228  if (nuid.empty ())
229  {
230  continue;
231  }
232 
233  node_map_t::iterator otherNode = m_graphNodes.find (nuid);
234  if (otherNode == m_graphNodes.end ())
235  {
236  bool ok;
237  tie (otherNode, ok) = m_graphNodes.insert (make_pair (nuid, add_vertex(nodeProperty (nuid), m_graph)));
238  NS_ASSERT (ok == true);
239 
240  put (vertex_index, m_graph, otherNode->second, m_maxNodeId);
241  m_maxNodeId ++;
242  }
243 
244  // cout << node->second << " <-> " << otherNode->second << endl;
245  // parallel edges are disabled in the graph, so no need to worry
246  add_edge (node->second, otherNode->second, m_graph);
247  }
248 }
249 
250 void RocketfuelMapReader::assignGw (Traits::vertex_descriptor vertex, uint32_t degree, node_type_t nodeType)
251 {
252  graph_traits<Graph>::adjacency_iterator u, endu;
253  for (tie (u, endu) = adjacent_vertices (vertex, m_graph); u != endu; u++)
254  {
255  if (get (vertex_rank, m_graph, *u) != UNKNOWN)
256  continue;
257 
258  put (vertex_rank, m_graph, *u, nodeType);
259  put (vertex_color, m_graph, *u, "green");
260 
261  uint32_t u_degree = out_degree (*u, m_graph);
262  if (u_degree < degree)
263  assignGw (*u, degree, BACKBONE);
264  }
265 };
266 
267 void
268 RocketfuelMapReader::AssignClients (uint32_t clientDegree, uint32_t gwDegree)
269 {
270  graph_traits<Graph>::vertex_iterator v, endv;
271  for (tie(v, endv) = vertices(m_graph); v != endv; v++)
272  {
273  uint32_t degree = out_degree (*v, m_graph);
274  if (degree == clientDegree)
275  {
276  put (vertex_rank, m_graph, *v, CLIENT);
277  put (vertex_color, m_graph, *v, "red");
278 
279  assignGw (*v, gwDegree+1, GATEWAY);
280  }
281  }
282 };
283 
284 NodeContainer
285 RocketfuelMapReader::Read (RocketfuelParams params, bool keepOneComponent/*=true*/, bool connectBackbones/*=true*/)
286 {
287  m_maxNodeId = 0;
288 
289  ifstream topgen;
290  topgen.open (GetFileName ().c_str ());
291  //NodeContainer nodes;
292  UniformVariable var;
293 
294  istringstream lineBuffer;
295  string line;
296  int lineNumber = 0;
297  char errbuf[512];
298 
299  if (!topgen.is_open ())
300  {
301  NS_LOG_WARN ("Couldn't open the file " << GetFileName ());
302  return m_nodes;
303  }
304 
305  while (!topgen.eof ())
306  {
307  int ret;
308  int argc;
309  char *argv[REGMATCH_MAX];
310  char *buf;
311 
312  lineNumber++;
313  line.clear ();
314  lineBuffer.clear ();
315 
316  getline (topgen, line);
317  buf = (char *)line.c_str ();
318 
319  regmatch_t regmatch[REGMATCH_MAX];
320  regex_t regex;
321 
322  ret = regcomp (&regex, ROCKETFUEL_MAPS_LINE, REG_EXTENDED | REG_NEWLINE);
323  if (ret != 0)
324  {
325  regerror (ret, &regex, errbuf, sizeof (errbuf));
326  regfree (&regex);
327  continue;
328  }
329 
330  ret = regexec (&regex, buf, REGMATCH_MAX, regmatch, 0);
331  if (ret == REG_NOMATCH)
332  {
333  NS_LOG_WARN ("match failed (maps file): %s" << buf);
334  regfree (&regex);
335  continue;
336  }
337 
338  line = buf;
339  argc = 0;
340 
341  /* regmatch[0] is the entire strings that matched */
342  for (int i = 1; i < REGMATCH_MAX; i++)
343  {
344  if (regmatch[i].rm_so == -1)
345  {
346  argv[i - 1] = NULL;
347  }
348  else
349  {
350  line[regmatch[i].rm_eo] = '\0';
351  argv[i - 1] = &line[regmatch[i].rm_so];
352  argc = i;
353  }
354  }
355 
356  GenerateFromMapsFile (argc, argv);
357  regfree (&regex);
358  }
359 
360  if (keepOneComponent)
361  {
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));
365  }
366 
367  for (int clientDegree = 1; clientDegree <= params.clientNodeDegrees; clientDegree++)
368  {
369  AssignClients (clientDegree, std::min (clientDegree, 3));
370  }
371 
372  graph_traits<Graph>::vertex_iterator v, endv;
373  for (tie(v, endv) = vertices(m_graph); v != endv; v++)
374  {
375  node_type_t type = get (vertex_rank, m_graph, *v);
376  if (type == UNKNOWN)
377  {
378  put (vertex_rank, m_graph, *v, BACKBONE);
379  put (vertex_color, m_graph, *v, "blue");
380  }
381  }
382 
383  if (connectBackbones)
384  {
385  ConnectBackboneRouters ();
386  }
387 
388  graph_traits<Graph>::edge_iterator e, ende;
389  for (tie (e, ende) = edges (m_graph); e != ende; )
390  {
391  Traits::vertex_descriptor
392  u = source (*e, m_graph),
393  v = target (*e, m_graph);
394 
395  node_type_t
396  u_type = get (vertex_rank, m_graph, u),
397  v_type = get (vertex_rank, m_graph, v);
398 
399  if (u_type == BACKBONE && v_type == BACKBONE)
400  {
401  // ok
402  }
403  else if ((u_type == GATEWAY && v_type == BACKBONE) ||
404  (u_type == BACKBONE && v_type == GATEWAY ))
405  {
406  // ok
407  }
408  else if (u_type == GATEWAY && v_type == GATEWAY)
409  {
410  // ok
411  }
412  else if ((u_type == GATEWAY && v_type == CLIENT) ||
413  (u_type == CLIENT && v_type == GATEWAY ))
414  {
415  // ok
416  }
417  else
418  {
419  // not ok
420  NS_LOG_DEBUG ("Wrong link type between nodes: " << u_type << " <-> " << v_type << " (deleting the link)");
421 
422  graph_traits<Graph>::edge_iterator tmp = e;
423  tmp++;
424 
425  remove_edge (*e, m_graph);
426  e = tmp;
427  continue;
428  }
429  e++;
430  }
431 
432  if (keepOneComponent)
433  {
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));
437  }
438 
439  for (tie(v, endv) = vertices(m_graph); v != endv; v++)
440  {
441  string nodeName = get (vertex_name, m_graph, *v);
442  Ptr<Node> node = CreateNode (nodeName, 0);
443 
444  node_type_t type = get (vertex_rank, m_graph, *v);
445  switch (type)
446  {
447  case BACKBONE:
448  Names::Rename (nodeName, "bb-" + nodeName);
449  put (vertex_name, m_graph, *v, "bb-" + nodeName);
450  m_backboneRouters.Add (node);
451  break;
452  case CLIENT:
453  Names::Rename (nodeName, "leaf-" + nodeName);
454  put (vertex_name, m_graph, *v, "leaf-" + nodeName);
455  m_customerRouters.Add (node);
456  break;
457  case GATEWAY:
458  Names::Rename (nodeName, "gw-" + nodeName);
459  put (vertex_name, m_graph, *v, "gw-" + nodeName);
460  m_gatewayRouters.Add (node);
461  break;
462  case UNKNOWN:
463  NS_FATAL_ERROR ("Should not happen");
464  break;
465  }
466  }
467 
468  for (tie (e, ende) = edges (m_graph); e != ende; e++)
469  {
470  Traits::vertex_descriptor
471  u = source (*e, m_graph),
472  v = target (*e, m_graph);
473 
474  node_type_t
475  u_type = get (vertex_rank, m_graph, u),
476  v_type = get (vertex_rank, m_graph, v);
477 
478  string
479  u_name = get (vertex_name, m_graph, u),
480  v_name = get (vertex_name, m_graph, v);
481 
482  if (u_type == BACKBONE && v_type == BACKBONE)
483  {
484  CreateLink (u_name, v_name,
485  params.averageRtt,
486  params.minb2bBandwidth, params.maxb2bBandwidth,
487  params.minb2bDelay, params.maxb2bDelay);
488  }
489  else if ((u_type == GATEWAY && v_type == BACKBONE) ||
490  (u_type == BACKBONE && v_type == GATEWAY ))
491  {
492  CreateLink (u_name, v_name,
493  params.averageRtt,
494  params.minb2gBandwidth, params.maxb2gBandwidth,
495  params.minb2gDelay, params.maxb2gDelay);
496  }
497  else if (u_type == GATEWAY && v_type == GATEWAY)
498  {
499  CreateLink (u_name, v_name,
500  params.averageRtt,
501  params.minb2gBandwidth, params.maxb2gBandwidth,
502  params.minb2gDelay, params.maxb2gDelay);
503  }
504  else if ((u_type == GATEWAY && v_type == CLIENT) ||
505  (u_type == CLIENT && v_type == GATEWAY ))
506  {
507  CreateLink (u_name, v_name,
508  params.averageRtt,
509  params.ming2cBandwidth, params.maxg2cBandwidth,
510  params.ming2cDelay, params.maxg2cDelay);
511  }
512  else
513  {
514  NS_FATAL_ERROR ("Wrong link type between nodes: " << u_type << " <-> " << v_type);
515  }
516  }
517 
518  ApplySettings ();
519 
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 ());
524 
525  return m_nodes;
526 }
527 
528 const NodeContainer &
529 RocketfuelMapReader::GetBackboneRouters () const
530 {
531  return m_backboneRouters;
532 }
533 
534 const NodeContainer &
535 RocketfuelMapReader::GetGatewayRouters () const
536 {
537  return m_gatewayRouters;
538 }
539 
540 const NodeContainer &
541 RocketfuelMapReader::GetCustomerRouters () const
542 {
543  return m_customerRouters;
544 }
545 
546 
547 static
548 void nodeWriter (std::ostream &os, NodeContainer& m)
549 {
550  for (NodeContainer::Iterator node = m.Begin ();
551  node != m.End ();
552  node ++)
553  {
554  std::string name = Names::FindName (*node);
555 
556  os << name << "\t" << "NA" << "\t" << 0 << "\t" << 0 << "\n";
557  }
558 };
559 
560 void
561 RocketfuelMapReader::SaveTopology (const std::string &file)
562 {
563  ofstream os (file.c_str (), ios::trunc);
564  os << "# any empty lines and lines starting with '#' symbol is ignored\n"
565  << "\n"
566  << "# The file should contain exactly two sections: router and link, each starting with the corresponding keyword\n"
567  << "\n"
568  << "# router section defines topology nodes and their relative positions (e.g., to use in visualizer)\n"
569  << "router\n"
570  << "\n"
571  << "# each line in this section represents one router and should have the following data\n"
572  << "# node comment yPos xPos\n";
573 
574  nodeWriter (os, m_backboneRouters);
575  nodeWriter (os, m_gatewayRouters);
576  nodeWriter (os, m_customerRouters);
577 
578  os << "# link section defines point-to-point links between nodes and characteristics of these links\n"
579  << "\n"
580  << "link\n"
581  << "\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";
588 
589  for (std::list<Link>::iterator link = m_linksList.begin ();
590  link != m_linksList.end ();
591  link ++)
592  {
593  string src = Names::FindName (link->GetFromNode ());
594  string dst = Names::FindName (link->GetToNode ());
595  os << src << "\t";
596  os << dst << "\t";
597 
598  string tmp;
599  if (link->GetAttributeFailSafe ("DataRate", tmp))
600  os << link->GetAttribute("DataRate") << "\t";
601  else
602  NS_FATAL_ERROR ("DataRate must be specified for the link");
603 
604  if (link->GetAttributeFailSafe ("OSPF", tmp))
605  os << link->GetAttribute("OSPF") << "\t";
606  else
607  {
608  DataRate rate = boost::lexical_cast<DataRate> (link->GetAttribute("DataRate"));
609 
610  int32_t cost = std::max (1, static_cast<int32_t> (1.0 * m_referenceOspfRate.GetBitRate () / rate.GetBitRate ()));
611 
612  os << cost << "\t";
613  }
614 
615  if (link->GetAttributeFailSafe ("Delay", tmp))
616  {
617  os << link->GetAttribute("Delay") << "\t";
618 
619  if (link->GetAttributeFailSafe ("MaxPackets", tmp))
620  {
621  os << link->GetAttribute("MaxPackets") << "\t";
622  }
623  }
624  os << "\n";
625  }
626 }
627 
628 
629 template <class Names, class Colors>
631 public:
632  name_color_writer(Names _names, Colors _colors) : names(_names), colors(_colors) {}
633 
634  template <class VertexOrEdge>
635  void operator()(std::ostream& out, const VertexOrEdge& v) const {
636  // out << "[label=\"" << names[v] << "\",style=filled,fillcolor=\"" << colors[v] << "\"]";
637  out << "[shape=\"circle\",width=0.1,label=\"\",style=filled,fillcolor=\"" << colors[v] << "\"]";
638  }
639 private:
640  Names names;
641  Colors colors;
642 };
643 
644 template <class Names, class Colors>
646 make_name_color_writer(Names n, Colors c) {
648 }
649 
650 
651 void
652 RocketfuelMapReader::SaveGraphviz (const std::string &file)
653 {
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));
658 }
659 
660 
661 void
662 RocketfuelMapReader::KeepOnlyBiggestConnectedComponent ()
663 {
664  std::map<graph_traits<Graph>::vertex_descriptor, int> temp;
665  associative_property_map< std::map<graph_traits<Graph>::vertex_descriptor, int> > components (temp);
666 
667  // //check if topology has breaks in its structure and trim it if yes
668  // property_map<Graph, vertex_index1_t>::type components = get (vertex_index1, m_graph);
669 
670  int num = connected_components (m_graph, components);
671  NS_LOG_DEBUG ("Topology has " << num << " components");
672 
673  vector<int> sizes (num, 0);
674 
675  graph_traits<Graph>::vertex_iterator v, endv;
676  for (tie(v, endv) = vertices(m_graph); v != endv; v++)
677  {
678  sizes[ get (components, *v) ] ++;
679  }
680  int largestComponent = max_element (sizes.begin (), sizes.end ()) - sizes.begin ();
681  // cout << "Largest: " << largestComponent << endl;
682 
683  // for (int i =0 ; i < num; i++) cout << sizes[i] << " ";
684  // cout << endl;
685 
687  // remove nodes and edges from smaller components //
689  for (tie(v, endv) = vertices(m_graph); v != endv; v++)
690  {
691  if (get (components, *v) == largestComponent)
692  continue;
693 
694  clear_vertex (*v, m_graph);
695  }
696 
697  // this works only if vertices are organized in listS or setS (iterator is not invalidated on remove)
698  for (tie(v, endv) = vertices(m_graph); v != endv; )
699  {
700  if (get (components, *v) == largestComponent)
701  {
702  v++;
703  continue;
704  }
705 
706  graph_traits<Graph>::vertex_iterator tmp = v;
707  tmp++;
708 
709  remove_vertex (*v, m_graph);
710  v = tmp;
711  }
712 
713  int index = 0;
714  // renumber nodes
715  for (tie(v, endv) = vertices(m_graph); v != endv; v++)
716  {
717  put (vertex_index, m_graph, *v, index++);
718  }
719 }
720 
721 void
722 RocketfuelMapReader::ConnectBackboneRouters ()
723 {
724  // not the tricky part. we want backbone to be a fully connected component,
725  // so traffic doesn't bounce from backbone to gateway and back
726 
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;
731  BbGraph bbGraph;
732  map<Traits::vertex_descriptor, graph_traits<BbGraph>::vertex_descriptor> nodeMap;
733 
734  int index = 0;
735 
736  graph_traits<Graph>::vertex_iterator v, endv;
737  for (tie(v, endv) = vertices(m_graph); v != endv; v++)
738  {
739  node_type_t type = get (vertex_rank, m_graph, *v);
740  if (type == BACKBONE)
741  {
742  graph_traits<BbGraph>::vertex_descriptor newv = add_vertex (*v, bbGraph);
743  put (vertex_index, bbGraph, newv, index++);
744  nodeMap[*v] = newv;
745  }
746  }
747 
748  graph_traits<BbGraph>::vertex_iterator bb, endBb;
749  for (tie (bb, endBb) = vertices (bbGraph); bb != endBb; bb++)
750  {
751  Traits::vertex_descriptor actualVertex = get (vertex_name, bbGraph, *bb);
752 
753  graph_traits<Graph>::adjacency_iterator u, endu;
754  for (tie (u, endu) = adjacent_vertices (actualVertex, m_graph); u != endu; u++)
755  {
756  if (nodeMap.find (*u) != nodeMap.end ())
757  {
758  add_edge (nodeMap [actualVertex], nodeMap[*u], bbGraph);
759  }
760  }
761  }
762 
763  property_map<BbGraph, vertex_index1_t>::type components = get (vertex_index1, bbGraph);
764 
765  int num = connected_components (bbGraph, components);
766  NS_LOG_DEBUG ("Backbone has " << num << " components");
767  if (num == 1)
768  return; // nothing to do
769 
770  vector< vector<graph_traits<BbGraph>::vertex_descriptor> > subgraphs (num);
771  for (tie (bb, endBb) = vertices (bbGraph); bb != endBb; bb++)
772  {
773  int component = get (vertex_index1, bbGraph, *bb);
774  subgraphs [component].push_back (*bb);
775  }
776 
777  UniformVariable randVar;
778 
779  for (int i = 1; i < num; i++)
780  {
781  int node1 = randVar.GetInteger (0, subgraphs[i-1].size ()-1);
782  int node2 = randVar.GetInteger (0, subgraphs[i].size ()-1);
783 
784  Traits::vertex_descriptor
785  v1 = get (vertex_name, bbGraph, subgraphs[i-1][node1]),
786  v2 = get (vertex_name, bbGraph, subgraphs[i ][node2]);
787 
788  NS_LOG_DEBUG ("Connecting " << get (vertex_name, m_graph, v1) << "[" << node1 << "] with "
789  << get (vertex_name, m_graph, v2) << "[" << node2 << "]");
790 
791  add_edge (v1, v2, m_graph);
792  }
793 }
794 
795 
796 } /* namespace ns3 */
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.