forest-net
an overlay networks for large-scale virtual worlds
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator
Router.cpp
Go to the documentation of this file.
1 
9 #include "Router.h"
10 
11 using namespace forest;
12 
23 bool processArgs(int argc, char *argv[], RouterInfo& args) {
24  // set default values
25  args.mode = "local";
26  args.myAdr = args.bootIp = args.nmAdr = args.nmIp = 0;
27  args.ccAdr = args.firstLeafAdr = args.lastLeafAdr = 0;
28  args.ifTbl = ""; args.lnkTbl = ""; args.comtTbl = "";
29  args.rteTbl = ""; args.statSpec = "";
30  args.portNum = 0; args.runLength = seconds(0);
31 
32  string s;
33  for (int i = 1; i < argc; i++) {
34  s = argv[i];
35  if (s.compare(0,10,"mode=local") == 0) {
36  args.mode = "local";
37  } else if (s.compare(0,11,"mode=remote") == 0) {
38  args.mode = "remote";
39  } else if (s.compare(0,6,"myAdr=") == 0) {
40  args.myAdr = Forest::forestAdr(&argv[i][6]);
41  } else if (s.compare(0,7,"bootIp=") == 0) {
42  args.bootIp = Np4d::ipAddress(&argv[i][7]);
43  } else if (s.compare(0,6,"nmAdr=") == 0) {
44  args.nmAdr = Forest::forestAdr(&argv[i][6]);
45  } else if (s.compare(0,5,"nmIp=") == 0) {
46  args.nmIp = Np4d::ipAddress(&argv[i][5]);
47  } else if (s.compare(0,6,"ccAdr=") == 0) {
48  args.ccAdr = Forest::forestAdr(&argv[i][6]);
49  } else if (s.compare(0,13,"firstLeafAdr=") == 0) {
50  args.firstLeafAdr = Forest::forestAdr(&argv[i][13]);
51  } else if (s.compare(0,12,"lastLeafAdr=") == 0) {
52  args.lastLeafAdr = Forest::forestAdr(&argv[i][12]);
53  } else if (s.compare(0,6,"ifTbl=") == 0) {
54  args.ifTbl = &argv[i][6];
55  } else if (s.compare(0,7,"lnkTbl=") == 0) {
56  args.lnkTbl = &argv[i][7];
57  } else if (s.compare(0,8,"comtTbl=") == 0) {
58  args.comtTbl = &argv[i][8];
59  } else if (s.compare(0,7,"rteTbl=") == 0) {
60  args.rteTbl = &argv[i][7];
61  } else if (s.compare(0,9,"statSpec=") == 0) {
62  args.statSpec = &argv[i][9];
63  } else if (s.compare(0,8,"portNum=") == 0) {
64  sscanf(&argv[i][8],"%hd",&args.portNum);
65  } else if (s.compare(0,8,"finTime=") == 0) {
66  int runtime;
67  sscanf(&argv[i][8],"%d",&runtime);
68  args.runLength = seconds(runtime);
69  } else {
70  cerr << "unrecognized argument: " << argv[i] << endl;
71  return false;
72  }
73  }
74  if (args.mode.compare("local") == 0 &&
75  (args.myAdr == 0 || args.firstLeafAdr == 0 ||
76  args.lastLeafAdr ==0 || args.lastLeafAdr < args.firstLeafAdr)) {
77  cerr << "processArgs: local configuration requires myAdr, "
78  "firstLeafAdr, lastLeafAdr and that firstLeafAdr "
79  "be no larger than lastLeafAdr\n";
80  return false;
81  } else if (args.mode.compare("remote") == 0 &&
82  (args.bootIp == 0 || args.myAdr == 0 ||
83  args.nmIp == 0 || args.nmAdr == 0)) {
84  cerr << "processArgs: remote configuration requires bootIp, "
85  "myAdr, netMgrIp and netMgrAdr\n";
86  return false;
87  }
88  return true;
89 }
90 
93 int main(int argc, char *argv[]) {
94  RouterInfo args;
95  if (!processArgs(argc, argv, args))
96  Util::fatal("Router:: error processing command line arguments");
97  Router router(args);
98 
99  if (args.mode.compare("local") == 0) {
100  if (!router.readTables(args) || !router.setup())
101  Util::fatal("Router::main: could not complete local "
102  "configuration\n");
103  }
104  router.run();
105  return 0;
106 }
107 
108 namespace forest {
109 
114 Router::Router(const RouterInfo& config) {
115  int nIfaces = 50; int nLnks = 1000;
116  int nComts = 5000; int nRts = 100000;
117  int nPkts = 100000; int nBufs = 50000;
118  int nQus = 10000;
119 
120  myAdr = config.myAdr;
121  bootIp = config.bootIp;
122  nmAdr = config.nmAdr;
123  nmIp = config.nmIp;
124  ccAdr = config.ccAdr;
125  firstLeafAdr = config.firstLeafAdr;
126  lastLeafAdr = config.lastLeafAdr;
127  runLength = config.runLength;
128 
129  try {
130  ps = new PacketStore(nPkts, nBufs);
131  ift = new IfaceTable(nIfaces);
132  lt = new LinkTable(nLnks);
133  ctt = new ComtreeTable(nComts,10*nComts);
134  rt = new RouteTable(nRts,myAdr,ctt);
135  sm = new StatsModule(1000, nLnks, nQus, ctt);
136  pktLog = new PacketLog(ps);
137  qm = new QuManager(nLnks, nPkts, nQus, min(50,5*nPkts/nLnks),
138  ps, sm);
139  sock = new int[nIfaces+1];
140  maxSockNum = -1;
141 
142  rip = new RouterInProc(this);
143  rop = new RouterOutProc(this);
144 
145  leafAdr = new ListPair((lastLeafAdr - firstLeafAdr)+1);
146  } catch (std::bad_alloc e) {
147  Util::fatal("Router: unable to allocate space for Router");
148  }
149 
150  if (config.mode.compare("local") == 0) {
151  if (!readTables(config) || !setup())
152  Util::fatal("Router: could not complete local "
153  "configuration\n");
154  } else {
155  booting = true;
156  }
157  seqNum = 0;
158  tZero = high_resolution_clock::now();
159 }
160 
161 Router::~Router() {
162 // consider thread cleanup
163  delete rip; delete rop; delete rop;
164  delete pktLog; delete qm; delete sm;
165  delete rt; delete ctt; delete lt; delete ift; delete ps;
166  delete leafAdr; delete [] sock;
167 }
168 
170 uint64_t Router::nextSeqNum() {
171  unique_lock<mutex> lck(snLock);
172  uint64_t sn = ++seqNum;
173  return sn;
174 }
175 
182 bool Router::readTables(const RouterInfo& config) {
183  if (config.ifTbl.compare("") != 0) {
184  ifstream fs; fs.open(config.ifTbl.c_str());
185  if (fs.fail() || !ift->read(fs)) {
186  cerr << "Router::readTables: can't read "
187  << "interface table\n";
188  return false;
189  }
190  fs.close();
191  }
192  if (config.lnkTbl.compare("") != 0) {
193  ifstream fs; fs.open(config.lnkTbl.c_str());
194  if (fs.fail() || !lt->read(fs)) {
195  cerr << "Router::readTables: can't read "
196  << "link table\n";
197  return false;
198  }
199  fs.close();
200  }
201  if (config.comtTbl.compare("") != 0) {
202  ifstream fs; fs.open(config.comtTbl.c_str());
203  if (fs.fail() || !ctt->read(fs)) {
204  cerr << "Router::readTables: can't read "
205  << "comtree table\n";
206  return false;
207  }
208  fs.close();
209  }
210  if (config.rteTbl.compare("") != 0) {
211  ifstream fs; fs.open(config.rteTbl.c_str());
212  if (fs.fail() || !rt->read(fs)) {
213  cerr << "Router::readTables: can't read "
214  << "routing table\n";
215  return false;
216  }
217  fs.close();
218  }
219  if (config.statSpec.compare("") != 0) {
220  ifstream fs; fs.open(config.statSpec.c_str());
221  if (fs.fail() || !sm->read(fs)) {
222  cerr << "Router::readTables: can't read "
223  << "statistics spec\n";
224  return false;
225  }
226  fs.close();
227  }
228  return true;
229 }
230 
235 bool Router::setup() {
236  dump(cout);
237  if (!setupAllIfaces()) return false;
238  if (!setupLeafAddresses()) return false;
239  if (!setupQueues()) return false;
240  if (!checkTables()) return false;
241  if (!setAvailRates()) return false;
242  addLocalRoutes();
243 
244  return true;
245 }
246 
251 bool Router::setupAllIfaces() {
252  for (int iface = ift->firstIface(); iface != 0;
253  iface = ift->nextIface(iface)) {
254  if (sock[iface] > 0) continue;
255  if (setupIface(iface)) {
256  cerr << "Router::setupIfaces: could not "
257  "setup interface " << iface << endl;
258  return false;
259  }
260  }
261  return true;
262 }
263 
269 bool Router::setupIface(int i) {
270  // create datagram socket
271  sock[i] = Np4d::datagramSocket();
272  if (sock[i] < 0) {
273  cerr << "Router::setup: socket call failed\n";
274  return false;
275  }
276  maxSockNum = max(maxSockNum, sock[i]);
277 
278  // bind it to an address and port
279  IfaceTable::Entry& ifte = ift->getEntry(i);
280  if (!Np4d::bind4d(sock[i], ifte.ipa, ifte.port)) {
281  string s;
282  cerr << "Router::setup: bind call failed for ("
283  << Np4d::ip2string(ifte.ipa)
284  << ", " << ifte.port << ") check interface's IP "
285  << "address and port\n";
286  return false;
287  }
288  ifte.port = Np4d::getSockPort(sock[i]);
289 
290  return true;
291 }
292 
298 bool Router::setupLeafAddresses() {
299  for (int lnk = lt->firstLink(); lnk != 0; lnk = lt->nextLink(lnk)) {
300  LinkTable::Entry& lte = lt->getEntry(lnk);
301  if (lte.peerType == Forest::ROUTER) continue;
302  if (!allocLeafAdr(lte.peerAdr))
303  return false;
304  }
305  return true;
306 }
307 
314 bool Router::setupQueues() {
315  // Set link rates in QuManager
316  for (int lnk = lt->firstLink(); lnk != 0; lnk = lt->nextLink(lnk)) {
317  LinkTable::Entry& lte = lt->getEntry(lnk);
318  qm->setLinkRates(lnk,lte.rates);
319  }
320  RateSpec rs(Forest::MINBITRATE,Forest::MINBITRATE,
321  Forest::MINPKTRATE,Forest::MINPKTRATE);
322  int ctx;
323  for (ctx = ctt->firstComt(); ctx != 0; ctx = ctt->nextComt(ctx)) {
324  for (int cLnk = ctt->firstComtLink(ctx); cLnk != 0;
325  cLnk = ctt->nextComtLink(ctx,cLnk)) {
326  int lnk = ctt->getLink(ctx,cLnk);
327  int qid = qm->allocQ(lnk);
328  if (qid == 0) return false;
329  ctt->setLinkQ(ctx,cLnk,qid);
330  qm->setQRates(qid,rs);
331  if (lt->getEntry(lnk).peerType == Forest::ROUTER)
332  qm->setQLimits(qid,100,200000);
333  else
334  qm->setQLimits(qid,50,100000);
335  sm->clearQuStats(qid);
336  }
337  }
338  return true;
339 }
340 
347 bool Router::checkTables() {
348  bool success = true;
349 
350  // verify that the default interface is valid and
351  // that each interface has a non-zero IP address
352  if (!ift->valid(ift->getDefaultIface())) {
353  cerr << "Router::checkTables: specified default iface "
354  << ift->getDefaultIface() << " is invalid\n";
355  success = false;
356  }
357  int iface;
358  for (iface = ift->firstIface(); iface != 0;
359  iface = ift->nextIface(iface)) {
360  if (ift->getEntry(iface).ipa == 0) {
361  cerr << "Router::checkTables: interface "
362  << iface << " has zero for IP address\n";
363  success = false;
364  }
365  }
366 
367  // verify that each link is assigned to a valid interface
368  // that the peer Ip address and port are non-zero and consistent,
369  // the the peer type is valid and that the peer address is a valid
370  // unicast forest address
371  int lnk;
372  for (lnk = lt->firstLink(); lnk != 0; lnk = lt->nextLink(lnk)) {
373  LinkTable::Entry& lte = lt->getEntry(lnk);
374  if (!ift->valid(lte.iface)) {
375  cerr << "Router::checkTables: interface " << iface
376  << " for link " << lnk << " is not valid\n";
377  success = false;
378  }
379  if (lte.peerIp == 0 && lte.peerType == Forest::ROUTER) {
380  cerr << "Router::checkTables: invalid peer IP "
381  << "for link " << lnk << endl;
382  success = false;
383  }
384  if (!Forest::validUcastAdr(lte.peerAdr)) {
385  cerr << "Router::checkTables: invalid peer address "
386  << "for link " << lnk << endl;
387  success = false;
388  }
389  }
390 
391  // verify that the links in each comtree are valid,
392  // that the router links and core links refer to peer routers,
393  // and that each comtree link is consistent
394  int ctx;
395  for (ctx = ctt->firstComt(); ctx != 0;
396  ctx = ctt->nextComt(ctx)) {
397  int comt = ctt->getComtree(ctx);
398  int plnk = ctt->getPlink(ctx);
399  int pcLnk = ctt->getPClink(ctx);
400  if (plnk != ctt->getLink(ctx,pcLnk)) {
401  cerr << "Router::checkTables: parent link "
402  << plnk << " not consistent with pcLnk\n";
403  success = false;
404  }
405  if (ctt->inCore(ctx) && plnk != 0 &&
406  !ctt->isCoreLink(ctx,pcLnk)) {
407  cerr << "Router::checkTables: parent link "
408  << plnk << " of core node does not lead to "
409  << "another core node\n";
410  success = false;
411  }
412  for (int cLnk = ctt->firstComtLink(ctx); cLnk != 0;
413  cLnk = ctt->nextComtLink(ctx,cLnk)) {
414  int lnk = ctt->getLink(ctx,cLnk);
415  if (!lt->valid(lnk)) {
416  cerr << "Router::checkTables: link "
417  << lnk << " in comtree " << comt
418  << " not in link table" << endl;
419  success = false;
420  continue;
421  }
422  fAdr_t dest = ctt->getDest(ctx,cLnk);
423  if (dest != 0 && !Forest::validUcastAdr(dest)) {
424  cerr << "Router::checkTables: dest addr "
425  << "for " << lnk << " in comtree " << comt
426  << " is not valid" << endl;
427  success = false;
428  }
429  int qid = ctt->getLinkQ(ctx,cLnk);
430  if (qid == 0) {
431  cerr << "Router::checkTables: queue id "
432  << "for " << lnk << " in comtree " << comt
433  << " is zero" << endl;
434  success = false;
435  }
436  }
437  if (!success) break;
438  for (int cLnk = ctt->firstRtrLink(ctx); cLnk != 0;
439  cLnk = ctt->nextRtrLink(ctx,cLnk)) {
440  int lnk = ctt->getLink(ctx,cLnk);
441  if (!ctt->isLink(ctx,lnk)) {
442  cerr << "Router::checkTables: router link "
443  << lnk << " is not valid in comtree "
444  << comt << endl;
445  success = false;
446  }
447  if (lt->getEntry(lnk).peerType != Forest::ROUTER) {
448  cerr << "Router::checkTables: router link "
449  << lnk << " in comtree " << comt
450  << " connects to non-router peer\n";
451  success = false;
452  }
453  }
454  for (int cLnk = ctt->firstCoreLink(ctx); cLnk != 0;
455  cLnk = ctt->nextCoreLink(ctx,cLnk)) {
456  int lnk = ctt->getLink(ctx,cLnk);
457  if (!ctt->isRtrLink(ctx,lnk)) {
458  cerr << "Router::checkTables: core link "
459  << lnk << " is not a router link "
460  << comt << endl;
461  success = false;
462  }
463  }
464  }
465  // come back later and add checks for route table
466  return success;
467 }
468 
474 bool Router::setAvailRates() {
475  bool success = true;
476  RateSpec minRates(Forest::MINBITRATE,Forest::MINBITRATE,
477  Forest::MINPKTRATE,Forest::MINPKTRATE);
478  RateSpec maxRates(Forest::MAXBITRATE,Forest::MAXBITRATE,
479  Forest::MAXPKTRATE,Forest::MAXPKTRATE);
480  int iface;
481  for (iface = ift->firstIface(); iface != 0;
482  iface = ift->nextIface(iface)) {
483  IfaceTable::Entry& e = ift->getEntry(iface);
484  if (!minRates.leq(e.rates) || !e.rates.leq(maxRates)) {
485  cerr << "Router::setAvailRates: interface rates "
486  "outside allowed range\n";
487  success = false;
488  }
489  e.availRates = e.rates;
490  }
491  if (!success) return false;
492  int lnk;
493  for (lnk = lt->firstLink(); lnk != 0; lnk = lt->nextLink(lnk)) {
494  LinkTable::Entry& lte = lt->getEntry(lnk);
495  if (!minRates.leq(lte.rates) || !lte.rates.leq(maxRates)) {
496  cerr << "Router::setAvailRates: link rates "
497  "outside allowed range\n";
498  success = false;
499  }
500  iface = lte.iface;
501  IfaceTable::Entry& ifte = ift->getEntry(iface);
502  if (!lte.rates.leq(ifte.availRates)) {
503  cerr << "Router::setAvailRates: oversubscribing "
504  "interface " << iface << endl;
505  success = false;
506  }
507  ifte.availRates.subtract(lte.rates);
508  lte.availRates = lte.rates;
509  lte.availRates.scale(.9); // allocate at most 90% of link
510  sm->clearLnkStats(lnk);
511  }
512  if (!success) return false;
513  int ctx;
514  for (ctx = ctt->firstComt(); ctx != 0;
515  ctx = ctt->nextComt(ctx)) {
516  for (int cLnk = ctt->firstComtLink(ctx); cLnk != 0;
517  cLnk = ctt->nextComtLink(ctx,cLnk)) {
518  int lnk = ctt->getLink(ctx,cLnk);
519  LinkTable::Entry& lte = lt->getEntry(lnk);
520  RateSpec comtRates = ctt->getRates(ctx, cLnk);
521  if (!comtRates.leq(lte.availRates)) {
522  cerr << "Router::setAvailRates: "
523  "oversubscribing link "
524  << lnk << endl;
525  success = false;
526  }
527  lte.availRates.subtract(comtRates);
528  }
529  }
530  return success;
531 }
532 
536 void Router::addLocalRoutes() {
537  for (int ctx = ctt->firstComt(); ctx != 0; ctx = ctt->nextComt(ctx)) {
538  int comt = ctt->getComtree(ctx);
539  for (int cLnk = ctt->firstComtLink(ctx); cLnk != 0;
540  cLnk = ctt->nextComtLink(ctx,cLnk)) {
541  int lnk = ctt->getLink(ctx,cLnk);
542  LinkTable::Entry& lte = lt->getEntry(lnk);
543  if (lte.peerType == Forest::ROUTER &&
544  Forest::zipCode(lte.peerAdr)
545  == Forest::zipCode(myAdr))
546  continue;
547  if (rt->getRtx(comt,lte.peerAdr) != 0)
548  continue;
549  rt->addRoute(comt,lte.peerAdr,cLnk);
550  }
551  }
552 }
553 
557 void Router::dump(ostream& out) {
558  out << "Interface Table\n\n" << ift->toString() << endl;
559  out << "Link Table\n\n" << lt->toString() << endl;
560  out << "Comtree Table\n\n" << ctt->toString() << endl;
561  out << "Routing Table\n\n" << rt->toString() << endl;
562  out << "Statistics\n\n" << sm->toString() << endl;
563 }
564 
565 void Router::run() {
566  // start input and output threads
567  thread inThred(RouterInProc::start,rip);
568  thread outThred(RouterOutProc::start,rop);
569 
570  // wait for them to finish
571  inThred.join();
572  outThred.join();
573 
574  cout << endl;
575  dump(cout); // print final tables
576  cout << endl;
577 }
578 
579 } // ends namespace