Browsing by Subject "Queuing theory"
Now showing 1 - 4 of 4
- Results Per Page
- Sort Options
Item Fluid models for Internet design and simulation(2006) Yi, Yung; Shakkottai, SanjayOver the past decade, fluid models have been widely used, and shown to be efficient and accurate in the modeling, analysis, and design of the Internet. In literature, much of this work has focused on the design of end-host controllers and control algorithms at routers (marking functions) for the stable end-to-end operation over the Internet. However, there is a significant fraction of uncontrolled flows such as real-time video and audio flows in the Internet, and the effect of those uncontrolled flows on the design and simulation of the Internet cannot be ignored in the use of fluid models. In this thesis, we first explore the use of time-scale decomposition of the end-systems and queueing dynamics at the intermediate routers. Based on this time-scale decomposition study, for a queue-based router model we develop an equivalent fluid model that depends only on the instantaneous traffic rate. The main intuition for such a rate based model is that there exists a sufficient randomness in the Internet due to uncontrolled flows. We next study how the rate based model can be practically used for a Internet simulation/emulation with a mixture of controlled and uncontrolled flows. We address this by developing a hybrid network simulator – FluNet – which combines actual network hardware (routers and switches) at the network edge, and rate based fluid models within the network core. Second, we study the effects of these uncontrolled flows on the design choices for the end controllers and marking function. Current research has focused on the design of controllers and network algorithms with the objective of stability and convergence of the transmission rates. However, an important criterion that has not received much attention is the design of the controllers with the objective of providing QoS guarantees to real-time flows that share the links with the controlled flows. In this thesis, we study the design rules for network congestion controllers with the objective of providing QoS support for such real-time flows. Third, while much of the research based on fluid models has focused on wireline networks, a growing area of research is that of wireless multi-hop networks. The main issue in using fluid models in this context is that the MAC (media access control) is a “discrete” entity, as a result of which fluid models have not been commonly used. In this work, we first investigate fluid models for MAC and appropriate models for congestion control over multi-hop wireless networks. Based on an optimization framework with constraints that arise from the multi-hop wireless network, we propose hop-by-hop congestion control algorithms, and study their properties on the stability and peak buffer requirement. Fourth, we study a realistic MAC protocol, which leads to the appropriate fluid models used for analysis and design of networking algorithms (i.e., congestion control) over wireless multi-hop networks. In this work, we study a distributed randomized MAC protocol that converges an optimal schedule with a simple one-hop synchronized contention signaling mechanism. Furthermore, by simulation and analysis, we show that the proposed protocol adapts well to slowly-varying load/topology changes.Item Scheduling and control of stochastic processing networks(2007-08) Adusumilli, Kranthi Mitra, 1979-; Hasenbein, John J.In this dissertation the following two control problems of different queueing systems are addressed. Service rate and Admission Control: We consider a single server system with constant Poisson arrivals subjected to both service rate and admission controls. The controller can admit or reject a customer on arrival and choose the service rate, from a fixed subset, when an arrival or departure occurs. With each control decision is associated a one time rejection cost and a cost for service. A holding cost and cost for service are continuously incurred. The holding cost is non-decreasing in the number of customers in the system and the cost for service is non-decreasing in the service rate. The objective is to minimize the long run average cost per unit time. We restrict to (state-dependent) stationary deterministic controls and derive the optimality equations. We use standard average cost dynamic programming techniques to obtain the optimality equations in terms of minimum achievable average cost. The stationary controls correspond to a threshold system state (finite or infinite) and service rates for each of the states. Customer are rejected service once the number of customers in the system is greater than or equal to the threshold. We suggest a fast scheme, based on considering incremental values of the system threshold for computing the optimal average cost and the associated optimal service rates. This is similar to initially fixing a system threshold, and choosing the optimal service rates thereafter. We establish the monotonicity of optimal service rates in terms of the queue lengths, for the original system as well as the intermediate systems. Finally, we prove that the constructed stationary optimal policy is optimal across all possible non-anticipative controls. Stochastic Scheduling under Parameter Uncertainty: We suggest a new approach to model randomness in the context of job shop scheduling. In addition to inherent randomness such as variable processing times for a job class, certain parameters, e.g. like the initial number of jobs might not be known with certainty. We consider scheduling of such a system: a stochastic job shop with parameter uncertainty. We model a situation in which the initial number of jobs and the mean processing times of jobs are uncertain. We assume that the controller has a limited ability to make certain control decisions before the initial number of jobs and processing times are revealed. Thus these decisions must be made a priori. For each server, the scheduler must choose a cycle length and the fraction of time devoted to processing each job class during a cycle. Under these assumptions the resulting optimization problem for minimizing expected makespan is a stochastic integer program. We obtain a continuous job shop model, a relaxation of the original model, by relaxing the integrality requirements. When we restrict allowable policies to satisfy certain time allocation constraints, we obtain a further relaxation called the fluid model. The optimal solution for the fluid model is shown to be optimal for the continuous job shop. The optimization problem for the fluid model is a stochastic non-linear program, which is easier to solve. Based on the optimal solution to the fluid model, we propose a scheduling heuristic. We show the asymptotic optimality of the heuristic. The optimality results is in terms the expected makespan. We also extend the asymptotic optimality results to the case when processing times are random, i.e., when the job completion process is doubly stochastic. We obtain tight bounds for makespan which hold with high probability. We also discuss an assignment problem for the single station case and suggest asymptotically optimal heuristics, which are constructed from the associated fluid model.Item Scheduling and stability analysis of Cambridge Ring(2007-05) Sampath, Balaji, 1977-; Hasenbein, John J.Multiclass queueing networks are widely used to model complex manufacturing systems and communications networks. In this dissertation we describe and analyze a multiclass queueing network model known as the Cambridge Ring. As the name suggest this network has a circular topology with unidirectional routing. In many cases the analysis of a stochastic model is a difficult task. For a few special cases of this network we show that all non-idling policies are throughput optimal for this system. One of the major differences between this work and precious literature is that we prove throughput optimality of all non-idling policies, whereas most of the previous work has been on establishing throughput optimality for a specific policy (usually First-In-First-Out). We use a macroscopic technique known as fluid model to identify optimal policies with respect to work in process. In one case we consider, the discrete scheduling policy motivated by the optimal fluid policy is indeed optimal in the discrete network. For the other special case we show by means of a deterministic counterexample that the discrete policy most naturally suggested by the fluid optimal policy may not be optimal for the queueing network. We also formulate the fluid holding cost optimization problem and present its solution for a simple version of the Cambridge Ring. Further we establish that the optimal policy under a class of policies known as "non-ejective" policies may be an idling policy. We use an example of the Cambridge Ring with a single vehicle to show that the optimal policy for this example has to be an idling policy.Item Stability and pricing of queueing models(2006) Yildirim, Utku; Hasenbein, John J.A queueing system can be described as a population of customers which from time to time utilize the resources of a service provider in order to obtain service. Since it is a difficult task to analyze a stochastic model, often macroscopic models are utilized to gain insight on high level properties of the real model. The contributions of this thesis can be summarized in three parts. In the first and second parts of the thesis, we investigate the stability of the fluid models and the relationship between the fluid and the stochastic models. In the third part, we use queueing theory to tackle a revenue management problem of a monopolistic firm. First, we investigate a fundamental property of fluid solutions in multiclass fluid networks. In [14] it is shown that if a fluid network has the finite decomposition property and is not weakly stable, then any queueing network associated with the fluid network is not rate stable. In particular, we show that the finite decomposition property holds for certain classes of two-pass fluid networks. Next, we try to characterize the intersection of stability regions of the static buffer priority service disciplines for a certain type of three station networks. The results expand the known stability region by utilizing fluid trajectories and a new methodology is proposed to identify if a service rate vector is in the aforementioned stability region or not. Finally, we investigate the pricing problem of a firm which dominates the market. In our model, there is a single server with exponential service times and arrivals follow a compound Poisson process where the number of customers in a group is a random variable. We let the firm to adjust the price as the length of the queue changes. A major difference between this research and the previous literature is that we allow group arrivals and the firm may only accept or reject customer groups as a whole. We identify the optimal acceptance policy that maximizes the revenue and show that this policy is also socially optimal.