ikr.simlib.algorithms.queuingDisciplines

Class FairQueuing

java.lang.Object

ikr.simlib.algorithms.queuingDisciplines.StackableQueuingDiscipline

ikr.simlib.algorithms.queuingDisciplines.FairQueuing

All Implemented Interfaces:

QueuingDiscipline, ReflectionConstructable, ReflectionConstructable2<SimNode,Parameters>

Direct Known Subclasses:

DeficitRoundRobinFairQueuing, MessageFairQueuing, UnitFairQueuing

public abstract class FairQueuing
extends StackableQueuingDiscipline

This class is the basis for fair queuing mechanisms, i.e. hierarchical Queuing Disciplines that achieve instantaneous and work saving fair sharing of a bottlenecks bandwidth for the classes / aggregates defined by a MessageClassificator. Fair queuing involves two tasks:

• maintaining a map of the sizes of the sub-QDiscs
• maintaining a data structure needed to dequeue the "right" sub-QDisc. This differs depending on the fairness metric, e.g. bytes or messages.

While the first can mostly be implemented generally, the second cannot and therefore this class is abstract.

Author:

dwagner

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	FairQueuing.SortableQDiscContainer

Nested classes/interfaces inherited from interface ikr.simlib.algorithms.queuingDisciplines.QueuingDiscipline

QueuingDiscipline.QueueEntry

Field Summary

Fields

Modifier and Type	Field and Description
protected FairQueuing.SortableQDiscContainer	activeQ
protected java.util.TreeMap<java.lang.Long,java.util.LinkedList<FairQueuing.SortableQDiscContainer>>	longestQList
protected int	maxSizeInUnits
protected MessageClassificator<?,FairQueuing.SortableQDiscContainer>	queues

Fields inherited from class ikr.simlib.algorithms.queuingDisciplines.StackableQueuingDiscipline

lossProbability, numberOfMessages, numberOfUnits, parent, simNode, transferTime, waitingTime

Fields inherited from interface ikr.simlib.parameters.reflection.ReflectionConstructable

CREATE_INSTANCE_METHOD_NAME

Constructor Summary

Constructors

Constructor and Description
FairQueuing(SimNode ownNode, Parameters pars)

Method Summary

Methods

Modifier and Type	Method and Description
protected abstract boolean	activeQListIsEmpty()
protected abstract void	addToActiveQList(FairQueuing.SortableQDiscContainer sq)
protected abstract void	advanceActiveQ()
protected void	bufferStealing() Discard if necessary to obey the maximum size.
abstract FairQueuing.SortableQDiscContainer	createSortableQDisc(StackableQueuingDiscipline q)
int	getMaxSizeInUnits()
boolean	isEmpty()
protected QueuingDiscipline.QueueEntry	peekInternal()
protected QueuingDiscipline.QueueEntry	pop() Retrieve and remove the next QueueEntry according to the queuing discipline.
protected void	push(QueuingDiscipline.QueueEntry qe) Push message into the data structure managed by the queuing discipline.
protected abstract void	updateActiveQList(FairQueuing.SortableQDiscContainer sq, double oldPos)
protected void	updateLongestQList(FairQueuing.SortableQDiscContainer sq, long oldLength)
abstract boolean	wouldStore(Message msg)

Methods inherited from class ikr.simlib.algorithms.queuingDisciplines.StackableQueuingDiscipline

dequeue, dropScheduledNext, enqueue, getCurrentNumberOfMessages, getCurrentNumberOfUnits, getName, getNode, getParent, handleLossMessage, handleLossMessageInternal, handleMessage, handleRejectedMessage, hasSpaceFor, peek, statsUpdateDequeue, statsUpdateEnqueue, statsUpdateLoss, statsUpdateReject

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

queues

protected MessageClassificator<?,FairQueuing.SortableQDiscContainer> queues

longestQList

protected java.util.TreeMap<java.lang.Long,java.util.LinkedList<FairQueuing.SortableQDiscContainer>> longestQList

activeQ

protected FairQueuing.SortableQDiscContainer activeQ

maxSizeInUnits

protected int maxSizeInUnits

Constructor Detail

FairQueuing

public FairQueuing(SimNode ownNode,
           Parameters pars)

Method Detail

wouldStore

public abstract boolean wouldStore(Message msg)

Specified by:

wouldStore in interface QueuingDiscipline

Overrides:

wouldStore in class StackableQueuingDiscipline

Returns:

true if the queue would store the given message. May return false due to a bounded buffer size or a probabilistic decision, for ProbabilisticQueuingDisciplines. For these, two subsequent calls with the same message may return different results!

createSortableQDisc

public abstract FairQueuing.SortableQDiscContainer createSortableQDisc(StackableQueuingDiscipline q)

activeQListIsEmpty

protected abstract boolean activeQListIsEmpty()

addToActiveQList

protected abstract void addToActiveQList(FairQueuing.SortableQDiscContainer sq)

updateActiveQList

protected abstract void updateActiveQList(FairQueuing.SortableQDiscContainer sq,
                     double oldPos)

advanceActiveQ

protected abstract void advanceActiveQ()

updateLongestQList

protected void updateLongestQList(FairQueuing.SortableQDiscContainer sq,
                      long oldLength)

getMaxSizeInUnits

public int getMaxSizeInUnits()

Specified by:

getMaxSizeInUnits in interface QueuingDiscipline

Specified by:

getMaxSizeInUnits in class StackableQueuingDiscipline

Returns:

maximum size of queue or Integer.MAX_VALUE if queue is unbounded.

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface QueuingDiscipline

Specified by:

isEmpty in class StackableQueuingDiscipline

push

protected void push(QueuingDiscipline.QueueEntry qe)

Description copied from class: StackableQueuingDiscipline

Push message into the data structure managed by the queuing discipline.

Specified by:

push in class StackableQueuingDiscipline

bufferStealing

protected void bufferStealing()

Discard if necessary to obey the maximum size. This implements buffer stealing as introduced in McKenney - "Stochastic Fair Queuing" http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=91316

peekInternal

protected QueuingDiscipline.QueueEntry peekInternal()

Specified by:

peekInternal in class StackableQueuingDiscipline

pop

protected QueuingDiscipline.QueueEntry pop()

Description copied from class: StackableQueuingDiscipline

Retrieve and remove the next QueueEntry according to the queuing discipline.

Specified by:

pop in class StackableQueuingDiscipline

Returns:

the QueueEntry