virtual.h 6.41 KB
Newer Older
Robert Ricci's avatar
Robert Ricci committed
1 2
/*
 * EMULAB-COPYRIGHT
3
 * Copyright (c) 2000-2006 University of Utah and the Flux Group.
Robert Ricci's avatar
Robert Ricci committed
4 5 6
 * All rights reserved.
 */

Mac Newbold's avatar
Mac Newbold committed
7 8 9
#ifndef __VIRTUAL_H
#define __VIRTUAL_H

10 11 12 13 14
/*
 * We have to do these includes differently depending on which version of gcc
 * we're compiling with
 */
#if __GNUC__ == 3 && __GNUC_MINOR__ > 0
15 16
#include <queue>
using namespace std;
17 18 19 20 21 22 23 24
#else
#include <queue>
#endif

#include <vector>
#include <list>
using namespace std;

25
#include "featuredesire.h"
26 27 28 29 30 31 32 33
#include "fstring.h"

#include <boost/config.hpp>
#include <boost/utility.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

class tb_plink;
class tb_vnode;
class tb_vlink;
class tb_vclass;

typedef property<vertex_data_t,tb_vnode*> VNodeProperty;
typedef property<edge_data_t,tb_vlink*> VEdgeProperty;

typedef adjacency_list<listS,listS,undirectedS,
  VNodeProperty,VEdgeProperty> tb_vgraph;

typedef property_map<tb_vgraph,vertex_data_t>::type tb_vgraph_vertex_pmap;
typedef property_map<tb_vgraph,edge_data_t>::type tb_vgraph_edge_pmap;

typedef graph_traits<tb_vgraph>::vertex_descriptor vvertex;
typedef graph_traits<tb_vgraph>::edge_descriptor vedge;

typedef graph_traits<tb_vgraph>::vertex_iterator vvertex_iterator;
typedef graph_traits<tb_vgraph>::edge_iterator vedge_iterator;
typedef graph_traits<tb_vgraph>::out_edge_iterator voedge_iterator;

56

57 58
class tb_link_info {
public:
59
  typedef enum {LINK_UNMAPPED, LINK_DIRECT,
60 61
		LINK_INTRASWITCH, LINK_INTERSWITCH,
		LINK_TRIVIAL, LINK_DELAYED} linkType;
62 63
  linkType type_used;		// type of physical link used to satisfy this
  				// virtual link
64 65 66
  pedge_path plinks;		// the path of pedges
  pvertex_list switches;	// what switches were used

67 68 69 70 71
  tb_link_info() { ; };
  tb_link_info(linkType _type_used) : type_used(_type_used), plinks(), switches() { ; };
  tb_link_info(linkType _type_used, pedge_path _plinks) : type_used(_type_used), plinks(_plinks), switches() { ; };
  tb_link_info(linkType _type_used, pedge_path _plinks, pvertex_list _switches) : type_used(_type_used), plinks(_plinks), switches(_switches) { ; };
  
72 73 74
  friend ostream &operator<<(ostream &o, const tb_link_info& link)
  {
    o << "  Type: ";
75 76
    switch (link.type_used) {
    case LINK_UNMAPPED : o << "LINK_UNMAPPED"; break;
77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
    case LINK_DIRECT : o << "LINK_DIRECT"; break;
    case LINK_INTRASWITCH : o << "LINK_INTRASWITCH"; break;
    case LINK_INTERSWITCH : o << "LINK_INTERSWITCH"; break;
    case LINK_TRIVIAL : o << "LINK_TRIVIAL"; break;
    }
    o << " Path: ";
    for (pedge_path::const_iterator it=link.plinks.begin();
	 it!=link.plinks.end();it++) {
      o << *it << " ";
    }
    o << " Switches: ";
    for (pvertex_list::const_iterator it=link.switches.begin();
	 it!=link.switches.end();it++) {
      o << *it << " ";
    }
    o << endl;
    return o;
  }
};

Mac Newbold's avatar
Mac Newbold committed
97 98
class tb_vnode {
public:
99
  tb_vnode(): vclass(NULL), fixed(false), assigned(false), subnode_of(NULL),
100
      subnode_of_name(""), typecount(1) {;}
101

Mac Newbold's avatar
Mac Newbold committed
102
  friend ostream &operator<<(ostream &o, const tb_vnode& node)
103 104
  {
    o << "tb_vnode: " << node.name << " (" << &node << ")" << endl;
105
    o << "  Type: " << node.type <<  " Count: " << node.typecount << endl;
106
    o << "  Desires:" << endl;
107
    for (node_desire_set::const_iterator it = node.desires.begin();
108
	 it!=node.desires.end();it++) 
109
      o << "    " << it->name() << " -> " << it->cost() << endl;
110 111 112 113 114 115
    o << " vclass=" << node.vclass << " fixed=" <<
      node.fixed << endl;
    return o;
  }

  // contains weight of each desire
116
  node_desire_set desires;
Mac Newbold's avatar
Mac Newbold committed
117

118
  fstring type;			// the current type of the node
119
  int typecount;		// How many slots of the type this vnode takes up
120
  tb_vclass *vclass;		// the virtual class of the node, if any
121
  fstring name;			// string name of the node
122
  bool fixed;			// is this node fixed
123 124
  bool assigned;		// is this node assigned?
  pvertex assignment;		// the physical vertex assigned to
Mac Newbold's avatar
Mac Newbold committed
125

126 127
#ifdef PER_VNODE_TT
  int num_links;
128
  int total_bandwidth;
129
#endif
Mac Newbold's avatar
Mac Newbold committed
130

131 132 133 134 135 136
  // For the case where we want to make sure that a vnode has all trivial
  // links, or no trivial links, but not a mix of both.
  bool disallow_trivial_mix;
  int nontrivial_links;
  int trivial_links;

137 138 139 140 141 142
  // For the subnode-of relationship - we need to keep track of not only our
  // own parent (if any), but any children we have, since our being assigned
  // will mean that we have to check them as well
  tb_vnode *subnode_of;
  typedef list<tb_vnode*> subnode_list;
  subnode_list subnodes;
143
  fstring subnode_of_name;
144

145
  // Counts how many links of each type this virtual node has
146
  typedef hash_map<fstring,int> link_counts_map;
147 148
  link_counts_map link_counts;

149
};
Mac Newbold's avatar
Mac Newbold committed
150 151 152 153

class tb_vlink {
public:
  tb_vlink() {;}
154 155 156 157 158 159 160 161 162 163 164 165 166

  friend ostream &operator<<(ostream &o, const tb_vlink& link)
  {
    o << "tb_vnode: " << link.name << " (" << &link << ")" << endl;
    o << " emulated=" << link.emulated << " allow_delayed=" <<
      link.allow_delayed << " no_connection=" << link.no_connection << endl;
    o << "delay_info: " << link.delay_info;
    o << link.link_info;
    return o;
  }

  tb_delay_info delay_info;	// the delay characteristics of the link
  tb_link_info link_info;	// what it's mapped to
167 168 169 170 171 172 173
  fstring name;			// name
  fstring type;			// type of this link
  bool fix_src_iface;		// Did the user fix the name of the iface (src)?
  fstring src_iface;		// If so, this is what it must be named
  bool fix_dst_iface;		// Did the user fix the name of the iface (dst)?
  fstring dst_iface;		// If so, this is what it must be named

174 175
  bool emulated;		// is this an emulated link, i.e. can it
				// share a plink withouter emulated vlinks
176 177 178
  bool no_connection;		// true if this link should be satisfied
				// but isn't.
  bool allow_delayed;		// can this vlink by a delayed link
179
  bool allow_trivial;           // can this vlink be a trivial link?
180
  vvertex src, dst;		// Source and destination for this link
Mac Newbold's avatar
Mac Newbold committed
181 182
};

183 184 185
extern tb_vgraph_vertex_pmap vvertex_pmap;
extern tb_vgraph_edge_pmap vedge_pmap;

186
typedef hash_map<fstring,vvertex> name_vvertex_map;
187 188 189 190 191 192 193 194 195 196 197 198 199 200
typedef pair<vvertex,int> vvertex_int_pair;
typedef vector<vvertex> vvertex_vector;

struct ltnodepq {
  bool operator()(const vvertex_int_pair &A,const vvertex_int_pair &B) const {
    return A.second < B.second;
  };
};

typedef priority_queue<vvertex_int_pair,
  vector<vvertex_int_pair>, ltnodepq> vvertex_int_priority_queue;
typedef list<vvertex> vvertex_list;

int parse_top(tb_vgraph &G, istream& i);
Mac Newbold's avatar
Mac Newbold committed
201

202 203 204 205 206 207 208
/*
 * Globals
 */

/* The virtual graph, defined in assign.cc */
extern tb_vgraph VG;

Mac Newbold's avatar
Mac Newbold committed
209
#endif
210 211