score.cc 20.6 KB
Newer Older
1 2 3 4 5
/*
 * EMULAB-COPYRIGHT
 * Copyright (c) 2000-2002 University of Utah and the Flux Group.
 * All rights reserved.
 */
6

7 8 9 10 11
/*
 * ASSUMPTIONS:
 *  1. Any switch can get to any other switch either directly
 *     or via at most one other switch (star formation).
 */
12

13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
// Note on variable names: LEDA has generic 'edge' and 'node'.  When
// these are translated to 'tb_*' structures the variables end in
// r.  I.e. dst -> dstr.  dst is a node, and dstr is a tb_pnode or similar.

// Not sure we need all these LEDA includes.
#include <LEDA/graph_alg.h>
#include <LEDA/ugraph.h>
#include <LEDA/graphwin.h>
#include <LEDA/dictionary.h>
#include <LEDA/map.h>
#include <LEDA/graph_iterator.h>
#include <LEDA/sortseq.h>
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h>
#include <string.h>
Mac Newbold's avatar
Mac Newbold committed
32 33

#include "common.h"
34
#include "vclass.h"
35
#include "virtual.h"
36
#include "physical.h"
Christopher Alfeld's avatar
 
Christopher Alfeld committed
37 38 39
#include "pclass.h"
#include "score.h"

Mac Newbold's avatar
Mac Newbold committed
40

41
#include "assert.h"
42

43 44
typedef node_array<edge> switch_pred_array;
extern node_array<switch_pred_array> switch_preds;
45

46
float score;			// The score of the current mapping
Mac Newbold's avatar
Mac Newbold committed
47 48
int violated;			// How many times the restrictions
				// have been violated.
49 50
node pnodes[MAX_PNODES];	// int->node map
				// pnodes[0] == NULL
Mac Newbold's avatar
Mac Newbold committed
51 52 53

violated_info vinfo;		// specific info on violations

54
extern tb_vgraph G;		// virtual graph
Mac Newbold's avatar
Mac Newbold committed
55
extern tb_pgraph PG;		// physical grpaph
56
extern tb_sgraph SG;		// switch fabric
Mac Newbold's avatar
Mac Newbold committed
57

58 59 60 61 62 63
edge direct_link(node a,node b);
void score_link(edge e,edge v,bool interswitch);
void unscore_link(edge e,edge v,bool interswitch);
edge find_link_to_switch(node n);
int find_intraswitch_path(node src,node dst,edge *first,edge *second);
int find_interswitch_path(node src,node dst,int bandwidth,list<edge> &L);
Mac Newbold's avatar
Mac Newbold committed
64 65

#ifdef SCORE_DEBUG_MORE
66 67
#define SADD(amount) fprintf(stderr,"SADD: %s = %.2f\n",#amount,amount);score+=amount
#define SSUB(amount) fprintf(stderr,"SSUB: %s = %.2f\n",#amount,amount);score-=amount
Mac Newbold's avatar
Mac Newbold committed
68 69 70 71 72 73 74 75 76
#else
#define SADD(amount) score += amount
#define SSUB(amount) score -= amount
#endif

/*
 * score()
 * Returns the score.
 */
77
float get_score() {return score;}
Mac Newbold's avatar
Mac Newbold committed
78 79 80 81 82 83 84 85

/*
 * init_score()
 * This initialized the scoring system.  It also clears all
 * assignments.
 */
void init_score()
{
86 87 88
#ifdef SCORE_DEBUG
  fprintf(stderr,"SCORE: Initializing\n");
#endif
Mac Newbold's avatar
Mac Newbold committed
89 90 91 92 93
  score=0;
  violated=0;
  vinfo.unassigned = vinfo.pnode_load = 0;
  vinfo.no_connection = vinfo.link_users = vinfo.bandwidth = 0;

94 95 96 97 98 99
  node n;
  edge e;
  forall_nodes(n,G) {
    tb_vnode &vn=G[n];
    vn.posistion=0;
    vn.no_connections=0;
Mac Newbold's avatar
Mac Newbold committed
100 101 102 103
    SADD(SCORE_UNASSIGNED);
    vinfo.unassigned++;
    violated++;
  }
104 105 106 107
  forall_edges(e,G) {
    tb_vlink &ve=G[e];
    ve.type=tb_vlink::LINK_UNKNOWN;
    ve.plink=NULL;
Mac Newbold's avatar
Mac Newbold committed
108
  }
109 110 111 112 113
  forall_nodes(n,PG) {
    tb_pnode &pn=PG[n];
    pn.typed=false;
    pn.current_load=0;
    pn.pnodes_used=0;
Mac Newbold's avatar
Mac Newbold committed
114
  }
115 116 117 118 119
  forall_edges(e,PG) {
    tb_plink &pe=PG[e];
    pe.bw_used=0;
    pe.emulated=0;
    pe.nonemulated=0;
Mac Newbold's avatar
Mac Newbold committed
120 121
  }

122 123 124
  assert(pnodes[0] == NULL);
#ifdef SCORE_DEBUG
  fprintf(stderr,"  score = %.2f violated = %d\n",score,violated);
125 126
#endif
}
127

Mac Newbold's avatar
Mac Newbold committed
128
/*
129
 * void remove_node(node node)
Mac Newbold's avatar
Mac Newbold committed
130
 * This removes a virtual node from the assignments, adjusting
131 132 133
 * the score appropriately.
 */
void remove_node(node n)
Mac Newbold's avatar
Mac Newbold committed
134 135
{
  /* Find pnode assigned to */
136 137 138 139 140 141 142 143 144
  node pnode;

  tb_vnode &vnoder = G[n];
  pnode = pnodes[vnoder.posistion];
  tb_pnode &pnoder = PG[pnode];

#ifdef SCORE_DEBUG
  cerr <<  "SCORE: remove_node(" << vnoder.name << ")\n";
  fprintf(stderr,"       no_connections = %d\n",vnoder.no_connections);
Mac Newbold's avatar
Mac Newbold committed
145 146 147 148
#endif

  assert(pnode != NULL);

149
  pclass_unset(pnoder);
150 151

  // pclass
152 153 154 155
  if (pnoder.my_class->used == 0) {
#ifdef SCORE_DEBUG
    cerr << "  freeing pclass\n";
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
156 157
    SSUB(SCORE_PCLASS);
  }
158 159

  // vclass
160 161 162 163 164
  if (vnoder.vclass != NULL) {
    double score_delta = vnoder.vclass->unassign_node(vnoder.type);
#ifdef SCORE_DEBUG
    cerr << "  vclass unassign " << score_delta << endl;
#endif
165 166 167 168 169 170 171
    
    if (score_delta <= -1) {
      violated--;
      vinfo.vclass--;
    }
    SSUB(-score_delta*SCORE_VCLASS);
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
172
  
173 174 175 176 177 178 179
  edge e;
  tb_vlink *vlink;
  node vdst;
  tb_vnode *vdstr;
  node pdst;
  tb_pnode *pdstr;

Mac Newbold's avatar
Mac Newbold committed
180
  // remove the scores associated with each edge
181 182 183 184 185 186 187 188
  forall_inout_edges(e,n) {
    vlink=&G[e];
    vdst=G.target(e);
    if (vdst == n)
      vdst = G.source(e);
    vdstr=&G[vdst];
#ifdef SCORE_DEBUG
    cerr << "  edge to " << vdstr->name << endl;
189
#endif
190 191 192 193 194
    if (vdstr->posistion == 0) continue;
    if (vlink->type == tb_vlink::LINK_DIRECT) {
      // DIRECT LINK
#ifdef SCORE_DEBUG
      fprintf(stderr,"   direct link\n");
195
#endif
196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
      unscore_link(vlink->plink,e,false);
    } else if (vlink->type == tb_vlink::LINK_INTERSWITCH) {
      // INTERSWITCH LINK
      pdst=pnodes[vdstr->posistion];
      pdstr=&PG[pdst];
#ifdef SCORE_DEBUG
      cerr << "  interswitch link\n";
#endif

      edge cur;      
      forall(cur,G[e].path) {
	SSUB(SCORE_INTERSWITCH_LINK);
	unscore_link(cur,e,true);
      }
      G[e].path.clear();
      
      unscore_link(vlink->plink_local_one,e,false);
      unscore_link(vlink->plink_local_two,e,false);
    } else if (vlink->type == tb_vlink::LINK_INTRASWITCH) {
      // INTRASWITCH LINK
#ifdef SCORE_DEBUG
      fprintf(stderr,"   intraswitch link\n");
Mac Newbold's avatar
Mac Newbold committed
218
#endif
219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238
      SSUB(SCORE_INTRASWITCH_LINK);

      unscore_link(vlink->plink,e,false);
      unscore_link(vlink->plink_two,e,false); 
    } else if (vlink->type != tb_vlink::LINK_TRIVIAL) {
      // No link
      fprintf(stderr,"Internal error - no link\n");
      abort();
    }
  }

  // remove scores associated with the node
  SSUB(SCORE_NO_CONNECTION*vnoder.no_connections);
  violated -= vnoder.no_connections;
  vinfo.no_connection -= vnoder.no_connections;

  // adjust pnode scores
  pnoder.current_load--;
  vnoder.posistion = 0;
  if (pnoder.current_load == 0) {
239
    // release pnode
240 241 242
#ifdef SCORE_DEBUG
    fprintf(stderr,"  releasing pnode\n");
#endif
Mac Newbold's avatar
Mac Newbold committed
243
    SSUB(SCORE_PNODE);
244 245 246 247 248
    node the_switch=pnoder.the_switch;
    if (the_switch) {
      if ((--PG[the_switch].pnodes_used) == 0) {
#ifdef SCORE_DEBUG
	cerr << "  releasing switch " << PG[the_switch].name << endl;
Mac Newbold's avatar
Mac Newbold committed
249
#endif
250 251 252 253
	// release switch
	SSUB(SCORE_SWITCH);
      }
    }
Mac Newbold's avatar
Mac Newbold committed
254
    // revert pnode type
255 256 257 258 259
    pnoder.typed=false;
  } else if (pnoder.current_load >= pnoder.max_load) {
#ifdef SCORE_DEBUG
    fprintf(stderr,"  reducing penalty, new load = %d (>= %d)\n",pnoder.current_load,pnoder.max_load);
#endif
Mac Newbold's avatar
Mac Newbold committed
260 261 262 263 264 265 266 267
    SSUB(SCORE_PNODE_PENALTY);
    vinfo.pnode_load--;
    violated--;
  }
  // add score for unassigned node
  SADD(SCORE_UNASSIGNED);
  vinfo.unassigned++;
  violated++;
268 269

  // features/desires
Christopher Alfeld's avatar
 
Christopher Alfeld committed
270
  int fd_violated;
271
  double fds=fd_score(vnoder,pnoder,&fd_violated);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
272 273 274
  SSUB(fds);
  violated -= fd_violated;
  vinfo.desires -= fd_violated;
275
  
276 277
#ifdef SCORE_DEBUG
  fprintf(stderr,"  new score = %.2f  new violated = %d\n",score,violated);
278 279 280 281
#endif
}

/*
282 283 284 285 286
 * int add_node(node node,int ploc)
 * Add a mapping of node to ploc and adjust score appropriately.
 * Returns 1 in the case of an incompatible mapping.  This should
 * never happen as the same checks should be in place in a higher
 * level.  (Optimization?)
287
 */
288
int add_node(node n,int ploc)
289
{
290 291 292 293 294 295 296 297 298 299 300 301 302 303
  tb_vnode &vnoder=G[n];
  node pnode = pnodes[ploc];
  tb_pnode &pnoder=PG[pnode];

#ifdef SCORE_DEBUG
  cerr << "SCORE: add_node(" << vnoder.name << "," << pnoder.name << "[" << ploc << "])\n";
  fprintf(stderr,"  vnode type = ");
  cerr << vnoder.type << " pnode switch = ";
  if (pnoder.the_switch) {
    cerr << PG[pnoder.the_switch].name;
  } else {
    cerr << "No switch";
  }
  cerr << endl;
Mac Newbold's avatar
Mac Newbold committed
304 305 306 307
#endif
  
  // set up pnode
  // figure out type
308 309 310 311 312 313
  if (!pnoder.typed) {
#ifdef SCORE_DEBUG
    fprintf(stderr,"  virgin pnode\n");
    cerr << "    vtype = " << vnoder.type << "\n";
#endif
    
Mac Newbold's avatar
Mac Newbold committed
314 315
    // Remove check assuming at higher level?
    // Remove higher level checks?
316 317 318 319 320
    pnoder.max_load=0;
    if (pnoder.types.lookup(vnoder.type) != nil)
      pnoder.max_load = pnoder.types.access(vnoder.type);
    
    if (pnoder.max_load == 0) {
Mac Newbold's avatar
Mac Newbold committed
321
      // didn't find a type
322 323 324
#ifdef SCORE_DEBUG
      fprintf(stderr,"  no matching type\n");
#endif
Mac Newbold's avatar
Mac Newbold committed
325 326
      return 1;
    }
327

328 329 330 331 332 333 334 335
    pnoder.current_type=vnoder.type;
    pnoder.typed=true;

#ifdef SCORE_DEBUG
    fprintf(stderr,"  matching type found (");
    cerr << pnoder.current_type << ", max = " << pnoder.max_load;
    cerr << ")" << endl;
#endif
Mac Newbold's avatar
Mac Newbold committed
336
  } else {
337 338 339 340 341 342 343
#ifdef SCORE_DEBUG
    fprintf(stderr,"  pnode already has type\n");
#endif
    if (pnoder.current_type != vnoder.type) {
#ifdef SCORE_DEBUG      
      fprintf(stderr,"  incompatible types\n");
#endif
Mac Newbold's avatar
Mac Newbold committed
344 345
      return 1;
    } else {
346 347 348 349
#ifdef SCORE_DEBUG
      fprintf(stderr,"  comaptible types\n");
#endif
      if (pnoder.current_load == pnoder.max_load) {
350 351 352
	/* XXX - We could ignore this check and let the code
	   at the end of the routine penalize for going over
	   load.  Failing here seems to work better though. */
353 354 355
#ifdef SCORE_DEBUG
	fprintf(stderr,"  node is full\n");
#endif
Mac Newbold's avatar
Mac Newbold committed
356 357
	return 1;
      }
358
      
Mac Newbold's avatar
Mac Newbold committed
359 360 361
    }
  }

362
  // set up links
363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
  vnoder.no_connections=0;
  edge e;
  node dst;
  tb_vlink *er;
  tb_plink *pl;
  edge pedge;
  forall_inout_edges(e,n) {
    dst=G.source(e);
    er=&G[e];
    if (dst == n) {
      dst=G.target(e);
    }
    tb_vnode &dstr=G[dst];
    assert(dst != n);
    assert(&dstr != &vnoder);
#ifdef SCORE_DEBUG
    cerr << "  edge to " << dstr.name << endl;
Mac Newbold's avatar
Mac Newbold committed
380
#endif
381 382 383 384 385 386 387 388

    if (dstr.posistion != 0) {
      // dstr is assigned
      node dpnode=pnodes[dstr.posistion];
      tb_pnode &dpnoder=PG[dpnode];

#ifdef SCORE_DEBUG
      cerr << "   goes to " << dpnoder.name << endl;
389 390
#endif

391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414
      if (dpnode == pnode) {
#ifdef SCORE_DEBUG
	fprintf(stderr,"  trivial link\n");
#endif SCORE_DEBUG
	er->type = tb_vlink::LINK_TRIVIAL;
      } else if ((pedge=direct_link(dpnode,pnode)) != NULL) {
#ifdef SCORE_DEBUG
	fprintf(stderr,"   found direct link = %p\n",pedge);
#endif
	pl = &PG[pedge];

	// direct
	er->type = tb_vlink::LINK_DIRECT;
	er->plink = pedge;

	score_link(pedge,e,false);
      } else if (pnoder.the_switch &&
		 (pnoder.the_switch == dpnoder.the_switch)) {
	// intraswitch
	assert(pnoder.the_switch == dpnoder.the_switch);
	edge first,second;
	if (find_intraswitch_path(pnode,dpnode,&first,&second) == 1) {
	  fprintf(stderr,"Internal error: Could not find intraswitch link!\n");
	  abort();
415
	}
Christopher Alfeld's avatar
 
Christopher Alfeld committed
416

417 418 419 420 421
	assert(first != NULL);
	assert(second != NULL);
	
#ifdef SCORE_DEBUG
	fprintf(stderr,"   found intraswitch link (%p,%p)\n",first,second);
422
#endif
423 424 425 426 427 428 429 430 431 432 433 434 435 436
	er->type = tb_vlink::LINK_INTRASWITCH;
	er->plink = first;
	er->plink_two = second;
	SADD(SCORE_INTRASWITCH_LINK);

	// check users and bandwidth
	score_link(first,e,false);
	score_link(second,e,false);
      } else {
	// try to find interswitch
#ifdef SCORE_DEBUG
	cerr << "   looking for interswitch link " <<
	  (pnoder.the_switch != nil?PG[pnoder.the_switch].name:string("No Switch")) << " " <<
	  (dpnoder.the_switch != nil?PG[dpnoder.the_switch].name:string("No Switch")) << endl;
437
#endif
438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457
	if (find_interswitch_path(pnoder.the_switch,dpnoder.the_switch,
				  er->bandwidth,er->path) == 0) {
#ifdef SCORE_DEBUG
	  fprintf(stderr,"   could not find path - no connection\n");
#endif

	  // Need to free up all links already made and abort
	  forall_inout_edges(e,n) {
	    tb_vlink &vlink = G[e];
	    if (vlink.type == tb_vlink::LINK_DIRECT) {
	      unscore_link(vlink.plink,e,false);
	    } else if (vlink.type == tb_vlink::LINK_INTRASWITCH) {
	      SSUB(SCORE_INTRASWITCH_LINK);
	      unscore_link(vlink.plink,e,false);
	      unscore_link(vlink.plink_two,e,false);
	    } else if (vlink.type == tb_vlink::LINK_INTERSWITCH) {
	      edge cur;
	      forall(cur,G[e].path) {
		SSUB(SCORE_INTERSWITCH_LINK);
		unscore_link(cur,e,true);
458
	      }
459 460 461 462
	      G[e].path.clear();
	      unscore_link(vlink.plink_local_one,e,false);
	      unscore_link(vlink.plink_local_two,e,false);
	    } // else LINK_UNKNOWN i.e. unassigned.
463
	  }
464 465 466 467 468 469 470 471

	  // Reset to be retyped next time and abort.  This is a
	  // fatal error.
	  pnoder.typed = false;
	  return 1;
 	} else {
#ifdef SCORE_DEBUG
	  fprintf(stderr,"   found interswitch link\n");
472
#endif
473 474 475 476 477 478 479
	  er->type=tb_vlink::LINK_INTERSWITCH;

	  edge cur;
	  forall(cur,er->path) {
	    SADD(SCORE_INTERSWITCH_LINK);
#ifdef SCORE_DEBUG
	    cerr << "     " << PG[cur].name << endl;
480
#endif
481 482 483 484 485 486 487 488 489 490
	    score_link(cur,e,true);
	  }

	  er->plink_local_one = find_link_to_switch(pnode);
	  assert(er->plink_local_one != NULL);
	  er->plink_local_two = find_link_to_switch(dpnode);
	  assert(er->plink_local_two != NULL);

	  score_link(er->plink_local_one,e,false);
	  score_link(er->plink_local_two,e,false);
Mac Newbold's avatar
Mac Newbold committed
491 492 493 494
	}
      }
    }
  }
495
    
Mac Newbold's avatar
Mac Newbold committed
496
  // finish setting up pnode
497 498 499 500 501
  pnoder.current_load++;
  vnoder.posistion = ploc;
  if (pnoder.current_load > pnoder.max_load) {
#ifdef SCORE_DEBUG
    fprintf(stderr,"  load to high - penalty (%d)\n",pnoder.current_load);
Mac Newbold's avatar
Mac Newbold committed
502 503 504 505 506
#endif
    SADD(SCORE_PNODE_PENALTY);
    vinfo.pnode_load++;
    violated++;
  } else {
507 508 509
#ifdef SCORE_DEBUG
    fprintf(stderr,"  load is fine\n");
#endif
Mac Newbold's avatar
Mac Newbold committed
510
  }
511 512 513 514
  if (pnoder.current_load == 1) {
#ifdef SCORE_DEBUG
    fprintf(stderr,"  new pnode\n");
#endif
Mac Newbold's avatar
Mac Newbold committed
515
    SADD(SCORE_PNODE);
516 517 518 519
    if (pnoder.the_switch &&
	(++PG[pnoder.the_switch].pnodes_used) == 1) {
#ifdef SCORE_DEBUG
      fprintf(stderr,"  new switch\n");
Mac Newbold's avatar
Mac Newbold committed
520
#endif
521 522
      SADD(SCORE_SWITCH);
    }
Mac Newbold's avatar
Mac Newbold committed
523 524 525 526 527 528 529
  }

  // node no longer unassigned
  SSUB(SCORE_UNASSIGNED);
  vinfo.unassigned--;
  violated--;

530
  // features/desires
Christopher Alfeld's avatar
 
Christopher Alfeld committed
531
  int fd_violated;
532
  double fds = fd_score(vnoder,pnoder,&fd_violated);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
533 534 535 536 537
  SADD(fds);
  violated += fd_violated;
  vinfo.desires += fd_violated;

  // pclass
538 539 540 541
  if (pnoder.my_class->used == 0) {
#ifdef SCORE_DEBUG
    cerr << "  new pclass\n";
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
542
    SADD(SCORE_PCLASS);
543
  }
544 545

  // vclass
546 547 548 549 550
  if (vnoder.vclass != NULL) {
    double score_delta = vnoder.vclass->assign_node(vnoder.type);
#ifdef SCORE_DEBUG
    cerr << "  vclass assign " << score_delta << endl;
#endif
551 552 553 554 555 556 557
    SADD(score_delta*SCORE_VCLASS);
    if (score_delta >= 1) {
      violated++;
      vinfo.vclass++;
    }
  }

558 559 560 561
#ifdef SCORE_DEBUG
  fprintf(stderr,"  posistion = %d\n",vnoder.posistion);
  fprintf(stderr,"  new score = %.2f  new violated = %d\n",score,violated);
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
562

563
  pclass_set(vnoder,pnoder);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
564
  
Mac Newbold's avatar
Mac Newbold committed
565 566 567 568 569 570
  return 0;
}

// returns "best" direct link between a and b.
// best = less users
//        break ties with minimum bw_used
571
edge direct_link(node a,node b)
Mac Newbold's avatar
Mac Newbold committed
572
{
573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591
  node dst;
  edge e;
  edge best = NULL;
  tb_plink *pl;
  tb_plink *bestpl = NULL;
  forall_inout_edges(e,a) {
    dst=PG.target(e);
    if (dst == a)
      dst=PG.source(e);
    if (dst == b) {
      pl = &PG[e];
      if (! bestpl ||
	  ((pl->emulated+pl->nonemulated <
	    bestpl->emulated+bestpl->nonemulated) ||
	   (pl->emulated+pl->nonemulated ==
	    bestpl->emulated+bestpl->nonemulated) &&
	   (pl->bw_used < bestpl->bw_used))) {
	best = e;
	bestpl = pl;
Mac Newbold's avatar
Mac Newbold committed
592 593 594
      }
    }
  }
595
  return best;
Mac Newbold's avatar
Mac Newbold committed
596 597
}

598
edge find_link_to_switch(node n)
Mac Newbold's avatar
Mac Newbold committed
599
{
600 601 602 603 604
  tb_pnode &nr = PG[n];

  edge e;
  node edst;
  float best_bw=1000.0;
Mac Newbold's avatar
Mac Newbold committed
605
  int best_users = 1000;
606 607 608 609 610 611 612 613 614 615 616 617 618 619
  float bw;
  edge best=NULL;
  forall_inout_edges(e,n) {
    edst = PG.target(e);
    if (edst == n)
      edst = PG.source(e);
    if (edst == nr.the_switch) {
      tb_plink &er = PG[e];
      bw = er.bw_used / er.bandwidth;
      if ((er.emulated+er.nonemulated < best_users) ||
	  ((er.emulated+er.nonemulated == best_users) && (bw < best_bw))) {
	best = e;
	best_bw = bw;
	best_users = er.emulated+er.nonemulated;
Mac Newbold's avatar
Mac Newbold committed
620 621 622
      }
    }
  }
623 624 625
  
  return best;
}
Mac Newbold's avatar
Mac Newbold committed
626

627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643
// this looks for the best links between the src and the switch
// and the dst and the switch.
int find_intraswitch_path(node src,node dst,edge *first,edge *second)
{
  tb_pnode &srcr=PG[src];
  tb_pnode &dstr=PG[dst];

  assert(srcr.the_switch == dstr.the_switch);
  assert(srcr.the_switch != NULL);
  assert(src != dst);

  *first = find_link_to_switch(src);
  *second = find_link_to_switch(dst);

  if ((*first != NULL) &&
      (*second != NULL)) return 0;
  return 1;
Mac Newbold's avatar
Mac Newbold committed
644 645
}

646 647 648 649
// this uses the shortest paths calculated over the switch graph to
// find a path between src and dst.  It passes out list<edge>, a list
// of the edges used. (assumed to be empty to begin with).
// Returns 0 if no path exists and 1 otherwise.
650
int find_interswitch_path(node src,node dst,int bandwidth,list<edge> &L)
Mac Newbold's avatar
Mac Newbold committed
651
{
652 653 654 655 656 657
  // We know the shortest path from src to node already.  It's stored
  // in switch_preds[src] and is a node_array<edge>.  Let P be this
  // array.  We can trace our shortest path by starting at the end and
  // following the pred edges back until we reach src.  We need to be
  // careful though because the switch_preds deals with elements of SG
  // and we have elements of PG.
658
  if ((src == nil) || (dst == nil)) {return 0;}
Mac Newbold's avatar
Mac Newbold committed
659
  
660 661 662 663 664 665
  node sg_src = PG[src].sgraph_switch;
  node sg_dst = PG[dst].sgraph_switch;
  edge sg_ed;
  node sg_cur=sg_dst;
  switch_pred_array &preds = switch_preds[sg_src];
  if (preds[sg_dst] == nil) {
666
    // unreachable
Mac Newbold's avatar
Mac Newbold committed
667 668
    return 0;
  }
669 670 671 672 673 674 675 676
  while (sg_cur != sg_src) {
    sg_ed = preds[sg_cur];
    L.push(SG[sg_ed].mate);
    if (SG.source(sg_ed) == sg_cur) {
      sg_cur = SG.target(sg_ed);
    } else {
      sg_cur = SG.source(sg_ed);
    }
677 678
  }
  return 1;
Mac Newbold's avatar
Mac Newbold committed
679 680 681
}

// this does scoring for over users and over bandwidth on edges.
682
void score_link(edge e,edge v,bool interswitch)
Mac Newbold's avatar
Mac Newbold committed
683
{
684 685
  tb_plink &pl = PG[e];
  tb_vlink &er = G[v];
Mac Newbold's avatar
Mac Newbold committed
686

687 688
#ifdef SCORE_DEBUG
  cerr << "  score_link(" << e << ") - " << pl.name << " / " << er.name << endl;
689
#endif
690 691

  if (! interswitch) {
692 693
    // need too account for three things here, the possiblity of a new plink
    // the user of a new emulated link, and a possible violation.
694 695
    if (er.emulated) {
      pl.emulated++;
696 697
      SADD(SCORE_EMULATED_LINK);
    }
698 699
    else pl.nonemulated++;
    if (pl.nonemulated+pl.emulated == 1) {
700
      // new link
701 702 703
#ifdef SCORE_DEBUG
      fprintf(stderr,"    first user\n");
#endif
704
      SADD(SCORE_DIRECT_LINK);
Mac Newbold's avatar
Mac Newbold committed
705
    } else {
706 707
      // check for violation, basically if this is the first of it's
      // type to be added.
708 709 710 711 712
      if (((! er.emulated) && (pl.nonemulated == 1)) ||
	  ((er.emulated) && (pl.emulated == 1))) {
#ifdef SCORE_DEBUG
	  fprintf(stderr,"    link user - penalty\n");
#endif
713 714 715
	  SADD(SCORE_DIRECT_LINK_PENALTY);
	  vinfo.link_users++;
	  violated++;
716
      }
Mac Newbold's avatar
Mac Newbold committed
717
    }
718 719
  }
    
720 721 722 723 724 725 726 727
  // bandwidth
  int prev_bw = pl.bw_used;
  pl.bw_used += er.bandwidth;
  if ((pl.bw_used > pl.bandwidth) &&
      (prev_bw <= pl.bandwidth)) {
#ifdef SCORE_DEBUG
    fprintf(stderr,"    went over bandwidth (%d > %d)\n",
	    pl.bw_used,pl.bandwidth);
Mac Newbold's avatar
Mac Newbold committed
728
#endif
729 730 731
    violated++;
    vinfo.bandwidth++;
    SADD(SCORE_OVER_BANDWIDTH);
Mac Newbold's avatar
Mac Newbold committed
732 733 734
  }
}

735
void unscore_link(edge e,edge v,bool interswitch)
Mac Newbold's avatar
Mac Newbold committed
736
{
737 738
  tb_plink &pl = PG[e];
  tb_vlink &er = G[v];
Mac Newbold's avatar
Mac Newbold committed
739

740 741
#ifdef SCORE_DEBUG
  fprintf(stderr,"  unscore_link(%p)\n",e);
Mac Newbold's avatar
Mac Newbold committed
742 743
#endif

744 745 746
  if (!interswitch) {
    if (er.emulated) {
      pl.emulated--;
747 748
      SSUB(SCORE_EMULATED_LINK);
    } else {
749
      pl.nonemulated--;
750
    }
751
    if (pl.nonemulated+pl.emulated == 0) {
752
      // link no longer used
753 754 755
#ifdef SCORE_DEBUG
      fprintf(stderr,"   freeing link\n");
#endif
756 757 758 759
      SSUB(SCORE_DIRECT_LINK);
    } else {
      // check to see if re freed up a violation, basically did
      // we remove the last of it's link type.
760 761
      if ((er.emulated && (pl.emulated == 0)) ||
	  ((! er.emulated) && pl.nonemulated == 0)) {
762
	// all good
763 764 765
#ifdef SCORE_DEBUG
	fprintf(stderr,"   users ok\n");
#endif
766 767 768 769
	SSUB(SCORE_DIRECT_LINK_PENALTY);
	vinfo.link_users--;
	violated--;
      }
Mac Newbold's avatar
Mac Newbold committed
770 771 772 773
    }
  }
  
  // bandwidth check
774 775 776 777 778 779 780
  int prev_bw = pl.bw_used;
  pl.bw_used -= er.bandwidth;
  if ((pl.bw_used <= pl.bandwidth) &&
      (prev_bw > pl.bandwidth)) {
#ifdef SCORE_DEBUG
    fprintf(stderr,"   went under bandwidth (%d <= %d)\n",
	    pl.bw_used,pl.bandwidth);
Mac Newbold's avatar
Mac Newbold committed
781
#endif
782 783 784
    violated--;
    vinfo.bandwidth--;
    SSUB(SCORE_OVER_BANDWIDTH);
Mac Newbold's avatar
Mac Newbold committed
785
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
786

787
  er.type = tb_vlink::LINK_UNKNOWN;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
788 789
}

790
double fd_score(tb_vnode &vnoder,tb_pnode &pnoder,int *fd_violated)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
791 792
{
  double fd_score=0;
793 794 795 796
  (*fd_violated)=0;
  
  seq_item desire;
  seq_item feature;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
797
  double value;
798 799 800 801 802 803 804 805
  for (desire = vnoder.desires.min_item();desire;
       desire = vnoder.desires.succ(desire)) {
    feature = pnoder.features.lookup(vnoder.desires.key(desire));
#ifdef SCORE_DEBUG
    cerr << "  desire = " << vnoder.desires.key(desire) \
	 << " " << vnoder.desires.inf(desire) << "\n";
#endif
    if (!feature) {
Christopher Alfeld's avatar
 
Christopher Alfeld committed
806
      // Unmatched desire.  Add cost.
807 808 809 810
#ifdef SCORE_DEBUG
      cerr << "    unmatched\n";
#endif
      value = vnoder.desires.inf(desire);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
811 812
      fd_score += SCORE_DESIRE*value;
      if (value >= 1) {
813
	(*fd_violated)++;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
814 815 816
      }
    }
  }
817 818 819 820 821 822 823 824
  for (feature = pnoder.features.min_item();feature;
       feature = pnoder.features.succ(feature)) {
    desire = vnoder.desires.lookup(pnoder.features.key(feature));
#ifdef SCORE_DEBUG
    cerr << "  feature = " << pnoder.features.key(feature) \
	 << " " << pnoder.features.inf(feature) << "\n";
#endif
    if (! desire) {
Christopher Alfeld's avatar
 
Christopher Alfeld committed
825
      // Unused feature.  Add weight
826 827 828 829
#ifdef SCORE_DEBUG
      cerr << "    unused\n";
#endif
      value = pnoder.features.inf(feature);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
830 831 832 833 834
      fd_score+=SCORE_FEATURE*value;
    }
  }

  return fd_score;
Mac Newbold's avatar
Mac Newbold committed
835
}