开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
route.cc
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：21k
源码类别：

通讯编程

开发平台：

Visual C++

route.cc：源码内容
  1. /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
  2. /*
  3.  * Copyright (c) 1991-1994 Regents of the University of California.
  4.  * All rights reserved.
  5.  *
  6.  * Redistribution and use in source and binary forms, with or without
  7.  * modification, are permitted provided that the following conditions
  8.  * are met:
  9.  * 1. Redistributions of source code must retain the above copyright
  10.  *    notice, this list of conditions and the following disclaimer.
  11.  * 2. Redistributions in binary form must reproduce the above copyright
  12.  *    notice, this list of conditions and the following disclaimer in the
  13.  *    documentation and/or other materials provided with the distribution.
  14.  * 3. All advertising materials mentioning features or use of this software
  15.  *    must display the following acknowledgement:
  16.  * This product includes software developed by the University of
  17.  * California, Berkeley and the Network Research Group at
  18.  * Lawrence Berkeley Laboratory.
  19.  * 4. Neither the name of the University nor of the Laboratory may be used
  20.  *    to endorse or promote products derived from this software without
  21.  *    specific prior written permission.
  22.  *
  23.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33.  * SUCH DAMAGE.
  34.  *
  35.  * Routing code for general topologies based on min-cost routing algorithm in
  36.  * Bertsekas' book.  Written originally by S. Keshav, 7/18/88
  37.  * (his work covered by identical UC Copyright)
  38.  */
  40. #ifndef lint
  41. static const char rcsid[] =
  42. "@(#) $Header: /cvsroot/nsnam/ns-2/routing/route.cc,v 1.39 2005/09/12 04:34:16 tomh Exp $ (LBL)";
  43. #endif
  45. #include <stdlib.h>
  46. #include <assert.h>
  47. #include "config.h"
  48. #include "route.h"
  49. #include "address.h"
  51. class RouteLogicClass : public TclClass {
  52. public:
  53. RouteLogicClass() : TclClass("RouteLogic") {}
  54. TclObject* create(int, const char*const*) {
  55. return (new RouteLogic());
  56. }
  57. } routelogic_class;
  59. void RouteLogic::reset_all()
  60. {
  61. delete[] adj_;
  62. delete[] route_;
  63. adj_ = 0; 
  64. route_ = 0;
  65. size_ = 0;
  66. }
  68. int RouteLogic::command(int argc, const char*const* argv)
  69. {
  70. Tcl& tcl = Tcl::instance();
  71. if (argc == 2) {
  72. if (strcmp(argv[1], "compute") == 0) {
  73. if (adj_ == 0)
  74. return (TCL_OK);
  75. compute_routes();
  76. return (TCL_OK);
  77. } else if (strcmp(argv[1], "hier-compute") == 0) {
  78. if (hadj_ == 0) {
  79. return (TCL_OK);
  80. }
  81. hier_compute();
  82. return (TCL_OK);
  83. } else if (strcmp(argv[1], "hier-print") == 0) {
  84. hier_print_hadj();
  85. return (TCL_OK);
  86. } else if (strcmp(argv[1], "hier-print-route") == 0) {
  87. hier_print_route();
  88. return (TCL_OK);
  89. } else if (strcmp(argv[1], "reset") == 0) {
  90. reset_all();
  91. return (TCL_OK);
  92. }
  93. } else if (argc > 2) {
  94. if (strcmp(argv[1], "insert") == 0) {
  95. int src = atoi(argv[2]) + 1;
  96. int dst = atoi(argv[3]) + 1;
  97. if (src <= 0 || dst <= 0) {
  98. tcl.result("negative node number");
  99. return (TCL_ERROR);
  100. }
  101. double cost = (argc == 5 ? atof(argv[4]) : 1);
  102. insert(src, dst, cost);
  103. return (TCL_OK);
  104. } else if (strcmp(argv[1], "hlevel-is") == 0) {
  105. level_ = atoi(argv[2]);
  106. if (level_ < 1) {
  107. tcl.result("send-hlevel: # hierarchy levels should be non-zero");
  108. return (TCL_ERROR);
  109. }
  110. return (TCL_OK);
  111. } else if (strcmp(argv[1], "send-num-of-domains") == 0) {
  112. D_ = atoi(argv[2]) + 1;
  113. if (D_ <= 1) {
  114. tcl.result("send-num-of-domains: # domains should be larger than 1");
  115. return (TCL_ERROR);
  116. }
  117. return (TCL_OK);
  118. } else if (strcmp(argv[1], "send-num-of-clusters") == 0) {
  119. if (argc != D_ + 1) {
  120. tcl.resultf("send-num-of-clusters: # of "
  121.     "clusters %d != domain (%d) + 1n",
  122.     argc, D_);
  123. return (TCL_ERROR);
  124. }
  125. C_ = new int[D_];
  126. int i, j = 2;
  127. for (i = 1; i < D_; i++) {
  128. C_[i] = atoi(argv[j]) + 1;
  129. j++;
  130. }
  131. hier_init();
  132. return (TCL_OK);
  133. } else if(strcmp(argv[1], "send-num-of-nodes") == 0) {
  134. int i, j, k=2, Ctotal=0 ;
  135. for (i=1; i < D_; i++)
  136. Ctotal = Ctotal + (C_[i]-1);
  137. if (argc != (Ctotal + 2)) {
  138. tcl.result("send-hlastdata: # args do not match");
  139. return (TCL_ERROR);
  140. }
  141. for (i=1; i < D_; i++)
  142. for (j=1; (j < C_[i]); j++) {
  143. cluster_size_[INDEX(i, j, Cmax_)] = atoi(argv[k]);
  144. k++;
  145. }
  146. return (TCL_OK);
  147. } else if (strcmp(argv[1], "hier-insert") == 0) {
  148. if(Cmax_== 0 || D_== 0) {
  149. tcl.result("Required Hier_data not sent");
  150. return (TCL_ERROR);
  151. }
  152. int i;
  153. int src_addr[SMALL_LEN], dst_addr[SMALL_LEN];
  154. str2address(argv, src_addr, dst_addr);
  155. for (i=0; i < level_; i++)
  156. if (src_addr[i]<=0 || dst_addr[i]<=0){
  157. tcl.result ("negative node number");
  158. return (TCL_ERROR);
  159. }
  160. int cost = (argc == 5 ? atoi(argv[4]) : 1);
  161. hier_insert(src_addr, dst_addr, cost);
  162. return (TCL_OK);
  163. } else if (strcmp(argv[1], "hier-reset") == 0) {
  164. int i;
  165. int  src_addr[SMALL_LEN], dst_addr[SMALL_LEN];
  167. str2address(argv, src_addr, dst_addr);
  168. // assuming node-node addresses (instead of 
  169. // node-cluster or node-domain pair) 
  170. // are sent for hier_reset  
  171. for (i=0; i < level_; i++)
  172. if (src_addr[i]<=0 || dst_addr[i]<=0){
  173. tcl.result ("negative node number");
  174. return (TCL_ERROR);
  175. }
  176. hier_reset(src_addr, dst_addr);
  177. return (TCL_OK);
  178. } else if (strcmp(argv[1], "hier-lookup") == 0) {
  179. int nh;
  180. int res = lookup_hier((char*)argv[2], (char*)argv[3],
  181.       nh);
  182. return res;
  183. } else if (strcmp(argv[1], "reset") == 0) {
  184. int src = atoi(argv[2]) + 1;
  185. int dst = atoi(argv[3]) + 1;
  186. if (src <= 0 || dst <= 0) {
  187. tcl.result("negative node number");
  188. return (TCL_ERROR);
  189. }
  190. reset(src, dst);
  191. return (TCL_OK);
  192. } else if (strcmp(argv[1], "lookup") == 0) {
  193. int nh;
  194. int res = lookup_flat((char*)argv[2], (char*)argv[3], 
  195.       nh);
  196. if (res == TCL_OK)
  197. tcl.resultf("%d", nh);
  198. return res;
  199. }
  200. }
  201. return (TclObject::command(argc, argv));
  202. }
  204. // xxx: using references as in this result is bogus---use pointers!
  205. int RouteLogic::lookup_flat(char* asrc, char* adst, int& result) {
  206. Tcl& tcl = Tcl::instance();
  207. int src = atoi(asrc) + 1;
  208. int dst = atoi(adst) + 1;
  210. if (route_ == 0) {
  211. // routes are computed only after the simulator is running
  212. // ($ns run).
  213. tcl.result("routes not yet computed");
  214. return (TCL_ERROR);
  215. }
  216. if (src >= size_ || dst >= size_) {
  217. tcl.result("node out of range");
  218. return (TCL_ERROR);
  219. }
  220. result = route_[INDEX(src, dst, size_)].next_hop - 1;
  221. return TCL_OK;
  222. }
  224. //added for pushback. a method callable from c++ code. 
  225. //probably could have been concocted from already existing methods - ratul
  226. int RouteLogic::lookup_flat(int sid, int did) {
  227. int src = sid+1;
  228. int dst = did+1;
  229. if (route_ == 0) {
  230. // routes are computed only after the simulator is running
  231. // ($ns run).
  232. printf("routes not yet computedn");
  233. return (-1);
  234. }
  235. if (src >= size_ || dst >= size_) {
  236. printf("node out of rangen");
  237. return (-2);
  238. }
  239. return route_[INDEX(src, dst, size_)].next_hop - 1;
  240. }
  242. // xxx: using references as in this result is bogus---use pointers!
  243. int RouteLogic::lookup_hier(char* asrc, char* adst, int& result) {
  244. int i;
  245. int src[SMALL_LEN], dst[SMALL_LEN];
  246. Tcl& tcl = Tcl::instance();
  248. if ( hroute_ == 0) {
  249. tcl.result("Required Hier_data not sent");
  250. return TCL_ERROR;
  251. }
  252.       
  253. ns_strtok(asrc, src);
  254. ns_strtok(adst, dst);
  256. for (i=0; i < level_; i++)
  257. if (src[i] <= 0) {
  258. tcl.result("negative src node number");
  259. return TCL_ERROR;
  260. }
  261. if (dst[0] <= 0) {
  262. tcl.result("negative dst domain number");
  263. return TCL_ERROR;
  264. }
  266. int d = src[0];
  267. int index = INDEX(src[0], src[1], Cmax_);
  268. int size = cluster_size_[index];
  270. if (hsize_[index] == 0) {
  271. tcl.result("Routes not computed");
  272. return TCL_ERROR;
  273. }
  274. if ((src[0] < D_) || (dst[0] < D_)) {
  275. if((src[1] < C_[d]) || (dst[1] < C_[dst[0]]))
  276. if((src[2] <= size) ||
  277.    (dst[2]<=cluster_size_[INDEX(dst[0],dst[1],Cmax_)]))
  278. ;
  279. } else { 
  280. tcl.result("node out of range");
  281. return TCL_ERROR;
  282. }
  283. int next_hop = 0;
  284. /* if node-domain lookup */
  285. if (((dst[1] <= 0) && (dst[2] <= 0)) ||
  286.     (src[0] != dst[0])){
  287. next_hop = hroute_[index][N_D_INDEX(src[2], dst[0], size, C_[d], D_)];
  288. }
  289. /* if node-cluster lookup */
  290. else if ((dst[2] <= 0) || (src[1] != dst[1])) {
  291. next_hop = hroute_[index][N_C_INDEX(src[2], dst[1], size, C_[d], D_)];
  292. }
  293. /* if node-node lookup */
  294. else {
  295. next_hop = hroute_[index][N_N_INDEX(src[2], dst[2], size, C_[d], D_)];
  296. }
  298. char target[SMALL_LEN];
  299. if (next_hop > 0) {
  300. get_address(target, next_hop, index, d, size, src);
  301. tcl.result(target);
  302. result= Address::instance().str2addr(target);
  303. } else {
  304. tcl.result("-1");
  305. result = -1;
  306. }
  307. return TCL_OK;
  308. }
  310. RouteLogic::RouteLogic()
  311. {
  312. size_ = 0;
  313. adj_ = 0;
  314. route_ = 0;
  315. /* additions for hierarchical routing extension */
  316. C_ = 0;
  317. D_ = 0;
  318. Cmax_ = 0;
  319. level_ = 0;
  320. hsize_ = 0;
  321. hadj_ = 0;
  322. hroute_ = 0;
  323. hconnect_ = 0;
  324. cluster_size_ = 0;
  325. }
  327. RouteLogic::~RouteLogic()
  328. {
  329. delete[] adj_;
  330. delete[] route_;
  332. for (int i = 0; i < (Cmax_ * D_); i++) {
  333. for (int j = 0; j < (Cmax_ + D_) * (cluster_size_[i]+1); j++) {
  334. if (hconnect_[i][j] != NULL)
  335. delete [] hconnect_[i][j];
  336. }
  337. delete [] hconnect_[i];
  338. }
  340. for (int n =0; n < (Cmax_ * D_); n++) {
  341. if (hadj_[n] != NULL)
  342. delete [] hadj_[n];
  343. if (hroute_[n] != NULL)
  344. delete [] hroute_[n];
  345. }
  347. delete [] C_;
  348. delete [] hsize_;
  349. delete [] cluster_size_;
  350. delete hadj_;
  351. delete hroute_;
  352. delete hconnect_;
  353. }
  355. void RouteLogic::alloc(int n)
  356. {
  357. size_ = n;
  358. n *= n;
  359. adj_ = new adj_entry[n];
  360. for (int i = 0; i < n; ++i) {
  361. adj_[i].cost = INFINITY;
  362. adj_[i].entry = 0;
  363. }
  364. }
  366. /*
  367.  * Check that we have enough storage in the adjacency array
  368.  * to hold a node numbered "n"
  369.  */
  370. void RouteLogic::check(int n)
  371. {
  372. if (n < size_)
  373. return;
  375. adj_entry* old = adj_;
  376. int osize = size_;
  377. int m = osize;
  378. if (m == 0)
  379. m = 16;
  380. while (m <= n)
  381. m <<= 1;
  383. alloc(m);
  384. for (int i = 0; i < osize; ++i) {
  385. for (int j = 0; j < osize; ++j)
  386. adj_[INDEX(i, j, m)].cost =old[INDEX(i, j, osize)].cost;
  387. }
  388. size_ = m;
  389. delete[] old;
  390. }
  392. void RouteLogic::insert(int src, int dst, double cost)
  393. {
  394. check(src);
  395. check(dst);
  396. adj_[INDEX(src, dst, size_)].cost = cost;
  397. }
  398. void RouteLogic::insert(int src, int dst, double cost, void* entry_)
  399. {
  400. check(src);
  401. check(dst);
  402. adj_[INDEX(src, dst, size_)].cost = cost;
  403. adj_[INDEX(src, dst, size_)].entry = entry_;
  404. }
  406. void RouteLogic::reset(int src, int dst)
  407. {
  408. assert(src < size_);
  409. assert(dst < size_);
  410. adj_[INDEX(src, dst, size_)].cost = INFINITY;
  411. }
  413. void RouteLogic::compute_routes()
  414. {
  415. int n = size_;
  416. int* parent = new int[n];
  417. double* hopcnt = new double[n];
  418. #define ADJ(i, j) adj_[INDEX(i, j, size_)].cost
  419. #define ADJ_ENTRY(i, j) adj_[INDEX(i, j, size_)].entry
  420. #define ROUTE(i, j) route_[INDEX(i, j, size_)].next_hop
  421. #define ROUTE_ENTRY(i, j) route_[INDEX(i, j, size_)].entry
  422. delete[] route_;
  423. route_ = new route_entry[n * n];
  424. memset((char *)route_, 0, n * n * sizeof(route_[0]));
  426. /* do for all the sources */
  427. int k;
  428. for (k = 1; k < n; ++k) {
  429. int v;
  430. for (v = 0; v < n; v++)
  431. parent[v] = v;
  433. /* set the route for all neighbours first */
  434. for (v = 1; v < n; ++v) {
  435. if (parent[v] != k) {
  436. hopcnt[v] = ADJ(k, v);
  437. if (hopcnt[v] != INFINITY) {
  438. ROUTE(k, v) = v;
  439. ROUTE_ENTRY(k, v) = ADJ_ENTRY(k, v);
  440. }
  441. }
  442. }
  443. for (v = 1; v < n; ++v) {
  444. /*
  445.  * w is the node that is the nearest to the subtree
  446.  * that has been routed
  447.  */
  448. int o = 0;
  449. /* XXX */
  450. hopcnt[0] = INFINITY;
  451. int w;
  452. for (w = 1; w < n; w++)
  453. if (parent[w] != k && hopcnt[w] < hopcnt[o])
  454. o = w;
  455. parent[o] = k;
  456. /*
  457.  * update distance counts for the nodes that are
  458.  * adjacent to o
  459.  */
  460. if (o == 0)
  461. continue;
  462. for (w = 1; w < n; w++) {
  463. if (parent[w] != k &&
  464.     hopcnt[o] + ADJ(o, w) < hopcnt[w]) {
  465. ROUTE(k, w) = ROUTE(k, o);
  466. ROUTE_ENTRY(k, w) = 
  467.     ROUTE_ENTRY(k, o);
  468. hopcnt[w] = hopcnt[o] + ADJ(o, w);
  469. }
  470. }
  471. }
  472. }
  473. /*
  474.  * The route to yourself is yourself.
  475.  */
  476. for (k = 1; k < n; ++k) {
  477. ROUTE(k, k) = k;
  478. ROUTE_ENTRY(k, k) = 0; // This should not matter
  479. }
  481. delete[] hopcnt;
  482. delete[] parent;
  483. }
  485. /* hierarchical routing support */
  487. /*
  488.  * This function creates adjacency matrix for each cluster at the lowest level
  489.  * of the hierarchy for every node in the cluster, for every other cluster in 
  490.  * the domain, and every other domain. can be extended from 3-level hierarchy 
  491.  * to n-level along similar lines
  492.  */
  493. void RouteLogic::hier_alloc(int i)
  494. {
  495. hsize_[i] = cluster_size_[i]+ Cmax_+ D_ ;
  496. hsize_[i] *= hsize_[i];
  497. hadj_[i] = new int[hsize_[i]];
  498. hroute_[i] = new int[hsize_[i]];
  499. hconnect_[i] = new char*[(Cmax_ + D_) * (cluster_size_[i]+1)];
  500. for (int n = 0; n < hsize_[i]; n++){
  501. hadj_[i][n] = INFINITY;
  502. hroute_[i][n] = INFINITY;
  503. }
  504. }
  506. void RouteLogic::hier_check(int i)
  507. {
  508. if(hsize_[i] > 0)
  509. return;
  510. else
  511. hier_alloc(i);
  512. }
  514. void RouteLogic::hier_init(void) 
  515. {
  516. int i;
  518. for (i = 1; i < D_; i++) {
  519. Cmax_ = C_[i] > Cmax_ ? C_[i]: Cmax_;
  520. }
  521. int arr_size = Cmax_ * D_ ;
  522. cluster_size_ = new int[arr_size]; 
  523. hsize_ = new int[arr_size];
  524. for (i = 0; i < arr_size; i++)
  525. hsize_[i] = 0;
  526. hadj_ = new int*[arr_size];
  527. hroute_ = new int*[arr_size];
  528. hconnect_ = new char**[arr_size];
  529. }
  532. int RouteLogic::domain_size(int domain) { 
  533. return (C_[domain+1]-1); 
  534. }
  535. int RouteLogic::cluster_size(int d, int c) {
  536. d += 1;
  537. c += 1;
  538. return (cluster_size_[INDEX(d, c, Cmax_)]);
  539. }
  541. int RouteLogic::elements_in_level(int *addr, int level) {
  542. if (level == 1)
  543. return (domains());
  544. else if (level == 2)
  545. return (domain_size(addr[0]));
  546. else if (level == 3) {
  547. return (cluster_size(addr[0], addr[1]));
  548. }
  549. return (-1);
  550. }
  552. void RouteLogic::str2address(const char*const* argv, int *src_addr, int *dst_addr)
  553. {
  554. char src[SMALL_LEN];
  555. char dst[SMALL_LEN];
  557. strcpy(src, argv[2]);
  558. strcpy(dst, argv[3]);
  560. ns_strtok(src, src_addr);
  561. ns_strtok(dst, dst_addr);
  562. }
  564. void RouteLogic::ns_strtok(char *addr, int *addrstr)
  565. {
  566. int i;
  567. char tmpstr[SMALL_LEN];
  568. char *next, *index;
  570. i = 0;
  571. strcpy(tmpstr, addr);
  572. next = tmpstr;
  573. while(*next){
  574. index = strstr(next, ".");
  575. if (index != NULL){
  576. next[index - next] = '';
  577. addrstr[i] = atoi(next) + 1;
  578. next = index + 1;
  579. i++;
  580. }
  581. else {
  582. if (*next != '') //damn that ending point
  583. addrstr[i] = atoi(next) + 1;
  584. break;
  585. }
  586. }
  587. }
  590. void RouteLogic::get_address(char *address, int next_hop, int index, int d, 
  591.      int size, int *src)
  592. {
  593. if (next_hop <= size) {
  594. sprintf(address,"%d.%d.%d", src[0]-1, src[1]-1, next_hop-1);
  595. }
  596. else if ((next_hop > size) && (next_hop < (size + C_[d]))) {
  597. int temp = next_hop - size;
  598. int I = src[2] * (C_[d] + D_) + temp;
  599. strcpy(address, hconnect_[index][I]);
  600. }
  601. else {
  602. int temp = next_hop - size - (C_[d] - 1);
  603. int I = src[2] * (C_[d] + D_) + (C_[d] - 1 + temp);
  604. strcpy(address,hconnect_[index][I]);
  605. }
  606. }
  608. void RouteLogic::hier_reset(int *src, int *dst)
  609. {
  610. int i, d, n;
  611. d = src[0];
  612. if (src[0] == dst[0])
  613. if (src[1] == dst[1]) {
  614. i = INDEX(src[0], src[1], Cmax_);
  615. n = cluster_size_[i];
  616. hadj_[i][N_N_INDEX(src[2], dst[2], n, C_[d], D_)] = INFINITY;
  617. } else {
  618. for (int y=1; y < C_[d]; y++) { 
  619. i = INDEX(src[0], y, Cmax_);
  620. n = cluster_size_[i];
  621. hadj_[i][C_C_INDEX(src[1], dst[1], n, C_[d], D_)] = INFINITY;
  622. if (y == src[1])
  623. hadj_[i][N_C_INDEX(src[2], dst[1], n, C_[d], D_)] = INFINITY; 
  624. }
  625. }
  626. else {
  627. for (int x=1; x < D_; x++)
  628. for (int y=1; y < C_[x]; y++) {
  629. i = INDEX(x, y, Cmax_);
  630. n = cluster_size_[i];
  631. hadj_[i][D_D_INDEX(src[0], dst[0], n, C_[x], D_)] = INFINITY;
  632. if ( x == src[0] ){
  633. hadj_[i][C_D_INDEX(src[1], dst[0], n, C_[x], D_)] = INFINITY;
  634. if (y == src[1])
  635. hadj_[i][N_D_INDEX(src[2], dst[0], n, C_[x], D_)] = INFINITY;
  636. }
  637. }
  638. }
  639. }
  641. void RouteLogic::hier_insert(int *src_addr, int *dst_addr, int cost)
  642. {
  643. int X1 = src_addr[0];
  644. int Y1 = src_addr[1];
  645. int Z1 = src_addr[2];
  646. int X2 = dst_addr[0];
  647. int Y2 = dst_addr[1];
  648. int Z2 = dst_addr[2];
  649. int n, i;
  651. if ( X1 == X2)
  652. if (Y1 == Y2){ 
  653. /*
  654.  * For the same domain & cluster 
  655.  */
  656. i = INDEX(X1, Y1, Cmax_);
  657. n = cluster_size_[i];
  658. hier_check(i);
  659. hadj_[i][N_N_INDEX(Z1, Z2, n, C_[X1], D_)] = cost;
  660. } else { 
  661. /* 
  662.  * For the same domain but diff clusters 
  663.  */
  664. for (int y=1; y < C_[X1]; y++) { /* insert cluster connectivity */
  665. i = INDEX(X1, y, Cmax_);
  666. n = cluster_size_[i];
  667. hier_check(i);
  668. hadj_[i][C_C_INDEX(Y1, Y2, n, C_[X1], D_)] = cost;
  670. if (y == Y1) {  /* insert node conn. */
  671. hadj_[i][N_C_INDEX(Z1, Y2, n, C_[X1], D_)] = cost;
  672. int I = Z1 * (C_[X1]+ D_) + Y2;
  673. hconnect_[i][I] = new char[SMALL_LEN];
  674. sprintf(hconnect_[i][I],"%d.%d.%d",X2-1,Y2-1,Z2-1);
  675. }
  676. }
  677. }
  678. else { 
  679. /* 
  680.  * For different domains 
  681.  */
  682. for (int x=1; x < D_; x++) { /* inset domain connectivity */
  683. for (int y=1; y < C_[x]; y++) {
  684. i = INDEX(x, y, Cmax_);
  685. n = cluster_size_[i];
  686. hier_check(i);
  687. hadj_[i][D_D_INDEX(X1, X2, n, C_[x], D_)] = cost;
  688. }
  689. }
  690. for (int y=1; y < C_[X1]; y++) { /* insert cluster connectivity */
  691. i = INDEX(X1, y, Cmax_);
  692. n = cluster_size_[i];
  693. hier_check(i);
  694. hadj_[i][C_D_INDEX(Y1, X2, n, C_[X1], D_)] = cost;
  695. }
  696. /* insert node connectivity */
  697. i = INDEX(X1, Y1, Cmax_);
  698. n = cluster_size_[i]; 
  699. hadj_[i][N_D_INDEX(Z1, X2, n, C_[X1], D_)] = cost;
  700. int I = Z1 * (C_[X1] + D_) + (C_[X1] - 1 + X2);
  701. hconnect_[i][I] = new char[SMALL_LEN];
  702. sprintf(hconnect_[i][I],"%d.%d.%d",X2-1,Y2-1,Z2-1);
  703. }
  704. }
  706. void RouteLogic::hier_compute_routes(int i, int j)
  707. {
  708. int size = (cluster_size_[i] + C_[j] + D_);
  709. int n = size ;
  710. double* hopcnt = new double[n];
  711. #define HADJ(i, j) adj_[INDEX(i, j, size)].cost
  712. #define HROUTE(i, j) route_[INDEX(i, j, size)].next_hop
  713. delete[] route_;
  714. route_ = new route_entry[n * n];
  715. int* parent = new int[n];
  716. memset((char *)route_, 0, n * n * sizeof(route_[0]));
  718. /* do for all the sources */
  719. int k;
  720. for (k = 1; k < n; ++k) {
  721. int v;
  722. for (v = 0; v < n; v++)
  723. parent[v] = v;
  725. /* set the route for all neighbours first */
  726. for (v = 1; v < n; ++v) {
  727. if (parent[v] != k) {
  728. hopcnt[v] = HADJ(k, v);
  729. if (hopcnt[v] != INFINITY)
  730. HROUTE(k, v) = v;
  731. }
  732. }
  733. for (v = 1; v < n; ++v) {
  734. /*
  735.  * w is the node that is the nearest to the subtree
  736.  * that has been routed
  737.  */
  738. int o = 0;
  739. /* XXX */
  740. hopcnt[0] = INFINITY;
  741. int w;
  742. for (w = 1; w < n; w++)
  743. if (parent[w] != k && hopcnt[w] < hopcnt[o])
  744. o = w;
  745. parent[o] = k;
  746. /*
  747.  * update distance counts for the nodes that are
  748.  * adjacent to o
  749.  */
  750. if (o == 0)
  751. continue;
  752. for (w = 1; w < n; w++) {
  753. if (parent[w] != k &&
  754.     hopcnt[o] + HADJ(o, w) < hopcnt[w]) {
  755. HROUTE(k, w) = HROUTE(k, o);
  756. hopcnt[w] = hopcnt[o] + HADJ(o, w);
  757. }
  758. }
  759. }
  760. }
  761. /*
  762.  * The route to yourself is yourself.
  763.  */
  764. for (k = 1; k < n; ++k)
  765. HROUTE(k, k) = k;
  767. delete[] hopcnt;
  768. delete[] parent;
  769. }
  771. /* function to check the adjacency matrices created */
  772. void RouteLogic::hier_print_hadj() {
  773. int i, j, k;
  775. for (j=1; j < D_; j++) 
  776. for (k=1; k < C_[j]; k++) {
  777. i = INDEX(j, k, Cmax_);
  778. int s = (cluster_size_[i] + C_[j] + D_);
  779. printf("ADJ MATRIX[%d] for cluster %d.%d :n",i,j,k);
  780. int temp = 1;
  781. printf(" ");
  782. while(temp < s){
  783. printf(" %d",temp);
  784. temp++;
  785. }
  786. printf("n");
  787. for(int n=1; n < s;n++){
  788. printf("%d ",n);
  789. for(int m=1;m < s;m++){
  790. if(hadj_[i][INDEX(n,m,s)] == INFINITY)
  791. printf("~ ");
  792. else
  793. printf("%d ",hadj_[i][INDEX(n,m,s)]);
  794. }
  795. printf("n");
  796. }
  797. printf("nn");
  798. }
  799. }
  801. void RouteLogic::hier_compute()
  802. {
  803. int i, j, k, m, n;
  804. for (j=1; j < D_; j++) 
  805. for (k=1; k < C_[j]; k++) {
  806. i = INDEX(j, k, Cmax_);
  807. int s = (cluster_size_[i] + C_[j] + D_);
  808. adj_ = new adj_entry[(s * s)];
  809. memset((char *)adj_, 0, s * s * sizeof(adj_[0]));
  810. for (n=0; n < s; n++)
  811. for(m=0; m < s; m++)
  812. adj_[INDEX(n, m, s)].cost = hadj_[i][INDEX(n, m, s)];
  813. hier_compute_routes(i, j);
  815. for (n=0; n < s; n++)
  816. for(m=0; m < s; m++)
  817. hroute_[i][INDEX(n, m, s)] = route_[INDEX(n, m, s)].next_hop;
  818. delete [] adj_;
  819. }
  820. }
  822. /*
  823.  * Prints routing table - debugging function
  824.  */
  825. void RouteLogic::hier_print_route()
  826. {
  827. for (int j=1; j < D_; j++) 
  828. for (int k=1; k < C_[j]; k++) {
  829. int i = INDEX(j, k, Cmax_);
  830. int s = (cluster_size_[i]+C_[j]+D_);
  831. printf("ROUTE_TABLE[%d] for cluster %d.%d :n",i,j,k);
  832. int temp = 1;
  833. printf(" ");
  834. while(temp < s){
  835. printf(" %d",temp);
  836. temp++;
  837. }
  838. printf("n");
  839. for(int n=1; n < s; n++){
  840. printf("%d ",n);
  841. for(int m=1; m < s; m++)
  842. printf("%d ",hroute_[i][INDEX(n, m, s)]);
  843. printf("n");
  844. }
  845. printf("nn");
  846. }
  847. }
  849. static class RouteLogicAlgoClass : public TclClass {
  850. public:
  851. RouteLogicAlgoClass() : TclClass("RouteLogic/Algorithmic") {}
  852. TclObject* create(int, const char*const*) {
  853. return (new RouteLogicAlgo);
  854. }
  855. } class_routelogic_algo;