Abstract

We have developed a new traffic measuring tool and applied it to the real-time simulation of a network. It monitors IP traffic on an ATM link and continuously transfers the length and timestamp of each IP packet to a post-processing system. The post-processing system receives the data, estimates the cell's arrival epoch at the transmission queue of the ATM link, and simulates the queueing behavior on-line if conditions differ from those of the actual system. The measuring tool and real-time simulation rep resent a new approach to traffic engineering. A new estimation problem, the arrival sequence estimation, is shown and some algorithms are proposed and evaluated. Document type: Part of book or chapter of book

Abstract

Air transport delays have increased during the past decade both in Europe and US. The main reasons have been continuously growing air transport demand, constrained capacity of the system infrastructure, and disruption of services caused by bad weather, failures of the infrastructure components, facilities and equipment, and industrial action of the aviation staff. Growing demand combined with constrained infrastructure capacity and frequently disrupted by a bad weather have been identified as the most frequent causes of congestion and delays at large airports. Potential remedies have shown to be improvement of utilisation of the existing infrastructure capacity by introducing technological and operational innovations, physical expansion of this capacity, and management of access to the scarce infrastructure capacity. The first option has shown to have the very limited effect. In many cases, the second option has been impossible to be implemented due to the various political and environmental constraints in terms of land take in both the airport airside and landside area. The solution of management of access to the existing scarce infrastructure capacity (i.e., ?demand management) has recently been considered as an additional viable option to relief the congestion problem. This paper deals with modelling of management of access to a congested airport by using congestion charging. The complexity of setting up a relevant congestion charge (toll) based on the system delays imposed by an additional aircraft on itself and on the others during peak-periods has been particularly elaborated. For such a purpose, queuing model of a congested airport, as an essential tool for estimating the aircraft delays, particularly in cases of changes of the airport capacity caused by disruptions, is developed. The existing theory of congestion pricing is upgraded by an explicit introduction of the differences between particular customers - the aircraft - requesting service during peaks in terms of the arrival time, type (seat capacity, operational cost), type of flight (short, medium, long-haul), and actual number of passengers on board. These all are also the most important factors expected to influence a tool, which, if consequently applied, is expected to change in line with changes of these factors. This also illustrates controversy and complexity of implementing such tool, the process, which is under consideration (i.e., in a rudimentary phase) at some airports in the U.S. and Europe. KEY WORDS: air transport, airport, queuing theory, congestion pricing Document type: Part of book or chapter of book

Abstract

The purpose of this tutorial presentation is to introduce G-Networks, or Gelenbe Networks, which are product form queueing networks which include normal or positive customers, as well as negative customers which destroy other customers, and triggers which displace other customers from one queue to another. We derive the balance equations for these models in the context of multiple customer classes, show the product form results, and exhibit the traffic equations which - in this case, contrary to BCMP and Jackson networks - are non-linear. This leads to interesting issues of existence and uniqueness of the steady-state solution. Gelenbe Network can be used to model large scale computer systems and networks in which signaling functions represented by negative customers and triggers are used to achieve flow and congestion control. Document type: Part of book or chapter of book

Abstract

Network convergence and new applications running on end-hosts result in increasingly variable and unpredictable traffic patterns. By providing origin-destination pairs with several possible paths, load-balancing has proved itself an excellent tool to face this uncertainty. Formally, load-balancing is defined in terms of a convex link cost function of its load, where the objective is to minimize the total cost. Typically, the link queueing delay is used as this cost since it measures its congestion. Over-simplistic models are used to calculate it, which have been observed to result in suboptimal resource usage and total delay. In this paper we investigate the possibility of learning the delay function from measurements, thus converging to the actual minimum. A novel regression method is used to make the estimation, restricting the assumptions to the minimum (e.g. delay should increase with load). The framework is relatively simple to implement, and we discuss some possible variants. Document type: Part of book or chapter of book

Abstract

This paper considers a congested bottleneck. A fast lane reserves a more than proportional share of capacity to a designated group of travellers. Travellers are otherwise identical and other travellers can use the reserved capacity when it would otherwise be idle. The paper shows that such a fast lane is always Pareto improving under Nash equilibrium in arrival times at the bottleneck and inelastic demand. It can replicate the arrival schedule and queueing outcomes of a toll that optimally charges a constant toll during part of the demand peak. Within some bounds, the fast lane scheme is still welfare improving when demand is elastic. Document type: Book

Abstract

This paper addresses the requirement for a congestion control mechanism, in order to efficiently handle paging traffic over cellular networks. The standard simultaneous paging approach can easily result in congestion, for relatively small values of the offered load. Instead of differentiating paging capacity based on the incoming load, this approach is more oriented towards a limited-resource system. Considering that a paging channel usually experiences high and low utilization periods, it is proposed to differentiate the paging mechanism according to the processed load. Given medium or even mild overload conditions, several forms of sequential paging substantially decrease blocking probabilities, while presenting good delay behavior. Based on a queueing analysis, we are able to quantitatively estimate potential improvements, and point out the basic points of such an adaptive scheme. Document type: Part of book or chapter of book

Abstract

Most prior work on congestion in datagram systems focuses on buffer management. We find it illuminating to consider the case of a packet switch with infinite storage. Such a packet switch can never run out of buffers. It can, however, still become congested. The meaning of congestion in an infinite-storage system is explored. We demonstrate the unexpected result that a datagram network with infinite storage, first-in, first-out queueing, at least two packet switches, and a finite packet lifetime will, under overload, drop all packets. By attacking the problem of congestion for the infinite-storage case, we discover new solutions applicable to switches with finite storage. Document type: Report

Abstract

Acknowledgement (ACK) filtering has been proposed as a technique to alleviate the congestion at the input of a slow channel located on the reverse path of a TCP connection. Old ACKs waiting at the input of the slow channel are erased when new ACKs are to be queued. In the literature the case of one-ACK per connection at a time has been studied. In this paper we show that this is too aggressive for short transfers where ACKs arrive in bursts due to the slow start phase, and where the TCP source needs to receive the maximum number of ACKs to increase fast its window. We study first static filtering where a certain ACK queue length is allowed. We show analytically how this length needs to be chosen. We present then some algorithms that adapt the filtering of ACKs as a function of the slow channel utilization rather than the ACK queue length. These algorithms provide a good compromise between reducing the ACK queueing delay and passing a large number of ACKs that guarantee a fast window increase. Copyright © 2003 John Wiley & Sons, Ltd. Document type: Report

Abstract

The assessment of uninterrupted traffic flow is traditionally based on empirical methods. We develop some analytic queueing models based on traffic counts and we model the behavior of traffic flows as a function of some of the most relevant determinants. These analytic models allow for parameterized experiments, which pave the way towards our research objectives: assessing what-if scenarios and sensitivity analysis for traffic management, congestion control, traffic design and the environmental impact of road traffic (e.g. emission models). The impact of some crucial modelling parameters is studied in detail and links with the broader research objectives are given. We illustrate our results for a highway, based on counted traffic flows in Flanders.

Abstract

We present an algorithmic method for analyzing networks of intersections with static signaling, with as primary example a line network that allows traffic flow over several intersections in one main direction. The method decomposes the network into separate intersections and treats each intersection in isolation using an extension of the fixed-cycle traffic-light (FCTL) queue. The network effects are modeled by matching the output process of one intersection with the input process of the next (downstream) intersection. This network analysis provides insight into wave phenomena due to vehicles experiencing progressive cascades of green lights and sheds light on platoon forming in case of imperfections. Our algorithm is shown to match results from extensive discrete-event simulations and can also be applied to more complex network structures.