Queues and agents

Agent	The base class for an agent.
InfoAgent	An agent that carries information about the QueueNetwork around.
InfoQueue	A queue that stores information about the network.
GreedyAgent	An agent that chooses the queue with the shortest line as their next destination.
LossQueue	A finite capacity queue.
NullQueue	A terminal queue.
poisson_random_measure	A function that returns the arrival time of the next arrival for a Poisson random measure.
QueueServer	The base queue-server class.
ResourceAgent	An agent designed to interact with the ResourceQueue class.
ResourceQueue	An queue designed to interact with the ResourceAgent class.

Queues

class queueing_tool.queues.QueueServer(num_servers=1, edge=(0, 0, 0, 1), arrival_f=lambda t: ..., service_f=lambda t: ..., AgentFactory=Agent, keep_data=False, active_cap=np.infty, deactive_t=np.infty, coloring_sensitivity=2, **kwargs)

The base queue-server class.

Built to work with the QueueNetwork class, but can stand alone as a multi-server queue. It supports a capped pool of potential arrivals using the active_cap attribute, as well as the stopping time attribute, deactive_t, after which no more arrivals can enter the queue. When connected to a network of queues via a QueueNetwork, the active_cap and deactive_t attributes applies only to arrivals from outside the network; the QueueServer instance always accepts arrivals from other queues inside the QueueNetwork.

This class supports arbitrary arrival and service distribution functions (that can depend on time but do not on the state of the system).

Note that of the following parameters are assigned to an attribute of the same name.

Parameters:

num_serversint or numpy.infty (optional, default: 1)

The number of servers servicing agents.

arrival_ffunction (optional, default: lambda t: t + exponential(1))

A function that returns the time of next arrival from outside the network. When this function is called, t is always taken to be the current time.

service_ffunction (optional, default: lambda t: t + exponential(0.9))

A function that returns the time of an agent’s service time. When this function is called, t is the time the agent is entering service.

edge4-tuple of int (optional, default: (0, 0, 0, 1))

A tuple that uniquely identifies which edge this queue lays on and the edge type. The first slot of the tuple is the source vertex, the second slot is the target vertex, and the third slot is the edge_index of that edge, and the last slot is the edge type for this queue. This is automatically created when a QueueNetwork instance is created.

AgentFactoryclass (optional, default: the Agent class)

Any function that can create agents. Note that the function must take one parameter.

active_capint (optional, default: infty)

The maximum number of arrivals the queue will accept from outside the network.

deactive_tfloat (optional, default: infty)

Sets a stopping time, after which no more arrivals (from outside the network) will attempt to enter the QueueServer.

collect_databool (optional, default: False)

A bool that defines whether the queue collects each Agent's arrival, service start, and departure times and other data. See fetch_data() for more on the information that is collected.

colorsdict (optional)

A dictionary of the colors used when drawing the graph. The possible colors are:

edge_loop_color

The default color of the edge if the edge is a loop.

edge_color

The normal color a non-loop edge.

vertex_fill_color

The normal fill color for a vertex; this also colors the target vertex in the graph if the edge is a loop.

vertex_color

The color of the vertex border if the edge is a loop.

The defaults are listed in the notes.

coloring_sensitivityint (optional, default: 2)

Specifies how sensitive the coloring of the queue is to the number of arrivals. See the notes for how this parameter affects coloring.

seedint (optional)

If supplied seed is used to initialize numpy’s psuedo-random number generator.

Notes

This is a generic multi-server queue implimentation (see [4]). In Kendall’s notation, this is a \(\text{GI}_t/\text{GI}_t/c/\infty/N/\text{FIFO}\) queue class, where \(c\) is set by num_servers and \(N\) is set by active_cap. See chapter 1 of [3] (pdfs from the author and the publisher) for a good introduction to the theory behind the multi-server queue.

Each queue sits on an edge in a graph. When drawing the graph, the queue colors the edges. If the target vertex does not have any loops, the number of agents in this queue affects the target vertex’s color as well.

Some defaults:

>>> default_colors = {
...     'edge_loop_color'   : [0, 0, 0, 0],
...     'edge_color'        : [0.9, 0.9, 0.9, 0.5],
...     'vertex_fill_color' : [1.0, 1.0, 1.0, 1.0],
...     'vertex_color'      : [0.0, 0.5, 1.0, 1.0]
... }

If the queue is in a QueueNetwork and lies on a non-loop edge, the coloring of the edge is given by the following code:

>>> div = coloring_sensitivity * num_servers + 1. 
>>> tmp = 1. - min(num_system / div, 1)  
>>> color = [i * tmp for i in colors['edge_color']] 
>>> color[3] = 1 / 2. 

References

[3]

Harchol-Balter, Mor. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013. ISBN: 9781107027503.

[4]

Queueing Theory, Wikipedia http://en.wikipedia.org/wiki/Queueing_theory.

Examples

The following code constructs an \(\text{M}_t/\text{GI}/5\) QueueServer with mean utilization rate \(\rho = 0.8\). The arrivals are modeled as a Poisson random measure with rate function \(r(t) = 2 + 16 \sin^2(\pi t / 8)\) and a service distribution that is gamma with shape and scale parameters 4 and 0.1 respectively. To create such a queue run:

>>> import queueing_tool as qt
>>> import numpy as np
>>> def rate(t): return 2 + 16 * np.sin(np.pi * t / 8)**2
>>> def arr(t): return qt.poisson_random_measure(t, rate, 18)
>>> def ser(t): return t + np.random.gamma(4, 0.1)
>>> q = qt.QueueServer(5, arrival_f=arr, service_f=ser)

Before you can simulate the queue, it must be set to active; also, no data is collected by default, we change these with the following:

>>> q.set_active()
>>> q.collect_data = True

To simulate 12000 events and collect the data run

>>> q.simulate(n=12000)
>>> data = q.fetch_data()

Attributes:

activebool

Returns whether the queue accepts arrivals from outside the network (the queue will always accept arrivals from inside the network). The default is False. To change call set_active().

coloring_sensitivityint

Specifies how sensitive the coloring of the edge is to the number of arrivals.

current_timefloat

The time of the last event.

datadict

Keeps track of each Agent's arrival, service start, and departure times, as well as how many other agents were waiting to be served and the total number agents in the system (upon arrival). The keys are the Agent's unique agent_id, and the values is a list of lists. Each time an agent arrives at the queue it appends this data to the end of the list. Use fetch_data() to retrieve a formated version of this data.

num_arrivalslist

A list with two entries. The first slot is the total number of arrivals up until the current_time. The second slot is the number of arrivals created using the servers AgentFactory, which includes agents that have been created but arrive in the future.

num_departuresint

The total number of departures from the queue.

num_systemint

The number of agents in the entire QueueServer at the current_time – this includes those being served and those waiting to be served.

queuedeque

A queue for the agents waiting to enter service.

timefloat

The time of the next event.

at_capacity()

Returns whether the queue is at capacity or not.

Returns:

bool

Always returns False, since the QueueServer class has infinite capacity.

clear()

Clears out the queue. Removes all arrivals, departures, and queued agents from the QueueServer, resets num_arrivals, num_departures, num_system, and the clock to zero. It also clears any stored data and the server is then set to inactive.

copy()

Returns a deep copy of itself.

delay_service(t=None)

Adds an extra service time to the next departing Agent's service time.

Parameters:

tfloat (optional)

Specifies the departing time for the agent scheduled to depart next. If t is not given, then an additional service time is added to the next departing agent.

fetch_data(return_header=False)

Fetches data from the queue.

Parameters:

return_headerbool (optonal, default: False)

Determines whether the column headers are returned.

Returns:

datandarray

A six column ndarray of all the data. The columns are:

• 1st: The arrival time of an agent.

• 2nd: The service start time of an agent.

• 3rd: The departure time of an agent.

• 4th: The length of the queue upon the agents arrival.

• 5th: The total number of Agents in the QueueServer.

• 6th: The QueueServer's edge index.

headersstr (optional)

A comma seperated string of the column headers. Returns 'arrival,service,departure,num_queued,num_total,q_id'

next_event()

Simulates the queue forward one event.

Use simulate() instead.

Returns:

outAgent (sometimes)

If the next event is a departure then the departing agent is returned, otherwise nothing is returned.

See also

simulate()

Simulates the queue forward.

next_event_description()

Returns an integer representing whether the next event is an arrival, a departure, or nothing.

Returns:

outint

An integer representing whether the next event is an arrival or a departure: 1 corresponds to an arrival, 2 corresponds to a departure, and 0 corresponds to nothing scheduled to occur.

number_queued()

Returns the number of agents waiting in line to be served.

Returns:

outint

The number of agents waiting in line to be served.

set_active()

Changes the active attribute to True. Agents may now arrive from outside the network.

set_inactive()

Changes the active attribute to False.

set_num_servers(n)

Change the number of servers in the queue to n.

Parameters:

nint or numpy.infty

A positive integer (or numpy.infty) to set the number of queues in the system to.

Raises:

TypeError

If n is not an integer or positive infinity then this error is raised.

ValueError

If n is not positive.

simulate(n=1, t=None, nA=None, nD=None)

This method simulates the queue forward for a specified amount of simulation time, or for a specific number of events.

Parameters:

nint (optional, default: 1)

The number of events to simulate. If t, nA, and nD are not given then this parameter is used.

tfloat (optional)

The minimum amount of simulation time to simulate forward.

nAint (optional)

Simulate until nA additional arrivals are observed.

nDint (optional)

Simulate until nD additional departures are observed.

Examples

Before any simulations can take place the QueueServer must be activated:

>>> import queueing_tool as qt
>>> import numpy as np
>>> rate = lambda t: 2 + 16 * np.sin(np.pi * t / 8)**2
>>> arr = lambda t: qt.poisson_random_measure(t, rate, 18)
>>> ser = lambda t: t + np.random.gamma(4, 0.1)
>>> q = qt.QueueServer(5, arrival_f=arr, service_f=ser, seed=54)
>>> q.set_active()

To simulate 50000 events do the following:

>>> q.simulate(50000)
>>> num_events = q.num_arrivals[0] + q.num_departures
>>> num_events
50000

To simulate forward 75 time units, do the following:

>>> t0 = q.time
>>> q.simulate(t=75)
>>> round(float(q.time - t0), 1)
75.1
>>> q.num_arrivals[1] + q.num_departures - num_events
1597

To simulate forward until 1000 new departures are observed run:

>>> nA0, nD0 = q.num_arrivals[1], q.num_departures
>>> q.simulate(nD=1000)
>>> q.num_departures - nD0, q.num_arrivals[1] - nA0
(1000, 983)

To simulate until 1000 new arrivals are observed run:

>>> nA0, nD0 = q.num_arrivals[1], q.num_departures
>>> q.simulate(nA=1000)
>>> q.num_departures - nD0, q.num_arrivals[1] - nA0,
(987, 1000)

class queueing_tool.queues.LossQueue(qbuffer=0, **kwargs)

Bases: QueueServer

A finite capacity queue.

If an agent arrives to a queue that is at capacity, then the agent gets blocked. If this agent is arriving from inside the network then that agent has to stay at their current queue. If the agent is arriving from outside the network then the agent is deleted.

Parameters:

qbufferint (optional, default: 0)

Specifies the maximum number of agents that can be waiting to be serviced.

**kwargs

Any QueueServer parameters.

Notes

In Kendall’s notation, this is a \(\text{GI}_t/\text{GI}_t/c/c+b/N/\text{FIFO}\) queue, where \(b\) is the qbuffer. If the default parameters are used then the instance is an \(\text{M}/\text{M}/1/1\) queue.

Attributes:

num_blockedint

The number of times arriving agents have been blocked because the server was full.

bufferint

Specifies how many agents can be waiting to be serviced.

at_capacity()

Returns whether the queue is at capacity or not.

Returns:

outbool

Returns whether the number of agents in the system – the number of agents being serviced plus those waiting to be serviced – is equal to num_servers + buffer.

clear()

Clears out the queue. Removes all arrivals, departures, and queued agents from the QueueServer, resets num_arrivals, num_departures, num_system, and the clock to zero. It also clears any stored data and the server is then set to inactive.

next_event()

Simulates the queue forward one event.

Use simulate() instead.

Returns:

outAgent (sometimes)

If the next event is a departure then the departing agent is returned, otherwise nothing is returned.

See also

simulate()

Simulates the queue forward.

class queueing_tool.queues.InfoQueue(net_size=1, AgentFactory=InfoAgent, qbuffer=np.infty, **kwargs)

Bases: LossQueue

A queue that stores information about the network.

This queue gets information about the state of the network (number of Agent's at other queues) from arriving InfoAgent's. When an InfoAgent arrives, the queue extracts all the information the agent has and replaces it’s out-of-date network information with the agents more up-to-date information (if the agent has any). When an InfoAgent departs this queue, the queue gives the departing agent all the information it has about the state of the network.

Parameters:

net_sizeint (optional, default: 1)

The total number of edges in the network.

AgentFactoryclass (optional, default: InfoAgent)

The class of agents that arrive from outside the network.

qbufferint (optional, default: infty)

The maximum number of agents that can be waiting to be serviced.

**kwargs

Extra parameters to pass to LossQueue.

clear()

Clears out the queue. Removes all arrivals, departures, and queued agents from the QueueServer, resets num_arrivals, num_departures, num_system, and the clock to zero. It also clears any stored data and the server is then set to inactive.

next_event()

Simulates the queue forward one event.

Use simulate() instead.

Returns:

outAgent (sometimes)

If the next event is a departure then the departing agent is returned, otherwise nothing is returned.

See also

simulate()

Simulates the queue forward.

class queueing_tool.queues.ResourceQueue(num_servers=10, AgentFactory=ResourceAgent, qbuffer=0, **kwargs)

Bases: LossQueue

An queue designed to interact with the ResourceAgent class.

If a ResourceAgent does not have a resource already it will take a resource from this queue when it departs. It does this by reducing the number of servers here by one. When a ResourceAgent arrives to this queue with a resource, it adds one to the number of servers here. The ResourceAgent is then deleted.

Attributes:

max_serversint

The maximum number of servers that can be here. This is a soft max, and it is only used to keep track of how often the queue will be overflowing with resources.

over_maxint

The number of times an agent has deposited a resource here when the number of servers was at max_servers.

kwargs

Any arguments to pass to LossQueue.

clear()

Clears out the queue. Removes all arrivals, departures, and queued agents from the QueueServer, resets num_arrivals, num_departures, num_system, and the clock to zero. It also clears any stored data and the server is then set to inactive.

next_event()

Simulates the queue forward one event.

This method behaves identically to a LossQueue if the arriving/departing agent is anything other than a ResourceAgent. The differences are;

Arriving:

• If the ResourceAgent has a resource then it deletes the agent upon arrival and adds one to num_servers.

• If the ResourceAgent is arriving without a resource then nothing special happens.

Departing:

• If the ResourceAgent does not have a resource, then num_servers decreases by one and the agent then has a resource.

Use simulate() for simulating instead.

set_num_servers(n)

Change the number of servers in the queue to n.

Parameters:

nint or numpy.infty

A positive integer (or numpy.infty) to set the number of queues in the system to.

Raises:

TypeError

If n is not an integer or positive infinity then this error is raised.

ValueError

If n is not positive.

class queueing_tool.queues.NullQueue(*args, **kwargs)

Bases: QueueServer

A terminal queue.

A queue that is used by the QueueNetwork class to represent agents leaving the network. Since the NullQueue is used to represent agents leaving the network, all agents that arrive to this queue are deleted.

This class can collect data on agents, but only collects each agent’s arrival time. With the exception of next_event_description, number_queued, and current_color, all inherited methods have been replaced with pass. The methods next_event_description() and number_queued() will always return 0.

Agents

class queueing_tool.queues.Agent(agent_id=(0, 0), **kwargs)

The base class for an agent.

Agents are the objects that move throughout the network. Agents are instantiated by a queue, and once serviced the Agent moves on to another queue in the network. Each Agent decides where in the network it wants to arrive at next but choosing amongst its options randomly. The probabilities are specified in QueueNetwork's transition matrix. See set_transitions() for changing the routing probabilities.

Parameters:

agent_idtuple (optional, default: (0, 0))

A unique identifier for an agent. Is set automatically by the QueueServer that instantiates the Agent. The first slot is the QueueServer's edge index and the second slot is the Agent's instantiation number for that queue.

**kwargs

Unused.

Attributes:

agent_idtuple

A unique identifier for an agent.

blockedint

Specifies how many times an agent has been blocked by a finite capacity queue.

add_loss(*args, **kwargs)

Adds one to the number of times the agent has been blocked from entering a queue.

desired_destination(network, edge)

Returns the agents next destination given their current location on the network.

An Agent chooses one of the out edges at random. The probability that the Agent will travel along a specific edge is specified in the QueueNetwork's transition matrix.

Parameters:

networkQueueNetwork

The QueueNetwork where the Agent resides.

edgetuple

A 4-tuple indicating which edge this agent is located at. The first two slots indicate the current edge’s source and target vertices, while the third slot indicates this edges edge_index. The last slot indicates the edge type of that edge

Returns:

outint

Returns an the edge index corresponding to the agents next edge to visit in the network.

See also

transitions()

QueueNetwork's method that returns the transition probabilities for each edge in the graph.

queue_action(queue, *args, **kwargs)

A method that acts on the queue the Agent is at. This method is called when the Agent arrives at the queue (where args[0] == 0), when service starts for the Agent (where args[0] == 1), and when the Agent departs from the queue (where args[0] == 2). By default, this method does nothing to the queue, but is here if the Agent class is extended and this method is overwritten.

class queueing_tool.queues.GreedyAgent(agent_id=(0, 0))

Bases: Agent

An agent that chooses the queue with the shortest line as their next destination.

Notes

If there are any ties, the GreedyAgent chooses the first queue with the shortest line (where the ordering is given by QueueNetwork's out_edges attribute).

desired_destination(network, edge)

Returns the agents next destination given their current location on the network.

GreedyAgents choose their next destination with-in the network by picking the adjacent queue with the fewest number of Agents in the queue.

Parameters:

networkQueueNetwork

The QueueNetwork where the Agent resides.

edgetuple

A 4-tuple indicating which edge this agent is located at. The first two slots indicate the current edge’s source and target vertices, while the third slot indicates this edges edge_index. The last slot indicates the edges edge type.

Returns:

outint

Returns an the edge index corresponding to the agents next edge to visit in the network.

class queueing_tool.queues.InfoAgent(agent_id=(0, 0), net_size=1, **kwargs)

Bases: Agent

An agent that carries information about the QueueNetwork around.

This agent is designed to work with the InfoQueue. It collects load data (utilization rate, and the number of agents waiting to be served) from each queue that it visits.

Parameters:

agent_idtuple (optional, default: (0, 0))

A unique identifier for an agent. Is set automatically by the queue that instantiates the agent. The first slot is queues edge index and the second slot is specifies the instantiation number for that queue.

net_sizeint (optional, default: 1)

The number of edges in the network.

**kwargs

Any arguments to pass to Agent.

add_loss(qedge, *args, **kwargs)

Adds one to the number of times the agent has been blocked from entering a queue.

queue_action(queue, *args, **kwargs)

A method that acts on the queue the Agent is at. This method is called when the Agent arrives at the queue (where args[0] == 0), when service starts for the Agent (where args[0] == 1), and when the Agent departs from the queue (where args[0] == 2). By default, this method does nothing to the queue, but is here if the Agent class is extended and this method is overwritten.

class queueing_tool.queues.ResourceAgent(agent_id=(0, 0))

Bases: Agent

An agent designed to interact with the ResourceQueue class.

When an ResourceAgent departs from a ResourceQueue, they take a resource from the queue if the agent does not have a resource yet. It does this by reducing the number of servers at that queue by one. When a ResourceAgent with a resource arrives at a ResourceQueue, the ResourceAgent adds a resource to that queue by increasing the number of servers there by one; the ResourceAgent is then deleted.

queue_action(queue, *args, **kwargs)

Function that specifies the interaction with a ResourceQueue upon departure.

When departuring from a ResourceQueue (or a QueueServer), this method is called. If the agent does not already have a resource then it decrements the number of servers at ResourceQueue by one. Note that this only applies to ResourceQueue's.

Parameters:

queueQueueServer

The instance of the queue that the ResourceAgent will interact with.

Queueing Functions

queueing_tool.queues.poisson_random_measure(t, rate, rate_max)

A function that returns the arrival time of the next arrival for a Poisson random measure.

Parameters:

tfloat

The start time from which to simulate the next arrival time.

ratefunction

The intensity function for the measure, where rate(t) is the expected arrival rate at time t.

rate_maxfloat

The maximum value of the rate function.

Returns:

outfloat

The time of the next arrival.

Notes

This function returns the time of the next arrival, where the distribution of the number of arrivals between times \(t\) and \(t+s\) is Poisson with mean

\[\int_{t}^{t+s} dx \, r(x)\]

where \(r(t)\) is the supplied rate function. This function can only simulate processes that have bounded intensity functions. See chapter 6 of [3] for more on the mathematics behind Poisson random measures; the book’s publisher, Springer, has that chapter available online for free at (pdf).

A Poisson random measure is sometimes called a non-homogeneous Poisson process. A Poisson process is a special type of Poisson random measure.

References

[3]

Cinlar, Erhan. Probability and stochastics. Graduate Texts in Mathematics. Vol. 261. Springer, New York, 2011. DOI: 10.1007/978-0-387-87859-1

Examples

Suppose you wanted to model the arrival process as a Poisson random measure with rate function \(r(t) = 2 + \sin( 2\pi t)\). Then you could do so as follows:

>>> import queueing_tool as qt
>>> import numpy as np
>>> np.random.seed(10)
>>> rate  = lambda t: 2 + np.sin(2 * np.pi * t)
>>> arr_f = lambda t: qt.poisson_random_measure(t, rate, 3)
>>> arr_f(1)  
1.491...