scfqscheduler.java

中間件開發详细说明：清华大学J2EE教程讲义（ppt）-Tsinghua University J2EE tutorial lectures (ppt) [上载源码成为会员下载此源码] [成为VIP会

/*
 * ** Network and Service Differentiation Extensions to GridSim 3.0 **
 *
 * Gokul Poduval & Chen-Khong Tham
 * Computer Communication Networks (CCN) Lab
 * Dept of Electrical & Computer Engineering
 * National University of Singapore
 * August 2004
 *
 * Licence: GPL - http://www.gnu.org/copyleft/gpl.html
 *
 * SCFQ.java - Implements a Self Clocked Fair Queuing scheduler
 *
 */

package gridsim.net;

import eduni.simjava.*;
import gridsim.*;
import java.util.*;


/**
 * SCFQScheduler implements a Self Clocked Fair Queueing Scheduler. A SCFQ is a
 * variation of Weighted Fair Queueing (WFQ), which is easier to implement than
 * WFQ because it does not need to compute round numbers at every iteration.
 * For more details refer to <b>S. R. Golestani's</b> INFOCOM '94 paper
 * <i>A self-clocked fair queueing scheme for broadband applications</i>.
 * <p>
 * A SCFQ scheduler can provide differentiated service to traffic by changing
 * the weights associated with a certain class of traffic. The higher the weight
 * of a class of traffic, the better treatment it receives. In this class, you
 * can set the weights by calling setWeights() with a linear array of weights.
 * Traffic that is class <tt>0 (default)</tt>, are assigned the first element
 * of the array as its weight.
 * <p>
 * For example: <br>
 * String userName = { "User_0", "User_1", User_2" };  // list of user names<br>
 * int[] trafficClass = { 0, 1, 2 };  // a list of class for each user<br>
 * int[] weights = { 1, 2, 3 };       // a list of weights for each class<br>
 * <br>
 * From the above example, <i>User_0</i> has a traffic class of 0 (low
 * priority), whereas <i>User_2</i> has a traffic class of 2 (high priority)
 * judging from their respective weights.
 *
 * @invariant $none
 * @since GridSim Toolkit 3.1
 * @author Gokul Poduval & Chen-Khong Tham, National University of Singapore
 */
public class SCFQScheduler implements PacketScheduler
{
    private String name_;       // this scheduler name
	private double baudRate_;   // baud rate of this scheduler
    private Vector pktList;     // Sorted List of all Packets
    private Vector timeList;    // Sorted list of finish times
    private double[] weights;   // weights for different ToS packets
    private double CF ;         // current finish number
    private Hashtable flowTable;


    /**
     * Creates a new SCFQ packet scheduler with the specified name and baud rate
     * (in bits/s). The name can be useful for debugging purposes, but serves
     * no functional purposes.
     *
     * @param name       Name of this scheduler
     * @param baudRate   baud rate in bits/s of the port that is using
     *                   this scheduler.
     * @throws ParameterException This happens when the name is null or
     *                   the baud rate <= 0
     * @pre name != null
     * @pre baudRate > 0
     * @post $none
     */
    public SCFQScheduler(String name, double baudRate)
                         throws ParameterException
    {
        if (name == null) {
            throw new ParameterException("SCFQScheduler(): Name is null.");
        }

        if (baudRate <= 0) {
		    throw new ParameterException("SCFQScheduler(): Baudrate <= 0.");
        }

        name_ = name;
        baudRate_ = baudRate;
        init();
    }

    /**
     * Creates a new SCFQ packet scheduler with the specified baud rate
     * (bits/s). The name is set to a generic name: <b>"SCFQScheduler"</b>.
     *
     * @param baudRate   baud rate in bits/s of the port that is using
     *                   this scheduler.
     * @throws ParameterException This happens when the baud rate <= 0
     * @pre baudRate > 0
     * @post $none
     */
    public SCFQScheduler(double baudRate) throws ParameterException
    {
        if (baudRate <= 0) {
		    throw new ParameterException("SCFQScheduler(): Baudrate <= 0.");
        }

        name_ = "SCFQScheduler";
        baudRate_ = baudRate;
        init();
    }

    /**
     * Creates a new SCFQ packet scheduler with the specified name.
     * The baud rate is left at 0, and should be set with
     * {@link gridsim.net.PacketScheduler#setBaudRate(double)}
     * before the simulation starts.
     *
     * @param name Name of this scheduler
     * @throws ParameterException This happens when the name is null
     * @see gridsim.net.PacketScheduler#setBaudRate(double)
     * @pre name != null
     * @post $none
     */
    public SCFQScheduler(String name) throws ParameterException
    {
        if (name == null) {
            throw new ParameterException("SCFQScheduler(): Name is null.");
        }

        name_ = name;
        baudRate_ = 0;
        init();
    }

    /**
     * Creates a new packet scheduler with the name <b>"SCFQScheduler"</b>.
     * The baud rate is left at 0, and should be set with
     * {@link gridsim.net.PacketScheduler#setBaudRate(double)}
     * before the simulation starts.
     * @throws ParameterException This happens when the name is null
     * @see gridsim.net.PacketScheduler#setBaudRate(double)
     * @pre $none
     * @post $none
     */
    public SCFQScheduler() throws ParameterException
    {
        name_ = "SCFQScheduler";
        baudRate_ = 0;
        init();
    }

    /**
     * Initialises all the attributes
     * @pre $none
     * @post $none
     */
    private void init()
    {
        flowTable = new Hashtable();
        pktList = new Vector();
        timeList = new Vector();
        weights = null;
        CF = 0;
    }

    /**
     * This method allows you to set different weights for different types of
     * traffic. Traffic of class <tt>n</tt> are assigned a weight of
     * <tt>weights[n]</tt>. The higher the weight of a class, the better the
     * service it receives. <br>
     * <b>NOTE</b>: Do not set a weight to be <tt>0</tt> or a negative number.
     *
     * @param weights a linear array of the weights to be assigned to different
     *                classes of traffic.
     * @return <tt>true</tt> if it is successful, <tt>false</tt>otherwise
     * @pre weights != null
     * @post $none
     */
    public boolean setWeights(double[] weights)
    {
        if (weights == null) {
            return false;
        }

        // check whether the value of weights are correct
        for (int i = 0; i < weights.length; i++)
        {
            if (weights[i] <= 0)
            {
                System.out.println(name_ +
                    ".setWeights(): Error - weight must be a positive number.");
                return false;
            }
        }

        this.weights = weights;
        return true;
    }

    /**
     * Puts a packet into the queue
     *
     * @param pnp    A Packet to be enqued by this scheduler.
     * @return <tt>true</tt> if enqued, <tt>false</tt> otherwise
     * @pre pnp != null
     * @post $none
     */
    public synchronized boolean enque(Packet pnp)
    {
        int srcID = pnp.getSrcID();     // source entity id
        int destID = pnp.getDestID();   // destination entity id
        int type = pnp.getNetServiceType();     // packet service type

        Double nextTime = (Double) flowTable.get("" + srcID + destID + type);
        if (nextTime == null)
        {
            nextTime = new Double(CF);
            flowTable.put("" + srcID + destID + type, nextTime);
        }

        double pktTime = calculateFinishTime( pnp, nextTime.doubleValue() );
        flowTable.put("" + srcID + destID + type, new Double(pktTime) );
        insert(pnp, pktTime);   // Sort the queue list
        return true;
    }

    /**
     * Calculates the finish time of a particular packet
     * @param np  a network packet
     * @param nextTime  the next available time
     * @pre np != null
     * @pre nextTime >= 0
     * @post $none
     */
    private double calculateFinishTime(Packet np, double nextTime)
    {
        double time = 0;
        double ratio = 0;

        try
        {
            int type = np.getNetServiceType();
            if (type >= weights.length)   // out of bound array error checking
            {
                System.out.println(name_ +".calculateFinishTime(): Warning - " +
                    " packet class = " + type + ", weight.length = " +
                    weights.length);
                type = 0;
            }

            ratio = np.getSize() / weights[type];
        }
        catch(Exception e) {
            ratio = 1;  // default ratio if an error occurs
        }

        if (nextTime > CF) {
                time = nextTime + ratio;
        }
        else {
            time = CF + ratio;
        }

        return time;
    }

    /**
     * This function inserts a WFQClass into the sorted
     * queue list (using binary search)
     *
     * @param np    a network packet
     * @param time  simulation time
     * @pre np != null
     * @pre time >= 0
     * @post $none
     */
    private synchronized void insert(Packet np, double time)
    {
        if ( timeList.isEmpty() )
        {
            timeList.add( new Double(time) );
            pktList.add(np);
            return;
        }

        for (int i = 0; i < timeList.size(); i++)
        {
            double next = ( (Double) timeList.get(i) ).doubleValue();
            if (next > time)
            {
                timeList.add(i, new Double(time));
                pktList.add(i, np);
                return;
            }
        }

        // add to end
        timeList.add( new Double(time) );
        pktList.add(np);
        return;
    }

    /**
     * The method deque() has to decide which queue is to be
     * served next. In the original WFQ algorithm, this is always the
     * packet with lowest finish time. We also need to update the CF
     * (current finish no.) to that of the packet being served.
     *
     * @return the packet to be sent out
     * @pre $none
     * @post $none
     */
    public synchronized Packet deque()
    {
        Packet p = null;
        if (pktList.size() > 0 && timeList.size() > 0)
        {
            p = (Packet) pktList.remove(0);
            CF = ( (Double) timeList.remove(0) ).doubleValue();
        }

        return p;
    }

    /**
     * Determines whether the scheduler is currently keeping any packets in
     * its queue(s).
     *
     * @return <tt>true</tt> if no packets are enqueued, <tt>false</tt>
     *         otherwise
     * @pre $none
     * @post $none
     */
    public synchronized boolean isEmpty() {
        return pktList.isEmpty();
    }

    /**
     * Determines the number of packets that are currently enqueued in this
     * scheduler.
     *
     * @return the number of packets enqueud by this scheduler.
     * @pre $none
     * @post $none
     */
    public synchronized int size() {
        return pktList.size();
    }

    /**
     * Gets the ID of this scheduler.
     * @return the ID of this scheduler or <tt>-1</tt> if no ID is found
     * @pre $none
     * @post $none
     */
    public int getSchedID()
    {
        System.out.println(name_ + ".getID(): No ID is set for this object.");
        return -1;
    }

    /**
     * Gets the name of this scheduler.
     * @return the name of this scheduler
     * @pre $none
     * @post $none
     */
    public String getSchedName() {
        return name_;
    }

    /**
     * Sets the baud rate that this scheduler will be sending packets at.
     * @param rate the baud rate of this scheduler (in bits/s)
     * @pre rate > 0
     * @post $none
     */
    public boolean setBaudRate(double rate)
    {
        if (rate <= 0.0) {
            return false;
        }
        baudRate_ = rate;
        return true;
    }

    /**
     * Returns the baud rate of the egress port that is using this scheduler.
     * If the baud rate is zero, it means you haven't set it up.
     * @return the baud rate in bits/s
     * @see gridsim.net.PacketScheduler#setBaudRate(double)
     * @pre $none
     * @post $result >= 0
     */
    public double getBaudRate() {
        return baudRate_;
    }

    /**
     * Sets the router ID that hosts this scheduler.
     * @param routerID  the router ID that hosts this scheduler
     * @return <tt>true</tt> if successful or <tt>false</tt> otherwise
     * @pre $none
     * @post $none
     */
    public boolean setRouterID(int routerID)
    {
        System.out.println(name_ + ".setRouterID(): Router ID is not required");
        return false;
    }

    /**
     * Gets the router ID that hosts this scheduler.
     * @return the router ID or <tt>-1</tt> if no ID is found
     * @pre $none
     * @post $none
     */
    public int getRouterID() {
        return -1;
    }

} // end class