In this thesis, we study the queueing systems with heterogeneous servers and service rate uncertainty under the Halfin-Whitt heavy traffic regime. First, we analyse many server queues with abandonments when service rates are i.i.d. random variables. We derive a diffusion approximation using a novel method. The diffusion has a random drift, and hence depending on the realisations of service rates, the system can be in Quality Driven (QD), Efficiency Driven (ED) or Quality-Efficiency-Driven (QED) regime. When the system is under QD or QED regime, the abandonments are negligible in the fluid limit, but when it is under ED regime, the probability of abandonment will converge to a non-zero value. We then analyse the optimal staffing levels to balance holding costs with staffing costs combining these three regimes. We also analyse how the variance of service rates influence abandonment rate. Next, we focus on the state space collapse (SSC) phenomenon. We prove that under some assumptions, the system process will collapse to a lower dimensional process without losing essential information. We first formulate a general method to prove SSC results inside pools for heavy traffic systems using the hydrodynamic limit idea. Then we work on the SSC in multi-class queueing networks under the Halfin-Whitt heavy traffic when service rates are i.i.d. random variables within pools. For such systems, exact analysis provides limited insight on the general properties. Alternatively, asymptotic analysis by diffusion approximation proves to be effective. Further, limit theorems, which state the diffusively scaled system process weakly converges to a diffusion process, are usually the central part in such asymptotic analysis. The SSC result is key to proving such a limit. We conclude by giving examples on how SSC is applied to the analysis of systems.

No description available.

abstract: This dissertation presents a novel algorithm for recovering missing values of co-evolving time series with partial embedded network information. The idea is to connect two sources of data through a shared low dimensional latent space. The proposed algorithm, named NetDyna, is an Expectation-Maximization algorithm, and uses the Kalman filter and matrix factorization approaches to infer the missing values both in the time series and embedded network. The experimental results on real datasets, including a Motes dataset and a Motion Capture dataset, show that (1) NetDyna outperforms other state-of-the-art algorithms, especially with partially observed network information; (2) its computational complexity scales linearly with the time duration of time series; and (3) the algorithm recovers the embedded network in addition to missing time series values. This dissertation also studies a load balancing algorithm, the so called power-of-two-choices(Po2), for many-server systems (with N servers) and focuses on the convergence of stationary distribution of Po2 in the both light and heavy traffic regimes to the solution of mean-field system. The framework of Stein’s method and state space collapse (SSC) are used to analyze both regimes. In both regimes, the thesis first uses the argument of state space collapse to show that the probability of the state being far from the mean-field solution is small enough. By a simple Markov inequality, it is able to show that the probability is indeed very small with a proper choice of parameters. Then, for the state space close to the solution of mean-field model, the thesis uses Stein’s method to show that the stochastic system is close to a linear mean-field model. By characterizing the generator difference, it is able to characterize the dominant terms in both regimes. Note that for heavy traffic case, the lower and upper bound analysis of a tridiagonal matrix, which arises from the linear mean-field model, is needed. From the dominant term, it allows to calculate the coefficient of the convergence rate. In the end, comparisons between the theoretical predictions and numerical simulations are presented. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2020

abstract: This dissertation studies load balancing algorithms for many-server systems (with N servers) and focuses on the steady-state performance of load balancing algorithms in the heavy traffic regime. The framework of Stein’s method and (iterative) state-space collapse (SSC) are used to analyze three load balancing systems: 1) load balancing in the Sub-Halfin-Whitt regime with exponential service time; 2) load balancing in the Beyond-Halfin-Whitt regime with exponential service time; 3) load balancing in the Sub-Halfin-Whitt regime with Coxian-2 service time. When in the Sub-Halfin-Whitt regime, the sufficient conditions are established such that any load balancing algorithm that satisfies the conditions have both asymptotic zero waiting time and zero waiting probability. Furthermore, the number of servers with more than one jobs is o(1), in other words, the system collapses to a one-dimensional space. The result is proven using Stein’s method and state space collapse (SSC), which are powerful mathematical tools for steady-state analysis of load balancing algorithms. The second system is in even “heavier” traffic regime, and an iterative refined procedure is proposed to obtain the steady-state metrics. Again, asymptotic zero delay and waiting are established for a set of load balancing algorithms. Different from the first system, the system collapses to a two-dimensional state-space instead of one-dimensional state-space. The third system is more challenging because of “non-monotonicity” with Coxian-2 service time, and an iterative state space collapse is proposed to tackle the “non-monotonicity” challenge. For these three systems, a set of load balancing algorithms is established, respectively, under which the probability that an incoming job is routed to an idle server is one asymptotically at steady-state. The set of load balancing algorithms includes join-the-shortest-queue (JSQ), idle-one-first(I1F), join-the-idle-queue (JIQ), and power-of-d-choices (Pod) with a carefully-chosen d. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2019

L'analyse de la performance à l'état stationnaire dans de nombreux systèmes de files d'attente est complexe et les résultats sous forme explicite ne sont disponibles que dans des cas particuliers. Nous avons donc développé des approximations pour des critères de performance importants à l'état stationnaire tels que la longueur de la file d'attente, le temps d'attente et le temps de traitement total. Nous analysons d'abord la performance dans des cas à faible et fort trafic. Nous montrons ensuite comment développer une approximation basée sur une interpolation qui est valable pour n'importe quelle condition de trafic. Un avantage de l'approche proposée est qu'elle n'est pas dépendante d’un modèle particulier et donc elle peut être appliquée à d'autres modèles de files d'attente complexes. Nous appliquons cette technique pour trois modèles largement utilisés dans l'évaluation des performances des réseaux stochastiques : le modèle du supermarché, la file d'attente Discriminatory-Processor-Sharing (DPS) et la file d'attente Relative Priority (RP). Le modèle du supermarché est une file d'attente à plusieurs serveurs où lorsqu’un client arrive, deux serveurs sont choisis au hasard dans un ensemble de serveurs. La politique Join-the-Shortest-Queue (JSQ) est ensuite utilisée parmi les deux serveurs sélectionnés. DPS et RP sont deux files d'attente à plusieurs classes et à serveur unique mettant en œuvre des priorités relatives entre les clients des différentes classes. La discipline DPS sert tous les clients simultanément, tandis que RP sert un seul client à la fois de manière non-préemptive. Nous montrons que dans certains cas, l'interpolation est exacte. Nous utilisons ensuite cette approximation pour déduire comment la performance dépend des paramètres des modèles, et nous effectuons des expériences numériques illustrant la précision de l'interpolation dans un grand nombre de cas de figure / The analysis of the steady-state performance in many queuing systems is complex and closed-form results are available only in particular cases. We therefore set out to develop approximations for important performance measures in steady-state such as the queue length vector, waiting time and sojourn time. We first analyse the performance in a light-traffic and heavy-traffic regime. We then show how to develop an interpolation-based approximation that is valid for any load in the system. An advantage of the approach taken is that it is not model dependent and hence could potentially be applied to other complex queuing models. We apply this technique to three widely used models in the performance evaluation of stochastic networks: The supermarket model, the Discriminatory-Processor-Sharing (DPS) queue and the Relative Priority (RP) queue. The supermarket model is a multi-server queue where upon arrival of a customer two servers are selected at random from the available pool of servers. The Join-the-Shortest-Queue policy is then used in isolation with these two servers. DPS and RP are both single-server multi-class queues that implement relative priorities among customers of the various classes. The DPS discipline serves all customers simultaneously while RP serves one customer at a time in a non-preemptive way. We show that in some instances the interpolation approximation is exact. We then use the approximation to draw structural insights onto the performance of the system, and we carry out numerical experiments that illustrate that the interpolation approximation is accurate over a wide range of parameters

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第20517号 / 情博第645号 / 新制||情||111(附属図書館) / 京都大学大学院情報学研究科システム科学専攻 / (主査)教授 髙橋 豊, 教授 太田 快人, 教授 大塚 敏之, 准教授 増山 博之 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Customer call centers with hundreds of agents working in parallel are ubiquitous in many industries. These systems have a large amount of daily traffic that is stochastic in nature. It becomes more and more difficult to manage a call center because of its increasingly large scale and the stochastic variability in arrival and service processes. In call center operations, customer abandonment is a key factor and may significantly impact the system performance. It must be modeled explicitly in order for an operational model to be relevant for decision making. In this thesis, a large-scale call center is modeled as a queue with many parallel servers. To model the customer abandonment, each customer is assigned a patience time. When his waiting time for service exceeds his patience time, a customer abandons the system without service. We develop analytical and numerical tools for analyzing such a queue. We first study a sequence of G/G/n+GI queues, where the customer patience times are independent and identically distributed (iid) following a general distribution. The focus is the abandonment and the queue length processes. We prove that under certain conditions, a deterministic relationship holds asymptotically in diffusion scaling between these two stochastic processes, as the number of servers goes to infinity. Next, we restrict the service time distribution to be a phase-type distribution with d phases. Using the aforementioned asymptotic relationship, we prove limit theorems for G/Ph/n+GI queues in the quality- and efficiency-driven (QED) regime. In particular, the limit process for the customer number in each phase is a d-dimensional piecewise Ornstein-Uhlenbeck (OU) process. Motivated by the diffusion limit process, we propose two approximate models for a GI/Ph/n+GI queue. In each model, a d-dimensional diffusion process is used to approximate the dynamics of the queue. These two models differ in how the patience time distribution is built into them. The first diffusion model uses the patience time density at zero and the second one uses the entire patience time distribution. We also develop a numerical algorithm to analyze these diffusion models. The algorithm solves the stationary distribution of each model. The computed stationary distribution is used to estimate the queue's performance. A crucial part of this algorithm is to choose an appropriate reference density that controls the convergence of the algorithm. We develop a systematic approach to constructing a reference density. With the proposed reference density, the algorithm is shown to converge quickly in numerical experiments. These experiments also show that the diffusion models are good approximations of queues with a moderate to large number of servers.

No description available.

This dissertation focuses on quantifying the effects of multi-user co-channel interference for an avionic communication system operating in a heavy-traffic aeronautical mobile environment and proposes advanced interference cancellation techniques to mitigate the interference. The dissertation consists of two parts. The first part of the work investigates the use of a visualization method to quantify and characterize the multi-user co-channel interference (multiple access interference) effects impinging on an avionic communication system. The interference is caused by complex interactions of thousands of RF signals transmitted from thousands of aircraft; each attempts to access a common communication channel, which is governed by a specific channel contention access protocol. The visualization method transforms the co-channel interference, which is specified in terms of signal-overlaps (signal collisions), from a visual representation to a matrix representation for further statistical analysis. It is found that the statistical Poisson and its cumulative distribution provide the best estimates of multi-user co-channel interference. It is shown, using Monte Carlo simulation, that the co-channel interference of a victim aircraft operating in the heavy-traffic environment could result in as high as eight signal-overlaps. This constitutes to approximately 83.4% of success rate in signal detection for the entire three thousand aircraft environment using conventional FSK receiver. One key finding shows that high-quality communications, up to 98.5% success rate, is achievable if only three overlapping signals can be decoded successfully. The interference results found in the first part set the stage for interference cancellation research in the second part. The second part of the work proposes the use of advanced interference cancellation techniques, namely sequential interference cancellation (SIC) and parallel interference cancellation (PIC), as potential solutions to mitigating the interference effects. These techniques can be implemented in radio receivers to perform multi-signal decoding functionality to remove the required interferers (three overlapping signals) so that high-quality communication, as described in the first part, can be achieved. Various performance graphs are shown for B-FSK and B-PSK for both SIC and PIC techniques. One key finding is that the system performance can be improved substantially to an additional 15% in signal reception success rate by using SIC or PIC. This means that critical information transmitted from 450 aircraft (out of approximately three thousand aircraft in the environment) is preserved and successfully decoded. Multi-signal decoding using these interference cancellation receivers comes at a small penalty of 2 - 4.5 dBs in Eb/No when sufficient signal-to-interference (SIR) ratio (7-12 dB) is provided. / Ph. D.

In Sweden, there has been an long term effort to allow as heavy traffic as possible, provided thatthe road network can handle it. This is because heavy traffic offers a competitive advantage withsocio-economic gains. In July 2018, the Swedish Transport Administration made 12 percent ofthe Swedish road network avaliable for the new maximum vehicle weight of 74 tonnes, basedon a legislative change from 2017. It is known that heavy traffic has a negative effect on thedegradation of the road, but it prevails divided opinions on whether 74 tonnes have a greaterimpact on the degradation rate compared to previous maximum gross weights of 64 tonnes.The 74 tonne vehicles have the same allowed axle load, which means more axles per vehicle. Some argue that an increased total load and more axles affect the degradation associated withtime-dependent material properties, while others argue that 74 tonnes mean fewer heavy vehiclesoverall, and thus should have a positive impact on the road’s lifespan. The construction companySkanska therefore requests a statistical analysis that enables to nuance the effects that heavytraffic has on the Swedish state road network. Since there is very limited data on the effect of 74 tonne traffic, this Master thesis instead focuseson modeling heavy traffic in general in order to be able to draw conclusions on which variablesare significant for a road’s lifetime. The method used is survival analysis where the lifetimeof the road is defined as the time between two maintenance treatments. The model selectedis the semi-parametric ’Cox Proportional Hazard Model’. The model is fitted with data froman open source database called LTPP (Long Term Pavement Performance) which is providedby the National Road and Transport Research Institute (VTI). The result of the modeling ispresented with hazard ratios, which is the relative risk that a road will require maintance atthe next time stamp compared to a reference category. The covariates that turned out to besignificant for a road’s lifetime and thus are included in the model are; lane width, undergroundtype, speed limit, asphalt layer thickness, bearing layer thickness and proportion of heavy traffic. Survival curves estimated by the model are also presented. In addition, a sensitivity analysis ismade by exploring survival curves estimated for different scenarios, with different combinationsof covariate levels.The results is then compared with previous studies on the subject. The most interesting finding isa case study from Finland since Finland allow 76 tonne vehicles since 2013. In the comparison,the model’s significant variables are confirmed, but the significance of precipitation and thenumber of axes for a roads lifetime is also highlighted