We address the security of a network of Connected and Automated Vehicles (CAVs) cooperating to safely navigate through a conflict area (e.g., traffic intersections, merging roadways, roundabouts). Previous studies have shown that such a network can be targeted by adversarial attacks causing traffic jams or safety violations resulting in collisions. We focus on attacks targeting the V2X communication network used to share vehicle data and consider uncertainties as well due to noise in sensor measurements and communication channels. To combat these, motivated by recent work on the safe control of CAVs, we propose a trust-aware robust event-triggered decentralized control and coordination framework that can provably guarantee safety. We maintain a trust metric for each vehicle in the network computed based on their behavior and used to balance the tradeoff between conservativeness (when deeming every vehicle as untrustworthy) while guaranteeing safety and performance. It is important to highlight that our framework is invariant to the specific choice of the trust framework. Moreover, we show that our proposed trust framework is immune to false positives. Based on this framework, we propose an attack detection and mitigation scheme which provably guarantees safety against false positive cases which may arise from a poor choice of trust framework. We use extensive simulations in SUMO and CARLA to validate the theoretical guarantees and demonstrate the efficacy of our proposed scheme to detect and mitigate adversarial attacks. The code for the simulated scenarios are available at https://github.com/SabbirAhmad26/Trust_based_CBF .

We address the problem of safe policy learning in multi-agent safety-critical autonomous systems. In such systems, it is necessary for each agent to meet the safety requirements at all times while also cooperating with other agents to accomplish the task. Toward this end, we propose a safe Hierarchical Multi-Agent Reinforcement Learning (HMARL) approach based on Control Barrier Functions (CBFs). Our proposed hierarchical approach decomposes the overall reinforcement learning problem into two levels –- learning joint cooperative behavior at the higher level and learning safe individual behavior at the lower or agent level conditioned on the high-level policy. Specifically, we propose a skill-based HMARL-CBF algorithm in which the higher-level problem involves learning a joint policy over the skills for all the agents and the lower-level problem involves learning policies to execute the skills safely with CBFs. We validate our approach on challenging environment scenarios whereby a large number of agents have to safely navigate through conflicting road networks. Compared with existing state-of-the-art methods, our approach significantly improves the safety achieving near perfect (within $5\%$) success/safety rate while also improving performance across all the environments.

This paper develops a controller for Connected and Automated Vehicles (CAVs) traversing a single-lane roundabout so that it simultaneously determines (a) the optimal sequence and (b) the associated optimal motion control, jointly minimizing travel time, energy consumption and centrifugal discomfort while providing speed-dependent safety guarantees, as well as satisfying velocity and acceleration constraints. This is achieved by integrating (a) Model Predictive Control (MPC) to enable receding horizon optimization with (b) Control Lyapunov-Barrier Functions (CLBFs) to guarantee convergence to a safe set in finite time, thus providing an extended stability region compared to the use of standard Control Barrier Functions (CBFs). The proposed MPC-CLBF framework overcomes two important limitations of prior work on CAVs over multiple interconnected control zones in a traffic network: infeasibility and myopic control issues, while still providing safety guarantees. Simulations under varying traffic demands and roundabout configurations demonstrate the controller’s effectiveness and stability.

We consider the problem of controlling Connected and Automated Vehicles (CAVs) traveling through a roundabout so as to jointly minimize their travel time, energy consumption, and centrifugal discomfort while providing speed-dependent and lateral roll-over safety guarantees, as well as satisfying velocity and acceleration constraints. We first develop a systematic approach to determine the safety constraints for each CAV dynamically, as it moves through different merging points in the roundabout. We then derive the unconstrained optimal control solution which is subsequently optimally tracked by a real-time controller while guaranteeing that all constraints are always satisfied. Simulation experiments are performed to compare the controller we develop to a baseline of human-driven vehicles, showing its effectiveness under symmetric and asymmetric roundabout configurations, balanced and imbalanced traffic rates, and different sequencing rules for CAVs.

Securing traffic flows in internet of vehicles (IoV) environments for connected and automated vehicles (CAVs) is a critical task as it should be done in real-time to allow vehicles’ controllers engagement on time. In this paper, the security of CAV communication at merging points is studied, the insecure vehicle communication is analysed in terms of the possible security threats and consequences, and security goals are then identified to protect the environment. We present a network topology that improves the availability of the system and propose a high-level design of a vehicle authentication protocol based on public key cryptography to authenticate vehicles. Simulation and analysis of the cryptographic functions are done to choose the best fit for vehicle communication, where Rivest-Shamir-Adleman (RSA)-2048 algorithms provide faster and more efficient computations.

This article is devoted to the development of an optimal speed profile for autonomous vehicles in order to cross a signalized intersection without stopping. The design objective is to achieve both a short travel time and low energy consumption by taking full advantage of the traffic light information based on vehicle-to-infrastructure communication. The eco-driving problem is formulated as an optimal control problem. For the case where the vehicles are in free-flow mode, we derive a real-time on-line analytical solution, distinguishing our method from most existing approaches based on numerical calculations. Under mild assumptions, the optimal eco-driving algorithm is readily extended to cases where the free-flow mode does not apply due to the presence of interfering traffic. Extensive simulations are provided to compare the performance of autonomous vehicles under the proposed speed profile and human-driven vehicles. The results show quantitatively the advantages of the proposed algorithm in terms of energy consumption and travel time.Note to Practitioners—This article is motivated by the requirements for increased safety, increased efficiency in energy consumption, and lower congestion in signalized intersections. We take advantage of the traffic signal phase and timing information based on vehicle to infrastructure communication, and use the information to plan the vehicle’s trajectory to avoid the red traffic signal. An optimal speed profile is developed to achieve a trade-off between minimizing trip time and avoiding unnecessary braking and acceleration which corresponds to minimizing energy consumption. We then show how such a speed profile can be efficiently computed and control the motion of an autonomous vehicle (or serve as an intelligent speed advisory system for human-driven vehicles) leading to a safe, time-efficient, and energy-efficient trip. A video of a real autonomous vehicle test implementing our control algorithm can be found athttps://www.youtube.com/watch?v=x-ao4szeLYo.

We develop an event-driven Receding Horizon Control (RHC) scheme for a Mobility-on-Demand System (MoDS) in a transportation network where vehicles may be shared to pick up and drop off passengers so as to minimize a weighted sum of passenger waiting and traveling times. Viewed as a discrete event system, the event-driven nature of the controller significantly reduces the complexity of the vehicle assignment problem, thus enabling its real-time implementation. Simulation results using actual city maps and real taxi traffic data illustrate the effectiveness of the RH controller in terms of real-time implementation and performance relative to known greedy heuristics.

We derive optimal control policies for a Connected Automated Vehicle (CAV) cooperating with neighboring CAVs in order to implement a lane change maneuver consisting of a longitudinal phase where the CAV properly positions itself relative to the cooperating neighbors and a lateral phase where it safely changes lanes. For the first phase, we optimize the maneuver time subject to safety constraints and subsequently minimize the associated surrogate energy consumption of all cooperating vehicles in this maneuver. For the second phase, we jointly optimize time and energy approximation and provide three different solution methods including a real-time approach based on Control Barrier Functions (CBFs). We prove structural properties of the optimal policies which simplify the solution derivations and, in the case of the longitudinal maneuver, lead to analytical optimal control expressions. The solutions, when they exist, are guaranteed to satisfy safety constraints for all vehicles involved in the maneuver. Simulation results where the controllers are implemented show their effectiveness in terms of significant performance improvements compared to maneuvers performed by human-driven vehicles.

We study the problem of eco-routing for Plug-In Hybrid Electric Vehicles (PHEVs) to minimize the overall energy consumption cost. We propose an algorithm which can simultaneously calculate an energy-optimal route (eco-route) for a PHEV and an optimal power-train control strategy over this route. In order to show the effectiveness of our method in practice, we use a HERE Maps API to apply our algorithms based on traffic data in the city of Boston with more than 110,000 links. Moreover, we validate the performance of our eco-routing algorithm using speed profiles collected from a traffic simulator (SUMO) as input to a high-fidelity energy model to calculate energy consumption costs. Our results show significant energy savings (around 12%) for PHEVs with a near real-time execution time for the algorithm.

This paper studies congestion-aware route-planning policies for intermodal Autonomous Mobility-on-Demand (AMoD) systems, whereby a fleet of autonomous vehicles provides on-demand mobility jointly with public transit under mixed traffic conditions (consisting of AMoD and private vehicles). First, we devise a network flow model to jointly optimize the AMoD routing and rebalancing strategies in a congestion-aware fashion by accounting for the endogenous impact of AMoD flows on travel time. Second, we capture the effect of exogenous traffic stemming from private vehicles adapting to the AMoD flows in a user-centric fashion by leveraging a sequential approach. Since our results are in terms of link flows, we then provide algorithms to retrieve the explicit recommended routes to users. Finally, we showcase our framework with two case-studies considering the transportation sub-networks in Eastern Massachusetts and New York City, respectively. Our results suggest that for high levels of demand, pure AMoD travel can be detrimental due to the additional traffic stemming from its rebalancing flows. However, blending AMoD with public transit, walking and micromobility options can significantly improve the overall system performance by leveraging the high-throughput of public transit combined with the flexibility of walking and micromobility.

The properties of cooperative driving strategies for planning and controlling Connected and Automated Vehicles (CAVs) at intersections range from some that achieve highly efficient coordination performance to others whose implementation is computationally fast. This paper comprehensively compares the performance of four representative strategies in terms of travel time, energy consumption, computation time, and fairness under different conditions, including the geometric configuration of intersections, asymmetry in traffic arrival rates, and the relative magnitude of these rates. Our simulation-based study has led to the following conclusions: 1) The Monte Carlo Tree Search (MCTS)-based strategy achieves the best traffic efficiency and has great performance in fuel consumption; 2) MCTS and Dynamic Resequencing (DR) strategies both perform well in all metrics of interest. If the computation budget is adequate, the MCTS strategy is recommended; otherwise, the DR strategy is preferable; 3) An asymmetric intersection has a noticeable impact on the strategies, whereas the influence of the arrival rates can be neglected. When the geometric shape is asymmetrical, the modified First-In-First-Out (FIFO) strategy significantly outperforms the FIFO strategy and works well when the traffic demand is moderate, but their performances are similar in other situations; and 4) Improving traffic efficiency sometimes comes at the cost of fairness, but the DR and MCTS strategies can be adjusted to realize a better trade-off between various performance metrics by appropriately designing their objective functions.

We address the problem of optimally controlling Connected and Automated Vehicles (CAVs) arriving from four multi-lane roads at a signal-free intersection where they conflict in terms of safely crossing (including turns) with no collision. The objective is to jointly minimize the travel time and energy consumption of each CAV while ensuring safety. This problem was solved in prior work for single-lane roads. A direct extension to multiple lanes on each road is limited by the computational complexity required to obtain an explicit optimal control solution. Instead, we propose a general framework that first converts a multi-lane intersection problem into a decentralized optimal control problem for each CAV with less conservative safety constraints than prior work. We then employ a method combining optimal control and control barrier functions, which has been shown to efficiently track tractable unconstrained optimal CAV trajectories while also guaranteeing the satisfaction of all constraints. Simulation examples are included to show the effectiveness of the proposed framework under symmetric and asymmetric intersection geometries and different CAV sequencing policies.

In order for reinforcement learning techniques to be useful in real-world decision making processes, they must be able to produce robust performance from limited data. Deep policy optimization methods have achieved impressive results on complex tasks, but their real-world adoption remains limited because they often require significant amounts of data to succeed. When combined with small sample sizes, these methods can result in unstable learning due to their reliance on high-dimensional sample-based estimates. In this work, we develop techniques to control the uncertainty introduced by these estimates. We leverage these techniques to propose a deep policy optimization approach designed to produce stable performance even when data is scarce. The resulting algorithm, Uncertainty-Aware Trust Region Policy Optimization, generates robust policy updates that adapt to the level of uncertainty present throughout the learning process.

In real-world decision making tasks, it is critical for data-driven reinforcement learning methods to be both stable and sample efficient. On-policy methods typically generate reliable policy improvement throughout training, while off-policy methods make more efficient use of data through sample reuse. In this work, we combine the theoretically supported stability benefits of on-policy algorithms with the sample efficiency of off-policy algorithms. We develop policy improvement guarantees that are suitable for the off-policy setting, and connect these bounds to the clipping mechanism used in Proximal Policy Optimization. This motivates an off-policy version of the popular algorithm that we call Generalized Proximal Policy Optimization with Sample Reuse. We demonstrate both theoretically and empirically that our algorithm delivers improved performance by effectively balancing the competing goals of stability and sample efficiency.

A docking bike-sharing system (BSS) is modeled as a network representing the underlying transportation network. Mobile agents (replenishment trucks) traverse the network making routing decisions and deciding how and when to replenish station inventories so as to prevent imbalances due to users' one-way rides as well as time-varying demand. This load balancing process entails selecting both optimal routes for the agents and the number of bikes to load/unload at a station with an objective of minimizing a user dissatisfaction metric. First, we establish a time-dependent replenishment fill-to level policy for each station based on the demand rates and station capacities. Next, we focus on developing a receding horizon controller (RHC) to find optimal routes. The controller proceeds in an event-driven manner to determine after each event the optimal routes for a fleet of agents over a finite planning horizon, with the control applied over a shorter action horizon. The proposed controller is applied to a simulated BSS with station and demand parameters taken from the public data sets of Bluebikes, the BSS in Boston, MA, USA, and a cost-benefit analysis is performed on agent shift hours. In order to demonstrate the robustness of the RHC, sensitivity analysis is also performed on the arc travel times and the demand processes.

Efficient flight routing and scheduling play an important role in air traffic flow management, which aims to maximize the utilization of airport and enroute capacities to ensure safety and efficiency of air transportation. In this paper, we first propose a novel discrete-time flow dynamic model for an air traffic network, consisting of airports, waypoints, and air links, upon which we formulate an air flow routing and scheduling problem as an integer linear programming problem. Considering the NP-hard nature of the problem, we present a novel hierarchical flow routing and scheduling approach, where the hierarchical architecture is derived naturally from the network containment relationship, and computation is carried out in a bottom-up manner, which relies on an incremental strategy. On the resulting flow routes and schedules, a heuristic algorithm is carried out to determine flight plans for individual aircrafts. The effectiveness of the proposed hierarchical approach is illustrated by air traffic data in four flight information regions in the association of Southeast Asian nations.

This special issue brings together recent international research on one of the most challenging and multidisciplinary subjects of present and future engineering, architectural, medical, economic, information, and social sciences: the smart city paradigm.

Among the many functions a smart city must support, transportation dominates in terms of resource consumption, strain on the environment, and frustration of its citizens. We study transportation networks under two different routing policies, the commonly assumed selfish user-centric routing policy and a socially optimal system-centric one. We consider a performance metric of efficiency-the Price of Anarchy (PoA)-defined as the ratio of the total travel latency cost under selfish routing over the corresponding quantity under socially optimal routing. We develop a data-driven approach to estimate the PoA, which we subsequently use to conduct a case study using extensive actual traffic data from the Eastern Massachusetts road network. To estimate the PoA, our approach learns from data a complete model of the transportation network, including origin-destination demand and user preferences. We leverage this model to propose possible strategies to reduce the PoA and increase efficiency.

We study the problem of routing for energy-aware battery-powered vehicles (BPVs) in networks with charging nodes. The objective is to minimize the total elapsed time, including travel and recharging time at charging stations, so that the vehicle reaches its destination without running out of energy. Relaxing the homogeneity of charging stations, and here, we investigate the routing problem for BPVs through a network of “inhomogeneous” charging nodes. We study two versions of the problem: the single-vehicle (user-centric) routing problem and the multiple-vehicle (system-centric) routing problem. For the former, we formulate a mixed-integer nonlinear programming (NLP)problem for obtaining an optimal path and charging policy simultaneously. We then reduce its computational complexity by decomposing it into two linear programming problems. For the latter, we use a similar approach by grouping vehicles into “subflows” and formulating the problem at a subflow-level with the inclusion of traffic congestion effects. We also propose an alternative NLP formulation obtaining near-optimal solutions with orders of magnitude reduction in the computation time. We have applied our optimal routing approach to a subnetwork of the eastern Massachusetts transportation network using actual traffic data provided by the Boston Region Metropolitan Planning Organization. Using these data, we estimate cost (congestion) functions and investigate the optimal solutions obtained under different charging station and energy-aware vehicle loads.

Air traffic flow management (ATFM) is an important component in an air traffic control system and has significant effects on the safety and efficiency of air transportation. In this paper, we propose a distributed ATFM strategy to minimize the airport departure and arrival schedule deviations. The scheduling problem is formulated based on an en-route air traffic system model consisting of air routes, waypoints, and airports. A cell transmission flow dynamic model is adopted to describe the system dynamics under safety related constraints, such as the capacities of air routes and airports, and the aircraft speed limits. Our ATFM problem is formulated as an integer quadratic programming problem. To overcome the computational complexity associated with this problem, we first solve a relaxed quadratic programming problem by a distributed approach based on Lagrangian relaxation. Then a heuristic forward-backward propagation algorithm is proposed to obtain the final integer solution. Experimental results demonstrate the effectiveness of the proposed scheduling strategy.

The 12 papers in this special section can be divided into two sets. The first eight papers deal with general DES control problems, while the second set of four papers addresses other particular DES problems such as diagnosability analysis, state estimation, deadlock avoidance and testing.

We consider discrete event systems (DESs) involving tasks with dependability requirements in the form of real-time constraints. We seek to control their processing times so as to satisfy these constraints while also minimizing a given cost function. When tasks are processed by a single resource, it has been shown that there are structural properties of the optimal state trajectory for this problem that lead to the critical task decomposition algorithm (CTDA) with a time complexity of O(N2). For a DES with multiple resources, we consider a multilayer network where each layer contains multiple nodes, each node may have multiple inputs and multiple outputs, and tasks are processed so that the real-time constraints apply on an end-to-end basis. Extending earlier results (where each layer contained a single node), we derive structural properties of the optimal solution that lead to the idea of introducing “virtual” deadlines at each node (except for the last layer) and decouple nodes so that the CTDA for single-node problems can be used. We prove that an appropriately constructed sequence of solutions of these simpler problems converges to the global optimum of the original problem and hence obtain an efficient scalable multilayer virtual deadline algorithm (MLVDA). We illustrate the efficiency of the MLVDA through numerical examples.

We propose a novel “smart parking” system for an urban environment. The system assigns and reserves an optimal parking space based on the driver's cost function that combines proximity to destination and parking cost. Our approach solves a mixed-integer linear programming (MILP) problem at each decision point defined in a time-driven sequence. The solution of each MILP is an optimal allocation based on current state information and is updated at the next decision point with a guarantee that there is no resource reservation conflict and that no driver is ever assigned a resource with a cost function higher than this driver's current cost function value. Based on simulation results, compared with uncontrolled parking processes or state-of-the-art guidance-based systems, our system reduces the average time to find a parking space and the parking cost, whereas the overall parking capacity is more efficiently utilized. We also describe full implementation in a garage to test this system, where a new light system scheme is proposed to guarantee user reservations.

We present a new way to solve the “lot-sizing” problem viewed as a stochastic noncooperative resource contention game. We develop a Stochastic Flow Model (SFM) for polling systems with non-negligible changeover times enabling us to formulate lot sizing as an optimization problem without imposing constraints on the distributional characteristics of the random processes in the system. Using Infinitesimal Perturbation Analysis (IPA) methods, we derive gradient estimators of the performance metrics of interests with respect to the lot-size parameters and prove they are unbiased. We then derive an online gradient-based algorithm for obtaining optimal lot sizes from both a system-centric and user-centric perspective. Uncharacteristically for such cases, there is no gap between the two solutions in the two-class case for which we have obtained explicit numerical results. We derive a proof of this phenomenon for a deterministic version of the problem, suggesting that lot-sizing-like scheduling policies in resource contention problems have a natural property of balancing certain user-centric and system-centric performance metrics.

Idle listening is a major source of energy waste in wireless sensor networks. It can be reduced through Low-Power Listening (LPL) techniques in which a node is allowed to sleep for a significant amount of time. In contrast to conventional fixed sleep time policies, we introduce a novel dynamic sleep time control approach that further reduces control packet energy waste by utilizing known data traffic statistics. We propose two distinct approaches to dynamically compute the sleep time, depending on the objectives and constraints of the network. The first approach provides a dynamic sleep time policy that guarantees a specified average delay at the sender node resulting from packets waiting for the end of a sleep interval at the receiver. The second approach determines the optimal policy that minimizes total energy consumed. In the case where data traffic statistics are unknown, we propose an adaptive learning algorithm to estimate them online and develop corresponding sleep time computation algorithms. Simulation results are included to illustrate the use of dynamic sleep time control and to demonstrate how it dominates fixed sleep time methods. An implementation of our approach on a commercial sensor node supports the computational feasibility of the proposed approach.

Dynamic voltage scaling is used in energy-limited systems as a means of conserving energy and prolonging their life. We consider a setting in which the tasks performed by such a system are nonpreemptive and aperiodic. Our objective is to control the processing rate over different tasks so as to minimize energy subject to hard real-time processing constraints. Under any given task scheduling policy, we prove that the optimal solution to the offline version of the problem can be efficiently obtained by exploiting the structure of optimal sample paths, leading to a new dynamic voltage scaling algorithm termed the critical task decomposition algorithm (CTDA). The efficiency of the algorithm rests on the existence of a set of critical tasks that decompose the optimal sample path into decoupled segments within which optimal processing times are easily determined. The algorithm is readily extended to an online version of the problem as well. Its worst-case complexity of both offline and online problems is O(N2)

In deploying a wireless sensor network with a given number of nodes, a placement policy is required to minimize the power consumption needed for communication. This issue is addressed by formulating a non-linear optimization problem. To avoid combinatorial complexity, we propose an incremental self-deployment algorithm by adding nodes one-at-a-time into the network in the most energy-efficient way identified. This scheme, which achieves possibly suboptimal performance, is tested in a simulation environment and its effectiveness is discussed.

Hybrid systems combine time-driven and event-driven dynamics. This is a natural framework for manufacturing processes: The physical characteristics of production parts undergo changes at various operations described by time-driven models, while the timing control of operations is described by event-driven models. Accordingly, in the framework we propose, manufactured parts are characterized by physical states (e.g. temperature, geometry) subject to time-driven dynamics and by temporal states (e.g., operation start and stop times) subject to event-driven dynamics. We first provide a tutorial introduction to this hybrid system framework and associated optimal control problems through a single-stage manufacturing process model. We then show how the structure of the problem can be exploited to decompose what is a hard nonsmooth, nonconvex optimization problem into a collection of simpler problems. Next, we present extensions to multistage manufacturing processes for which we develop solution algorithms that make use of Bezier approximation techniques. Emphasis is given to the issue of deriving solutions through efficient algorithms, and some explicit numerical results are included.

We address the problem of dynamically assigning the time-slots of a transmission frame to the various classes of transmitters of a packet radio network. We assume that packets are transmitted in a fixed-length frame and employ a discrete optimization scheme to construct the frame slot assignments in order to minimize the mean packet delay. Several simulation results are also included.

The authors study the effect of increasing buffer capacities on the performance of queuing networks that use probabilistic or state-dependent routing. The approach is to establish strong stochastic ordering relations on several performance measures using sample path arguments. In particular, it is proved that the throughput is monotonically increasing with respect to an overall capacity vector in networks with exponential service times, or deterministic service times and synchronous transmission. However, in networks with deterministic service times and asynchronous transmission this property may not hold, as seen through a counterexample. A simple retransmission algorithm is proposed to overcome this problem. Finally, the monotonicity property is also shown to hold in tandem networks with exponential servers where blocked customers are retransmitted rather than rejected.>

Efficient techniques for estimating performance measures in communication networks in a steady-state or transient setting are developed. These techniques may be used in a simulation environment or in connection with real-time observations. For Markov chain models, the recently proposed standard clock approach is extended, and a class of real-time algorithms for simultaneously generating multiple sample paths under different parameter sets is presented. Attention is focused on the link crash time estimation problem, where a 'crash' is defined as the first time a buffer overflows, given some initial conditions. An algorithm for estimating crash times under various traffic shocks is derived, where all estimates are obtained in parallel to an actual network's normal operation. An algorithm for crash time estimation of a G/D/1 link model is also derived using a different (perturbation-analysis-based) approach. Finally, extensive simulation results are provided to validate the proposed algorithms and compare them to brute-force simulation.>

A procedure is presented for estimating online marginal packet delays through links with respect to link flows without making the standard assumptions (exponentially distributed packet lengths, Poisson arrival processes). This procedure is based on a technique known as perturbation analysis. No knowledge of network parameters (arrival rates, link capacities) is required. This is used in the context of a minimum delay distributed routing algorithm for real-time implementation. Experimental results are included to investigate the effect of the algorithm step-size and observation period parameters, demonstrate the adaptivity of the approach, and compare it to well-known analytical approximation.>

The authors address the problem of flow control and routing of real-time traffic in a network, where messages must arrive at their destination within given deadlines if they are not to be considered lost. Performance in this case is measured in terms of the probability of losing a message. For the case of n parallel links, the problem is formulated as one of optimal flow allocation and solved under general conditions. It is shown that for a FCFS (first-come first-served) service discipline an admission policy rejecting messages before link assignment is optimal when the load exceeds a critical value. Thus, the authors take advantage of the fact that if some messages will exceed their deadlines anyway, it is beneficial not to admit them in the first place. An efficient algorithm for explicitly solving the problem is presented and specific examples are analyzed. The authors also discuss the applicability of online algorithms for this problem when modeling assumptions cannot be made.>

The basic problem of constructing a perturbed sample path (given a parameter perturbation) from information contained in a nominal sample path is considered. Two conditions, observability and constructability, which have to be satisfied for this to be feasible are identified. One approach for accomplishing this task is to develop an augmented system model which captures both nominal and perturbed system behaviour. For the case of systems with Markov properties, an explicit methodology is presented for constructing such models. It is also shown that by an observability transformation it is generally possible to satisfy constructability conditions allowing the performance of a perturbed discrete event system to be estimated by observing only a nominal sample path. In practice, a variety of techniques may be used to accomplish this goal, depending on issues such as parameter value availability and convergence speed of various performance sensitivity, estimates.>

A procedure is presented for estimating online marginal packet delays through links with respect to link flows without making such assumptions, based on perturbation analysis. No knowledge of network parameters is required (arrival rates, link capacities). This is used in the context of a minimum-delay distributed routing algorithm for real-time implementation. The effect of the algorithm step-size and observation period parameters is investigated experimentally. Results demonstrate the adaptivity of the approach. It is seen to compare favourably to well-known analytical approximations.>

An analysis is provided of queuing models in virtual route networks for which a pacing window flow control mechanism is used. An input queue is introduced to describe the waiting system where messages prevented from entering the network are stored in first-come, first-served manner. Both finite and infinite capacity are considered. The model leads to a Markovian queuing system, which is fully solved by matrix-geometric methods. The analytical results show that the optimal window size which maximizes the power criterion including the admission delay is nearly twice the number of hops (nodes of the network) for the model with infinite input-queue capacity. This rule of thumb also applies to the finite-capacity model with certain restrictions. Simulations are presented to verify the analytical results.>

Perturbation analysis (PA) is a technique for estimating performance sensitivities of queuing networks from direct observation of a single stochastic realization. It is used here to address such problems for communication networks. For a G/G/1 link model, it is shown that efficient PA algorithms can be used to estimate online the marginal delay of messages due to incoming flow perturbations. This information is used in a minimum-delay distribution algorithm to optimize routing. PA algorithms are extended to estimate throughput and mean delay sensitivities with respect to link capacities, including blocking phenomena due to finite queues. A window-flow-control model is considered, and experimental results of PA estimates for throughput sensitivities are provided. these estimates are seen to be accurate under heavy-load conditions, but, in general, enhanced PA techniques are required to incorporate more-complicated dynamic flow control and routing policies.>