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/interfaces inherited from interface ikr.simlib.algorithms.queuingDisciplines.QueuingDiscipline

QueuingDiscipline.QueueEntry

Field Summary

Fields

Modifier and Type	Field and Description
protected ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer	activeQ
protected java.util.TreeMap<java.lang.Long,java.util.LinkedList<ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer>>	longestQList
protected int	maxSizeInUnits
protected MessageClassificator<ikr.simlib.algorithms.queuingDisciplines.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() update the sortedQList, that defines which Q is dequeued next, and the longestQList, which defines which Q would be dropped from next, if push() makes that necessary
protected abstract void	addToActiveQList(ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer sq)
protected abstract void	advanceActiveQ()
protected void	bufferStealing() Discard if necessary to obey the maximum size.
abstract ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer	createSortableQDisc(StackableQueuingDiscipline q)
int	getMaxSizeInUnits()
boolean	isEmpty()
protected QueuingDiscipline.QueueEntry	peek() Retrieve the QueueEntry that would be delivered next, without actually removing it.
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(ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer sq, double oldPos)
protected void	updateLongestQList(ikr.simlib.algorithms.queuingDisciplines.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, handleMessage, handleRejectedMessage, hasSpaceFor, 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<ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer> queues

longestQList

protected java.util.TreeMap<java.lang.Long,java.util.LinkedList<ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer>> longestQList

activeQ

protected ikr.simlib.algorithms.queuingDisciplines.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 ProbabilisticQeuingDisciplines. For these, two subsequent calls with the same message may return different results!

createSortableQDisc

public abstract ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer createSortableQDisc(StackableQueuingDiscipline q)

activeQListIsEmpty

protected abstract boolean activeQListIsEmpty()

update the sortedQList, that defines which Q is dequeued next, and the longestQList, which defines which Q would be dropped from next, if push() makes that necessary

Parameters:

sq -

oldKey -

addToActiveQList

protected abstract void addToActiveQList(ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer sq)

updateActiveQList

protected abstract void updateActiveQList(ikr.simlib.algorithms.queuingDisciplines.FairQueuing.SortableQDiscContainer sq,
                     double oldPos)

advanceActiveQ

protected abstract void advanceActiveQ()

updateLongestQList

protected void updateLongestQList(ikr.simlib.algorithms.queuingDisciplines.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

peek

protected QueuingDiscipline.QueueEntry peek()

Description copied from class: StackableQueuingDiscipline

Retrieve the QueueEntry that would be delivered next, without actually removing it.

Specified by:

peek 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