forest-net
an overlay networks for large-scale virtual worlds
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator
ComtInfo.cpp
Go to the documentation of this file.
1 
9 #include "ComtInfo.h"
10 
11 namespace forest {
12 
20 ComtInfo::ComtInfo(int maxComtree1, NetInfo& net1)
21  : maxComtree(maxComtree1), net(&net1) {
22  comtree = new ComtreeInfo[maxComtree+1];
23  comtreeMap = new IdMap(maxComtree);
24 }
25 
29 ComtInfo::~ComtInfo() {
30  for (int ctx = comtreeMap->firstId(); ctx != 0;
31  ctx = comtreeMap->nextId(ctx)) {
32  delete comtree[ctx].coreSet;
33  delete comtree[ctx].leafMap;
34  delete comtree[ctx].rtrMap;
35  pthread_cond_destroy(&comtree[ctx].busyCond);
36  }
37  delete [] comtree; delete comtreeMap;
38  pthread_mutex_destroy(&mapLock);
39 }
40 
42 bool ComtInfo::init() {
43  if (pthread_mutex_init(&mapLock,NULL) != 0) return false;
44  for (int ctx = 1; ctx <= maxComtree; ctx++) {
45  comtree[ctx].busyBit = false;
46  if (pthread_cond_init(&comtree[ctx].busyCond,NULL) != 0)
47  return false;
48  }
49  return true;
50 }
51 
58 int ComtInfo::getComtIndex(int comt) {
59  lockMap();
60  int ctx = comtreeMap->getId(comt);
61  if (ctx == 0) { unlockMap(); return 0; }
62  while (comtree[ctx].busyBit) { // wait until comtree is not busy
63  pthread_cond_wait(&comtree[ctx].busyCond,&mapLock);
64  ctx = comtreeMap->getId(comt);
65  if (ctx == 0) {
66  pthread_cond_signal(&comtree[ctx].busyCond);
67  unlockMap(); return 0;
68  }
69  }
70  comtree[ctx].busyBit = true; // set busyBit to lock comtree
71  unlockMap();
72  return ctx;
73 }
74 
79 void ComtInfo::releaseComtree(int ctx) {
80  lockMap();
81  comtree[ctx].busyBit = false;
82  pthread_cond_signal(&comtree[ctx].busyCond);
83  unlockMap();
84 }
85 
90 int ComtInfo::firstComtree() {
91  lockMap();
92  int ctx = comtreeMap->firstId();
93  if (ctx == 0) { unlockMap(); return 0; }
94  while (comtree[ctx].busyBit) {
95  pthread_cond_wait(&comtree[ctx].busyCond,&mapLock);
96  ctx = comtreeMap->firstId();
97  if (ctx == 0) {
98  pthread_cond_signal(&comtree[ctx].busyCond);
99  unlockMap(); return 0;
100  }
101  }
102  comtree[ctx].busyBit = true;
103  unlockMap();
104  return ctx;
105 }
106 
113 int ComtInfo::nextComtree(int ctx) {
114  lockMap();
115  int nuCtx = comtreeMap->nextId(ctx);
116  if (nuCtx == 0) {
117  comtree[ctx].busyBit = false;
118  pthread_cond_signal(&comtree[ctx].busyCond);
119  unlockMap();
120  return 0;
121  }
122  while (comtree[nuCtx].busyBit) {
123  pthread_cond_wait(&comtree[nuCtx].busyCond,&mapLock);
124  nuCtx = comtreeMap->nextId(ctx);
125  if (nuCtx == 0) {
126  comtree[ctx].busyBit = false;
127  pthread_cond_signal(&comtree[ctx].busyCond);
128  pthread_cond_signal(&comtree[nuCtx].busyCond);
129  unlockMap();
130  return 0;
131  }
132  }
133  comtree[nuCtx].busyBit = true;
134  comtree[ctx].busyBit = false;
135  pthread_cond_signal(&comtree[ctx].busyCond);
136  unlockMap();
137  return nuCtx;
138 }
139 
146 int ComtInfo::addComtree(int comt) {
147  lockMap();
148  int ctx = comtreeMap->addPair(comt);
149  if (ctx == 0) { unlockMap(); return 0; }
150  // since this is a newly allocated comtree, it cannot be
151  // locked by another thread
152  comtree[ctx].busyBit = true;
153  comtree[ctx].comtreeNum = comt;
154  comtree[ctx].coreSet = new set<fAdr_t>;
155  comtree[ctx].rtrMap = new map<fAdr_t,ComtRtrInfo>;
156  comtree[ctx].leafMap = new map<fAdr_t,ComtLeafInfo>;
157  unlockMap();
158  return ctx;
159 }
160 
168 bool ComtInfo::removeComtree(int ctx) {
169  lockMap();
170  if (!validComtIndex(ctx) || !comtree[ctx].busyBit) {
171  unlockMap(); return false;
172  }
173  comtreeMap->dropPair(comtree[ctx].comtreeNum);
174  comtree[ctx].comtreeNum = 0;
175  delete comtree[ctx].coreSet;
176  delete comtree[ctx].leafMap;
177  delete comtree[ctx].rtrMap;
178  comtree[ctx].busyBit = false;
179  unlockMap();
180  return true;
181 }
182 
188 bool ComtInfo::addNode(int ctx, fAdr_t fa) {
189  int nn = net->getNodeNum(fa);
190  if (nn != 0 && net->isRouter(nn)) {
191  map<fAdr_t,ComtRtrInfo>::iterator rp;
192  rp = comtree[ctx].rtrMap->find(fa);
193  if (rp != comtree[ctx].rtrMap->end()) return true;
194  pair<fAdr_t,ComtRtrInfo> newPair;
195  newPair.first = fa;
196  newPair.second.plnk = 0;
197  comtree[ctx].rtrMap->insert(newPair);
198  return true;
199  }
200  map<fAdr_t,ComtLeafInfo>::iterator lp;
201  lp = comtree[ctx].leafMap->find(fa);
202  if (lp != comtree[ctx].leafMap->end()) return true;
203  pair<fAdr_t,ComtLeafInfo> newPair;
204  newPair.first = fa;
205  newPair.second.plnkRates = comtree[ctx].leafDefRates;
206  if (nn != 0) {
207  int plnk = net->firstLinkAt(nn);
208  int parent = net->getPeer(nn,plnk);
209  newPair.second.parent = net->getNodeAdr(parent);
210  newPair.second.llnk = net->getLLnum(plnk,parent);
211  }
212  comtree[ctx].leafMap->insert(newPair);
213  return true;
214 }
215 
223 bool ComtInfo::removeNode(int ctx, fAdr_t fa) {
224  map<fAdr_t,ComtRtrInfo>::iterator np;
225  np = comtree[ctx].rtrMap->find(fa);
226  if (np != comtree[ctx].rtrMap->end()) {
227  int plnk = np->second.plnk;
228  if ((plnk == 0 && np->second.lnkCnt != 0) ||
229  (plnk != 0 && np->second.lnkCnt != 1))
230  return false;
231  if (plnk != 0) {
232  int parent = net->getPeer(net->getNodeNum(fa),plnk);
233  map<fAdr_t,ComtRtrInfo>::iterator pp;
234  pp = comtree[ctx].rtrMap->find(net->getNodeAdr(parent));
235  pp->second.lnkCnt--;
236  }
237  comtree[ctx].rtrMap->erase(np);
238  comtree[ctx].coreSet->erase(fa);
239  return true;
240  }
241  map<fAdr_t,ComtLeafInfo>::iterator lp;
242  lp = comtree[ctx].leafMap->find(fa);
243  map<fAdr_t,ComtRtrInfo>::iterator pp;
244  pp = comtree[ctx].rtrMap->find(lp->second.parent);
245  pp->second.lnkCnt--;
246  comtree[ctx].leafMap->erase(lp);
247  return true;
248 }
249 
250 
259 bool ComtInfo::adjustSubtreeRates(int ctx, fAdr_t rtrAdr, RateSpec& rs) {
260  int rtr = net->getNodeNum(rtrAdr);
261  map<fAdr_t,ComtRtrInfo>::iterator rp;
262  rp = comtree[ctx].rtrMap->find(rtrAdr);
263  int count = 0;
264  while (true) {
265  rp->second.subtreeRates.add(rs);
266  if (rp->second.plnk == 0) return true;
267  rtr = net->getPeer(rtr,rp->second.plnk);
268  rp = comtree[ctx].rtrMap->find(net->getNodeAdr(rtr));
269  if (count++ > 50) {
270  cerr << "ComtInfo::adjustSubtreeRates: excessively "
271  "long path detected in comtree "
272  << getComtree(ctx) << ", probably a cycle\n";
273  return false;
274  }
275  }
276 }
277 
303 bool ComtInfo::read(istream& in) {
304  int comtNum = 1; // comtNum = i for i-th comtree read
305 
306  string s, errMsg;
307  while (!in.eof()) {
308  if (!Util::skipBlank(in) || Util::verify(in,';')) break;
309  if (!Util::readWord(in, s)) {
310  cerr << "NetInfo:: read: syntax error: expected "
311  "(;) or keyword (router,leaf,link)\n";
312  return false;
313  }
314  if (s == "comtree") {
315  if (readComtree(in, errMsg) == 0) {
316  cerr << "ComtInfo::read: error when attempting "
317  " to read " << comtNum << "-th comtree "
318  "(" << errMsg << ")\n";
319  return false;
320  }
321  } else {
322  cerr << "ComtInfo::read: unrecognized word " << s
323  << " when attempting to read "
324  << comtNum << "-th comtree\n";
325  return false;
326  }
327  comtNum++;
328  }
329  return check() && setAllComtRates();
330 }
331 
344 comt_t ComtInfo::readComtree(istream& in, string& errMsg) {
345  comt_t comt; fAdr_t owner; fAdr_t root;
346  int core; vector<int> coreNodes;
347  bool autoConfig; RateSpec bbRates, leafRates;
348 
349  errMsg = "";
350  if (!Util::verify(in,'(',50)) {
351  errMsg = "syntax error, expected left paren";
352  return 0;
353  }
354  // read comtree number
355  Util::skipBlank(in);
356  in >> comt;
357  if (in.fail() || !Util::verify(in,',',20)) {
358  errMsg = "could not read comtree number";
359  return 0;
360  }
361  // read owner name
362  Util::skipBlank(in);
363  string s;
364  if (!Util::readWord(in,s) || !Util::verify(in,',',20) ||
365  (owner = net->getNodeNum(s)) == 0) {
366  errMsg = "could not read owner name";
367  return 0;
368  }
369  // read root node name
370  Util::skipBlank(in);
371  if (!Util::readWord(in,s) || !Util::verify(in,',',20) ||
372  (root = net->getNodeNum(s)) == 0) {
373  errMsg = "could not read root node name";
374  return 0;
375  }
376  // read backbone configuration mode
377  Util::skipBlank(in);
378  if (!Util::readWord(in,s)) {
379  errMsg = "could not read backbone configuration mode";
380  return 0;
381  }
382  if (s == "auto") autoConfig = true;
383  else if (s == "manual") autoConfig = false;
384  else {
385  errMsg = "invalid backbone configuration mode " + s;
386  return 0;
387  }
388  // read default rate specs
389  Util::skipBlank(in);
390  if (!Util::verify(in,',',20) || !readRateSpec(in,bbRates)) {
391  errMsg = "could not backbone default rates";
392  return 0;
393  }
394  Util::skipBlank(in);
395  if (!Util::verify(in,',',20) || !readRateSpec(in,leafRates)) {
396  errMsg = "could not read leaf default rates";
397  return 0;
398  }
399  // read list of core nodes (may be empty)
400  Util::skipBlank(in);
401  if (Util::verify(in,',',20)) { // read list of additional core nodes
402  Util::skipBlank(in);
403  if (Util::verify(in,'(',20)) {
404  if (!Util::verify(in,')',20)) {
405  while (true) {
406  Util::skipBlank(in);
407  string s;
408  if (!Util::readWord(in,s)) {
409  errMsg = "could not read core "
410  "node name";
411  return 0;
412  }
413  if ((core = net->getNodeNum(s)) == 0) {
414  errMsg = "invalid core node "
415  "name " + s;
416  return 0;
417  }
418  coreNodes.push_back(core);
419  if (Util::verify(in,')',20)) break;
420  if (!Util::verify(in,',',20)) {
421  errMsg = "syntax error in list "
422  "of core nodes "
423  "after " + s;
424  return 0;
425  }
426  }
427  }
428  }
429  }
430  // read list of links (may be empty)
431  vector<LinkMod> links;
432  Util::skipBlank(in);
433  LinkMod lm;
434  if (Util::verify(in,',',20)) {
435  int lnk; int child;
436  RateSpec rs; rs.set(-1);
437  if (!readLink(in,lnk,rs,child,errMsg)) return 0;
438  lm.set(lnk,child,rs);
439  links.push_back(lm);
440  while (Util::verify(in,',',20)) {
441  rs.set(-1);
442  if (!readLink(in,lnk,rs,child,errMsg)) return 0;
443  lm.set(lnk,child,rs);
444  links.push_back(lm);
445  }
446  }
447  if (!Util::verify(in,')',20)) {
448  errMsg = "syntax error at end of link list, expected "
449  "right paren";
450  return 0;
451  }
452  int ctx;
453  if ((ctx = addComtree(comt)) == 0) {
454  errMsg = "could not allocate new comtree";
455  return 0;
456  }
457  releaseComtree(ctx); // this is assumed to be only thread with
458  // access to comtree, so locking not needed
459 
460  fAdr_t ownerAdr = net->getNodeAdr(owner);
461  fAdr_t rootAdr = net->getNodeAdr(root);
462 
463  // configure comtree
464  if (!setOwner(ctx,ownerAdr) || !setRoot(ctx,rootAdr)) {
465  errMsg = "could not configure comtree";
466  return 0;
467  }
468  setConfigMode(ctx,autoConfig);
469  getDefLeafRates(ctx) = leafRates;
470  getDefBbRates(ctx) = bbRates;
471 
472  if (!addNode(ctx,rootAdr) || !addCoreNode(ctx,rootAdr)) {
473  errMsg = "could not add root to comtree";
474  return 0;
475  }
476  for (unsigned int i = 0; i < coreNodes.size(); i++) {
477  fAdr_t cnAdr = net->getNodeAdr(coreNodes[i]);
478  if (!addNode(ctx,cnAdr) || !addCoreNode(ctx,cnAdr)) {
479  errMsg = "could not add core node to comtree";
480  return 0;
481  }
482  }
483 
484  for (unsigned int i = 0; i < links.size(); i++) {
485  int lnk = links[i].lnk;
486  int child = links[i].child;
487  int parent = net->getPeer(child,lnk);
488  fAdr_t childAdr = net->getNodeAdr(child);
489  fAdr_t parentAdr = net->getNodeAdr(parent);
490  RateSpec rs = links[i].rs;
491 
492  addNode(ctx,childAdr); addNode(ctx,parentAdr);
493  if (net->isLeaf(child)) {
494  map<fAdr_t,ComtLeafInfo>::iterator cp;
495  cp = comtree[ctx].leafMap->find(childAdr);
496  if (rs.bitRateUp == -1) rs = leafRates;
497  cp->second.plnkRates = rs;
498  } else {
499  map<fAdr_t,ComtRtrInfo>::iterator cp;
500  cp = comtree[ctx].rtrMap->find(childAdr);
501  cp->second.plnk = lnk; cp->second.lnkCnt++;
502  if (rs.bitRateUp == -1) rs = bbRates;
503  else cp->second.frozen = true;
504  cp->second.plnkRates = rs;
505  rs = cp->second.subtreeRates;
506  }
507  adjustSubtreeRates(ctx,parentAdr,rs);
508  map<fAdr_t,ComtRtrInfo>::iterator pp;
509  pp = comtree[ctx].rtrMap->find(parentAdr);
510  pp->second.lnkCnt++;
511  }
512 
513  return true;
514 }
515 
521 bool ComtInfo::readRateSpec(istream& in, RateSpec& rs) {
522  int bru, brd, pru, prd;
523  if (!Util::verify(in,'(',50)) return false;
524  in >> bru; if (in.fail()) return false;
525  if (!Util::verify(in,',',20)) return false;
526  in >> brd; if (in.fail()) return false;
527  if (!Util::verify(in,',',20)) return false;
528  in >> pru; if (in.fail()) return false;
529  if (!Util::verify(in,',',20)) return false;
530  in >> prd; if (in.fail()) return false;
531  if (!Util::verify(in,')',20)) return false;
532  rs.set(bru,brd,pru,prd);
533  return true;
534 }
535 
546 bool ComtInfo::readLink(istream& in, int& lnk, RateSpec& rs, int& child,
547  string& errMsg) {
548  string nameL, nameR; int numL, numR;
549 
550  errMsg = "";
551  // read the link endpoints
552  if (!Util::verify(in,'(',50) ||
553  !readLinkEndpoint(in,nameL,numL) || !Util::verify(in,',',20)) {
554  errMsg = "could not first link endpoint";
555  return false;
556  }
557  if (!readLinkEndpoint(in,nameR,numR)) {
558  errMsg = "could not read second link endpoint";
559  return false;
560  }
561  // find the link number in the NetInfo object
562  if ((child = net->getNodeNum(nameL)) == 0) {
563  errMsg = "invalid name for link endpoint " + nameL;
564  return false;
565  }
566  int parent;
567  if ((parent = net->getNodeNum(nameR)) == 0) {
568  errMsg = "invalid name for link endpoint " + nameR;
569  return false;
570  }
571  if (!net->isRouter(parent)) {
572  errMsg = "invalid link: first node must be child in comtree";
573  return false;
574  }
575  lnk = net->getLinkNum(child,numL);
576  if (lnk != net->getLinkNum(parent,numR) || lnk == 0) {
577  stringstream ss;
578  ss << "detected invalid link (" << nameL;
579  if (numL != 0) ss << "." << numL;
580  ss << "," << nameR;
581  if (numR != 0) ss << "." << numR;
582  ss << ")";
583  errMsg = ss.str();
584  return false;
585  }
586  if (Util::verify(in,',',20)) {
587  if (!readRateSpec(in,rs)) {
588  errMsg = "could not read rate specification for link";
589  return false;
590  }
591  }
592  if (!Util::verify(in,')',20)) {
593  errMsg = "syntax error, expected right paren";
594  return false;
595  }
596  return true;
597 }
598 
605 bool ComtInfo::readLinkEndpoint(istream& in, string& name, int& num) {
606  if (!Util::readWord(in,name)) return false;
607  num = 0;
608  if (Util::verify(in,'.')) {
609  in >> num;
610  if (in.fail() || num < 1) return false;
611  }
612  return true;
613 }
617 bool ComtInfo::check() {
618  bool status = true;
619  for (int ctx = firstComtree(); ctx != 0; ctx = nextComtree(ctx)) {
620  int comt = getComtree(ctx);
621  fAdr_t rootAdr = getRoot(ctx);
622  int root = net->getNodeNum(rootAdr);
623 
624  // first check that every leaf in comtree has a parent
625  // that is a router in the comtree
626  map<fAdr_t,ComtLeafInfo>::iterator lp;
627  for (lp = comtree[ctx].leafMap->begin();
628  lp != comtree[ctx].leafMap->end(); lp++) {
629  if (!isComtRtr(ctx,getParent(ctx,lp->first))) {
630  int leaf = net->getNodeNum(lp->first);
631  string leafName;
632  if (leaf != 0) net->getNodeName(leaf,leafName);
633  else Forest::fAdr2string(leaf,leafName);
634  cerr << "ComtInfo::check: comtree " << comt
635  << " has leaf " << leafName << " whose "
636  "parent is not a router in comtree\n";
637  status = false;
638  }
639  }
640  // next, check that at most one router in comtree lacks a
641  // parent
642  map<fAdr_t,ComtRtrInfo>::iterator rp;
643  int cnt = 0;
644  for (rp = comtree[ctx].rtrMap->begin();
645  rp != comtree[ctx].rtrMap->end(); rp++) {
646  if (getParent(ctx,rp->first) == 0) cnt++;
647  }
648  if (cnt != 1) {
649  cerr << "ComtInfo::check: comtree " << comt
650  << " has " << cnt << " routers with no parent\n";
651  status = false;
652  }
653 
654  // check that the comtree backbone topology is really a tree
655  // by doing a breadth-first search from the root;
656  // while we're at it, make sure the parent of every
657  // core node is a core node and that the zip codes
658  // of routers within the comtree are contiguous
659  queue<int> pending; pending.push(root);
660  map<fAdr_t,int> plink; plink[root] = 0;
661  set<fAdr_t> zipSet;
662  zipSet.insert(Forest::zipCode(rootAdr));
663  unsigned int nodeCount = 0;
664  while (!pending.empty()) {
665  int u = pending.front(); pending.pop();
666  fAdr_t uAdr = net->getNodeAdr(u);
667  nodeCount++;
668  bool foundCycle = false;
669  int uzip = Forest::zipCode(net->getNodeAdr(u));
670  for (int lnk = net->firstLinkAt(u); lnk != 0;
671  lnk = net->nextLinkAt(u,lnk)) {
672  int v = net->getPeer(u,lnk);
673  if (!net->isRouter(v)) continue;
674  fAdr_t vAdr = net->getNodeAdr(v);
675  if (!isComtNode(ctx,vAdr)) continue;
676  if (getPlink(ctx,vAdr) != lnk) continue;
677  if (lnk == plink[u]) continue;
678  int vzip = Forest::zipCode(vAdr);
679  if (plink.find(v) != plink.end()) {
680  cerr << "ComtInfo::check: "
681  "comtree " << comt
682  << " contains a cycle\n";
683  foundCycle = true;
684  break;
685  }
686  plink[v] = lnk;
687  pending.push(v);
688  // now check that if v is in core, so is u
689  if (isCoreNode(ctx,vAdr) &&
690  !isCoreNode(ctx,uAdr)) {
691  string s;
692  cerr << "ComtInfo::check: comtree "
693  << comt << " contains a core node "
694  << net->getNodeName(v,s)
695  << " whose parent is not a "
696  "core node\n";
697  status = false;
698  }
699  // now check that if v has a different zip code
700  // than u, that we haven't already seen this zip
701  if (vzip != uzip) {
702  if (zipSet.find(vzip) != zipSet.end()) {
703  cerr << "ComtInfo::check: zip "
704  "code " << vzip <<
705  " is non-contiguous in "
706  "comtree " << comt
707  << "\n";
708  status = false;
709  } else {
710  zipSet.insert(vzip);
711  }
712  }
713  }
714  if (foundCycle) { status = false; break; }
715  }
716  if (nodeCount != comtree[ctx].rtrMap->size()) {
717  cerr << "ComtInfo::check: comtree " << comt
718  << " not connected\n";
719  status = false;
720  }
721  }
722  return status;
723 }
724 
725 bool ComtInfo::checkLinkCounts(int ctx) {
726  int n = net->getMaxRouter();
727  int *lnkCounts = new int[n+1];
728 
729  bool status = true;
730  for (int i = 1; i <= n; i++) lnkCounts[i] = 0;
731 
732  int comt = getComtree(ctx);
733 
734  // first count links from leaf nodes
735  map<fAdr_t,ComtLeafInfo>::iterator lp;
736  for (lp = comtree[ctx].leafMap->begin();
737  lp != comtree[ctx].leafMap->end(); lp++) {
738  fAdr_t padr = getParent(ctx,lp->first);
739  int parent = net->getNodeNum(padr);
740  lnkCounts[parent]++;
741  }
742  // next, count links to other routers
743  map<fAdr_t,ComtRtrInfo>::iterator rp;
744  for (rp = comtree[ctx].rtrMap->begin();
745  rp != comtree[ctx].rtrMap->end(); rp++) {
746  fAdr_t radr = rp->first;
747  int rtr = net->getNodeNum(radr);
748  fAdr_t padr = getParent(ctx,radr);
749  if (padr == 0) continue;
750  int parent = net->getNodeNum(padr);
751  lnkCounts[parent]++;
752  lnkCounts[rtr]++;
753  }
754 
755  // now check stored link counts for routers
756  for (rp = comtree[ctx].rtrMap->begin();
757  rp != comtree[ctx].rtrMap->end(); rp++) {
758  fAdr_t radr = rp->first;
759  int rtr = net->getNodeNum(radr);
760  if (lnkCounts[rtr] != rp->second.lnkCnt) {
761  string s;
762  cerr << "router " << net->getNodeName(rtr,s)
763  << " has " << lnkCounts[rtr]
764  << " links in comtree " << comt
765  << ", but recorded lnkCnt is "
766  << rp->second.lnkCnt;
767  status = false;
768  }
769  }
770  return status;
771 }
772 
773 bool ComtInfo::checkSubtreeRates(int ctx) {
774  int n = net->getMaxRouter();
775  RateSpec *subtreeRates = new RateSpec[n+1];
776 
777  bool status = true;
778  for (int i = 1; i <= n; i++) subtreeRates[i].set(0);
779 
780  int comt = getComtree(ctx);
781  fAdr_t rootAdr = getRoot(ctx);
782  int root = net->getNodeNum(rootAdr);
783 
784  // compute bottom-up from leaf nodes
785  // check for negative rates while we're at it
786  map<fAdr_t,ComtLeafInfo>::iterator lp;
787  for (lp = comtree[ctx].leafMap->begin();
788  lp != comtree[ctx].leafMap->end(); lp++) {
789  RateSpec& prates = lp->second.plnkRates;
790  if (prates.bitRateUp <= 0 || prates.bitRateDown <= 0 ||
791  prates.pktRateUp <= 0 || prates.pktRateDown <= 0) {
792  string s1, s2;
793  int lnk = net->getLinkNum(
794  net->getNodeNum(lp->second.parent),
795  lp->second.llnk);
796  cerr << "detected non-positive comtree link rate for "
797  << comt << " link " << net->link2string(lnk,s1)
798  << " rateSpec=" << prates.toString(s2) << endl;
799  status = false;
800  }
801  fAdr_t radr = getParent(ctx,lp->first);
802  while (true) {
803  int rtr = net->getNodeNum(radr);
804  subtreeRates[rtr].add(prates);
805  if (rtr == root) break;
806  radr = getParent(ctx,radr);
807  }
808  }
809 
810  // now check stored subtree rates
811  map<fAdr_t,ComtRtrInfo>::iterator rp;
812  for (rp = comtree[ctx].rtrMap->begin();
813  rp != comtree[ctx].rtrMap->end(); rp++) {
814  fAdr_t radr = rp->first;
815  int rtr = net->getNodeNum(radr);
816  if (!subtreeRates[rtr].equals(rp->second.subtreeRates)) {
817  string s1, s2, s3;
818  cerr << "router " << net->getNodeName(rtr,s1)
819  << " has subtree rate "
820  << subtreeRates[rtr].toString(s2)
821  << " in comtree " << comt << ", but recorded"
822  << " value is "
823  << rp->second.subtreeRates.toString(s3) << endl;
824  status = false;
825  }
826  }
827  return status;
828 }
829 
830 bool ComtInfo::checkLinkRates(int ctx) {
831  if (!getConfigMode(ctx)) return true;
832 
833  bool status = true;
834  int comt = getComtree(ctx);
835  fAdr_t rootAdr = getRoot(ctx);
836 
837  map<fAdr_t,ComtRtrInfo>::iterator rp;
838  rp = comtree[ctx].rtrMap->find(rootAdr);
839  RateSpec& rootRates = rp->second.subtreeRates;
840 
841  for (rp = comtree[ctx].rtrMap->begin();
842  rp != comtree[ctx].rtrMap->end(); rp++) {
843  if (rp->second.frozen) continue;
844  int lnk = rp->second.plnk;
845  if (lnk == 0) continue;
846  fAdr_t rtr = rp->first;
847  RateSpec rs(0);
848  RateSpec& srates = rp->second.subtreeRates;
849  RateSpec trates = rootRates; trates.subtract(srates);
850  if (isCoreNode(ctx,rtr)) {
851  rs.set( srates.bitRateUp,trates.bitRateUp,
852  srates.pktRateUp,trates.pktRateUp);
853  } else {
854  rs.set( srates.bitRateUp,
855  min(srates.bitRateDown,trates.bitRateUp),
856  srates.pktRateUp,
857  min(srates.pktRateDown,trates.pktRateUp));
858  }
859  if (!rs.equals(rp->second.plnkRates)) {
860  string s1, s2, s3;
861  cerr << "detected inconsistent comtree link rates in "
862  << comt << " link " << net->link2string(lnk,s1)
863  << " computed rates: " << rs.toString(s2)
864  << " and stored rates: "
865  << rp->second.plnkRates.toString(s3) << endl;
866  status = false;
867  }
868  }
869  return status;
870 }
871 
877 bool ComtInfo::setAllComtRates() {
878  for (int ctx = firstComtree(); ctx != 0; ctx = nextComtree(ctx)) {
879  if (!setComtRates(ctx)) return false;
880  }
881  return true;
882 }
883 
892 bool ComtInfo::setComtRates(int ctx) {
893  if (!validComtIndex(ctx)) return false;
894  if (getConfigMode(ctx)) setAutoConfigRates(ctx);
895  if (!checkComtRates(ctx)) {
896  cerr << "network lacks capacity for comtree "
897  << getComtree(ctx) << endl;
898  return false;
899  }
900  provision(ctx);
901  return true;
902 }
903 
910 void ComtInfo::setAutoConfigRates(int ctx) {
911  fAdr_t root = getRoot(ctx);
912  map<fAdr_t,ComtRtrInfo>::iterator rp;
913  rp = comtree[ctx].rtrMap->find(root);
914  RateSpec& rootRates = rp->second.subtreeRates;
915  for (rp = comtree[ctx].rtrMap->begin();
916  rp != comtree[ctx].rtrMap->end(); rp++) {
917  if (rp->second.frozen) continue;
918  int lnk = rp->second.plnk;
919  if (lnk == 0) continue;
920  fAdr_t rtr = rp->first;
921  RateSpec& rs = rp->second.plnkRates;
922  RateSpec& srates = rp->second.subtreeRates;
923  RateSpec trates = rootRates; trates.subtract(srates);
924  if (isCoreNode(ctx,rtr)) {
925  rs.set( srates.bitRateUp,trates.bitRateUp,
926  srates.pktRateUp,trates.pktRateUp);
927  } else {
928  rs.set( srates.bitRateUp,
929  min(srates.bitRateDown,trates.bitRateUp),
930  srates.pktRateUp,
931  min(srates.pktRateDown,trates.pktRateUp));
932  }
933  }
934  return;
935 }
936 
944 bool ComtInfo::checkComtRates(int ctx) {
945  // first check parent links at routers
946  map<fAdr_t,ComtRtrInfo>::iterator rp;
947  for (rp = comtree[ctx].rtrMap->begin();
948  rp != comtree[ctx].rtrMap->end(); rp++) {
949  fAdr_t rtr = rp->first; int lnk = rp->second.plnk;
950  if (lnk == 0) continue;
951  RateSpec rs = rp->second.plnkRates;
952  if (rtr != net->getLeft(lnk)) rs.flip();
953  RateSpec availRates = net->getAvailRates(lnk);
954  if (!rs.leq(availRates)) { return false; }
955  }
956  // then check access links, for static leaf nodes
957  map<fAdr_t,ComtLeafInfo>::iterator lp;
958  for (lp = comtree[ctx].leafMap->begin();
959  lp != comtree[ctx].leafMap->end(); lp++) {
960  fAdr_t leafAdr = lp->first;
961  int leaf = net->getNodeNum(leafAdr);
962  if (leaf == 0) continue;
963  int lnk = net->firstLinkAt(leaf);
964  RateSpec rs = lp->second.plnkRates;
965  if (leaf != net->getLeft(lnk)) rs.flip();
966  RateSpec availRates = net->getAvailRates(lnk);
967  if (!rs.leq(availRates)) { return false; }
968  }
969  return true;
970 }
971 
979 void ComtInfo::provision(int ctx) {
980  map<fAdr_t,ComtRtrInfo>::iterator rp;
981  for (rp = comtree[ctx].rtrMap->begin();
982  rp != comtree[ctx].rtrMap->end(); rp++) {
983  fAdr_t rtr = rp->first; int lnk = rp->second.plnk;
984  if (lnk == 0) continue;
985  RateSpec rs = rp->second.plnkRates;
986  if (rtr != net->getLeft(lnk)) rs.flip();
987  net->getAvailRates(lnk).subtract(rs);
988  }
989  // provision statically configured leaf nodes
990  map<fAdr_t,ComtLeafInfo>::iterator lp;
991  for (lp = comtree[ctx].leafMap->begin();
992  lp != comtree[ctx].leafMap->end(); lp++) {
993  fAdr_t leafAdr = lp->first;
994  int leaf = net->getNodeNum(leafAdr);
995  if (leaf == 0) continue;
996  int lnk = net->firstLinkAt(leaf);
997  RateSpec rs = lp->second.plnkRates;
998  if (leaf != net->getLeft(lnk)) rs.flip();
999  net->getAvailRates(lnk).subtract(rs);
1000  }
1001 }
1002 
1008 void ComtInfo::unprovision(int ctx) {
1009  map<fAdr_t,ComtRtrInfo>::iterator rp;
1010  for (rp = comtree[ctx].rtrMap->begin();
1011  rp != comtree[ctx].rtrMap->end(); rp++) {
1012  fAdr_t rtr = rp->first; int lnk = rp->second.plnk;
1013  if (lnk == 0) continue;
1014  RateSpec rs = rp->second.plnkRates;
1015  if (rtr != net->getLeft(lnk)) rs.flip();
1016  net->getAvailRates(lnk).add(rs);
1017  }
1018  map<fAdr_t,ComtLeafInfo>::iterator lp;
1019  for (lp = comtree[ctx].leafMap->begin();
1020  lp != comtree[ctx].leafMap->end(); lp++) {
1021  fAdr_t leafAdr = lp->first;
1022  int leaf = net->getNodeNum(leafAdr);
1023  if (leaf == 0) continue;
1024  int lnk = net->firstLinkAt(leaf);
1025  RateSpec rs = lp->second.plnkRates;
1026  if (leaf != net->getLeft(lnk)) rs.flip();
1027  net->getAvailRates(lnk).add(rs);
1028  }
1029 }
1030 
1047 int ComtInfo::findPath(int ctx, int src, RateSpec& rs, list<LinkMod>& path) {
1048  path.clear();
1049  fAdr_t srcAdr = net->getNodeAdr(src);
1050  if (isComtNode(ctx,srcAdr)) return src;
1051  int n = 0;
1052  for (fAdr_t r = net->firstRouter(); r != 0; r = net->nextRouter(r)) {
1053  n = max(r,n);
1054  }
1055  Heap h(n); int d[n+1];
1056  int plnk[n+1]; // note: reverse from direction in comtree
1057  for (fAdr_t r = net->firstRouter(); r != 0; r = net->nextRouter(r)) {
1058  plnk[r] = 0; d[r] = BIGINT;
1059  }
1060  RateSpec availRates;
1061  d[src] = 0;
1062  h.insert(src,d[src]);
1063  while (!h.empty()) {
1064  fAdr_t r = h.deletemin();
1065  for (int lnk = net->firstLinkAt(r); lnk != 0;
1066  lnk = net->nextLinkAt(r,lnk)) {
1067  if (lnk == plnk[r]) continue;
1068  int peer = net->getPeer(r,lnk);
1069  if (!net->isRouter(peer)) continue;
1070  // if this link cannot take the default backbone
1071  // rate for this comtree, ignore it
1072  availRates = net->getAvailRates(lnk);
1073  if (r != net->getLeft(lnk)) availRates.flip();
1074  if (!rs.leq(availRates)) continue;
1075  if (isComtNode(ctx,net->getNodeAdr(peer))) { // done
1076  plnk[peer] = lnk;
1077  int u = peer;
1078  for (int pl = plnk[u]; pl != 0; pl = plnk[u]) {
1079  int v = net->getPeer(u,plnk[u]);
1080  LinkMod lm(pl,v,rs);
1081  path.push_front(lm);
1082  u = v;
1083  }
1084  return peer;
1085  }
1086  if (d[peer] > d[r] + net->getLinkLength(lnk)) {
1087  plnk[peer] = lnk;
1088  d[peer] = d[r] + net->getLinkLength(lnk);
1089  if (h.member(peer)) h.changekey(peer,d[peer]);
1090  else h.insert(peer,d[peer]);
1091  }
1092  }
1093  }
1094  return 0;
1095 }
1096 
1114 bool ComtInfo::findRootPath(int ctx, int src, RateSpec& rs, vector<int>& path) {
1115  fAdr_t srcAdr = net->getNodeAdr(src);
1116 
1117  path.clear();
1118  // if src is in comtree, just return path to root
1119  if (isComtNode(ctx,srcAdr)) {
1120  int u = src;
1121  int pl = getPlink(ctx,net->getNodeAdr(u));
1122  while (pl != 0) {
1123  path.push_back(net->getLLnum(pl,u));
1124  u = net->getPeer(u,pl);
1125  pl = getPlink(ctx,net->getNodeAdr(u));
1126  }
1127  return true;
1128  }
1129 
1130  int n = 0;
1131  for (fAdr_t r = net->firstRouter(); r != 0; r = net->nextRouter(r)) {
1132  n = max(r,n);
1133  }
1134  Heap h(n); int d[n+1];
1135  int plnk[n+1]; // note: reverse from direction in comtree
1136  for (fAdr_t r = net->firstRouter(); r != 0; r = net->nextRouter(r)) {
1137  plnk[r] = 0; d[r] = BIGINT;
1138  }
1139  RateSpec availRates;
1140  d[src] = 0;
1141  h.insert(src,d[src]);
1142  while (!h.empty()) {
1143  fAdr_t r = h.deletemin();
1144  for (int lnk = net->firstLinkAt(r); lnk != 0;
1145  lnk = net->nextLinkAt(r,lnk)) {
1146  if (lnk == plnk[r]) continue;
1147  int peer = net->getPeer(r,lnk);
1148  if (!net->isRouter(peer)) continue;
1149  // if this link cannot take the specified rate spec,
1150  // ignore it
1151  availRates = net->getAvailRates(lnk);
1152  if (r != net->getLeft(lnk)) availRates.flip();
1153  if (!rs.leq(availRates)) continue;
1154  if (isComtNode(ctx,net->getNodeAdr(peer))) { // done
1155  // copy spt path to path vector in reverse order
1156  plnk[peer] = lnk;
1157  int u = peer;
1158  int len = 0;
1159  for (int pl = plnk[u]; pl != 0; pl = plnk[u]) {
1160  len++; u = net->getPeer(u,pl);
1161  }
1162  path.resize(len);
1163  int i = len-1; u = peer;
1164  for (int pl = plnk[u]; pl != 0; pl = plnk[u]) {
1165  u = net->getPeer(u,pl);
1166  path[i--] = net->getLLnum(pl,u);
1167  }
1168 
1169  // continue up the comtree
1170  u = peer;
1171  int pl = getPlink(ctx,net->getNodeAdr(u));
1172  while (pl != 0) {
1173  path.push_back(net->getLLnum(pl,u));
1174  u = net->getPeer(u,pl);
1175  pl = getPlink(ctx,net->getNodeAdr(u));
1176  }
1177  return true;
1178  }
1179  if (d[peer] > d[r] + net->getLinkLength(lnk)) {
1180  plnk[peer] = lnk;
1181  d[peer] = d[r] + net->getLinkLength(lnk);
1182  if (h.member(peer)) h.changekey(peer,d[peer]);
1183  else h.insert(peer,d[peer]);
1184  }
1185  }
1186  }
1187  return false;
1188 }
1189 
1200 void ComtInfo::addPath(int ctx, list<LinkMod>& path) {
1201  if (path.begin() == path.end()) return;
1202  list<LinkMod>::iterator pp;
1203  for (pp = path.begin(); pp != path.end(); pp++) {
1204  // add lnk to the comtree in net
1205  int child = pp->child; int lnk = pp->lnk;
1206  RateSpec rs = pp->rs;
1207  int parent = net->getPeer(child,lnk);
1208  fAdr_t childAdr = net->getNodeAdr(child);
1209  fAdr_t parentAdr = net->getNodeAdr(parent);
1210  addNode(ctx,childAdr); addNode(ctx,parentAdr);
1211  setPlink(ctx,childAdr,lnk); thaw(ctx,childAdr);
1212  getLinkRates(ctx,childAdr) = rs;
1213  if (child != net->getLeft(lnk)) rs.flip();
1214  net->getAvailRates(lnk).subtract(rs);
1215  }
1216  return;
1217 }
1218 
1226 void ComtInfo::removePath(int ctx, list<LinkMod>& path) {
1227  if (path.begin() == path.end()) return;
1228  list<LinkMod>::iterator pp;
1229  for (pp = path.begin(); pp != path.end(); pp++) {
1230  fAdr_t childAdr = net->getNodeAdr(pp->child);
1231  RateSpec rs = getLinkRates(ctx,childAdr);
1232  if (pp->child != net->getLeft(pp->lnk)) rs.flip();
1233  net->getAvailRates(pp->lnk).add(rs);
1234  removeNode(ctx,childAdr);
1235  }
1236  return;
1237 }
1238 
1250 bool ComtInfo::computeMods(int ctx, list<LinkMod>& modList) {
1251  fAdr_t root = getRoot(ctx);
1252  map<fAdr_t,ComtRtrInfo>::iterator rp;
1253  rp = comtree[ctx].rtrMap->find(root);
1254  modList.clear();
1255  bool status = computeMods(ctx,root,rp->second.subtreeRates,modList);
1256  return status;
1257 }
1258 
1275 bool ComtInfo::computeMods(int ctx, fAdr_t radr, RateSpec& rootRates,
1276  list<LinkMod>& modList) {
1277  int rnum = net->getNodeNum(radr);
1278  if (!net->isRouter(rnum)) return true;
1279  map<fAdr_t,ComtRtrInfo>::iterator rp;
1280  rp = comtree[ctx].rtrMap->find(radr);
1281  int plnk = rp->second.plnk;
1282  if (plnk != 0 && !isFrozen(ctx,radr)) {
1283  // determine the required rates on link to parent
1284  LinkMod nuMod;
1285  nuMod.child = rnum; nuMod.lnk = plnk;
1286  RateSpec& srates = rp->second.subtreeRates;
1287  RateSpec trates = rootRates; trates.subtract(srates);
1288  if (isCoreNode(ctx,radr)) {
1289  nuMod.rs.set(srates.bitRateUp,trates.bitRateUp,
1290  srates.pktRateUp,trates.pktRateUp);
1291  } else {
1292  nuMod.rs.set(srates.bitRateUp,
1293  min(srates.bitRateDown,trates.bitRateUp),
1294  srates.pktRateUp,
1295  min(srates.pktRateDown,trates.pktRateUp));
1296  }
1297  nuMod.rs.subtract(rp->second.plnkRates);
1298  if (nuMod.rs.isZero()) return true; // no change needed
1299  RateSpec availRates = net->getAvailRates(plnk);
1300  if (rnum != net->getLeft(plnk)) availRates.flip();
1301  if (!nuMod.rs.leq(availRates)) return false;
1302  modList.push_back(nuMod);
1303  }
1304 
1305  // Now, do subtrees; note that this method is going to be
1306  // slow for comtrees with very large backbones; only way to
1307  // fix it is to add child and sibling pointers; later, maybe
1308  for (rp = comtree[ctx].rtrMap->begin();
1309  rp != comtree[ctx].rtrMap->end(); rp++) {
1310  if (radr != getParent(ctx,rp->first)) continue;
1311  if (!computeMods(ctx,rp->first,rootRates,modList))
1312  return false;
1313  }
1314  return true;
1315 }
1316 
1326 void ComtInfo::provision(int ctx, list<LinkMod>& modList) {
1327  list<LinkMod>::iterator mlp;
1328  RateSpec delta;
1329  for (mlp = modList.begin(); mlp != modList.end(); mlp++) {
1330  int rtr = mlp->child; fAdr_t rtrAdr = net->getNodeAdr(rtr);
1331  int plnk = mlp->lnk; delta = mlp->rs;
1332  map<fAdr_t,ComtRtrInfo>::iterator rp;
1333  rp = comtree[ctx].rtrMap->find(rtrAdr);
1334  rp->second.plnkRates.add(delta);
1335  if (rtr != net->getLeft(plnk)) delta.flip();
1336  net->getAvailRates(plnk).subtract(delta);
1337  }
1338 }
1339 
1347 void ComtInfo::unprovision(int ctx, list<LinkMod>& modList) {
1348  list<LinkMod>::iterator mlp;
1349  RateSpec delta;
1350  for (mlp = modList.begin(); mlp != modList.end(); mlp++) {
1351  int rtr = mlp->child; fAdr_t rtrAdr = net->getNodeAdr(rtr);
1352  int plnk = mlp->lnk; delta = mlp->rs;
1353  map<fAdr_t,ComtRtrInfo>::iterator rp;
1354  rp = comtree[ctx].rtrMap->find(rtrAdr);
1355  rp->second.plnkRates.add(delta);
1356  if (rtr != net->getLeft(plnk)) delta.flip();
1357  net->getAvailRates(plnk).add(delta);
1358  }
1359 }
1360 
1361 
1368 string& ComtInfo::toString(string& s) {
1369  s = "";
1370  for (int ctx = firstComtree(); ctx != 0; ctx = nextComtree(ctx)) {
1371  string s1;
1372  s += comt2string(ctx,s1);
1373  }
1374  s += ";\n";
1375  return s;
1376 }
1377 
1386 string& ComtInfo::link2string(int ctx, int lnk, string& s) const {
1387  stringstream ss;
1388  fAdr_t childAdr = getChild(ctx,lnk);
1389  int child = net->getNodeNum(childAdr);
1390  int parent = net->getPeer(child,lnk);
1391  ss << "(" << net->getNodeName(child,s);
1392  if (net->isRouter(child))
1393  ss << "." << net->getLLnum(lnk,child);
1394  ss << "," << net->getNodeName(parent,s) << "."
1395  << net->getLLnum(lnk,parent);
1396  RateSpec rs;
1397  if (net->isRouter(child)) {
1398  map<fAdr_t,ComtRtrInfo>::iterator rp;
1399  rp = comtree[ctx].rtrMap->find(childAdr);
1400  rs = rp->second.plnkRates;
1401  } else {
1402  map<fAdr_t,ComtLeafInfo>::iterator lp;
1403  lp = comtree[ctx].leafMap->find(childAdr);
1404  rs = lp->second.plnkRates;
1405  }
1406  ss << ",(" << rs.bitRateUp << "," << rs.bitRateDown
1407  << "," << rs.pktRateUp << "," << rs.pktRateDown << "))";
1408  s = ss.str();
1409  return s;
1410 }
1411 
1420 string& ComtInfo::leafLink2string(int ctx, fAdr_t leafAdr, string& s) const {
1421  int leaf = net->getNodeNum(leafAdr);
1422  if (leaf != 0) return link2string(ctx,net->firstLinkAt(leaf),s);
1423 
1424  map<fAdr_t,ComtLeafInfo>::iterator lp;
1425  lp = comtree[ctx].leafMap->find(leafAdr);
1426  int parent = net->getNodeNum(lp->second.parent);
1427  stringstream ss;
1428  ss << "(" << Forest::fAdr2string(leafAdr,s);
1429  ss << "," << net->getNodeName(parent,s) << "." << lp->second.llnk;
1430  ss << "," << lp->second.plnkRates.toString(s) << ")";
1431  s = ss.str();
1432  return s;
1433 }
1434 
1442 string& ComtInfo::comt2string(int ctx, string& s) const {
1443  s = "";
1444  if (!validComtIndex(ctx)) return s;
1445  stringstream ss;
1446  ss << "comtree(" << getComtree(ctx) << ","
1447  << net->getNodeName(net->getNodeNum(getOwner(ctx)),s) << ",";
1448  ss << net->getNodeName(net->getNodeNum(getRoot(ctx)),s) << ","
1449  << (getConfigMode(ctx) ? "auto" : "manual") << ",";
1450  ss << comtree[ctx].bbDefRates.toString(s) << ",";
1451  ss << comtree[ctx].leafDefRates.toString(s);
1452  int numNodes = comtree[ctx].rtrMap->size()
1453  + comtree[ctx].leafMap->size();
1454  if (numNodes <= 1) {
1455  ss << ")\n"; s = ss.str(); return s;
1456  } else if (comtree[ctx].coreSet->size() > 1) {
1457  ss << ",\n\t(";
1458  // iterate through core nodes and print
1459  bool first = true;
1460  for (fAdr_t c = firstCore(ctx); c != 0; c = nextCore(ctx,c)) {
1461  if (c == getRoot(ctx)) continue;
1462  if (first) first = false;
1463  else ss << ",";
1464  ss << net->getNodeName(net->getNodeNum(c),s);
1465  }
1466  ss << ")";
1467  } else {
1468  ss << ",";
1469  }
1470  if (numNodes <= 1) {
1471  ss << "\n)\n";
1472  } else {
1473  ss << ",\n";
1474  int num2go = numNodes - 1;
1475  // iterate through routers and print parent links
1476  int numDone = 0;
1477  map<fAdr_t,ComtRtrInfo>::iterator rp;
1478  for (rp = comtree[ctx].rtrMap->begin();
1479  rp != comtree[ctx].rtrMap->end(); rp++) {
1480  if (rp->second.plnk == 0) continue;
1481  ss << "\t" << link2string(ctx,rp->second.plnk,s);
1482  if (++numDone < num2go) ss << ",";
1483  ss << "\n";
1484  }
1485  // iterate through leaf nodes and print parent links
1486  map<fAdr_t,ComtLeafInfo>::iterator lp;
1487  for (lp = comtree[ctx].leafMap->begin();
1488  lp != comtree[ctx].leafMap->end(); lp++) {
1489  ss << "\t"
1490  << leafLink2string(ctx,lp->first,s);
1491  if (++numDone < num2go) ss << ",";
1492  ss << "\n";
1493  }
1494  ss << ")\n";
1495  }
1496  s = ss.str();
1497  return s;
1498 }
1499 
1508 string& ComtInfo::comtStatus2string(int ctx, string& s) const {
1509  s = "";
1510  if (!validComtIndex(ctx)) return s;
1511  stringstream ss;
1512  ss << "comtree(" << getComtree(ctx) << ","
1513  << net->getNodeName(net->getNodeNum(getOwner(ctx)),s) << ",";
1514  ss << net->getNodeName(net->getNodeNum(getRoot(ctx)),s) << ","
1515  << (getConfigMode(ctx) ? "auto" : "manual") << ",";
1516  ss << comtree[ctx].bbDefRates.toString(s) << ",";
1517  ss << comtree[ctx].leafDefRates.toString(s);
1518  int numNodes = comtree[ctx].rtrMap->size()
1519  + comtree[ctx].leafMap->size();
1520  if (numNodes <= 1) {
1521  ss << ")\n"; s = ss.str(); return s;
1522  } else if (comtree[ctx].coreSet->size() > 1) {
1523  ss << ",\n\t(";
1524  // iterate through core nodes and print
1525  bool first = true;
1526  for (fAdr_t c = firstCore(ctx); c != 0; c = nextCore(ctx,c)) {
1527  if (c == getRoot(ctx)) continue;
1528  if (first) first = false;
1529  else ss << ",";
1530  ss << net->getNodeName(net->getNodeNum(c),s);
1531  }
1532  ss << ")";
1533  } else {
1534  ss << ",";
1535  }
1536  if (numNodes <= 1) {
1537  ss << "\n)\n";
1538  } else {
1539  ss << ",\n";
1540  // count number of nodes to be added to string
1541  int num2go = comtree[ctx].rtrMap->size();
1542  map<fAdr_t,ComtLeafInfo>::iterator lp;
1543  for (lp = comtree[ctx].leafMap->begin();
1544  lp != comtree[ctx].leafMap->end(); lp++) {
1545  if (net->getNodeNum(lp->first) != 0) num2go++;
1546  }
1547  // iterate through routers and print nodes, parents, rates
1548  // and link counts
1549  int numDone = 0;
1550  map<fAdr_t,ComtRtrInfo>::iterator rp;
1551  for (rp = comtree[ctx].rtrMap->begin();
1552  rp != comtree[ctx].rtrMap->end(); rp++) {
1553  fAdr_t radr = rp->first;
1554  int rtr = net->getNodeNum(radr);
1555  ss << "\t(";
1556  if (rp->second.plnk == 0) { // special case of root
1557  ss << net->getNodeName(rtr,s) << ","
1558  << rp->second.lnkCnt;
1559  } else {
1560  int parent = net->getPeer(rtr,rp->second.plnk);
1561  ss << net->getNodeName(rtr,s) << "."
1562  << net->getLLnum(rp->second.plnk,rtr) << ",";
1563  ss << net->getNodeName(parent,s) << ".";
1564  ss << net->getLLnum(rp->second.plnk,parent)
1565  << "," << rp->second.plnkRates.toString(s)
1566  << "," << rp->second.lnkCnt;
1567  }
1568  ss << ")";
1569  if (++numDone < num2go) ss << ",";
1570  ss << "\n";
1571  }
1572  // iterate through static leaf nodes and print parent links
1573  for (lp = comtree[ctx].leafMap->begin();
1574  lp != comtree[ctx].leafMap->end(); lp++) {
1575  fAdr_t ladr = lp->first;
1576  int leaf = net->getNodeNum(ladr);
1577  if (leaf == 0) continue; // skip dynamic leafs
1578  ss << "\t(";
1579  int parent = net->getNodeNum(lp->second.parent);
1580  ss << net->getNodeName(leaf,s) << ",";
1581  ss << net->getNodeName(parent,s) << "."
1582  << lp->second.llnk ;
1583  ss << "," << lp->second.plnkRates.toString(s) << ")";
1584  if (++numDone < num2go) ss << ",";
1585  ss << "\n";
1586  }
1587  ss << ")\n";
1588  }
1589  s = ss.str();
1590  return s;
1591 }
1592 
1593 string& ComtInfo::comtStatus22string(int ctx, string& s) const {
1594  s = "";
1595  if (!validComtIndex(ctx)) return s;
1596  stringstream ss;
1597  ss << "comtree(" << getComtree(ctx) << ","
1598  << net->getNodeName(net->getNodeNum(getOwner(ctx)),s) << ",";
1599  ss << net->getNodeName(net->getNodeNum(getRoot(ctx)),s) << ","
1600  << (getConfigMode(ctx) ? "auto" : "manual") << ",";
1601  ss << comtree[ctx].bbDefRates.toString(s) << ",";
1602  ss << comtree[ctx].leafDefRates.toString(s);
1603  int numNodes = comtree[ctx].rtrMap->size()
1604  + comtree[ctx].leafMap->size();
1605  if (numNodes <= 1) {
1606  ss << ")\n"; s = ss.str(); return s;
1607  } else if (comtree[ctx].coreSet->size() > 1) {
1608  ss << ",\n\t(";
1609  // iterate through core nodes and print
1610  bool first = true;
1611  for (fAdr_t c = firstCore(ctx); c != 0; c = nextCore(ctx,c)) {
1612  if (c == getRoot(ctx)) continue;
1613  if (first) first = false;
1614  else ss << ",";
1615  ss << net->getNodeName(net->getNodeNum(c),s);
1616  }
1617  ss << ")";
1618  } else {
1619  ss << ",";
1620  }
1621  if (numNodes <= 1) {
1622  ss << "\n)\n";
1623  } else {
1624  ss << ",\n";
1625  // count number of nodes to be added to string
1626  int num2go = comtree[ctx].rtrMap->size();
1627  map<fAdr_t,ComtLeafInfo>::iterator lp;
1628  for (lp = comtree[ctx].leafMap->begin();
1629  lp != comtree[ctx].leafMap->end(); lp++) {
1630  if (net->getNodeNum(lp->first) != 0) num2go++;
1631  }
1632  // iterate through routers and print nodes, parents, rates
1633  // and link counts
1634  int numDone = 0;
1635  map<fAdr_t,ComtRtrInfo>::iterator rp;
1636  for (rp = comtree[ctx].rtrMap->begin();
1637  rp != comtree[ctx].rtrMap->end(); rp++) {
1638  fAdr_t radr = rp->first;
1639  int rtr = net->getNodeNum(radr);
1640  ss << "\t(";
1641  if (rp->second.plnk == 0) { // special case of root
1642  ss << net->getNodeName(rtr,s) << ","
1643  << rp->second.lnkCnt;
1644  } else {
1645  int parent = net->getPeer(rtr,rp->second.plnk);
1646  ss << net->getNodeName(rtr,s) << "."
1647  << net->getLLnum(rp->second.plnk,rtr) << ",";
1648  ss << net->getNodeName(parent,s) << ".";
1649  ss << net->getLLnum(rp->second.plnk,parent)
1650  << "," << rp->second.plnkRates.toString(s);
1651  ss << "," << rp->second.subtreeRates.toString(s)
1652  << "," << rp->second.lnkCnt;
1653  }
1654  ss << ")";
1655  if (++numDone < num2go) ss << ",";
1656  ss << "\n";
1657  }
1658  // iterate through static leaf nodes and print parent links
1659  for (lp = comtree[ctx].leafMap->begin();
1660  lp != comtree[ctx].leafMap->end(); lp++) {
1661  fAdr_t ladr = lp->first;
1662  int leaf = net->getNodeNum(ladr);
1663  if (leaf == 0) continue; // skip dynamic leafs
1664  ss << "\t(";
1665  int parent = net->getNodeNum(lp->second.parent);
1666  ss << net->getNodeName(leaf,s) << ",";
1667  ss << net->getNodeName(parent,s) << "."
1668  << lp->second.llnk ;
1669  ss << "," << lp->second.plnkRates.toString(s) << ")";
1670  if (++numDone < num2go) ss << ",";
1671  ss << "\n";
1672  }
1673  ss << ")\n";
1674  }
1675  s = ss.str();
1676  return s;
1677 }
1678 
1679 } // ends namespace
1680