tora_dest.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1997 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 Computer Systems
 *      Engineering 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.
 */
/* Ported from CMU/Monarch's code */
/* 
   $Id: tora_dest.cc,v 1.2 1999/08/12 21:12:29 yaxu Exp $
   */

#include <agent.h>
#include <random.h>
#include <trace.h>

#include <ll.h>
#include <priqueue.h>
#include <tora/tora_packet.h>
#include <tora/tora.h>

#define CURRENT_TIME    Scheduler::instance().clock()

/* ======================================================================
   TORADest Class Functions
   ====================================================================== */
TORADest::TORADest(nsaddr_t id, Agent *a) :  height(id)
{
    index = id;

    rt_req = 0;
    time_upd = 0.0;

    time_rt_req = 0.0;
    time_tx_qry = 0.0;

    LIST_INIT(&nblist);
    num_active = num_down = num_up = 0;

        agent = (toraAgent*) a;
}


void
TORADest::dump()
{
    TORANeighbor *tn = nb_find_next_hop();

    fprintf(stdout, "\tDEST: %d, RT Req: %x, Time UPD: %f\n",
        index, rt_req, time_upd);
    fprintf(stdout, "\t\ttau: %f, oid: %d, r: %d, delta: %d, id: %d\n",
        height.tau, height.oid, height.r, height.delta, height.id);
    fprintf(stdout, "\t\tActive: %d, Down: %d, Up: %d, Next Hop: %d\n\n",
        num_active, num_down, num_up, tn ? tn->index : -1);

    for(tn = nblist.lh_first; tn; tn = tn->link.le_next)
        tn->dump();
}


/* ====================================================================== */

TORANeighbor*
TORADest::nb_add(nsaddr_t id)
{
    TORANeighbor *tn = new TORANeighbor(id, agent);
    assert(tn);

    LIST_INSERT_HEAD(&nblist, tn, link);

    num_active += 1;
    if(tn->index == index) {
        tn->height.Zero();
        tn->lnk_stat = LINK_DN;
        num_down += 1;
    }

    return tn;
}


int
TORADest::nb_del(nsaddr_t id)
{
    TORANeighbor *tn = nblist.lh_first;

    for( ; tn; tn = tn->link.le_next) {
        if(tn->index == id) {

            num_active -= 1;

            if(tn->lnk_stat == LINK_DN)
                num_down -=1;
            if(tn->lnk_stat == LINK_UP)
                num_up -= 1;


            LIST_REMOVE(tn, link);
            delete tn;

                        /*
                         *  Here's were we decide whether or not to
                         *  do route maintenance.
                         */
                        if(num_down == 0) {
                if(num_up > 0) {
                    update_height(CURRENT_TIME,
                              index,
                              0,
                              0,
                              index);
                } else {
                    update_height(-1,
                              -1,
                              -1,
                              -1,
                              index);
                    // set height to NULL
                }

                agent->logNbDeletedLastDN(this);

                return 1;
                // send an UPDATE packet
            }
            return 0;
        }
    }
        return 0;
}


TORANeighbor*
TORADest::nb_find(nsaddr_t id)
{
    TORANeighbor *tn = nblist.lh_first;
    for( ; tn; tn = tn->link.le_next) {
        if(tn->index == id)
            return tn;
    }
    return 0;
}


TORANeighbor*
TORADest::nb_find_next_hop()
{
    TORANeighbor *tn = nblist.lh_first;
    TORANeighbor *tn_min = 0;

    for( ; tn; tn = tn->link.le_next) {
        if(tn->height.isNull())
                        continue;

                if(tn->lnk_stat != LINK_DN)
                        continue;

                if(tn_min == 0 || tn_min->height.compare(&tn->height) < 0) {
                        tn_min = tn;
                }
    }
    assert(tn_min == 0 || tn_min->lnk_stat == LINK_DN);
    return tn_min;
}


/*
 *  Find a neighbor of minimum height, subject to the constraint
 *  that height.r == R.
 */
TORANeighbor*
TORADest::nb_find_min_height(int R)
{
    TORANeighbor *tn = nblist.lh_first;
    TORANeighbor *tn_min = 0;

    for( ; tn; tn = tn->link.le_next) {
        if(tn->height.r == R) {
            if(tn_min == 0 ||
                           tn_min->height.compare(&tn->height) < 0)
                tn_min = tn;
        }
    }
    return tn_min;
}


/*
 *  Find a neighbor of minimum height, subject to the constraint
 *  that height.(tau,oid,r) == (tau,oid,r) and height != NULL
 */
TORANeighbor*
TORADest::nb_find_min_nonnull_height(Height *h)
{
    TORANeighbor *tn = nblist.lh_first;
    TORANeighbor *tn_min = 0;

    assert(h);

    for( ; tn; tn = tn->link.le_next) {
        if(tn->height.isNull() == 0 &&
           tn->height.tau == h->tau &&
           tn->height.oid == h->oid &&
           tn->height.r == h->r) {
            if(tn_min == 0 ||
                           tn_min->height.compare(&tn->height) < 0)
                tn_min = tn;
        }
    }
    return tn_min;
}


/*
 *  Find a neighbor of maximum height, subject to the constraint
 *  that height != NULL.
 */
TORANeighbor*
TORADest::nb_find_max_height()
{
    TORANeighbor *tn = nblist.lh_first;
    TORANeighbor *tn_max = 0;

    for( ; tn; tn = tn->link.le_next) {
        if(tn->height.isNull() == 0) {
            if(tn_max == 0 ||
                           tn_max->height.compare(&tn->height) > 0)
                tn_max = tn;
        }
    }
    return tn_max;
}


// Verify that all neighbors of non-null height have the same reference
// level.
int
TORADest::nb_check_same_ref()
{
    TORANeighbor *tn = nblist.lh_first;
    TORANeighbor *tref = 0;

    for( ; tn; tn = tn->link.le_next) {
        if(tn->height.isNull() == 0) {
            if(tref == 0)
                tref = tn;
            else if(tref->height.tau != tn->height.tau ||
                tref->height.oid != tn->height.oid ||
                tref->height.r != tn->height.r)
                return 0;
        }
    }
    return 1;
}

    
void
TORADest::update_height_nb(TORANeighbor *tn, struct hdr_tora_upd *uh)
{
    Height h(uh->tu_id);

    h.tau = uh->tu_tau;
    h.oid = uh->tu_oid;
    h.r = uh->tu_r;
    h.delta = uh->tu_delta;

    tn->height.update(&h);

    /*
     *  Update num_down/num_up
     */
    if(tn->lnk_stat == LINK_DN)
        num_down -= 1;
    if(tn->lnk_stat == LINK_UP)
        num_up -= 1;

    tn->update_link_status(&height);

    /*
     *  Update num_down/num_up
     */
    if(tn->lnk_stat == LINK_DN)
        num_down += 1;
    if(tn->lnk_stat == LINK_UP)
        num_up += 1;
}


/*
 *  Updates the height of a destination and then recomputes
 *  all of the link status information for the neighbors.
 */
void
TORADest::update_height(double TAU, nsaddr_t OID, int R, int DELTA, nsaddr_t ID)
{
    TORANeighbor *tn = nblist.lh_first;

    height.tau = TAU;
    height.oid = OID;
    height.r = R;
    height.delta = DELTA;
    height.id = ID;

#ifdef LOGGING
        agent->log_dst_state_change(this);
#endif
    num_active = num_down = num_up = 0;

    for( ; tn; tn = tn->link.le_next) {

        tn->update_link_status(&height);

        num_active += 1;

        if(tn->lnk_stat == LINK_DN)
            num_down += 1;
        if(tn->lnk_stat == LINK_UP)
            num_up += 1;
    }
}

---