Search NASA⌕ Search

SEARCH · Search NASA

Results for “Queues”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2026

Same Data, Different Audiences: Using Personas to Scope a Supercomputing Job Queue Visualization

Domain-specific visualizations sometimes focus on narrow, albeit important, tasks for one group of users. This focus limits the utility of a visualization to other groups working with the same data. While tasks elicited from other groups can present a design pitfall if not disambiguated, they also present a design opportunity—namely, the development of visualizations that support multiple groups. This development choice presents a trade-off of broadening the scope but limiting support for the more narrow tasks of any one group, which in some cases can enhance the overall utility of the visualization. We investigate this scenario through a design study where we develop Guidepost, a notebook-embedded visualization of data that helps scientists assess compute wait times, machine learning researchers understand prediction accuracy, and system maintainers analyze usage trends. We adapt the use of personas for visualization design from existing literature in the HCI and design domains, applying them to categorize tasks based on their uniqueness across stakeholder personas. Under this model, tasks shared between all groups should be supported by interactive visualizations and tasks unique to each group can be deferred to scripting with notebook-embedded visualization design. We evaluate our visualization through real-world case studies and a task-focused evaluation with nine participants. We observe that together, Guidepost's visual encodings, interactions, and export capabilities support the tasks of our differing personas.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1993

A Report on Stochastic Fairness Queueing (SFQ) Experiments

SRI International (SRI) has developed an improved queueing algorithm, known as Stochastic Fairness Queueing (SFQ), for best-effort traffic (i.e., traffic that does not require any guaranteed service). SFQ is a probablistic variant of strict fair queueing where instead of a single queue being allocated per flow, a fixed number of queues are used and a hash function maps the IP source and destination to a particular queue. A seed to the hash function is also perturbed occasionally to help distribute the flows amongst different queues when more than one flow maps to the same queue during the lifetime of the flow. SFQ provides 'fair' access by trying to ensure that each flow from source to destination host obtains equal access to the available bandwidth. This report covers a series of experiments performed on DARTnet evaluating the behavior and performance of SFQ against a FIFO queueing discipline. These experiments were designed to show SFQ's advantages and performance, and include tests demonstrating: Fair utilization of available resources; Starvation prevention; Graceful degradation under overload conditions; and Resource usage. In general, the experiments do show that SFQ is better than FIFO queueing at allocating bandwidth equally among a set of flows. SFQ also prevents a stream from dominating the available bandwidth, which seems to be a tendency with FIFO queueing (i.e., if a flow demands more than its share of the available bandwidth, with FIFO queueing that stream receives a disproportionate amount when compared to flows demanding less than their share). Furthermore, SFQ seems to reward 'nice' users of the network by providing a lower variance in delay and more throughput when their resource demand is less than their available share. Both SFQ and FIFO queueing seem to degrade fairly well as the network becomes saturated and to recover well as the network becomes less congested. Not unexpectedly, FIFO queueing is a little more efficient than SFQ-the delays are less and the throughput slightly higher because SFQ requires more processing. However, the performance difference between the two queueing disciplines is relatively small. However, the experiments do point out some interesting behavior. FIFO queueing can behave better than SFQ with seed perturbation. We recommend further evaluation of the hash function and the seed perturbation technique. There are probably weaknesses in their current selection that cause this unexpected behavior. SFQ also seems to possess good scaling properties. To verify this, more experiments with a larger number of streams from more hosts need to be executed and examined, including the staggered introduction of streams. Staggering the streams may prove important, because graphs in the degradation experiment revealed some unexpected increases and decreases in throughput, which should be examined. This may again be due to the interaction of the hash function with the seed perturbation but it may also be related to some other unknown problem.

Denny, Barbara A.↗
DOE OSTI2020

Dynamic Queue Prediction at Signalized Intersections with Fusing Sensory Information and Connected Vehicles

Queue length is one of the most essential metrics for indicating traffic conditions at signalized intersections. Most existing studies mainly focus on queue length estimation in a retrieving way which cannot effectively predict the future state of vehicle in queue. This paper proposes an innovative dynamic queue prediction model in a vehicle-infrastructure cooperative way. The proposed dynamic queue predictor can customize the queue prediction using the trajectories of preceding vehicles from radar detection with varying information from loop detectors and connected vehicles (CVs). The dynamic queue prediction accuracy can be further improved with at least one present CV in the same cycle. With the accurate dynamic queue prediction, we present a case study of Queue-Aware Eco-Approach and Departure (QEAD) to provide an online optimal vehicle trajectory considering both the signal status and preceding vehicle's future status in queue. The proposed framework and algorithms are of pragmatic significance and one of its advanced features is the ability to work under low penetration rate of CVs. The test using Next Generation SIMulation (NGSIM) dataset and a case study in VISSIM microscopic simulation show promising results.

Ye, Fei↗
NASA NTRS1992

Optimal routing and buffer allocation for a class of finite capacity queueing systems

The problem of routing jobs to K parallel queues with identical exponential servers and unequal finite buffer capacities is considered. Routing decisions are taken by a controller which has buffering space available to it and may delay routing of a customer to a queue. Using ideas from weak majorization, it is shown that the shorter nonfull queue delayed (SNQD) policy minimizes both the total number of customers in the system at any time and the number of customers that are rejected by that time. The SNQD policy always delays routing decisions as long as all servers are busy. Only when all the buffers at the controller are occupied is a customer routed to the queue with the shortest queue length that is not at capacity. Moreover, it is shown that, if a fixed number of buffers is to be distributed among the K queues, then the optimal allocation scheme is the one in which the difference between the maximum and minimum queue capacities is minimized, i.e., becomes either 0 or 1.

Towsley, Don↗
DOE OSTI2021

A Memory Efficient Lock-Free Circular Queue

Hardware queues are import in many applications, such as data transfer, synchronization of concurrent modules with the need of mutual exclusion constructs. State of the art bounded (of a fixed size) lock free circular queues are implemented either by read/write atomic operations, or barrier conditions, or by separating dequeue and enqueue operations. However, these queues always require an unused element at all the times to safe-guard the front and rear pointers of the queue, so as to avoid data race conditions, which leads to the waste of memory. The waste of memory is especially disadvantageous in applications such as I/O data transfer, and image transfer between processing filters, when large element size is needed, We propose a lock-free solution of the bounded circular queue through read/write atomic operations, but without the need of an extra element in the queue. The proposed solution is implemented and verified in both Verilog and ’C’ languages. We also demonstrate its effectiveness by comparing its area and delay metrics with the implementations of other existing designs of queue.

Miniskar, Narasinga Rao↗
NASA NTRS1983

Control of a heterogeneous two-server exponential queueing system

A dynamic control policy known as 'threshold queueing' is defined for scheduling customers from a Poisson source on a set of two exponential servers with dissimilar service rates. The slower server is invoked in response to instantaneous system loading as measured by the length of the queue of waiting customers. In a threshold queueing policy, a specific queue length is identified as a 'threshold,' beyond which the slower server is invoked. The slower server remains busy until it completes service on a customer and the queue length is less than its invocation threshold. Markov chain analysis is employed to analyze the performance of the threshold queueing policy and to develop optimality criteria. It is shown that probabilistic control is suboptimal to minimize the mean number of customers in the system. An approximation to the optimum policy is analyzed which is computationally simple and suffices for most operational applications.

Larsen, R. L.↗
NASA NTRS1998

Priority Queues for Computer Simulations

The present invention is embodied in new priority queue data structures for event list management of computer simulations, and includes a new priority queue data structure and an improved event horizon applied to priority queue data structures. ne new priority queue data structure is a Qheap and is made out of linked lists for robust, fast, reliable, and stable event list management and uses a temporary unsorted list to store all items until one of the items is needed. Then the list is sorted, next, the highest priority item is removed, and then the rest of the list is inserted in the Qheap. Also, an event horizon is applied to binary tree and splay tree priority queue data structures to form the improved event horizon for event management.

Steinman, Jeffrey S.↗
NASA NTRS2016

Departure Queue Prediction for Strategic and Tactical Surface Scheduler Integration

A departure metering concept to be demonstrated at Charlotte Douglas International Airport (CLT) will integrate strategic and tactical surface scheduling components to enable the respective collaborative decision making and improved efficiency benefits these two methods of scheduling provide. This study analyzes the effect of tactical scheduling on strategic scheduler predictability. Strategic queue predictions and target gate pushback times to achieve a desired queue length are compared between fast time simulations of CLT surface operations with and without tactical scheduling. The use of variable departure rates as a strategic scheduler input was shown to substantially improve queue predictions over static departure rates. With target queue length calibration, the strategic scheduler can be tuned to produce average delays within one minute of the tactical scheduler. However, root mean square differences between strategic and tactical delays were between 12 and 15 minutes due to the different methods the strategic and tactical schedulers use to predict takeoff times and generate gate pushback clearances. This demonstrates how difficult it is for the strategic scheduler to predict tactical scheduler assigned gate delays on an individual flight basis as the tactical scheduler adjusts departure sequence to accommodate arrival interactions. Strategic/tactical scheduler compatibility may be improved by providing more arrival information to the strategic scheduler and stabilizing tactical scheduler changes to runway sequence in response to arrivals.

departure scheduling↗
DOE OSTI2024

Evaluating Interconnection Queue Impacts Using Hosting Capacity Analysis

The interconnection queue has been identified as a bottleneck in the efforts to shift the nations generation resources towards renewable sources and meet various state and federal goals. Efforts such as the interconnection innovation e-Xchange (i2X) are therefore trying to come up with ways in which the queue could be altered to make interconnection faster, cheaper, and fairer. This paper proposes using hosting capacity analysis methods to simulate the evolution of a power system as new resources are added. Modeling the interconnection process in this way enables simulation based study of various policy decisions for queue management and cost allocation. Sample results are presented to illustrate how some queue modifications might play out both in distribution and transmission systems.

Distributed Energy Resources, Interconnection↗
NASA NTRS1976

Behavior of queues at signalized intersections in heavy traffic

This paper derives the asymptotic behavior of traffic queues at signalized intersections when the excess of departure capacity over arrivals approaches zero from above. The most interesting result is that the distribution of queue length approaches a negative exponential, with fewer restrictive assumptions than hitherto known. The main improvement results from more precise use of a combinatorial lemma of Spitzer, giving the maximum of the partial sums of a sequence of independent identically distributed random variables, plus some specific constructive probability calculations, many of them involving the Fourier transform. New results are presented on the probability that the queue be below a fixed bound and/or on the probability that the queue be empty. Applications to on-line estimators for real-time traffic control are suggested.

Posner, E. C.↗
NASA NTRS1984

In-trail dynamics of multiple CDTI-equipped aircraft queues

One of the potential problems of in-trail self-spacing with a Cockpit Display of Traffic Information (CDTI) is whether dynamic oscillations would occur in a queue of aircraft flying an approach, similar to the ""accordion'' effect seem with the queue of automobiles in stop-and-go traffic. In order to gain some insight into this potential problem, a brief experiment was conducted with the Transport Systems Research Vehicle (TSRV) ground-based simulator equipped with CDTI which presented the position of other aircraft in the area. Three simulation sessions were conducted wherein queues of up to nine aircraft were built, each one self-spacing on the preceding aircraft. The aircraft crews were rotated to ensure that the pilots had no prior knowledge of the lead aircraft behavior they would be following. Two different spacing criteria were employed: a constant time predictor criterion and a constant time delay criterion. The experiment failed to uncover any dynamic oscillatory tendencies in queues of seven to nine aircraft.

Kelly, J. R.↗
DOE OSTI2020

Deep Learning-Based Queue-Aware Eco-Approach and Departure System for Plug-In Hybrid Electric Buses at Signalized Intersections: A Simulation Study

Eco-Approach and Departure (EAD) has been considered as a promising eco-driving strategy for vehicles traveling in an urban environment, where information such as signal phase and timing (SPaT) and geometric intersection description is well utilized to guide vehicles passing through intersections in the most energy-efficient manner. Previous studies formulated the optimal trajectory planning problem as finding the shortest path on a graphical model. While this method is effective in terms of energy saving, its computation efficiency can be further enhanced by adopting machine learning techniques. In this paper, we propose an innovative deep learning-based queue-aware eco-approach and departure (DLQ-EAD) system for a plug-in hybrid electric bus (PHEB), which is able to provide an online optimal trajectory for the vehicle considering both the downstream traffic condition (i.e. traffic lights, queues) and the vehicle powertrain efficiency. Based on optimal solutions obtained from the graph-based trajectory planning algorithm (GTPA), a deep neural network (DNN) is developed to learn the optimal vehicle speed for the next time step given its current state. It is demonstrated that the trained DNN can provide energy-efficient trajectories with high computational efficiency and high flexibility adopting to dynamic changes in the surrounding environment. To address the impact of downstream traffic, a queue prediction model is further developed using data from radars and connected vehicles (CVs), as well as signal timing data from SPaT messages. A comprehensive simulation study in the microscopic traffic modeling software PTV VISSIM shows that the proposed DLQ-EAD can achieve 18.7%-24.0% energy efficiency improvements for a single PHEB on various traffic congestion levels. The proposed queue prediction model can be of practical significance even at low penetration rates of CVs. Specifically, additional energy savings of 2.0%-8.2% can be further achieved with 20% vehicles in the network.

Ye, Fei↗
DOE OSTI2023

Circular queue management with split indexes

Methods and apparatus for managing circular queues are disclosed. A pointer designates an index position of a particular queue element and contains an additional pointer state, whereby two pointer values (split indexes) can designate the same index position. Front and rear pointers are respectively managed by dequeue and enqueue logic. The front pointer state and rear pointer state distinguish full and empty queue states when both pointers designate the same index position. Asynchronous dequeue and enqueue operations are supported, no lock is required, and no queue entry is wasted. Hardware and software embodiments for numerous applications are disclosed.

Miniskar, Narasinga Rao↗
DOE OSTI2024

Quantifying Uncertainty in HPC Job Queue Time Predictions

High Performance Computing (HPC) has developed at an unprecedented pace in recent decades. This growth has demanded corresponding development in the area of HPC Operational Data Analytics (ODA), which encompasses a wide range of data analysis techniques, ML/AI efforts, tools, and visualizations. Published studies in ODA offer a variety of practical ways to inform HPC users, administrators, procurement managers, and other stakeholders. Uncertainty analysis, however, is rare in the related published literature. For instance, we identify only 1 out of 14 existing studies focused on job queue time prediction that investigates the uncertainty aspect of their proposed predictions. We recognize the utmost importance uncertainty quantification can have in such predictive analytics solutions, with consequences in how users interpret information they receive, and attempt to bridge this gap. With the goal of improving access to such insights, we develop a process for determining upper and lower bounds of the predicted queue times of a regression model at a specified confidence level. Our current research is focused on the uncertainty in predicting job queue times, yet our approach may be employed in predicting other metrics.

HPC↗
DOE OSTI2021

Automatic Traffic Queue-End Identification using Location-Based Waze User Reports

Traffic queues, especially queues caused by non-recurrent events such as incidents, are unexpected to high-speed drivers approaching the end of queue (EOQ) and become safety concerns. Though the topic has been extensively studied, the identification of EOQ has been limited by the spatial-temporal resolution of traditional data sources. This study explores the potential of location-based crowdsourced data, specifically Waze user reports. It presents a dynamic clustering algorithm that can group the location-based reports in real time and identify the spatial-temporal extent of congestion as well as the EOQ. The algorithm is a spatial-temporal extension of the density-based spatial clustering of applications with noise (DBSCAN) algorithm for real-time streaming data with an adaptive threshold selection procedure. Here, the proposed method was tested with 34 traffic congestion cases in the Knoxville, Tennessee area of the United States. It is demonstrated that the algorithm can effectively detect spatial-temporal extent of congestion based on Waze report clusters and identify EOQ in real-time. The Waze report-based detection are compared to the detection based on roadside sensor data. The results are promising: The EOQ identification time of Waze is similar to the EOQ detection time of traffic sensor data, with only 1.1 min difference on average. In addition, Waze generates 1.9 EOQ detection points every mile, compared to 1.8 detection points generated by traffic sensor data, suggesting the two data sources are comparable in respect of reporting frequency. The results indicate that Waze is a valuable complementary source for EOQ detection where no traffic sensors are installed.

99 GENERAL AND MISCELLANEOUS↗
DOE OSTI2023

Waiting in Queue: A Historical Evaluation of Interconnection Policy

Both states and Independent System Operators (ISO)/Regional Transmission Organizations (RTO) have struggled with long wait times in interconnection queues. As a result, numerous reforms have been proposed to expedite the connection of new resources to the grid. This paper conducts a quantitative analysis of two of these policies: one providing detail hosting capacity information in Massachusetts, the other experimenting with cost allocation in New York. We find that both policies led to a statistically significant decrease in the times projects spend pending in interconnection queues, with New York seeing a small drop in days pending, and Massachusetts seeing a much larger one. We also include an analysis of how energy storage is impacts queue time in these states. These results can help inform regulators who are weighing reforms to interconnection policies, with the goal of reducing wait times.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1979

Application of queueing models to multiprogrammed computer systems operating in a time-critical environment

A model of a central processor (CPU) which services background applications in the presence of time critical activity is presented. The CPU is viewed as an M/M/1 queueing system subject to periodic interrupts by deterministic, time critical process. The Laplace transform of the distribution of service times for the background applications is developed. The use of state of the art queueing models for studying the background processing capability of time critical computer systems is discussed and the results of a model validation study which support this application of queueing models are presented.

Eckhardt, D. E., Jr.↗
NASA NTRS1986

The network queueing system

Described is the implementation of a networked, UNIX based queueing system developed on contract for NASA. The system discussed supports both batch and device requests, and provides the facilities of remote queueing, request routing, remote status, queue access controls, batch request resource quota limits, and remote output return.

Kingsbury, Brent K.↗