wfq.cc~

rsvp and wfq patch for Netowrk Simulator 2

/*
 * Copyright (c) 1998 The University of Bonn
 * All rights reserved.
 * 
 * Permission to use and copy this software in source and binary forms
 * is hereby granted, provided that the above copyright notice, this
 * paragraph and the following disclaimer are retained in any copies
 * of any part of this software and that the University of Bonn is
 * acknowledged in all documentation pertaining to any such copy
 * or derivative work. The name of the University of Bonn may not
 * be used to endorse or promote products derived from this software
 * without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
 * EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE WARRANTIES OF 
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL 
 * THE UNIVERSITY OF BONN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 
 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 
 * SOFTWARE.
 */

#include "wfq.h"


static class WFQClassCl : public TclClass {
public:
  WFQClassCl() : TclClass("WFQClass") {}
  TclObject* create(int, const char*const*) {
    return (new WFQClass);
  }
} class_WFQClass;


WFQClass::WFQClass() : next_(0), bw_(0), next_time_(-1), last_time_(-1) {
  bind("off_cmn_", &off_cmn_);
  bind("limit_", &qlim_);
  bind_bw("bw_", &bw_);
  q_ = new PacketQueue;
  size_ = 0;
}


/* Inserts a packet into the queue associated with the WFQClass and
   calculates the new size (in bytes). */
void WFQClass::enque(Packet *p) {
  hdr_cmn *hdr = (hdr_cmn*)p->access(off_cmn_);
  q_->enque(p);
  size_ += hdr->size();
}


/* Removes a packet from the queue associated with the WFQClass
   and calculates the new size (in bytes). */
Packet *WFQClass::deque() {
  Packet *p = q_->deque();
  hdr_cmn *hdr = (hdr_cmn*)p->access(off_cmn_);
  size_ -= hdr->size();
  return p;
}


/*
 * The function 'calculate_next_time()' is the 'heart' both of the
 * WFQ and WF2Q algorithms. It calculates the time at which the next
 * packet for the queue would complete service in the corresponding
 * GPS system.
 */
void WFQClass::calculate_next_time() {
  Packet *np = q_->head();
  hdr_cmn *hdr = (hdr_cmn*)np->access(off_cmn_);
  last_time_ = next_time_;
  /* For packet i that arrives in a queue, the completion time 
   * c_time(i) is:
   * c_time(i) = max {(time() + size(i)/rate) ; (c_time(i-1) + size(i)/rate)}
   * Note that the size of a packet is measured in bytes while the bandwidth
   * is measured in bits per second, hence the 'size()*8' calculation in
   * the formula below.
   */
  if (Scheduler::instance().clock() > next_time_) {
    next_time_ = Scheduler::instance().clock() + hdr->size()*8 / bw_; } 
  else {
    next_time_ = next_time_ + hdr->size()*8 / bw_;
  }
}


/* 
 * There are no commands for the class WFQClass yet. This might
 * change later.
 */
int WFQClass::command(int argc, const char*const* argv) {
  return (Queue::command(argc, argv));
}


static class WFQCl : public TclClass {
public:
  WFQCl() : TclClass("Queue/WFQ") {}
  TclObject* create(int, const char*const*) {
    return (new WFQ);
  }
} class_WFQ;


WFQ::WFQ() : queue_list_(0) {
  // int i; - unused
  bind("off_ip_", &off_ip_);
  bind("off_cmn_", &off_cmn_);
  bind_bool("wf2q_", &wf2q_);
  bind_bool("best_effort_", &best_effort_);
  bind_bool("borrow_", &borrow_);
  bind_bool("prio_", &prio_);
  bind("num_classes_", &num_classes_);
  bind("num_flows_", &num_flows_);
  bind("num_drops_", &num_drops_);
  bind("size_drops_", &size_drops_);
  hash = new Hashtable(HASHBUCKETS);
}
 

/* 
 * New classes can be added to (or removed from) a WFQ link with
 * 'add WFQClass' (or 'remove WFQClass'). Flows can be assigned to
 * a class (or the assignment can be deleted) with 'bind WFQClass <flowid>'
 * (or 'unbind <flowid>').
 */
int WFQ::command(int argc, const char*const* argv) {
  Tcl& tcl = Tcl::instance();
  if (argc == 3) {
    // add WFQClass
    if (strcmp(argv[1], "add") == 0) {
      WFQClass *cl = (WFQClass*)TclObject::lookup(argv[2]);
      if (cl == NULL) {
	tcl.resultf("WFQ: no class object %s", argv[2]);
	return (TCL_ERROR);
      }
      insert(cl);
      num_classes_++;
      return (TCL_OK);
    }
    // remove WFQClass
    if (strcmp(argv[1], "remove") == 0) {
      WFQClass *cl = (WFQClass*)TclObject::lookup(argv[2]);
      if (cl == NULL) {
	tcl.resultf("WFQ: no class object %s", argv[2]);
	return (TCL_ERROR);
      }
      WFQClass *search = queue_list_;
      if (queue_list_ == NULL) {
	tcl.resultf("WFQ: no class object %s found in WFQ link", argv[2]);
	return (TCL_ERROR);
      }
      if (queue_list_ == cl) {
	queue_list_ = queue_list_->next_;
      } else {
	while ((search->next_ != NULL) && (search->next_ != cl)) {
	  search = search->next_;
	}
	if (search->next_ == NULL) {
	  tcl.resultf("WFQ: no class object %s found in WFQ link", argv[2]);
	  return (TCL_ERROR);
	}
	search->next_ = search->next_->next_;
      }
      num_classes_--;
      return (TCL_OK);
    }
    // getclass <flowid>
    if (strcmp(argv[1], "getclass") == 0) {
      WFQClass *cl;
      int fid = atoi(argv[2]);
      if ((cl = (WFQClass *)hash->lookup(fid)) == NULL) {
	tcl.resultf("");
      } else {
	tcl.resultf("%s", cl->name());
      }
      return (TCL_OK);
    }
  }
  if ((argc == 4) || (argc == 5)) {
    // bind WFQClass <priority>   or   bind WFQClass <src id> <flowid>
    if (strcmp(argv[1], "bind") == 0) {
      WFQClass *cl = (WFQClass*)TclObject::lookup(argv[2]);
      if (cl == NULL) {
	tcl.resultf("WFQ: no class object %s", argv[2]);
	return (TCL_ERROR);
      }
      WFQClass *search = queue_list_;
      while ((search != NULL) && (search != cl)) {
	search = search->next_;
      }
      if (search == NULL) {
	tcl.resultf("WFQ: no class object %s found in WFQ link", argv[2]);
	return (TCL_ERROR);
      }
      int fid = -1;
      if ((prio_) && (argc == 4)) {  
	fid = atoi(argv[3]);
      }
      if ((!prio_) && (argc == 5)) {
	fid = (atoi(argv[3]) + 1) * FLOWNUM + atoi(argv[4]);
      }
      if (fid == -1) {
	tcl.resultf("WFQ: Wrong number of arguments for bind");
	return (TCL_ERROR);
      }
      hash->insert(cl, fid);
      num_flows_++;
      return(TCL_OK);
    }
  }
  if ((argc == 3) || (argc == 4)) {
    // unbind <flowid>   or   unbind <src id> <flowid>
    if (strcmp(argv[1], "unbind") == 0) {
      int fid = -1;
      if ((prio_) && (argc == 3)) {  
	fid = atoi(argv[2]);
      }
      if ((!prio_) && (argc == 4)) {
	fid = (atoi(argv[2]) + 1) * FLOWNUM + atoi(argv[3]);
      }
      if (fid == -1) {
	tcl.resultf("WFQ: Wrong number of arguments for unbind");
	return (TCL_ERROR);
      }
      if (hash->lookup(fid) == NULL) {
	tcl.resultf("%s WFQ: No class assigned to flow %d", name(), fid);
	return (TCL_ERROR);
      }
      hash->remove(fid);
      num_flows_--;
      return(TCL_OK);
    }
  }
  return (Queue::command(argc, argv));
}


int WFQ::length() {
  WFQClass *s = queue_list_;
  int l;
  l = 0;
  while (s != NULL) {
    l += s->length();
    s = s->next_;
  }
  return l;
}


void WFQ::enque(Packet* p)
{
  int num;
  WFQClass *cl; // , *next; - next is unused
  int be;
  Tcl& tcl = Tcl::instance();
  hdr_ip *hdr = (hdr_ip*)p->access(off_ip_);
  // Check if a class has been assigned to this flow/priority:
  if (prio_) {
    num = hdr->prio();
    cl = (WFQClass *)hash->lookup(num);
    if ((be = (cl == NULL))) {
      if (best_effort_) {
	cl = (WFQClass *)hash->lookup(0);
      } else {
	tcl.evalf("%s WFQ: unknown priority %u",name(), num);
      }
    }
  } else {
    // num = ((hdr->src() >> Address::instance().NodeShift_[1]) + 1) * FLOWNUM +
    num = ( hdr->saddr() + 1 ) * FLOWNUM + // SM
      hdr->flowid();
    cl = (WFQClass *)hash->lookup(num);
    if (cl == NULL) {
      num = hdr->flowid();
      cl = (WFQClass *)hash->lookup(num);
    }
    if ((be = (cl == NULL))) {
      if (best_effort_) {
	cl = (WFQClass *)hash->lookup(0);
      } else {
	tcl.evalf("%s WFQ: unknown flow %u",name(), num);
      }
    }
  }
  /* Is the queue full? Drop the packet, or if best effort and borrow 
     mode is enabled and it is not already in the best-effort class, 
     try to insert it into the best-effort class. */
  hdr_cmn *hdrc = (hdr_cmn*)p->access(off_cmn_);
  if (cl->length() + hdrc->size() > cl->limit()) {
    if (best_effort_ && borrow_ && (num > 0)) {
      cl = (WFQClass*)hash->lookup(0);
      if (cl->length() + hdrc->size() > cl->limit()) {
	drop(p);
	if (!be) {
	  num_drops_++;
	  size_drops_ += hdrc->size();
	}
      } else {
	cl->enque(p);
	// Check if the queue was empty. In that case, calculate
	// the GPS completion time for the new packet.
	if (cl->get_next_time() == -1) {
	  cl->calculate_next_time();
	}
	// Sort the queue list
	reinsert(cl);
      }
    } else {
      drop(p);
      if ((!be) && (num > 0)) {
  	num_drops_++;
	size_drops_ += hdrc->size();
      }
    }
  } else {
    cl->enque(p);
    // Check if the queue was empty. In that case, calculate
    // the GPS completion time for the new packet.
    if (cl->get_next_time() == -1) {
      cl->calculate_next_time();
    }
    // Sort the queue list
    reinsert(cl);
  }
}


int WFQ::greater(double t1, double t2) {
  if (t2 == -1) return 0;
  if (t1 == -1) return 1;
  if (t1 > t2) return 1;
  return 0;
}


/*
 * The function 'WFQ::insert()' inserts a WFQClass into the sorted
 * queue list
 */
void WFQ::insert(WFQClass *element) {
 if ((queue_list_ == NULL) || 
     greater(queue_list_->get_next_time(), element->get_next_time())) {
    element->next_ = queue_list_;
    queue_list_ = element;
  } else {
    WFQClass *search = queue_list_;
    WFQClass *next = search->next_;
    while ((next != NULL) && 
	   greater(element->get_next_time(), next->get_next_time())) {
      search = search->next_;
      next = next->next_;
    }
    search->next_ = element;
    element->next_ = next;
  }
}


/*
 * The function 'WFQ::reinsert' removes an element for the sorted
 * queue list, then inserts it in the right place with the 'WFQ::insert()'
 * function.
 */
void WFQ::reinsert(WFQClass *element) {
  WFQClass *search;
  if (queue_list_ == element) {
    queue_list_ = queue_list_->next_;
    insert(element);
  } else {
    search = queue_list_;
    while (search->next_ != element) {
      search = search->next_;
    }
    search->next_ = element->next_;
    insert(element);
  }
}


/*
 * The function 'WFQ::deque()' has to decide which queue is to be
 * served next. In the original WFQ algorithm, this is always the queue
 * with the lowest completion time for the next packet. In WF2Q, it is
 * the queue with the lowest completion time of all queues that would
 * already be served in the GPS system (or if no queues would be served
 * at the moment, the queue with the lowest completion time is chosen).
 */
Packet* WFQ::deque()
{
  Packet *p; //, *np; - np is unused
  // Are we using the WFQ or the WF2Q algorithm?
  if (wf2q_ == 0) {
    // ***** WFQ *****
    WFQClass *head;
    // Are there any packets in the queue?
    if ((queue_list_ == NULL) || (queue_list_->get_next_time() == -1)) {
      return NULL;
    }
    // Take the next packet from the first queue in the list
    p = queue_list_->deque();
    // Determine the next completion time: Either -1 if the queue is
    // empty now, or the result of the 'calculate_next_time' function.
    // Then insert the queue in the right place in the sorted queue list.
    if (queue_list_->length() == 0) {
      queue_list_->set_next_time(-1);
      if ((queue_list_->next_ != NULL) && 
	  (queue_list_->next_->get_next_time() != -1)) {
	head = queue_list_;
	queue_list_ = queue_list_->next_;
	insert(head);
      }
    } else {
      queue_list_->calculate_next_time();
      if ((queue_list_->next_ != NULL) && 
	  (queue_list_->next_->get_next_time() != -1) &&
	  (queue_list_->next_->get_next_time() < queue_list_->get_next_time())) {
	head = queue_list_;
	queue_list_ = queue_list_->next_;
	insert(head);
      }
    }
    return p;
  } else {
    // ***** WF2Q *****
    WFQClass *search, *element;
    // Are there any packets in the queue?
    if ((queue_list_ == NULL) || (queue_list_->get_next_time() == -1)) {
      return NULL;
    }
    // Has the first queue in the list already started service in the 
    // GPS system?
    if (Scheduler::instance().clock() > queue_list_->get_last_time()) {
      element = queue_list_;
      queue_list_ = queue_list_->next_;
    } else {
      // If not, search for the first queue in the list which has
      // started service in the GPS system
      search = queue_list_;
      while ((search->next_ != NULL) && 
	     (Scheduler::instance().clock() <= search->next_->get_last_time()) &&
	     (search->next_->get_next_time() != -1)) {
	search = search->next_;
      }
      // If none is found, simply choose the first queue.
      if ((search->next_ == NULL) || (search->next_->get_next_time() == -1)) {
	element = queue_list_;
	queue_list_ = queue_list_->next_;
      } else {
	element = search->next_;
	search->next_ = search->next_->next_;
      }
    }
    // Take the first packet from the queue, recalculate the completion
    // time (either -1 if the queue is empty now, or the result of the
    // 'calculate_next_time()' function), then insert the element into
    // the right place in the sorted queue list.
    p = element->deque();
    if (element->length() == 0) {
      element->set_last_time(-1);
      element->set_next_time(-1);
    } else {
      element->calculate_next_time();
    }
    insert(element);      
    return p;
  }
}


Hashtable::Hashtable(int buckets) {
  buckets_ = buckets;
  table_ = new (node *)[buckets];
  int i;
  for (i = 0; i < buckets; i++) {
    table_[i] = NULL;
  }
}


void Hashtable::insert(TclObject *obj, int value) {
  if (lookup(value) == NULL) {
    int bucket = value % buckets_;
    node *n, *s;
    n = new node;
    n->obj = obj;
    n->value = value;
    n->next = NULL;
    if (table_[bucket] == NULL) {
      table_[bucket] = n;
    } else {
      if (value < table_[bucket]->value) {
	n->next = table_[bucket];
	table_[bucket] = n;
      } else {
	s = table_[bucket];
	/* The elements are sorted in ascending order. Since it can be assumed
	   that lookups will occur much more often than inserts, this can
	   increase the performance considerably. */
	while ((s->next != NULL) && (s->next->value < value)) {
	  s = s->next;
	}
	n->next = s->next;
	s->next = n;
      }
    }
  }
}


void Hashtable::remove(int value) {
  int bucket = value % buckets_;
  node *temp;
  node *s = table_[bucket];
  if (s != NULL) {
    if (s->value == value) {
      table_[bucket] = s->next;
      delete s;
    } else {
      while ((s->next != NULL) && (s->next->value < value)) {
	s = s->next;
      }
      if ((s->next != NULL) && (s->next->value == value)) {
	temp = s->next;
	s->next = temp->next;
	delete temp;
      }
    }
  }
}



TclObject *Hashtable::lookup(int value) {
  int bucket = value % buckets_;
  node *s = table_[bucket];
  while ((s != NULL) && (s->value != value)) {
    s = s->next;
  }
  if (s != NULL) {
    return s->obj;
  } else {
    return NULL;
  }
}