forest-net
an overlay networks for large-scale virtual worlds
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator
NetInfo.cpp
Go to the documentation of this file.
1 
9 #include "NetInfo.h"
10 
11 namespace forest {
12 
13 
20 NetInfo::NetInfo(int maxNode1, int maxLink1, int maxRtr1, int maxCtl1)
21  : maxRtr(maxRtr1), maxNode(maxNode1), maxLink(maxLink1),
22  maxCtl(maxCtl1) {
23  maxLeaf = maxNode-maxRtr;
24  netTopo = new Wgraph(maxNode, maxLink);
25 
26  rtr = new RtrNodeInfo[maxRtr+1];
27  routers = new UiSetPair(maxRtr);
28 
29  leaf = new LeafNodeInfo[maxLeaf+1];
30  leaves = new UiSetPair(maxLeaf);
31  nameNodeMap = new map<string,int>;
32  adrNodeMap = new map<fAdr_t,int>;
33  controllers = new set<int>();
34  defaultLeafRates.set(50,500,25,250); // default for access link rates
35 
36  link = new LinkInfo[maxLink+1];
37  locLnk2lnk = new HashMap(2*min(maxLink,maxRtr*(maxRtr-1)/2)+1);
38 
39  if (pthread_mutex_init(&glock,NULL) != 0)
40  fatal("NetInfo::NetInfo: cannot initialize lock");
41 }
42 
46 NetInfo::~NetInfo() {
47 // add code to delete other comtree info
48  delete netTopo;
49  delete [] rtr; delete routers;
50  delete [] leaf; delete leaves; delete controllers;
51  delete nameNodeMap; delete adrNodeMap;
52  delete [] link; delete locLnk2lnk;
53  pthread_mutex_destroy(&glock);
54 }
55 
56 
62 int NetInfo::getIface(int llnk, int rtr) const {
63  for (int i = 1; i <= getNumIf(rtr); i++) {
64  if (!validIf(rtr,i)) continue;
65  pair<int,int> links; getIfLinks(rtr,i,links);
66  if (llnk >= links.first && llnk <= links.second) return i;
67  }
68  return 0;
69 }
70 
78 int NetInfo::addRouter(const string& name) {
79  int r = routers->firstOut();
80  if (r == 0) return 0;
81  if (nameNodeMap->find(name) != nameNodeMap->end()) return 0;
82  routers->swap(r);
83 
84  rtr[r].name = name; (*nameNodeMap)[name] = r;
85  rtr[r].nType = Forest::ROUTER;
86  rtr[r].fAdr = -1;
87 
88  pair<double,double> loc(UNDEF_LAT,UNDEF_LONG);
89  setNodeLocation(r,loc);
90  pair<fAdr_t,fAdr_t> range(-1,-1);
91  setLeafRange(r,range);
92  rtr[r].numIf = 0; rtr[r].iface = 0;
93  return r;
94 }
95 
106 bool NetInfo::addInterfaces(int r, int numIf) {
107  if (!isRouter(r) || getNumIf(r) != 0) return false;
108  rtr[r].iface = new IfInfo[numIf+1];
109  rtr[r].numIf = numIf;
110  return true;
111 }
112 
120 int NetInfo::addLeaf(const string& name, Forest::ntyp_t nTyp) {
121  int ln = leaves->firstOut();
122  if (ln == 0) return 0;
123  if (nameNodeMap->find(name) != nameNodeMap->end()) return 0;
124  leaves->swap(ln);
125 
126  int nodeNum = ln + maxRtr;
127  leaf[ln].name = name;
128  (*nameNodeMap)[name] = nodeNum;
129  if (nTyp == Forest::CONTROLLER) controllers->insert(ln);
130  leaf[ln].fAdr = -1;
131 
132  setLeafType(nodeNum,nTyp); setLeafIpAdr(nodeNum,0);
133  pair<double,double> loc(UNDEF_LAT,UNDEF_LONG);
134  setNodeLocation(nodeNum,loc);
135  return nodeNum;
136 }
137 
149 int NetInfo::addLink(int u, int v, int uln, int vln) {
150  int lnk = (isLeaf(v) ? netTopo->join(v,u) : netTopo->join(u,v));
151  if (lnk == 0) return 0;
152  netTopo->setWeight(lnk,0);
153  if (isRouter(u)) {
154  if (!locLnk2lnk->put(ll2l_key(u,uln),2*lnk)) {
155  netTopo->remove(lnk); return 0;
156  }
157  if (isLeaf(v)) setRightLLnum(lnk,uln);
158  else setLeftLLnum(lnk,uln);
159  }
160  if (isRouter(v)) {
161  if (!locLnk2lnk->put(ll2l_key(v,vln),2*lnk+1)) {
162  locLnk2lnk->remove(ll2l_key(u,uln));
163  netTopo->remove(lnk); return 0;
164  }
165  setRightLLnum(lnk,vln);
166  }
167  getLinkRates(lnk).set(Forest::MINBITRATE,Forest::MINBITRATE,
168  Forest::MINPKTRATE,Forest::MINPKTRATE);
169  return lnk;
170 }
171 
172 
195 bool NetInfo::read(istream& in) {
196  RtrNodeInfo cRtr; // holds data for router being parsed
197  LeafNodeInfo cLeaf; // holds data for leaf being parsed
198  LinkDesc cLink; // hods data for link being parsed
199  IfInfo iface[Forest::MAXINTF+1]; // holds data for router interfaces
200 
201  int rtrNum = 1; // rtrNum = i for i-th router in file
202  int leafNum = 1; // leafNum = i for i-th leaf in file
203  int linkNum = 1; // linkNum = i for i-th link in file
204 
205  string s, errMsg;
206  while (!in.eof()) {
207  if (!Util::skipBlank(in) || Util::verify(in,';')) break;
208  if (!Util::readWord(in, s)) {
209  cerr << "NetInfo:: read: syntax error: expected "
210  "(;) or keyword (router,leaf,link)\n";
211  return false;
212  }
213  if (s == "router") {
214  if (!readRouter(in, cRtr, iface, errMsg)) {
215  cerr << "NetInfo::read: error when attempting "
216  " to read " << rtrNum << "-th router ("
217  << errMsg << ")\n";
218  return false;
219  }
220  int r = addRouter(cRtr.name);
221  if (r == 0) {
222  cerr << "NetInfo::read: cannot add router "
223  << cRtr.name << endl;
224  return false;
225  }
226  setNodeAdr(r,cRtr.fAdr);
227  pair<double,double> loc(cRtr.latitude/1000000.0,
228  cRtr.longitude/1000000.0);
229  setNodeLocation(r,loc);
230  pair<fAdr_t,fAdr_t> range(cRtr.firstLeafAdr,
231  cRtr.lastLeafAdr);
232  setLeafRange(r,range);
233  addInterfaces(r,cRtr.numIf);
234  for (int i = 1; i <= getNumIf(r); i++)
235  rtr[r].iface[i] = iface[i];
236  rtrNum++;
237  } else if (s == "leaf") {
238  if (!readLeaf(in, cLeaf, errMsg)) {
239  cerr << "NetInfo::read: error when attempting "
240  " to read " << leafNum << "-th leaf ("
241  << errMsg << ")\n";
242  return false;
243  }
244  int nodeNum = addLeaf(cLeaf.name,cLeaf.nType);
245  if (nodeNum == 0) {
246  cerr << "NetInfo::read: cannot add leaf "
247  << cLeaf.name << endl;
248  return false;
249  }
250  setLeafType(nodeNum,cLeaf.nType);
251  setLeafIpAdr(nodeNum,cLeaf.ipAdr);
252  setNodeAdr(nodeNum,cLeaf.fAdr);
253  pair<double,double> loc(cLeaf.latitude/1000000.0,
254  cLeaf.longitude/1000000.0);
255  setNodeLocation(nodeNum,loc);
256  leafNum++;
257  } else if (s == "link") {
258  if (!readLink(in, cLink, errMsg)) {
259  cerr << "NetInfo::read: error when attempting "
260  " to read " << linkNum << "-th link ("
261  << errMsg << ")\n";
262  return false;
263  }
264  // add new link and set attributes
265  map<string,int>::iterator pp;
266  pp = nameNodeMap->find(cLink.nameL);
267  if (pp == nameNodeMap->end()) {
268  cerr << "NetInfo::read: error when attempting "
269  " to read " << linkNum << "-th link ("
270  << cLink.nameL << " invalid node name)\n";
271  }
272  int u = pp->second;
273  pp = nameNodeMap->find(cLink.nameR);
274  if (pp == nameNodeMap->end()) {
275  cerr << "NetInfo::read: error when attempting "
276  " to read " << linkNum << "-th link ("
277  << cLink.nameR << " invalid node name)\n";
278  }
279  int v = pp->second;
280  int lnk = addLink(u,v,cLink.numL,cLink.numR);
281  if (lnk == 0) {
282  cerr << "NetInfo::read: can't add link ("
283  << cLink.nameL << "." << cLink.numL << ","
284  << cLink.nameR << "." << cLink.numR << ")"
285  << endl;
286  return false;
287  }
288  getLinkRates(lnk) = cLink.rates;
289  cLink.rates.scale(.9);
290  getAvailRates(lnk) = cLink.rates;
291  setLinkLength(lnk, cLink.length);
292  linkNum++;
293  } else if (s == "defaultLeafRates") {
294  if (!readRateSpec(in,defaultLeafRates)) {
295  cerr << "NetInfo::read: can't read default "
296  "rates for links\n";
297  return false;
298  }
299  } else {
300  cerr << "NetInfo::read: unrecognized keyword (" << s
301  << ")\n";
302  return false;
303  }
304  }
305  return check();
306 }
307 
319 bool NetInfo::readRouter(istream& in, RtrNodeInfo& rtr, IfInfo *ifaces,
320  string& errMsg) {
321  string name; fAdr_t fadr; pair<double,double> loc;
322  pair<fAdr_t,fAdr_t> adrRange;
323 
324  errMsg = "";
325  if (!Util::verify(in,'(',50) ||
326  !Util::readWord(in,name) || !Util::verify(in,',',20)) {
327  errMsg = "could not read router name";
328  return false;
329  }
330  if (!Forest::readForestAdr(in,fadr) || !Util::verify(in,',',20)) {
331  errMsg = "could not read Forest address for router " + name;
332  return false;
333  }
334  if (!readLocation(in,loc) || !Util::verify(in,',',20)) {
335  errMsg = "could not read location for router " + name;
336  return false;
337  }
338  if (!readAdrRange(in,adrRange) || !Util::verify(in,',',20)) {
339  errMsg = "could not read address range for router " + name;
340  return false;
341  }
342  Util::skipBlank(in);
343  int rv = readIface(in,ifaces,errMsg);
344  if (rv == 0) return false;
345  int maxif = rv;
346  while (Util::verify(in,',',20)) {
347  Util::skipBlank(in);
348  rv = readIface(in,ifaces,errMsg);
349  if (rv == 0) return false;
350  maxif = max(rv,maxif);
351  }
352  if (!Util::verify(in,')',50)) return false;
353 
354  rtr.name = name; rtr.fAdr = fadr;
355  rtr.latitude = (int) 1000000*loc.first;
356  rtr.longitude = (int) 1000000*loc.second;
357  rtr.firstLeafAdr = adrRange.first; rtr.lastLeafAdr = adrRange.second;
358  rtr.numIf = maxif;
359  return true;
360 }
361 
367 bool NetInfo::readLocation(istream& in, pair<double,double>& loc) {
368  if (!Util::verify(in,'(',50)) return false;
369  in >> loc.first; if (in.fail()) return false;
370  if (!Util::verify(in,',',20)) return false;
371  in >> loc.second; if (in.fail()) return false;
372  if (!Util::verify(in,')',20)) return false;
373  return true;
374 }
375 
382 bool NetInfo::readAdrRange(istream& in, pair<fAdr_t,fAdr_t>& range) {
383  return Util::verify(in,'(',50) &&
384  Forest::readForestAdr(in,range.first) &&
385  Util::verify(in,'-',20) &&
386  Forest::readForestAdr(in,range.second) &&
387  Util::verify(in,')',20);
388 }
389 
395 bool NetInfo::readRateSpec(istream& in, RateSpec& rs) {
396  int bru, brd, pru, prd;
397  if (!Util::verify(in,'(',50)) return false;
398  in >> bru; if (in.fail()) return false;
399  if (!Util::verify(in,',',20)) return false;
400  in >> brd; if (in.fail()) return false;
401  if (!Util::verify(in,',',20)) return false;
402  in >> pru; if (in.fail()) return false;
403  if (!Util::verify(in,',',20)) return false;
404  in >> prd; if (in.fail()) return false;
405  if (!Util::verify(in,')',20)) return false;
406  rs.set(bru,brd,pru,prd);
407  return true;
408 }
409 
419 int NetInfo::readIface(istream& in, IfInfo *ifaces, string& errMsg) {
420  int ifn; ipa_t ip; int firstLink, lastLink; RateSpec rs;
421 
422  if (!Util::verify(in,'[',50)) {
423  errMsg = "syntax error: expected left bracket";
424  return 0;
425  }
426  in >> ifn;
427  if (in.fail()) {
428  errMsg = "could not read interface number";
429  return 0;
430  }
431  stringstream ss;
432  if (ifn < 1 || ifn > Forest::MAXINTF) {
433  ss << "interface number " << ifn << " exceeds allowed range";
434  errMsg = ss.str();
435  return 0;
436  }
437  if (!Util::verify(in,',',20) ||
438  !Np4d::readIpAdr(in,ip)) {
439  ss << "could not read ip address for interface " << ifn;
440  errMsg = ss.str();
441  return 0;
442  }
443  if (!Util::verify(in,',',20)) {
444  ss << "syntax error in iface " << ifn << ", expected comma";
445  errMsg = ss.str();
446  return 0;
447  }
448  in >> firstLink;
449  if (in.fail()) {
450  ss << "could not read link range for iface " << ifn;
451  errMsg = ss.str();
452  return 0;
453  }
454  lastLink = firstLink;
455  if (Util::verify(in,'-',20)) {
456  in >> lastLink;
457  if (in.fail()) {
458  ss << "could not read link range for iface " << ifn;
459  errMsg = ss.str();
460  return 0;
461  }
462  }
463  if (!Util::verify(in,',',20)) {
464  ss << "syntax error in iface " << ifn << ", expected comma";
465  errMsg = ss.str();
466  return 0;
467  }
468  if (!readRateSpec(in,rs)) {
469  ss << "could not read ip address for interface " << ifn;
470  errMsg = ss.str();
471  return 0;
472  }
473  if (!Util::verify(in,']',20)) {
474  ss << "syntax error in iface " << ifn
475  << ", expected right bracket";
476  errMsg = ss.str();
477  return 0;
478  }
479  ifaces[ifn].ipAdr = ip;
480  ifaces[ifn].firstLink = firstLink;
481  ifaces[ifn].lastLink = lastLink;
482  ifaces[ifn].rates = rs;
483  return ifn;
484 }
485 
495 bool NetInfo::readLeaf(istream& in, LeafNodeInfo& leaf, string& errMsg) {
496  string name;
497  Forest::ntyp_t ntyp = Forest::UNDEF_NODE;
498  ipa_t ip; fAdr_t fadr;
499  pair<double,double> loc;
500 
501  errMsg = "";
502  if (!Util::verify(in,'(',50) ||
503  !Util::readWord(in,name) || !Util::verify(in,',',20)) {
504  errMsg = "could not read leaf node name";
505  return false;
506  }
507  string typstr;
508  if (!Util::readWord(in,typstr) ||
509  (ntyp = Forest::getNodeType(typstr)) == Forest::UNDEF_NODE ||
510  !Util::verify(in,',',20)) {
511  errMsg = "could not read leaf node name";
512  return false;
513  }
514  if (!Np4d::readIpAdr(in,ip) || !Util::verify(in,',',20)) {
515  errMsg = "could not read IP address for leaf node " + name;
516  return false;
517  }
518  if (!Forest::readForestAdr(in,fadr) || !Util::verify(in,',',20)) {
519  errMsg = "could not read Forest address for leaf node " + name;
520  return false;
521  }
522  if (!readLocation(in,loc) || !Util::verify(in,')',20)) {
523  errMsg = "could not read location for leaf node " + name;
524  return false;
525  }
526  leaf.name = name; leaf.nType = ntyp; leaf.ipAdr = ip;
527  leaf.fAdr = fadr;
528  leaf.latitude = (int) 1000000*loc.first;
529  leaf.longitude = (int) 1000000*loc.second;
530  return true;
531 }
532 
542 bool NetInfo::readLink(istream& in, LinkDesc& link, string& errMsg) {
543  string nameL, nameR; int numL, numR, length; RateSpec rs;
544 
545  errMsg = "";
546  if (!Util::verify(in,'(',50) ||
547  !readLinkEndpoint(in,nameL,numL) || !Util::verify(in,',',20)) {
548  errMsg = "could not first link endpoint";
549  return false;
550  }
551  if (!readLinkEndpoint(in,nameR,numR) || !Util::verify(in,',',20)) {
552  errMsg = "could not read second link endpoint";
553  return false;
554  }
555  in >> length;
556  if (in.fail()) {
557  errMsg = "could not read link length";
558  return false;
559  }
560  if (Util::verify(in,')',20)) { // omitted rate spec
561  rs = defaultLeafRates;
562  } else {
563  if (!Util::verify(in,',',20) || !readRateSpec(in,rs)) {
564  errMsg = "could not read rate specification";
565  return false;
566  }
567  if (!Util::verify(in,')',20)) {
568  errMsg = "syntax error, expected right paren";
569  return false;
570  }
571  }
572  link.nameL = nameL; link.numL = numL;
573  link.nameR = nameR; link.numR = numR;
574  link.length = length; link.rates = rs;
575  return true;
576 }
577 
584 bool NetInfo::readLinkEndpoint(istream& in, string& name, int& num) {
585  if (!Util::readWord(in,name)) return false;
586  num = 0;
587  if (Util::verify(in,'.')) {
588  in >> num;
589  if (in.fail() || num < 1) return false;
590  }
591  return true;
592 }
593 
598 bool NetInfo::check() const {
599  bool status = true;
600 
601  // make sure there is at least one router
602  if (getNumRouters() == 0 || firstRouter() == 0) {
603  cerr << "NetInfo::check: no routers in network, terminating\n";
604  return false;
605  }
606  // make sure that local link numbers
607  // the same local link number
608  if (!checkLocalLinks()) status = false;
609 
610  // make sure that routers are all connected, by doing
611  // a breadth-first search from firstRouter()
612  if (!checkBackBone()) status = false;
613 
614  // check that node addresses are consistent
615  if (!checkAddresses()) status = false;
616 
617  // check that the leaf address ranges are consistent
618  if (!checkLeafRange()) status = false;
619 
620  // check that all leaf nodes are consistent.
621  if (!checkLeafNodes()) status = false;
622 
623  // check that link rates are within bounds
624  if (!checkLinkRates()) status = false;
625 
626  // check that router interface rates are within bounds
627  if (!checkRtrRates()) status = false;
628 
629  return status;
630 }
631 
636 bool NetInfo::checkLocalLinks() const {
637  bool status = true;
638  for (int rtr = firstRouter(); rtr != 0; rtr = nextRouter(rtr)) {
639  for (int l1 = firstLinkAt(rtr); l1 != 0;
640  l1 = nextLinkAt(rtr,l1)) {
641  for (int l2 = nextLinkAt(rtr,l1); l2 != 0;
642  l2 = nextLinkAt(rtr,l2)) {
643  if (getLLnum(l1,rtr) == getLLnum(l2,rtr)) {
644  string s1,s2;
645  cerr << "NetInfo::checkLocalLinks: "
646  "detected two links at router "
647  << rtr << " with same local link "
648  "number: "
649  << link2string(l1,s1) << " and "
650  << link2string(l2,s2) << "\n";
651  status = false;
652  }
653  }
654  // check that local link numbers fall within the
655  // range of some valid interface
656  int llnk = getLLnum(l1,rtr);
657  if (getIface(llnk,rtr) == 0) {
658  string s;
659  cerr << "NetInfo::checkLocalLinks: link "
660  << llnk << " at " << getNodeName(rtr,s)
661  << " is not in the range assigned "
662  "to any valid interface\n";
663  status = false;
664  }
665  }
666  }
667  return status;
668 }
669 
674 bool NetInfo::checkBackBone() const {
675  set<int> seen; seen.insert(firstRouter());
676  queue<int> pending; pending.push(firstRouter());
677  while (!pending.empty()) {
678  int u = pending.front(); pending.pop();
679  for (int lnk = firstLinkAt(u); lnk != 0;
680  lnk = nextLinkAt(u,lnk)) {
681  int v = getPeer(u,lnk);
682  if (getNodeType(v) != Forest::ROUTER) continue;
683  if (seen.find(v) != seen.end()) continue;
684  seen.insert(v);
685  pending.push(v);
686  }
687  }
688  if ((int) seen.size() == getNumRouters()) return true;
689  cerr << "NetInfo::checkBackbone: network is not connected";
690  return false;
691 }
692 
697 bool NetInfo::checkAddresses() const {
698  bool status = true;
699  for (int n1 = firstNode(); n1 != 0; n1 = nextNode(n1)) {
700  for (int n2 = nextNode(n1); n2 != 0; n2 = nextNode(n2)) {
701  if (getNodeAdr(n1) == getNodeAdr(n2)) {
702  string s1,s2;
703  cerr << "NetInfo::check: detected two nodes "
704  << getNodeName(n1,s1) << " and "
705  << getNodeName(n2,s1) << " with the same "
706  "forest address\n";
707  status = false;
708  }
709  }
710  }
711  return status;
712 }
713 
720 bool NetInfo::checkLeafRange() const {
721  bool status = true;
722  // check that the leaf address range for a router
723  // is compatible with the router's address
724  for (int r = firstRouter(); r != 0; r = nextRouter(r)) {
725  int rzip = Forest::zipCode(getNodeAdr(r));
726  pair<fAdr_t,fAdr_t> range; getLeafRange(r,range);
727  int flzip = Forest::zipCode(range.first);
728  int llzip = Forest::zipCode(range.second);
729  if (rzip != flzip || rzip != llzip) {
730  cerr << "netInfo::checkLeafRange: detected router " << r
731  << "with incompatible address and leaf address "
732  << "range\n";
733  status = false;
734  }
735  if (range.first > range.second) {
736  cerr << "netInfo::check: detected router " << r
737  << "with empty leaf address range\n";
738  status = false;
739  }
740  }
741 
742  // make sure that no two routers have overlapping leaf
743  // address ranges
744  for (int r1 = firstRouter(); r1 != 0; r1 = nextRouter(r1)) {
745  pair<fAdr_t,fAdr_t> range1; getLeafRange(r1,range1);
746  for (int r2 = nextRouter(r1); r2 != 0; r2 = nextRouter(r2)) {
747  pair<fAdr_t,fAdr_t> range2; getLeafRange(r2,range2);
748  if (range1.first > range2.first) continue;
749  if (range2.first <= range1.second) {
750  cerr << "netInfo::checkLeafRange: detected two "
751  "routers " << r1 << " and " << r2
752  << " with overlapping address ranges\n";
753  status = false;
754  }
755  }
756  }
757  return status;
758 }
759 
764 bool NetInfo::checkLeafNodes() const {
765  bool status = true;
766  for (int u = firstLeaf(); u != 0; u = nextLeaf(u)) {
767  int lnk = firstLinkAt(u);
768  if (lnk == 0) {
769  string s;
770  cerr << "NetInfo::checkLeafNodes: detected a leaf node "
771  << getNodeName(u,s) << " with no links\n";
772  status = false; continue;
773  }
774  if (nextLinkAt(u,lnk) != 0) {
775  string s;
776  cerr << "NetInfo::checkLeafNodes: detected a leaf node "
777  << getNodeName(u,s)<< " with more than one link\n";
778  status = false; continue;
779  }
780  if (getNodeType(getPeer(u,lnk)) != Forest::ROUTER) {
781  string s;
782  cerr << "NetInfo::checkLeafNodes: detected a leaf node "
783  << getNodeName(u,s) << " with link to non-router"
784  "\n";
785  status = false; continue;
786  }
787  int rtr = getPeer(u,lnk);
788  int adr = getNodeAdr(u);
789  pair<fAdr_t,fAdr_t> range; getLeafRange(rtr,range);
790  if (adr < range.first || adr > range.second) {
791  string s;
792  cerr << "NetInfo::checkLeafNodes: detected a leaf node "
793  << getNodeName(u,s) << " with an address outside "
794  " the leaf address range of its router\n";
795  status = false; continue;
796  }
797  }
798  return status;
799 }
800 
804 bool NetInfo::checkLinkRates() const {
805  bool status = true;
806  RateSpec minRates(Forest::MINBITRATE,Forest::MINBITRATE,
807  Forest::MINPKTRATE,Forest::MINPKTRATE);
808  RateSpec maxRates(Forest::MAXBITRATE,Forest::MAXBITRATE,
809  Forest::MAXPKTRATE,Forest::MAXPKTRATE);
810  for (int lnk = firstLink(); lnk != 0; lnk = nextLink(lnk)) {
811  if (!minRates.leq(getLinkRates(lnk)) ||
812  !getLinkRates(lnk).leq(maxRates)) {
813  string s;
814  cerr << "NetInfo::check: detected a link "
815  << link2string(lnk,s) << " with rates "
816  "outside the allowed range\n";
817  status = false;
818  }
819  }
820  return status;
821 }
822 
827 bool NetInfo::checkRtrRates() const {
828  bool status =true;
829  RateSpec minRates(Forest::MINBITRATE,Forest::MINBITRATE,
830  Forest::MINPKTRATE,Forest::MINPKTRATE);
831  RateSpec maxRates(Forest::MAXBITRATE,Forest::MAXBITRATE,
832  Forest::MAXPKTRATE,Forest::MAXPKTRATE);
833  for (int r = firstRouter(); r != 0; r = nextRouter(r)) {
834  // check all interfaces at r
835  for (int i = 1; i <= getNumIf(r); i++) {
836  if (!validIf(r,i)) continue;
837  if (!minRates.leq(getIfRates(r,i)) ||
838  !getIfRates(r,i).leq(maxRates)) {
839  cerr << "NetInfo::checkRtrRates: interface "
840  << i << "at router " << r << " has "
841  "rates outside the allowed range\n";
842  status = false;
843  }
844  }
845  // check that the link rates at each interface do not
846  // exceed interface rate
847  RateSpec* ifrates = new RateSpec[getNumIf(r)+1];
848  for (int i = 0; i <= getNumIf(r); i++) ifrates[i].set(0);
849  for (int lnk = firstLinkAt(r); lnk != 0;
850  lnk = nextLinkAt(r,lnk)) {
851  int llnk = getLLnum(lnk,r);
852  int iface = getIface(llnk,r);
853  RateSpec rs = getLinkRates(lnk);
854  if (r == getLeft(lnk)) rs.flip();
855  ifrates[iface].add(rs);
856  }
857  for (int i = 0; i <= getNumIf(r); i++) {
858  if (!validIf(r,i)) continue;
859  if (!ifrates[i].leq(getIfRates(r,i))) {
860  string s;
861  cerr << "NetInfo::check: links at interface "
862  << i << " of router " << getNodeName(r,s)
863  << " exceed its capacity\n";
864  }
865  }
866  delete [] ifrates;
867  }
868  return status;
869 }
870 
876 string& NetInfo::link2string(int lnk, string& s) const {
877  stringstream ss; string s1;
878  if (lnk == 0) { s = "-"; return s; }
879  int left = getLeft(lnk); int right = getRight(lnk);
880  ss << "(" << getNodeName(left,s1);
881  if (getNodeType(left)==Forest::ROUTER) ss << "." << getLeftLLnum(lnk);
882  ss << "," << getNodeName(right,s1);
883  if (getNodeType(right)==Forest::ROUTER) ss << "." << getRightLLnum(lnk);
884  ss << ")";
885  s = ss.str();
886  return s;
887 }
888 
894 string& NetInfo::linkProps2string(int lnk, string& s) const {
895  if (lnk == 0) { s = "-"; return s; }
896  stringstream ss; string s1;
897  int left = getLeft(lnk); int right = getRight(lnk);
898  ss << "(" << getNodeName(left,s1);
899  if (getNodeType(left)==Forest::ROUTER) ss << "." << getLeftLLnum(lnk);
900  ss << "," << getNodeName(right,s1);
901  if (getNodeType(right)==Forest::ROUTER) ss << "." << getRightLLnum(lnk);
902  ss << "," << getLinkLength(lnk) << ",";
903  ss << getLinkRates(lnk).toString(s1) << ")";
904  s = ss.str();
905  return s;
906 }
907 
913 string& NetInfo::linkState2string(int lnk, string& s) const {
914  if (lnk == 0) { s = "-"; return s; }
915  stringstream ss; string s1;
916  int left = getLeft(lnk); int right = getRight(lnk);
917  ss << "(" << getNodeName(left,s1);
918  if (getNodeType(left)==Forest::ROUTER) ss << "." << getLeftLLnum(lnk);
919  ss << "," << getNodeName(right,s1);
920  if (getNodeType(right)==Forest::ROUTER) ss << "." << getRightLLnum(lnk);
921  ss << "," << getLinkLength(lnk) << ",";
922  ss << getLinkRates(lnk).toString(s1);
923  ss << "," << getAvailRates(lnk).toString(s1) << ")";
924  s = ss.str();
925  return s;
926 }
927 
932 string& NetInfo::toString(string& s) const {
933  // First write the routers section
934  s = ""; string s1;
935  for (int r = firstRouter(); r != 0; r = nextRouter(r)) {
936  s += rtr2string(r,s1);
937  }
938 
939  // Next write the leaf nodes, starting with the controllers
940  for (int c = firstController(); c != 0; c = nextController(c)) {
941  s += leaf2string(c,s1);
942  }
943  for (int n = firstLeaf(); n != 0; n = nextLeaf(n)) {
944  if (getNodeType(n) != Forest::CONTROLLER)
945  s += leaf2string(n,s1);
946  }
947  s += '\n';
948 
949  // Now, write the links
950  for (int lnk = firstLink(); lnk != 0; lnk = nextLink(lnk)) {
951  s += "link" + linkProps2string(lnk,s1) + "\n";
952  }
953 
954  // and finally, the default link rates
955  s += "defaultLeafRates" + (defaultLeafRates.toString(s1)) + "\n";
956 
957  s += ";\n"; return s;
958 }
959 
965 string& NetInfo::rtr2string(int rtr, string& s) const {
966  stringstream ss; string s1;
967  ss << "router(" + getNodeName(rtr,s1) << ", ";
968  ss << Forest::fAdr2string(getNodeAdr(rtr),s1) << ", ";
969  pair<double,double>loc; getNodeLocation(rtr,loc);
970  ss << "(" << loc.first << "," << loc.second << "), ";
971  pair<fAdr_t,fAdr_t>range; getLeafRange(rtr,range);
972  ss << "(" << Forest::fAdr2string(range.first,s1);
973  ss << "-" << Forest::fAdr2string(range.second,s1) << "),\n";
974  bool firstIface = true;
975  for (int i = 1; i <= getNumIf(rtr); i++) {
976  if (!validIf(rtr,i)) continue;
977  if (firstIface) firstIface = false;
978  else ss << ",\n";
979  ss << "\t[ " << i << ", "
980  << Np4d::ip2string(getIfIpAdr(rtr,i),s1) << ", ";
981  pair<int,int> links; getIfLinks(rtr,i,links);
982  if (links.first == links.second) {
983  ss << links.first << ", ";
984  } else {
985  ss << links.first << "-" << links.second << ", ";
986  }
987  ss << getIfRates(rtr,i).toString(s1) << " ]";
988  }
989  ss << "\n)\n";
990  s = ss.str();
991  return s;
992 }
993 
999 string& NetInfo::leaf2string(int leaf, string& s) const {
1000  stringstream ss; string s1;
1001  ss << "leaf(" << getNodeName(leaf,s1) << ", ";
1002  ss << Forest::nodeType2string(getNodeType(leaf),s1) << ", ";
1003  ss << Np4d::ip2string(getLeafIpAdr(leaf),s1) << ", ";
1004  ss << Forest::fAdr2string(getNodeAdr(leaf),s1) << ", ";
1005  pair<double,double>loc; getNodeLocation(leaf,loc);
1006  ss << "(" << loc.first << "," << loc.second << ")";
1007  ss << ")\n";
1008  s = ss.str();
1009  return s;
1010 }
1011 
1012 } // ends namespace
1013