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.39 2005/09/12 04:34:16 tomh 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);
            return (TCL_OK);
        } 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;

---