UPDATE This is for an old version of queueing-tool.

Queueing-tool is a simulator of queueing networks. It was built to test simulate of transportation systems – such as congestion and parking dynamics – and does so by simulating a network of queues. Although the goal was to apply this tool to transportation, it can be used for lots of other queueing problems.

Installation

If you want to try out queueing-tool, here’s what you do. First you’ll need to install graph-tool and numpy. You probably already have numpy installed so I’ll focus on installing graph-tool. There are precompiled packages of graph-tool made for Debian & Ubuntu. If you follow the link you’ll find graph-tool’s Ubuntu (and Debian) repositories. Once you add them to your sources, open a terminal and run

sudo apt-get install python3-graph-tool

Note that if you want to use Python 2 you can – there is python-graph-tool package in the repository for Python 2 and queueing-tool works fine in Python 2 – but it is recommended that you use Python 3 since some of the visualization packages in graph-tool work better there. Next, you’ll want to clone the queueing-tool repository to your hard drive. To do so, type

git clone https://github.com/djordon/queueing-tool.git

in the terminal. If you don’t have git installed on your computer (and you don’t want to install it) you can go to the github page and download a zip file of the package.

We recommend installing this package locally, rather than in your systems shared resources folder /usr/lib/. In Ubuntu Linux, installing it locally will put the package in ~/.local/lib/python3.4/ (assuming you’re using Python 3.4), and will create this directory if it does not exist. Once you have the package locally on your computer (and unzipped if you downloaded if from github), change directories to the queueing-tool directory in your terminal and install locally using

python3 setup.py build
python3 setup.py install --user

Note that you do not need to use sudo before these command.

Usage

There are only a few of things that this package can do well, and in this section I’ll detail them, and why someone might be interested in a package that can do them.

Simulating a Transportation Network

Suppose you wanted to simulate traffic in an urban environment. Using openstreetmaps.org and a little bit of work, one can create graph of any city’s road network. In this section I’ll explain how to get the simulation up and running, and I’ll be using downtown Pittsburgh as an example.

To begin, first start Python 3 and run the following code

import queueing_tool as qt
import requests
import tempfile

url = 'https://dl.dropboxusercontent.com/u/6214615/graphs/downtown_pittsburgh.xml'
res = requests.get(url)

tmp = tempfile.NamedTemporaryFile(mode='w+t')
tmp.write(res.text)

qn  = qt.QueueNetwork(g=tmp.name)

tmp.close()

The above code will download downtown_pittsburgh.xml but will not save it to disk. If you want to save it you can, just run the following (which saves it to your current working directory).

import queueing_tool as qt
import requests

url = 'https://dl.dropboxusercontent.com/u/6214615/graphs/downtown_pittsburgh.xml'
res = requests.get(url)

with open('downtown_pittsburgh.xml', 'w') as a_file :
    a_file.write(res.text)

qn  = qt.QueueNetwork(g='downtown_pittsburgh.xml')

This creates an instance of a QueueNetwork where the graph uses the network specified in downtown_pittsburgh.xml, and adds Markovian service queues on top of each edge. Specifically, most queues are $M/M/k$ queues where $k$ is the number of lanes for that road. There are also garages and destination nodes in this network, and the queues that represent them are finite capacity Markovian queues. For queues that represent garages, the number of servers is equal to the total number of parking spaces in that garage. There are also queues for traffic lights, but at the moment they are treated $M/M/k$ queues. The default inter-arrival time distribution is $\text{Exp}(1)$, and the default service distribution is $\text{Exp}(0.95)$.

To see what things look like run

qn.draw()

The orange nodes represent traffic lights, the purple nodes represent destinations, the green nodes represent garages, and the blue nodes represent regular roads. Before you can run any simulations, you’ll first have to “initialize” the network. The network is created empty and no queues expect any arrivals from the outside world. To initialize run

qn.initialize(200)
qn.max_agents = 3000

This sets 200 queues, chosen randomly, to being active, which means these 200 queues are now accepting arrivals from the outside world. If you desired, you can specify which queues are active. The max_agents variable sets a cap to the total number of agents allowed in the system at any moment. Note that this system is closed, so there is no way for agents to leave the system once they have arrived.

Now lets simulate. Let’s have the system run for 50,000 events and then view the system. To do so enter

qn.simulate(n=50000)
qn.draw()

Note the difference in the way the graph looks. The shade of each edge depicts how many agents are located at the corresponding queue. The shade of each vertex is determined by the total number of inbound agents. Although loops are not visible by default, the vertex that corresponds to a loop shows how many agents are in that loop.

Very little system time has actually passed, even though 50,000 events have occurred. Take a look at the attribute qn.current_time, which keeps track of the simulation clock. If you want to have a specific amount of simulation time pass, like say 60 time units, use

qn.simulate(t=60)

To see the system changing in real-time, run

qn.animate()

If your computer is like mine, this animation will appear to be happening slowly. This is due to the size of the network, since many objects need to be rendered for each frame.

Queueing Analysis and Simulation

The above demo used only default parameters on a graph was given, but what if you wanted to specify some of the parameters or specify your graph? Right now there is a random graph generating function built-in to test with. It creates a (minimally) connected graph from points that are uniformly distributed on the unit square. Special ‘destination’ and ‘garage’ types are assigned to various nodes. To create such a graph run

g  = qt.generate_pagerank_graph(nVertices=100)
qn = qt.QueueNetwork(g=g)
qn.draw()

At this point in time I’m supposed to explain how to change the parameters but I won’t; I’m too tired.

If you want a special kind of graph, you may be in luck because graph-tool has lots of functions to generate specialized graphs. The following will create price network

import numpy            as np
import queueing_tool    as qt
import graph_tool.all   as gt

g  = gt.price_network(100)
b  = gt.adjacency(g)
m  = b.toarray()
et = b.toarray()

k  = np.argmax(et)
j  = np.argmax(et[k])
et[k, j] = 2

q_cls = {0 : qt.NullQueue,  1 : qt.QueueServer, 2 : qt.QueueServer}
args  = {0 : {'colors'     : {'vertex_pen' : [0.2, 0.3, 0.4, 0.9]}},
         2 : {'nServers'   : 10,
              'colors'     : {'vertex_pen' : [0.2, 0.3, 0.4, 0.9]},
              'arrival_f'  : lambda x : x + np.random.exponential(3),
              'service_f'  : lambda x : x + np.random.exponential(2),
              'max_agents' : np.infty}}

g  = qt.adjacency2graph(m, et)
qn = qt.QueueNetwork(g, q_classes=q_cls, q_args=args)
qn.max_agents = np.infty
qn.initialize(qn.nE)
qn.animate()

Here is the network mid simulation.

You can do other things, like specify a network using the an adjacency list/matrix. You can also look at statistics for individual agents (like their waiting, sojourn, and service times), but they don’t make for as pretty pictures so I’ll pass on that explanation for now.