physical.h 15.4 KB
Newer Older
Robert Ricci's avatar
Robert Ricci committed
1
/*
Robert Ricci's avatar
Robert Ricci committed
2
 * Copyright (c) 2000-2010 University of Utah and the Flux Group.
3
 *
4
 * {{{EMULAB-LICENSE
5
 *
6
 * This file is part of the Emulab network testbed software.
7
 *
8 9 10 11
 * This file is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or (at
 * your option) any later version.
12
 *
13 14 15 16
 * This file 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 Affero General Public
 * License for more details.
17
 *
18 19
 * You should have received a copy of the GNU Affero General Public License
 * along with this file.  If not, see <http://www.gnu.org/licenses/>.
20
 *
21
 * }}}
Robert Ricci's avatar
Robert Ricci committed
22 23
 */

Mac Newbold's avatar
Mac Newbold committed
24 25 26
#ifndef __PHYSICAL_H
#define __PHYSICAL_H

27
#include "common.h"
28
#include "delay.h"
29
#include "port.h"
30

31
#include <set>
32 33 34 35 36
#include <list>
using namespace std;

#include <boost/config.hpp>
#include <boost/utility.hpp>
37
#include BOOST_PMAP_HEADER
38
#include <boost/graph/adjacency_list.hpp>
39
#include <boost/graph/graph_traits.hpp>
40 41
using namespace boost;

42 43 44
#include <string>
using namespace std;

45 46 47 48
// Icky, but I can't include virtual.h here
class tb_vnode;
typedef hash_set<tb_vnode*,hashptr<tb_vnode*> > tb_vnode_set;

49
// Class forward declarations - defined below
50
class tb_pclass;
51 52 53 54 55
class tb_pnode;
class tb_switch;
class tb_plink;
class tb_slink;

56
// typedefs
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
typedef property<vertex_data_t,tb_pnode*> PNodeProperty;
typedef property<edge_data_t,tb_plink*> PEdgeProperty;
typedef property<vertex_data_t,tb_switch*> SNodeProperty;
typedef property<edge_data_t,tb_slink*,
  property<edge_weight_t,long> > SEdgeProperty;

typedef adjacency_list<listS,listS,undirectedS,
  PNodeProperty,PEdgeProperty> tb_pgraph;
typedef adjacency_list<listS,vecS,undirectedS,
  SNodeProperty,SEdgeProperty> tb_sgraph;

typedef property_map<tb_pgraph,vertex_data_t>::type tb_pgraph_vertex_pmap;
typedef property_map<tb_pgraph,edge_data_t>::type tb_pgraph_edge_pmap;
typedef property_map<tb_sgraph,vertex_data_t>::type tb_sgraph_vertex_pmap;
typedef property_map<tb_sgraph,edge_data_t>::type tb_sgraph_edge_pmap;
typedef property_map<tb_sgraph,edge_weight_t>::type tb_sgraph_weight_pmap;

typedef graph_traits<tb_pgraph>::vertex_descriptor pvertex;
typedef graph_traits<tb_pgraph>::edge_descriptor pedge;
typedef graph_traits<tb_sgraph>::vertex_descriptor svertex;
typedef graph_traits<tb_sgraph>::edge_descriptor sedge;

typedef graph_traits<tb_pgraph>::vertex_iterator pvertex_iterator;
typedef graph_traits<tb_pgraph>::edge_iterator pedge_iterator;
typedef graph_traits<tb_pgraph>::out_edge_iterator poedge_iterator;
typedef graph_traits<tb_sgraph>::vertex_iterator svertex_iterator;
typedef graph_traits<tb_sgraph>::edge_iterator sedge_iterator;
typedef graph_traits<tb_sgraph>::out_edge_iterator soedge_iterator;

86
typedef set<pvertex> pvertex_set;
87
typedef hash_map<tb_pnode*,pvertex,hashptr<tb_pnode*> > pnode_pvertex_map;
88
typedef hash_map<fstring,pvertex> name_pvertex_map;
89 90 91 92 93 94 95
typedef vector<svertex> switch_pred_map;
typedef hash_map<svertex,switch_pred_map*>switch_pred_map_map;
typedef vector<svertex> switch_dist_map;
typedef hash_map<svertex,switch_dist_map*>switch_dist_map_map;
typedef list<pedge> pedge_path;
typedef list<pvertex> pvertex_list;

96
typedef hash_map<fstring,int> link_type_count_map;
97

98 99
// Globals, declared in assign.cc

100 101 102 103
extern tb_pgraph_vertex_pmap pvertex_pmap;
extern tb_pgraph_edge_pmap pedge_pmap;
extern tb_sgraph_vertex_pmap svertex_pmap;
extern tb_sgraph_edge_pmap sedge_pmap;
104

105 106 107 108
// These are down here because forwarding.h need tb_pgraph and related types
#include "featuredesire.h"
#include "forwarding.h"

109 110 111 112 113
/*
 * Represents a physical type
 */
class tb_ptype {
    public:
114
	tb_ptype(fstring _name) : users(0), max_users(-1), my_name(_name), slots(0)
115
	    { ; }
116
	inline fstring name() const { return my_name; };
117 118 119 120 121
	inline int pnode_slots() const { return slots; };
	inline int maxusers() const { return max_users; };
	inline int add_users(int count = 1) {
	    int oldusers = users;
	    users = users + count;
122
	    if ((max_users >= 0) && (oldusers <= max_users) && (users > max_users)) {
123 124 125 126 127 128 129 130 131
		return 1;
	    } else {
		return 0;
	    }
	}
	inline int remove_users(int count = 1) {
	    int oldusers = users;
	    users = users - count;
	    assert(users >= 0);
132
	    if ((max_users >= 0) && (oldusers > max_users) && (users <= max_users)) {
133 134 135 136 137
		return 1;
	    } else {
		return 0;
	    }
	}
138 139
	inline void set_max_users(int _max_users) {
	    max_users = _max_users;
140 141
	}
	inline void add_slots(int additional_slots) {
142
	    //cerr << "Adding " << additional_slots << " to " << my_name
143
            //<< endl;
144 145
	    slots += additional_slots;
	}
146
	inline void remove_slots(int slots_to_remove) {
147 148
	    //cerr << "Removing " << slots_to_remove << " from " << my_name
            //<< endl;
149 150
	    slots -= slots_to_remove;
	}
151
    private:
152
	fstring my_name;
153 154 155 156 157 158 159 160 161
	/* How many users are using this type right now */
	int users;
	/* The maximum number of nodes of this type we're allowed to use */
	int max_users;
	/* How many slots of this type are available in the physical topology */
	int slots;
};


Mac Newbold's avatar
Mac Newbold committed
162 163
class tb_pnode {
public:
164
  tb_pnode() { tb_pnode("(unnamed)"); }
165
  tb_pnode(fstring _name) : types(), features(), name(_name), typed(false),
166 167
  			  current_type_record(NULL), total_load(0),
			  switches(), sgraph_switch(), switch_used_links(0),
168
			  total_interfaces(0), used_interfaces(0),
169 170
			  total_bandwidth(0), nontrivial_bw_used(0),
			  my_class(NULL), my_own_class(NULL), assigned_nodes(),
171
			  trivial_bw(0), trivial_bw_used(0), subnode_of(NULL),
172
			  subnode_of_name(""), has_subnode(false),
173
			  unique(false), is_switch(false), forwarding() {;}
174

175 176
  class type_record {
      public:
177
	  type_record(int _max_load, bool _static_type, tb_ptype *_ptype) :
178
	      max_load(_max_load), current_load(0),
179
	      static_type(_static_type), ptype(_ptype) { ; }
180

181
	  bool operator==(const type_record &b) {
182
	      return ((max_load == b.max_load) && (static_type == b.static_type));
183
	  }
184

185 186 187
	  tb_ptype *get_ptype() const {
	      return(ptype);
          }
188

189 190 191
          bool is_static() const {
   	      return(static_type);
          }
192

193 194 195
          int get_max_load() const {
	      return(max_load);
          }
196

197 198 199
          int get_current_load() const {
	      return(current_load);
          }
200

201 202 203
          void add_load(int howmuch) {
              current_load += howmuch;
	  }
204

205 206 207
          void remove_load(int howmuch) {
	      current_load -= howmuch;
          }
208

209 210
	  friend ostream &operator<<(ostream &o, const type_record& node)
	  {
211
	      return (o << "max_load = " << node.max_load <<
212
		   " current_load = " << node.current_load <<
213
		   " static_type = " << node.static_type);
214
	  }
215 216 217 218
      private:
          int max_load;		// maximum load for this type
          int current_load;	// how many vnodes are assigned of this type
          bool static_type;	// whether this type is static or dynamic
219

220 221
          tb_ptype *ptype;	// Pointer to the global ptype strucutre for
	     		        // type
222

223 224
  };

225 226
  // Contains max nodes for each type
  // NOTE: Parallel data strucure, see below!
227
  typedef hash_map<fstring,type_record*> types_map;
228
  types_map types;
229

230 231 232 233
  // Same as above, but a list for fast iteration
  // If you touch the above list, you must touch this one too
  typedef list<type_record*> types_list;
  types_list type_list;
234 235

  // contains cost of each feature
236
  node_feature_set features;
237

238
  fstring name;			// name of the node
239
  bool typed;			// has it been typed
240
  fstring current_type;		// type the node is currently being used as
241 242 243 244
  type_record* current_type_record;
  int total_load;		// total load for all types
  //int max_load;			// maxmium load for current type
  //int current_load;		// how many vnodes are assigned to this pnode
245 246 247 248 249 250 251 252 253 254
  pvertex_set switches;		// what switches the node is attached to

  svertex sgraph_switch;	// only for switches, the corresponding
				// sgraph switch.
  int switch_used_links;	// only for switches, how many links are
				// in use.  Switch is in use whenever > 0

  int total_interfaces;		// total number of links leaving the node
  int used_interfaces;		// number of links that are currently in use
  int total_bandwidth;		// total bandwidth of all this nodes' links
255 256
  int nontrivial_bw_used;	// amount of non-trivial bandwidth in use on
  				// this node - for debugging only
257 258 259

  tb_pclass *my_class;		// the pclass this node belongs to

260 261 262
  tb_pclass *my_own_class;	// if using DYNAMIC_PCLASSES, a pointer to the
  				// node's own class

263 264 265 266 267 268
  tb_vnode_set assigned_nodes;	// the set of vnodes currently assigned

  int trivial_bw;		// the maximum amount of trivial bandwidth
  				// available
  int trivial_bw_used;		// the amount of bandwidth currently used by
  				// trivial links
269 270 271

  tb_pnode *subnode_of;		// the pnode, if any, that this node is a
  				// subnode of
272
  fstring subnode_of_name;        // name of the pnode this node is a subnode of -
273
                                // used to do late bindind
274 275

  bool has_subnode;		// whether or not this node has any subnodes
276 277 278 279

  bool unique;		// says that this pnode should never go into a
  				// pclass with other nodes, because of some
				// characteristic that is not known to assign
Robert Ricci's avatar
Robert Ricci committed
280 281 282

  bool is_switch;		// Indicates whether or not this pnode is a
                                // switch
283
				// XXX: Should go away soon!
284

285 286
  forwarding_info forwarding;	// Records the set of protocols this node can
                                // forward
287

288
  link_type_count_map link_counts; // Counts how many links of each type this
289 290
  				   // node has

291
  bool set_current_type(fstring type) {
292 293 294 295 296 297 298 299 300 301 302 303
      if (types.find(type) == types.end()) {
	  //cout << "Failed to find type " << type << endl;
	  return false;
      }
      current_type = type;
      typed = true;
      current_type_record = types[type];
      return true;
  }

  void remove_current_type() {
      typed = false;
Robert Ricci's avatar
Robert Ricci committed
304
      current_type = "";
305 306 307
      current_type_record = NULL;
  }

308
  // Output operator for debugging
Mac Newbold's avatar
Mac Newbold committed
309 310
  friend ostream &operator<<(ostream &o, const tb_pnode& node)
    {
311 312 313
      o << "tb_pnode: " << node.name << " (" << &node << ")" << endl;
      o << "  Types:" << endl;
      for (types_map::const_iterator it = node.types.begin();
314
	   it!=node.types.end();it++)
Robert Ricci's avatar
Robert Ricci committed
315
	o << "    " << (*it).first << " -> " << *((*it).second) << endl;
316
      o << "  Features:" << endl;
317
      for (node_feature_set::const_iterator it = node.features.begin();
318
	   it != node.features.end(); it++)
319
	cout << "    " << it->name() << " -> " << it->cost() << endl;
Robert Ricci's avatar
Robert Ricci committed
320
      /* o << "  Current Type: " << node.current_type << endl; <<
321
	" (" << node.current_load << "/" << node.max_load << ")" <<  endl; */
Robert Ricci's avatar
Robert Ricci committed
322
      /*o << "  switches=";
323 324 325 326 327
      for (pvertex_set::const_iterator it = node.switches.begin();
	   it != node.switches.end();++it) {
	o << " " << get(pvertex_pmap,*it)->name;
      }
      o << endl;
328
      o << " sgraph_switch=" << node.sgraph_switch
Robert Ricci's avatar
Robert Ricci committed
329
	  << " my_class=" << node.my_class << endl; */
Mac Newbold's avatar
Mac Newbold committed
330 331
      return o;
    }
332

333 334 335 336
};

class tb_switch {
public:
337 338 339 340 341 342
  friend ostream &operator<<(ostream &o, const tb_switch& node)
  {
    o << "tb_switch: " << &node << endl;
    o << "  mate=" << node.mate << endl;
    return o;
  }
343

344 345 346
  tb_switch() {;}
  pvertex mate;			// match in PG
};
Mac Newbold's avatar
Mac Newbold committed
347

348
// Hasher for pairs
349
template <class T> struct pairhash {
350
    size_t operator()(pair<T,T> const &A) const {
351 352
#ifdef NEW_GCC
	__gnu_cxx::hash<T> H;
353
#elif ! defined __clang__
354
        ::hash<T> H;
355 356
#else
	std::hash<T> H;
357
#endif
358 359
	return (H(A.first) | H(A.second));
    }
360
};
361

362 363
typedef pair<fstring,fstring> nodepair;
typedef hash_map<nodepair,int,pairhash<fstring> > nodepair_count_map;
364

Mac Newbold's avatar
Mac Newbold committed
365 366
class tb_plink {
public:
367
  typedef enum {PLINK_NORMAL,PLINK_INTERSWITCH,PLINK_LAN} plinkType;
368
  typedef hash_set<fstring> type_set;
369

370 371
  tb_plink(fstring _name, plinkType _is_type, fstring _type, fstring _srcnode, fstring _srcmac,
         fstring _srciface, fstring _dstnode,  fstring _dstmac, fstring _dstiface)
372
    : name(_name), srcmac(_srcmac), dstmac(_dstmac), is_type(_is_type),
373
      srciface(_srciface), dstiface(_dstiface),
374
      srcnode(_srcnode), dstnode(_dstnode),
375 376
      delay_info(), bw_used(0), emulated(0), nonemulated(0),
      penalty(0.0), fixends(false), current_endpoints(), current_count(0),
377 378 379
      vedge_counts() {
	  types.insert(_type);
      }
380

381
  fstring name;			// the name
382
  fstring srcnode,dstnode;      // source and destination node names
383 384
  fstring srcmac,dstmac;	// source and destination MAC addresses.
  fstring srciface, dstiface;	// source and destination interface names
385

386 387
  plinkType is_type;		// inter-switch type of the link
  type_set types;		// type (ie. ethernet) of the link
388 389
  tb_delay_info delay_info;	// the delay characteristics of this link
  int bw_used;			// how much is used
390

391 392 393 394 395 396 397 398 399 400 401
  int emulated;			// number of emulated vlinks
  int nonemulated;		// number of nonemulated vlinks
  float penalty;		// penaly for bandwidth used

  bool fixends;                 // if using as a emulated link, fix endpoints
  nodepair current_endpoints;	// pnodes at the endpoints of the vlink using
  				// this plink
  int current_count;		// number of mapped vlinks that share these
				// pnode endpoints
  nodepair_count_map vedge_counts; // list, and count, of all pairs of pnode
				   // endpoints sharing this link
402 403 404 405 406

  bool has_type(fstring type) const {	// Returns true if the given type is one
				        // of the types supported by this link
    return(types.find(type) != types.end());
  }
407

408 409 410
  friend ostream &operator<<(ostream &o, const tb_plink& link)
  {
    o << "tb_plink: " << link.name << " (" << &link << ")" << endl;
411 412 413 414 415
    o << "  types=";
    for (type_set::iterator it = link.types.begin();
	 it != link.types.end();
	 it++) {
	o << *it << " ";
416
    }
417 418 419 420 421 422 423 424 425 426 427 428
    o << endl;
    o << "  interswitch type: ";
      switch (link.is_type) {
	  case tb_plink::PLINK_NORMAL:
	      o << "normal" << endl;
	      break;
	  case tb_plink::PLINK_INTERSWITCH:
	      o << "interswitch" << endl;
	      break;
	  case tb_plink::PLINK_LAN:
	      o << "lan" << endl;
	      break;
429
      }
430 431 432 433 434 435 436
    o << "  bw_used=" << link.bw_used <<
      " srcmac=" << link.srcmac << " dstmac=" << link.dstmac <<
      " emulated=" << link.emulated << " nonemulated=" <<
      link.nonemulated << endl;
    o << link.delay_info;
    return o;
  }
437 438 439 440 441 442

  // Return true if the two plinks are equivalent, in terms of type and
  // bandwidth.
  // NOTE: should probably use a helper function in delay_info, but right now,
  // we only care about bandwidth
  const bool is_equiv(const tb_plink& link) {
443
#ifdef PCLASS_DEBUG_TONS
444
      cerr << "        Comparing " << delay_info.bandwidth
445 446 447 448 449 450
          << " and " << link.delay_info.bandwidth << endl;
#endif
      if (types != link.types) {
#ifdef PCLASS_DEBUG_TONS
          cerr << "            No, types" << endl;
#endif
451 452 453
	  return false;
      }
      if (delay_info.bandwidth != link.delay_info.bandwidth) {
454 455 456
#ifdef PCLASS_DEBUG_TONS
          cerr << "            No, bandwidth" << endl;
#endif
457 458 459
	  return false;
      }

460 461 462
#ifdef PCLASS_DEBUG_TONS
          cerr << "            Yes" << endl;
#endif
463 464
      return true;
  }
Mac Newbold's avatar
Mac Newbold committed
465 466
};

467
class tb_slink {
Mac Newbold's avatar
Mac Newbold committed
468
public:
469
  tb_slink() {;}
470 471 472 473 474 475 476 477

  friend ostream &operator<<(ostream &o, const tb_slink &link)
  {
    o << "tb_slink: " << &link << endl;
    o << "  mate=" << link.mate << endl;
    return o;
  }
  pedge mate;			// match in PG
Mac Newbold's avatar
Mac Newbold committed
478 479
};

480
int parse_ptop(tb_pgraph &PG, tb_sgraph &SG, istream& i);
Mac Newbold's avatar
Mac Newbold committed
481

482 483 484 485 486 487 488
/*
 * Globals
 */

/* The physical graph, defined in assign.cc */
extern tb_pgraph PG;

489
/* A map of all tb_ptypes currently in existance */
490
typedef map<fstring,tb_ptype*> tb_ptype_map;
491 492
extern tb_ptype_map ptypes;

Mac Newbold's avatar
Mac Newbold committed
493
#endif