wfq.cc

rsvp and wfq patch for Netowrk Simulator 2

    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_);
  hdr_cmn *hdrc = hdr_cmn::access(p) ;
  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;
  }
}