Search NASA⌕ Search

SEARCH · Search NASA

Results for “traffic queue model”

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.

18 records
All sourcesNASA NTRSDOE OSTI
NASA NTRSDate not supplied

Traffic Flow Analysis for Package Delivery Drones using a Queueing Model

A key component of the small unmanned aircraft systems traffic management ecosystem is the design of scalable algorithms for strategic deconfliction of drones prior to takeoff. In this work, we focus on efficient flow management of drones on a network of intersecting edges subject to two kinds of spacing constraints: 1) between any two adjacent vehicles on an edge and 2) between any two vehicles on two different edges arriving one after the other at an intersection. The spacing is designed to enable non-intersection of operational volumes corresponding to two different vehicles thereby properly separating the vehicles inside each volume. For simplicity, we assume a constant ground speed for the drones and fixed dimensions for the operational volume blocks. The deconfliction is managed by adjusting the takeoff time of the drones, thereby regulating their arrival time at various crossing waypoints in the network. This framework allows us to study the maximum flow (throughput) of vehicles on a network of edges connecting depots to drop off sites subject to the temporal spacing constraints. The departure scheduling of individual drones results in a combinatorial optimization problem. To alleviate this, we solve a max-flow formulation and use queueing theory to simplify the analysis and provide upper bounds to the underlying optimization problem for individual drone departure scheduling. Our results indicate that throughput drops rapidly after the density of drones in the network passes the max-flow limits.

Alexey A Munishkin↗
NASA NTRS2003

Modeling and Control of Airport Queueing Dynamics under Severe Flow Restrictions

Based on field observations and interviews with controllers at BOS and EWR, we identify the closure of local departure fixes as the most severe class of airport departure restrictions. A set of simple queueing dynamics and traffic rules are developed to model departure traffic under such restrictions. The validity of the proposed model is tested via Monte Carlo simulation against 10 hours of actual operations data collected during a case-study at EWR on June 29,2000. In general, the model successfully reproduces the aggregate departure congestion. An analysis of the average error over 40 simulation runs indicates that flow-rate restrictions also significantly impact departure traffic; work is underway to capture these effects. Several applications and what-if scenarios are discussed for future evaluation using the calibrated model.

Carr, Francis↗
NASA NTRS1979

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.↗
NASA NTRS1992

NCC Simulation Model: Simulating the operations of the network control center, phase 2

The simulation of the network control center (NCC) is in the second phase of development. This phase seeks to further develop the work performed in phase one. Phase one concentrated on the computer systems and interconnecting network. The focus of phase two will be the implementation of the network message dialogues and the resources controlled by the NCC. These resources are requested, initiated, monitored and analyzed via network messages. In the NCC network messages are presented in the form of packets that are routed across the network. These packets are generated, encoded, decoded and processed by the network host processors that generate and service the message traffic on the network that connects these hosts. As a result, the message traffic is used to characterize the work done by the NCC and the connected network. Phase one of the model development represented the NCC as a network of bi-directional single server queues and message generating sources. The generators represented the external segment processors. The served based queues represented the host processors. The NCC model consists of the internal and external processors which generate message traffic on the network that links these hosts. To fully realize the objective of phase two it is necessary to identify and model the processes in each internal processor. These processes live in the operating system of the internal host computers and handle tasks such as high speed message exchanging, ISN and NFE interface, event monitoring, network monitoring, and message logging. Inter process communication is achieved through the operating system facilities. The overall performance of the host is determined by its ability to service messages generated by both internal and external processors.

Benjamin, Norman M.↗
NASA NTRSDate not supplied

A Queuing Theory Approach to Pilot-Controller Coordination for m:N Operations

In recent years, attention and interest by industry and researchers has grown in a control paradigm for remotely piloted aircraft termed “m:N operations.” In an m:N operation, a team of m remote pilots in command (RIPCs) collaboratively manage the flights of N aircraft. A consequence of an m:N concept of operations is that the RPICs will have to switch attention from one aircraft to another and from one task to another. Previous research in m:N operations has focused on the workload experienced by an RPIC and their level of situation awareness on their flights. Researchers have found that RPIC workload and situation awareness are generally sensitive to increasing N, although NASA’s Multi-Vehicle (m:N) Working Group has suggested that the driver of workload/situation awareness is the number of exceptions requiring human intervention as opposed to the value of N itself. In any case, a natural antecedent of workload is task load. In this paper, queueing theory is applied to a 1:N Urban Air Mobility (UAM) air taxi operation in order to estimate pilot task load for managing radio communications with air traffic controllers (ATCs) under increasing N. An M/M/1 queueing system is used to model the RIPC’s servicing of calls and clearance requests (e.g., departure, arrival, or airspace transition) to ATC for the N aircraft. Important parameters for the queueing model are the task arrival rate and the average service time for task completion. Radio communication times from past human-in-the-loop simulation studies are used to measure service times for a 1:4 and 1:12 UAM operation and to interpolate service times for 4 < N < 12. A Monte Carlo method is then employed, using the measured and interpolated service times, to estimate arrival rate and related queueing statistics. The paper concludes by considering the estimated queuing statistics, particularly the RPIC’s utilization (i.e., proportion of time actively servicing tasks), the length of the task queue over time, and the implications for task-balanced system design.

task load↗
NASA NTRS1993

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↗
NASA NTRS1990

Rate-based congestion control in networks with smart links, revision

The author uses a network simulator to explore rate-based congestion control in networks with smart links that can feed back information to tell senders to adjust their transmission rates. This method differs in a very important way from congestion control in which a congested network component just drops packets - the most commonly used method. It is clearly advantageous for the links in the network to communicate with the end users about the network capacity, rather than the users unilaterally picking a transmission rate. The components in the middle of the network, not the end users, have information about the capacity and traffic in the network. The author experiments with three different algorithms for calculating the control rate to feed back to the users. All of the algorithms exhibit problems in the form of large queues when simulated with a configuration modeling the dynamics of a packet-voice system. However, the problems are not with the algorithms themselves, but with the fact that feedback takes time. If the network steady-state utilization is low enough that it can absorb transients in the traffic through it, then the large queues disappear. If the users are modified to start sending slowly, to allow the network to adapt to a new flow without causing congestion, a greater portion of the network's bandwidth can be used.

Heybey, Andrew Tyrrell↗
NASA NTRS1990

Queueing models for token and slotted ring networks

Currently the end-to-end delay characteristics of very high speed local area networks are not well understood. The transmission speed of computer networks is increasing, and local area networks especially are finding increasing use in real time systems. Ring networks operation is generally well understood for both token rings and slotted rings. There is, however, a severe lack of queueing models for high layer operation. There are several factors which contribute to the processing delay of a packet, as opposed to the transmission delay, e.g., packet priority, its length, the user load, the processor load, the use of priority preemption, the use of preemption at packet reception, the number of processors, the number of protocol processing layers, the speed of each processor, and queue length limitations. Currently existing medium access queueing models are extended by adding modeling techniques which will handle exhaustive limited service both with and without priority traffic, and modeling capabilities are extended into the upper layers of the OSI model. Some of the model are parameterized solution methods, since it is shown that certain models do not exist as parameterized solutions, but rather as solution methods.

Peden, Jeffery H.↗
NASA NTRS2003

Input-Output Modeling and Control of the Departure Process of Congested Airports

A simple queueing model of busy airport departure operations is proposed. This model is calibrated and validated using available runway configuration and traffic data. The model is then used to evaluate preliminary control schemes aimed at alleviating departure traffic congestion on the airport surface. The potential impact of these control strategies on direct operating costs, environmental costs and overall delay is quantified and discussed.

Pujet, Nicolas↗
NASA NTRS1977

A computerized traffic control algorithm to determine optimal traffic signal settings

An algorithm was developed to optimally control the traffic signals at each intersection using a discrete time traffic model applicable to heavy or peak traffic. Off line optimization procedures were applied to compute the cycle splits required to minimize the lengths of the vehicle queues and delay at each intersection. The method was applied to an extensive traffic network in Toledo, Ohio. Results obtained with the derived optimal settings are compared with the control settings presently in use.

Seldner, K.↗
NASA NTRS1991

The effect of model uncertainty on some optimal routing problems

The effect of model uncertainties on optimal routing in a system of parallel queues is examined. The uncertainty arises in modeling the service time distribution for the customers (jobs, packets) to be served. For a Poisson arrival process and Bernoulli routing, the optimal mean system delay generally depends on the variance of this distribution. However, as the input traffic load approaches the system capacity the optimal routing assignment and corresponding mean system delay are shown to converge to a variance-invariant point. The implications of these results are examined in the context of gradient-based routing algorithms. An example of a model-independent algorithm using online gradient estimation is also included.

Mohanty, Bibhu↗
NASA NTRS2001

Air Traffic Control Improvement Using Prioritized CSMA

Version 7 simulations of the industry-standard network simulation software "OPNET" are presented of two applications of the Aeronautical Telecommunications Network (ATN), Controller Pilot Data Link Communications (CPDLC) and Automatic Dependent Surveillance-Broadcast mode (ADS-B), over VHF Data Link mode 2 (VDL-2). Communication is modeled for air traffic between just three cities. All aircraft are assumed to have the same equipage. The simulation involves Air Traffic Control (ATC) ground stations and 105 aircraft taking off, flying realistic free-flight trajectories, and landing in a 24-hr period. All communication is modeled as unreliable. Collision-less, prioritized carrier sense multiple access (CSMA) is successfully tested. The statistics presented include latency, queue length, and packet loss. This research may show that a communications system simpler than the currently accepted standard envisioned may not only suffice, but also surpass performance of the standard at a lower cost of deployment.

Robinson, Daryl C.↗
NASA NTRS2017

Evaluation of a Tactical Surface Metering Tool for Charlotte Douglas International Airport Via Human-in-the-Loop Simulation

NASA has been working with the FAA and aviation industry partners to develop and demonstrate new concepts and technologies that integrate arrival, departure, and surface traffic management capabilities. In March 2017, NASA conducted a human-in-the-loop (HITL) simulation for integrated surface and airspace operations, modeling Charlotte Douglas International Airport, to evaluate the operational procedures and information requirements for the tactical surface metering tool, and data exchange elements between the airline controlled ramp and ATC Tower. In this paper, we focus on the calibration of the tactical surface metering tool using various metrics measured from the HITL simulation results. Key performance metrics include gate hold times from pushback advisories, taxi-in/out times, runway throughput, and departure queue size. Subjective metrics presented in this paper include workload, situational awareness, and acceptability of the metering tool and its calibration

air traffic management↗
NASA NTRS1987

Optimal service allocation among two heterogeneous traffic types with no queueing

Two communication traffic streams with Poisson statistics arrive at a network node. These are to be transmitted across a channel with a total bandwidth capacity of C slots. Messages not accepted at the node are assumed to be lost. Under the assumptions of exponential service time distributions, the problem of dynamic allocation of available channel bandwidth among the two traffic types is studied in order to minimize a weighted sum of blocking probabilities. Modeling the system as a two-dimensional Markov chain is studied to minimize a weighted sum of blocking probabilities. Modeling the system as a two-dimensional Markov chain, it is shown by an application of dynamic programming principles that the optimal policy has the form of a 'switching curve'.

Lambadaris, I.↗
NASA NTRS1992

Dynamically-allocated multi-queue buffers for VLSI communication switches

Several buffer structures are discussed and compared in terms of implementation complexity, interswitch handshaking requirements, and their ability to deal with variations in traffic patterns and message lengths. A new design of buffers is presented that provide non-FIFO message handling and efficient storage allocation for variable size packets using linked lists managed by a simple on-chip controller. The new buffer design is evaluated by comparing it to several alternative designs in the context of a multistage interconnection network. The present modeling and simulations show that the new buffer outperforms alternative buffers and can thus be used to improve the performance of a wide variety of systems currently using less efficient buffers.

Tamir, Yuval↗
NASA NTRS1972

A model for the I/O-channel traffic in computer systems.

A new model is proposed which is based on the assumption that the actual traffic to be processed by an I/O channel system is generated as the overflow from a fictitious server system having Poisson traffic as the input. The number of servers and the mean arrival rate can be readily adjusted to verify the main value and the variance of the actual traffic to be handled. A closed solution for the stationary probabilities of state is obtained, and the parameters conventionally used to describe the grade of performance of queuing systems (such as mean queue length, mean waiting time, and probability of waiting) are defined.

Kuemmerle, K.↗
NASA NTRS2017

Evaluation of a Tactical Surface Metering Tool for Charlotte Douglas International Airport via Human-in-the-Loop Simulation

NASA has been working with the FAA and aviation industry partners to develop and demonstrate new concepts and technologies that integrate arrival, departure, and surface traffic management capabilities. In March 2017, NASA conducted a human-in-the-loop (HITL) simulation for integrated surface and airspace operations, modeling Charlotte Douglas International Airport, to evaluate the operational procedures and information requirements for the tactical surface metering tool, and data exchange elements between the airline controlled ramp and ATC Tower. In this paper, we focus on the calibration of the tactical surface metering tool using various metrics measured from the HITL simulation results. Key performance metrics include gate hold times from pushback advisories, taxi-in-out times, runway throughput, and departure queue size. Subjective metrics presented in this paper include workload, situational awareness, and acceptability of the metering tool and its calibration.

Verma, Savita↗
NASA NTRS2016

An Integrated Gate Turnaround Management Concept Leveraging Big Data Analytics for NAS Performance Improvements

"Gate Turnaround" plays a key role in the National Air Space (NAS) gate-to-gate performance by receiving aircraft when they reach their destination airport, and delivering aircraft into the NAS upon departing from the gate and subsequent takeoff. The time spent at the gate in meeting the planned departure time is influenced by many factors and often with considerable uncertainties. Uncertainties such as weather, early or late arrivals, disembarking and boarding passengers, unloading/reloading cargo, aircraft logistics/maintenance services and ground handling, traffic in ramp and movement areas for taxi-in and taxi-out, and departure queue management for takeoff are likely encountered on the daily basis. The Integrated Gate Turnaround Management (IGTM) concept is leveraging relevant historical data to support optimization of the gate operations, which include arrival, at the gate, departure based on constraints (e.g., available gates at the arrival, ground crew and equipment for the gate turnaround, and over capacity demand upon departure), and collaborative decision-making. The IGTM concept provides effective information services and decision tools to the stakeholders, such as airline dispatchers, gate agents, airport operators, ramp controllers, and air traffic control (ATC) traffic managers and ground controllers to mitigate uncertainties arising from both nominal and off-nominal airport gate operations. IGTM will provide NAS stakeholders customized decision making tools through a User Interface (UI) by leveraging historical data (Big Data), net-enabled Air Traffic Management (ATM) live data, and analytics according to dependencies among NAS parameters for the stakeholders to manage and optimize the NAS performance in the gate turnaround domain. The application will give stakeholders predictable results based on the past and current NAS performance according to selected decision trees through the UI. The predictable results are generated based on analysis of the unique airport attributes (e.g., runway, taxiway, terminal, and gate configurations and tenants), and combined statistics from past data and live data based on a specific set of ATM concept-of-operations (ConOps) and operational parameters via systems analysis using an analytic network learning model. The IGTM tool will then bound the uncertainties that arise from nominal and off-nominal operational conditions with direct assessment of the gate turnaround status and the impact of a certain operational decision on the NAS performance, and provide a set of recommended actions to optimize the NAS performance by allowing stakeholders to take mitigation actions to reduce uncertainty and time deviation of planned operational events. An IGTM prototype was developed at NASA Ames Simulation Laboratories (SimLabs) to demonstrate the benefits and applicability of the concept. A data network, using the System Wide Information Management (SWIM)-like messaging application using the ActiveMQ message service, was connected to the simulated data warehouse, scheduled flight plans, a fast-time airport simulator, and a graphic UI. A fast-time simulation was integrated with the data warehouse or Big Data/Analytics (BAI), scheduled flight plans from Aeronautical Operational Control AOC, IGTM Controller, and a UI via a SWIM-like data messaging network using the ActiveMQ message service, illustrated in Figure 1, to demonstrate selected use-cases showing the benefits of the IGTM concept on the NAS performance.

Efficent ATM systems↗