forest-net
an overlay networks for large-scale virtual worlds
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator
BuildRtables.cpp
Go to the documentation of this file.
1 
10 #include <string>
11 #include <queue>
12 #include "stdinc.h"
13 #include "Forest.h"
14 #include "NetInfo.h"
15 #include "ComtInfo.h"
16 #include "IfaceTable.h"
17 #include "QuManager.h"
18 #include "LinkTable.h"
19 #include "ComtreeTable.h"
20 
21 using namespace forest;
22 
33 bool buildIfaceTable(int, const NetInfo&, IfaceTable&);
34 bool buildLinkTable(int, const NetInfo&, LinkTable&);
35 bool buildComtTable(int, const NetInfo&, ComtInfo&, ComtreeTable&);
36 
37 int main() {
38  int maxNode = 100000; int maxLink = 10000;
39  int maxRtr = 5000; int maxCtl = 200;
40  int maxComtree = 10000;
41 
42  NetInfo net(maxNode, maxLink, maxRtr, maxCtl);
43  ComtInfo comtrees(maxComtree,net);
44 
45  if (!net.read(cin) || !comtrees.read(cin)) {
46  cerr << "buildTables: cannot read input\n";
47  exit(1);
48  }
49 
50  for (int r = net.firstRouter(); r != 0; r = net.nextRouter(r)) {
51  string rName; net.getNodeName(r,rName);
52 
53  // build and write interface table for r
54  IfaceTable *ifTbl = new IfaceTable(Forest::MAXINTF);
55  if (!buildIfaceTable(r, net, *ifTbl)) {
56  cerr << "buildTables: could not build interface table "
57  << "for router " << r << endl;
58  exit(1);
59  }
60  string iftName = rName + "/ift";
61  ofstream ifts; ifts.open(iftName.c_str());
62  if (ifts.fail()) {
63  cerr << "buildTables:: can't open interface table\n";
64  exit(1);
65  }
66  string s;
67  ifts << ifTbl->toString(s); ifts.close();
68 
69  // build and write link table for r
70  LinkTable *lnkTbl = new LinkTable(Forest::MAXLNK);
71  if (!buildLinkTable(r, net, *lnkTbl)) {
72  cerr << "buildTables: could not build link table "
73  << "for router " << r << endl;
74  exit(1);
75  }
76  string ltName = rName + "/lt";
77  ofstream lts; lts.open(ltName.c_str());
78  if (lts.fail()) {
79  cerr << "buildTables:: can't open link table\n";
80  exit(1);
81  }
82  lts << lnkTbl->toString(s); lts.close();
83 
84  // build and write comtree table for r
85  ComtreeTable *comtTbl = new ComtreeTable(10*Forest::MAXLNK,
86  20*Forest::MAXLNK,lnkTbl);
87  if (!buildComtTable(r, net, comtrees, *comtTbl)) {
88  cerr << "buildTables: could not build comtree table "
89  << "for router " << r << endl;
90  exit(1);
91  }
92  string cttName = rName + "/ctt";
93  ofstream ctts; ctts.open(cttName.c_str());
94  if (ctts.fail()) {
95  cerr << "buildTables:: can't open comtree table\n";
96  exit(1);
97  }
98  ctts << comtTbl->toString(s); ctts.close();
99 
100  delete lnkTbl; delete comtTbl;
101  }
102 }
103 
104 bool buildIfaceTable(int r, const NetInfo& net, IfaceTable& ift) {
105  for (int i = 1; i <= net.getNumIf(r); i++) {
106  if (!net.validIf(r,i)) continue;
107  RateSpec rs = net.getIfRates(r,i);
108  ift.addEntry(i, net.getIfIpAdr(r,i), net.getIfPort(r,i), rs);
109  }
110  return true;
111 }
112 
113 bool buildLinkTable(int r, const NetInfo& net, LinkTable& lt) {
114 
115  for (int lnk = net.firstLinkAt(r); lnk != 0;
116  lnk = net.nextLinkAt(r,lnk)) {
117 
118  // find the interface that "owns" this link
119  int iface = 0;
120  int llnk = net.getLLnum(lnk,r);
121  for (int i = 1; i <= net.getNumIf(r); i++) {
122  if (!net.validIf(r,i)) continue;
123  pair<int,int> leafRange; net.getIfLinks(r,i,leafRange);
124  if (llnk >= leafRange.first &&
125  llnk <= leafRange.second) {
126  iface = i; break;
127  }
128  }
129  // find peer and interface for link at peer
130  int peer = net.getPeer(r,lnk);
131  int peerIface = 0;
132  int plnk = net.getLLnum(lnk,peer);
133  for (int i = 1; i <= net.getNumIf(peer); i++) {
134  if (!net.validIf(peer,i)) continue;
135  pair<int,int> leafRange;
136  net.getIfLinks(peer,i,leafRange);
137  if (plnk >= leafRange.first &&
138  plnk <= leafRange.second) {
139  peerIface = i; break;
140  }
141  }
142  ipa_t peerIp = (net.getNodeType(peer) == Forest::ROUTER ?
143  net.getIfIpAdr(peer,peerIface) :
144  net.getLeafIpAdr(peer));
145  ipp_t peerPort = (net.getNodeType(peer) == Forest::ROUTER ?
146  Forest::ROUTER_PORT : 0);
147  lt.addEntry(llnk, peerIp, peerPort, 0);
148  lt.setIface(llnk,iface);
149  lt.setPeerType(llnk,net.getNodeType(peer));
150  lt.setPeerAdr(llnk,net.getNodeAdr(peer));
151  lt.getRates(llnk) = net.getLinkRates(lnk);
152  }
153 
154  return true;
155 }
156 
165 int findParentLink(int r, int ctx, const NetInfo& net,
166  const ComtInfo& comtrees) {
167  int ctRoot = comtrees.getRoot(ctx);
168  if (r == ctRoot) return 0;
169 
170  queue<int> pending; pending.push(ctRoot);
171 
172  int plink[net.getMaxNode()];
173  for (int i = 1; i <= net.getMaxNode(); i++) plink[i] = 0;
174 
175  while (!pending.empty()) {
176  vertex u = pending.front(); pending.pop();
177  for (edge e = net.firstLinkAt(u); e != 0;
178  e = net.nextLinkAt(u,e)) {
179  if (!comtrees.isComtLink(ctx,e) || e == plink[u]) continue;
180  vertex v = net.getPeer(u,e);
181  if (plink[v] != 0) {
182  cerr << "findParentLink: found cycle in "
183  << "comtree " << ctx << endl;
184  return -1;
185  }
186  if (v == r) return e;
187  pending.push(v); plink[v] = e;
188  }
189  }
190  cerr << "findParentLink: could not find target node " << r
191  << " in comtree " << comtrees.getComtree(ctx) << endl;
192  return -1;
193 }
194 
195 bool buildComtTable(int r, const NetInfo& net, ComtInfo& comtrees,
196  ComtreeTable& comtTbl) {
197 
198  // find the subset of comtrees involving this router
199  set<int> comtreeSet;
200  for (int ctx = comtrees.firstComtree(); ctx != 0;
201  ctx = comtrees.nextComtree(ctx)) {
202  fAdr_t radr = net.getNodeAdr(r);
203  if (comtrees.isComtRtr(ctx,radr))
204  comtreeSet.insert(ctx);
205  }
206 
207  set<int>::iterator p;
208  for (p = comtreeSet.begin(); p != comtreeSet.end(); p++) {
209  int ctx = *p;
210  int ctte = comtTbl.addEntry(comtrees.getComtree(ctx));
211  if (ctte == 0) {
212  cerr << "buildComtTable: detected inconsistency "
213  << "while building comtree table for router "
214  << r << " comtree " << comtrees.getComtree(ctx)
215  << endl;
216  return false;
217  }
218 
219  comtTbl.setCoreFlag(ctte,comtrees.isCoreNode(ctx,r));
220 
221  // add all comtree links incident to r and to the table entry
222  for (int lnk = net.firstLinkAt(r); lnk != 0;
223  lnk = net.nextLinkAt(r,lnk)) {
224  if (!comtrees.isComtLink(ctx,lnk)) continue;
225  int llnk = net.getLLnum(lnk,r);
226  int peer = net.getPeer(r,lnk);
227  comtTbl.addLink(ctte,llnk,net.isRouter(peer),
228  comtrees.isCoreNode(ctx,peer));
229  }
230 
231  // find parent link by doing a tree-traversal from root
232  //int plink = findParentLink(r,ctx,net,comtrees);
233  //if (plink < 0) return false;
234  int plink = comtrees.getPlink(ctx,r);
235  comtTbl.setPlink(ctte,net.getLLnum(plink,r));
236  }
237  return true;
238 }
239