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 73 records · Page 4

Fast simulation of packet loss rates in a shared buffer communications switch

This paper describes an efficient technique for estimating, via simulation, the probability of buffer overflows in a queueing model that arises in the analysis of ATM (Asynchronous Transfer Mode) communication switches. There are multiple streams of (autocorrelated) traffic feeding the switch that has a buffer of finite capacity. Each stream is designated as either being of high or low priority. When the queue length reaches a certain threshold, only high priority packets are admitted to the switch's buffer. The problem is to estimate the loss rate of high priority packets. An asymptotically optimal importance sampling approach is developed for this rare event simulation problem. In this approach, the importance sampling is done in two distinct phases. In the first phase, an importance sampling change of measure is used to bring the queue length up to the threshold at which low priority packets get rejected. In the second phase, a different importance sampling change of measure is used to move the queue length from the threshold to the buffer capacity.

Chang, Cheng-Shang↗

Parallel integer sorting with medium and fine-scale parallelism

Two new parallel integer sorting algorithms, queue-sort and barrel-sort, are presented and analyzed in detail. These algorithms do not have optimal parallel complexity, yet they show very good performance in practice. Queue-sort designed for fine-scale parallel architectures which allow the queueing of multiple messages to the same destination. Barrel-sort is designed for medium-scale parallel architectures with a high message passing overhead. The performance results from the implementation of queue-sort on a Connection Machine CM-2 and barrel-sort on a 128 processor iPSC/860 are given. The two implementations are found to be comparable in performance but not as good as a fully vectorized bucket sort on the Cray YMP.

Dagum, Leonardo↗

A Simulation Study of Paced TCP

In this paper, we study the performance of paced TCP, a modified version of TCP designed especially for high delay- bandwidth networks. In typical networks, TCP optimizes its send-rate by transmitting increasingly large bursts, or windows, of packets, one burst per round-trip time, until it reaches a maximum window-size, which corresponds to the full capacity of the network. In a network with a high delay-bandwidth product, however, Transmission Control Protocol's (TCPs) maximum window-size may be larger than the queue size of the intermediate routers, and routers will begin to drop packets as soon as the windows become too large for the router queues. The TCP sender then concludes that the bottleneck capacity of the network has been reached, and it limits its send-rate accordingly. Partridge proposed paced TCP as a means of solving the problem of queueing bottlenecks. A sender using paced TCP would release packets in multiple, small bursts during a round-trip time in which ordinary TCP would release a single, large burst of packets. This approach allows the sender to increase its send-rate to the maximum window size without encountering queueing bottlenecks. This paper describes the performance of paced TCP in a simulated network and discusses implementation details that can affect the performance of paced TCP.

Kulik, Joanna↗

Job Scheduling Under the Portable Batch System

The typical batch queuing system schedules jobs for execution by a set of queue controls. The controls determine from which queues jobs may be selected. Within the queue, jobs are ordered first-in, first-run. This limits the set of scheduling policies available to a site. The Portable Batch System removes this limitation by providing an external scheduling module. This separate program has full knowledge of the available queued jobs, running jobs, and system resource usage. Sites are able to implement any policy expressible in one of several procedural language. Policies may range from "bet fit" to "fair share" to purely political. Scheduling decisions can be made over the full set of jobs regardless of queue or order. The scheduling policy can be changed to fit a wide variety of computing environments and scheduling goals. This is demonstrated by the use of PBS on an IBM SP-2 system at NASA Ames.

Henderson, Robert L.↗

Delay Banking for Managing Air Traffic

Delay banking has been invented to enhance air-traffic management in a way that would increase the degree of fairness in assigning arrival, departure, and en-route delays and trajectory deviations to aircraft impacted by congestion in the national airspace system. In delay banking, an aircraft operator (airline, military, general aviation, etc.) would be assigned a numerical credit when any of their flights are delayed because of an air-traffic flow restriction. The operator could subsequently bid against other operators competing for access to congested airspace to utilize part or all of its accumulated credit. Operators utilize credits to obtain higher priority for the same flight, or other flights operating at the same time, or later, in the same airspace, or elsewhere. Operators could also trade delay credits, according to market rules that would be determined by stakeholders in the national airspace system. Delay banking would be administered by an independent third party who would use delay banking automation to continually monitor flights, allocate delay credits, maintain accounts of delay credits for participating airlines, mediate bidding and the consumption of credits of winning bidders, analyze potential transfers of credits within and between operators, implement accepted transfers, and ensure fair treatment of all participating operators. A flow restriction can manifest itself in the form of a delay in assigned takeoff time, a reduction in assigned airspeed, a change in the position for the aircraft in a queue of all aircraft in a common stream of traffic (e.g., similar route), a change in the planned altitude profile for an aircraft, or change in the planned route for the aircraft. Flow restrictions are typically imposed to mitigate traffic congestion at an airport or in a region of airspace, particularly congestion due to inclement weather, or the unavailability of a runway or region of airspace. A delay credit would be allocated to an operator of a flight that has accepted, or upon which was imposed, a flow restriction. The amount of the credit would increase with the amount of delay caused by the flow restriction, the exact amount depending on which of several candidate formulas is eventually chosen. For example, according to one formula, there would be no credit for a delay smaller than some threshold value (e.g., 30 seconds) and the amount of the credit for a longer delay would be set at the amount of the delay minus the threshold value. Optionally, the value of a delay credit could be made to decay with time according to a suitable formula (e.g., an exponential decay). Also, optionally, a transaction charge could be assessed against the value of a delay credit that an operator used on a flight different from the one for which the delay originated or that was traded with a different operator. The delay credits accumulated by a given airline could be utilized in various ways. For example, an operator could enter a bid for priority handling in a new flow restriction that impacts one or more of the operator s flights; if the bid were unsuccessful, all or a portion of the credit would be returned to the bidder. If the bid pertained to a single aircraft that was in a queue, delay credits could be consumed in moving the aircraft to an earlier position within the queue. In the case of a flow restriction involving a choice of alternate routes, planned altitude profile, aircraft spacing, or other non-queue flow restrictions, delay credits could be used to bid for an alternative assignment.

Green, Steve↗

A new traffic control design method for large networks with signalized intersections

The paper presents a traffic control design technique for application to large traffic networks with signalized intersections. It is shown that the design method adopts a macroscopic viewpoint to establish a new traffic modelling procedure in which vehicle platoons are subdivided into main stream queues and turning queues. Optimization of the signal splits minimizes queue lengths in the steady state condition and improves traffic flow conditions, from the viewpoint of the traveling public. Finally, an application of the design method to a traffic network with thirty-three signalized intersections is used to demonstrate the effectiveness of the proposed technique.

Leininger, G. G.↗

A microprocessor based high speed space-borne packet switch

The design and performance evaluation of a single microprocessor based packet switch for use on-board a satellite are presented. The primary design criterion is to maximize the system throughput. A number of protocols and their impact on the switch design are discussed. Stem and processor hardware architectures are described. The flow charts of the software required to accomplish the essential functions are presented and modification needed for use in a multisatellite network are also indicated. Maximum throughput attainable is calculated, desirable characteristics of microprocessors for this application are pointed out. A queue theoretic model of the packet switch has been developed. Analytical relationships of the average waiting times and the queue sizes at the queues and the overall average response time with the various design parameters of the switch have been obtained. A number of graphs showing the effect of variation in the number of input and output lines, data rates, destination functions, speed of output lines and some other design parameters on the performance of the switch are presented and discussed.

Arozullah, M.↗

A microprocessor based satellite borne packet switch

Design considerations applicable to a space-borne single microprocessor based packet switch are identified. These include system architecture decisions and microprocessor selection. The division of tasks among different subroutines is discussed. The primary design criterion is to maximize throughput. The extension to a multi-satellite network is discussed. The maximum throughput attainable is derived. A queue theoretic model has been developed and expressions for average response times and average queue sizes are obtained. A number of graphs showing the effect of various design parameters on the average response time and the average queue sizes are presented.

Crist, S. C.↗

Parallel discrete event simulation using shared memory

With traditional event-list techniques, evaluating a detailed discrete-event simulation-model can often require hours or even days of computation time. By eliminating the event list and maintaining only sufficient synchronization to ensure causality, parallel simulation can potentially provide speedups that are linear in the numbers of processors. A set of shared-memory experiments, using the Chandy-Misra distributed-simulation algorithm, to simulate networks of queues is presented. Parameters of the study include queueing network topology and routing probabilities, number of processors, and assignment of network nodes to processors. These experiments show that Chandy-Misra distributed simulation is a questionable alternative to sequential-simulation of most queueing network models.

Reed, Daniel A.↗

Analysis of exhaustive limited service for token ring networks

Token ring operation is well-understood in the cases of exhaustive, gated, gated limited, and ordinary cyclic service. There is no current data, however, on queueing models for the exhaustive limited service type. This service type differs from the others in that there is a preset maximum (omega) on the number of packets which may be transmitted per token reception, and packets which arrive after token reception may still be transmitted if the preset packet limit has not been reached. Exhaustive limited service is important since it closely approximates a timed token service discipline (the approximation becomes exact if packet lengths are constant). A method for deriving the z-transforms of the distributions of the number of packets present at both token departure and token arrival for a system using exhaustive limited service is presented. This allows for the derivation of a formula for mean queueing delay and queue lengths. The method is theoretically applicable to any omega. Fortunately, as the value of omega becomes large (typically values on the order of omega = 8 are considered large), the exhaustive limited service discipline closely approximates an exhaustive service discipline.

Peden, Jeffery H.↗

Systolic array processing of the sequential decoding algorithm

A systolic array processing technique is applied to implementing the stack algorithm form of the sequential decoding algorithm. It is shown that sorting, a key function in the stack algorithm, can be efficiently realized by a special type of systolic arrays known as systolic priority queues. Compared to the stack-bucket algorithm, this approach is shown to have the advantages that the decoding always moves along the optimal path, that it has a fast and constant decoding speed and that its simple and regular hardware architecture is suitable for VLSI implementation. Three types of systolic priority queues are discussed: random access scheme, shift register scheme and ripple register scheme. The property of the entries stored in the systolic priority queue is also investigated. The results are applicable to many other basic sorting type problems.

Chang, C. Y.↗

An architecture for real-time vision processing

To study the feasibility of developing an architecture for real time vision processing, a task queue server and parallel algorithms for two vision operations were designed and implemented on an i860-based Mercury Computing System 860VS array processor. The proposed architecture treats each vision function as a task or set of tasks which may be recursively divided into subtasks and processed by multiple processors coordinated by a task queue server accessible by all processors. Each idle processor subsequently fetches a task and associated data from the task queue server for processing and posts the result to shared memory for later use. Load balancing can be carried out within the processing system without the requirement for a centralized controller. The author concludes that real time vision processing cannot be achieved without both sequential and parallel vision algorithms and a good parallel vision architecture.

Chien, Chiun-Hong↗

Tactical Surface Metering Procedures for Charlotte Douglas International Airport

NASA has been collaborating with the Federal Aviation Administration (FAA) and aviation industry partners to develop and demonstrate new concepts and technologies for the Integrated Arrival, Departure, and Surface (IADS) traffic management capabilities under the Airspace Technology Demonstration 2 (ATD-2) project. The primary goal of the ATD-2 project is to improve the predictability and the operational efficiency of the air traffic system in metroplex environments while maintaining or improving throughput by enhancing and integrating arrival, departure and surface prediction, scheduling, and management systems. In the Phase 1 Baseline IADS Demonstration, the tactical surface scheduling capability and the user interfaces for ramp controllers and ramp traffic managers were implemented for ramp operations. The purpose of the tactical surface scheduling capability is to provide the airline ramp controller with aircraft pushback advisories that prevent surface congestion and to respond to surface and airspace constraints that become known over relatively short time horizons. For this purpose, the tactical surface metering tool first estimates the capacity of current and near-future runway resources from flight schedule and surveillance data. With demand forecasts and predicted taxi trajectories, this tool computes an efficient runway schedule of aircraft in the planning horizon based on their readiness, Earliest Off-Block Times (EOBTs), and a ration by schedule (RBS) rule. Details on the implementation of the Tactical Surface Metering tool will be provided in the full paper. Both pushback and recommended hold times advisories provided by this surface metering tool are shown on the user interfaces for the ramp controller and the ramp traffic manager, called Ramp Traffic Console (RTC) and Ramp Manager Traffic Console (RMTC), respectively. There is excess queue time in the system due to demand capacity imbalance, this time can be taken as a hold on the runway queue or at the gate and was referred to as the Metering Value. This metering value can be adjusted by the Ramp Manager in collaboration with Air Traffic Controller-Tower Traffic Management Coordinator (TMC). They selected a set of metering values as default values for the tool during human-in-the-loop simulation. As the metering value increases, there is a decrease in the gate hold and increase in the queue time at the runway. Procedures and Information needs related to managing the surface metering procedures were researched in the simulated environment. These procedures will be compared to the procedures adopted at Charlotte Douglas International Airport when the tools were deployed and adopted in November 2017 for one departure push bank per day. Feedback regarding initial issues, information needs such as the need to see EOBTs on the flight data tags and how they compare to scheduled times will also be discussed in the full paper. Initial results will be provided regarding the choice of the metering value and how it was adjusted on a daily basis and what procedures evolved will also be presented in the paper.

surface metering↗

DSN command system Mark III-78

The Deep Space Network command Mark III-78 data processing system includes a capability for a store-and-forward handling method. The functions of (1) storing the command files at a Deep Space station; (2) attaching the files to a queue; and (3) radiating the commands to the spacecraft are straightforward. However, the total data processing capability is a result of assuming worst case, failure-recovery, or nonnominal operating conditions. Optional data processing functions include: file erase, clearing the queue, suspend radiation, command abort, resume command radiation, and close window time override.

Stinnett, W. G.↗

A microprocessor based high speed packet switch for satellite communications

The architectures of a single processor, a three processor, and a multiple processor system are described. The hardware circuits, and software routines required for implementing the three and multiple processor designs are presented. A bit-slice microprocessor was designed and microprogrammed. Maximum throughput was calculated for all three designs. Queue theoretic models for these three designs were developed and utilized to obtain analytical expressions for the average waiting times, overall average response times and average queue sizes. From these expressions, graphs were obtained showing the effect on the system performance of a number of design parameters.

Arozullah, M.↗

Adaptive allocation of decisionmaking responsibility between human and computer in multitask situations

As human and computer come to have overlapping decisionmaking abilities, a dynamic or adaptive allocation of responsibilities may be the best mode of human-computer interaction. It is suggested that the computer serve as a backup decisionmaker, accepting responsibility when human workload becomes excessive and relinquishing responsibility when workload becomes acceptable. A queueing theory formulation of multitask decisionmaking is used and a threshold policy for turning the computer on/off is proposed. This policy minimizes event-waiting cost subject to human workload constraints. An experiment was conducted with a balanced design of several subject runs within a computer-aided multitask flight management situation with different task demand levels. It was found that computer aiding enhanced subsystem performance as well as subjective ratings. The queueing model appears to be an adequate representation of the multitask decisionmaking situation, and to be capable of predicting system performance in terms of average waiting time and server occupancy. Server occupancy was further found to correlate highly with the subjective effort ratings.

Chu, Y.-Y.↗

Evaluation of a three-processor architecture for a satellite packet switch

The architecture of a microprocessor-based packet switch using three processors for use on-board satellites is presented. The operation of the switch involves three distinct functions, namely, the input, the routing and the output functions. Each of these functions is performed by one of the three microprocessors. The operation of the switch along with those of the corresponding software routines are explained. An expression for the throughput is presented. A queue theoretic model of the switch is developed. Analytical expressions for the overall average response time at the various queues are obtained. A number of graphs showing the average response time as a function of some parameters of the switch are also presented.

Arozullakh, M.↗

On the design of prioritized multiplexing systems

Systems in which many data sources are multiplexed over a single communication channel are considered. Data from all the sources are generated in fixed-length packets, and are stored in a common buffer with finite capacity. Packets overflowed or removed from the buffer prior to transmission are lost. The system performance measure is the set of packet loss probabilities associated with the sources. Queueing disciplines vary depending on the stringency of prioritization and the utilization of system resources. The set of all possible performances is characterized as the set of all queueing disciplines is spanned. Whether a given performance is possible can be deduced. Strategies that achieve the minimum overall loss probability are identified. The extreme disciplines are specified, and their performances are calculable by means of a given algorithm.

Clare, L. P.↗