assign.cc 36.8 KB
Newer Older
Robert Ricci's avatar
Robert Ricci committed
1 2
/*
 * EMULAB-COPYRIGHT
Mike Hibler's avatar
Mike Hibler committed
3
 * Copyright (c) 2000-2010 University of Utah and the Flux Group.
Robert Ricci's avatar
Robert Ricci committed
4 5 6
 * All rights reserved.
 */

7 8 9 10 11 12 13 14
#include "port.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>
#include <boost/graph/dijkstra_shortest_paths.hpp>
15
#ifdef GRAPHVIZ_SUPPORT
16
#include <boost/graph/graphviz.hpp>
17
#endif
18

19 20
#include <fstream>
#include <iostream>
21
#include <time.h>
Mac Newbold's avatar
Mac Newbold committed
22
#include <stdlib.h>
23
#include <math.h>
Mac Newbold's avatar
Mac Newbold committed
24 25
#include <sys/types.h>
#include <sys/time.h>
26
#include <sys/resource.h>
27 28
#include <signal.h>
#include <sys/signal.h>
29
#include <queue>
30
#include <algorithm>
31 32

using namespace boost;
Mac Newbold's avatar
Mac Newbold committed
33

34 35
#include <stdio.h>

Mac Newbold's avatar
Mac Newbold committed
36
#include "common.h"
37
#include "delay.h"
Mac Newbold's avatar
Mac Newbold committed
38
#include "physical.h"
39
#include "virtual.h"
40
#include "vclass.h"
41
#include "pclass.h"
42
#include "score.h"
43 44 45
#include "solution.h"
#include "maps.h"
#include "anneal.h"
46 47
#include "config.h"

48 49
#ifdef WITH_XML
#include "parse_ptop_xml.h"
50 51 52
#include "parse_vtop_xml.h"
#include "parse_advertisement_rspec.h"
#include "parse_request_rspec.h"
53
#endif
54 55 56

// Here we set up all our graphs.  Need to create the graphs
// themselves and then setup the property maps.
57
tb_pgraph PG;
58 59 60 61 62 63 64 65 66 67
tb_pgraph_vertex_pmap pvertex_pmap = get(vertex_data, PG);
tb_pgraph_edge_pmap pedge_pmap = get(edge_data, PG);
tb_sgraph SG;
tb_sgraph_vertex_pmap svertex_pmap = get(vertex_data, SG);
tb_sgraph_edge_pmap sedge_pmap = get(edge_data, SG);
tb_vgraph VG;
tb_vgraph_vertex_pmap vvertex_pmap = get(vertex_data, VG);
tb_vgraph_edge_pmap vedge_pmap = get(edge_data, VG);

// List of virtual types by name.
68
name_count_map vtypes;
69
name_list_map vclasses;
70 71

// A list of all pclasses.
72
pclass_list pclasses;
73 74 75
 	
// Map from a pnode* to the the corresponding pvertex.
pnode_pvertex_map pnode2vertex;
76 77 78

// Map of a type to a tt_entry, a vector of pclasses and the size of
// the vector.
79
pclass_types type_table;
80 81 82
#ifdef PER_VNODE_TT
pclass_types vnode_type_table;
#endif
83

84 85 86 87 88
// This datastructure contains all the information needed to calculate
// the shortest path between any two switches.  Indexed by svertex,
// the value will be a predicate map (indexed by svertex as well) of
// the shortest paths for the given vertex.
switch_pred_map_map switch_preds;
89

90 91
// Same, but for distances 
switch_dist_map_map switch_dist;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
92

93 94
// Time started, finished, and the time limit
double timestart, timeend, timelimit, timetarget;
95

96 97 98
// An amount to scale the neighborhood size by
double scale_neighborhood = 1.0;

99 100 101 102 103
#ifdef GNUPLOT_OUTPUT
FILE *scoresout, *tempout, *deltaout;
#endif
// Whether or not assign is allowed to generate trivial links
bool allow_trivial_links = true;
104

105
// Whether or not assign should use pclasses
106
bool disable_pclasses = false;
107

Robert Ricci's avatar
Robert Ricci committed
108 109 110
// Whether or not assign should prune out pclasses that it knows can
// never be used
bool prune_pclasses = false;
111 112 113

// Whether or not we should use the experimental support for dynamic pclasses
bool dynamic_pclasses = false;
114 115 116

// Whether or not to allow assign to temporarily over-subscribe pnodes
bool allow_overload = false;
Robert Ricci's avatar
Robert Ricci committed
117 118 119 120

// Forces assign to do greedy link assignment, by chosing the first link in its
// list, which is usually the lowest-cost
bool greedy_link_assignment = false;
Robert Ricci's avatar
Robert Ricci committed
121 122 123 124 125

// Forces assign to skip melting, and, instead, use the temperature given as
// the initial temperature
bool no_melting = false;
double initial_temperature = 0.0f;
126 127 128 129 130 131

// Print out a summary of the solution in addition to the solution itself
bool print_summary = false;

// Use the 'connected' find algorithm
double use_connected_pnode_find = 0.0f;
132

133 134 135
// Whether or not to perform all checks on fixed nodes
bool check_fixed_nodes = false;

136 137 138
// If true, dump a bunch of configrution information
bool dump_config = false;

139
// Use XML for file input
140 141 142 143 144 145
// bool xml_input = false;
#ifdef WITH_XML
bool ptop_xml_input = false;
bool vtop_xml_input = false;
bool ptop_rspec_input = false;
bool vtop_rspec_input = false;
146
#endif
147

148 149 150 151 152 153 154 155 156 157 158 159 160
/*
 * Score and violations for the best score found so far
 * XXX - shouldn't be in this file
 */
double best_score;
int best_violated;

/*
 * Number of iterations executed so far, and how many it took us to find the
 * best solution
 * XXX - shouldn't be in this file
 */
int iters, iters_to_best;
Robert Ricci's avatar
Robert Ricci committed
161

162 163 164
// Map of all physical types in use in the system
tb_ptype_map ptypes;

165 166 167
/*
 * Internal functions
 */
Mac Newbold's avatar
Mac Newbold committed
168

Robert Ricci's avatar
Robert Ricci committed
169
// Return the CPU time (in seconds) used by this process
170
float used_time() {
171 172 173 174 175 176
  struct rusage ru;
  getrusage(RUSAGE_SELF,&ru);
  return ru.ru_utime.tv_sec+ru.ru_utime.tv_usec/1000000.0+
    ru.ru_stime.tv_sec+ru.ru_stime.tv_usec/1000000.0;
}

177 178 179 180 181 182 183 184 185 186 187 188
// Constructs the output file name for the annotated rspec
string annotated_filename (const char* filepath)
{
	string input_filepath = string(filepath);
	int pos_last_backslash = input_filepath.find_last_of("/");
	string input_filename = input_filepath.substr(pos_last_backslash+1, input_filepath.length()-pos_last_backslash-1);
	string output_filepath = input_filepath.substr(0, pos_last_backslash+1);
	output_filepath.append("annotated-");
	output_filepath.append(input_filename);
	return (output_filepath);
}

Robert Ricci's avatar
Robert Ricci committed
189
// Read in the .ptop file
190
void read_physical_topology(char *filename) {
191 192
  ifstream ptopfile;
  ptopfile.open(filename);
Robert Ricci's avatar
Robert Ricci committed
193
  if (!ptopfile.is_open()) {
194
      cout << "*** Unable to open ptop file " << filename << endl;
195
      exit(EXIT_FATAL);
Robert Ricci's avatar
Robert Ricci committed
196
  }
197 198
  
#ifdef WITH_XML
199
  if (ptop_xml_input) {
200 201 202 203
	cout << "Physical Graph: " << parse_ptop_xml(PG,SG,filename) << endl;
  } 
  else if (ptop_rspec_input) {
	cout << "Physical Graph: " << parse_advertisement(PG, SG, filename) << endl;
204 205
	}
	else {
206 207 208
      cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;
  }
#else
209
	cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;
210
#endif
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232

#ifdef DUMP_GRAPH
  {
    cout << "Physical Graph:" << endl;
    
    pvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(PG);
    
    for (;vit != vendit;vit++) {
      tb_pnode *p = get(pvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    pedge_iterator eit,eendit;
    tie(eit,eendit) = edges(PG);

    for (;eit != eendit;eit++) {
      tb_plink *p = get(pedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,PG) << " <-> " <<
	target(*eit,PG) << ")\t" << *p;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
233
#endif // DUMP_GRAPH
234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256

#ifdef GRAPH_DEBUG
  {
    cout << "Switch Graph:" << endl;
    

    svertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(SG);
    
    for (;vit != vendit;vit++) {
      tb_switch *p = get(svertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    sedge_iterator eit,eendit;
    tie(eit,eendit) = edges(SG);

    for (;eit != eendit;eit++) {
      tb_slink *p = get(sedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,SG) << " <-> " <<
	target(*eit,SG) << ")\t" << *p;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
257
#endif // GRAPH_DEBUG
258

Robert Ricci's avatar
Robert Ricci committed
259 260
  // Set up pnode2vertex - a mapping between vertices in the physical graph and
  // the pnodes that we just read in from the ptop file
261 262 263 264 265 266 267 268
  pvertex_iterator pvit,pvendit;
  tie(pvit,pvendit) = vertices(PG);
  for (;pvit != pvendit;pvit++) {
    pnode2vertex[get(pvertex_pmap,*pvit)]=*pvit;
  }

}

Robert Ricci's avatar
Robert Ricci committed
269 270
// Calculate the minimum spanning tree for the switches - we only consider one
// potential path between each pair of switches.
271
// XXX: Should soon be replaced by calculate_shortest_routes()
272
void calculate_switch_MST() {
273
  cout << "Calculating shortest paths on switch fabric." << endl;
Robert Ricci's avatar
Robert Ricci committed
274 275

  // Set up the weight map for Dijkstra's
276 277 278 279 280 281 282 283 284 285
  tb_sgraph_weight_pmap sweight_pmap = get(edge_weight, SG);
  sedge_iterator seit,seendit;
  tie(seit,seendit) = edges(SG);
  for (;seit != seendit;seit++) {
    tb_slink *slink = get(sedge_pmap,*seit);
    // XXX should we make this more complicated depending on
    // latency/loss as well?
    put(sweight_pmap,*seit,
	100000000-get(pedge_pmap,slink->mate)->delay_info.bandwidth);
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
286

Robert Ricci's avatar
Robert Ricci committed
287
  // Let boost do the Disjktra's for us, from each switch
288 289 290 291 292 293 294 295
  svertex_iterator svit,svendit;
  tie(svit,svendit) = vertices(SG);
  for (;svit != svendit;svit++) {
    switch_preds[*svit] = new switch_pred_map(num_vertices(SG));
    switch_dist[*svit] = new switch_dist_map(num_vertices(SG));
    dijkstra_shortest_paths(SG,*svit,
    			    predecessor_map(&((*switch_preds[*svit])[0])).
			    distance_map(&((*switch_dist[*svit])[0])));
Christopher Alfeld's avatar
 
Christopher Alfeld committed
296 297
  }

298 299 300 301 302 303 304 305 306
#ifdef GRAPH_DEBUG
  cout << "Shortest paths" << endl;
  tie(svit,svendit) = vertices(SG);
  for (;svit != svendit;svit++) {
    cout << *svit << ":" << endl;
    for (unsigned int i = 0;i<num_vertices(SG);++i) {
      cout << i << " " << (*switch_dist[*svit])[i] << endl;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
307
#endif // GRAPH_DEBUG
308 309
}

Robert Ricci's avatar
Robert Ricci committed
310
// Read in the .top file
311
void read_virtual_topology(char *filename) {
312 313
  ifstream topfile;
  topfile.open(filename);
Robert Ricci's avatar
Robert Ricci committed
314
  if (!topfile.is_open()) {
315
      cout << "*** Unable to open top file " << filename << endl;
316
      exit(EXIT_FATAL);
Robert Ricci's avatar
Robert Ricci committed
317
  }
318
  
319 320 321 322 323
#ifdef WITH_XML  
  if (vtop_xml_input) {
	cout << "Virtual Graph: " << parse_vtop_xml(VG,filename) << endl;
  }
  else if (vtop_rspec_input){
324
  	  cout << "Virtual Graph: " << parse_request (VG, filename) << endl;
325 326
  }
  else {
327 328 329
      cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;
  }
#else
330
	cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;
331
#endif
332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356

#ifdef DUMP_GRAPH
  {
    cout << "Virtual Graph:" << endl;
    

    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
    
    for (;vit != vendit;vit++) {
      tb_vnode *p = get(vvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    vedge_iterator eit,eendit;
    tie(eit,eendit) = edges(VG);

    for (;eit != eendit;eit++) {
      tb_vlink *p = get(vedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,VG) << " <-> " <<
	target(*eit,VG) << ")\t" << *p;
    }
  }  
#endif
}
Robert Ricci's avatar
Robert Ricci committed
357 358 359 360 361 362 363 364 365 366
/*
 * Make a pass through the pclasses, looking for ones that no node can use, and
 * nuking them.
 */
void prune_unusable_pclasses() {
    cout << "Pruning pclasses." << endl;
    int pruned = 0;
    pclass_list::iterator pclass_iterator = pclasses.begin();
    while (pclass_iterator != pclasses.end()) {
	if ((*pclass_iterator)->refcount == 0) {
367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384
            /*
             * Remove the nodes in the pclass we're removing from the slot
             * counts for their ptypes
             */
            tb_pclass::pclass_members_map::iterator ptype_iterator;
            ptype_iterator = (*pclass_iterator)->members.begin();
            while (ptype_iterator != (*pclass_iterator)->members.end()) {
                /*
                 * Find the recort for this type in the ptypes structure
                 */
                fstring this_type = ptype_iterator->first;
                tb_ptype_map::iterator ptype = ptypes.find(this_type);
                assert(ptype != ptypes.end());
                tb_ptype *this_type_p = ptype->second;

                /*
                 * For every node with this type, we want to remove its slot
                 * count from the total slot count for the type, since we know
385 386 387
                 * we will never use this particular node.
                 * Note: We only have to do this for pclasses that are "real",
                 * not dynamic ones.
388
                 */
389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410
                if (!(*pclass_iterator)->is_dynamic) {
                    tb_pnodelist::list_iter pnode_iterator =
                        ptype_iterator->second->L.begin();
                    while (pnode_iterator != ptype_iterator->second->L.end()) {
                        /*
                         * Get the slotcount for this ptype
                         */
                        tb_pnode::types_map::iterator tm_iterator;
                        tm_iterator = (*pnode_iterator)->types.find(this_type);
                        assert(tm_iterator != (*pnode_iterator)->types.end());

                        /*
                         * Remove it from the current ptype
                         */
                        this_type_p->remove_slots(
                                tm_iterator->second->get_max_load());

                        /*
                         * Move on to the next node
                         */
                        pnode_iterator++;
                    }
411 412 413 414
                }
                ptype_iterator++;
            }

Robert Ricci's avatar
Robert Ricci committed
415 416 417 418 419 420
	    pclass_list::iterator nukeme = pclass_iterator;
	    pclass_iterator++;
#ifdef PCLASS_DEBUG
	    cout << "Pruning " << (*nukeme)->name << endl;
#endif
	    pruned++;
421

Robert Ricci's avatar
Robert Ricci committed
422 423 424 425 426 427 428 429 430 431
	    delete *nukeme;
	    pclasses.erase(nukeme);
	} else {
	    pclass_iterator++;
	}
    }
    cout << "pclass pruning complete: removed " << pruned << " pclasses, " <<
	pclasses.size() << " remain." << endl;
}

432
void print_help() {
433
  cout << "assign [options] ptopfile topfile [cparams]" << endl;
434
  cout << "Options: " << endl;
435
#ifdef TIME_TERMINATE
436
  cout << "  -l <time>   - Limit runtime." << endl;
Mac Newbold's avatar
Mac Newbold committed
437
#endif
438
  cout << "  -s <seed>   - Set the seed." << endl;
439
#ifdef GRAPHVIZ_SUPPORT
440
  cout << "  -v <viz>    - Produce graphviz files with given prefix." <<
441
    endl;
442
#endif
443 444 445
  cout << "  -r          - Don't allow trivial links." << endl;
  cout << "  -p          - Disable pclasses." << endl;
  cout << "  -d          - Enable dynamic pclasses." << endl;
446
#ifdef PER_VNODE_TT
447
  cout << "  -P          - Prune unusable pclasses." << endl;
448
#endif
449 450 451
  cout << "  -T          - Doing some scoring self-testing." << endl;
  cout << "  -H <float>  - Try <float> times harder." << endl;
  cout << "  -o          - Allow overloaded pnodes to be considered." << endl;
Robert Ricci's avatar
Robert Ricci committed
452 453
  cout << "  -t <float>  - Start the temperature at <float> instead of melting."
      << endl;
454 455
  cout << "  -u           - Print a summary of the solution." << endl;
  cout << "  -c <float>   - Use the 'connected' pnode finding algorithm ";
456 457
  cout <<                   "<float>*100%" << endl;
  cout << "                 of the time." << endl;
458 459 460 461
  cout << "  -n           - Don't anneal - just do the prechecks." << endl;

  cout << "  -x <file>    - Specify a text ptop file" << endl;
  cout << "  -y <file>    - Specify a text top file" << endl;
462
#ifdef WITH_XML
463
  cout << "  -W <file>    - Specify the output rspec file" << endl;
464 465 466
  cout << "  -f <T>[/<T>] - Specify the ptop/vtop file formats " << endl;
  cout << "                 T should be one of (text|xml|rspec)" << endl;
  cout << "                 Specifying only one T is equivalent to -f T/T"<<endl;
467
#endif
468 469 470 471 472
  cout << "  -F          - Apply additional checking to fixed nodes" << endl;
  cout << "  -D          - Dump configuration options" << endl;
  cout << "  cparams     - You probably don't want to touch these!" << endl;
  cout << "                If you must, see config.h in the source for a list"
       << endl;
473
  exit(EXIT_FATAL);
474 475 476 477 478
}
 
// Perfrom a pre-cehck to make sure that there are enough free nodes of the
// proper types. Returns 1 if the proper types exist, 0 if they do not.
// TODO - move away from using global variables
479
int type_precheck(int round) {
480
    cout << "Type precheck:" << endl;
481

482
    bool ok = true;
Mac Newbold's avatar
Mac Newbold committed
483

484 485 486 487 488 489 490 491 492 493 494
    /*
     * Tailor our error messages, depending on the round - the first round of
     * the precheck is looking for available pnodes, the second is looking for
     * sutiable nodes (ie. at least one vnode could map to it)
     */
    char *round_str;
    if (round == 1) {
        round_str = "available";
    } else {
        round_str = "suitable";
    }
495
    // First, check the regular types
496 497
    for (name_count_map::iterator vtype_it=vtypes.begin();
	    vtype_it != vtypes.end();++vtype_it) {
498

499
	// Check to see if there were any pnodes of the type at all
500
	tb_ptype_map::iterator ptype_it = ptypes.find(vtype_it->first);
501
	if (ptype_it == ptypes.end()) {
502
	    cout << "  *** No " << round_str << " physical nodes of type "
503 504
                << vtype_it->first << " found (" << vtype_it->second
                << " requested)" << endl;
505
	    ok = false;
506
	} else {
507
	    // Okay, there are some - are there enough?
508
	    if (ptype_it->second->pnode_slots() < vtype_it->second) {
509
		cout << "  *** " << vtype_it->second << " nodes of type " <<
510 511 512
                    vtype_it->first << " requested, but only " <<
                    ptype_it->second->pnode_slots() << " " << round_str <<
                    " nodes of type " << vtype_it->first<< " found" << endl;
513 514 515 516 517 518 519 520
		ok = false;
	    }
	    // Okay, there are enough - but are we allowed to use them?
	    if (ptype_it->second->maxusers() &&
		    (ptype_it->second->maxusers() < vtype_it->second)) {
		cout << "  *** " << vtype_it->second << " nodes of type " <<
		    vtype_it->first << " requested, but you are only " <<
		    "allowed to use " << ptype_it->second->maxusers() << endl;
521 522
		ok = false;
	    }
523
	}
524
    }
525 526 527 528

    // Check the vclasses, too
    for (name_list_map::iterator vclass_it = vclasses.begin();
	    vclass_it != vclasses.end(); ++vclass_it) {
529
	bool found_match = false;
530
        // Make sure we actually use this vclass
531
        name_vclass_map::iterator dit = vclass_map.find(vclass_it->first);
532 533 534 535 536 537 538 539 540 541 542
        if (dit == vclass_map.end()) {
            cout << "***: Internal error - unable to find vtype " <<
                vclass_it->first << endl;
            exit(EXIT_FATAL);
        } else {
            if (dit->second->empty()) {
                // Nobody uses it, don't check
                continue;
            }
        }

543
	for (vector<fstring>::iterator vtype_it = vclass_it->second.begin();
544
		vtype_it != vclass_it->second.end(); vtype_it++) {
545 546
	    tb_ptype_map::iterator mit = ptypes.find(*vtype_it);
	    if ((mit != ptypes.end()) && (mit->second->pnode_slots() != 0)) {
547 548 549 550 551 552
		found_match = true;
		break;
	    }
	}

	if (!found_match) {
553 554
	    cout << "  *** No " << round_str <<
                " physical nodes can satisfy vclass " << vclass_it->first << endl;
555 556 557 558
	    ok = false;
	}
    }

559
    if (ok) {
560
      cout << "Type precheck passed." << endl;
561 562
      return 1;
    } else {
563
      cout << "*** Type precheck failed!" << endl;
564 565 566
      return 0;
    }
}
567

568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583
// Perfrom a pre-cehck to make sure that every vnode has at least one possible
// mapping.  Returns 1 if this is the case, 0 if not.
// TODO - move away from using global variables
int mapping_precheck() {
#ifdef PER_VNODE_TT
    cout << "Node mapping precheck:" << endl;
    /*
     * Build up an entry in the type table for each vnode, by first looking at
     * the type table entry for the vnode's type, then checking each entry to
     * make sure that it:
     * (1) Has enough interfaces
     * (2) Has enough total bandwidth (for emulated links)
     * (3) Meets any 1.0-weight features and/or desires
     */
    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
584

585 586 587 588
    /*
     * Indicates whether all nodes have potential matches or not
     */
    bool ok = true;
589

590 591
    for (;vit != vendit;vit++) {
	tb_vnode *v = get(vvertex_pmap,*vit);
592

593 594 595
	pclass_vector *vec = new pclass_vector();
	vnode_type_table[v->name] = tt_entry(0,vec);

596 597 598 599
	// Remember if there are no nodes of the requested type in the physical
	// topology. Without this diagnostic, our "guess what's wrong with
	// the vnode" code concludes that there was not enough bandwidth.
	bool matched_node_type = true;
600 601 602 603 604
	// This constitutes a list of the number of ptypes that matched the
	// criteria. We use to guess what's wrong with the vnode.
	int matched_bw = 0;
	// Keep track of desires had how many 'hits', so that we can tell
	// if any simply were not matched
605
	map<fstring,int> matched_desires;
606

607 608 609
	// Keep track of which link types had how many 'hits', so that we can
	// tell which type(s) caused this node to fail
	tb_vnode::link_counts_map matched_link_counts;
610 611
        hash_map<fstring,int> max_links;
        hash_map<fstring,int> desired_links;
612
	map<fstring,bool> matched_links;
613

614
	tb_vclass *vclass = v->vclass;
615
	tb_vclass::members_map::const_iterator mit;
616
	if (vclass) {
617
	    mit = vclass->get_members().begin();
618
	}
619 620 621
	for (;;) {
	    // Loop over all types this node can take on, which might be only
	    // one, if it's not part of a vclass
622
	    fstring this_type;
623 624 625 626 627
	    if (vclass) {
		this_type = mit->first;
	    } else {
		this_type = v->type;
	    }
628

629 630 631
            // Check to make sure there are actually nodes of this type in the
            // physical topology
            if (type_table.find(this_type) == type_table.end()) {
632
                matched_node_type = false;
633 634 635 636 637
                // Yes, I know, goto is evil. But I'm not gonna indent the next
                // 100 lines of code for this error case
                goto nosuchtype;
            }

638 639
	    for (pclass_vector::iterator it = type_table[this_type].second->begin();
		    it != type_table[this_type].second->end(); it++) {
640

641 642
		bool potential_match = true;
		// Grab the first node of the pclass as a representative sample
643
	 	tb_pnode *pnode = *((*it)->members[this_type]->L.begin());
644 645 646

		// Check to see if any of the link that this pnode has are of
		// the correct type for the virtual node
Mac Newbold's avatar
Mac Newbold committed
647

648 649 650 651
		// Check bandwidth on emulated links
		if (pnode->total_bandwidth >= v->total_bandwidth) {
		    matched_bw++;
		} else {
652
			potential_match = false;
653
		}
Mac Newbold's avatar
Mac Newbold committed
654

655 656
		// Check to see if if the pnode has enough slots of the
		// appropriate type available
657 658 659
		tb_pnode::types_map::iterator type_iterator =
		    pnode->types.find(v->type);
		if (type_iterator == pnode->types.end()) {
660 661
		    // Must have been a vtype to get here - ignore it
		} else {
662
		    if (v->typecount > type_iterator->second->get_max_load()) {
663 664 665 666 667
			// Nope, this vnode is too demanding
			potential_match = false;
		    }
		}

668 669 670 671 672 673 674
		/*
		 * Check features and desires
		*/
		tb_featuredesire_set_iterator
		    fdit(v->desires.begin(),v->desires.end(),
			 pnode->features.begin(),pnode->features.end());
		for (;!fdit.done();fdit++) {
675
		    // Skip 'local' and 'global' features
676
		    if (fdit->is_global() || fdit->is_local()) {
677 678
			continue;
		    }
679 680 681
		    // Only check for FDs that would result in a violation if
		    // unmatched.
		    if (fdit.either_violateable()) {
682 683 684 685 686
			if (fdit.membership() !=
				tb_featuredesire_set_iterator::BOTH) {
			    potential_match = false;
			}

687 688
			// We look for violateable desires on vnodes so that we
			// can report them to the user
689 690 691 692 693 694 695 696 697
			if ((fdit.membership() ==
				tb_featuredesire_set_iterator::FIRST_ONLY ||
			    fdit.membership() ==
				 tb_featuredesire_set_iterator::BOTH)
				&& fdit.first_iterator()->is_violateable()) {
			    if (matched_desires.find(fdit->name()) ==
				    matched_desires.end()) {
				matched_desires[fdit->name()] = 0;
			    }
698 699 700 701
			}
			if (fdit.membership() ==
				tb_featuredesire_set_iterator::BOTH) {
			    matched_desires[fdit->name()]++;
702 703 704
			}
		    }
		}
705
		
706 707 708 709 710 711
		// Check link types - right now, we treat LANs specially, which
                // I am not happy about, but it seems to be necessary.
                // Otherwise, we can get a false negative when there are few
                // ports on a switch available, but we could map by using
                // the trunk links
                if (this_type != "lan") {
712 713 714 715 716 717
                  tb_vnode::link_counts_map::iterator link_it;
                  for (link_it = v->link_counts.begin();
		       link_it != v->link_counts.end();
                       link_it++) {
                    fstring type = link_it->first;
                    int count = link_it->second;
718
                    desired_links[type] = count;
719 720 721 722
                    if (pnode->link_counts.find(type) !=
                          pnode->link_counts.end()) {
                      // Found at least one link of this type
                      matched_links[type] = true;
723 724 725
                      if (pnode->link_counts[type] > max_links[type]) {
                        max_links[type] = pnode->link_counts[type];
                      }
726 727 728 729 730 731 732 733 734 735 736
                      if (pnode->link_counts[type] >= count) {
                        // Great, there are enough, too
                        matched_link_counts[type]++;
                      } else {
                        potential_match = false;
                      }
                    } else {
                      potential_match = false;
                    }
                  }
                }
Mac Newbold's avatar
Mac Newbold committed
737

738 739 740 741 742 743
		if (potential_match) {
		    vec->push_back(*it);
		    vnode_type_table[v->name].first++;
		    (*it)->refcount++;
#ifdef PCLASS_DEBUG
		    cerr << v->name << " can map to " << (*it)->name << endl;
744
#endif
745 746
		}
	    }
747

748
nosuchtype:
749 750
	    if (vclass) { 
		mit++;
751
		if (mit == vclass->get_members().end()) {
752 753 754 755 756 757
		    break;
		}
	    } else {
		// If not a vtype, we only had to do this once
		break;
	    }
758
	}
759

760
	if (vnode_type_table[v->name].first == 0) {
761
	    cout << "  *** No possible mapping for " << v->name << endl;
762
	    // Make an attempt to figure out why it didn't match
763 764 765 766 767
	    
	    // Check all of its link types
	    tb_vnode::link_counts_map::iterator lit;
	    for (lit = v->link_counts.begin(); lit != v->link_counts.end();
		lit++) {
768
	      fstring type = lit->first;
769
	      if (!matched_links[type]) {
770 771
		cout << "      No links of type " << type << " found! (" <<
                  desired_links[type] << " requested)" << endl;
772 773
	      } else {
		if (!matched_link_counts[type]) {
774 775 776
		  cout << "      Too many links of type " << type << "! (" <<
                    desired_links[type] << " requested, " << max_links[type] <<
                    " found)" << endl;
777 778
		}
	      }
779
	    }
780

781 782 783 784
	    if (!matched_node_type) {
		cout << "      No physical nodes of requested type '"
		     << v->type << "'!\n";
	    } else if (!matched_bw) {
785
		cout << "      Too much bandwidth on emulated links!" << endl;
786
	    }
787

788
	    for (map<fstring,int>::iterator dit = matched_desires.begin();
789 790 791
		    dit != matched_desires.end();
		    dit++) {
		if (dit->second == 0) {
792
		    cout << "      No physical nodes have feature " << dit->first
793 794
			<< "!" << endl;
		}
795
	    }
796
	    ok = false;
797
	}
798 799 800
#ifdef PCLASS_DEBUG
	cerr << v->name << " can map to " << vnode_type_table[v->name].first << " pclasses"
	    << endl;
801
#endif
802

803
    }
804

805 806 807
    if (ok) {
	cout << "Node mapping precheck succeeded" << endl;
	return 1;
808
    } else {
809
	cout << "*** Node mapping precheck failed!" << endl;
810
	return 0;
811 812
    }

813 814 815
#else // PER_VNODE_TT
    // PER_VNODE_TT is required for this check, just pretend it's OK.
    return 1;
Robert Ricci's avatar
Robert Ricci committed
816
#endif
817
}
Christopher Alfeld's avatar
 
Christopher Alfeld committed
818

819 820 821 822 823 824 825 826 827 828 829 830 831 832
// Perfrom a pre-cehck to make sure that polices that are checkable at precheck
// time are not violated. Returns 1 if everything is A-OK, 0 otherwise
// TODO - move away from using global variables
int policy_precheck() {
  cout << "Policy precheck:" << endl;
  if (tb_featuredesire::check_desire_policies()) {
    cout << "Policy precheck succeeded" << endl;
    return 1;
  } else {
    cout << "*** Policy precheck failed!" << endl;
    return 0;
  }
}  

833 834 835
// Signal handler - add a convneint way to kill assign and make it return an
// unretryable error
void exit_unretryable(int signal) {
836
  cout << "*** Killed with signal " << signal << " - exiting!" << endl;
837 838 839 840 841 842 843
  _exit(EXIT_UNRETRYABLE);
}

// Singal handler - add a way for a user to get some status information
extern double temp;
void status_report(int signal) {
  cout << "I: " << iters << " T: " << temp << " S: " << get_score() << " V: "
844
    << violated << " (Best S: " << best_score << " V:" << best_violated << ")"
845
    << endl;
846
  cout.flush();
847 848
}

849 850 851 852
// From anneal.cc - the best solution found
extern solution best_solution;

int main(int argc,char **argv) {
853
  int seed = 0;
854
#ifdef GRAPHVIZ_SUPPORT
855
  fstring viz_prefix;
856
#endif
857
  bool scoring_selftest = false;
858
  bool prechecks_only = false;
859 860 861 862 863
  
  // Handle command line
  char ch;
  timelimit = 0.0;
  timetarget = 0.0;
864 865 866
  
  char* ptopFilename = "";
  char* vtopFilename = "";
867 868
  char* vtopOutputFilename = 0;

869 870 871 872 873 874
#ifdef WITH_XML
	char* ptopFileFormat;
	char* vtopFileFormat;
	char* delims = "/";
	char* flags = "s:v:l:t:rpPTdH:oguc:nx:y:W:FDf:";
#else
Mike Hibler's avatar
Mike Hibler committed
875
	char* flags = "s:v:l:t:rpPTdH:oguc:nx:y:FD";
876 877 878
#endif	
	
  while ((ch = getopt(argc,argv,flags)) != -1) {
879 880 881
    switch (ch) {
    case 's':
      if (sscanf(optarg,"%d",&seed) != 1) {
882
		print_help();
883
      }
884
      break;
885
#ifdef GRAPHVIZ_SUPPORT
886 887 888
    case 'v':
      viz_prefix = optarg;
      break;
889
#endif
890 891 892 893 894 895 896 897 898 899 900 901 902
#ifdef TIME_TERMINATE
    case 'l':
      if (sscanf(optarg,"%lf",&timelimit) != 1) {
	print_help();
      }
      break;
#endif
#ifdef TIME_TARGET
    case 't':
      if (sscanf(optarg,"%lf",&timetarget) != 1) {
	print_help();
      }
      break;
903
#endif
904 905 906
    case 'r':
      allow_trivial_links = false; break;
    case 'p':
907
      disable_pclasses = true; break;
Robert Ricci's avatar
Robert Ricci committed
908 909 910 911
#ifdef PER_VNODE_TT
    case 'P':
      prune_pclasses = true; break;
#endif
912 913
    case 'T':
      scoring_selftest = true; break;
914 915
    case 'd':
      dynamic_pclasses = true; break;
916 917 918 919 920
    case 'H':
      if (sscanf(optarg,"%lf",&scale_neighborhood) != 1) {
	print_help();
      }
      break;
921 922
    case 'o':
      allow_overload = true; break;
Robert Ricci's avatar
Robert Ricci committed
923 924
    case 'g':
      greedy_link_assignment = true; break;
Robert Ricci's avatar
Robert Ricci committed
925 926 927 928 929
    case 't':
      if (sscanf(optarg,"%lf",&initial_temperature) != 1) {
	print_help();
      }
      no_melting = true; break;
930 931 932 933 934 935 936
    case 'u':
      print_summary = true; break;
    case 'c':
      if (sscanf(optarg,"%lf",&use_connected_pnode_find) != 1) {
	print_help();
      }
      break;
937 938 939 940
    case 'n':
      prechecks_only = true;
      cout << "Doing only prechecks, exiting early" << endl;
      break;
941 942 943
    case 'D':
      dump_config = true;
      break;
944
    case 'x':
945 946 947 948 949 950 951
#ifdef WITH_XML
      ptop_xml_input = false;
#endif
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  ptopFilename = optarg;
952
      break;
953 954
    
		case 'y':
955 956
#ifdef WITH_XML
      vtop_xml_input = false;