forest-net
an overlay networks for large-scale virtual worlds
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator
ComtInfo.h
Go to the documentation of this file.
1 
9 #ifndef COMTINFO_H
10 #define COMTINFO_H
11 
12 #include "NetInfo.h"
13 #include "Heap.h"
14 
15 namespace forest {
16 
18 class LinkMod {
19 public:
20  int lnk;
21  int child;
22  RateSpec rs;
23  LinkMod() { lnk = 0; child = 0; rs.set(0); }
24  LinkMod(int l, int c, RateSpec& rs1) { set(l,c,rs1); }
25  LinkMod(const LinkMod& lm) { (*this) = lm; }
26  void set(int l, int c, RateSpec& rs1) {
27  lnk = l; child = c; rs = rs1;
28  }
29 };
30 
33 class ComtInfo {
34 public:
35  ComtInfo(int,NetInfo&);
36  ~ComtInfo();
37  bool init();
38 
39  // predicates
40  bool validComtree(int) const;
41  bool validComtIndex(int) const;
42  bool isComtNode(int,int) const;
43  bool isComtRtr(int,int) const;
44  bool isComtLeaf(int,int) const;
45  bool isCoreNode(int,fAdr_t) const;
46  bool isComtLink(int,int) const;
47 
48  // methods for iterating through comtrees and comtree components
49  int firstComtree();
50  int nextComtree(int);
51  fAdr_t firstCore(int) const;
52  fAdr_t nextCore(int, fAdr_t) const;
53  fAdr_t firstRouter(int) const;
54  fAdr_t nextRouter(int, fAdr_t) const;
55  fAdr_t firstLeaf(int) const;
56  fAdr_t nextLeaf(int, fAdr_t) const;
57 
58  // access comtree attributes
59  int getComtIndex(int);
60  int getComtree(int) const;
61  fAdr_t getOwner(int) const;
62  fAdr_t getRoot(int) const;
63  bool getConfigMode(int) const;
64  RateSpec& getDefLeafRates(int);
65  RateSpec& getDefBbRates(int);
66  fAdr_t getChild(int,int) const;
67  int getPlink(int,fAdr_t) const;
68  fAdr_t getParent(int,fAdr_t) const;
69  int getLinkCnt(int,fAdr_t) const;
70  bool isFrozen(int,fAdr_t) const;
71  RateSpec& getLinkRates(int,int) const;
72 
73  // add/remove/modify comtrees
74  int addComtree(int);
75  bool removeComtree(int);
76  bool setRoot(int,fAdr_t);
77  bool setOwner(int,fAdr_t);
78  void setConfigMode(int,bool);
79  bool addNode(int,fAdr_t);
80  bool removeNode(int,fAdr_t);
81  bool addCoreNode(int,fAdr_t);
82  bool removeCoreNode(int,fAdr_t);
83  bool setPlink(int,fAdr_t,int);
84  bool setParent(int,fAdr_t,fAdr_t,int);
85  void freeze(int,fAdr_t);
86  void thaw(int,fAdr_t);
87 
88  // compute rates and provision network capacity
89  bool setAllComtRates();
90  bool setComtRates(int);
91  void setAutoConfigRates(int);
92  bool checkComtRates(int);
93  int findPath(int,int,RateSpec&,list<LinkMod>&);
94  bool findRootPath(int,int,RateSpec&,vector<int>&);
95  void addPath(int,list<LinkMod>&);
96  void removePath(int,list<LinkMod>&);
97  bool adjustSubtreeRates(int,int,RateSpec&);
98  bool computeMods(int,list<LinkMod>&);
99  bool computeMods(int,fAdr_t,RateSpec&,list<LinkMod>&);
100  void provision(int);
101  void provision(int,list<LinkMod>&);
102  void unprovision(int);
103  void unprovision(int,list<LinkMod>&);
104 
105  // io methods
106  bool read(istream&);
107  comt_t readComtree(istream&,string&);
108  bool readRateSpec(istream&,RateSpec&);
109  bool readLink(istream&,int&,RateSpec&,int&,string&);
110  bool readLinkEndpoint(istream&,string&,int&);
111  string& link2string(int,int,string&) const;
112  string& leafLink2string(int,fAdr_t,string&) const;
113  string& comt2string(int,string&) const;
114  string& comtStatus2string(int,string&) const;
115  string& comtStatus22string(int,string&) const;
116  string& toString(string&);
117 
118  // verification methods - used after reading ComtInfo file
119  bool check();
120  bool checkLinkCounts(int);
121  bool checkSubtreeRates(int);
122  bool checkLinkRates(int);
123 
124  // locking methods
125  void releaseComtree(int);
126  void lockMap(); // use with extreme caution! see below
127  void unlockMap();
128 
129 private:
130  int maxComtree;
131  NetInfo *net;
132 
133  // used in rtrMap of ComtreeInfo
134  struct ComtRtrInfo {
135  int plnk; // link to parent in comtree
136  int lnkCnt; // number of comtree links at this router
137  RateSpec subtreeRates; // rates for subtree rooted at this node
138  bool frozen; // true if plnk rate is frozen
139  RateSpec plnkRates; // rates for link
140  ComtRtrInfo() { plnk = lnkCnt = 0; frozen = false;
141  subtreeRates.set(0); plnkRates.set(0); };
142  ComtRtrInfo(const ComtRtrInfo& cr) { (*this) = cr; }
143  };
144  struct ComtLeafInfo {
145  fAdr_t parent; // forest address of parent of this leaf
146  int llnk; // local link number of parent link at parent
147  RateSpec plnkRates; // rates for leaf and link to parent
148  ComtLeafInfo() { parent = llnk = 0; plnkRates.set(0); };
149  ComtLeafInfo(const ComtLeafInfo& cl) { (*this) = cl; }
150  };
151 
152  struct ComtreeInfo {
153  int comtreeNum;
154  fAdr_t owner;
155  fAdr_t root;
156  bool autoConfig;
157  RateSpec bbDefRates;
158  RateSpec leafDefRates;
159  set<fAdr_t> *coreSet;
160  map<fAdr_t,ComtRtrInfo> *rtrMap;
161  map<fAdr_t,ComtLeafInfo> *leafMap;
162  pthread_cond_t busyCond;
163  bool busyBit;
164  };
165  ComtreeInfo *comtree;
166  IdMap *comtreeMap;
167 
168  pthread_mutex_t mapLock;
169 };
170 
171 // Note that methods that take a comtree index as an argument
172 // assume that the comtree index is valid. This was a conscious
173 // decision to allow the use of ComtInfo in contexts where a program
174 // needs to define per-comtree locks. Any operation that uses or
175 // changes comtreeMap must be protected by a "global" lock.
176 // This includes the validComtIndex() method, so if we checked
177 // the comtree index in methods that just affect one comtree,
178 // client programs would need to acquire a global lock for any
179 // of these operations. Hence, we don't check and we trust the client
180 // program to never pass an invalid comtree index.
181 // Of course, locks are only required in multi-threaded programs.
182 
188 inline bool ComtInfo::validComtree(int comt) const {
189  return comtreeMap->validKey(comt);
190 }
191 
200 inline bool ComtInfo::validComtIndex(int ctx) const {
201  return comtreeMap->validId(ctx);
202 }
203 
210 inline bool ComtInfo::isCoreNode(int ctx, fAdr_t r) const {
211  return comtree[ctx].coreSet->find(r) != comtree[ctx].coreSet->end();
212 }
213 
220 inline bool ComtInfo::isComtNode(int ctx, fAdr_t fa) const {
221  return isComtLeaf(ctx,fa) || isComtRtr(ctx,fa);
222 }
223 
230 inline bool ComtInfo::isComtRtr(int ctx, fAdr_t fa) const {
231  return comtree[ctx].rtrMap->find(fa) != comtree[ctx].rtrMap->end();
232 }
233 
239 inline bool ComtInfo::isComtLeaf(int ctx, fAdr_t ln) const {
240  return comtree[ctx].leafMap->find(ln) != comtree[ctx].leafMap->end();
241 }
242 
249 inline bool ComtInfo::isComtLink(int ctx, int lnk) const {
250  fAdr_t left = net->getNodeAdr(net->getLeft(lnk));
251  fAdr_t right = net->getNodeAdr(net->getRight(lnk));
252 
253  return (isComtNode(ctx,left) && right == getParent(ctx,left)) ||
254  (isComtNode(ctx,right) && left == getParent(ctx,right));
255 }
256 
262 inline int ComtInfo::firstCore(int ctx) const {
263  set<fAdr_t>::iterator p = comtree[ctx].coreSet->begin();
264  return (p != comtree[ctx].coreSet->end() ? *p : 0);
265 }
266 
273 inline int ComtInfo::nextCore(int ctx, fAdr_t rtr) const {
274  set<fAdr_t>::iterator p = comtree[ctx].coreSet->find(rtr);
275  p++;
276  return (p != comtree[ctx].coreSet->end() ? *p : 0);
277 }
278 
284 inline int ComtInfo::firstRouter(int ctx) const {
285  map<fAdr_t,ComtRtrInfo>::iterator p = comtree[ctx].rtrMap->begin();
286  return (p != comtree[ctx].rtrMap->end() ? p->first : 0);
287 }
288 
295 inline int ComtInfo::nextRouter(int ctx, fAdr_t rtr) const {
296  map<fAdr_t,ComtRtrInfo>::iterator p = comtree[ctx].rtrMap->find(rtr);
297  p++;
298  return (p != comtree[ctx].rtrMap->end() ? p->first : 0);
299 }
300 
306 inline int ComtInfo::firstLeaf(int ctx) const {
307  map<fAdr_t,ComtLeafInfo>::iterator p = comtree[ctx].leafMap->begin();
308  return (p != comtree[ctx].leafMap->end() ? p->first : 0);
309 }
310 
317 inline int ComtInfo::nextLeaf(int ctx, fAdr_t leaf) const {
318  map<fAdr_t,ComtLeafInfo>::iterator p = comtree[ctx].leafMap->find(leaf);
319  p++;
320  return (p != comtree[ctx].leafMap->end() ? p->first : 0);
321 }
322 
328 inline int ComtInfo::getComtree(int ctx) const {
329  return comtree[ctx].comtreeNum;
330 }
331 
337 inline fAdr_t ComtInfo::getRoot(int ctx) const {
338  return comtree[ctx].root;
339 }
340 
346 inline fAdr_t ComtInfo::getOwner(int ctx) const {
347  return comtree[ctx].owner;
348 }
349 
357 inline int ComtInfo::getPlink(int ctx, fAdr_t nfa) const {
358  map<fAdr_t,ComtRtrInfo>::iterator rp;
359  rp = comtree[ctx].rtrMap->find(nfa);
360  if (rp != comtree[ctx].rtrMap->end())
361  return rp->second.plnk;
362  map<fAdr_t,ComtLeafInfo>::iterator lp;
363  lp = comtree[ctx].leafMap->find(nfa);
364  return lp->second.llnk;
365 }
366 
372 inline fAdr_t ComtInfo::getParent(int ctx, fAdr_t fa) const {
373  map<fAdr_t,ComtRtrInfo>::iterator rp;
374  rp = comtree[ctx].rtrMap->find(fa);
375  if (rp != comtree[ctx].rtrMap->end()) {
376  if (rp->second.plnk == 0) return 0;
377  int parent = net->getPeer(net->getNodeNum(fa),rp->second.plnk);
378  return net->getNodeAdr(parent);
379  }
380  map<fAdr_t,ComtLeafInfo>::iterator lp;
381  lp = comtree[ctx].leafMap->find(fa);
382  return lp->second.parent;
383 }
384 
390 inline fAdr_t ComtInfo::getChild(int ctx, int lnk) const {
391  int left = net->getLeft(lnk);
392  fAdr_t leftAdr = net->getNodeAdr(left);
393  if (net->isLeaf(left)) return leftAdr;
394  int right = net->getRight(lnk);
395  fAdr_t rightAdr = net->getNodeAdr(right);
396  if (net->isLeaf(right)) return rightAdr;
397  map<fAdr_t,ComtRtrInfo>::iterator rp;
398  rp = comtree[ctx].rtrMap->find(leftAdr);
399  return (rp->second.plnk == lnk ? leftAdr : rightAdr);
400 }
401 
408 inline int ComtInfo::getLinkCnt(int ctx, fAdr_t rtr) const {
409  map<fAdr_t,ComtRtrInfo>::iterator rp;
410  rp = comtree[ctx].rtrMap->find(rtr);
411  return rp->second.lnkCnt;
412 }
413 
418 inline RateSpec& ComtInfo::getDefLeafRates(int ctx) {
419  return comtree[ctx].leafDefRates;
420 }
421 
426 inline RateSpec& ComtInfo::getDefBbRates(int ctx) {
427  return comtree[ctx].bbDefRates;
428 }
429 
436 inline bool ComtInfo::isFrozen(int ctx, fAdr_t rtr) const {
437  map<fAdr_t,ComtRtrInfo>::iterator rp;
438  rp = comtree[ctx].rtrMap->find(rtr);
439  return rp->second.plnk != 0 && rp->second.frozen;
440 }
441 
451 inline RateSpec& ComtInfo::getLinkRates(int ctx, fAdr_t fa) const {
452  map<fAdr_t,ComtRtrInfo>::iterator rp;
453  rp = comtree[ctx].rtrMap->find(fa);
454  if (rp != comtree[ctx].rtrMap->end()) return rp->second.plnkRates;
455  map<fAdr_t,ComtLeafInfo>::iterator lp;
456  lp = comtree[ctx].leafMap->find(fa);
457  return lp->second.plnkRates;
458 }
459 
465 inline bool ComtInfo::setOwner(int ctx, fAdr_t owner) {
466  if (net->getNodeNum(owner) == 0) return false;
467  comtree[ctx].owner = owner;
468  return true;
469 }
470 
476 inline bool ComtInfo::setRoot(int ctx, fAdr_t r) {
477  if (net->getNodeNum(r) == 0) return false;
478  comtree[ctx].root = r;
479  return true;
480 }
481 
486 inline bool ComtInfo::getConfigMode(int ctx) const {
487  return comtree[ctx].autoConfig;
488 }
489 
495 inline void ComtInfo::setConfigMode(int ctx, bool autoConfig) {
496  comtree[ctx].autoConfig = autoConfig;
497 }
498 
519 inline bool ComtInfo::addCoreNode(int ctx, fAdr_t rtrAdr) {
520  int rtr = net->getNodeNum(rtrAdr);
521  if (!net->isRouter(rtr)) return false;
522  if (!isComtRtr(ctx,rtrAdr)) addNode(ctx,rtrAdr);
523  comtree[ctx].coreSet->insert(rtrAdr);
524  return true;
525 }
526 
533 inline bool ComtInfo::removeCoreNode(int ctx, fAdr_t rtrAdr) {
534  comtree[ctx].coreSet->erase(rtrAdr);
535  return true;
536 }
537 
545 inline bool ComtInfo::setPlink(int ctx, fAdr_t rtr, int plnk) {
546  map<fAdr_t,ComtRtrInfo>::iterator rp;
547  rp = comtree[ctx].rtrMap->find(rtr);
548  if (rp->second.plnk != 0) {
549  // handle case when moving a node already in comtree
550  // note: no cycle checking
551  fAdr_t parent = net->getNodeAdr(net->getPeer(
552  net->getNodeNum(rtr),rp->second.plnk));
553  map<fAdr_t,ComtRtrInfo>::iterator rpp;
554  rpp = comtree[ctx].rtrMap->find(parent);
555  rpp->second.lnkCnt--;
556  if (plnk == 0) rp->second.lnkCnt--;
557  } else if (plnk != 0) {
558  rp->second.lnkCnt++;
559  }
560  rp->second.plnk = plnk;
561  if (plnk == 0) return true;
562 
563  fAdr_t parent = net->getNodeAdr(net->getPeer(
564  net->getNodeNum(rtr),plnk));
565  rp = comtree[ctx].rtrMap->find(parent);
566  rp->second.lnkCnt++;
567  return true;
568 }
569 
577 inline bool ComtInfo::setParent(int ctx, fAdr_t leaf, fAdr_t parent, int llnk) {
578  map<fAdr_t,ComtLeafInfo>::iterator lp;
579  lp = comtree[ctx].leafMap->find(leaf);
580  lp->second.parent = parent;
581  lp->second.llnk = llnk;
582 
583  map<fAdr_t,ComtRtrInfo>::iterator rp;
584  rp = comtree[ctx].rtrMap->find(parent);
585  rp->second.lnkCnt++;
586 
587  return true;
588 }
589 
595 inline void ComtInfo::freeze(int ctx, fAdr_t rtr) {
596  map<fAdr_t,ComtRtrInfo>::iterator rp;
597  rp = comtree[ctx].rtrMap->find(rtr);
598  rp->second.frozen = true;
599 }
600 
606 inline void ComtInfo::thaw(int ctx, fAdr_t rtr) {
607  map<fAdr_t,ComtRtrInfo>::iterator rp;
608  rp = comtree[ctx].rtrMap->find(rtr);
609  rp->second.frozen = false;
610 }
611 
619 inline void ComtInfo::lockMap() {
620  pthread_mutex_lock(&mapLock);
621 }
622 
623 inline void ComtInfo::unlockMap() {
624  pthread_mutex_unlock(&mapLock);
625 }
626 
627 } // ends namespace
628 
629 
630 #endif