The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Eytan Modiano - One of the best experts on this subject based on the ideXlab platform.
-
learning algorithms for minimizing Queue Length regret
IEEE Transactions on Information Theory, 2021Co-Authors: Thomas Stahlbuhk, Brooke Shrader, Eytan ModianoAbstract:We consider a system consisting of a single transmitter/receiver pair and N channels over which they may communicate. Packets randomly arrive to the transmitter’s Queue and wait to be successfully sent to the receiver. The transmitter may attempt a frame transmission on one channel at a time, where each frame includes a packet if one is in the Queue. For each channel, an attempted transmission is successful with an unknown probability. The transmitter’s objective is to quickly identify the best channel to minimize the number of packets in the Queue over T time slots. To analyze system performance, we introduce Queue Length regret, which is the expected difference between the total Queue Length of a learning policy and a controller that knows the rates, a priori. One approach to designing a transmission policy would be to apply algorithms from the literature that solve the closely-related stochastic multi-armed bandit problem. These policies would focus on maximizing the number of successful frame transmissions over time. However, we show that these methods have $\Omega (\log {{T}})$ Queue Length regret. On the other hand, we show that there exists a set of Queue-Length based policies that can obtain order optimal ${O}(1)$ Queue Length regret. We use our theoretical analysis to devise heuristic methods that are shown to perform well in simulation.
-
learning algorithms for minimizing Queue Length regret
International Symposium on Information Theory, 2018Co-Authors: Thomas Stahlbuhk, Brooke Shrader, Eytan ModianoAbstract:We consider a system consisting of a single transmitter and $N$ channels. Packets randomly arrive to the transmitter's Queue, and at each time slot a controller can schedule one of the $N$ channels for transmission. The channel's rates are time-varying with unknown statistics and must be learned through observation. Our objective is to minimize the number of packets in the system's Queue over $T$ time slots. We define the regret of the system to be the expected difference between the total Queue Length of a controller that must learn the channels' average rates and a controller that knows the rates, a priori. One approach to solving this problem would be to apply algorithms from the literature that were developed to solve the closely-related stochastic multi-armed bandit problem. However, we show that these methods have $\Omega(\log(T))$ Queue Length regret. On the other hand, we show that there exists a set of Queue-Length based policies that are able to obtain order optimal, $O(1)$ , regret.
-
minimizing Queue Length regret under adversarial network models
Measurement and Modeling of Computer Systems, 2018Co-Authors: Qingkai Liang, Eytan ModianoAbstract:Stochastic models have been dominant in network optimization theory for over two decades, due to their analytical tractability. However, these models fail to capture non-stationary or even adversarial network dynamics which are of increasing importance for modeling the behavior of networks under malicious attacks or characterizing short-term transient behavior. In this paper, we focus on minimizing Queue Length regret under adversarial network models, which measures the finite-time Queue Length difference between a causal policy and an "oracle" that knows the future. Two adversarial network models are developed to characterize the adversary's behavior. We provide lower bounds on Queue Length regret under these adversary models and analyze the performance of two control policies (i.e., the MaxWeight policy and the Tracking Algorithm). We further characterize the stability region under adversarial network models, and show that both the MaxWeight policy and the Tracking Algorithm are throughput-optimal even in adversarial settings.
-
The Impact of Queue Length Information on Buffer Overflow in Parallel Queues
IEEE Transactions on Information Theory, 2013Co-Authors: Krishna Jagannathan, Eytan ModianoAbstract:We consider a system consisting of N parallel Queues, served by one server. Time is slotted, and the server serves one of the Queues in each time slot, according to some scheduling policy. We first characterize the exponent of the buffer overflow probability and the most likely overflow trajectories under the Longest Queue First (LQF) scheduling policy. Under statistically identical arrivals to each Queue, we show that the buffer overflow exponents can be simply expressed in terms of the total system occupancy exponent of m parallel Queues, for some m ≤ N. We next turn our attention to the rate of Queue Length information needed to operate a scheduling policy, and its relationship to the buffer overflow exponents. It is known that Queue Length blind policies such as processor sharing and random scheduling perform worse than the Queue aware LQF policy, when it comes to buffer overflow probability. However, we show that the overflow exponent of the LQF policy can be preserved with arbitrarily infrequent Queue Length updates.
-
on the role of Queue Length information in network control
IEEE Transactions on Information Theory, 2011Co-Authors: Krishna Jagannathan, Eytan Modiano, Lizhong ZhengAbstract:We study the role played by Queue Length information in the operation of flow control and server allocation policies. We first consider a simple model of a single server Queue with congestion-based flow control. The input rate at any instant is decided by a flow control policy, based on the Queue occupancy. We identify a simple “two-threshold” control policy, which achieves the best possible exponential scaling for the Queue congestion probability, for any rate of control. We show that when the control channel is reliable, the control rate needed to ensure the optimal decay exponent for the congestion probability can be made arbitrarily small. However, if control channel erasures occur probabilistically, we show the existence of a critical erasure probability threshold beyond which the congestion probability undergoes a drastic increase due to the frequent loss of control packets. We also determine the optimal amount of error protection to apply to the control signals by using a simple bandwidth sharing model. Finally, we show that the Queue Length based server allocation problem can also be treated using this framework and that the results obtained for the flow control setting can also be applied to the server allocation case.
Henry X Liu - One of the best experts on this subject based on the ideXlab platform.
-
maximum likelihood estimation of probe vehicle penetration rates and Queue Length distributions from probe vehicle data
IEEE Transactions on Intelligent Transportation Systems, 2021Co-Authors: Yan Zhao, Jianfeng Zheng, Wai Wong, Henry X LiuAbstract:Queue Length estimation plays an important role in traffic signal control and performance measures of signalized intersections. Traditionally, Queue Lengths are estimated by applying the shockwave theory to loop detector data. In recent years, the tremendous amount of vehicle trajectory data collected from probe vehicles such as ride-hailing vehicles and connected vehicles provides an alternative approach to Queue Length estimation. To estimate Queue Lengths cycle by cycle, many existing methods require the knowledge of the probe vehicle penetration rate and Queue Length distribution. However, the estimation of the two parameters has not been well studied. This paper proposes a maximum likelihood estimation method that can estimate the parameters from historical probe vehicle data. The maximum likelihood estimation problem is solved by the expectation-maximization (EM) algorithm iteratively. Validation results show that the proposed method could estimate the parameters accurately and thus enable the existing methods to estimate Queue Lengths cycle by cycle.
-
various methods for Queue Length and traffic volume estimation using probe vehicle trajectories
Transportation Research Part C-emerging Technologies, 2019Co-Authors: Yan Zhao, Jianfeng Zheng, Wai Wong, Xingmin Wang, Yuan Meng, Henry X LiuAbstract:Abstract The rapid development of connected vehicle technology and the emergence of ride-hailing services have enabled the collection of a tremendous amount of probe vehicle trajectory data. Due to the large scale, the trajectory data have become a potential substitute for the widely used fixed-location sensors in terms of the performance measures of transportation networks. Specifically, for traffic volume and Queue Length estimation, most of the trajectory data based methods in the existing literature either require high market penetration of the probe vehicles to identify the shockwave or require the prior information about the Queue Length distribution and the penetration rate, which may not be feasible in the real world. To overcome the limitations of the existing methods, this paper proposes a series of novel methods based on probability theory. By exploiting the stopping positions of the probe vehicles in the Queues, the proposed methods try to establish and solve a single-variable equation for the penetration rate of the probe vehicles. Once the penetration rate is obtained, it can be used to project the total Queue Length and the total traffic volume. The validation results using both simulation data and real-world data show that the methods would be accurate enough for assistance in performance measures and traffic signal control at intersections, even when the penetration rate of the probe vehicles is very low.
Krishna Jagannathan - One of the best experts on this subject based on the ideXlab platform.
-
The Impact of Queue Length Information on Buffer Overflow in Parallel Queues
IEEE Transactions on Information Theory, 2013Co-Authors: Krishna Jagannathan, Eytan ModianoAbstract:We consider a system consisting of N parallel Queues, served by one server. Time is slotted, and the server serves one of the Queues in each time slot, according to some scheduling policy. We first characterize the exponent of the buffer overflow probability and the most likely overflow trajectories under the Longest Queue First (LQF) scheduling policy. Under statistically identical arrivals to each Queue, we show that the buffer overflow exponents can be simply expressed in terms of the total system occupancy exponent of m parallel Queues, for some m ≤ N. We next turn our attention to the rate of Queue Length information needed to operate a scheduling policy, and its relationship to the buffer overflow exponents. It is known that Queue Length blind policies such as processor sharing and random scheduling perform worse than the Queue aware LQF policy, when it comes to buffer overflow probability. However, we show that the overflow exponent of the LQF policy can be preserved with arbitrarily infrequent Queue Length updates.
-
on the role of Queue Length information in network control
IEEE Transactions on Information Theory, 2011Co-Authors: Krishna Jagannathan, Eytan Modiano, Lizhong ZhengAbstract:We study the role played by Queue Length information in the operation of flow control and server allocation policies. We first consider a simple model of a single server Queue with congestion-based flow control. The input rate at any instant is decided by a flow control policy, based on the Queue occupancy. We identify a simple “two-threshold” control policy, which achieves the best possible exponential scaling for the Queue congestion probability, for any rate of control. We show that when the control channel is reliable, the control rate needed to ensure the optimal decay exponent for the congestion probability can be made arbitrarily small. However, if control channel erasures occur probabilistically, we show the existence of a critical erasure probability threshold beyond which the congestion probability undergoes a drastic increase due to the frequent loss of control packets. We also determine the optimal amount of error protection to apply to the control signals by using a simple bandwidth sharing model. Finally, we show that the Queue Length based server allocation problem can also be treated using this framework and that the results obtained for the flow control setting can also be applied to the server allocation case.
-
Queue Length asymptotics for generalized max weight scheduling in the presence of heavy tailed traffic
International Conference on Computer Communications, 2011Co-Authors: Krishna Jagannathan, Eytan Modiano, Mihalis G Markakis, John N TsitsiklisAbstract:We investigate the asymptotic behavior of the steady-state Queue Length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel Queues, served by a single server. One of the Queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput optimal max-weight-α scheduling policies, and derive an exact asymptotic characterization of the steady-state Queue Length distributions. In particular, we show that the tail of the light Queue distribution is heavier than a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also shows that the celebrated max-weight scheduling policy leads to the worst possible tail of the light Queue distribution, among all non-idling policies. Motivated by the above ‘negative’ result regarding the max-weight-α policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light Queue tail, while still being throughput optimal.
-
Queue Length asymptotics for generalized max weight scheduling in the presence of heavy tailed traffic
arXiv: Networking and Internet Architecture, 2010Co-Authors: Krishna Jagannathan, Eytan Modiano, Mihalis G Markakis, John N TsitsiklisAbstract:We investigate the asymptotic behavior of the steady-state Queue Length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel Queues, served by a single server. One of the Queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput optimal max-weight-alpha scheduling policies, and derive an exact asymptotic characterization of the steady-state Queue Length distributions. In particular, we show that the tail of the light Queue distribution is heavier than a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also contains an intuitively surprising result - the celebrated max-weight scheduling policy leads to the worst possible tail of the light Queue distribution, among all non-idling policies. Motivated by the above negative result regarding the max-weight-alpha policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light Queue tail, while still being throughput optimal.
-
The impact of Queue Length information on buffer overflow in parallel Queues
2009 47th Annual Allerton Conference on Communication Control and Computing (Allerton), 2009Co-Authors: Krishna Jagannathan, Eytan ModianoAbstract:We consider a system consisting of N parallel Queues, served by one server. Time is slotted, and the server serves one of the Queues in each time slot, according to some scheduling policy. In the first part of the paper, we characterize the buffer overflow exponents and the likeliest overflow trajectories under the Longest Queue First (LQF) scheduling policy. Under statistically identical arrivals to each Queue, we show that the buffer overflow exponent can be simply expressed in terms of the total system occupancy exponent of m parallel Queues, for some m ¿ N. We next turn our attention to the rate of Queue Length information needed to operate a scheduling policy, and its relationship to the buffer overflow exponents. It is known that LQF scheduling has superior overflow exponents compared to Queue blind policies such as processor sharing (PS) and random scheduling. However, we show that the overflow exponent of the LQF policy can be preserved under arbitrarily infrequent Queue Length information.
Gurcan Comert - One of the best experts on this subject based on the ideXlab platform.
-
Queue Length estimation from probe vehicles at isolated intersections estimators for primary parameters
European Journal of Operational Research, 2016Co-Authors: Gurcan ComertAbstract:Abstract This paper develops estimators for market penetration level and arrival rate in finding Queue Lengths from probe vehicles at isolated traffic intersections. Closed-form analytical expressions for expectations and variances of these estimators are formulated. Derived estimators are compared based on squared error losses. Effect of number of cycles (i.e., short-term and long-term performances), estimation at low penetration rates, and impact of combinations of derived estimators on Queue Length problem are also addressed. Fully analytical formulas with unknown parameters are derived to evaluate how Queue Length estimation errors change with respect to percent of probe vehicles in the traffic stream. Developed models can be used for the real-time cycle-to-cycle estimation of the Queue Lengths by inputting some of the fundamental information that probe vehicles provide (e.g., location, time, and count). Models are evaluated using VISSIM microscopic simulations with different arrival patterns. Numerical experiments show that the developed estimators are able to point the true arrival rate values at 5% probe penetration level with 10 cycles of data. For low penetrations such as 0.1%, large number of cycles of data is required by arrival rate estimators which are essential for overflow Queue and volume-to-capacity ratios. Queue Length estimation with tested parameter estimators is able to provide cycle-to-cycle errors within ±5% of coefficient of variations with less than 5 cycles of probe data at 0.1% penetration for all arrival rates used.
-
analytical evaluation of the error in Queue Length estimation at traffic signals from probe vehicle data
IEEE Transactions on Intelligent Transportation Systems, 2011Co-Authors: Gurcan Comert, Mecit CetinAbstract:Probe vehicle data are increasingly becoming more attractive for real-time system state estimation in transportation networks. This paper presents analytical models for the real-time estimation of Queue Lengths at traffic signals using the fundamental information (i.e., location and time) that probe vehicles provide. For a single Queue with Poisson arrivals, analytical models are developed to evaluate how error changes in Queue Length estimation as the percentage of probe vehicles in the traffic stream varies. When the overflow Queue is ignored, a closed-form solution is obtained for the variance of the estimation error. For the more general case with the overflow Queue, a formulation for the error variance is presented, which requires the marginal probability distribution of the overflow Queue as the input. In addition, an approximate model is presented for the latter case, which yields results that are comparable with the exact solution. Overall, the formulations presented here can be used to assess the error in Queue Length estimation from probe data without conducting simulation runs for various scenarios of probe vehicle market-penetration rates and congestion levels.
-
Queue Length estimation from probe vehicle location and the impacts of sample size
European Journal of Operational Research, 2009Co-Authors: Gurcan Comert, Mecit CetinAbstract:Probe vehicles are increasingly receiving more attention as an alternative means of collecting real-time traffic data needed for system optimization. This paper focuses on real-time estimation of Queue Lengths from the location information of probe vehicles in a Queue at an isolated and undersaturated intersection. The paper also addresses the evaluation of the accuracy of such estimates as a function of the market penetration of probe vehicles. An analytical formulation based on conditional probability distributions is developed for estimating the expected Queue Length and its variance. It is found that, for the given settings, only the location information of the last probe vehicle in the Queue is sufficient for the estimation. Exact expressions for the conditional mean and variance of Queue Length are derived. Various numerical results are documented to show how estimation errors behave by the volume to capacity ratio and by market penetration.
Mecit Cetin - One of the best experts on this subject based on the ideXlab platform.
-
probe vehicle lane identification for Queue Length estimation at intersections
Journal of Intelligent Transportation Systems, 2018Co-Authors: Semuel Y R Rompis, Mecit Cetin, Filmon G HabtemichaelAbstract:ABSTRACTVehicles instrumented with Global Positioning Systems, also known as GPS probe vehicles, have become increasingly popular for collecting traffic flow data. Previous studies have explored the probe vehicle data for estimating speeds and travel time; however, there is very limited research on predicting Queue dynamics from such data. In this research, a methodology was developed for identifying the lane position of the GPS-instrumented vehicles when they are standing in the Queue at signalized intersections with multiple lanes, particularly in the case of unequal Queue. Various supervised and unsupervised clustering methods were tested on data generated from a microsimulation model. Among the tested methods, the Optimal Bayes Rule that utilizes probability density functions estimated using bivariate statistical mixture models was found to be effective in identifying the lanes. The methodology for lane identification was tested for Queue Length estimation. This research confirms that the lane identif...
-
analytical evaluation of the error in Queue Length estimation at traffic signals from probe vehicle data
IEEE Transactions on Intelligent Transportation Systems, 2011Co-Authors: Gurcan Comert, Mecit CetinAbstract:Probe vehicle data are increasingly becoming more attractive for real-time system state estimation in transportation networks. This paper presents analytical models for the real-time estimation of Queue Lengths at traffic signals using the fundamental information (i.e., location and time) that probe vehicles provide. For a single Queue with Poisson arrivals, analytical models are developed to evaluate how error changes in Queue Length estimation as the percentage of probe vehicles in the traffic stream varies. When the overflow Queue is ignored, a closed-form solution is obtained for the variance of the estimation error. For the more general case with the overflow Queue, a formulation for the error variance is presented, which requires the marginal probability distribution of the overflow Queue as the input. In addition, an approximate model is presented for the latter case, which yields results that are comparable with the exact solution. Overall, the formulations presented here can be used to assess the error in Queue Length estimation from probe data without conducting simulation runs for various scenarios of probe vehicle market-penetration rates and congestion levels.
-
Queue Length estimation from probe vehicle location and the impacts of sample size
European Journal of Operational Research, 2009Co-Authors: Gurcan Comert, Mecit CetinAbstract:Probe vehicles are increasingly receiving more attention as an alternative means of collecting real-time traffic data needed for system optimization. This paper focuses on real-time estimation of Queue Lengths from the location information of probe vehicles in a Queue at an isolated and undersaturated intersection. The paper also addresses the evaluation of the accuracy of such estimates as a function of the market penetration of probe vehicles. An analytical formulation based on conditional probability distributions is developed for estimating the expected Queue Length and its variance. It is found that, for the given settings, only the location information of the last probe vehicle in the Queue is sufficient for the estimation. Exact expressions for the conditional mean and variance of Queue Length are derived. Various numerical results are documented to show how estimation errors behave by the volume to capacity ratio and by market penetration.
