srm-topo.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) Xerox Corporation 1997. All rights reserved.
 *  
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2 of the License, or (at your
 * option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Linking this file statically or dynamically with other modules is making
 * a combined work based on this file.  Thus, the terms and conditions of
 * the GNU General Public License cover the whole combination.
 *
 * In addition, as a special exception, the copyright holders of this file
 * give you permission to combine this file with free software programs or
 * libraries that are released under the GNU LGPL and with code included in
 * the standard release of ns-2 under the Apache 2.0 license or under
 * otherwise-compatible licenses with advertising requirements (or modified
 * versions of such code, with unchanged license).  You may copy and
 * distribute such a system following the terms of the GNU GPL for this
 * file and the licenses of the other code concerned, provided that you
 * include the source code of that other code when and as the GNU GPL
 * requires distribution of source code.
 *
 * Note that people who make modified versions of this file are not
 * obligated to grant this special exception for their modified versions;
 * it is their choice whether to do so.  The GNU General Public License
 * gives permission to release a modified version without this exception;
 * this exception also makes it possible to release a modified version
 * which carries forward this exception.
 *
 * This file contributed by Suchitra Raman <sraman@parc.xerox.com>, June 1997.
 */

#include <stdlib.h>
#include <math.h>
#include <assert.h>

#include "config.h"
#include "tclcl.h"
#include "srm-topo.h"
#include "scheduler.h"

#define SRM_DEBUG


Topology::Topology(int nn, int src) : idx_(nn), src_(src)
{
    node_ = new SrmNode[nn];
    for (int i = 0; i < nn; i ++) 
        node_[i].id(i);

    bind("src_", &src_);
    bind("delay_", &delay_);
    bind("D_", &D_);
    bind("frac_", &frac_);
    /* D_ (ms) is the delay of node 1 from node 0 */

    bind("det_", &det_);
    bind("rtt_est_", &rtt_est_);
    bind("rand_", &rand_);
}

Topology::~Topology() {
    delete [] node_;
}

int Topology::command(int argc, const char*const* argv) 
{
    //Tcl& tcl = Tcl::instance();
    if (argc == 3) {
        if (strcmp(argv[1], "flood") == 0) {
            flood(0, atoi(argv[2]));
            return (TCL_OK);
        }
    }
    return (TclObject::command(argc, argv));
}

SrmNode* Topology::node(int nn) 
{ 
    if (nn < 0 || nn >= idx_) return 0;
    return &(node_[nn]); 
}


static class LineClass : public TclClass {
public:
    LineClass() : TclClass("Topology/Line") {} 
    TclObject* create(int, const char*const* argv) {
        int nn = atoi(argv[4]);
        return (new Line(nn, 0));
    }
} class_line_topo;


double Line::backoff(int dst) 
{
    double rtt;

    if (topology->rtt_estimated() == 1)
        rtt = delay(dst, 0);
    else rtt = D_ * frac_;
    double b;
    double sqroot = sqrt(rtt);
    double r = Random::uniform(0.0, 1.0);

    switch(c2func_) {
    case LOG :
        b = rtt * (det_ +  rand_ * r * log(rtt)/log(D_));
        break;
    case SQRT :
        b = rtt * (det_ +  rand_ * r * sqroot/sqrt(D_));
        break;
    case LINEAR :
        b = rtt * (det_ +  rand_ * r * rtt/D_);
        break;
    case CONSTANT :
        b = rtt * (det_ +  rand_ * r * 1.);
        break;
    default:
        // quiet compiler
        b = 0.0;
        assert (false);
        break;
    }
    return b;
}

#ifdef SRM_BIMODAL
double Line::backoff(int dst) 
{
    double rtt;
    if (topology->rtt_estimated() == 1) 
        rtt = delay(dst, 0);
    else rtt = D_ * frac_;

    double rbackoff;
    double p = Random::uniform(0.0, 1.0);
    int bin = 0;
    int copies = c_;
    int size = topology->idx();
    
    if (p <= copies * 1./size) {
        rbackoff = Random::uniform(0.0, alpha_);
        bin = 0;
    } else {
        rbackoff = Random::uniform(beta_, 1.0 + beta_);
        bin = 1;
    }

    return (rtt * (det_ + rand_ * rbackoff));
}
#endif

Interface_List* Line::oif(int node, int iif=SRM_NOIF)
{
    //int oif;
    Interface_List *ilist = new Interface_List;

    /* If there are no more nodes downstream, return -1 */
    if ((iif <= node && node >= idx_ - 1) ||  (iif > node && node == 0))
        return 0;

    if (iif == SRM_NOIF) 
    {
        ilist->append(node + 1);
        ilist->append(node - 1);
    } else if (iif <= node) 
        ilist->append(node + 1);
    else 
        ilist->append(node - 1);
    return (ilist);
}

double Line::delay(int src, int dst) 
{
    if (src == 0 || dst == 0) 
        return D_ + delay_ * abs(dst - src - 1);
    else
        return delay_ * abs(dst - src);
}


double Star::delay(int src, int dst) 
{
    if (src == 0 || dst == 0) 
        return D_;
    else
        return delay_;
}

/* 
 * Very simple now, can only send to direct ancestor/descendant 
 */
double BTree::delay(int src, int dst)
{
    double src_ht = 0;
    double dst_ht = 0;
    
    if (src > 0) 
        src_ht = 1 + floor(log(src)/log(2));
    if (dst > 0)
        dst_ht = 1 + floor(log(dst)/log(2));
    
    if (src == 0 || dst == 0) 
        return D_ + delay_ * abs(int (dst_ht - src_ht - 1));
    else 
        return delay_ * abs(int (dst_ht - src_ht));
}   

/* 
 * There is always an outbound interface. We should not 
 * start a flood() from a leaf node. 
 * Change it for other topologies. 
 */
void Line::flood(int start, int seqno)
{
    SRM_Event *se = new SRM_Event(seqno, SRM_DATA, start);
    node_[start].send(se);
}

/*
 * BTree -
 */

static class BTreeClass : public TclClass {
public:
    BTreeClass() : TclClass("Topology/BTree") {} 
    TclObject* create(int, const char*const* argv) {
        int nn = atoi(argv[4]);
        return (new BTree(nn, 0));
    }
} class_btree_topo;


/* 
 * The ranges of the different distributions 
 * must be normalized to 1. 
 */
double BTree::backoff(int id) 
{
    double rtt;
    if (topology->rtt_estimated())
        rtt = delay(id, 0);
    else rtt = D_ * frac_; 

    double r = Random::uniform(0.0, 1.0);
    double b;
    double sqroot = sqrt(rtt);
    double D = topology->D();

    switch(c2func_) {
    case LOG :
        b = rtt * (det_ +  rand_ * r * log(rtt)/log(D));
        break;
    case SQRT :
        b = rtt * (det_ +  rand_ * r * sqroot/sqrt(D));
        break;
    case LINEAR :
        b = rtt * (det_ +  rand_ * r * rtt/D);
        break;
    case CONSTANT :
        b = rtt * (det_ +  rand_ * r * 1.);
        break;
    default:
        // quiet compiler
        b = 0.0;
        assert (false);
        break;
    }
    return b;
}

Interface_List* BTree::oif(int node, int iif=SRM_NOIF)
{
    //int oif;
    Interface_List *ilist = new Interface_List;
    /* 
     * If the packet comes from the source, 
     * there is only 1 outgoing link.
     * We make the assumption that source = 0 always (YUCK!)
     */
    if (iif == SRM_NOIF) {
        if (node == 0) {
            ilist->append(1);
        }
        else {
            ilist->append(2 * node + 1);
            ilist->append(2 * node);
            int k = (int)floor(.5 * node);
            ilist->append(k);
        }
    } else if (iif <= node) {
        ilist->append(2 * node + 1);
        ilist->append(2 * node);
    }

    // Packet came along 2n + 1 or 2n + 2
    else if (iif == 2 * node + 1) {
        if (node == 0)
            return ilist;
        
        ilist->append(2 * node);
        ilist->append((int) floor(.5 * node));
    } else if (iif == 2 * node) {
        ilist->append(2 * node + 1);
        ilist->append((int)floor(.5 * node));
    }
    return (ilist);
}

/*
 * Star -
 */

static class StarClass : public TclClass {
public:
    StarClass() : TclClass("Topology/Star") {} 
    TclObject* create(int, const char*const* argv) {
        int nn = atoi(argv[4]);
        return (new Star(nn, 0));
    }
} class_star_topo;


/* 
 * SrmNode -
 */

void SrmNode::dump_packet(SRM_Event *e) 
{
#ifdef SRM_DEBUG
    tprintf(("(type %d) (in %d) -- @ %d --> \n", e->type(), e->iif(), id_));
#endif
}

/* This forwards an event by making multiple copies of the
 * event 'e'. Does NOT free event 'e'. 
 */
void SrmNode::send(SRM_Event *e) 
{
    /* 
     * Copy the packet and send it over to 
     * all the outbound interfaces 
     */
    int nn;
    Scheduler& s = Scheduler::instance();
    SRM_Event *copy;
    Interface *p;
    Interface_List *ilist = topology->oif(id_, e->iif());
    if (e->iif() < 0)
        e->iif(id_);

    if (ilist) {
        for (p=ilist->head_; p; p=p->next_) {
            nn = p->in_;
            int t = e->type();
            //int i = id_; 
            int snum = e->seqno();
            SrmNode *next = topology->node(nn);
            if (next) {
                copy = new SRM_Event(snum, t, id_);
                s.schedule(next, copy,
                       topology->delay(id_, nn));    
            }
        }
    }
    delete ilist;
    delete e;
}


/* 
 * Demux the two types of events depending on 
 * the type field.
 */ 
void SrmNode::handle(Event* event)
{
    SRM_Event *srm_event = (SRM_Event *) event;
    int type  = srm_event->type();
    int seqno = srm_event->seqno();
    //int iif   = srm_event->iif();
    //Scheduler& s = Scheduler::instance();

    switch (type) {
    case SRM_DATA :
        if (seqno != expected_) 
            sched_nack(seqno);
        expected_ = seqno;
        break;

    case SRM_PENDING_RREQ :
        tprintf(("Fired RREQ (node %d)\n", id_));
        remove(seqno, SRM_NO_SUPPRESS);
        srm_event->type(SRM_RREQ);
        break;

    case SRM_RREQ :

        remove(seqno, SRM_SUPPRESS);
        break;

    default :
        tprintf(("panic: node(%d) Unexpected type %d\n", id_, type));
        return;
    }
#ifdef SRM_STAR
    if (type == SRM_RREQ || type == SRM_DATA) {
        delete srm_event;
        return;
    }
#endif
    send(srm_event);    
    return;
}

/* 
 * XXX Should take two sequence numbers. The iif field is a dummy. We should be
 * careful not to use it for NACKs 
 */
void SrmNode::sched_nack(int seqno) 
{
    double backoff, time;
    Scheduler& s = Scheduler::instance();
    SRM_Event *event = new SRM_Event(seqno, 
                     SRM_PENDING_RREQ, SRM_NOIF);
    append(event);

    backoff = topology->backoff(id_);
    time = backoff + s.clock();
//  tprintf(("node(%d) schd rrq after %f s\n", id_, backoff));
    s.schedule(this, event, backoff);
}

void SrmNode::append(SRM_Event *e) 
{
    SRM_Request *req = new SRM_Request(e);
    req->next_ = pending_;
    pending_ = req;
}

/* If an event identical to e exists, cancel it */
void SrmNode::remove(int seqno, int flag)
{
    SRM_Request *curr, *prev;
    SRM_Event *ev;

    if (!pending_)
        return;
    for (curr=pending_, prev=0; curr; curr=curr->next_) 
    {
        ev = curr->event_;
        if (ev->seqno() == seqno) {
            if (!prev) 
                pending_ = curr->next_;
            else {
                prev->next_ = curr->next_;
                prev = curr;
            }
            if (flag == SRM_SUPPRESS) {
                curr->cancel_timer();
            }
            delete curr;
        }
    }
}


SRM_Event::SRM_Event(SRM_Event *e) 
{
    seqno_ = e->seqno();
    type_  = e->type();
    iif_   = e->iif();
}

SRM_Request::~SRM_Request() {}

void SRM_Request::cancel_timer() 
{
    if (event_) {
        Scheduler& s = Scheduler::instance();
        s.cancel(event_);
        // xxx: should event be free'd?  possible memory leak.
    }
}

void Interface_List::append(int in) 
{
    Interface *i = new Interface(in);
    i->next_ = head_;
    head_ = i;
}

Interface_List::~Interface_List() 
{
    Interface *p, *next;
    for (p=head_; p; p=next)
    {
        next = p->next_;
        delete p;
    }
}

void BTree::flood(int start, int seqno)
{
    SRM_Event *se = new SRM_Event(seqno, SRM_DATA, SRM_NOIF);
    node_[start].send(se);
}

void Star::flood(int start, int seqno)
{
    SRM_Event *se = new SRM_Event(seqno, SRM_DATA, start);
    node_[start].send(se);
}

Interface_List* Star::oif(int node, int iif=SRM_NOIF)
{
    int i;
    Interface_List *ilist = new Interface_List;

    /* Make a list with every node except myself */
    for (i = 0; i < topology->idx(); i ++)
    {
        if (i != node && i != iif) {
            ilist->append(i);
        }
    }

    return (ilist);
}

/* 
 * Distance of source to cluster = D_
 */
double Star::backoff(int id)
{
    double rtt = topology->delay(id, 0);
    double rbackoff;
    double p = Random::uniform(0.0, 1.0);
    static int bin = 0;
    int copies = c_;
    int size = topology->idx();
    
    if (p <= copies * 1./size) {
        rbackoff = Random::uniform(0.0, alpha_);
        bin ++;
    } else {
        rbackoff = Random::uniform(beta_, 1.0 + beta_);
    }
    return (rtt * (det_ + rand_ * rbackoff));
}


#ifdef SRM_BIMODAL
double BTree::backoff(int dst) 
{
    double height = floor(log(dst)/log(2));

    double D = topology->D();
    double rtt = delay_ * height + D;
    double p = Random::uniform(0.0, 1.0);
    double rbackoff;

    static int bin = 0;
    int copies = c_;
    int size = topology->idx();
    
    if (p <= copies * 1./size) {
        rbackoff = Random::uniform(0.0, alpha_);
        bin ++;
    } else {
        rbackoff = Random::uniform(1.0 + alpha_, 2.0);
    }
    return (rtt * (det_ + rand_ * rbackoff));
}
#endif

---