# 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: t + np.random.exponential(1),service_f=lambda t: t + np.random.exponential(0.9),AgentFactory=Agent,keep_data=False,active_cap=np.infty,deactive_t=np.infty,coloring_sensitivity=2,**kwargs)[source]¶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_servers: int or`numpy.infty`

(optional, default:`1`

)The number of servers servicing agents.

arrival_f: function (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_f: function (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.

edge: 4-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.

AgentFactory: class (optional, default: the`Agent`

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

active_cap: int (optional, default:`infty`

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

deactive_t: float (optional, default:`infty`

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

`QueueServer`

.

collect_data: bool (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.

colors: dict (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_sensitivity: int (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.

seed: int (optional)If supplied

`seed`

is used to initialize numpy’s psuedo-random number generator.Notes

This is a generic multi-server queue implimentation (see [R11]). 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 [R10] (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

[R10] (1, 2)Harchol-Balter, Mor.Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013. ISBN: 9781107027503.

[R11] (1, 2)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 = TrueTo simulate 12000 events and collect the data run

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

active (bool) 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_sensitivity (int) Specifies how sensitive the coloring of the edge is to the number of arrivals. current_time (float) The time of the last event. data (dict) 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_arrivals (list) A list with two entries. The first slot is the total number of arrivals, while the second slot is the number of arrivals from outside the network. num_departures (int) The total number of departures from the queue. num_system (int) The number of agents in the entire `QueueServer`

– this includes those being served and those waiting to be served.queue ( `deque`

) A queue for the agents waiting to enter service.time (float) The time of the next event.

`at_capacity`

()[source]¶Returns whether the queue is at capacity or not.

Returns: bool

Always returns

`False`

, since the`QueueServer`

class has infinite capacity.

`clear`

()[source]¶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.

`delay_service`

(t=None)[source]¶Adds an extra service time to the next departing

`Agent's`

service time.

Parameters:

t: float (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)[source]¶Fetches data from the queue.

Parameters:

return_header: bool (optonal, default:`False`

)Determines whether the column headers are returned.

Returns:

data:`ndarray`

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.

headers: str (optional)A comma seperated string of the column headers. Returns

`'arrival,service,departure,num_queued,num_total,q_id'`

`next_event`

()[source]¶Simulates the queue forward one event.

Use

`simulate()`

instead.

Returns:

out:`Agent`

(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`

()[source]¶Returns an integer representing whether the next event is an arrival, a departure, or nothing.

Returns:

out: intAn 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`

()[source]¶Returns the number of agents waiting in line to be served.

Returns:

out: intThe number of agents waiting in line to be served.

`set_active`

()[source]¶Changes the

`active`

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

`set_num_servers`

(n)[source]¶Change the number of servers in the queue to

`n`

.

Parameters:

n: int or`numpy.infty`

A positive integer (or

`numpy.infty`

) to set the number of queues in the system to.Raises:

TypeErrorIf

`n`

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

ValueErrorIf

`n`

is not positive.

`simulate`

(n=1,t=None,nA=None,nD=None)[source]¶This method simulates the queue forward for a specified amount of simulation time, or for a specific number of events.

Parameters:

n: int (optional, default:`1`

)The number of events to simulate. If

`t`

,`nA`

, and`nD`

are not given then this parameter is used.

t: float (optional)The minimum amount of simulation time to simulate forward.

nA: int (optional)Simulate until

`nA`

additional arrivals are observed.

nD: int (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 50000To 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 1597To 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)[source]¶Bases:

`queueing_tool.queues.queue_servers.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:

qbuffer: int (optional, default:`0`

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

**kwargsAny

`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_blocked (int) The number of times arriving agents have been blocked because the server was full. buffer (int) Specifies how many agents can be waiting to be serviced.

class`queueing_tool.queues.`

`InfoQueue`

(net_size=1,AgentFactory=InfoAgent,qbuffer=np.infty,**kwargs)[source]¶Bases:

`queueing_tool.queues.queue_servers.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_size: int (optional, default:`1`

)The total number of edges in the network.

AgentFactory: class (optional, default:`InfoAgent`

)The class of agents that arrive from outside the network.

qbuffer: int (optional, default:`infty`

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

**kwargs :Extra parameters to pass to

`LossQueue`

.

class`queueing_tool.queues.`

`ResourceQueue`

(num_servers=10,AgentFactory=ResourceAgent,qbuffer=0,**kwargs)[source]¶Bases:

`queueing_tool.queues.queue_servers.LossQueue`

An queue designed to interact with the

`ResourceAgent`

class.If a

`ResourceAgent`

does not have a resource already it will take aresourcefrom 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_servers (int) 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_max (int) 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`

.

`next_event`

()[source]¶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 thenhas a resource.Use

`simulate()`

for simulating instead.

class`queueing_tool.queues.`

`NullQueue`

(*args,**kwargs)[source]¶Bases:

`queueing_tool.queues.queue_servers.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 functions 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)[source]¶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`

decideswhere 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_id: tuple (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_id (tuple) A unique identifier for an agent. blocked (int) Specifies how many times an agent has been blocked by a finite capacity queue.

`add_loss`

(*args,**kwargs)[source]¶Adds one to the number of times the agent has been blocked from entering a queue.

`desired_destination`

(network,edge)[source]¶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:

network:`QueueNetwork`

The

`QueueNetwork`

where the Agent resides.

edge: tupleA 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 edgeReturns:

out: intReturns 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)[source]¶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))[source]¶Bases:

`queueing_tool.queues.agents.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)[source]¶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:

network:`QueueNetwork`

The

`QueueNetwork`

where the Agent resides.

edge: tupleA 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:

out: intReturns 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)[source]¶Bases:

`queueing_tool.queues.agents.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_id: tuple (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_size: int (optional, default: 1)The number of edges in the network.

**kwargs :Any arguments to pass to

`Agent`

.

class`queueing_tool.queues.`

`ResourceAgent`

(agent_id=(0,0))[source]¶Bases:

`queueing_tool.queues.agents.Agent`

An agent designed to interact with the

`ResourceQueue`

class.When an

`ResourceAgent`

departs from a`ResourceQueue`

, they take aresourcefrom 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)[source]¶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:

queue:`QueueServer`

The instance of the queue that the

`ResourceAgent`

will interact with.

## Queueing Functions¶

`queueing_tool.queues.`

`poisson_random_measure`

(t,rate,rate_max)[source]¶A function that returns the arrival time of the next arrival for a Poisson random measure.

Parameters:

t: floatThe start time from which to simulate the next arrival time.

rate: functionThe

intensity functionfor the measure, where`rate(t)`

is the expected arrival rate at time`t`

.

rate_max: floatThe maximum value of the

`rate`

function.Returns:

out: floatThe 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 [R12] 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

[R12] (1, 2)Cinlar, Erhan.Probability and stochastics. Graduate Texts in Mathematics. Vol. 261. Springer, New York, 2011. DOI: 10.1007/978-0-387-87859-1Examples

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...