In this study the maximum entropy formalism [JAYN 57] is suggested as an alternative theory for general queueing systems of computer performance analysis. The motivation is to overcome some of the problems arising in this field and to extend the scope of the results derived in the context of Markovian queueing theory. For the M/G/l model a unique maximum entropy solution., satisfying locALl balance is derived independent of any assumptions about the service time distribution. However, it is shown that this solution is identical to the steady state solution of the underlying Marko-v process when the service time distribution is of the generalised exponential (CE) type. (The GE-type distribution is a mixture of an exponential term and a unit impulse function at the origin). For the G/M/1 the maximum entropy solution is identical in form to that of the underlying Markov process, but a GE-type distribution still produces the maximum overall similar distributions. For the GIG11 model there are three main achievements: first, the spectral methods are extended to give exaft formulae for the average number of customers in the system for any G/G/l with rational Laplace transform. Previously, these results are obtainable only through simulation and approximation methods. (ii) secondly, a maximum entropy model is developed and used to obtain unique solutions for some types of the G/G/l. It is also discussed how these solutions can be related to the corresponding stochastic processes. (iii) the importance of the G/GE/l and the GE/GE/l for the analysis of general networks is discussed and some flow processes for these systems are characterised. For general queueing networks it is shown that the maximum entropy solution is a product of the maximum entropy solutions of the individual nodes. Accordingly, existing computational algorithms are extended to cover general networks with FCFS disciplines. Some implementations are suggested and a flow algorithm is derived. Finally, these results are iised to improve existing aggregation methods. In addition, the study includes a number of examples, comparisons, surveys, useful comments and conclusions.

Decomposition methods based on the hierarchical partitioning of the state space of queueing network models offer powerful evaluation tools for the performance analysis of computer systems and communication networks. These methods being conventionally implemented capture the exact solution of separable queueing network models but their credibility differs when applied to general queueing networks. This thesis provides a universal information theoretic framework for the implementation of hierarchical decomposition schemes, based on the principle of minimum relative entropy given fully decomposable subset and aggregate utilization, mean queue length and flow-balance constraints. This principle is used, in conjuction with asymptotic connections to infinite capacity queues, to derive new closed form approximations for the conditional and marginal state probabilities of general queueing network models. The minimum relative entropy solutions are implemented iteratively at each decomposition level involving the generalized exponential (GE) distributional model in approximating the general service and asymptotic flow processes in the network. It is shown that the minimum relative entropy joint state probability, subject to mean queue length and flow-balance constraints, is identical to the exact product-form solution obtained as if the network was separable. An investigation into the effect of different couplings of the resource units on the relative accuracy of the approximation is carried out, based on an extensive experimentation. The credibility of the method is demonstrated with some illustrative examples involving first-come-first-served general queueing networks with single and multiple servers and favourable comparisons against exact solutions and other approximations are made.

Priority based scheduling disciplines are widely used by existing computer operating systems. However, the mathematical analysis and modelling of these systems present great difficulties since priority schedulling is not compatible with exact product form solutions of queueing network models (QNM's). It is therefore, necessary to employ credible approximate techniques for solving QNM's with priority classes. The principle of maximum entropy (ME) is a method of inference for estimating a probability distribution given prior information in the form of expected values. This principle is applied, based on marginal utilisation, mean queue length and idle state probability constraints, to characterise new product-form approximations for general open and closed QNM's with priority (preemptive-resume, non-preemtive head-of-line) and non-priority (first-come-first-served, processor-sharing, last-come-first-served with, or without preemtion) servers. The ME solutions are interpreted in terms of a decomposition of the original network into individual stable GIG11 queueing stations with assumed renewal arrival processes. These solutions are implemented by making use of the generalised exponential (GE) distributional model to approximate the interarrival-time and service-time distributions in the network. As a consequence the ME queue length distribution of the stable GE/GEzl priority queue, subject to mean value constraints obtained via classical queueing theory on bulk queues, is used as a 'building block' together with corresponding universal approximate flow formulae for the analysis of general QNM's with priorities. The credibility of the ME method is demonstrated with illustrative numerical examples and favourable comparisons against exact, simulation and other approximate methods are made. / Algerian government

Most used security mechanisms in high-speed networks have been adopted without adequate quantification of their impact on performance degradation. Appropriate quantitative network models may be employed for the evaluation and prediction of ¿optimal¿ performance vs. security trade-offs. Several quantitative models introduced in the literature are based on queueing networks (QNs) and generalised stochastic Petri nets (GSPNs). However, these models do not take into consideration Performance Engineering Principles (PEPs) and the adverse impact of traffic burstiness and security protocols on performance. The contributions of this thesis are based on the development of an effective quantitative methodology for the analysis of arbitrary QN models and GSPNs through discrete-event simulation (DES) and extended applications into performance vs. security trade-offs involving infrastructure and infrastructure-less high-speed networks under bursty traffic conditions. Specifically, investigations are carried out focusing, for illustration purposes, on high-speed network routers subject to Access Control List (ACL) and also Robotic Ad Hoc Networks (RANETs) with Wired Equivalent Privacy (WEP) and Selective Security (SS) protocols, respectively. The Generalised Exponential (GE) distribution is used to model inter-arrival and service times at each node in order to capture the traffic burstiness of the network and predict pessimistic ¿upper bounds¿ of network performance. In the context of a router with ACL mechanism representing an infrastructure network node, performance degradation is caused due to high-speed incoming traffic in conjunction with ACL security computations making the router a bottleneck in the network. To quantify and predict the trade-off of this degradation, the proposed quantitative methodology employs a suitable QN model consisting of two queues connected in a tandem configuration. These queues have single or quad-core CPUs with multiple-classes and correspond to a security processing node and a transmission forwarding node. First-Come-First-Served (FCFS) and Head-of-the-Line (HoL) are the adopted service disciplines together with Complete Buffer Sharing (CBS) and Partial Buffer Sharing (PBS) buffer management schemes. The mean response time and packet loss probability at each queue are employed as typical performance metrics. Numerical experiments are carried out, based on DES, in order to establish a balanced trade-off between security and performance towards the design and development of efficient router architectures under bursty traffic conditions. The proposed methodology is also applied into the evaluation of performance vs. security trade-offs of robotic ad hoc networks (RANETs) with mobility subject to Wired Equivalent Privacy (WEP) and Selective Security (SS) protocols. WEP protocol is engaged to provide confidentiality and integrity to exchanged data amongst robotic nodes of a RANET and thus, to prevent data capturing by unauthorised users. WEP security mechanisms in RANETs, as infrastructure-less networks, are performed at each individual robotic node subject to traffic burstiness as well as nodal mobility. In this context, the proposed quantitative methodology is extended to incorporate an open QN model of a RANET with Gated queues (G-Queues), arbitrary topology and multiple classes of data packets with FCFS and HoL disciplines under bursty arrival traffic flows characterised by an Interrupted Compound Poisson Process (ICPP). SS is included in the Gated-QN (G-QN) model in order to establish an ¿optimal¿ performance vs. security trade-off. For this purpose, PEPs, such as the provision of multiple classes with HoL priorities and the availability of dual CPUs, are complemented by the inclusion of robot¿s mobility, enabling realistic decisions in mitigating the performance of mobile robotic nodes in the presence of security. The mean marginal end-to-end delay was adopted as the performance metric that gives indication on the security improvement. The proposed quantitative methodology is further enhanced by formulating an advanced hybrid framework for capturing ¿optimal¿ performance vs. security trade-offs for each node of a RANET by taking more explicitly into consideration security control and battery life. Specifically, each robotic node is represented by a hybrid Gated GSPN (G-GSPN) and a QN model. In this context, the G-GSPN incorporates bursty multiple class traffic flows, nodal mobility, security processing and control whilst the QN model has, generally, an arbitrary configuration with finite capacity channel queues reflecting ¿intra¿-robot (component-to-component) communication and ¿inter¿-robot transmissions. Two theoretical case studies from the literature are adapted to illustrate the utility of the QN towards modelling ¿intra¿ and ¿inter¿ robot communications. Extensions of the combined performance and security metrics (CPSMs) proposed in the literature are suggested to facilitate investigating and optimising RANET¿s performance vs. security trade-offs. This framework has a promising potential modelling more meaningfully and explicitly the behaviour of security processing and control mechanisms as well as capturing the robot¿s heterogeneity (in terms of the robot architecture and application/task context) in the near future (c.f. [1]. Moreover, this framework should enable testing robot¿s configurations during design and development stages of RANETs as well as modifying and tuning existing configurations of RANETs towards enhanced ¿optimal¿ performance and security trade-offs. / Ministry of Higher Education in Libya and the Libyan Cultural Attaché bureau in London

No description available.

Modelling is an important technique in the comprehension and management of complex systems. Queueing network models capture most relevant information from computer system and network behaviour. The construction and resolution of these models is constrained by many factors. Approximations contain detail lost for exact solution and/or provide results at lower cost than simulation. Information at the resource and interactive command level is gathered with monitors under ULTRIX'. Validation studies indicate central processor service times are highly variable on the system. More pessimistic predictions assuming this variability are in part verified by observation. The utility of the Generalised Exponential (GE) as a distribution parameterised by mean and variance is explored. Small networks of GE service centres can be solved exactly using methods proposed for Generalised Stochastic Petri Nets. For two centre. systems of GE type a new technique simplifying the balance equations is developed. A very efficient "building bglloocbka"l. is presented for exactly solving two centre systems with service or transfer blocking, Bernoulli feedback and load dependent rate, multiple GE servers. In the tandem finite buffer algorithm the building block illustrates problems encountered modelling high variability in blocking networks. A parametric validation study is made of approximations for single class closed networks of First-Come-First-Served (FCFS) centres with general service times. The multiserver extension using the building block is validated. Finally the Maximum Entropy approximation is extended to FCFS centres with multiple chains and implemented with computationally efficient convolution.

The traffic signal affects the life of virtually everyone every day. The effectiveness of signal systems can reduce the incidence of delays, stops, fuel consumption, emission of pollutants, and accidents. The problems related to rapid growth in traffic congestion call for more effective traffic signalization using robust feedback control methodology. Online traffic-responsive signalization is based on real-time traffic conditions and selects cycle, split, phase, and offset for the intersection according to detector data. A robust traffic feedback control begins with assembling traffic demands, traffic facility supply, and feedback control law for the existing traffic operating environment. This information serves the input to the traffic control process which in turn provides an output in terms of the desired performance under varying conditions. Traffic signalization belongs to a class of hybrid systems since the differential equations model the continuous behavior of the traffic flow dynamics and finite-state machines model the discrete state changes of the controller. A complicating aspect, due to the state-space constraint that queue lengths are necessarily nonnegative, is that the continuous-time system dynamics is actually the projection of a smooth system of ordinary differential equations. This also leads to discontinuities in the boundary dynamics of a sort common in queueing problems. The project is concerned with the design of a feedback controller to minimize accumulated queue lengths in the presence of unknown inflow disturbances at an isolated intersection and a traffic network with some signalized intersections. A dynamical system has finite L₂-gain if it is dissipative in some sense. Therefore, the H<SUB>infinity</SUB>-control problem turns to designing a controller such that the resulting closed loop system is dissipative, and correspondingly there exists a storage function. The major contributions of this thesis include 1) to propose state space models for both isolated multi-phase intersections and a class of queueing networks; 2) to formulate H<SUB>infinity</SUB> problems for the control systems with persistent disturbances; 3) to present the projection dynamics aspects of the problem to account for the constraints on the state variables; 4) formally to study this problem as a hybrid system; 5) to derive traffic-actuated feedback control laws for the multi-phase intersections. Though we have mathematically presented a robust feedback solution for the traffic signalization, there still remains some distance before the physical implementation. A robust adaptive control is an interesting research area for the future traffic signalization. / Ph. D.

Modelling is an important technique in the comprehension and management of complex systems. Queueing network models capture most relevant information from computer system and network behaviour. The construction and resolution of these models is constrained by many factors. Approximations contain detail lost for exact solution and/or provide results at lower cost than simulation. Information at the resource and interactive command level is gathered with monitors under ULTRIX'. Validation studies indicate central processor service times are highly variable on the system. More pessimistic predictions assuming this variability are in part verified by observation. The utility of the Generalised Exponential (GE) as a distribution parameterised by mean and variance is explored. Small networks of GE service centres can be solved exactly using methods proposed for Generalised Stochastic Petri Nets. For two centre. systems of GE type a new technique simplifying the balance equations is developed. A very efficient "building bglloocbka"l. is presented for exactly solving two centre systems with service or transfer blocking, Bernoulli feedback and load dependent rate, multiple GE servers. In the tandem finite buffer algorithm the building block illustrates problems encountered modelling high variability in blocking networks. ': . _. A parametric validation study is made of approximations for single class closed networks of First-Come-First-Served (FCFS) centres with general service times. The multiserver extension using the building block is validated. Finally the Maximum Entropy approximation is extended to FCFS centres with multiple chains and implemented with computationally efficient convolution.

整合電腦及通訊網路技術之分散式系統(Digtributed System)，係將分散各地的電腦 系統及相關的資訊設備透過通訊網路連接在一起，以形成能夠相互效換資訊，分享資 源，並具備分散式處理能力的系統。由於電腦及通訊網路技術突破性的進展，在許多 情況下，已使分散式系統較傳統的集中式系統具有低成本、高可靠度、容易擴充、效 能較佳等優勢。 本研究根據分散式系統的基本架構，使用排隊網路(Queueing Network)分析技術，建 立一套一般性的分散式系統模式，此模式可用以評估分散式系統運作之效能(Perfor- mance)，探討影響分散式系統效能的因素。同時，本研究進一步利用系統模擬(Syst- em Simulation)技術分析分散式系統模式，並進行分析結果的比較與驗證，以做為規 劃與設計分散式系統的參考依據。為說明其應用，我們並以校園線上即時選課資訊網 路系統為例，找出影響其效能的主要因素及可接受的設計方案，以做為校園資訊網路 整體系統架構設計決策的參考依據。 本研究之預期貢獻主要在於提供一套簡單經濟且具有相當程度準確性的方法，藉以模 擬、預測或評估分散式系統之行為與效能，這套方法可以廣泛應用在各種不同組態下 的分散式系統。

The performance modelling of large-scale systems using discrete-state approaches is fundamentally hampered by the well-known problem of state-space explosion, which causes exponential growth of the reachable state space as a function of the number of the components which constitute the model. Because they are mapped onto continuous-time Markov chains (CTMCs), models described in the stochastic process algebra PEPA are no exception. This thesis presents a deterministic continuous-state semantics of PEPA which employs ordinary differential equations (ODEs) as the underlying mathematics for the performance evaluation. This is suitable for models consisting of large numbers of replicated components, as the ODE problem size is insensitive to the actual population levels of the system under study. Furthermore, the ODE is given an interpretation as the fluid limit of a properly defined CTMC model when the initial population levels go to infinity. This framework allows the use of existing results which give error bounds to assess the quality of the differential approximation. The computation of performance indices such as throughput, utilisation, and average response time are interpreted deterministically as functions of the ODE solution and are related to corresponding reward structures in the Markovian setting. The differential interpretation of PEPA provides a framework that is conceptually analogous to established approximation methods in queueing networks based on meanvalue analysis, as both approaches aim at reducing the computational cost of the analysis by providing estimates for the expected values of the performance metrics of interest. The relationship between these two techniques is examined in more detail in a comparison between PEPA and the Layered Queueing Network (LQN) model. General patterns of translation of LQN elements into corresponding PEPA components are applied to a substantial case study of a distributed computer system. This model is analysed using stochastic simulation to gauge the soundness of the translation. Furthermore, it is subjected to a series of numerical tests to compare execution runtimes and accuracy of the PEPA differential analysis against the LQN mean-value approximation method. Finally, this thesis discusses the major elements concerning the development of a software toolkit, the PEPA Eclipse Plug-in, which offers a comprehensive modelling environment for PEPA, including modules for static analysis, explicit state-space exploration, numerical solution of the steady-state equilibrium of the Markov chain, stochastic simulation, the differential analysis approach herein presented, and a graphical framework for model editing and visualisation of performance evaluation results.