route.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1991-1994 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the University of
 *      California, Berkeley and the Network Research Group at
 *      Lawrence Berkeley Laboratory.
 * 4. Neither the name of the University nor of the Laboratory may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * Routing code for general topologies based on min-cost routing algorithm in
 * Bertsekas' book.  Written originally by S. Keshav, 7/18/88
 * (his work covered by identical UC Copyright)
 */

#ifndef lint
static const char rcsid[] =
"@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/routing/route.cc,v 1.38 2001/02/22 19:45:39 haldar Exp $ (LBL)";
#endif

#include <stdlib.h>
#include <assert.h>
#include "config.h"
#include "route.h"
#include "address.h"

class RouteLogicClass : public TclClass {
public:
        RouteLogicClass() : TclClass("RouteLogic") {}
        TclObject* create(int, const char*const*) {
                return (new RouteLogic());
        }
} routelogic_class;

void RouteLogic::reset_all()
{
        delete[] adj_;
        delete[] route_;
        adj_ = 0; 
        route_ = 0;
        size_ = 0;
}

int RouteLogic::command(int argc, const char*const* argv)
{
        Tcl& tcl = Tcl::instance();
        if (argc == 2) {
                if (strcmp(argv[1], "compute") == 0) {
                        if (adj_ == 0)
                                return (TCL_OK);
                        compute_routes();
                        return (TCL_OK);
                } else if (strcmp(argv[1], "hier-compute") == 0) {
                        if (hadj_ == 0) {
                                return (TCL_OK);
                        }
                        hier_compute();
                        return (TCL_OK);
                } else if (strcmp(argv[1], "hier-print") == 0) {
                        hier_print_hadj();
                        return (TCL_OK);
                } else if (strcmp(argv[1], "hier-print-route") == 0) {
                        hier_print_route();
                        return (TCL_OK);
                } else if (strcmp(argv[1], "reset") == 0) {
                        reset_all();
                        return (TCL_OK);
                }
        } else if (argc > 2) {
                if (strcmp(argv[1], "insert") == 0) {
                        int src = atoi(argv[2]) + 1;
                        int dst = atoi(argv[3]) + 1;
                        if (src <= 0 || dst <= 0) {
                                tcl.result("negative node number");
                                return (TCL_ERROR);
                        }
                        double cost = (argc == 5 ? atof(argv[4]) : 1);
                        insert(src, dst, cost);
                        return (TCL_OK);
                } else if (strcmp(argv[1], "hlevel-is") == 0) {
                        level_ = atoi(argv[2]);
                        if (level_ < 1) {
                                tcl.result("send-hlevel: # hierarchy levels should be non-zero");
                                return (TCL_ERROR);
                        }
                        return (TCL_OK);
                } else if (strcmp(argv[1], "send-num-of-domains") == 0) {
                        D_ = atoi(argv[2]) + 1;
                        if (D_ <= 1) {
                                tcl.result("send-num-of-domains: # domains should be larger than 1");
                                return (TCL_ERROR);
                        }
                        return (TCL_OK);
                } else if (strcmp(argv[1], "send-num-of-clusters") == 0) {
                        if (argc != D_ + 1) {
                                tcl.resultf("send-num-of-clusters: # of "
                                            "clusters %d != domain (%d) + 1\n",
                                            argc, D_);
                                return (TCL_ERROR);
                        }
                        C_ = new int[D_];
                        int i, j = 2;
                        for (i = 1; i < D_; i++) {
                                C_[i] = atoi(argv[j]) + 1;
                                j++;
                        }
                        hier_init();
                        return (TCL_OK);
                } else if(strcmp(argv[1], "send-num-of-nodes") == 0) {
                        int i, j, k=2, Ctotal=0 ;
                        for (i=1; i < D_; i++)
                                Ctotal = Ctotal + (C_[i]-1);
                        if (argc != (Ctotal + 2)) {
                                tcl.result("send-hlastdata: # args do not match");
                                return (TCL_ERROR);
                        }
                        for (i=1; i < D_; i++)
                                for (j=1; (j < C_[i]); j++) {
                                        cluster_size_[INDEX(i, j, Cmax_)] = atoi(argv[k]);
                                        k++;
                                }
                        return (TCL_OK);
                } else if (strcmp(argv[1], "hier-insert") == 0) {
                        if(Cmax_== 0 || D_== 0) {
                                tcl.result("Required Hier_data not sent");
                                return (TCL_ERROR);
                        }
                        int i;
                        int src_addr[SMALL_LEN], dst_addr[SMALL_LEN];
                        str2address(argv, src_addr, dst_addr);
                        for (i=0; i < level_; i++)
                                if (src_addr[i]<=0 || dst_addr[i]<=0){
                                        tcl.result ("negative node number");
                                        return (TCL_ERROR);
                                }
                        int cost = (argc == 5 ? atoi(argv[4]) : 1);
                        hier_insert(src_addr, dst_addr, cost);
                        return (TCL_OK);
                } else if (strcmp(argv[1], "hier-reset") == 0) {
                        int i;
                        int  src_addr[SMALL_LEN], dst_addr[SMALL_LEN];
                        
                        str2address(argv, src_addr, dst_addr);
                        // assuming node-node addresses (instead of 
                        // node-cluster or node-domain pair) 
                        // are sent for hier_reset  
                        for (i=0; i < level_; i++)
                                if (src_addr[i]<=0 || dst_addr[i]<=0){
                                        tcl.result ("negative node number");
                                        return (TCL_ERROR);
                                }
                        hier_reset(src_addr, dst_addr);
                } else if (strcmp(argv[1], "hier-lookup") == 0) {
                        int nh;
                        int res = lookup_hier((char*)argv[2], (char*)argv[3],
                                              nh);
                        return res;
                } else if (strcmp(argv[1], "reset") == 0) {
                        int src = atoi(argv[2]) + 1;
                        int dst = atoi(argv[3]) + 1;
                        if (src <= 0 || dst <= 0) {
                                tcl.result("negative node number");
                                return (TCL_ERROR);
                        }
                        reset(src, dst);
                        return (TCL_OK);
                } else if (strcmp(argv[1], "lookup") == 0) {
                        int nh;
                        int res = lookup_flat((char*)argv[2], (char*)argv[3], 
                                              nh);
                        if (res == TCL_OK)
                                tcl.resultf("%d", nh);
                        return res;
                }
        }
        return (TclObject::command(argc, argv));
}

// xxx: using references as in this result is bogus---use pointers!
int RouteLogic::lookup_flat(char* asrc, char* adst, int& result) {
        Tcl& tcl = Tcl::instance();
        int src = atoi(asrc) + 1;
        int dst = atoi(adst) + 1;

        if (route_ == 0) {
                // routes are computed only after the simulator is running
                // ($ns run).
                tcl.result("routes not yet computed");
                return (TCL_ERROR);
        }
        if (src >= size_ || dst >= size_) {
                tcl.result("node out of range");
                return (TCL_ERROR);
        }
        result = route_[INDEX(src, dst, size_)].next_hop - 1;
        return TCL_OK;
}

//added for pushback. a method callable from c++ code. 
//probably could have been concocted from already existing methods - ratul
int RouteLogic::lookup_flat(int sid, int did) {
        int src = sid+1;
        int dst = did+1;
        if (route_ == 0) {
                // routes are computed only after the simulator is running
                // ($ns run).
                printf("routes not yet computed\n");
                return (-1);
        }
        if (src >= size_ || dst >= size_) {
                printf("node out of range\n");
                return (-2);
        }
        return route_[INDEX(src, dst, size_)].next_hop - 1;
}

// xxx: using references as in this result is bogus---use pointers!
int RouteLogic::lookup_hier(char* asrc, char* adst, int& result) {
        int i;
        int src[SMALL_LEN], dst[SMALL_LEN];
        Tcl& tcl = Tcl::instance();

        if ( hroute_ == 0) {
                tcl.result("Required Hier_data not sent");
                return TCL_ERROR;
        }
      
        ns_strtok(asrc, src);
        ns_strtok(adst, dst);

        for (i=0; i < level_; i++)
                if (src[i] <= 0) {
                        tcl.result("negative src node number");
                        return TCL_ERROR;
                }
        if (dst[0] <= 0) {
                tcl.result("negative dst domain number");
                return TCL_ERROR;
        }

        int d = src[0];
        int index = INDEX(src[0], src[1], Cmax_);
        int size = cluster_size_[index];

        if (hsize_[index] == 0) {
                tcl.result("Routes not computed");
                return TCL_ERROR;
        }
        if ((src[0] < D_) || (dst[0] < D_)) {
                if((src[1] < C_[d]) || (dst[1] < C_[dst[0]]))
                        if((src[2] <= size) ||
                           (dst[2]<=cluster_size_[INDEX(dst[0],dst[1],Cmax_)]))
                                ;
        } else { 
                tcl.result("node out of range");
                return TCL_ERROR;
        }
        int next_hop = 0;
        /* if node-domain lookup */
        if (((dst[1] <= 0) && (dst[2] <= 0)) ||
            (src[0] != dst[0])){
                next_hop = hroute_[index][N_D_INDEX(src[2], dst[0], size, C_[d], D_)];
        }
        /* if node-cluster lookup */
        else if ((dst[2] <= 0) || (src[1] != dst[1])) {
                next_hop = hroute_[index][N_C_INDEX(src[2], dst[1], size, C_[d], D_)];
        }
        /* if node-node lookup */
        else {
                next_hop = hroute_[index][N_N_INDEX(src[2], dst[2], size, C_[d], D_)];  
        }
        
        char target[SMALL_LEN];
        if (next_hop > 0) {
                get_address(target, next_hop, index, d, size, src);
                tcl.result(target);
                result= Address::instance().str2addr(target);
        } else {
                tcl.result("-1");
                result = -1;
        }
        return TCL_OK;
}

RouteLogic::RouteLogic()
{
        size_ = 0;
        adj_ = 0;
        route_ = 0;
        /* additions for hierarchical routing extension */
        C_ = 0;
        D_ = 0;
        Cmax_ = 0;
        level_ = 0;
        hsize_ = 0;
        hadj_ = 0;
        hroute_ = 0;
        hconnect_ = 0;
        cluster_size_ = 0;
}
        
RouteLogic::~RouteLogic()
{
        delete[] adj_;
        delete[] route_;

        for (int i = 0; i < (Cmax_ * D_); i++) {
                for (int j = 0; j < (Cmax_ + D_) * (cluster_size_[i]+1); j++) {
                        if (hconnect_[i][j] != NULL)
                                delete [] hconnect_[i][j];
                }
                delete [] hconnect_[i];
        }

        for (int n =0; n < (Cmax_ * D_); n++) {
                if (hadj_[n] != NULL)
                        delete [] hadj_[n];
                if (hroute_[n] != NULL)
                        delete [] hroute_[n];
        }

        delete [] C_;
        delete [] hsize_;
        delete [] cluster_size_;
        delete hadj_;
        delete hroute_;
        delete hconnect_;
}

void RouteLogic::alloc(int n)
{
        size_ = n;
        n *= n;
        adj_ = new adj_entry[n];
        for (int i = 0; i < n; ++i) {
                adj_[i].cost = INFINITY;
                adj_[i].entry = 0;
        }
}

/*
 * Check that we have enough storage in the adjacency array
 * to hold a node numbered "n"
 */
void RouteLogic::check(int n)
{
        if (n < size_)
                return;

        adj_entry* old = adj_;
        int osize = size_;
        int m = osize;
        if (m == 0)
                m = 16;
        while (m <= n)
                m <<= 1;

        alloc(m);
        for (int i = 0; i < osize; ++i) {
                for (int j = 0; j < osize; ++j)
                        adj_[INDEX(i, j, m)].cost =old[INDEX(i, j, osize)].cost;
        }
        size_ = m;
        delete[] old;
}

void RouteLogic::insert(int src, int dst, double cost)
{
        check(src);
        check(dst);
        adj_[INDEX(src, dst, size_)].cost = cost;
}
void RouteLogic::insert(int src, int dst, double cost, void* entry_)
{
        check(src);
        check(dst);
        adj_[INDEX(src, dst, size_)].cost = cost;
        adj_[INDEX(src, dst, size_)].entry = entry_;
}

void RouteLogic::reset(int src, int dst)
{
        assert(src < size_);
        assert(dst < size_);
        adj_[INDEX(src, dst, size_)].cost = INFINITY;
}

void RouteLogic::compute_routes()
{
        int n = size_;
        int* parent = new int[n];
        double* hopcnt = new double[n];
#define ADJ(i, j) adj_[INDEX(i, j, size_)].cost
#define ADJ_ENTRY(i, j) adj_[INDEX(i, j, size_)].entry
#define ROUTE(i, j) route_[INDEX(i, j, size_)].next_hop
#define ROUTE_ENTRY(i, j) route_[INDEX(i, j, size_)].entry
        delete[] route_;
        route_ = new route_entry[n * n];
        memset((char *)route_, 0, n * n * sizeof(route_[0]));

        /* do for all the sources */
        int k;
        for (k = 1; k < n; ++k) {
                int v;
                for (v = 0; v < n; v++)
                        parent[v] = v;
        
                /* set the route for all neighbours first */
                for (v = 1; v < n; ++v) {
                        if (parent[v] != k) {
                                hopcnt[v] = ADJ(k, v);
                                if (hopcnt[v] != INFINITY) {
                                        ROUTE(k, v) = v;
                                        ROUTE_ENTRY(k, v) = ADJ_ENTRY(k, v);
                                }
                        }
                }
                for (v = 1; v < n; ++v) {
                        /*
                         * w is the node that is the nearest to the subtree
                         * that has been routed
                         */
                        int o = 0;
                        /* XXX */
                        hopcnt[0] = INFINITY;
                        int w;
                        for (w = 1; w < n; w++)
                                if (parent[w] != k && hopcnt[w] < hopcnt[o])
                                        o = w;
                        parent[o] = k;
                        /*
                         * update distance counts for the nodes that are
                         * adjacent to o
                         */
                        if (o == 0)
                                continue;
                        for (w = 1; w < n; w++) {
                                if (parent[w] != k &&
                                    hopcnt[o] + ADJ(o, w) < hopcnt[w]) {
                                        ROUTE(k, w) = ROUTE(k, o);
                                        ROUTE_ENTRY(k, w) = 
                                            ROUTE_ENTRY(k, o);
                                        hopcnt[w] = hopcnt[o] + ADJ(o, w);
                                }
                        }
                }
        }
        /*
         * The route to yourself is yourself.
         */
        for (k = 1; k < n; ++k) {
                ROUTE(k, k) = k;
                ROUTE_ENTRY(k, k) = 0; // This should not matter
        }

        delete[] hopcnt;
        delete[] parent;
}

/* hierarchical routing support */

/*
 * This function creates adjacency matrix for each cluster at the lowest level
 * of the hierarchy for every node in the cluster, for every other cluster in 
 * the domain, and every other domain. can be extended from 3-level hierarchy 
 * to n-level along similar lines
 */
void RouteLogic::hier_alloc(int i)
{
        hsize_[i] = cluster_size_[i]+ Cmax_+ D_ ;
        hsize_[i] *= hsize_[i];
        hadj_[i] = new int[hsize_[i]];
        hroute_[i] = new int[hsize_[i]];
        hconnect_[i] = new char*[(Cmax_ + D_) * (cluster_size_[i]+1)];
        for (int n = 0; n < hsize_[i]; n++){
                hadj_[i][n] = INFINITY;
                hroute_[i][n] = INFINITY;
        }
}

void RouteLogic::hier_check(int i)
{
        if(hsize_[i] > 0)
                return;
        else
                hier_alloc(i);
}

void RouteLogic::hier_init(void) 
{
        int i;

        for (i = 1; i < D_; i++) {
                Cmax_ = C_[i] > Cmax_ ? C_[i]: Cmax_;
        }
        int arr_size = Cmax_ * D_ ;
        cluster_size_ = new int[arr_size]; 
        hsize_ = new int[arr_size];
        for (i = 0; i < arr_size; i++)
                hsize_[i] = 0;
        hadj_ = new int*[arr_size];
        hroute_ = new int*[arr_size];
        hconnect_ = new char**[arr_size];
}


int RouteLogic::domain_size(int domain) { 
        return (C_[domain+1]-1); 
}
int RouteLogic::cluster_size(int d, int c) {
        d += 1;
        c += 1;
        return (cluster_size_[INDEX(d, c, Cmax_)]);
}

int RouteLogic::elements_in_level(int *addr, int level) {
        if (level == 1)
                return (domains());
        else if (level == 2)
                return (domain_size(addr[0]));
        else if (level == 3) {
                return (cluster_size(addr[0], addr[1]));
        }
        return (-1);
}

void RouteLogic::str2address(const char*const* argv, int *src_addr, int *dst_addr)
{
        char src[SMALL_LEN];
        char dst[SMALL_LEN];

        strcpy(src, argv[2]);
        strcpy(dst, argv[3]);

        ns_strtok(src, src_addr);
        ns_strtok(dst, dst_addr);
}

void RouteLogic::ns_strtok(char *addr, int *addrstr)
{
        int     i;
        char    tmpstr[SMALL_LEN];
        char    *next, *index;
        
        i = 0;
        strcpy(tmpstr, addr);
        next = tmpstr;
        while(*next){
                index = strstr(next, ".");
                if (index != NULL){
                        next[index - next] = '\0';
                        addrstr[i] = atoi(next) + 1;
                        next = index + 1;
                        i++;
                }
                else {
                        if (*next != '\0') //damn that ending point
                                addrstr[i] = atoi(next) + 1;
                        break;
                }
        }
}


void RouteLogic::get_address(char *address, int next_hop, int index, int d, 
                             int size, int *src)
{
        if (next_hop <= size) {
                sprintf(address,"%d.%d.%d", src[0]-1, src[1]-1, next_hop-1);
        }
        else if ((next_hop > size) && (next_hop < (size + C_[d]))) {
                int temp = next_hop - size;
                int I = src[2] * (C_[d] + D_) + temp;
                strcpy(address, hconnect_[index][I]);
        }
        else {
                int temp = next_hop - size - (C_[d] - 1);
                int I = src[2] * (C_[d] + D_) + (C_[d] - 1 + temp);
                strcpy(address,hconnect_[index][I]);
        }
}

void RouteLogic::hier_reset(int *src, int *dst)
{
        int i, d, n;
        d = src[0];
        if (src[0] == dst[0])
                if (src[1] == dst[1]) {
                        i = INDEX(src[0], src[1], Cmax_);
                        n = cluster_size_[i];
                        hadj_[i][N_N_INDEX(src[2], dst[2], n, C_[d], D_)] = INFINITY;
                } else {
                        for (int y=1; y < C_[d]; y++) { 
                                i = INDEX(src[0], y, Cmax_);
                                n = cluster_size_[i];
                                hadj_[i][C_C_INDEX(src[1], dst[1], n, C_[d], D_)] = INFINITY;
                                if (y == src[1])
                                        hadj_[i][N_C_INDEX(src[2], dst[1], n, C_[d], D_)] = INFINITY; 
                        }
                }
        else {
                for (int x=1; x < D_; x++)
                        for (int y=1; y < C_[x]; y++) {
                                i = INDEX(x, y, Cmax_);
                                n = cluster_size_[i];
                                hadj_[i][D_D_INDEX(src[0], dst[0], n, C_[x], D_)] = INFINITY;
                                if ( x == src[0] ){
                                        hadj_[i][C_D_INDEX(src[1], dst[0], n, C_[x], D_)] = INFINITY;
                                        if (y == src[1])
                                                hadj_[i][N_D_INDEX(src[2], dst[0], n, C_[x], D_)] = INFINITY;
                                }
                        }
        }
}

void RouteLogic::hier_insert(int *src_addr, int *dst_addr, int cost)
{
        int X1 = src_addr[0];
        int Y1 = src_addr[1];
        int Z1 = src_addr[2];
        int X2 = dst_addr[0];
        int Y2 = dst_addr[1];
        int Z2 = dst_addr[2];
        int n, i;

        if ( X1 == X2)
                if (Y1 == Y2){ 
                        /*
                         * For the same domain & cluster 
                         */
                        i = INDEX(X1, Y1, Cmax_);
                        n = cluster_size_[i];
                        hier_check(i);
                        hadj_[i][N_N_INDEX(Z1, Z2, n, C_[X1], D_)] = cost;
                } else { 
                        /* 
                         * For the same domain but diff clusters 
                         */
                        for (int y=1; y < C_[X1]; y++) { /* insert cluster connectivity */
                                i = INDEX(X1, y, Cmax_);
                                n = cluster_size_[i];
                                hier_check(i);
                                hadj_[i][C_C_INDEX(Y1, Y2, n, C_[X1], D_)] = cost;

                                if (y == Y1) {  /* insert node conn. */
                                        hadj_[i][N_C_INDEX(Z1, Y2, n, C_[X1], D_)] = cost;
                                        int I = Z1 * (C_[X1]+ D_) + Y2;
                                        hconnect_[i][I] = new char[SMALL_LEN];
                                        sprintf(hconnect_[i][I],"%d.%d.%d",X2-1,Y2-1,Z2-1);
                                }
                        }
                }
        else { 
                /* 
                 * For different domains 
                 */
                for (int x=1; x < D_; x++) { /* inset domain connectivity */
                        for (int y=1; y < C_[x]; y++) {
                                i = INDEX(x, y, Cmax_);
                                n = cluster_size_[i];
                                hier_check(i);
                                hadj_[i][D_D_INDEX(X1, X2, n, C_[x], D_)] = cost;
                        }
                }
                for (int y=1; y < C_[X1]; y++) { /* insert cluster connectivity */
                        i = INDEX(X1, y, Cmax_);
                        n = cluster_size_[i];
                        hier_check(i);
                        hadj_[i][C_D_INDEX(Y1, X2, n, C_[X1], D_)] = cost;
                }
                /* insert node connectivity */
                i = INDEX(X1, Y1, Cmax_);
                n = cluster_size_[i]; 
                hadj_[i][N_D_INDEX(Z1, X2, n, C_[X1], D_)] = cost;
                int I = Z1 * (C_[X1] + D_) + (C_[X1] - 1 + X2);
                hconnect_[i][I] = new char[SMALL_LEN];
                sprintf(hconnect_[i][I],"%d.%d.%d",X2-1,Y2-1,Z2-1);
        }
}

void RouteLogic::hier_compute_routes(int i, int j)
{
        int size = (cluster_size_[i] + C_[j] + D_);
        int n = size ;
        double* hopcnt = new double[n];
#define HADJ(i, j) adj_[INDEX(i, j, size)].cost
#define HROUTE(i, j) route_[INDEX(i, j, size)].next_hop
        delete[] route_;
        route_ = new route_entry[n * n];
        int* parent = new int[n];
        memset((char *)route_, 0, n * n * sizeof(route_[0]));

        /* do for all the sources */
        int k;
        for (k = 1; k < n; ++k) {
                int v;
                for (v = 0; v < n; v++)
                        parent[v] = v;

                /* set the route for all neighbours first */
                for (v = 1; v < n; ++v) {
                        if (parent[v] != k) {
                                hopcnt[v] = HADJ(k, v);
                                if (hopcnt[v] != INFINITY)
                                        HROUTE(k, v) = v;
                        }
                }
                for (v = 1; v < n; ++v) {
                        /*
                         * w is the node that is the nearest to the subtree
                         * that has been routed
                         */
                        int o = 0;
                        /* XXX */
                        hopcnt[0] = INFINITY;
                        int w;
                        for (w = 1; w < n; w++)
                                if (parent[w] != k && hopcnt[w] < hopcnt[o])
                                        o = w;
                        parent[o] = k;
                        /*
                         * update distance counts for the nodes that are
                         * adjacent to o
                         */
                        if (o == 0)
                                continue;
                        for (w = 1; w < n; w++) {
                                if (parent[w] != k &&
                                    hopcnt[o] + HADJ(o, w) < hopcnt[w]) {
                                        HROUTE(k, w) = HROUTE(k, o);
                                        hopcnt[w] = hopcnt[o] + HADJ(o, w);
                                }
                        }
                }
        }
        /*
         * The route to yourself is yourself.
         */
        for (k = 1; k < n; ++k)
                HROUTE(k, k) = k;

        delete[] hopcnt;
        delete[] parent;
}

/* function to check the adjacency matrices created */
void RouteLogic::hier_print_hadj() {
        int i, j, k;

        for (j=1; j < D_; j++) 
                for (k=1; k < C_[j]; k++) {
                        i = INDEX(j, k, Cmax_);
                        int s = (cluster_size_[i] + C_[j] + D_);
                        printf("ADJ MATRIX[%d] for cluster %d.%d :\n",i,j,k);
                        int temp = 1;
                        printf(" ");
                        while(temp < s){
                                printf(" %d",temp);
                                temp++;
                        }
                        printf("\n");
                        for(int n=1; n < s;n++){
                                printf("%d ",n);
                                for(int m=1;m < s;m++){
                                        if(hadj_[i][INDEX(n,m,s)] == INFINITY)
                                                printf("~ ");
                                        else
                                                printf("%d ",hadj_[i][INDEX(n,m,s)]);
                                }
                                printf("\n");
                        }
                        printf("\n\n");
                }
}

void RouteLogic::hier_compute()
{
        int i, j, k, m, n;
        for (j=1; j < D_; j++) 
                for (k=1; k < C_[j]; k++) {
                        i = INDEX(j, k, Cmax_);
                        int s = (cluster_size_[i] + C_[j] + D_);
                        adj_ = new adj_entry[(s * s)];
                        memset((char *)adj_, 0, s * s * sizeof(adj_[0]));
                        for (n=0; n < s; n++)
                                for(m=0; m < s; m++)
                                        adj_[INDEX(n, m, s)].cost = hadj_[i][INDEX(n, m, s)];
                        hier_compute_routes(i, j);
        
                        for (n=0; n < s; n++)
                                for(m=0; m < s; m++)
                                        hroute_[i][INDEX(n, m, s)] = route_[INDEX(n, m, s)].next_hop;
                        delete [] adj_;
                }
}

/*
 * Prints routing table - debugging function
 */
void RouteLogic::hier_print_route()
{
        for (int j=1; j < D_; j++) 
                for (int k=1; k < C_[j]; k++) {
                        int i = INDEX(j, k, Cmax_);
                        int s = (cluster_size_[i]+C_[j]+D_);
                        printf("ROUTE_TABLE[%d] for cluster %d.%d :\n",i,j,k);
                        int temp = 1;
                        printf(" ");
                        while(temp < s){
                                printf(" %d",temp);
                                temp++;
                        }
                        printf("\n");
                        for(int n=1; n < s; n++){
                                printf("%d ",n);
                                for(int m=1; m < s; m++)
                                        printf("%d ",hroute_[i][INDEX(n, m, s)]);
                                printf("\n");
                        }
                        printf("\n\n");
                }
}

static class RouteLogicAlgoClass : public TclClass {
public:
        RouteLogicAlgoClass() : TclClass("RouteLogic/Algorithmic") {}
        TclObject* create(int, const char*const*) {
                return (new RouteLogicAlgo);
        }
} class_routelogic_algo;

---