Este trabalho apresenta uma proposta de Arquitetura Orientada a Serviço para desenvolvimento de aplicações com restrições temporais, isto é, aplicações em que o tempo de resposta a uma requisição deve respeitar limites máximos. No desenvolvimento da arquitetura proposta foram considerados os modelos de filas com um único servidor e com múltiplos servidores, por meio da utilização de serviços redundantes e do escalonamento de requisições para melhoria do determinismo no tempo de resposta das requisições efetuadas. Para avaliação da arquitetura proposta foi construído um sistema de testes de forma a ser observado o comportamento do tempo de resposta das requisições em função do número de servidores disponíveis e sua respectiva taxa de utilização. Os resultados obtidos indicam que é possível obter um aumento no determinismo do tempo de resposta das requisições efetuadas (diminuição da dispersão de valores), tendo sido obtidos resultados semelhantes para os dois algoritmos de escalonamento utilizados: por ordem de chegada das requisições e SRPT (Shortest Remaining Processing Time). / This thesis presents a proposal for a Service Oriented Architecture applied to development of time constrained systems, where the timeliness of the results is a major requirement. The development is based on the queuing theory (models using one and multiple servers) and requests scheduling to improve response time determinism. In order to verify the proposal, a test system had been developed to observe the dynamic behavior of the requests response time dispersion according to the number of servers available and associated processing rate. The results obtained show an improvement over the request response time determinism and almost similar performance for the two scheduling algorithms used: request arrival order and SRPT (Shortest Remaining Processing Time).

by Tang Chi Nang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 104-[109]). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Gaussian elimination --- p.2 / Chapter 1.1.1 --- Numerical stability --- p.2 / Chapter 1.2 --- Block Gaussian elimination --- p.3 / Chapter 1.2.1 --- Numerical stability --- p.4 / Chapter 1.3 --- Elimination graph --- p.4 / Chapter 1.4 --- Elimination ordering --- p.5 / Chapter 1.5 --- Computation and storage requirement --- p.6 / Chapter 1.6 --- Outline of the thesis --- p.7 / Chapter 2 --- Weighted graph elimination --- p.8 / Chapter 2.1 --- Weighted elimination graph --- p.8 / Chapter 2.2 --- Sparse Gaussian elimination --- p.9 / Chapter 2.3 --- Computation and storage requirement --- p.12 / Chapter 2.3.1 --- Computation requirement --- p.12 / Chapter 2.3.2 --- Storage requirement --- p.14 / Chapter 2.4 --- Elimination ordering --- p.15 / Chapter 2.5 --- Repeated structure --- p.18 / Chapter 3 --- Main theory --- p.21 / Chapter 3.1 --- Motivation --- p.21 / Chapter 3.2 --- Notations --- p.22 / Chapter 3.2.1 --- Connectivity --- p.23 / Chapter 3.2.2 --- Separator --- p.23 / Chapter 3.2.3 --- Equivalence --- p.24 / Chapter 3.3 --- Repetition separator --- p.25 / Chapter 3.4 --- Repetition elimination process --- p.30 / Chapter 3.5 --- Multiple Separators --- p.32 / Chapter 3.6 --- Feasibility --- p.33 / Chapter 3.6.1 --- Two-separator case --- p.34 / Chapter 3.6.2 --- General case --- p.39 / Chapter 3.6.3 --- Successive repetition elimination process (SREP) --- p.41 / Chapter 3.7 --- Generalized repetition elimination process --- p.42 / Chapter 3.7.1 --- Extra edges --- p.42 / Chapter 3.7.2 --- Acyclic edges --- p.43 / Chapter 3.7.3 --- Generalized repetition separator --- p.45 / Chapter 4 --- Application in queueing analysis --- p.52 / Chapter 4.1 --- Markov Chain Reduction Principle --- p.54 / Chapter 4.1.1 --- Numerical stability --- p.57 / Chapter 4.2 --- Multi-class MMPP/M/1/L queue --- p.57 / Chapter 4.2.1 --- Single-class case (QBD case) --- p.58 / Chapter 4.2.2 --- Preemptive LCFS case --- p.63 / Chapter 4.2.3 --- Non-preemptive LCFS case --- p.70 / Chapter 4.2.4 --- FCFS case --- p.72 / Chapter 4.2.5 --- Extension to phase type service time --- p.77 / Chapter 4.3 --- 2-class priority system --- p.77 / Chapter 5 --- Choosing the right algorithm --- p.85 / Chapter 5.1 --- MMPP/M/1/L system with bursty arrival --- p.86 / Chapter 5.1.1 --- Algorithm Comparison --- p.89 / Chapter 5.1.2 --- Numerical Examples --- p.90 / Chapter 5.2 2 --- -class priority system --- p.90 / Chapter 5.2.1 --- Algorithm Comparison --- p.95 / Chapter 5.2.2 --- Numerical Examples --- p.95 / Chapter 5.3 --- Conclusion --- p.95 / Chapter 6 --- Conclusion --- p.98 / Chapter 6.1 --- Further research --- p.99 / Chapter A --- List of frequently-used notations --- p.101 / Chapter A.l --- System of equations and Digraph --- p.101 / Chapter A.2 --- General-purpose functions --- p.102 / Chapter A.3 --- Single repetition separator --- p.102 / Chapter A.4 --- Sequence of repetition separators --- p.103 / Chapter A.5 --- Compatibility --- p.103 / Bibliography --- p.104

Thesis. 1977. M.S.--Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography : leaf 188. / M.S.

Thesis. 1977. M.S.--Massachusetts Institute of Technology. Dept. of Civil Engineering. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Includes bibliographical references. / M.S.

This thesis is concerned with addressing operational issues in two types of dynamic markets where queueing plays an important role: limit order books (financial industry), and dynamic matching markets (residential real estate). We first study the smart order routing decisions of investors in fragmented limit order book markets and the implications on the market dynamics. In modern equity markets, participants have a choice of many exchanges at which to trade. Exchanges typically operate as electronic limit order books operating under a “price-time” priority rule and, in turn, can be modeled as multi-class FIFO queueing systems. A market with multiple exchanges can be thought as a decentralized, parallel queueing system. Heterogeneous traders that submit limit orders select the exchange to place their orders by trading off delays until their order may fill against financial considerations. Simultaneously, traders that submit market orders select the exchange to direct their orders. These market orders trigger instantaneous service completions of queued limit orders. Taking into account the effect of investors’ order routing decisions, we find that the equilibrium of this decentralized market exhibits a state space collapse property. The predicted dimension reduction is the result of high-frequency order routing decisions that essentially couple the dynamics across exchanges. Analyzing a TAQ dataset for a sample of stocks over a one month period, we find empirical support for the predicted state space collapse. In the second part of this thesis, we model an electronic limit order book as a multi-class queueing system under fluid dynamics, and formulate and solve a problem of limit and market order placement to optimally buy a block of shares over a short, predetermined time horizon. Using the structure of the optimal execution policy, we identify microstructure variables that affect trading costs over short time horizons and propose a resulting microstructure-based model of market impact costs. We use a proprietary data set to estimate this cost model, and highlight its insightful structure and increased accuracy over conventional (macroscopic) market impact models that estimate the cost of a trade based on its normalized size but disregarding measurements of limit order book variables. In the third part of this thesis, we study the residential real estate markets as dynamic matching systems with an emphasis on their microstructure. We propose a stylized microstructure model and analyze the market dynamics and its equilibrium under the simplifying approximation where buyers and sellers use linear bidding strategies. We motivate and characterize this near closed-form approximation of the market equilibrium, and show that it is asymptotically accurate. We also provide numerical evidence in support of this approximation. Then with the gained tractability, we characterize steady-state properties such as market depth, price dispersion, and anticipated delays in selling or buying a unit. We characterize congestion and matching patterns for sellers and buyers, taking into account market dynamics, heterogeneity, and supply and demand imbalance manifested in the competition among buyers and sellers. Furthermore, we show the effects of market primitives with comparative statics results.

In this dissertation, we develop the theory of the periodic Little's law (PLL) as well as discussing one of its applications. As extensions of the famous Little's law, the PLL applies to the queueing systems where the underlying processes are strictly or asymptotically periodic. We give a sample-path version, a steady-state stochastic version and a central-limit-theorem version of the PLL in the first part. We also discuss closely related issues such as sufficient conditions for the central-limit-theorem version of the PLL and the weak convergence in countably infinite dimensional vector space which is unconventional in queueing theory. The PLL provides a way to estimate the occupancy level indirectly. We show how to construct a real-time predictor for the occupancy level inspired by the PLL as an example of its applications, which has better forecasting performance than the direct estimators.

Thesis. 1975. Ph.D.--Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. / Vita. / Bibliography: leaves 187-192. / Ph.D.

Optical buffers are essential components of future optical switches for resolving contentions among arriving packets. Currently, optical buffers are composed of Fiber Delay Lines (FDL). Unlike the conventional electronic buffer, optical buffer only has finite time resolution, which introduces a void period between two successive buffered packets. The void period leads to service interruptions and deteriorates the buffer performance. We develop a queueing system with exceptional service for the first packet in each busy period to model the buffer behavior. For the first time, the closed-form expressions of packet blocking probability and mean delay of optical buffer are derived. We show that the packet blocking probability can be minimized by finding the optimal FDL time granularity. This optimal granularity is neither sensitive to packet length distribution, nor sensitive to the buffer length, it is mainly determined by the traffic load. / Service interruption is a special case of varying service rate. A current trend in wireless communication is to enable devices to operate using many different transmission rates. This motivates us to develop the queueing models with varying service rate. We apply the continuous time Markov chain to characterize the service rate varying process, and develop a queueing system with Markov-modulated service rate. In this kind of problem, due to the complex interaction between the rate varying process and packet arrival process, it is hard to characterize the server state evolvement; this makes it difficult to get an analytical solution, even the server only has two service rates. To escape the trap, first, we develop a discrete time Markov chain to model the server state transition process, which makes our problem to be easily manipulated. Second, apart from the previous methods, we concentrate on the moments of the packet number in system. We find the recursive relationship between the moments of packet number, this fundamental relationship widely exists in the birth-death queue systems. Our results provide a new methodology to the design of communication systems with varying service rate. / This thesis is aimed to study the interaction between service interruption and the operation of communication systems, and develop analytical methods to help the design and optimization of communication systems with interrupted services. Our work are focused on two systems: optical buffer and wireless sensor network. The common ground of these two problems is they both present the features of service interruption. / Wireless sensor network is an ad hoc network consisting of hundreds of sensor nodes equipped with limited power sources, transmission range and functionality. A simple and effective way to save energy and prolong the network lifetime is to let the nodes interrupt their sensing and data transmission process, enter sleep mode randomly. However, sleep mode corresponds to low power consumption as well as to reduced network capacity, increased latency and slowed system response. We develop a queueing model with server shutting down in a varying neighborhood to model the behavior of sensor nodes, Combining the node queueing model and the network flow balance model, we construct an analytical framework to model the network performance, derive the network capacity, packet delivery delay and node responsive property. We also develop a node power consumption model, which takes the node sleep to active transition frequency into consideration. Our results demonstrate that the sleep/active dynamics produces the predominant impact on the average power consumption and packet delay, and properly choosing the time scale of sleep/active cycle is vital to design a power-efficient sensor network. / Liu Jianming. / "Apr. 2006." / Adviser: Tony Tong Lee. / Source: Dissertation Abstracts International, Volume: 67-11, Section: B, page: 6623. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (p. 109-117). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Este trabalho apresenta uma proposta de Arquitetura Orientada a Serviço para desenvolvimento de aplicações com restrições temporais, isto é, aplicações em que o tempo de resposta a uma requisição deve respeitar limites máximos. No desenvolvimento da arquitetura proposta foram considerados os modelos de filas com um único servidor e com múltiplos servidores, por meio da utilização de serviços redundantes e do escalonamento de requisições para melhoria do determinismo no tempo de resposta das requisições efetuadas. Para avaliação da arquitetura proposta foi construído um sistema de testes de forma a ser observado o comportamento do tempo de resposta das requisições em função do número de servidores disponíveis e sua respectiva taxa de utilização. Os resultados obtidos indicam que é possível obter um aumento no determinismo do tempo de resposta das requisições efetuadas (diminuição da dispersão de valores), tendo sido obtidos resultados semelhantes para os dois algoritmos de escalonamento utilizados: por ordem de chegada das requisições e SRPT (Shortest Remaining Processing Time). / This thesis presents a proposal for a Service Oriented Architecture applied to development of time constrained systems, where the timeliness of the results is a major requirement. The development is based on the queuing theory (models using one and multiple servers) and requests scheduling to improve response time determinism. In order to verify the proposal, a test system had been developed to observe the dynamic behavior of the requests response time dispersion according to the number of servers available and associated processing rate. The results obtained show an improvement over the request response time determinism and almost similar performance for the two scheduling algorithms used: request arrival order and SRPT (Shortest Remaining Processing Time).

Mobile cloud computing is a way of delegating complex algorithms from a mobile device to the cloud to complete the tasks quickly and save energy on the mobile device. However, the cloud may not be available or suitable for helping all the time. For example, in a battlefield scenario, the cloud may not be reachable. This work considers neighbouring devices as alternatives to the cloud for offloading computation and presents three key contributions, namely a comprehensive investigation of the trade-off between computation and communication, Multi-Objective Optimisation based approach to offloading, and Queuing Theory based algorithms that present the benefits of offloading to neighbours. Initially, the states of neighbouring devices are considered to be known and the decision of computation offloading is proposed as a multi-objective optimisation problem. Novel Pareto optimal solutions are proposed. The results on a simulated dataset show up to 30% increment in performance even when cloud computing is not available. However, information about the environment is seldom known completely. In Chapter 5, a realistic environment is considered such as delayed node state information and partially connected sensors. The network of sensors is modelled as a network of queues (Open Jackson network). The offloading problem is posed as minimum cost problem and solved using Linear solvers. In addition to the simulated dataset, the proposed solution is tested on a real computer vision dataset. The experiments on the random waypoint dataset showed up to 33% boost on performance whereas in the real dataset, exploiting the temporal and spatial distribution of the targets, a significantly higher increment in performance is achieved.