//SOURCE:http://j-sim.googlecode.com/svn/trunk/stable/src/drcl/diffserv/scheduling/
// @(#)wrr.java 9/2002
// Copyright (c) 1998-2002, Distributed Real-time Computing Lab (DRCL)
// 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. Neither the name of "DRCL" nor the names of its contributors may be used
// to endorse or promote products derived from this software without specific
// prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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.
//
package drcl.diffserv.scheduling;
/**
* A Deficit Weighted Round Robin Scheduler
* Base on M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit round robin,"
* Proc. of ACM SIGCOMM '95, Aug. 1995
*
* @author Rong Zheng (zhengr@ee.eng.ohio-state.edu)
* @version 1.0 10/26/2000
* @version 1.1 05/22/2002, Hung-ying Tyan (tyanh@ieee.org)
*
*/
import java.util.*;
import drcl.inet.core.Queue;
import drcl.net.*;
public class wrr extends drcl.diffserv.HQS
{
int lastServed = 0;
Vector vQInfo;
Hashtable htQToQInfo;
public wrr()
{ super(); }
public wrr(String id)
{ super(id);}
public void reset()
{
super.reset(); lastServed = 0;
if (vQInfo != null)
for (int i = 0; i < vQInfo.size(); i++) {
QInfo qi_ = (QInfo)vQInfo.elementAt(i);
if (qi_ == null) continue;
qi_.reset();
}
}
protected Queue pickEligibleQueue(boolean dequeue_)
{
if (vQInfo == null) return null;
Packet p_ = null;
/*
boolean hasPacket_ = false;
for (int nturn_ = 0; nturn_ < vQInfo.size() || hasPacket_;
nturn_++, lastServed = (lastServed + 1) % vQInfo.size()) {
QInfo qi_ = (QInfo)vQInfo.elementAt(lastServed);
if (qi_ == null) continue;
Queue q_ = qi_.q;
if(qi_.turn == 0){
qi_.counter += qi_.weight;
qi_.turn = 1;
}
p_ = (Packet)q_.firstElement();
if (p_ != null) {
hasPacket_ = true;
if(p_.size <= qi_.counter) {
qi_.counter -= p_.size;
if(isDebugEnabled())
debug("nturn:" + nturn_ + ", lastServed:" + lastServed+ ", QInfo:" + qi_ + ", pkt=" + p_);
return q_;
} else {
qi_.turn = 0;
//if(isDebugEnabled())
// debug("not enough counter, lastServed:" + lastServed+ ", QInfo:" + qi_);
}
} else {
// dont accumulate credit when queue is empty
qi_.turn = 0;
qi_.counter = 0;
//if(isDebugEnabled())
// debug("empty queue, lastServed:" + lastServed+ ", QInfo:" + qi_);
}
}
return null;
}
*/
int lastserved_ = lastServed;
int minnturn_ = Integer.MAX_VALUE;
QInfo best_ = null;
Packet pkt_ = null; // the first packet in the best child queue
for (int i = 0; i < vQInfo.size(); i++,
lastserved_ = (lastserved_ + 1) % vQInfo.size()) {
QInfo qi_ = (QInfo)vQInfo.elementAt(lastserved_);
if (qi_ == null) continue;
p_ = (Packet)qi_.q.firstElement();
if (p_ != null) {
// calculate # of turns needed for this child queue to be
// eligible
qi_.turn = true;
int tmp_ = (p_.size - qi_.counter + qi_.weight - 1) / qi_.weight;
if (tmp_ < minnturn_) {
best_ = qi_;
minnturn_ = tmp_;
if (dequeue_) {
lastServed = lastserved_;
pkt_ = p_;
}
}
}
else
qi_.turn = false;
}
if (best_ != null && dequeue_) {
for (int i = 0; i < vQInfo.size(); i++) {
QInfo qi_ = (QInfo)vQInfo.elementAt(i);
if (qi_ == null || !qi_.turn) continue;
qi_.counter += qi_.weight * minnturn_;
if (qi_ == best_) {
qi_.counter -= pkt_.size;
if(isDebugEnabled())
debug("nturn:" + minnturn_ + ", lastServed:" + lastServed
+ ", QInfo:" + qi_ + ", pkt=" + pkt_);
}
}
}
return best_ == null? null: best_.q;
}
public void addQueueSet(Queue child_, long classMask_, long classId_)
{ drcl.Debug.error("Should use addQueueSet(Queue, long, long, int) to specify weight"); }
public void addQueueSet(Queue child_, long classMask_, long classId_, int weight_)
{
super.addQueueSet(child_, classMask_, classId_);
if (vQInfo == null) {
vQInfo = new Vector(3);
htQToQInfo = new Hashtable(3);
}
QInfo new_ = new QInfo(weight_, child_);
vQInfo.addElement(new_);
htQToQInfo.put(child_, new_);
}
public void removeQueueSet(Queue child_)
{
super.removeQueueSet(child_);
if (vQInfo != null) {
QInfo qi_ = (QInfo)htQToQInfo.remove(child_);
if (qi_ != null) vQInfo.removeElement(qi_);
}
}
protected String configInfo(String prefix_)
{
if (vQInfo == null) return "";
Queue lastServed_ = ((QInfo)vQInfo.elementAt(lastServed)).q;
return prefix_ + "LastServed: " + lastServed_.getID() + "\n";
}
protected String configInfo(String prefix_, Queue q_)
{
QInfo qi_ = (QInfo)htQToQInfo.get(q_);
return prefix_ + qi_;
}
class QInfo {
int weight;
int counter = 0;
boolean turn = false;
Queue q;
public QInfo(int w_, Queue q_)
{
weight = w_;
q = q_;
}
void reset()
{
counter = 0;
turn = false;
}
public String toString()
//{ return "weight=" + weight + ", counter=" + counter + ", turn=" + turn; }
{ return "weight=" + weight + ", counter=" + counter; }
}
}
