Pretty Damn Quick

e-mail why PDQ has no GUI

2007-11-15T07:33:00.001-08:00

Neil Gunther has sent you a link to a blog:

Athanasios, Here is my more considered response to the issue of a GUI for PDQ. Hope this clarifies. Best wishes.

Blog: Performance Dynamics Agora
Post: Why Doesn't PDQ Have a GUI?
Link: http://perfdynamics.blogspot.com/2007/09/why-doesnt-pdq-have-gui.html

--
Powered by Blogger
http://www.blogger.com/

PDQ BUGS

2007-08-27T15:45:00.000-07:00

- over 10 nodes in a network throws Exception when EXACT solve method / with APPROX it works but I don't whats the quality of the results.

- GetThrouput() / GetResidenceTime() / GetUtilization() methods have a problem when they are about o return results for a ISRV node (delay cetre)... totally unexpected results are shown instead of 100 and 0 ... I really don't know why.

Lack of support for MSQ nodes:
I have implemented multiserver queues in the PDQ C-language only library, and it is now in beta test.
The goal is to allow you to create OPEN-circuit models (initially) by defining any sequence of M/M/m queues. Instead of introducing a completely new procedure, like PDQ_CreateMultiNode (or PDQ::CreateMultiNode described in Chapter 6 of the Perl::PDQ book), I have come up with a simpler idea. You will call PDQ_CreateNode() in the usual way but, by asserting a new MSQ flag to tell PDQ the node is multi-server queue, you then specify the integer number of servers (m) for that node. For example, an m = 10 multiserver PDQ node named "mserver" would be instantiated using the standard CreateNode procedure with the following arguments:

PDQ_CreateNode("mserver", 10, MSQ).

The PDQ generic report has also been altered to include the new MSQ node.
More details will be forthcoming as the implementation unfolds. Stay tuned.

PageRank Algorithm

2007-08-23T17:44:00.000-07:00

PageRank(DirectedGraph graph, double bias, String edgeWeightKeyName)
Specialized constructor that allows the user to specify an edge key if edges already have user-defined weights assigned to them.

This algorithm measures the importance of a node in terms of the fraction of time spent at that node relative to all other nodes. This fraction is measured by first transforming the graph into a first-order Markov chain where the transition probability of going from node u to node v is equal to (1-alpha)*[1/outdegree(u)] + alpha*(1/|V|) where |V| is the # of vertices in the graph and alpha is a parameter typically set to be between 0.1 and 0.2 (according to the authors). If u has no out-edges in the original graph then 0 is used instead of 1/outdegree(v). Once the markov chain is created, the stationary probability of being at each node (state) is computed using an iterative update method that is guaranteed to converge if the markov chain is ergodic.

PageRank:
PageRank is a link analysis algorithm that assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set. The algorithm may be applied to any collection of entities with reciprocal quotations and references. The numerical weight that it assigns to any given element E is also called the PageRank of E and denoted by PR(E).

PageRank was developed at Stanford University by Larry Page (hence the name Page-Rank[1]) and later Sergey Brin as part of a research project about a new kind of search engine. The project started in 1995 and led to a functional prototype, named Google, in 1998. Shortly after, Page and Brin founded Google Inc., the company behind the Google search engine. While just one of many factors which determine the ranking of Google search results, PageRank continues to provide the basis for all of Google's web search tools.[2]

Simplified PageRank algorithm

Assume a small universe of four web pages: A, B, C and D. The initial approximation of PageRank would be evenly divided between these four documents. Hence, each document would begin with an estimated PageRank of 0.25.

If pages B, C, and D each only link to A, they would each confer 0.25 PageRank to A. All PageRank PR( ) in this simplistic system would thus gather to A because all links would be pointing to A.

PR(A)= PR(B) + PR(C) + PR(D).\,

But then suppose page B also has a link to page C, and page D has links to all three pages. The value of the link-votes is divided among all the outbound links on a page. Thus, page B gives a vote worth 0.125 to page A and a vote worth 0.125 to page C. Only one third of D's PageRank is counted for A's PageRank (approximately 0.083).

PR(A)= \frac{PR(B)}{2}+ \frac{PR(C)}{1}+ \frac{PR(D)}{3}.\,

In other words, the PageRank conferred by an outbound link L( ) is equal to the document's own PageRank score divided by the normalized number of outbound links (it is assumed that links to specific URLs only count once per document).

PR(A)= \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}. \,

In the general case, the PageRank value for any page u can be expressed as:

PR(u) = \sum_{v \in B_u} \frac{PR(v)}{L(v)},

i.e. the PageRank value for a page u is dependent on the PageRank values for each page v out of the set Bu (this set contains all pages linking to page u), divided by the number L(v) of links from page v.

Reference

[] "The Anatomy of a Large-Scale Hypertextual Web Search Engine by L. Page and S. Brin, 1999"

The Evolution of Queueing Networks for Computer System Analysis

2007-08-22T16:18:00.000-07:00

The interaction between the system workload and the system resources determine the behaviour of a system in general. During the early period of queueing analysis the system was treated as a single queue which was serving an infinite population of tasks or jobs. This kind of model, which is based on the classical queueing theory, gives no clues to the relation between the external behaviour and the internal structure of the computing system. Additionally, this model has the limitation of the infinite population. Thus it can not represent the common situation of existing only a finite population of users.

Fig 1.0

In order to overcome this limitation, another model was created, which introduces a number of N terminals to the system, one for each user. In this model the number of jobs is N, and each of these jobs can be in one of the following states:
- “thinking” at the terminal,
- waiting in the queue of the central system,
- or being served by the central system.

Fig 1.1

However, this model, which is known as the “machine repairman” model, fails to represent the complexity of a typical computing system.

A significant step for the evolution of queueing networks occurred with Jackson's model. Jackson has developed a technique for solving a special category of queueing networks. These networks of queues were only involving a single class of jobs. There was also a distinction between open and closed queueing networks. In an open queueing network the jobs were only permitted to enter or leave the network, while in a closed queueing network the jobs were remaining inside. In Jackson's approach each node/queue contains one or more parallel servers, while the service time distributions, for each of these nodes, are assumed to be exponential.

A state of a network which contains M nodes/stations can be expressed a vector:

and expresses the number of jobs at node/station i.

The objective of analysing a Jackson's queueing network model is to find a closed form expression for the equilibrium probability of finding the network in any given state , which is:

Knowing the probabilities of this equilibrium state, several performance variables for the evaluation of the system can be derived, such as the utilization and the average queue length of each node and the throughput of the workload of the network.

If is the marginal probability of finding n jobs at the node then:

The probability of a node to be busy is called utilization it is computed as:

Jackson also proved something that it is termed as a “product form” which defines that, in an open network, the equilibrium probability of state , factors into the product of each of the marginal distributions:

Later, and without knowing about the earlier work of Jackson, two scientists, Gordon and Newell, obtained the equilibrium state probabilities for closed queueing networks. Again the service time distributions for each node was assumed to be exponential. The closed network they studied had a finite number of jobs, N and a finite number of nodes, M. Additionally, each node, i, may have a finite numberof parallel identical servers which have exponentially distributed service times as well. Independently of the state of the network, one job that has just serviced from the node i will be transmitted to the node j with probability .
A state of a network which contains M nodes and N jobs can be expressed as a vector again:

Now, because the network is closed, the sum of all the , must be N.
Gordon and Newell proved what exactly Jackson has proved for the open queueing networks some time ago, but applied to closed queueing networks this time. The equilibrium probability of state in a closed queueing network also satisfies a “product form”:

where G(N) is the normalisation constant which has been chosen to make all the feasible state probabilities sum to one:

where depends on the characteristics of the node:

, if node i is load dependent

OR , if node i is load independent.

In order to evaluate the normalisation constant G(N), a large number of operations is required. Thus, though the above product form solutions are easily expressed, the evaluation of the state probabilities can be computationally expensive. Additionally, the accuracy of the results is in doubt because there is a large number of finite precision arithmetic operations involved.

An efficient computational algorithm for evaluating the normalisation constant was developed by Buzen in the early seventies. Moreover, he studied ways of obtaining the performance measures of a queueing network, like utilisation, throughput and queue length, creating algorithms with simple functions that involve the normalisation constant and the model parameters. In that way more complex systems could be effectively studied.
Continuing his research, Buzen, tried to construct models of queueing networks, that would represent accurately the flow of the several jobs through a computer system. The result of his research was the construction of the “Central Server Model” of a multiprogramming system. In this model the nodes represent the processors of the computer system, while the several jobs/programs move in the direction of the arrows. A Job in this model can visit one node/processor at a time and when one job arrives to a node/processor which is busy, then a queue is formed. Using this type of queueing network models, bottlenecks of a system could be traced easier.

Fig 1.2.

There are two principal limitations to the models that Jackson and Gordon and Newell have studied. In these queueing networks, there is only one class of jobs, and all service time distributions are exponential. However, in a real system these principals are not generally valid, because time distributions are seldom exponential, while each job has its own service parameters for each node.
There are several queueing models that have been proposed in order to represent more accurately real computer systems. The truth is that all of these models expand and actually constitute special cases of the model developed by Baskett, Chandy, Muntz and Palacios (BCMP) in 1975.

The model described by Baskett, Chandy, Muntz and Palacios, in its general form, does not contain the two principal limitations of the previous models. Jobs are divided into R distinct classes, while each class may have different parameters such as a unique set of transition frequencies which has the form:

This expression describes the fraction of departures from node i in class r that go next to node j in class s. The above transition frequency expresses also an additional property of the jobs, which is that they can change class while they are moving through the system. A state of this kind of queueing network represents a distribution of jobs over classes and nodes.
A state of a network which contains M nodes can be expressed as a vector:

, where each component of is also a vector:

.

These vectors express the number of class r jobs at node .
These kind of queueing networks, that have been described by Baskett, Chandy, Muntz and Palacios in 1975, are also called BCMP networks (or models), and they constitute, until now, the most commonly used types of models for system performance evaluation. They can describe accurately a large variety of computer systems, much wider than the restrictive and simple models, introduced by Jackson and Gordon and Newell, are capable to. In general, a BCMP model is capable to describe an open, closed or mixed queueing network. A mixed system is closed for a specific set of classes of jobs and open for the other classes of jobs. However, the complexity of these systems, makes the calculation of their performance measures much more expensive in computing resources.

In a BCMP model each server can have one of the following queue disciplines (service policies):
- FCFS (First Come First Served): The job that arrives earlier in the queue is always served earlier than the one that arrives later, independently to the class that this job belongs to.
- PSHR (Processor Sharing): A single server chooses, using the round robin method, and serves one of the jobs that are waiting in its queue, for a quantum of time.
- ISRV (Infinite Server): An Infinite Server or Delay Centre is considered to be a node in which the number of servers it contains is always at least the maximum number of jobs coming at the node. In this way there is never a job waiting to be served in the queue.
- LCFS (Last Come First Served): The most recent job that arrives to the node, is the one that is served first.

In order to solve queueing network models it is essential to make some assumptions about the properties that influence the transition of the model, from one state to another. Buzen and Denning have studied these necessary assumptions that need to be made in order to simplify the procedure of balancing the flow into and out of system states. In order to simplify this procedure, it is assumed that there are no multiple job arrivals or departures in the system. This assumption, known as “one step transitions”, implies that the rate of job flow between the nodes is the only parameter that determines the rate a system enters or leaves a state. A second assumption declares that the queue length of the specific node is only a parameter that influences the flows out of a node, and not the queue lengths of the other nodes of the system. This assumption is known as “homogeneity”. []

References

[] Steven C. Bruell and Gianfranco Balbo, “Computational Algorithms for Closed Queueing Networks”, Elsevier North Holland, Inc. 1980.

Jung and Visualization

2007-08-18T12:08:00.000-07:00

The Java Universal Network/Graph Framework (JUNG) is a freely provided, under the BSD open-source licence, software library that offers a common and extendible language for the manipulation, analysis, and visualization of graphs and networks. It has been developed in Java programming language so it is portable and extendible. JUNG is not itself a stand alone tool, but it constitutes an object oriented framework which can be used to support the construction of applications and tools for manipulating data that can be represented as a graph or network. []
The architecture of this library supports a variety of representations of entities and their relations. It has been designed to support directed and undirected graphs, graphs with parallel edges, multi-modal graphs, and hypergraphs. Moreover, it provides a built in mechanism for annotating graphs, entities (Vertices) and relations (Edges) with data structures (metadata). It supports complex filtering mechanisms, which extract subsets of a network, and dynamic graphs. Additionally, the JUNG software includes implementations of a number of algorithms. These algorithms are used in exploratory data analysis, social network analysis, graph theory and machine learning. They can be used for clustering, optimization, statistical analysis, decomposition, random graph generation and calculation of network distances, flows, and ranking measures.
The developers of JUNG, in order to reduce the duplication of effort required for implementing certain functions that their software needed to perform, have used other, also platform-independent, Java libraries. Jung uses the following Java libraries:
Commons Collections (Apache Jakarta Project (2004)) library which enhances the basic Java API for collections of objects.
Colt (CERN (2004)) is a set of libraries for matrix algebra functions and generally for high-performance scientific and technical computing.
Xerces (Apache XML Project (2004)) is the common library, used for implementing the GraphML I/O capabilities, for XML parsing.

Building JUNG-based applications will require all of the above, plus the Java SDK (version 1.3 or later).
Except from the powerful JUNG API, there exist a number of other packages and tools for manipulating and visualizing network data such as the: Pajek (Batagelj and Mrva (2004)), the UCINET (Borgatti, Everett, and Freeman (2004)), the R (R Development Core Team (2004)) with sna (Butts (2004)), the NetMiner (Cyram Company, Ltd. (2004)), the MultiNet (Richards and Seary (2004)), the GFC (IBM Corporation (1999), the StOCNET (Boer, Huisman, Snijders, and Zeggelink (2003)), the Info Vis Cyberinfrastructure (Penumarthy, Mane, and Borner (2004)), the Info Vis (Fekete (2004)), the Visone (Brandes and Wagner (2003)), the Jgraph (Alder (2005)), The yFiles (yWorks (2004)) and the Boost (Siek, Lee, and Lumsdaine (2001)). []
Additionally, some extra open source projects for graph or network visualization written in Java are the: GiNY, HyperGraph, JDigraph, WilmaScope, JGraphT, TouchGraph, GVF, JgraphEd, VGJ, GUESS, Zoomgraph, Walrus, Prefuse, ZVTM, Large Graph Layout, NV2D, Otter, Gravisto, Linguine Maps, JIGGLE, Zest, Relo and SoNIA.
It should be reported that initially, the JGraphT software was selected for creating the GUI for the present project. JGraphT seems to be a simple and helpful software for creating graphical representations of network data, only if these data are already known. It does not seem to be appropriate for creating dynamic graphs. That was the reason why the powerful and flexible JUNG API was used in the end.
There is a long list of software projects that use JUNG for network data visualization. Some of them are listed here: Djinn (Fabien Benolt), RDF Gravity (Sunil Goyal, Rupert Westenthaler), GUESS (Eyatan Adar, David Feinberg), ADAPTNet (Michal Okoniewski, Tim Yates), Augur (Jon Froehlich), Ariadne (Cleidson de Souza et al.), Netsight (Yan-Biao Boey, Joshua O' Madadhain, Scott White, Padhraic Smyth), InfoVis CyberInfrastructure (Penumarthy, Mane, and Borner (2004)), PWComp (Joshua Adelman, Josh England, Alex Chen), Google Cartography (Richard Jones), GINY (Rowan Christmas), GraphExplore (Quanli Wang), TOTEM (Toolbox For Traffic Engineering Methods (S. Balon, O. Delcourt, J. Lepropre and F. Skivee), D2K (“Data to Knowledge”), graphBuilder (Ben Raymond), Semiophore, Xholon (Ken Webb), and Flink (Peter Mika). []
Additionally, there is another long list with papers and research projects that involve the JUNG software, which has been decided not to be mentioned. JUNG is a dynamically involving software and its second edition, called Jung 2.0, is currently in its alpha version. It is available to be downloaded from the Open Source Technology Group (SourceForge.net). In this point it is worthwhile to mention that during the first period of developing the GUI for the PDQ library, an effort has been made in order to implement the GUI using the newer second version of JUNG, instead of the 1.7.6. version. Using the second version of the software initially seemed to be an interesting challenge, since it is difficult to combine one quite under engineered software like PDQ with one like Jung2.0, which in its first sight looks quite over engineered. Finally, it was decided that the, very well done, 1.7.6 version could provide enough help to create a GUI for the Pretty Damn Quick library, since Jung2.0 is still in its alpha version and probably some changes will take place in the near future.

References
J O 'Madadhain, D Fisher, S White, Y Boey, “The JUNG (Java Universal Network/Graph) Framework”, (preprint by http://jung.sourceforge.net), 2007

Millennium Performance Problems and the contribution of the Jung API

2007-08-17T09:32:00.000-07:00

The first of the Millennium Performance Problems, as expressed by Neil J. Gunther, is the performance Visualization. The idea is to find alternative ways of representing performance data. The traditional reports which contain a set of tables with numbers and a variety of two dimensional diagrams, seem not to provide the expected help, when a special set of problems is involved. These are usually complex problems which need a special way of representation in order to become comprehensive from the human brain, and problems that demand a special analysis and solution methodology. Alternative ways of data representation should be considered which would take into account the new discoveries that have been made recently around the humans vision area of research, and generally around the way the human brain can perceive some certain types of information and knowledge. For this reason physicists and biologists use, and also are involved into, projects that have to do with animation and special GUIs, that are used to represent complex data in ways that could help their users to derive and solve problems easier. [Neil J. Gunther]
Thus, in order to achieve more effective representations of complex network data, several graphical analysis tools and frameworks have been developed to provide help to programmers and consultants. In this section, a quick reference to the several open source and freely available software projects, that have been developed for this purpose, will be made, and a short presentation of the Jung API capabilities, will be provided. But in order to complete the reference to the Millennium Performance Problems, it would be better to provide a short description of the other four remaining problems first, as expresses by Neil J. Gunther.
The second millennium performance problem has to do with the so called “Self-instrumented Applications”. It is well-known that object orientation logic has improved the way software is managed and organised. Primarily, this is achieved because in object orientated programming, code can be reused and maintained easier. The idea behind the self-instrumented applications is based on the same rationale, applied to the programmers or generally to the productive resources, themselves. These kind of objects should be then added to the object library as well. In this way, the performance analyst could have the ability to turn objects on and off selectively, achieving a more flexible and probably more efficient management, since paths to find bottlenecks through applications code, could be traced easier. Obviously, applying this logic could contribute to the analysis of production systems
The Von Neumann Bottleneck is the third millennium performance problem. Parallelism, is the technical term for doing more than one thing at once in order to achieve computational efficiency. In parallel computing centres, where supercomputers made either with clusters or with Grid computing techniques, the maximum efficiency for the system can be achieved if only a single thread is running in each of the processing units and this thread is not terminated until the end of the computation. Unfortunately to achieve practically something like that or to achieve general-purpose parallelism, seems to be an utopia for performance analysts, despite the intense effort that has been done over the last two decades. The paradigm of the human brain architecture has lead to the idea of using neural networks to achieve a higher degree of parallelism. Another idea is to construct quantum computers.
The fourth millennium performance problem as expressed by Neil J. Gunther has to do with the performance analysis of the Internet. Internet communication is based mostly on the concept of receiving and transmitting information coded as a packet of data. Internet packet analysis, which has taken place over the last fifteen years, showed that “long-term correlations can persist over several orders of magnitude in time” [Neil J. Gunther]. It is true that in the packet level, all the conventional queueing theory techniques are no longer valid. Packet arrivals don't follow the Poison distribution, while there are no constant service times. Thus the question is how the Internet could be modelled. A very challenging task could be the development of an Internet Simulator or a new theory for expressing complex systems of the same type.
The final millennium challenge for the performance analysts has to do with the performance analysis of Quantum Computers. The development of Quantum Computers may still sound like a science fiction story, but it is true that there have already been developed and used quantum communication devices for encryption. Maybe they are still very specialised and expensive but it is expected that during the following years, devices like those will be easier and cheaper to a be produced in a large scale. The question is how the wide use of this technology will affect performance. [Neil. J Gunther]
These five millennium performance problems, as they have been expressed by Neil J. Gunther, seem to reveal some interesting points about the upcoming challenges in the area of systems performance evaluation. The present project aims to perform a research and hopefully contribute to the first of these challenges. The visualization of complex data that have to do with the relations between distributed entities expressed as networks of data, and the analysis of the several ways that this can or already has been done, could be the subject of this project.

User Data in Jung

2007-08-17T09:19:00.000-07:00

There are two ways to associate data with graphs, edges or vertices.

1st. Class Extension, creating a class that extends one of the Graph, Vertice or Edge implementations.

2nd. Jung Annotation, using the existing built-in mechanism (the UserData class) for annotating graph elements with data. Several methods are used to manipulate these data.

I think that the first way is more appropriate for the needs of my project.

OverEngineering vs UnderEngineering

2007-08-15T15:07:00.000-07:00

It has fun when you are trying to combine one quite under engineered software like PDQ with one like Jung2, which produces very impressive graphic representations but, in its first sight looks quite over engineered. I decided that, the very well done, 1.7.6 could provide enough help to my project since Jung2.0 is still in its alpha version and probably some changes will take place in the near future.
leffe

Compiling a JUNG2 based code

2007-08-13T01:59:00.000-07:00

- Exception in thread "main" java.lang.NoClassDefFoundError: com/perfdynamics/pdq/examples/ClosedPassport

*/ Probably something is wrong with the classpath

- The type javax.vecmath.Point3f cannot be resolved. It is indirectly
referenced from required .class files

- Could not instantiate class, error in the constructor

The Millennium Performance Problems

2007-08-11T02:38:00.000-07:00

The Millennium Performance Problems are:

1. Performance Visualization:
The idea here is to find ways of representing performance data that are a better impedance match for our cognitive computer (our brain). One role model is the techniques used in so-called Scientific Visualization where physicists and biologists have learned to use things like special GUIs and animation to represent complex data in ways that help them solve problems. Why should they have all the fun?

2. Self-instrumented Applications:
Object-oriented programming has been promoted as a good thing primarily for reasons of reusability. If people are going to re-use objects, how about they come with their own instrumentation? This really should be part of the object library so that a programmer need nevre be concerned with adding such code. Then I, as the performance analyst would have the ability to turn objects on selectively and thereby trace paths through application code to find bottlenecks, even on production systems.

3. The Von Neummann Bottleneck:
An efficient way to compute something on a machine is to do more than one thing at once. The technical term is parallelism. Unfortunately, despite a lot of intense effort over the last two decades, general-purpose parallelism remains a holy grail of performance analysis. One reason for this barrier seems to stem from the influential success of early electronic computer designers such as Alan Turing and John von Neumann. The fundamental paradigm of sequential programming and operation seem to be almost impossible to break away from in the modern digital computer. But there is an obvious role model for a non-von computer architecture: our brain. This has led to the idea neural networks as way of achieving a higher degree of parallelism. Quantum computers are another.

4. Performance Analysis of the Internet:
The results of analyzing Internet packet traces 15 years ago at Bellcore (now Lucent) showed that long-term correlations can persist over several orders of magnitude in time. Packet arrivals are not Poisson, and service times are not constant. In other words, all the conventional queueing theory techniques near and dear to our hearts as performance analysts, are no longer valid at the packet level. How are we to model the Internet? Perhaps we need to think big. The climatologists use things like the Earth Simulator to address complex questions about global warming. Maybe we need an Internet Simulator of similar scale?

5. Performance Analysis of Quantum Computers:
Quantum Computers are probably a long way off, but quantum communication devices are already here. The only reason you are not aware of them is because they are expensive and therefore a specialty item for institutions like banks. In the next 3 to 5 years, I believe these things will reach commodity prices and will therefore become more ubiquitous. I am also working on these technologies now. The question for us is, How will they affect performance?

CMG Materials

JGraphT

2007-08-10T17:55:00.001-07:00

- JGraphT supports various types of graphs including: directed and undirected graphs, graphs with weighted / unweighted / labeled or any user-defined edges, various edge multiplicity options, including: simple-graphs, multigraphs, pseudographs, unmodifiable graphs - allow modules to provide "read-only" access to internal graphs, listenable graphs - allow external listeners to track modification events, subgraphs graphs that are auto-updating subgraph views on other graphs and all compositions of mentioned graphs. Powerful, but simple.

JUNG

2007-08-10T15:39:00.001-07:00

- JUNG — the Java Universal Network/Graph Framework--is a software library that provides a common and extendible language for the modeling, analysis, and visualization of data that can be represented as a graph or network. The JUNG architecture is designed to support a variety of representations of entities and their relations, such as directed and undirected graphs, multi-modal graphs, graphs with parallel edges, and hypergraphs. It provides a mechanism for annotating graphs, entities, and relations with metadata. The current distribution of JUNG includes implementations of a number of algorithms from graph theory, data mining, and social network analysis, such as routines for clustering, decomposition, optimization, random graph generation, statistical analysis, and calculation of network distances, flows, and importance measures (centrality, PageRank, HITS, etc.). Comprehensive, everything but the kitchen sink!

In order to run a JUNG-based application, you will need all the packages listed on the JUNG download page. (As of this writing, this includes .jar files for JUNG, version 1.3 (or later) of a Java runtime environment (JRE), Apache Jakarta commons-collections, the CERN Colt scientific library, and Xerces.

Building JUNG-based applications will require all of the above, plus the Java SDK (version 1.3 or later).

jung

Check here for more open source graph network visual tools in Java ;-)
http://www.manageability.org/blog/stuff/open-source-graph-network-visualization-in-java/view

Algorithm for calculating the Time Share Ratio between the Queues

2007-08-10T03:35:00.000-07:00

v(j) = Σv(i)p(i→j)

p(i→j) = probability for the Job (Workload) to leave Queue (Node) i and go to j

in order to make the calculation, firstly one of the v(i) should be considered =1, (v(i) = 1)

Potential GUI Approach for the existing PDQ Java version

2007-08-08T14:26:00.000-07:00

As I've mentioned before, I believe that in order to develop a correct, in matters of software engineering, software tool with a fully functional GUI, and potentials for further development, it is essential to perform some refactoring to the already existing Java code.
On the other hand, if the only purpose is to develop a GUI based just on the already existing code with just the current functionality, an approach could be:
- Initially represent graphically a queueing model with Nodes(Queues) and Arcs with parameters,
- keep the information and parameters into some additional memory structures (ArryList/Hashmap),
- perform a validation, and after the visually defined model is valid,
- export the buffered parameters of the visual model into the actual PDQ model and then
- solve it using the PDQ_solve(). After that
- take the results using the appropriate "PDQ_get" functions and
- represent them graphically, using some external of the PDQ library functions again.

Having this approach, in the case that a queueing model has defined, then validated and finaly solved, if the user would like to change just one parameter of the model then after the first execution of the MVA algorithm the pdq model should be deleted (actually calling the PDQ_Init()) and then recreated from the beginning since no changes can be done to an already defined PDQ model.
This approach doesn't extend the functionality of the existing PDQ library. It just creates a visual shell, which gives the impression that the PDQ tool is more high level.

braju.jar

2007-08-08T14:00:00.001-07:00

Why braju.jar?

An additional quite old library called "braju" is used from the PDQ library. In contrast with the PDQ library, the braju library is not open source (it is freely available though). This library is commonly used in order to represent the C - like functions: fprintf(), printf() and sprintf() in Java. I don't really understand what is the purpose of using this package in the Java PDQ implementation. I suppose that the only purpose of doing this is to create an as much as relevant and close to the C version, PDQ Java code version.

The API of the Package com.braju.format contains:

Class Summary
Format: This class provides static C-style methods like sprintf(), printf() and fprintf() with variable number of parameters.
Parameters: This class makes it possible to simulate parameter lists to method with arbitrary length.
ParametersAutoClear: This class is an empty class with no extra methods.

Exception Summary
ParseErrorException: Exception thrown when there is an unexpected character or a syntax error in the format string passed to a *printf method.

It is possible that refactoring just the pdq.jar open source code, is going to be enough for creating the demanded functionality of the library, but I can not be sure about it. The truth is that even if it is feasible, an additional effort will be required in order to learn how the braju.jar library works if I still want to use it, but probably, in the case of refactoring, its use is going to be redundant.

Sofware Engineering Issues

2007-08-03T11:36:00.000-07:00

In my mind I had two potential approaches for developing the Graphical Queueing Networks Analysis Tool:

1. Just use the library as it is (don't change the functionality).
Ignore the details of the implementation of the PDQ software, and focus on the functionality. In other words, just use the functionality PDQ API provides, mostly just using the PDQ class which can be pretty much enough, in order to define models. Decipher how this can be done through the several examples and the PDQ users manual. Try to automate the modeling procedure and then represent the required code visually creating classes - elements of a GUI.

2. Develop the API (add more functionality) after studying its code.
Understand thoroughly not only the way PDQ API can be used in order to define Queueing networks models (probably using examples and the manual), but also the several details of the software implementation. Which are the attributes and functions each of the classes of the API provide? Which of these classes should be expanded and how? What kind of functions should be added in order create a higher level of the library and after that a GUI? This is essential because of Software Engineering reasons. Do I just need to create a GUI for an already complete API or I need to expand the functionality of the PDQ API as well, adding more attributes and methods?

I think that the second approach is the only rational approach cause the PDQ API is really very low level. Thus re-engineering is essential, otherwise the result will be a clumsy, non-functional GUI, based only on the already existing functionality of the library.

Some of the PDQ library functions are grouped here in order of most frequent invocation:
PDQ_Init() Initializes all internal PDQ variables. Must be called prior to any other PDQ function.
PDQ_CreateOpen() Defines the characteristics of a workload in an open-circuit queueing model.
PDQ_CreateClosed() Defines the characteristics of a workload in a closed-circuit queueing model.
PDQ_CreateNode() Defines a single queueing-center in either a closed or open circuit queueing model.
PDQ_SetDemand() Defines the service demand of a specific workload at a specified node.
PDQ_SetVisits() Define the service demand in terms of the service time and visit count.
PDQ_SetDebug() enables diagnostic printout of PDQ internal variables.
PDQ_Solve() The solution method must be passed as an argument.
PDQ_GetResponse() Returns the system response time for the specified workload.
PDQ_GetThruput() Returns the system throughput for the specified workload.
PDQ_GetUtilization() Returns the utilization of the designated queueing node by the specified workload.
PDQ_Report() Generates a formatted report containing system, and node level performance measures.

- It seems that there are no implemented methods for deleting Nodes and Workloads in the PDQ class. PDQ_RemoveNode(), PDQ_RemoveClosed(), etc.

- Nodes and Workloads can only be created. Then they are stored in a simple static array structure defined in the PDQ class.

- Should I create a subclass of the PDQ class called eg. class ThePDQ expands PDQ {}, which implements these required methods?

- Should I create a subclass of the Node class called eg class TheNode expands PDQ {}, which gives more attributes to the Node Object, such as displayed Image as well as complementary methods for manipulating the behavior of a Node such as a method that calculates automatically the Demand of this Node?

- Should I do something similar and create an additional Workload() class?

- What about the Arc() class? Which are the attributes of this about-to-be implemented class? How the Arcs that join the several Nodes should behave? Should this potential Arc() class expand some other relative class of the PDQ API?

- Which other classes should be expanded in order to have a coherent set of classes and methods?

- Apparently, the existing Java version of the PDQ library can be considered under-engineered. How can I avoid this and how can I avoid potential over-engineering as well? Is it preferable instead of expanding one class, just to develop a separate class in which an instance of the about to be expanded class is created?

New Challenges For The Professional Modellers and the Systems Modelling Methodology: Grid Computing

2007-08-02T17:00:00.000-07:00

Professional modellers deal with a variety of real problems and their main objective is to “translate” each of these problems into a strict mathematical form. In order to achieve something like that, several stages of the modelling process should be preceded. Initially, all the aspects of the problem should be clarified, and then the several variables of the problem should be identified. Finally the modeller should be able to estimate and approximate a set of courses of action that may cost money and time. It is a very important skill for the modeller to be able to identify the critical parts of a problem in order to create an optimised, abstract version, which constitutes the mathematical model of the problem. Generally, any model can be defined as a simplified representation of certain aspects, preferably the most important, of a real system. A mathematical model can be defined as a model which is created using several mathematical concepts such as functions and equations.
It should never be forgotten the fact that modelling, compared to simulation, is usually a less accurate but faster methodology for estimating the behaviour of a system, and that the main purpose of using this methodology is its high performance. Additionally, it is essential to underline, for one more time, the role of systems modelling in industry and business. Optimising the procedures of decision making and systems performance evaluation, a significant competitive advantage in matters of time and money may be gained for the company. A not so naïve observer could possibly identify a gap between the reasoning required for creating a mathematical principle, and this required for creating a mathematical model. It is true that mathematical principles are based on sound reasoning and development but, when we come to model a given real problem, we must feel free to construct the model using whatever mathematical relationships and techniques seem appropriate. In the case of creating a mathematical model, nothing can be considered as totally true or totally false and there are always several ways in which a model of a real problem can be created. [1]
Moreover, new achievements in the area of distributed and parallel computing systems have raised the need for developing models and modelling mechanisms, that can evaluate effectively the behaviour of highly complex systems, such as supercomputers, which have been created using clusters or idle desktop computers connected to the Internet. The second method of creating a supercomputer is based on the principles and the technology that define the term Grid Computing. Using the computational power of idle non-dedicated desktop machines that are connected in the Internet reveals another, more modern, approach to the way supercomputers can be created. This methodology called cycle-scavenging, which is based on volunteer computing, is currently used effectively to projects like BOINC, which was initially developed to support the SETI@home computationally intensive project. SETI was aiming to detect intelligent life outside Earth, after analysing a large amount of data coming from a telescope. There are several freely available technologies, which have been developed around the idea of Grid Computing. Distributed Resource Management Application API (DRMAA) is a high level specification API, provided by the Global Grid Forum (GGF). which is a community which aims to standardise Grid Computing globally. DRMAA tries to specify the way in which the several jobs, within one or more Distributed Resource Management (DRM) systems, are submitted and controlled. “Condor” is a popular open source software framework for course-grained distributed parallelization of computationally intensive tasks. It is commonly used to manage workload on a dedicated cluster of machines or on a Grid of idle non-dedicated desktop computers connected to the Internet. Alternative and complementary frameworks are the Cactus Grid Project and the Sun Grid Engine. Some other popular open source software middlewares for building computing grids are the “Globus Toolkit”, and the “Parallel Virtual Machine” (PVM). OGSA (Open Grid Service Architecture) describes an architecture for grid computing environment, based around services, developed within the GGF (Global Grid Forum) for scientific and business use. It actually constitutes a distributed interaction and computing architecture which assures interoperability on heterogeneous systems, so that different types of resources can communicate and share information in order to provide several services. There are several other applications and middlewares created to support the Grid Computing technology, while additionally several low or higher level APIs have been developed such as the “Message Passing Interface” (MPI) which is used for non-shared memory programming (computer clusters) , the OpenMP API used for shared memory multiprocessing programming, and the most recent “Simple API for Grid Applications” (SAGA), which is an open standard that describes an interface for high level Grid applications programming. Additionally, combining the MPI and OpenMP technologies, several other hybrids have been developed, by different distributors, in a variety of supported programming languages. The main objectives of these technologies are: high performance, scalability and portability. Parallel, multiprocessing programming in a lower level, is based on the use of threads (eg. POSIX Threads), and a key task for achieving maximum efficiency in shared memory parallel architectures is to both use exactly one thread per processor and keep these threads running during the whole lifetime of the parallel program. There are several techniques that can optimise this procedure. Additionally, the most popular and supportive languages for parallel programming are C/C++ and Fortran. Java programming language assures portability, ease of software engineering, automatic garbage collection (using the finalize() method), thorough type checking and absence of pointers. These attributes make Java development less error prone. On the other hand there are some characteristics that make the Java programming language inappropriate for parallel systems programming such as lower performance because of slower compilers, lack of support for complex numbers and multidimensional arrays, lack of suitable standards for parallel programming (no standardised interface for MPI / OpenMP), and problems using native Java Threads instead of a directive system (OpenMP). However there are some efforts to create specifications using OpenMP-like directives, in order to standardise somehow the parallel programming with Java. Similar efforts have been done for other languages as well, such as Perl and Python.
To sum up, having as a task to evaluate the behaviour of a highly complex system, such as a supercomputer, can be very demanding. This is another challenge for professional system modellers. Taking into account the recent evolution in the area of supercomputers, several questions can be derived. Which is the way, and what kind of tools could be developed and used in order to help modellers, to evaluate and optimise modern, large-scale systems, such as projects based on Grid Computing technology? How could the Queueing Networks be used in order to model and evaluate the quite complex procedures taking place within a multi-platform, shared memory (or not), multiprocessing environment. Although the low level technology and middlewares related to the Grid computing have been already matured, there are not many high level Grid applications created yet. This lack of experience in the particular field, makes the Grid computing systems modelling and evaluation even more demanding and challenging.

Reference
[1] Edwards & Hamson, “Guide Mathematical Modelling”, Palgrave 2001.

Eclipse has the problem not the PDQ library

2007-07-27T04:24:00.000-07:00

http://dev.eclipse.org/newslists/news.eclipse.newcomer/msg02312.html

Problem: PDQ Java distribution is not compatible with Java 6?

2007-07-26T11:57:00.000-07:00

These 3 kind of errors occur during the compile of the API:

Severity and Description Path Resource Location Creation Time Id

The method printf(String, Object[]) in the type PrintStream is not applicable for the arguments (String, Parameters) Thesis/src/com/perfdynamics/pdq MVA.java line 432 1185383257573 64

The method printf(String, Object[]) in the type PrintStream is not applicable for the arguments (String, String) Thesis/src/com/perfdynamics/pdq PDQ.java line 381 1185383257470 51

The method printf(String, Object[]) in the type PrintStream is not applicable for the arguments (String) Thesis/src/com/perfdynamics/pdq PDQ.java line 379 1185383257470 50

I should try to backdate the java version to 5.

Notes for Observational/Operational Laws

2007-07-10T06:01:00.000-07:00

A = number of arrivals at the queueing center
C = number of completions departing the queueing center
T = Measurement or observation period
B = Total time the system was busy during T

arrival rate: lamda = A/T

throughput: X = C/T

mean service time: S = B/C

utilization: U = B/T (it is actually a special case of Little's Law)

Little's LAW: Q = lamda x R (or L=AW)
Q: average queue length
R: average residence time spent at the center (time waiting in line + service time)

Constrains

2007-07-09T13:41:00.000-07:00

- no blocking mechanisms involved.
- this means that only nodes with infinite servers (delay centers), or nodes with infinite capacity servers are going to be used.

PROJECT DESCRIPTION

2007-05-27T13:38:00.000-07:00

Introduction

Queueing Network Modelling and Analysis is the subject of this proposed project. Nowadays, the need for tools and techniques that assist in understanding the behaviour of the even more complex, modern systems has become essential. Additionally, it is very important for these tools and techniques to provide results quickly, even if they are less accurate. These needs have encouraged the idea of modelling, rather than simulating, the behaviour of one system. Thus, a more abstract model, which contains only the most significant elements of the real system, is preferable to a more accurate but inflexible and costly one.
In the Queueing Network Modelling approach, the system is represented as a network of queues. A network of queues is a collection of queueing nodes (service centres) that represent resources of the system, and workload (customers) that represent transactions or users of the services that are provided by the system. After the model of the queueing network is created, it can be evaluated analytically using a combination of algorithmic and numerical procedures. Specialised software is commonly used to solve efficiently a set of equations that have been derived from the queueing network and its properties. For the needs of this project, an open source library, called PDQ, will be used to define the parameters and solve the user-defined queueing network.

Project Description

The proposed project constitutes a Graphical Analysis Tool for Closed Queueing Networks. Its purpose is to analyse a large variety of general closed queueing networks. Actually the mathematical algorithms that represent and solve queueing networks are already provided by an open source, freely distributed software called pretty damn quick PDQ. This software constitutes a considerable low level implementation of a set of functions, originally written in C programming language, that can be used to define the properties of a queueing network and then solve it. The solution is derived after applying one appropriate version of the powerful Mean Value Analysis (MVA) algorithm to the previously defined model.

Features related to the GUI
The rationale of undertaking this project is summarised to the need of creating a user friendly tool set, which will provide a more high level approach to the existing low level PDQ software. Users that are not familiar with the API of the PDQ library, should be able to make use of the capabilities of this powerful tool in a simple and straightforward way, using the features that the GUI of the proposed client, will provide. In this point it is worthwhile to mention that the purpose of this tool will be mostly educational, rather than strictly scientific or commercial. Thus, it is a primary goal to be user-oriented and minimalistic.

Basic requirements of the potential user-friendly Graphical User Interface are presented below:
The GUI should allow the creation of queueing networks using drag and drop elements in an adjustable design area. Queues and the way they are connected should be represented graphically, using icons and other design elements like forks and arrows. Generally, a simple and comprehensive visual representation of the queueing network should be encouraged by the program.
Clicking on each inserted queue should provide a menu, or a dialogue window, which will show the properties of the queue. if this action takes place during the definition of the model (before the execution), the shown parameters are going to be editable by the user. In an already solved queueing network, the indicated properties should demonstrate the execution results that the program has produced for the specific queueing node. Alternative ways of demonstrating queueing parameters and properties of the queueing network, should be also available (e.g. by selecting an option from the general application menu bar).
A control algorithm should be developed which will identify if the designed representation of the model constitutes a closed queueing network. This tool will be able to handle only closed queueing circuits. Generally additional methods should be implemented, which will indicate errors in the design of the queueing network. Additionally, if an error occurs during the design process, descriptive error messages should be generated.
The creation and modification of a queueing model should be flexible and easy. The need to implement “add/delete element” options is essential, while additional element handling options could be created, to enhance flexibility and user's control when creating or modifying a queueing circuit.
The output after solving the queuing model should be presented graphically to the user. Different indicative colours for each queue can be used, as well as plots and diagrams. The support of printable reports, with all the details of the model and its solution, is also a good additional feature. Moreover, analysis results should be printed into files for keeping data records.
Finally, constructed queueing networks should be able to be saved, while previously saved networks should be able to open.

Features of the proposed tool:
Some of the basic technical characteristics, related to the function of the proposed software are presented below:
Only closed queueing networks will be supported.
The capacity of each queue could be finite or infinite.
Single as well as multiple classes of workload will be able to be supported (actually up to 2 types of class workload are going to be available, one with zero think-time and one with nonzero think-time).
For finite capacity queues, a wide range of blocking mechanisms should be handled.
For networks of infinite capacity queues, multiple workload classes should be able to be handled, and for a single class of workload, fork or joined nodes should be able to be handled.

More specifically the Queueing Networks analysed by the tool can potentially be:

Closed networks of multi-server infinite capacity queues with multiple workload classes.
Closed networks of multi-server infinite capacity queues with a single workload class, with fork/join nodes, and with/without synchronizing queue.
Closed networks of multi-server finite or infinite capacity queues with a single workload class and with transfer blocking.
Closed networks of multi-server finite or infinite capacity queues with a single workload class and with repetitive service blocking.

Additional requirements:
Additional requirement for the proposed program is to be available for a big variety of computer systems. The property of this requirement will to be accomplished by implementing the above software in a platform independent programming language, such as Java. The version of Java release, which is intended to be used for the needs of developing this software, is the recent Java 6 version. The GUI will be probably created using the well-known AWT and SWING APIs included in every Java version. The system requirements for executing the developed software are expected to be low, but it depends to the size and the complexity of the defined model.

Summary

To sum up this report is intended to provide a general description of the project. It demonstrates the rationale and the significance of undertaking a project like that as well as the user requirements. Its purpose is to indicate what work will be conducted in pursuit of meeting the aims and objectives of the project. Finally it demonstrates a basic set of features, that the intended created software should include, indicating significant aspects of the project.

AIMS & OBJECTIVES

2007-05-27T10:32:00.001-07:00

Aims & Objectives

Aim of this project is to provide a general tool set with a GUI, which will allow the user to specify models of closed queueing networks in a simple and efficient way, using simple graphical "drag and drop" elements and flexible correcting and designing tools.
The defined problem should be solved using the “Pretty Damn Quick” (PDQ) library, which is a free open source software. Actually, an objective is to create a tool set, which will provide a more high level approach to the existing low level PDQ software, hiding the mathematical details as much as possible. Users that are not familiar with the underlined API, should be able to make use of the PDQ library capabilities in a simple and straightforward way, through the designed GUI of the software tool.
Additionally, the output of the program should demonstrate the results in a comprehensive way, that does not demand detailed knowledge of the underlined mathematical model from the user. The solution should be represented in a graphical way as well (plot diagrams, colour use, etc.). In this point it should be declared that the purpose of this tool is mostly educational rather than commercial.
Additional objective is to investigate the possibly different existing approaches in designing an interface, for representing closed queuing network models, then analyse the alternatives, and finally select one of these approaches or propose a new approach, explaining the rationale and the reasons of choosing this design approach.

LITERATURE REVIEW

2007-05-26T06:39:00.001-07:00

Literature Review

1.Introduction

Day by day the need for taking decisions, and performing tasks in a correct way and within tight time constrains, is becoming more and more essential. Today's real time systems are demanded to be effective and quick. An important performance factor, that may be the key to the success of a system implementation, is the system's throughput. Different approaches have been suggested for increasing system's performance. [23]
Additionally, the need for creating effective tools that can perform system performance evaluation (for measuring and optimising system's throughput, for example) has become more essential than ever. There are three approaches to the performance evaluation of computer and communication systems: Benchmarking, Simulation, and Analytical Modelling. The third one, is the most significant for the purposes of this project, and its idea is to construct, via a combination of algorithmic and numerical procedures, a mathematical model of the system. Commonly, the system resources are represented as a queueing network.
The mathematical study of queues, known as Queueing Theory, provides the appropriate background for developing several algorithms that solve queueing networks. Some of the well known algorithms are the Convolution and the Mean Value Analysis algorithm. As soon as the model has been constructed, it can be solved using one of the several computational algorithms. Probability Theory and Stochastic Processes constitute the relevant mathematical background for comprehending the mechanisms behind these computational algorithms.
Several performance modelling software tools have been developed to provide help to the system analyser, in order to define the model of the system and interpret the results, in an effective and comprehensive way. The accuracy of each of these tools is depended on the computational algorithms it uses and the type of the problem it solves. Usually, different computational algorithms, solve a specific class of problems in an effective way.
Pretty Damn Quick (PDQ) is an open source software, originally written in C, which solves queueing networks in an effective way. It is free, and the aim of this proposed dissertation is to create a toolkit with a GUI based on the functions of this library, for computer system performance evaluation.
This literature review aims to provide information about what knowledge and ideas have been established on a the topic of queueing networks and system performance analysis, and what their strengths and weaknesses are.

2.Performance Modelling

High-speed networking, which has been recently developed placed in a demanding business market, has resulted into changing the approach of performance analysis techniques applied to a system. Simple models, even if less precise, are preferred of complex and more accurate models, . A more modern approach compared to simulation is to create simple and easier to define models -even if less precise-, rather than complex and more accurate, because decisions are expected to be taken up right away so the answers to problems should not take too long to be formed. [15]

In 1990 Tehany A. Fergany and Howard A. Sholl, in their paper under the title: "Performance-Based Multiple Server Support for Distributed Real-Time Applications” [23], present two different solutions for the problem of having a heavily requested computation, or, another characteristic that may effect the performance of a system, which is the occurrence of a demanding subtask which requires long service time. A pipeline subtask decomposition is used in the first approach, while in the second approach is used a set of parallel servers. The analysis of the system is performed using a queuing model. This paper constitutes a representative application of the relevant to the dissertation topic, and demonstrates how queuing theory can be applied to system analysis.

Neil J. Gunther, in his book "The Practical Performance Analyst, Performance-By-Design Techniques For Distributed Systems" (McGraw-Hill, 1998) [15], presents in a simple and understandable way the main ideas of queuing theory (single and multi server queues, finite and infinite source queues, Markovian and non-Markovian models), including examples and sampling programs in a disk. The software in which the book is referred to is the same that is going to be used for the implementation of the dissertation project except from the fact that this version (it is the first one) of the PDQ library has been written in C, while the implementation makes use of the more recent Java version of the software. Pretty Damn Quick (PDQ) software library is presented in an Appendix in the end of the book. This book is highly associated to the library, so it constitutes the basic guide for the programmer who wants to create, using the PDQ open source software.

The high cost of designing and developing a system and the even higher cost of modifying or redesigning the system, when the requirements have failed to be met, has led to different approaches in systems' performance modelling and measurement. There are three approaches to the performance modelling of computer and communication systems:
The first approach, known as “benchmarking”, suggests that the system first can be built, then modified and finally measured. This approach has the advantage that "performance estimate is perfectly accurate" [19], which means that there have not been introduced any errors that are not in the real system as well, since the whole procedure is based on the real system. The disadvantages of this approach is its high cost, its inflexibility, and the fact that it is particularly time consuming.
The second common approach is simulation. The idea of this approach is to build a simulation model of the system, which can be validated against the already existing system. After the validation several needed modifications can be indicated and applied. This approach permits an arbitrary level of detail to be included, this fact has the benefit that any system feature can be included and checked making the model more and more precise. On the other hand there is the danger to include too many features (which are not so essential for the performance of the required system) of the real system to the simulation, increasing, in this way, the complexity and the cost of applying the methodology.
Finally, the third, and the most significant for the purposes of this project, approach is called “analytic modelling”, and its idea is to construct a mathematical model (via a combination of algorithmic and numerical procedures) of the system and then perform validation, as in simulation. The benefit of this method is that the model is constructed much faster, the solution is calculated much faster than in simulation or benchmarking, and the fact that it provides a significant estimation of the behaviour of the potential system without first implementing it. Thus it is a much cheaper technique. [19]

The potential system analyst need to have the basic modelling, simulation, and analysis background in order to understand performance terminology and the various analysis techniques such as statistics, probability theory, experimental design, and queuing theory. The potential system analyst need to know how to use queuing or simulation models, how to combine skills (applying techniques of measurement and modelling) to solve queuing problems and how to interpret the results.
The book “The Art of Computer Systems Performance Analysis” by Raj Jain focuses on the above needs and it is mostly practical than queuing theoretic. It suggests that "in practice, one needs to use both measurements as well as modelling techniques to solve performance problems" [21], and both aspects of the field are thoroughly demonstrated.

Moreover, an additional book in the area of computer system performance evaluation, called “Introduction to Computer System Performance Evaluation”, by K. Kant, provides fundamental techniques and algorithms, covering both the theory and practice, emphasising analytic modelling methodology. This book constitutes a basic guide for someone who wants to explore the field of performance evaluation, providing examples and exercises, that are very helpful for establishing a firm background, both theoretical and practical, in the area. The view of the author suggests the analytic modelling methodology, as more appropriate for evaluating computer systems' performance, compared to measurement and simulation methodologies. [8]

3.Queueing Theory

Queueing Theory could be defined as the mathematical study of waiting lines (queues), and it is generally considered a branch of “operations research” because the outcomes of the theory are applicable to make business decisions about the resources needed to provide service. It can be applied in several fields such as engineering, industry, business, commerce and systems' performance evaluation.
Queuing network analysis technique is used widely to estimate the performance of systems. Firstly, the process that is about to be investigated should in some way be modelled in queues. After this is applicable, this analysis method can help to design, gain experience about and optimize the process. “The main idea of this theory is to describe the system with interconnected queues and servers. Of course, for large systems the representing queuing model becomes rather large as well”. [12]

Queuing Networks and Markov Chains are commonly used for the performance and reliability evaluation of computer, communication and manufacturing systems. [7]
The book “Queuing Networks and Markov Chains” aims to offer a detailed treatment of queuing systems, queuing networks and continues and discrete Markov chains. It provides in depth numerical solution algorithms and a set of examples. It discusses stochastic Petri nets, solution of Markov Chains. Additionally, it describes and applies 4 software packages (PEPSY, SPNP, MOSES, SHARPE) and also provides problems as exercises. This content of the book, makes it an appropriate guide for someone who wants to investigate the area of queueing networks and Markov Chains in theory and the applications of these concepts using the 4 suggested software packages. [7]

Mathematical Background (Probability theory, Stochastic processes)

Moreover, in order to understand someone how the derived algorithms and methodologies related to queueing networks and Markov Chains are applied in systems' performance evaluation, it is essential a relevant mathematical background of Probability Theory and Stochastic Processes to be provided. There are several books in the literature that provide this demanded fundamental background such as, the first chapters of “Computer and Communication Systems Performance Modelling” by Peter J. B. King [18] and the first chapters of the book “Queueing Networks and Markov Chains” by Gunter Bolch, Stefan Greiner, Hermann de Meer, and Kishor S. Trivedi [7]. Additionally, the appendices of the book “Queuing Networks” by Xiouli Chao, Maskiyo Miyazawa and Michael Pinedo [27] provide the fundamental ideas of Probability Theory, Stochastic processes, and Markov and Poisson processes .

Queueing Networks (M/M/1, M/G/1, M/M/c, M/M/%)

After this mathematical background is established the contents of queueing networks should be investigated. There are several types of queues, and of different complexities. Basically, there is the discrimination between the single server and the multi server queueing networks. Simple queues (M/M/1), and more complex queues like M/G/1, M/M/c, and M/M/∞ are analytically presented in the book “Introduction to Queueing Networks” by Erol Gelenbe and Guy Pujolle [6]. This book also provides some very useful application examples, of the theoretically described content of queues, in the end of every chapter. In this way the practical significance of the underlined queueing concepts are derived. More advanced types of queues are described in the book “Queuing Networks” by Xiouli Chao, Maskiyo Miyazawa and Michael Pinedo [27], but the focus of this book is mainly theoretical than practical. A specialised book devoted to product-form results for queueing networks is: “Queueing Networks and Product Forms” by Nico M. van Dijk, which provides a more tight to the product forms context, revealing aspects that the queueing networks can be applied.
Additional book in the area of Queueing Theory is an edition that constitutes a collection of papers published from 1952 to 1983. This collection is particularly interesting because it indicates the process during which the queueing theory has evolved from a new mathematical study to a mature one. [11]

Computational Algorithms

There are several computational algorithms that solve queueing problems, which have been proposed by different scientists during times. These algorithms make use of the mathematical concepts around the area of queueing theory, in order to solve models of systems, which have been represented by queueing networks. The literature around these algorithms and their transformations is vast, so only few of them are presented in this literature review.

In 1983 Charles H. Sauer working for IBM, has developed the two most important computational algorithms for State Dependent Queueing Networks. Convolution and MVA (Mean Value Analysis). In his paper he demonstrated that they are both of equal generality, contrary to common belief. [3]

A new approach using Mean Value Analysis for polling systems in heavy traffic is presented in the homonym paper of R. D. van der Mei and E. M. M. Winands, published in 2006, which provides (including numerical examples) a demonstration of “results that reveal a number of insensitivity properties of the covariances with respect to the system parameters under heavy traffic assumptions, and moreover, lead to simple approximations for the covariances between the successive visit times for stable systems”. [22]

Another algorithm for computing the mean performance measures of product-form multiple-chain closed queuing networks, called Recursion by Chain Algorithm (RECAL) is presented in a paper A. E. Conway and N. D. Georganas have published in 1989, with title “RECAL – A New Efficient Algorithm for the Exact Analysis of Multiple- Chain Closed Queuing Networks”. in this paper it is indicated that this algorithm is more efficient than the convolution or MVA algorithms, when the network contains many routing chains. [1]

For soft real-time scheduling, an approximate analysis of the Shortest Queue Policy (JSQ) is developed and presented in a paper of Weiping Zhu. This study compares the results produced after applying the JSQ policy to soft real-time systems, with the results of the simulation. The paper indicates that the approximate analysis produces highly accurate results. [25]

An algorithm applied to closed product-form multiclass networks has been proposed by Wu-Lin and Colm Art O' Cinneide in 1998. It is actually a Markov Chain, Monte Carlo method for class throughputs, which simplifies the original network producing a network with a simpler structure, which is then simulated and solved. This method is supposed to perform well in a broad range of problems. [26]

There is vast literature on TCP modelling. Indicatively, an algorithm, for closed queueing network models of interacting long- lived TCP flows, is demonstrated by Michele Garetto. In his paper a new analytical model which estimates the performance of TCP connections is presented and compared against detailed simulation experiments. The numerical results show that the model estimates performance variables in an accurate way in all situations. [13]

A multi-thread memory scheduler that targets high performance chip multiprocessors is proposed and evaluated in the paper of Kyle j. Nesbit, Nidhi Aggarwal, James Laudon, and James E. Smith called “Fair Queuing Memory Systems”. The algorithm which is proposed is fair and provides Quality of Service (QoS) and improves system performance as well. This is an interesting applied example in the area of hardware development. [9]

Finally a series of computational algorithms for product form queueing networks are presented by Peter J. B. King in the book “Computer and Communication Systems Performance Modelling”, including the Convolution algorithm, MVA, LBANC, and RECAL algorithm. [19]

4.Existing Tools in the area

The increased complexity of modern systems has made the development of performance analysis tools very essential. The existing tools usually have a graphical user interface (GUI) or a special input language or both. in some cases it is difficult to acquire system measurements so the development of a system's model is an effective method of performance assessment. [7]

The solution methods that are usually provided by performance modelling software tools are:
DES (Discrete-event simulation).
CTMC and DTMC (generation of the state space and solution).
Exact/Approximate solution of product-form queueing networks (for example MVA, SCAT and Convolution algorithms).
Approximate solution of non-product-form queueing networks.
Hierarchical models (multiple levels) that combine one or more of the above methods.

For accurate description of system behaviour, the DES is used, but this method increases the computation time and the resource needs. Thus less accurate methods, related to queueing networks and Markov chain analysis, are preferred. When the approximation methods can not be applied to certain problems or when they are not accurate enough, DES or CTMC is used. Nowadays, the computational power has increased significantly as well as the effectiveness of the algorithms. Thus, the CTMC approach has started gaining more and more importance. [7]
The 12th chapter of the book written by Gunter Bolch, Stefan Greiner, Hermann de Meer, and Kishor S. Trivedi, "Queuing Networks and Markov Chains (Modeling and Performance Evaluation with Computer Science Applications)" introduces four representative performance modelling and analysis tools: PEPSY, SPNP, MOSES and SHARPE. [7]

An interesting compilation of papers related to performance engineering methods, which includes 6 tool presentations has published in 2002, after the 12th International Conference called TOOLS 2002. Between these tools, the most relative to the purposes of the proposed project are: “The ProC/B Toolset for the Modelling and Analysis of Process Chains”, “PRISM: Probabilistic Symbolic Model Checker”, “MAMSolver: A Matrix Analytic Methods Tool”, and “DrawNET++: Model Objects to Support Performance Analysis and Simulation of Systems”. Additionally, less relevant to the topic or more specialised to a specific kind of problems tools are presented to this book such as: “The MOMBASA Software Environment – A Toolkit for Performance Evaluation of Multicast-Based Mobility Support”, “GULK: A Dynamic Instrumentation Tool for the Linux Kernel” and “Geist: a Web Traffic Generation Tool” [24].
All the above tools are used for computer performance evaluation, using a variety of different methodologies and algorithms in order to provide accurate solutions to problems, each of them has been designed for. Some of them are more general while some others are focused on specific kind of systems and solve only specific kind of problems. Additionally, most of them provide a graphical user interface (GUI) and the approach that each of these tools follows, in matters of design, is going to be taken seriously into account when designing the GUI for this proposed dissertation project. Finally, the produced solutions of the proposed implementation can to be compared with the results that some of the above tools provide, in order to test the efficiency of the developed toolset which is going to make use of the PQD software library.

The structure of performability modelling and evaluation tools should allow the system designer to specify the model in a simple and efficient way, hiding the mathematical details as much as possible. Additionally, the output of the tool should demonstrate the results in a comprehensive way that does not demand detailed knowledge of the underlined mathematical model. [2] The 10th chapter of the book “Performability Modelling (Techniques and Tools)” edited by Boudewijn R. Haverkort, Raymond Marie, Gerardo Rubino, and Kishor Trivedi, presents and compares a number of tools designed for performability modelling and evaluation. In this comparison aspects like the class of models the tool can handle (from a mathematical point of view), the modelling language employed, and aspects related to the usability and effectiveness of their user interface and implementation are discussed. The list of the performance evaluation modelling tools, that the book presents and compares, includes: DSPN Express, DYQN Tool+, METAPHOR, METASAN, METFAC, NUMAS, PANDA, PENELOPE and COSTPN, PENPET, SAVE, SHARPE and GISHARPE, SPNP, SURF-2, TANGRAM-II, TIMENET, TIPPTOOL, and ULTRASAN. [2] The presentation of the above implemented tools as well as the comparison between them, is going to demonstrate several design and implementation aspects for the proposed GUI, which is going to be based on the PDQ library.

Additional presentations and descriptions of the several implemented tools for performance system evaluation can be found in separate papers in the literature.
The development of an efficient and practical software package called QST is reported by Lester Lipsky, Dilip Tagare and Edward Bigos, in the paper called "Evaluation of Queueing System Parameters Using Linear Algebraic Queueing Theory - An Implementation". The above package has been developed within the MATLAB environment and it aims to produce data or graphs of various performance attributes for a particular class of queueing systems it can be applied. [10]

An implementation which uses the DNAmaca Markov Chain Analyser interface language, is presented by Peter G. Harrison and William J. Knottenbelt, in a paper "Passage Time Distributions in Large Markov Chains". This implementation has been rigorously validated and it has already been applied in large Markov Chains with over one million states. [18]

The procedure of constructing queues is explored in the paper “From Switching Theory to Queueing Theory” written by Cheng-Shang Chang, Yi-Ting Chen, Jay Cheng, Po-Kai Huang and Duan-Shin Lee. The purpose of this text is to explore the potential of constructing various types of queues applying the switching theory. [4] This paper is representative to the work that has been done around the various ways of representing a queueing system, and it indicates helpful aspects in the field of designing and representing queues. How queues are going to be represented in the proposed GUI is under consideration and papers like this can provide several ideas of the potential approaches that can be followed.

5.The PDQ software

The purpose of this dissertation project is the design and development of a program with a graphical user interface (GUI) which makes use of an open source software called Pretty Damn Quick (PDQ). PDQ uses queue-theoretic paradigms to represent computer systems.
Firstly, the queueing model which represents the computer system resources should be constructed. Then queueing model can be solved using a combination of algorithmic and numerical procedures (analytically). In PDQ queues are invoked as functions as they make calls to the appropriate library functions. As soon as the system is expressed as a queueing network, it can be solved almost instantaneously by calling the PDQ_Solve() function. A report is then generated which includes all the corresponding performance metrics such as system throughput and system response time. Additionally, details about queue lengths and utilizations at each of the defined queues are generated.

For example, in a simple M/M/1 queueing network we can define as input the average Arrival Rate into the queue: λ and the average Service Time at the server: S. With these input parameters we can calculate all other performance quantities (outputs) of interest such as the average Residence Time a customer spends getting through the queueing system: R = S / (1 − λS), the Utilization of the server: U = λS, the average Queue Length of the system: Q = λR, and the average Waiting Time a customer can expect to spend before getting service: W = R − U. [14]

The first version of PDQ library, which is written in C programming language, is described in the book of Neil J. Gunther, "The Practical Performance Analyst, Performance-By-Design Techniques For Distributed Systems" [15], while the more recent Perl edition of the library is described in is book "Analyzing Computer Systems Performance: With Perl: PDQ" [14]. There are more distributions of the PDQ software available in other languages such as Python and PHP, while a Java version has been recently released. This Java version of the PDQ library is going to be used for the needs of this project.

6.Summary

To sum up, the need to analyse and evaluate the performance of the even and more complex modern systems, has encouraged the development of different techniques such as benchmarking, simulation and analytic modelling. The present research is focused mostly on the last of these techniques. Queueing theory is behind the analytical method, and more specifically the study of queueing networks. Firstly, the queueing model which represents the computer system resources should be constructed. Then queueing model can be solved using a combination of algorithmic and numerical procedures. The mathematical concepts around the probabilistic theory and Markov Chains have lead to the development of several algorithms that solve queueing networks Among the most effective of these algorithms is the Mean Value Analysis (MVA). Software tools that use algorithms like MVA have been developed complementary to already existing simulation tools. Some of them provide a GUI or a special input language or both. Pretty Damn Quick (PDQ) is a free open source library which contains s collection of functions that solve (using MVA) queueing networks.

References

[1] A. E. Conway, N. D. Georganas, "RECAL - A New Efficient Algorithm for the Exact Analysis of Multiple-Chain Closed Queuing Networks", Journal of the ACM (JACM), Volume 33 Issue 4, ACM Press, 1989.

[2] Boudewijn R. Haverkort, Raymond Marie, Gerardo Rubino, Kishor Trivedi (Eds.), "Performability Modelling (Techniques and Tools)", John Wiley & Sons, Ltd, 2001.

[3] Charles H. Sauer, "Computational Algorithms For State-Dependent Queueing Networks", ACM Transactions on Computer Systems (TOCS), Volume 1 Issue 1, ACM Press, 1983.

[4] Cheng-Shang Chang, Yi-Ting Chen, Jay Cheng, Po-Kai Huang and Duan-Shin Lee, "From Switching Thory to Queueing Theory", ACM SIGMETRICS Performance Evaluation Review, Volume 34 Issue 2, ACM Press, September 2006.

[5] Daniel A. Menasce, Lawrence W. Dowdy, Virgilio A.F. Almeida, "Performance by Design: Computer Capacity Planning By Example", Prentice Hall PTR, January 2004.

[6] Erol Gelenbe and Guy Pujolle, "Introduction To Queueing Networks", John Wiley & Sons Ltd, second edition, 1998.

[7] Gunter Bolch, Stefan Greiner, Hermann de Meer, and Kishor S. Trivedi, "Queuing Networks and Markov Chains (Modeling and Performance Evaluation with Computer Science Applications)", John Wiley & Sons, Inc, 1998.

[8] K. Kant, "Introduction to Computer System Performance Evaluation", McGraw-Hill Inc, 1992.

[9] Kyle j. Nesbit, Nidhi Aggarwal, James Laudon, James E. Smith, "Fair Queuing Memory Systems", Proceedings of the 39 Annual IEEE/ACM International Symposium on Microarchitecture MICRO 39, IEEE Computer Sociaty, 2006.

[10] Lester Lipsky, Dilip Tagare and Edward Bigos, "Evaluation of Queueing System Parameters Using Linear Algebraic Queueing Theory - An Implementation", Proceedings of the 1990 ACM SIGSMALL/PC symposium on Small systems SIGSMALL '90, ACM Press, February 1990.

[11] Liber Amicorum for J. W. Cohen, O. J. Boxma, R. Syski (Eds.), "Queueing Theory and its Applications", CWI Monograph, 1988.

[12] Mario Naugebauer, Jorn Plonnigs, Klaus Kabitzsch, “Prediction of Network Load in Building Automation”, In 5th IFAC International Conference on Fielbus Systems and Their Applications (FeT 2003), Aveiro, Portugal, 2003.

[13] Michele Garetto, Renato Lo Cigno, Michela Meo, Marco Ajmone Marsan, "Closed Queueing Network Models Of Interacting Long-Lived TCP flows", IEEE/ACM Transactions on Networking (TON), Volume 12 Issue 2, IEEE Press, April 2004.

[14] Neil J. Gunther, "Analyzing Computer Systems Performance: With Perl: PDQ", Springer, 2005.

[15] Neil J. Gunther, "The Practical Performance Analyst, Performance-By-Design Techniques For Distributed Systems", McGraw-Hill, 1998.

[16] Nico M. Van Dijk, "Queueing Networks and Product Forms (A Systems Approach)", John Wiley & Sons Ltd, 1993.

[17] Paul Fortier, Howard Michel, "Computer Systems Performance Evaluation and Prediction", Digital Press, 1st edition, October 2002.

[18] Peter G. Harrison, William J. Knottenbelt, "Passage Time Distributions in Large Markov Chains", ACM SIGMETRICS Performance Evaluation Review, Proceedings of the 2002 ACM SIGMETRICS International conference on Measurement and Modeling of Computer Systems SIGMETRICS '02, Volume 30 Issue 1, ACM Press, June 2002.

[19] Peter J. B. King. "Computer and Communication Systems Performance Modelling", Prentice Hall International (UK) Ltd, 1990.

[20] Piet Van Mieghem, "Performance Analysis of Communication Networks and Systems", Cambridge University Press, 2006.

[21] Raj Jain, "The Art Of Computer Systems Performance Analysis", John Wiley & Sons, Inc, 1991.

[22] R. D. van der Mei, E. M. M. Winands, "Mean Value Analysis For Polling Systems in Heavy Traffic", Proceedings of the 1st international conference on Performance evaluation methodologies
and tools valuetools '06, ACM Press, 2006.

[23] Tehany A. Fergany and Howard A. Sholl, "Performance-Based Multiple Server Support for Distributed Real-Time Applications", Proceedings of the 1990 ACM SIGSMALL/PC symposium on Small systems SIGSMALL '90, ACM Press, February 1990.

[24] Tony Field, Peter G. Harrison, Jeremy Bradley, Uli Harder (Eds.), 12th International Conference, TOOLS 2002 London, UK April 14-17, 2002 Proceedings, Springer, 2002.

[25] Weiping Zhu, "An Approximate Analysis of the Shortest Queue Policy on Soft Real-Time Scheduling", ACM SIGMETRICS Performance Evaluation Review, Volume 28 Issue 3, ACM Press, December 2000.

[26] Wu-Lin Chen, Colm Art O'Cinneide, "Towards a Polynomial-Time Randomized Algorithm for Closed Product-Form Networks", ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 8 Issue 3, ACM Press, July 1998.

[27] Xiouli Chao, Maskiyo Miyazawa and Michael Pinedo, "Queueing Networks (Customers, Signals and Product Form Solutions)", John Wiley & Sons Ltd, 1999.

References (alphabetically)

2007-05-25T19:02:00.000-07:00

References

[1] A. E. Conway, N. D. Georganas, "RECAL - A New Efficient Algorithm for the Exact Analysis of Multiple-Chain Closed Queuing Networks", Journal of the ACM (JACM), Volume 33 Issue 4, ACM Press, 1989.

[2] Boudewijn R. Haverkort, Raymond Marie, Gerardo Rubino, Kishor Trivedi (Eds.), "Performability Modelling (Techniques and Tools)", John Wiley & Sons, Ltd, 2001.

[3] Charles H. Sauer, "Computational Algorithms For State-Dependent Queueing Networks", ACM Transactions on Computer Systems (TOCS), Volume 1 Issue 1, ACM Press, 1983.

[4] Cheng-Shang Chang, Yi-Ting Chen, Jay Cheng, Po-Kai Huang and Duan-Shin Lee, "From Switching Thory to Queueing Theory", ACM SIGMETRICS Performance Evaluation Review, Volume 34 Issue 2, ACM Press, September 2006.

[5] Daniel A. Menasce, Lawrence W. Dowdy, Virgilio A.F. Almeida, "Performance by Design: Computer Capacity Planning By Example", Prentice Hall PTR, January 2004.

[6] Erol Gelenbe and Guy Pujolle, "Introduction To Queueing Networks", John Wiley & Sons Ltd, second edition, 1998.

[7] Gunter Bolch, Stefan Greiner, Hermann de Meer, and Kishor S. Trivedi, "Queuing Networks and Markov Chains (Modeling and Performance Evaluation with Computer Science Applications)", John Wiley & Sons, Inc, 1998.

[8] K. Kant, "Introduction to Computer System Performance Evaluation", McGraw-Hill Inc, 1992.

[9] Kyle j. Nesbit, Nidhi Aggarwal, James Laudon, James E. Smith, "Fair Queuing Memory Systems", Proceedings of the 39 Annual IEEE/ACM International Symposium on Microarchitecture MICRO 39, IEEE Computer Sociaty, 2006.

[10] Lester Lipsky, Dilip Tagare and Edward Bigos, "Evaluation of Queueing System Parameters Using Linear Algebraic Queueing Theory - An Implementation", Proceedings of the 1990 ACM SIGSMALL/PC symposium on Small systems SIGSMALL '90, ACM Press, February 1990.

[11] Liber Amicorum for J. W. Cohen, "Queueing Theory and its Applications", CWI Monograph, 1988.

[12] Michele Garetto, Renato Lo Cigno, Michela Meo, Marco Ajmone Marsan, "Closed Queueing Network Models Of Interacting Long-Lived TCP flows", IEEE/ACM Transactions on Networking (TON), Volume 12 Issue 2, IEEE Press, April 2004.

[13] Neil J. Gunther, "Analyzing Computer Systems Performance: With Perl: PDQ", Springer, 2005.

[14] Neil J. Gunther, "The Practical Performance Analyst, Performance-By-Design Techniques For Distributed Systems", McGraw-Hill, 1998.

[15] Nico M. Van Dijk, "Queueing Networks and Product Forms (A Systems Approach)", John Wiley & Sons Ltd, 1993.

[16] Paul Fortier, Howard Michel, "Computer Systems Performance Evaluation and Prediction", Digital Press, 1st edition, October 2002.

[17] Peter G. Harrison, William J. Knottenbelt, "Passage Time Distributions in Large Markov Chains", ACM SIGMETRICS Performance Evaluation Review, Proceedings of the 2002 ACM SIGMETRICS International conference on Measurement and Modeling of Computer Systems SIGMETRICS '02, Volume 30 Issue 1, ACM Press, June 2002.

[18] Peter J. B. King. "Computer and Communication Systems Performance Modelling", Prentice Hall International (UK) Ltd, 1990.

[19] Piet Van Mieghem, "Performance Analysis of Communication Networks and Systems", Cambridge University Press, 2006.

[20] Raj Jain, "The Art Of Computer Systems Performance Analysis", John Wiley & Sons, Inc, 1991.

[21] R. D. van der Mei, E. M. M. Winands, "Mean Value Analysis For Polling Systems in Heavy Traffic", Proceedings of the 1st international conference on Performance evaluation methodologies
and tools valuetools '06, ACM Press, 2006.

[22] Tehany A. Fergany and Howard A. Sholl, "Performance-Based Multiple Server Support for Distributed Real-Time Applications", Proceedings of the 1990 ACM SIGSMALL/PC symposium on Small systems SIGSMALL '90, ACM Press, February 1990.

[23] Tony Field, Peter G. Harrison, Jeremy Bradley, Uli Harder (Eds.), 12th International Conference, TOOLS 2002 London, UK April 14-17, 2002 Proceedings, Springer, 2002.

[24] Weiping Zhu, "An Approximate Analysis of the Shortest Queue Policy on Soft Real-Time Scheduling", ACM SIGMETRICS Performance Evaluation Review, Volume 28 Issue 3, ACM Press, December 2000.

[25] Wu-Lin Chen, Colm Art O'Cinneide, "Towards a Polynomial-Time Randomized Algorithm for Closed Product-Form Networks", ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 8 Issue 3, ACM Press, July 1998.

[26] Xiouli Chao, Maskiyo Miyazawa and Michael Pinedo, "Queueing Networks (Customers, Signals and Product Form Solutions)", John Wiley & Sons Ltd, 1999.

OVERVIEW

2007-05-25T13:48:00.001-07:00

OUTLINE OF DISSERTATION PROJECT

Modeling Queuing Networks for Decision Making and System's Performance Analysis using the PDQ library

1 Introduction

1.1 Aims and objectives

* The aim of this project is to provide a general tool with a GUI, which helps the user to define models of closed queuing networks using simple graphical "drag and drop" elements and then solve the defined problem using the PDQ library, which is a free open source software. The solution should be represented in a graphical way as well (plot diagrams, color use, etc).
* To investigate the possibly different existing approaches in designing an interface for representing closed queuing network problems, then analyze the alternatives, and finally select one of these approaches or propose a new approach, explaining the rationale and the reasons of choosing this design approach (potential benefits, advantages and disadvantages of the selected approach).

1.2 Queuing Theory

1.2.1 Definition

* Queuing Theory is the mathematical study of waiting lines (or queues), and it is generally considered a branch of operations research because the outcomes of the theory are applicable to make business decisions about the resources needed to provide service.

1.2.2 Problems with Queues

* Properties of queues and queue problems
* Common Algorithms (like FIFO LIFO, etc) and their properties
* Applications of queuing theory in everyday life and in cybernetics (PSTN example)

1.2.3 Queuing Networks
* Open Queuing Networks and Closed Queuing Networks
* Queuing Networks and Markov Chains
* Mathematical Background and Algorithms.
Queuing systems use Markov Chains which model the system in each state. Incoming traffic is modeled via a Poisson distribution and is a subject to Erlang's queuing theory assumptions.

1.3 Performance Analysis and Decision Making (introduction to the problem)
* Performance Analysis Techniques
* Systems' Modeling and Performance Evaluation
* Existing tools in the area of decision making based on queuing networks modeling (PDQ library)
* Which approach do these tools follow in matters of design

2 Literature Review/Survey/Requirements

2.1 Previous work on queuing networks and available software

2.2 Theories and applications (tools) related to queuing problems and decision making

2.3 How this approach differs from, or extends previous work in this area

3 Modeling of Closed Queuing Networks using the PDQ software

3.1 Description of the library characteristics, capabilities and functions

3.2 How this software can be used to help in modeling and solving closed queuing networks

3.3 Designing the GUI (analyzing properties, aims, requirements, alternatives, implementation and evaluation issues)

3.4 Implementation
* Programming language(s)
* Additional software that has been used (APIs)

4 Results

4.1 In which way the user defines the problem (queuing network model) using the features of the program

4.2 Which is the range of problems that this program finally solves?
* Large queuing networks and how they can be modeled and solved using the program.

4.3 Demonstration of how the program solves these problems and how the solution(results) is presented to the final user
* Graphical representation of the model
* Plots and Tables of the results
* Demonstration of the solution using colors

5 Conclusions

5.2 Evaluation of the final program in matters of effectiveness, usability, performance and design
* How close to reality is the proposed from the program solution
* How fast this solution is calculated from the program
* Compatibility and extensibility
* Drawbacks and bottlenecks

5.3 Comparison of the developed program with previous implementations that model and solve queuing networks

* Advantages and Disadvantages of the selected design and implementation approach

5.4 In which extend the achievements meet the requirements? Discussion

* Initial objectives and how they have been achieved or not
* What is the contribution in the area of queuing networks that has been made by this piece of work

5.5 Future work

* How the developed tool could be extended
* What should be done by anyone who would like to continue this project

References (topic related)

2007-05-25T11:41:00.000-07:00

Performance Modeling

[1] Peter J. B. King. "Computer and Communication Systems Performance Modelling", Prentice Hall International (UK) Ltd, 1990.

[2] Neil J. Gunther, "The Practical Performance Analyst, Performance-By-Design Techniques For Distributed Systems", McGraw-Hill, 1998.

[2.5] Neil J. Gunther, "Analyzing Computer Systems Performance: With Perl: PDQ", Springer, 2005.

[2.7] Daniel A. Menasce, Lawrence W. Dowdy, Virgilio A.F. Almeida, "Performance by Design: Computer Capacity Planning By Example", Prentice Hall PTR, January 2004.

[2.8] Paul Fortier, Howard Michel, "Computer Systems Performance Evaluation and Prediction", Digital Press, 1st edition, October 2002.

[3] Raj Jain, "The Art Of Computer Systems Performance Analysis", John Wiley & Sons, Inc, 1991.

[4] K. Kant, "Introduction to Computer System Performance Evaluation", McGraw-Hill Inc, 1992.

[5] Tehany A. Fergany and Howard A. Sholl, "Performance-Based Multiple Server Support for Distributed Real-Time Applications", Proceedings of the 1990 ACM SIGSMALL/PC symposium on Small systems SIGSMALL '90, ACM Press, February 1990.

[6] Piet Van Mieghem, "Performance Analysis of Communication Networks and Systems", Cambridge University Press, 2006.

Queuing Theory

[7] Nico M. Van Dijk, "Queueing Networks and Product Forms (A Systems Approach)", John Wiley & Sons Ltd, 1993.

[8] Xiouli Chao, Maskiyo Miyazawa and Michael Pinedo, "Queueing Networks (Customers, Signals and Product Form Solutions)", John Wiley & Sons Ltd, 1999.

[9] Erol Gelenbe and Guy Pujolle, "Introduction To Queueing Networks", John Wiley & Sons Ltd, second edition, 1998.

[10] Liber Amicorum for J. W. Cohen, "Queueing Theory and its Applications", CWI Monograph, 1988.

[11] Wu-Lin Chen, Colm Art O'Cinneide, "Towards a Polynomial-Time Randomized Algorithm for Closed Product-Form Networks", ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 8 Issue 3, ACM Press, July 1998.

[12] Michele Garetto, Renato Lo Cigno, Michela Meo, Marco Ajmone Marsan, "Closed Queueing Network Models Of Interacting Long-Lived TCP flows", IEEE/ACM Transactions on Networking (TON), Volume 12 Issue 2, IEEE Press, April 2004.

[13] R. D. van der Mei, E. M. M. Winands, "Mean Value Analysis For Polling Systems in Heavy Traffic", Proceedings of the 1st international conference on Performance evaluation methodologies
and tools valuetools '06, ACM Press, 2006.

[14] Kyle j. Nesbit, Nidhi Aggarwal, James Laudon, James E. Smith, "Fair Queuing Memory Systems", Proceedings of the 39 Annual IEEE/ACM International Symposium on Microarchitecture MICRO 39, IEEE Computer Sociaty, 2006.

[15] Charles H. Sauer, "Computational Algorithms For State-Dependent Queueing Networks", ACM Transactions on Computer Systems (TOCS), Volume 1 Issue 1, ACM Press, 1983.

[16] Weiping Zhu, "An Approximate Analysis of the Shortest Queue Policy on Soft Real-Time Scheduling", ACM SIGMETRICS Performance Evaluation Review, Volume 28 Issue 3, ACM Press, December 2000.

[17] A. E. Conway, N. D. Georganas, "RECAL - A New Efficient Algorithm for the Exact Analysis of Multiple-Chain Closed Queuing Networks", Journal of the ACM (JACM), Volume 33 Issue 4, ACM Press, 1989.

Tools

[18] Cheng-Shang Chang, Yi-Ting Chen, Jay Cheng, Po-Kai Huang and Duan-Shin Lee, "From Switching Thory to Queueing Theory", ACM SIGMETRICS Performance Evaluation Review, Volume 34 Issue 2, ACM Press, September 2006.

[19] Boudewijn R. Haverkort, Raymond Marie, Gerardo Rubino, Kishor Trivedi (Eds.), "Performability Modelling (Techniques and Tools)", John Wiley & Sons, Ltd, 2001.

[20] Gunter Bolch, Stefan Greiner, Hermann de Meer, and Kishor S. Trivedi, "Queuing Networks and Markov Chains (Modeling and Performance Evaluation with Computer Science Applications)", John Wiley & Sons, Inc, 1998.

[21] Tony Field, Peter G. Harrison, Jeremy Bradley, Uli Harder (Eds.), 12th International Conference, TOOLS 2002 London, UK April 14-17, 2002 Proceedings, Springer, 2002.

[22] Peter G. Harrison, William J. Knottenbelt, "Passage Time Distributions in Large Markov Chains", ACM SIGMETRICS Performance Evaluation Review, Proceedings of the 2002 ACM SIGMETRICS International conference on Measurement and Modeling of Computer Systems SIGMETRICS '02, Volume 30 Issue 1, ACM Press, June 2002.

[23] Lester Lipsky, Dilip Tagare and Edward Bigos, "Evaluation of Queueing System Parameters Using Linear Algebraic Queueing Theory - An Implementation", Proceedings of the 1990 ACM SIGSMALL/PC symposium on Small systems SIGSMALL '90, ACM Press, February 1990.

Literature Review Sections

2007-05-24T17:45:00.000-07:00

1. Introduction

2. Performance Modeling
(the 3 approaches and the focus on the 3rd)
- Benchmarking
- Simulation
- Analytical

3. Queuing Theory
- mathematical background (Probability theory, Stochastic processes)
- queuing networks (M/M/1, M/G/1, M/M/c, M/M/%)
- computational algorithms (Convolution algorithm, MVA, LBANC, RECAL -> P.Kings book)

4. Existing Tools in the area
(ProC/B, DrawNET++, ...)
- What kind of problems they solve
- Which methodology/algorithms they use
- Which of them is considered to be more effective

5. The PDQ software
(C and Perl version until the newer Java version of the library)
- C version
- Pearl/Python/PHP versions
- Java recent version
- How the library is used(functions, characteristics, capabilities, ...)
- Reference to the web site and the manual of the library

6. Conclusion
- How is the situation in this area
- What has been done
- How this is going to help me for my project
- What else is expected to be done

Additional Aim of the dissertation project

2007-05-24T17:30:00.000-07:00

To create a tool set, which will provide a more high level approach to the existing low level PDQ software. Users that are not familiar with the underlined API, should be able to make use of the PDQ library capabilities in a simple and straightforward way, through the designed GUI of the tool. The purpose of this tool is mostly educational rather than commercial.

Inputs & Outputs in a simple PDQ Example

2007-05-24T13:35:00.000-07:00

M/M/1 Formula

It is more convenient to think in terms of inputs and outputs. In other words, which parameters do we need to provide to the formulae versus those values we will calculate as the result of applying the formulae? We list them here:

Inputs:

* The average Arrival Rate into the queue: λ.
* The average Service Time at the server: S.

With these input parameters we can calculate all other performance quantities (outputs) of interest.

Outputs:

* The average Residence Time a customer spends getting through the queueing system: R = S / (1 − λS).
* The Utilization of the server: U = λS.
* The average Queue Length of the system: Q = λR.
* The average Waiting Time a customer can expect to spend before getting service: W = R − U.

To apply these relationships, we need to choose some values for λ and S. We choose the following values so as to keep the arithmetic simple.

Reference

The 3 approaches in Computer Performance Evaluation

2007-05-24T12:45:00.000-07:00

1. Benchmarking: The system can be built then modified and finally measured

+ "performance estimate is perfectly accurate"
+ it is based on a real system so it is sure that there haven't been introduced any errors that are not in the real system.

- high cost
- not flexible
- time consuming

2. Simulation: to build a simulation model of the system, which can be validated against the already existing system. After the validation several needed modifications can be derived.

This approach permits an arbitrary level of detail to be included:
+ any system feature can be included and checked
- there is the danger to include too many features(which are not so essential for the performance of the required system) of the real system to the simulation increasing complexity and cost

3. Analytic Modeling: to construct a mathematical model (via a combination of algorithmic and numerical procedures) of the system and then perform validation, as in simulation.

+ The model is constructed faster
+ The solution is calculated faster than in simulation or benchmarking for the final system
+ it provides a significant estimation of the behavior of the potential system without first implementing it. Thus it is a much cheaper technique.

Notes for the Book: "Computer and Comunication Systems Performance Modelling" by Peter J. B. King

2007-05-24T12:02:00.000-07:00

This book introduces the fundamental knowledge a student or professional should have around queuing theory. It provides the basic background of mathematical concepts such as probability theory, stochastic processes(Poison Processes, Markov Processes, Markov Chains, etc.), simple queues(M/M/1), single server(M/G/1) and multi server queues(M/M/c). Queuing problems and their significance in the field of system analysis and communication system performance is discussed. Several approaches of modeling and solving that kind of problems are presented, including algorithms and mathematical tools that are used commonly. Each chapter contains a bibliography which is very helpful for someone who is interested in further research. It is probably one of the first books that someone, who doesn't have a stable background in queuing theory and its relevant mathematical concepts, should read.
The book also includes a demonstration of some computational algorithms for product form queuing networks.

Notes of Book: "The Practical Performance Analyst" of Neil J. Gunther

2007-05-22T17:01:00.000-07:00

High-speed networking, which has been recently developed placed in a demanding business market, has resulted into changing the approach of performance analysis techniques applied to a system. Simple models, even if less precise, are preferred of complex and more accurate models, . A more modern approach compared to simulation is to create simple and easier to define models -even if less precise-, rather than complex and more accurate, because decisions are expected to be taken up right away so the answers to problems should not take too long to be formed.

This book presents in a simple and understandable way the main ideas of queuing theory (single and multi server queues, finite and infinite source queues, Markovian and non-Markovian models), including examples and sampling programs in a disk. The software in which the book is referred to is the same that is going to be used for the implementation of the dissertation project except from the fact that this version (it is the first one) of the PDQ library has been written in C, while the implementation makes use of the more recent Java version of the software. Pretty Damn Quick (PDQ) software library is presented in an Appendix in the end of the book. This book is highly associated to the library, so it constitutes the basic guide for the programmer who wants to create, using the PDQ open source software.

How to write the Literature Review

2007-05-20T07:28:00.000-07:00

In writing the literature review, your purpose is to convey to your reader what knowledge and ideas have been established on a topic, and what their strengths and weaknesses are. As a piece of writing, the literature review must be defined by a guiding concept (e.g., your research objective, the problem or issue you are discussing, or your argumentative thesis). It is not just a descriptive list of the material available, or a set of summaries.

Once you've settled on a general pattern of organization, you're ready to write each section. There are a few guidelines you should follow during the writing stage as well. Here is a sample paragraph from a literature review about sexism and language to illuminate the following discussion:

However, other studies have shown that even gender-neutral antecedents are more likely to produce masculine images than feminine ones (Gastil, 1990). Hamilton (1988) asked students to complete sentences that required them to fill in pronouns that agreed with gender-neutral antecedents such as "writer," "pedestrian," and "persons." The students were asked to describe any image they had when writing the sentence. Hamilton found that people imagined 3.3 men to each woman in the masculine "generic" condition and 1.5 men per woman in the unbiased condition. Thus, while ambient sexism accounted for some of the masculine bias, sexist language amplified the effect. (Source: Erika Falk and Jordan Mills, "Why Sexist Language Affects Persuasion: The Role of Homophily, Intended Audience, and Offense," Women and Language19:2.

Use evidence

In the example above, the writers refer to several other sources when making their point. A literature review in this sense is just like any other academic research paper. Your interpretation of the available sources must be backed up with evidence to show that what you are saying is valid.

Be selective

Select only the most important points in each source to highlight in the review. The type of information you choose to mention should relate directly to the review's focus, whether it is thematic, methodological, or chronological.

Use quotes sparingly

Falk and Mills do not use any direct quotes. That is because the survey nature of the literature review does not allow for in-depth discussion or detailed quotes from the text. Some short quotes here and there are okay, though, if you want to emphasize a point, or if what the author said just cannot be rewritten in your own words. Notice that Falk and Mills do quote certain terms that were coined by the author, not common knowledge, or taken directly from the study. But if you find yourself wanting to put in more quotes, check with your instructor.

Summarize and synthesize

Remember to summarize and synthesize your sources within each paragraph as well as throughout the review. The authors here recapitulate important features of Hamilton's study, but then synthesize it by rephrasing the study's significance and relating it to their own work.

Keep your own voice

While the literature review presents others' ideas, your voice (the writer's) should remain front and center. Notice that Falk and Mills weave references to other sources into their own text, but they still maintain their own voice by starting and ending the paragraph with their own ideas and their own words. The sources support what Falk and Mills are saying.

Use caution when paraphrasing

When paraphrasing a source that is not your own, be sure to represent the author's information or opinions accurately and in your own words. In the preceding example, Falk and Mills either directly refer in the text to the author of their source, such as Hamilton, or they provide ample notation in the text when the ideas they are mentioning are not their own, for example, Gastil's. For more information, please see our handout on plagiarism.

Revise, revise, revise

Draft in hand? Now you're ready to revise. Spending a lot of time revising is a wise idea, because your main objective is to present the material, not the argument. So check over your review again to make sure it follows the assignment and/or your outline. Then, just as you would for most other academic forms of writing, rewrite or rework the language of your review so that you've presented your information in the most concise manner possible. Be sure to use terminology familiar to your audience; get rid of unnecessary jargon or slang. Finally, double check that you've documented your sources and formatted the review appropriately for your discipline. For tips on the revising and editing process, see our handout Straight Talk about Revision

NOTES: Book: "The Art of Computer Systems Performance Analysis"

2007-05-17T09:12:00.000-07:00

purpose: to give the basic modeling, simulation, and analysis background to system analysts in order to understand performance terminology and the various analysis techniques such as statistics, probability theory, experimental design, and queuing theory. It indicates how to use queuing or simulation models, how to combine skills, applying techniques of measurement and modeling, to solve queuing problems and how to interpret the results.
This book is mostly practical than queuing theoretic. It suggests that "in practice, one needs to use both measurements as well as modeling techniques to solve performance problems", and both aspects of the field are thoroughly demonstrated.

Notes: Book: "Queueing networks and Markov Chains"

2007-05-17T07:44:00.000-07:00

Queuing Networks and Markov Chains are commonly used for the performance and reliability evaluation of computer, communication and manufacturing systems.

Aim of the book to offer a detailed treatment of queuing systems, queuing networks and continues and discrete Markov chains.

provides:
- in depth numerical solution algorithms.
- set of examples.
- discuss stochastic Petri nets - solution of Markov Chains
- describe and apply 4 software packages (PEPSY, SPNP, MOSES, SHARPE)
- provide problems as exercises

Notes about Queueing Networks

2007-05-11T06:04:00.000-07:00

2.4 Queuing Networks
Queuing network analysis is a well-known technique
to estimate the performance of systems. As
long as the process to investigate is in some way
to model in queues, this powerful analysis method
can help to design, gain experience about and
optimize it. The main idea of this theory is to
describe the system with interconnected queues
and servers. Of course, for large systems the representing
queuing model becomes rather large as
well.
To cope with these problems, tools for the automated
queuing network analysis can be used. One
example is the function library PDQ (pretty damn
quick)(Gunther, 2000). It provides the ability to
compute relatively large queuing networks in a
short time. Though, generating and specifying a
model is rather circumstantial. It has to be done in
C-les. As a result of the computation, PDQ oers
manifold information about the analyzed system
(e.g. utilization of the servers, residence times and
delays). But only with the knowledge of the environmental
behavior and the corresponding impact
on the queuing model, common-sense results can
be achieved.

http://web.inf.tu-dresden.de/~mn7/publications/neugebauer03prediction.pdf

Intro to PDQ Dissertation Idea

2007-05-11T04:03:00.000-07:00

PDQ (Pretty Damn Quick) is a library, originally created in C, which helps the user to model and solve queueing problems. The aim of this open source software is to provide a performance analysis tool for computer systems and not only. Newer versions of the library have been written in other languages as well (Perl, Python, Java, PHP). Probably the java version is going to be used for the needs of this project. The purpose of this java approach would be: efficiency(easier to create a GUI in Java) and portability (a Java project runs in every system). Additionally, Java is a Object Oriented language (modern compared to C)and the library PDQ written in Java is newer, so there is the motivation for testing and evaluation of this approach.

The objectives of this project are:

- research in the area of queueing networks:
what kind of mathematics and stochastic algorithms are used to solve that kind of problems? (Poison Distribution, Markov chains, memoryless techniques in general).

- development of a user friendly tool, with a GUI (probably implemented in Java), which solves simple queueing problems using the functions of PDQ library.
which alternatives exist in designing a graphical user interface, which provide benefits in matters of usability, efficiency, accuracy, elaboration etc. A comparison of the different identified approaches in design and evaluation of the selected approach.