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.
 *  
 * License is granted to copy, to use, and to make and to use derivative
 * works for research and evaluation purposes, provided that Xerox is
 * acknowledged in all documentation pertaining to any such copy or derivative
 * work. Xerox grants no other licenses expressed or implied. The Xerox trade
 * name should not be used in any advertising without its written permission.
 *  
 * XEROX CORPORATION MAKES NO REPRESENTATIONS CONCERNING EITHER THE
 * MERCHANTABILITY OF THIS SOFTWARE OR THE SUITABILITY OF THIS SOFTWARE
 * FOR ANY PARTICULAR PURPOSE.  The software is provided "as is" without
 * express or implied warranty of any kind.
 *  
 * These notices must be retained in any copies of any part of this software.
 *
 * This file contributed by Suchitra Raman <sraman@parc.xerox.com>, June 1997.
 */

#include <stdlib.h>
#include <math.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;
        }
        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;
        }
        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

---