To see the other types of publications on this topic, follow the link: Length of queue.
Dissertations / Theses on the topic 'Length of queue'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 38 dissertations / theses for your research on the topic 'Length of queue.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Hall, Susan A., and Richard C. 1943 Larson. "Using Partial Queue-Length Information to Improve the Queue Inference Engine's Performance." Massachusetts Institute of Technology, Operations Research Center, 1991. http://hdl.handle.net/1721.1/5222.
Full textAbstract:
The Queue Inference Engine (QIE) uses queue departure time data over a single congestion period to infer queue statistics. With partial queue-length information, the queue statistics become more accurate and the computational burden is reduced. We first consider the case in which we are given that the queue length never exceeded a given length L. We then consider the more general case in which we are given the times of all L-to-(L + 1) and (L + 1)-to-L queue-length transitions. We present algorithms, parallel to the QIE algorithms,for deriving the queue statistics under the new conditioning information. We also present computational results, comparing both accuracy and computation time, under the QIE and the new algorithms, for several sample runs.
2
Jagannathan, Krishna Prasanna. "Asymptotic performance of queue length based network control policies." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/62419.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (p. 199-204).<br>In a communication network, asymptotic quality of service metrics specify the probability that the delay or buffer occupancy becomes large. An understanding of these metrics is essential for providing worst-case delay guarantees, provisioning buffer sizes in networks, and to estimate the frequency of packet-drops due to buffer overflow. Second, many network control tasks utilize queue length information to perform effectively, which inevitably adds to the control overheads in a network. Therefore, it is important to understand the role played by queue length information in network control, and its impact on various performance metrics. In this thesis, we study the interplay between the asymptotic behavior of buffer occupancy, queue length information, and traffic statistics in the context of scheduling, flow control, and resource allocation. First, we consider a single-server queue and deal with the question of how often control messages need to be sent in order to effectively control congestion in the queue. Our results show that arbitrarily infrequent queue length information is sufficient to ensure optimal asymptotic decay for the congestion probability, as long as the control information is accurately received. However, if the control messages are subject to errors, the congestion probability can increase drastically, even if the control messages are transmitted often. Next, we consider a system of parallel queues sharing a server, and fed by a statistically homogeneous traffic pattern. We obtain the large deviation exponent of the buffer overflow probability under the well known max-weight scheduling policy. We also show that the queue length based max-weight scheduling outperforms some well known queue-blind policies in terms of the buffer overflow probability. Finally, we study the asymptotic behavior of the queue length distributions when a mix of heavy-tailed and light-tailed traffic flows feeds a system of parallel queues. We obtain an exact asymptotic queue length characterization under generalized max-weight scheduling. In contrast to the statistically homogeneous traffic scenario, we show that max-weight scheduling leads to poor asymptotic behavior for the light-tailed traffic, whereas a queue-blind priority policy gives good asymptotic behavior.<br>by Krishna Prasanna Jagannathan.<br>Ph.D.
3
Yamani, Jana H. (Jana Hashim). "Approximation of the transient joint queue-length distribution in tandem networks." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/85470.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2013.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 95-97).<br>This work considers an urban traffic network, and represents it as a Markovian queueing network. This work proposes an analytical approximation of the time-dependent joint queue-length distribution of the network. The challenge is to provide an accurate analytical description of between and within queue (i.e. link) dynamics, while deriving a tractable approach. In order to achieve this, we use an aggregate description of queue states (i.e. state space reduction). These are referred to as aggregate (queue-length) distributions. This reduces the dimensionality of the joint distribution. The proposed method is formulated over three different stages: we approximate the time-dependent aggregate distribution of 1) a single queue, 2) a tandem 3-queue network, 3) a tandem network of arbitrary size. The third stage decomposes the network into overlapping 3-queue sub-networks. The methods are validated versus simulation results. We then use the proposed tandem network model to solve an urban traffic signal control problem, and analyze the added value of accounting for time-dependent between queue dependency in traffic management problems for congested urban networks.<br>by Jana H. Yamani.<br>S.M.
4
Nikolaros, Ilias G. "Cross-layer design for OFDMA wireless networks with finite queue length based on game theory." Thesis, Brunel University, 2014. http://bura.brunel.ac.uk/handle/2438/10818.
Full textAbstract:
In next generation wireless networks such as 4G- LTE and WiMax, the demand for high data rates, the scarcity of wireless resources and the time varying channel conditions has led to the adoption of more sophisticated and robust techniques in PHY such as orthogonal frequency division multiplexing (OFDM) and the corresponding access technique known as orthogonal frequency division multiplexing access (OFDMA). Cross-layer schedulers have been developed in order to describe the procedure of resource allocation in OFDMA wireless networks. The resource allocation in OFDMA wireless networks has received great attention in research, by proposing many different ways for frequency diversity exploitation and system’s optimization. Many cross-layer proposals for dynamic resource allocation have been investigated in literature approaching the optimization problem from different viewpoints i.e. maximizing total data rate, minimizing total transmit power, satisfying minimum users’ requirements or providing fairness amongst users. The design of a cross-layer scheduler for OFDMA wireless networks is the topic of this research. The scheduler utilizes game theory in order to make decisions for subcarrier and power allocation to the users with the main concern being to maintain fairness as well as to maximize overall system’s performance. A very well known theorem in cooperative game theory, the Nash Bargaining Solution (NBS), is employed and solved in a close form way, resulting in a Pareto optimal solution. Two different cases are proposed. The first one is the symmetric NBS (S-NBS) where all users have the same weight and therefore all users have the same opportunity for resources and the second one, is the asymmetric NBS (A-NBS), where users have different weights, hence different priorities where the scheduler favours users with higher priorities at expense of lower priority users. As MAC layer is vital for cross-layer, the scheduler is combined with a queuing model based on Markov chain in order to describe more realistically the incoming procedure from the higher layers.
5
Bhattacharja, Bonane. "A better numerical approach for finding the steady-state waiting time and the average queue length of a system for the arithmetic GI/G/1 queue." Thesis, University of British Columbia, 2011. http://hdl.handle.net/2429/39784.
Full textAbstract:
In this research, an efficient numerical method is developed to determine the steady-state waiting time distribution of a GI/G/1 queue by solving the discrete-time version of Lindley’s equation, when the queue is bounded on a finite interval. Then, by using Little’s Formula, we calculate the stationary distribution for the total number of customers in the queue. The derivations are based on the Wiener-Hopf factorization of random walks. The method is carried out using a successive approximation method, by improving the weighted average. Finally, to prove the effectiveness of our method, we apply the algorithm for Uniform, Geometric, and Gamma distributions, to find an approximation. An analytical interpretation is also presented to find the waiting time distribution for the Geom/Geom/1 queue, which is not based on a finite interval, as an example of the GI/G/1 queue. Moreover, compare to the other related methods it has been proven that our method is numerically stable, simple, and robust.
6
Iwanowicz, Damian. "Model procesu powstawania i zmienności długości kolejki pojazdów na wlotach skrzyżowań z sygnalizacją świetlną." Rozprawa doktorska, Uniwersytet Technologiczno-Przyrodniczy w Bydgoszczy, 2018. http://dlibra.utp.edu.pl/Content/1178.
Full textAbstract:
W rozprawie doktorskiej przedstawiono najważniejsze z punktu widzenia praktycznego modele matematyczne, odnoszące się między innymi do długości kolejki pozostającej oraz do maksymalnego zasięgu kolejki pojazdów - dla dowolnie przyjętego okresu analizy. Zostały one opracowane na podstawie badań ruchu<br>The following dissertation presents the most important mathematical models from the practical point of view, relating to, inter alia, the length of the remaining queue, as well as the maximum vehicle queue reach, for any assumed analysis period. They were elaborated based on traffic research
7
Shah, Neelkamal P. "Entropy Maximisation and Queues With or Without Balking. An investigation into the impact of generalised maximum entropy solutions on the study of queues with or without arrival balking and their applications to congestion management in communication networks." Thesis, University of Bradford, 2014. http://hdl.handle.net/10454/7500.
Full textAbstract:
An investigation into the impact of generalised maximum entropy solutions on the study of queues with or without arrival balking and their applications to congestion management in communication networks
Keywords: Queues, Balking, Maximum Entropy (ME) Principle, Global Balance (GB), Queue Length Distribution (QLD), Generalised Geometric (GGeo), Generalised Exponential (GE), Generalised Discrete Half Normal (GdHN), Congestion Management, Packet Dropping Policy (PDP)
Generalisations to links between discrete least biased (i.e. maximum entropy (ME)) distribution inferences and Markov chains are conjectured towards the performance modelling, analysis and prediction of general, single server queues with or without arrival balking. New ME solutions, namely the generalised discrete Half Normal (GdHN) and truncated GdHN (GdHNT) distributions are characterised, subject to appropriate mean value constraints, for inferences of stationary discrete state probability distributions. Moreover, a closed form global balance (GB) solution is derived for the queue length distribution (QLD) of the M/GE/1/K queue subject to extended Morse balking, characterised by a Poisson prospective arrival process, i.i.d. generalised exponential (GE) service times and finite capacity, K. In this context, based on comprehensive numerical experimentation, the latter GB solution is conjectured to be a special case of the GdHNT ME distribution.
ii
Owing to the appropriate operational properties of the M/GE/1/K queue subject to extended Morse balking, this queueing system is applied as an ME performance model of Internet Protocol (IP)-based communication network nodes featuring static or dynamic packet dropping congestion management schemes. A performance evaluation study in terms of the model’s delay is carried out. Subsequently, the QLD’s of the GE/GE/1/K censored queue subject to extended Morse balking under three different composite batch balking and batch blocking policies are solved via the technique of GB. Following comprehensive numerical experimentation, the latter QLD’s are also conjectured to be special cases of the GdHNT. Limitations of this work and open problems which have arisen are included after the conclusions
8
Shah, Neelkamal Paresh. "Entropy maximisation and queues with or without balking : an investigation into the impact of generalised maximum entropy solutions on the study of queues with or without arrival balking and their applications to congestion management in communication networks." Thesis, University of Bradford, 2014. http://hdl.handle.net/10454/7500.
Full textAbstract:
An investigation into the impact of generalised maximum entropy solutions on the study of queues with or without arrival balking and their applications to congestion management in communication networks Keywords: Queues, Balking, Maximum Entropy (ME) Principle, Global Balance (GB), Queue Length Distribution (QLD), Generalised Geometric (GGeo), Generalised Exponential (GE), Generalised Discrete Half Normal (GdHN), Congestion Management, Packet Dropping Policy (PDP) Generalisations to links between discrete least biased (i.e. maximum entropy (ME)) distribution inferences and Markov chains are conjectured towards the performance modelling, analysis and prediction of general, single server queues with or without arrival balking. New ME solutions, namely the generalised discrete Half Normal (GdHN) and truncated GdHN (GdHNT) distributions are characterised, subject to appropriate mean value constraints, for inferences of stationary discrete state probability distributions. Moreover, a closed form global balance (GB) solution is derived for the queue length distribution (QLD) of the M/GE/1/K queue subject to extended Morse balking, characterised by a Poisson prospective arrival process, i.i.d. generalised exponential (GE) service times and finite capacity, K. In this context, based on comprehensive numerical experimentation, the latter GB solution is conjectured to be a special case of the GdHNT ME distribution. ii Owing to the appropriate operational properties of the M/GE/1/K queue subject to extended Morse balking, this queueing system is applied as an ME performance model of Internet Protocol (IP)-based communication network nodes featuring static or dynamic packet dropping congestion management schemes. A performance evaluation study in terms of the model’s delay is carried out. Subsequently, the QLD’s of the GE/GE/1/K censored queue subject to extended Morse balking under three different composite batch balking and batch blocking policies are solved via the technique of GB. Following comprehensive numerical experimentation, the latter QLD’s are also conjectured to be special cases of the GdHNT. Limitations of this work and open problems which have arisen are included after the conclusions.
9
Shawaly, El-Sayed Abdel-Azim. "Queue lengths and delays at oversaturated traffic signal-controlled intersections." Thesis, University of Sheffield, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.327891.
Full text
10
Xu, Ling. "Planning simulation run length in packet queues in communications networks." Thesis, Queen Mary, University of London, 2013. http://qmro.qmul.ac.uk/xmlui/handle/123456789/8712.
Full textAbstract:
Simulation is a technique of growing importance and is becoming an indispensable tool applied in various academic industries, including packet networks. Simulation provides an alternative research approach to implementing a real environment, owing to its features of scalability, exibility and ease of setup. However, simulating large-scale networks can be very time and resource consuming. It can take several days to run one long simulation experiment, which may be expensive or even unaffordable. Therefore, planning simulation is important. This research proposes to plan simulation run length through predicting the required shortest run length that approximates steady-state, in the form of mathematical and logical expressions, i.e. building an analytical model. Previously related research always focused on classical models, such as the M/M/1 queue model, M/G/1 queue model, and so on. This research expands the research base to include a packet multiplexing model of homogenous sources which is widely accepted and used. This thesis investigates different traffic types (Markovian/Pareto) and different QoS parameter (delay/losses), as well as applying them to end-to-end networks. These scenarios are analysed and expressed, in terms of different desired precision level. Final results show that run length time is well predicted using the developed analytical model, which can be a guide for simulation planning in packet networks of the present and the future. This can be of great significance for performance evaluation studies.
11
Alqahtani, Abdullah Ayed F. "Comparative Analysis of Roundabout Capacity Analysis Methods." University of Dayton / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=dayton1557252181941848.
Full text
12
Yoshigoe, Kenji. "Design and evaluation of the combined input and crossbar queued (CICQ) switch." [Tampa, Fla.] : University of South Florida, 2004. http://purl.fcla.edu/fcla/etd/SFE0000464.
Full text
13
Su, Yong-Shun, and 蘇永順. "Queue Management with Flow Number Estimation and Queue Length Feedback Control." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/93435115753975787095.
Full textAbstract:
碩士<br>國立成功大學<br>電機工程學系碩博士班<br>91<br>Many active queue management schemes such as Random Early Detection (RED) [3] [4], BLUE [2], Random Exponential Marking (REM) [5], Stabilized RED (SRED) [7], and Dynamic RED (DRED) [8] were proposed for IP routers in recent years. We evaluate the effects of parameters of queue management on the performance using 2k factorial designs. Among these systematic and environmental parameters, number of flows and Pmax are two dominate factors affecting the performance of RED queue management. Then, we propose a novel active queue management scheme, NRED, employing active flow-number estimation and queue length feedback control, which are motivated from Bloom filter and control theory, respectively. Fluctuation of queue length under NRED is smaller than any existing queue management schemes. Especially, NRED can stabilize the queue length very fast even when a lot of flows join in the competition suddenly. NRED is very suitable to be deployed in today’s networks where hot spot frequently occurs. Furthermore, delay jitter regulated by NRED is very low.
14
Cai, Yan. "Queue length based pacing of internet traffic." 2011. https://scholarworks.umass.edu/dissertations/AAI3482591.
Full textAbstract:
As the Internet evolves, there is a continued demand for high Internet bandwidth. This demand is driven partly by the widely spreading real-time video applications, such as on-line gaming, teleconference, high-definition video streaming. All-optical switches and routers have long been studied as a promising solution to the rapidly growing demand. Nevertheless, buffer sizes in all-optical switches and routers are very limited due to the challenges in manufacturing larger optical buffers. On the other hand, Internet traffic is bursty. The existence of burstiness in network traffic has been shown at all time scales, from tens of milliseconds to thousands of seconds. The widely existing burstiness has a very significant impact on the performance of small buffer networks, resulting in high packet drop probabilities and low link utilization. There have been many solutions proposed in the literature to solve the burstiness issue of network traffic. Traffic engineering techniques, such as traffic shaping and polishing, have been available in commercial routers/switches since the era of Asynchronous Transfer Mode (ATM) networks. Moreover, TCP pacing, as a natural solution to the TCP burstiness, has long been studied. Furthermore, several traffic conditioning and scheduling techniques are proposed to smooth core network traffics in a coordinated manner. However, all the existing solutions are inadequate to efficiently solve the burstiness issue of high-speed traffic. In this dissertation we aim to tackle the burstiness issue in small buffer networks, which refer to the future Internet core network consisting of all-optical routers and switches with small buffers. This dissertation is composed of two parts. In the first part, we analyze the impact of a general pacing scheme on the performance of a tandem queue network. This part serves as a theoretical foundation, based on which we demonstrate the benefits of pacing in a tandem queue model. Specifically, we use the Infinitesimal Perturbation Analysis (IPA) technique to study the impact of pacing on the instantaneous and average queue lengths of a series of nodes. Through theoretical analyses and extensive simulations, we show that under certain conditions there exists a linear relationship between system parameters and instantaneous/average queue lengths of nodes and that pacing improves the performance of the underlying tandem queue system by reducing the burstiness of the packet arrival process. In the second part, we propose a practical on-line packet pacing scheme, named Queue Length Based Pacing (QLBP). We analyze the impact of QLBP on the underlying network traffic in both time and frequency domains. We also present two implementation algorithms that allow us to evaluate the performance of QLBP in real experimental and virtual simulation environments. Through extensive simulations, we show that QLBP can effectively reduce the burstiness of network traffic and hence significantly improve the performance of a small buffer network. More important, the network traffic paced with QLBP does not exhibit a weakened competition capability when competing with non-paced traffic, which makes the QLBP scheme more attractive for ISPs.
15
Yan, Cai. "Queue Length Based Pacing of Internet Traffic." 2011. https://scholarworks.umass.edu/open_access_dissertations/423.
Full textAbstract:
As the Internet evolves, there is a continued demand for high Internet bandwidth. This demand is driven partly by the widely spreading real-time video applications, such as on-line gaming, teleconference, high-definition video streaming. All-optical switches and routers have long been studied as a promising solution to the rapidly growing demand. Nevertheless, buffer sizes in all-optical switches and routers are very limited due to the challenges in manufacturing larger optical buffers. On the other hand, Internet traffic is bursty. The existence of burstiness in network traffic has been shown at all time scales, from tens of milliseconds to thousands of seconds. The widely existing burstiness has a very significant impact on the performance of small buffer networks, resulting in high packet drop probabilities and low link utilization. There have been many solutions proposed in the literature to solve the burstiness issue of network traffic. Traffic engineering techniques, such as traffic shaping and polishing, have been available in commercial routers/switches since the era of Asynchronous Transfer Mode (ATM) networks. Moreover, TCP pacing, as a natural solution to the TCP burstiness, has long been studied. Furthermore, several traffic conditioning and scheduling techniques are proposed to smooth core network traffics in a coordinated manner. However, all the existing solutions are inadequate to efficiently solve the burstiness issue of high-speed traffic. In this dissertation we aim to tackle the burstiness issue in small buffer networks, which refer to the future Internet core network consisting of all-optical routers and switches with small buffers. This dissertation is composed of two parts. In the first part, we analyze the impact of a general pacing scheme on the performance of a tandem queue network. This part serves as a theoretical foundation, based on which we demonstrate the benefits of pacing in a tandem queue model. Specifically, we use the Infinitesimal Perturbation Analysis (IPA) technique to study the impact of pacing on the instantaneous and average queue lengths of a series of nodes. Through theoretical analyses and extensive simulations, we show that under certain conditions there exists a linear relationship between system parameters and instantaneous/average queue lengths of nodes and that pacing improves the performance of the underlying tandem queue system by reducing the burstiness of the packet arrival process. In the second part, we propose a practical on-line packet pacing scheme, named Queue Length Based Pacing (QLBP). We analyze the impact of QLBP on the underlying network traffic in both time and frequency domains. We also present two implementation algorithms that allow us to evaluate the performance of QLBP in real experimental and virtual simulation environments. Through extensive simulations, we show that QLBP can effectively reduce the burstiness of network traffic and hence significantly improve the performance of a small buffer network. More important, the network traffic paced with QLBP does not exhibit a weakened competition capability when competing with non-paced traffic, which makes the QLBP scheme more attractive for ISPs.
16
Wu, Chia-fa, and 吳洽發. "A packets drop algorithm with controlling queue length." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/74388282230588035953.
Full textAbstract:
碩士<br>國立中興大學<br>資訊科學研究所<br>93<br>The Internet is increasingly supporting real time applications such as VOIP, video conference and online games. These new applications have more requirements in terms of throughput or delay. We propose a new AQM mechanism to improve the performance of Adaptive Random Early Detection (ARED). Our mechanism is based on the proportional integral derivative control, which can provide robust and predictive congestion avoidance and stabilizes the queue length
17
Dwaraki, Abhishek. "Hardware Implementation of Queue Length Based Pacing on NetFPGA." 2011. https://scholarworks.umass.edu/theses/604.
Full textAbstract:
Optical packet switching networks are the foundation for next generation high speed Internet and are fast becoming the norm rather than an option. When such high speed optical networks are taken into account, one of the key considerations is packet buffering. The importance of packet buffering plays an even bigger role in optical networks because of the physical and technological constraints on the buffer sizes that can be implemented. Existing protocols, in many real world scenarios do not perform well in such networks. To eliminate such scenarios where there is a high possibility of packet loss, we use packet pacing. The proposed pacing scheme aims to reduce or eliminate packet losses arising from packet bursts in small-buffer networks. This thesis deals with a proposed hardware design and implementation of the packet pacing system on a NetFPGA. Our results show that the packet pacer can be implemented with a low overhead on hardware resources.
18
Chakraborty, Avijit. "Delay Differentiation By Balancing Weighted Queue Lengths." Thesis, 2013. https://etd.iisc.ac.in/handle/2005/2613.
Full textAbstract:
Scheduling policies adopted for statistical multiplexing should provide delay differentiation between different traffic classes, where each class represents an aggregate traffic of individual applications having same target-queueing-delay requirements. We propose scheduling to optimally balance weighted mean instanteneous queue lengths and later weighted mean cumulative queue lengths as an approach to delay differentiation, where the class weights are set inversely proportional to the respective products of target delays and packet arrival rates. In particular, we assume a discrete-time, two-class, single-server queueing model with unit service time per packet and provide mathematical frame-work throughout our work.
For iid Bernoulli packet arrivals, using a step-wise cost-dominance analytical approach using instantaneous queue lengths alone, for a class of one-stage cost functions not necessarily convex, we find the structure of the total-cost optimal policies for a part of the state space. We then consider two particular one-stage cost functions for finding two scheduling policies that are total-cost optimal for the whole state-space. The policy for the absolute weighted difference cost function minimizes the stationary mean, and the policy for the weighted sum-of-square cost function minimizes the stationary second-order moment, of the absolute value of the weighted difference of queue lengths. For the case of weighted sum-of-square cost function, the ‘iid Bernoulli arrivals’ assumption can be relaxed to either ‘iid arrivals with general batch sizes’ or to ‘Markovian zero-one arrivals’ for all of the state space, but for the linear switching curve. We then show that the average cost, starting from any initial state, exists, and is finite for every stationary work-conserving policy for our choices of the one-stage cost-function. This is shown for arbitrary number of class queues and for any i.i.d. batch arrival processes with finite appropriate moments.
We then use cumulative queue lengths information in the one-step cost function of the optimization formulation and obtain an optimal myopic policy with 3 stages to go for iid arrivals with general batch sizes. We show analytically that this policy achieves the given target delay ratio in the long run under finite buffer assumption, given that feasibility conditions are satisfied. We take recourse to numerical value iteration to show the existence of average-cost for this policy. Simulations with varied class-weights for Bernoulli arrivals and batch arrivals with Poisson batch sizes show that this policy achieves mean queueing delays closer to the respective target delays than the policy obtained earlier. We also note that the coefficients of variation of the queueing delays of both the classes using cumulative queue lengths are of the same order as those using instantaneous queue lengths. Moreover, the short-term behaviour of the optimal myopic policy using cumulative queue lengths is superior to the existing standard policy reported by Coffman and Mitrani by a factor in the range of 3 to 8. Though our policy performs marginally poorer compared to the value-iterated, sampled, and then stationarily employed policy, the later lacks any closed-form structure.
We then modify the definition of the third state variable and look to directly balance weighted mean delays. We come up with another optimal myopic policy with 3 stages to go, following which the error in the ratio of mean delays decreases as the window-size, as opposed to the policy mentioned in the last paragraph, wherein the error decreases as the square-root of the window-size. We perform numerical value-iteration to show the existence of average-cost and study the performance by simulation. Performance of our policy is comparable with the value-iterated, sampled, and then stationarily employed policy, reported by Mallesh. We have then studied general inter-arrival time processes and obtained the optimal myopic policy for the Pareto inter-arrival process, in particular. We have supported with simulation that our policy fares similarly to the PAD policy, reported by Dovrolis et. al., which is primarily heuristic in nature.
We then model the possible packet errors in the multiplexed channel by either a Bernoulli process, or a Markov modulated Bernoulli process with two possible channel states. We also consider two possible round-trip-time values for control information, namely zero and one-slot. The policies that are next-stage optimal (for zero round-trip-time), and two-stage optimal (for one-slot round-trip-time) are obtained. Simulations with varied class-weights for Bernoulli arrivals and batch arrivals with Poisson batch sizes show that these policies indeed achieve mean queueing delays very close to the respective target delays. We also obtain the structure for optimal policies with N = 2 + ⌈rtt⌉ stages-to-go for generic values of rtt, and which need not be multiple of time-slots.
19
Chakraborty, Avijit. "Delay Differentiation By Balancing Weighted Queue Lengths." Thesis, 2013. http://etd.iisc.ernet.in/handle/2005/2613.
Full textAbstract:
Scheduling policies adopted for statistical multiplexing should provide delay differentiation between different traffic classes, where each class represents an aggregate traffic of individual applications having same target-queueing-delay requirements. We propose scheduling to optimally balance weighted mean instanteneous queue lengths and later weighted mean cumulative queue lengths as an approach to delay differentiation, where the class weights are set inversely proportional to the respective products of target delays and packet arrival rates. In particular, we assume a discrete-time, two-class, single-server queueing model with unit service time per packet and provide mathematical frame-work throughout our work.
For iid Bernoulli packet arrivals, using a step-wise cost-dominance analytical approach using instantaneous queue lengths alone, for a class of one-stage cost functions not necessarily convex, we find the structure of the total-cost optimal policies for a part of the state space. We then consider two particular one-stage cost functions for finding two scheduling policies that are total-cost optimal for the whole state-space. The policy for the absolute weighted difference cost function minimizes the stationary mean, and the policy for the weighted sum-of-square cost function minimizes the stationary second-order moment, of the absolute value of the weighted difference of queue lengths. For the case of weighted sum-of-square cost function, the ‘iid Bernoulli arrivals’ assumption can be relaxed to either ‘iid arrivals with general batch sizes’ or to ‘Markovian zero-one arrivals’ for all of the state space, but for the linear switching curve. We then show that the average cost, starting from any initial state, exists, and is finite for every stationary work-conserving policy for our choices of the one-stage cost-function. This is shown for arbitrary number of class queues and for any i.i.d. batch arrival processes with finite appropriate moments.
We then use cumulative queue lengths information in the one-step cost function of the optimization formulation and obtain an optimal myopic policy with 3 stages to go for iid arrivals with general batch sizes. We show analytically that this policy achieves the given target delay ratio in the long run under finite buffer assumption, given that feasibility conditions are satisfied. We take recourse to numerical value iteration to show the existence of average-cost for this policy. Simulations with varied class-weights for Bernoulli arrivals and batch arrivals with Poisson batch sizes show that this policy achieves mean queueing delays closer to the respective target delays than the policy obtained earlier. We also note that the coefficients of variation of the queueing delays of both the classes using cumulative queue lengths are of the same order as those using instantaneous queue lengths. Moreover, the short-term behaviour of the optimal myopic policy using cumulative queue lengths is superior to the existing standard policy reported by Coffman and Mitrani by a factor in the range of 3 to 8. Though our policy performs marginally poorer compared to the value-iterated, sampled, and then stationarily employed policy, the later lacks any closed-form structure.
We then modify the definition of the third state variable and look to directly balance weighted mean delays. We come up with another optimal myopic policy with 3 stages to go, following which the error in the ratio of mean delays decreases as the window-size, as opposed to the policy mentioned in the last paragraph, wherein the error decreases as the square-root of the window-size. We perform numerical value-iteration to show the existence of average-cost and study the performance by simulation. Performance of our policy is comparable with the value-iterated, sampled, and then stationarily employed policy, reported by Mallesh. We have then studied general inter-arrival time processes and obtained the optimal myopic policy for the Pareto inter-arrival process, in particular. We have supported with simulation that our policy fares similarly to the PAD policy, reported by Dovrolis et. al., which is primarily heuristic in nature.
We then model the possible packet errors in the multiplexed channel by either a Bernoulli process, or a Markov modulated Bernoulli process with two possible channel states. We also consider two possible round-trip-time values for control information, namely zero and one-slot. The policies that are next-stage optimal (for zero round-trip-time), and two-stage optimal (for one-slot round-trip-time) are obtained. Simulations with varied class-weights for Bernoulli arrivals and batch arrivals with Poisson batch sizes show that these policies indeed achieve mean queueing delays very close to the respective target delays. We also obtain the structure for optimal policies with N = 2 + ⌈rtt⌉ stages-to-go for generic values of rtt, and which need not be multiple of time-slots.
20
Chen, Fu-chi, and 陳福吉. "A Fuzzy Controller for Improving Queue Length Stability and Packet Delay of RED's Active Queue Management." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/85034543437552997092.
Full textAbstract:
碩士<br>國立成功大學<br>資訊管理研究所<br>95<br>As network technique blooming, our livings are facilitated with the networks, which make the internet become an important infrastructure to the global industry transaction. As a result the demands of network bandwidth are increasing because of several communication protocols, Voice over Internet Protocol (VoIP), Video conferencing, Video on Demand (VoD), require wideband transmission. Therefore, planning and control for the Quality of Service (QoS) has become a research area. One way to avoiding flow congestion is using Random Early Detection (RED). In RED, when the average queue lies in between Min and Max, packets dropping probability exists a non-linear relationship between flows of network and queues. This research constructed a new active queue manage method. Based on RED mechanism, the packets loss rate between two thresholds is computed by Fuzzy Proportional Integral Integral Derivative. The fuzzy controller has advantages of processing non-linear relationship by using fuzzy algorithm and controlling queues in buffer to be near the target by PIID.
Evaluated the performance of Fuzzy PIID RED was conducted in the study. By simulation using ns2, this study also compared it with some popular AQM methods, such as RED and PI. The result of simulation shows good performance and significant improvement in the field of fairness, queue behavior, delay time of end to end and jitters. The problem concerning Look-Out of DropTail and Full Queue was also improved. The approach solves the problem of the difficulty of setting two thresholds in RED as well. The packets dropping probability using proposed controller also conforms non-linear relationship between flows of network and queues. In summary, Fuzzy PIID RED can control queue behavior effectively.
21
Rai, Shibashis. "Studies on Queue Length and Saturation Flow at Signalized Intersection." Thesis, 2016. http://ethesis.nitrkl.ac.in/9168/1/2016_MT_SRai.pdf.
Full textAbstract:
The most critical element which influences performance of urban road network is the at-grade intersection. To make the urban traffic safe and efficient the most of the at-grade intersections are made signalized. For a signalized intersection design it is very important to know the number of vehicles in a queue of an approach. So in this thesis queue lengths of different approaches of different signalized intersection were determined and how these queue lengths are affected by the green time is studied. Also capacity, operation and design of signalized intersection depend on Passenger Car Unit (PCU) and the saturation flow. As India is a developing country heterogeneous traffic is found in urban roads of India. So to evaluate the overall operation of signalized intersection it is essential to estimate Passenger Car Unit (PCU) and saturation flow of mixed traffic conditions. Analysis of saturation flow is done in this paper.
To do these analysis data were collected from three signalized intersection of Odisha namely IG Park Square (Rourkela), Laxmi Talkies Chowk (Sambalpur) and AG Square (Bhubaneswar). Different methods were used to extract the data. Graph between cumulative arrivals/departures and time is plotted to estimate the queue length and then created relation between these queue lengths and green time. Again to estimate the saturation flow, Passenger Car Unit (PCU) values were calculated. The Passenger Car Unit (PCU) values were calculated using area and speed of different vehicles. The saturation flow values of different approaches were compared with the saturation flow values those are found using Passenger Car Unit (PCU) values of IRC SP-41 and by an equation (S= 525W) present in IRC SP-41.
Queue lengths of different approaches of different intersections were obtained. Also how green time affects the queue length is obtained. The saturation flow values of different approaches estimated using the field Passenger Car Unit (PCU) values were compared with the saturation flow values those are found using Passenger Car Unit (PCU) values of IRC SP-41 and by an equation (S= 525W) present in IRC SP-41. These queue length values and saturation flow values have very significant impact on signalized intersections of urban road of India.
22
Xu, Bo-Han, and 許博涵. "Bandwidth allocation according to queue length-a scheduling algorithm for WiMAX network." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/90599059452587471687.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>電子工程系<br>100<br>Worldwide Interoperability for Microwave Access (WiMAX) is a broadband
wireless access (BWA) technology. It provides high data rate and multimedia service.
WiMAX support Quality of Service (QoS) for various types of application. It is
important to allocate appropriate resource to different class of service to guarantee the
delay of real-time service and avoid the starvation of non-real-time service. In IEEE
802.16 standard for WiMAX network, this part is left opened to be explored.
The connection admission control (CAC) mechanism allows a connection to
reserve a bandwidth beforehand. Since a good prediction of the needed bandwidth is
not easy, a reserved bandwidth may not always be equal to the needed one.
Therefore, an algorithm adaptive to the load is proposed in this paper. A fixed
bandwidth is assigned to each connection in the first round according to the reserved
bandwidth. In the second round, two weight round robin algorithms are proposed.
In the first one, the weight is decided by the left queue length of the connection. In
the second one, the weight is decided by the left queue length and priority of the
connection. The second round will continue until the bandwidth of the frame is
exhausted or all packets in the queue have been scheduled. The simulation has been
done for theses two algorithms and compared with round robin algorithm. The result
shows these algorithms can adapt to the load of the connection for a fixed reserved
bandwidth.
23
Pan, Cheng-Yi, and 潘政毅. "A downlink scheduling based on queue length estimation for VoIP in WiMAX networks." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/22430535022050592086.
Full textAbstract:
碩士<br>國立屏東商業技術學院<br>資訊管理系(所)<br>99<br>How to allocate resources in an efficient way and the provision of Quality of Services (QoS) guarantee are the major issues in delivering delay sensitive traffic, like VoIP service, in WiMAX (Worldwide Interoperability for Microwave Access). One well-designed scheduling algorithm is expected to coordinate QoS-related functional entities in WiMAX architecture. Existing downlink scheduling algorithms of WiMAX, like DRR (Deficit Round-Robin) and WRR (Weighted Round-Robin), usually reserve minimum rate to each type of traffic and cannot consider the status of queue length of each connection, thus making it unsuitable for VoIP on-off traffic model. Therefore, we propose an efficient downlink scheduling algorithm, which allocate the bandwidth based on queue-length estimation. We compare the proposed scheme with DRR and WRR by estimating the system performance such as average delay, loss rate and throughput under several traffic scenario and system parameters value.
24
Wang, Yue. "Queue length analysis of end-to-end differentiated service networks with self-similar traffic." 2005. http://digital.library.okstate.edu/etd/umi-okstate-1416.pdf.
Full text
25
Shiue-JhengTzeng and 曾學正. "A Queue Length-Based Resource Management Policy for Topology-Based Scaling Mechanism on Storm." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/89464317432079632696.
Full textAbstract:
碩士<br>國立成功大學<br>電腦與通信工程研究所<br>103<br>In the last few years, there are more and more systems and applications using a large volume of continuous data streams. Apache Storm is a well-known and distributed real-time computation system for processing unbounded and large volumes of stream data with high throughput and low latency. On scalability of Storm, there are some drawbacks. And a paper proposed a new scaling mechanism to avoid these drawbacks. But, this mechanism is not complete, it only has simple policy to add resource. When the high loading condition is different, the adding resource is also different. Besides, when high loading condition disappeared, it also need to release redundant resource.
Based on this mechanism, we proposed a queue length-based resource management policy for a topology-based scaling mechanism on Storm and made some modify on this mechanism. In our simulation result, our resource management policy
is effective and its response time is very small.
In the future, we will implement this policy on this mechanism, and do some performance evaluations. Besides, we will improve our policy so that it can accommodate to the heterogeneous cluster.
26
Chen, Cheng-yu, and 陳政隅. "Bandwidth Allocation according to Queue Length and packet loss rate - a scheduling algorithm for WiMAX network." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/46993299833005341947.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>電子工程系<br>101<br>IEEE 802.16 is a broadband multimedia standard which supports five different service classes and satisfies QoS(Quality of Service) requirements for each class.
The real-time packets are constrained by timing. When the delay time of transmission is bigger than the maximum value, packets will be dropped. In this dissertation, we focus on the ertPStraffic in WiMAX network and set a constraint on its delay time.With thisconstraint, packet dropping happens when delay time of a packet is bigger than this value.Then, the bandwidth is scheduled according to the length of each queue.With simulation, packet loss ratesare found for different traffic loads.With the second method of bandwidth allocation according to queue length(BA-QL2), each class is assigned a weight β. The main purpose of this dissertationis to find this value for possible required loss rate. With our proposed algorithm, β can be found such that the loss rate can be as close to this required value as possible. In this dissertation, the proposed algorithm is simulated and tested. The simulated approach can be used as a templatefor anyone who wants to find an appropriate β for his model.
27
Chiang, Hsiang-Yu, and 蔣翔宇. "Fixed Optimal and Adaptive Neural Fuzzy Queue-Length-Threshold Control for Capacity Assignment in a Wireless ATM." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/26114982188480856305.
Full textAbstract:
碩士<br>國立交通大學<br>電信工程研究所<br>84<br>Recently, a wireless ATM network is proposedwhich integrate
different services to provide person-to-person communicationsin
the same air interface and using ATM network as its backbone.For
a wireless ATM network, in this paper we study the design of its
buffermanagement and capacity assignment strategy.We first
propose a fixed optimal queue-length-threshold (QLT) scheduling
policyfor the buffer management and capacity assignment. And we
show this QLT policy still outscore other policies suchas
priority policy in a wireless ATM environment.Owing to the
traffic fluctuation in a wireless ATM network system
providingmultimedia services, the ATM network had better possess
an intelligentQLT controller that can adaptively adjust
parameters of QLT.Recently, fuzzy logic system have been widely
applied to deal with controlrelated problems for ATM networks.
Neural networks, like fuzzy logic controlsystems, have been
successfully applied to cope with traffic control related
problems. Different from the fixed QLT policy we mentioned
above,we propose a neural fuzzy QLT (NFQLT) which can adjust the
trafficparameters adaptively according to the status of voice
and data traffic.The results show that applying the adaptive
NFQLT can decrease thecombined total lost probability than the
fixed QLT and other policies.
28
ChonChao, Kai, and 鄒啟俊. "Prediction of Traffic Accident Duration and Vehicle Queue Length – Case Study of National Freeway No.5 in Taiwan." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/tenvmv.
Full textAbstract:
碩士<br>國立成功大學<br>交通管理科學系<br>102<br>Traffic accident occurrence on freeway is the main cause that affects travel time anticipated. Accurate travel time information will help travelers make better decisions in terms of departure time, route selection and even mode choice. This study aims to analyze the importance of accident features and evaluate the impacts of accident existence (queue length and recovery time) on freeway. The ultimate goal is to estimate accident duration and queue length when given relevant accident features according the accident database and vehicle detector database. All these information needs to be cross-checked in order to confirm the significant accident features and resulting impacts. Artificial neural network models are constructed with the most relevant factors identified in the above processes to provide predictive information of accident duration.
29
"A novel link buffer size and queue length estimation algorithm and its application on bandwidth-varying mobile data networks." 2012. http://library.cuhk.edu.hk/record=b5549031.
Full textAbstract:
隋著移動數據網絡的迅速發展，世界各地部署著不同制式的3G，HSPA和LTE網絡，這給移動互聯網應用帶來新的機遇和挑戰。不像他們的對手, 有線網絡，移動數據網絡有較長的延遲，較高的包率，以及急劇波動的頻寬。為了應付這些挑戰，移動無線基站往往配備較大的緩衝區（KBs以至數百多MBs），以吸收短期的頻寬波動，並促進鏈路層重傳。然而，由於大部分互聯網協議，並特別是TCP，全都假設路由器只擁有較小緩衝區，所以在移動網絡的大型緩衝區下，往往導致TCP展現出次優的性能。本論文解決兩個根本性的問題來克服這一項挑戰。首先，我們開發了一種新算法 (SoD）專門來估計網絡的鏈路緩衝區的大小和隊列長度。在今天的3G移動數據網絡，本文以大量網絡數據驅動的模擬結果證明 SoD 表現優於現有的算法，如 Max-min 和 Loss-pair。另外，我們採用 SoD算法來創造新的TCP擁塞控制模塊以解決移動網絡的大型緩衝區以及的頻寬波動問題。這個新的TCP變種，稱為 TCP- QA，在模擬情況以及移動數據網絡下均表現出大大優於現有的TCP變種，包括TCP CUBIC ，TCP Vegas，TCP Westwood，和FAST TCP。<br>The rapidly emerging mobile data networks fueled by the world-wide deployment of 3G, HSPA, and LTE networks created new opportunities and challenges for developing mobile Internet applications. Unlike their wired counterpart, mobile data networks are known to exhibit longer delay, higher packet loss rate, and rapidly fluctuating bandwidth. To tackle these challenges mobile radio base stations are often equipped with large buffers (from hundreds of KBs to multi-MBs) to absorb short-term bandwidth fluctuations and to facilitate link-layer retransmissions. However as most Internet protocols in general, and TCP in particular, were designed with the assumption of small router buffer size, the large buffer in mobile networks can and do interact, often negatively, with the Internet protocols, leading to sub-optimal performance. This work tackles two fundamental problems in overcoming this challenge. First, we developed a novel Sum-of-Delays (SoD) algorithm specifically designed to estimate the link buffer size and queue length of bandwidth-varying networks. Extensive trace-driven simulation results showed that SoD outperforms existing algorithms such as max-min and loss-pair by orders of magnitude in today’s 3G mobile data networks. Second, we apply the SoD algorithm to TCP’s congestion control module to incorporate and compensate for the mobile network’s large buffer size. This new TCP variant, called TCP-Queue-length-Adaptive (TCP-QA), substantially outperforms existing TCP variants including TCP CUBIC, TCP Vegas, TCP Westwood, and FAST TCP.<br>Detailed summary in vernacular field only.<br>Chan, Chi Fung.<br>Thesis (M.Phil.)--Chinese University of Hong Kong, 2012.<br>Includes bibliographical references.<br>Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.<br>Abstracts also in Chinese.<br>Abstract --- p.ii<br>摘要 --- p.iii<br>Acknowledgements --- p.iv<br>Contents --- p.v<br>Chapter Chapter 1 --- Introduction --- p.1<br>Chapter Chapter 2 --- Background and Related Work --- p.5<br>Chapter 2.1 --- Link Buffer Size Estimation --- p.6<br>Chapter 2.2 --- Queue Length Estimation --- p.8<br>Chapter 2.3 --- Performance over Fixed Networks --- p.10<br>Chapter 2.4 --- Performance over Bandwidth-Varying Networks --- p.15<br>Chapter Chapter 3 --- Sum-Of-Delay Method --- p.19<br>Chapter Chapter 4 --- Performance Evaluation --- p.22<br>Chapter 4.1 --- Link Buffer Size Estimation in Fixed Bandwidth Networks --- p.23<br>Chapter 4.2 --- Link Buffer Size Estimation in Variable Bandwidth Networks --- p.25<br>Chapter 4.3 --- Queue Length Estimation in Fixed Bandwidth Networks --- p.28<br>Chapter 4.4 --- Queue Length Estimation in Variable Bandwidth Networks --- p.31<br>Chapter 4.5 --- Convergence --- p.34<br>Chapter 4.6 --- Limitations in Passive Estimation --- p.40<br>Chapter Chapter 5 --- Impact of Competing Traffic --- p.42<br>Chapter 5.1 --- Simulation Setup --- p.42<br>Chapter 5.2 --- Link Buffer Size Estimation --- p.44<br>Chapter 5.3 --- Queue Length Estimation --- p.50<br>Chapter 5.4 --- Discussions --- p.54<br>Chapter Chapter 6 --- TCP-Queue-Length-Adaptive (TCP-QA) --- p.56<br>Chapter 6.1 --- Challenges in Mobile Networks --- p.57<br>Chapter 6.2 --- Queue-Length-Adaptive Congestion Control --- p.59<br>Chapter 6.3 --- Performance Comparisons --- p.65<br>Chapter Chapter 7 --- Summary and Future Work --- p.76<br>Bibliography --- p.78
30
Mallesh, K. "Errors In Delay Differentiation In Statistical Multiplexing." Thesis, 2007. https://etd.iisc.ac.in/handle/2005/647.
Full textAbstract:
Different applications of communication networks have different requirements that depend on the type of application. We consider the problem of differentiating between delay-sensitive applications based on their average delay requirements, as may be of interest in signalling networks. We consider packets of different classes that are to be transmitted on the same link with different average delay requirements, to reside in separate queues with the arrival statistics for the queues being specified. This statistical multiplexer has to schedule packets from different queues in so that the average delays of the queues approach the specified target delays as quickly as possible.
For simplicity, we initially consider a discrete-time model with two queues and a single work-conserving server, with independent Bernoulli packet arrivals and unit packet service times. With arrival rates specified, achieving mean queue lengths in a ratio which corresponds to the ratio of target mean delays is a means of achieving individual target mean delays. We formulate the problem in the framework of Markov decision theory. We study two scheduling policies called Queue Length Balancing and Delay Balancing respectively, and show through numerical computation that the expectation of magnitude of relative error in θ (1/m) and θ (1/√m) respectively, and that the expectation of the magnitude of relative error in weighted average delays decays as θ (1/√m) and θ (1/m) respectively, where m is the averaging interval length.
We then consider the model for an arbitrary number of queues each with i.i.d. batch arrivals, and analyse the errors in the average delays of individual queues. We assume that the fifth moment of busy period is finite for this model. We show that the expectation of the absolute value of error in average queue length for at least one of the queues decays at least as slowly as θ (1/√m), and that the mean squared error in queue length for at least one of the queues decays at least as slowly as θ (1/m). We show that the expectation of the absolute value of error in approximating Little’s law for finite horizon is 0 (1/m). Hence, we show that the mean squared error in delay for at least one of the queues decays at least slowly as θ (1/m). We also show that if the variance of error in delay decays for each queue, then the expectation of the absolute value of error in delay for at least one of the queues decays at least as slowly as θ (1/√m).
31
Mallesh, K. "Errors In Delay Differentiation In Statistical Multiplexing." Thesis, 2007. http://hdl.handle.net/2005/647.
Full textAbstract:
Different applications of communication networks have different requirements that depend on the type of application. We consider the problem of differentiating between delay-sensitive applications based on their average delay requirements, as may be of interest in signalling networks. We consider packets of different classes that are to be transmitted on the same link with different average delay requirements, to reside in separate queues with the arrival statistics for the queues being specified. This statistical multiplexer has to schedule packets from different queues in so that the average delays of the queues approach the specified target delays as quickly as possible.
For simplicity, we initially consider a discrete-time model with two queues and a single work-conserving server, with independent Bernoulli packet arrivals and unit packet service times. With arrival rates specified, achieving mean queue lengths in a ratio which corresponds to the ratio of target mean delays is a means of achieving individual target mean delays. We formulate the problem in the framework of Markov decision theory. We study two scheduling policies called Queue Length Balancing and Delay Balancing respectively, and show through numerical computation that the expectation of magnitude of relative error in θ (1/m) and θ (1/√m) respectively, and that the expectation of the magnitude of relative error in weighted average delays decays as θ (1/√m) and θ (1/m) respectively, where m is the averaging interval length.
We then consider the model for an arbitrary number of queues each with i.i.d. batch arrivals, and analyse the errors in the average delays of individual queues. We assume that the fifth moment of busy period is finite for this model. We show that the expectation of the absolute value of error in average queue length for at least one of the queues decays at least as slowly as θ (1/√m), and that the mean squared error in queue length for at least one of the queues decays at least as slowly as θ (1/m). We show that the expectation of the absolute value of error in approximating Little’s law for finite horizon is 0 (1/m). Hence, we show that the mean squared error in delay for at least one of the queues decays at least slowly as θ (1/m). We also show that if the variance of error in delay decays for each queue, then the expectation of the absolute value of error in delay for at least one of the queues decays at least as slowly as θ (1/√m).
32
Chakraborty, Avijit. "Optimal Scheduling For Balancing Queue Lengths." Thesis, 1999. https://etd.iisc.ac.in/handle/2005/1610.
Full text
33
Chakraborty, Avijit. "Optimal Scheduling For Balancing Queue Lengths." Thesis, 1999. http://etd.iisc.ernet.in/handle/2005/1610.
Full text
34
Teo, Chee Chong, Rohit Bhatnagar, and Stephen C. Graves. "An Extension to the Tactical Planning Model for a Job Shop: Continuous-Time Control." 2004. http://hdl.handle.net/1721.1/7447.
Full textAbstract:
We develop an extension to the tactical planning model (TPM) for a job shop by the third author. The TPM is a discrete-time model in which all transitions occur at the start of each time period. The time period must be defined appropriately in order for the model to be meaningful. Each period must be short enough so that a job is unlikely to travel through more than one station in one period. At the same time, the time period needs to be long enough to justify the assumptions of continuous workflow and Markovian job movements. We build an extension to the TPM that overcomes this restriction of period sizing by permitting production control over shorter time intervals. We achieve this by deriving a continuous-time linear control rule for a single station. We then determine the first two moments of the production level and queue length for the workstation.<br>Singapore-MIT Alliance (SMA)
35
Chen, Kun-Tso. "Design and Performance Analysis of an Asynchronous Combined-Input-Output-Queued Packet-Based Switch for Variable-Length Packet Unicast and Multicast Switching." 2004. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0001-0807200423121000.
Full text
36
Chen, Kun-Tso, and 陳坤佐. "Design and Performance Analysis of an Asynchronous Combined-Input-Output-Queued Packet-Based Switch for Variable-Length Packet Unicast and Multicast Switching." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/73287470980972291730.
Full textAbstract:
博士<br>國立臺灣大學<br>電信工程學研究所<br>92<br>Currently most of the switches are cell-based and synchronous,such that the length of the packet is fixed. However, a great partof the current network traffic consists of variable lengthpackets, for example, Ethernet or IP traffics. Hence, thecell-based switch must segment the incoming packets at the inputports into cells, switch these cells synchronously, reassemblethem at the output ports, and finally transmit the packets to theoutput links. The additional segmentation and reassembly circuitsare required. The synchronous cell-based switch incurs performancedeterioration due to synchronization and segmentation overheadwhen the input traffic consists of variable length packets. Inorder to switch the incoming packets with variable lengthasynchronously, we propose a novel switch architecture in thisthesis. Its performance is analyzed in detail by queueing theoryand simulation. The system parameters are optimized to attain thebest performance with the minimum cost.
In general, we can categorize the switch architecture as InputQueued (IQ), Output Queued (OQ), or Combined Input Output Queued(CIOQ) switch according to the position of the buffers. The IQswitch is simplest but its throughput is rather low because of theHead-Of-the-Line (HOL) blocking effect. The HOL blocking can beeliminated completely in an OQ switch, which stores the packets inthe output ports. However, the operation speed of the OQ switchmust be many times the rate of the input link in order to obtainhigh throughput. The required speedup of the switch operationrequires extreme short access time of the buffer memory. The speedof the transmission link increases fast because of thecontinuously growing network bandwidth demand and the advent ofWavelength Division Multiplexing (WDM) technology. However, thebottleneck of the network performance still exists because of thelack of high speed switches with large ports. The requirement ofextreme high switching operation speed makes an OQ switchinfeasible. Hence, a lot of schemes were proposed in theliterature to improve the performance of CIOQ switches, whichdon''t require the speedup of switching speed too much. However,these schemes require complicated control unit and thus aredifficult to implement. The key to success for a high capacity andhigh performance switch is a simple hardware design to arbitratethe contending packets and to control the routes of packets withthe switching fabric. The design goal of the proposed switch inthis thesis is to switch variable length packets asynchronouslywith simple and feasible hardware. We also take into account thescalability of the switch, i.e., the switch design is based on amodular architecture. There is neither packet arrivalsynchronization circuits nor central controllers, which arerequired in the conventional cell-based switches. Modularswitching elements and simple input controllers are used to switchpackets asynchronously.
The proposed switch provides unicast and multicast capabilitiesfor variable length packets. We theoretically analyze and obtainthe performance metric in closed form. Computer simulations aredone to verify the theoretical results. We also derive the optimalsystem parameters, which can be used as the design rule of theswitch. Moreover, we present a circuit level design of the switcharchitecture, which integrates the unicast and multicastcapabilities. This complete design also takes into account Qualityof Service(QoS) provision and packet sequence integrity afterswitching. We believe that the proposed switch is easy toimplement and can satisfy the requirement of high capacity in themodern high speed network.
37
Teo, Chee Chong. "A Study of Moment Recursion Models for Tactical Planning of a Job Shop: Literature Survey and Research Opportunities." 2003. http://hdl.handle.net/1721.1/3920.
Full textAbstract:
The Moment Recursion (MR) models are a class of models for tactical planning of job shops or other processing networks. The MR model can be used to determine or approximate the first two moments of production quantities and queue lengths at each work station of a job shop. Knowledge of these two moments is sufficient to carry out a variety of performance evaluation, optimization and decision-support applications. This paper presents a literature survey of the Moment-Recursion models. Limitations in the existing research and possible research opportunities are also discussed. Based on the research opportunities discussed, we are in the process of building a model that attempts to fill these research gaps.<br>Singapore-MIT Alliance (SMA)
38
Filipe, Luís Alexandre Coelho. "A tour of health care: emergency room, hospital and home." Doctoral thesis, 2020. http://hdl.handle.net/10362/108174.
Full textAbstract:
My thesis is a small tour of the health care system (emergency room, hospital and home), with special emphasis on providers. Chapter 1 analyzes how emergency room doctors change their behavior when the waiting room is crowded. The outcomes reflect the time spent with the patient, the intensity of treatment, and discharge destination. Chapter 2 extends the previous setting to inpatient care, to determine how doctors react to hospital occupancy level. It identifies doctors’ discharging criteria as a causal factor for the positive relation between occupancy rates and readmissions. The analysis in Chapters 1 and 2 contributes to the doctors’ incentives literature, explaining how these agents behave in the context of a National Health Service, with no financial incentives. Chapter 3 examines the impact of informally providing care to a partner (at home) on the physical and mental health of the carer.