assign.cc 33.6 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.
 */

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
// Use XML for file input
137 138 139 140 141 142
// 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;
143
#endif
144

145 146 147
// XXX - shouldn't be in this file
double absbest;
int absbestviolated, iters, iters_to_best;
Robert Ricci's avatar
Robert Ricci committed
148

149 150 151
// Map of all physical types in use in the system
tb_ptype_map ptypes;

152 153 154
/*
 * Internal functions
 */
Mac Newbold's avatar
Mac Newbold committed
155

Robert Ricci's avatar
Robert Ricci committed
156
// Return the CPU time (in seconds) used by this process
157
float used_time() {
158 159 160 161 162 163
  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;
}

164 165 166 167 168 169 170 171 172 173 174 175
// 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
176
// Read in the .ptop file
177
void read_physical_topology(char *filename) {
178 179
  ifstream ptopfile;
  ptopfile.open(filename);
Robert Ricci's avatar
Robert Ricci committed
180
  if (!ptopfile.is_open()) {
181
      cout << "*** Unable to open ptop file " << filename << endl;
182
      exit(EXIT_FATAL);
Robert Ricci's avatar
Robert Ricci committed
183
  }
184 185
  
#ifdef WITH_XML
186 187 188 189 190 191
  if (ptop_xml_input) {
		cout << "Physical Graph: " << parse_ptop_xml(PG,SG,filename) << endl;
  } else if (ptop_rspec_input) {
	  cout << "Physical Graph: " << parse_ptop_rspec (PG, SG, filename) << endl;
	}
	else {
192 193 194
      cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;
  }
#else
195
	cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;
196
#endif
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218

#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
219
#endif // DUMP_GRAPH
220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242

#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
243
#endif // GRAPH_DEBUG
244

Robert Ricci's avatar
Robert Ricci committed
245 246
  // Set up pnode2vertex - a mapping between vertices in the physical graph and
  // the pnodes that we just read in from the ptop file
247 248 249 250 251 252 253 254
  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
255 256
// Calculate the minimum spanning tree for the switches - we only consider one
// potential path between each pair of switches.
257
// XXX: Should soon be replaced by calculate_shortest_routes()
258
void calculate_switch_MST() {
259
  cout << "Calculating shortest paths on switch fabric." << endl;
Robert Ricci's avatar
Robert Ricci committed
260 261

  // Set up the weight map for Dijkstra's
262 263 264 265 266 267 268 269 270 271
  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
272

Robert Ricci's avatar
Robert Ricci committed
273
  // Let boost do the Disjktra's for us, from each switch
274 275 276 277 278 279 280 281
  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
282 283
  }

284 285 286 287 288 289 290 291 292
#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
293
#endif // GRAPH_DEBUG
294 295
}

Robert Ricci's avatar
Robert Ricci committed
296
// Read in the .top file
297
void read_virtual_topology(char *filename) {
298 299
  ifstream topfile;
  topfile.open(filename);
Robert Ricci's avatar
Robert Ricci committed
300
  if (!topfile.is_open()) {
301
      cout << "*** Unable to open top file " << filename << endl;
302
      exit(EXIT_FATAL);
Robert Ricci's avatar
Robert Ricci committed
303
  }
304
  
305 306 307 308 309 310 311 312
#ifdef WITH_XML  
  if (vtop_xml_input) {
	cout << "Virtual Graph: " << parse_vtop_xml(VG,filename) << endl;
  }
  else if (vtop_rspec_input){
  	  cout << "Virtual Graph: " << parse_vtop_rspec (VG, filename) << endl ;
  }
  else {
313 314 315
      cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;
  }
#else
316
	cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;
317
#endif
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342

#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
343 344 345 346 347 348 349 350 351 352
/*
 * 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) {
353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385
            /*
             * 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
                 * we will never use this particular node
                 */
                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
                     */
386
                    this_type_p->remove_slots(tm_iterator->second->get_max_load());
387 388 389 390 391 392 393 394 395

                    /*
                     * Move on to the next node
                     */
                    pnode_iterator++;
                }
                ptype_iterator++;
            }

Robert Ricci's avatar
Robert Ricci committed
396 397 398 399 400 401
	    pclass_list::iterator nukeme = pclass_iterator;
	    pclass_iterator++;
#ifdef PCLASS_DEBUG
	    cout << "Pruning " << (*nukeme)->name << endl;
#endif
	    pruned++;
402

Robert Ricci's avatar
Robert Ricci committed
403 404 405 406 407 408 409 410 411 412
	    delete *nukeme;
	    pclasses.erase(nukeme);
	} else {
	    pclass_iterator++;
	}
    }
    cout << "pclass pruning complete: removed " << pruned << " pclasses, " <<
	pclasses.size() << " remain." << endl;
}

413
void print_help() {
414 415
  cout << "assign [options] ptopfile topfile [config params]" << endl;
  cout << "Options: " << endl;
416
#ifdef TIME_TERMINATE
417
  cout << "  -l <time>   - Limit runtime." << endl;
Mac Newbold's avatar
Mac Newbold committed
418
#endif
419
  cout << "  -s <seed>   - Set the seed." << endl;
420
#ifdef GRAPHVIZ_SUPPORT
421
  cout << "  -v <viz>    - Produce graphviz files with given prefix." <<
422
    endl;
423
#endif
424 425 426
  cout << "  -r          - Don't allow trivial links." << endl;
  cout << "  -p          - Disable pclasses." << endl;
  cout << "  -d          - Enable dynamic pclasses." << endl;
427
#ifdef PER_VNODE_TT
428
  cout << "  -P          - Prune unusable pclasses." << endl;
429
#endif
430 431 432
  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
433 434
  cout << "  -t <float>  - Start the temperature at <float> instead of melting."
      << endl;
435 436
  cout << "  -u          - Print a summary of the solution." << endl;
  cout << "  -c <float>  - Use the 'connected' pnode finding algorithm " <<
437 438
      "<float>*100% of the time." << endl;
  cout << "  -n          - Don't anneal - just do the prechecks." << endl;
439 440 441 442 443 444

  cout << "  -x <file>   - Specify a text ptop file" << endl;
#ifdef WITH_XML
  cout << "  -X <file>   - Specify a XML ptop file" << endl;
#endif
  cout << "  -y <file>   - Specify a text top file" << endl;
445
#ifdef WITH_XML
446
  cout << "  -Y <file>   - Specify a XML vtop file" << endl;
447
#endif
448 449 450 451 452
#ifdef WITH_XML
  cout << "  -q <file>   - Specify a rspec ptop file" << endl;
  cout << "  -w <file>   - Specify a rspec vtop file" << endl;
#endif
  cout << "  -F          - Apply additional checking to fixed noded" << endl;
453
  exit(EXIT_FATAL);
454 455 456 457 458
}
 
// 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
459
int type_precheck(int round) {
460
    cout << "Type precheck:" << endl;
461

462
    bool ok = true;
Mac Newbold's avatar
Mac Newbold committed
463

464 465 466 467 468 469 470 471 472 473 474
    /*
     * 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";
    }
475
    // First, check the regular types
476 477
    for (name_count_map::iterator vtype_it=vtypes.begin();
	    vtype_it != vtypes.end();++vtype_it) {
478

479
	// Check to see if there were any pnodes of the type at all
480
	tb_ptype_map::iterator ptype_it = ptypes.find(vtype_it->first);
481
	if (ptype_it == ptypes.end()) {
482
	    cout << "  *** No " << round_str << " physical nodes of type "
483 484
                << vtype_it->first << " found (" << vtype_it->second
                << " requested)" << endl;
485
	    ok = false;
486
	} else {
487
	    // Okay, there are some - are there enough?
488
	    if (ptype_it->second->pnode_slots() < vtype_it->second) {
489
		cout << "  *** " << vtype_it->second << " nodes of type " <<
490 491 492
                    vtype_it->first << " requested, but only " <<
                    ptype_it->second->pnode_slots() << " " << round_str <<
                    " nodes of type " << vtype_it->first<< " found" << endl;
493 494 495 496 497 498 499 500
		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;
501 502
		ok = false;
	    }
503
	}
504
    }
505 506 507 508

    // Check the vclasses, too
    for (name_list_map::iterator vclass_it = vclasses.begin();
	    vclass_it != vclasses.end(); ++vclass_it) {
509
	bool found_match = false;
510
        // Make sure we actually use this vclass
511
        name_vclass_map::iterator dit = vclass_map.find(vclass_it->first);
512 513 514 515 516 517 518 519 520 521 522
        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;
            }
        }

523
	for (vector<fstring>::iterator vtype_it = vclass_it->second.begin();
524
		vtype_it != vclass_it->second.end(); vtype_it++) {
525 526
	    tb_ptype_map::iterator mit = ptypes.find(*vtype_it);
	    if ((mit != ptypes.end()) && (mit->second->pnode_slots() != 0)) {
527 528 529 530 531 532
		found_match = true;
		break;
	    }
	}

	if (!found_match) {
533 534
	    cout << "  *** No " << round_str <<
                " physical nodes can satisfy vclass " << vclass_it->first << endl;
535 536 537 538
	    ok = false;
	}
    }

539
    if (ok) {
540
      cout << "Type precheck passed." << endl;
541 542
      return 1;
    } else {
543
      cout << "*** Type precheck failed!" << endl;
544 545 546
      return 0;
    }
}
547

548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563
// 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);
564

565 566 567 568
    /*
     * Indicates whether all nodes have potential matches or not
     */
    bool ok = true;
569

570 571
    for (;vit != vendit;vit++) {
	tb_vnode *v = get(vvertex_pmap,*vit);
572

573 574 575 576 577 578 579 580
	pclass_vector *vec = new pclass_vector();
	vnode_type_table[v->name] = tt_entry(0,vec);

	// 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
581
	map<fstring,int> matched_desires;
582

583 584 585
	// 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;
586 587
        hash_map<fstring,int> max_links;
        hash_map<fstring,int> desired_links;
588
	map<fstring,bool> matched_links;
589

590
	tb_vclass *vclass = v->vclass;
591
	tb_vclass::members_map::const_iterator mit;
592
	if (vclass) {
593
	    mit = vclass->get_members().begin();
594
	}
595 596 597
	for (;;) {
	    // Loop over all types this node can take on, which might be only
	    // one, if it's not part of a vclass
598
	    fstring this_type;
599 600 601 602 603
	    if (vclass) {
		this_type = mit->first;
	    } else {
		this_type = v->type;
	    }
604

605 606 607 608 609 610 611 612
            // Check to make sure there are actually nodes of this type in the
            // physical topology
            if (type_table.find(this_type) == type_table.end()) {
                // Yes, I know, goto is evil. But I'm not gonna indent the next
                // 100 lines of code for this error case
                goto nosuchtype;
            }

613 614
	    for (pclass_vector::iterator it = type_table[this_type].second->begin();
		    it != type_table[this_type].second->end(); it++) {
615

616 617
		bool potential_match = true;
		// Grab the first node of the pclass as a representative sample
618
	 	tb_pnode *pnode = *((*it)->members[this_type]->L.begin());
619 620 621

		// 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
622

623 624 625 626
		// Check bandwidth on emulated links
		if (pnode->total_bandwidth >= v->total_bandwidth) {
		    matched_bw++;
		} else {
627
			potential_match = false;
628
		}
Mac Newbold's avatar
Mac Newbold committed
629

630 631
		// Check to see if if the pnode has enough slots of the
		// appropriate type available
632 633 634
		tb_pnode::types_map::iterator type_iterator =
		    pnode->types.find(v->type);
		if (type_iterator == pnode->types.end()) {
635 636
		    // Must have been a vtype to get here - ignore it
		} else {
637
		    if (v->typecount > type_iterator->second->get_max_load()) {
638 639 640 641 642
			// Nope, this vnode is too demanding
			potential_match = false;
		    }
		}

643 644 645 646 647 648 649
		/*
		 * 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++) {
650
		    // Skip 'local' and 'global' features
651
		    if (fdit->is_global() || fdit->is_local()) {
652 653
			continue;
		    }
654 655 656
		    // Only check for FDs that would result in a violation if
		    // unmatched.
		    if (fdit.either_violateable()) {
657 658 659 660 661
			if (fdit.membership() !=
				tb_featuredesire_set_iterator::BOTH) {
			    potential_match = false;
			}

662 663
			// We look for violateable desires on vnodes so that we
			// can report them to the user
664 665 666 667 668 669 670 671 672
			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;
			    }
673 674 675 676
			}
			if (fdit.membership() ==
				tb_featuredesire_set_iterator::BOTH) {
			    matched_desires[fdit->name()]++;
677 678 679
			}
		    }
		}
680
		
681 682 683 684 685 686
		// 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") {
687 688 689 690 691 692
                  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;
693
                    desired_links[type] = count;
694 695 696 697
                    if (pnode->link_counts.find(type) !=
                          pnode->link_counts.end()) {
                      // Found at least one link of this type
                      matched_links[type] = true;
698 699 700
                      if (pnode->link_counts[type] > max_links[type]) {
                        max_links[type] = pnode->link_counts[type];
                      }
701 702 703 704 705 706 707 708 709 710 711
                      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
712

713 714 715 716 717 718
		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;
719
#endif
720 721
		}
	    }
722

723
nosuchtype:
724 725
	    if (vclass) { 
		mit++;
726
		if (mit == vclass->get_members().end()) {
727 728 729 730 731 732
		    break;
		}
	    } else {
		// If not a vtype, we only had to do this once
		break;
	    }
733
	}
734

735
	if (vnode_type_table[v->name].first == 0) {
736
	    cout << "  *** No possible mapping for " << v->name << endl;
737
	    // Make an attempt to figure out why it didn't match
738 739 740 741 742
	    
	    // 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++) {
743
	      fstring type = lit->first;
744
	      if (!matched_links[type]) {
745 746
		cout << "      No links of type " << type << " found! (" <<
                  desired_links[type] << " requested)" << endl;
747 748
	      } else {
		if (!matched_link_counts[type]) {
749 750 751
		  cout << "      Too many links of type " << type << "! (" <<
                    desired_links[type] << " requested, " << max_links[type] <<
                    " found)" << endl;
752 753
		}
	      }
754
	    }
755

756
	    if (!matched_bw) {
757
		cout << "      Too much bandwidth on emulated links!" << endl;
758
	    }
759

760
	    for (map<fstring,int>::iterator dit = matched_desires.begin();
761 762 763
		    dit != matched_desires.end();
		    dit++) {
		if (dit->second == 0) {
764
		    cout << "      No physical nodes have feature " << dit->first
765 766
			<< "!" << endl;
		}
767
	    }
768
	    ok = false;
769
	}
770 771 772
#ifdef PCLASS_DEBUG
	cerr << v->name << " can map to " << vnode_type_table[v->name].first << " pclasses"
	    << endl;
773
#endif
774

775
    }
776

777 778 779
    if (ok) {
	cout << "Node mapping precheck succeeded" << endl;
	return 1;
780
    } else {
781
	cout << "*** Node mapping precheck failed!" << endl;
782
	return 0;
783 784
    }

785 786 787
#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
788
#endif
789
}
Christopher Alfeld's avatar
 
Christopher Alfeld committed
790

791 792 793 794 795 796 797 798 799 800 801 802 803 804
// 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;
  }
}  

805 806 807
// Signal handler - add a convneint way to kill assign and make it return an
// unretryable error
void exit_unretryable(int signal) {
808
  cout << "*** Killed with signal " << signal << " - exiting!" << endl;
809 810 811 812 813 814 815 816 817
  _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: "
    << violated << " (Best S: " << absbest << " V:" << absbestviolated << ")"
    << endl;
818
  cout.flush();
819 820
}

821 822 823 824
// From anneal.cc - the best solution found
extern solution best_solution;

int main(int argc,char **argv) {
825
  int seed = 0;
826
#ifdef GRAPHVIZ_SUPPORT
827
  fstring viz_prefix;
828
#endif
829
  bool scoring_selftest = false;
830
  bool prechecks_only = false;
831 832 833 834 835
  
  // Handle command line
  char ch;
  timelimit = 0.0;
  timetarget = 0.0;
836 837 838 839 840
  
  char* ptopFilename = "";
  char* vtopFilename = "";
  
  while ((ch = getopt(argc,argv,"s:v:l:t:rpPTdH:oguc:nx:X:y:Y:q:w:F")) != -1) {
841 842 843
    switch (ch) {
    case 's':
      if (sscanf(optarg,"%d",&seed) != 1) {
844
		print_help();
845
      }
846
      break;
847
#ifdef GRAPHVIZ_SUPPORT
848 849 850
    case 'v':
      viz_prefix = optarg;
      break;
851
#endif
852 853 854 855 856 857 858 859 860 861 862 863 864
#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;
865
#endif
866 867 868
    case 'r':
      allow_trivial_links = false; break;
    case 'p':
869
      disable_pclasses = true; break;
Robert Ricci's avatar
Robert Ricci committed
870 871 872 873
#ifdef PER_VNODE_TT
    case 'P':
      prune_pclasses = true; break;
#endif
874 875
    case 'T':
      scoring_selftest = true; break;
876 877
    case 'd':
      dynamic_pclasses = true; break;
878 879 880 881 882
    case 'H':
      if (sscanf(optarg,"%lf",&scale_neighborhood) != 1) {
	print_help();
      }
      break;
883 884
    case 'o':
      allow_overload = true; break;
Robert Ricci's avatar
Robert Ricci committed
885 886
    case 'g':
      greedy_link_assignment = true; break;
Robert Ricci's avatar
Robert Ricci committed
887 888 889 890 891
    case 't':
      if (sscanf(optarg,"%lf",&initial_temperature) != 1) {
	print_help();
      }
      no_melting = true; break;
892 893 894 895 896 897 898
    case 'u':
      print_summary = true; break;
    case 'c':
      if (sscanf(optarg,"%lf",&use_connected_pnode_find) != 1) {
	print_help();
      }
      break;
899 900 901 902
    case 'n':
      prechecks_only = true;
      cout << "Doing only prechecks, exiting early" << endl;
      break;
903
    case 'x':
904 905 906 907 908 909 910
#ifdef WITH_XML
      ptop_xml_input = false;
#endif
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  ptopFilename = optarg;
911
      break;
912 913 914 915 916 917 918 919 920 921 922 923
#ifdef WITH_XML      
    case 'X':
      ptop_xml_input = true;
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  ptopFilename = optarg;
    break;
#endif
    case 'y':
#ifdef WITH_XML
      vtop_xml_input = false;
924
#endif
925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  vtopFilename = optarg;
    break;
#ifdef WITH_XML
    case 'Y':
      vtop_xml_input = true;
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  vtopFilename = optarg;
    break;
#endif
#ifdef WITH_XML
	case 'q':
	  ptop_rspec_input = true;
	  if (strcmp(optarg, "") == 0) {
	  	print_help();
	  }
	  ptopFilename = optarg;
    break;

	case 'w':
	  vtop_rspec_input = true;
	  if (strcmp(optarg, "") == 0) {
	  	print_help();
	  }
	  vtopFilename = optarg;
    break;
#endif
        case 'F':
          check_fixed_nodes = true;
    break;

960 961
    default:
      print_help();
962
    }
963
  }
964 965 966
  argc -= optind;
  argv += optind;
  
967 968 969 970 971 972 973 974 975 976 977 978
  if (argc == 2)
  {
	  ptopFilename = argv[0];
	  vtopFilename = argv[1];
  }
  
  if (strcmp(ptopFilename, "") == 0)
	  print_help();
  	
  if (strcmp(vtopFilename, "") == 0)
	  print_help();	
  
979 980 981 982 983 984
  if (seed == 0) {
    if (getenv("ASSIGN_SEED") != NULL) {
      sscanf(getenv("ASSIGN_SEED"),"%d",&seed);
    } else {
      seed = time(NULL)+getpid();
    }
985
  }
986

987
#ifdef GRAPHVIZ_SUPPORT
988 989