A feedback fluid queue with two congestion control thresholds

Feedback fluid queues play an important role in modeling congestion control mechanisms for packet networks. In this paper we present and analyze a fluid queue with a feedback-based traffic rate adaptation scheme which uses two thresholds. The higher threshold B ₁ is used to signal the beginning of congestion while the lower threshold B ₂ signals the end of congestion. These two parameters together allow to make the trade-off between maximizing throughput performance and minimizing delay. The difference between the two thresholds helps to control the amount of feedback signals sent to the traffic source. In our model the input source can behave like either of two Markov fluid processes. The first applies as long as the upper threshold B ₁ has not been hit from below. As soon as that happens, the traffic source adapts and switches to the second process, until B ₂ (smaller than B ₁) is hit from above. We analyze the model by setting up the Kolmogorov forward equations, then solving the corresponding balance equations using a spectral expansion, and finally identifying sufficient constraints to solve for the unknowns in the solution. In particular, our analysis yields expressions for the stationary distribution of the buffer occupancy, the buffer delay distribution, and the throughput.     

The uniqueness property for networks with several origin–destination pairs

We consider congestion games on networks with nonatomic users and user-specific costs. We are interested in the uniqueness property defined by Milchtaich (2005) as the uniqueness of equilibrium flows for all assignments of strictly increasing cost functions. He settled the case with two-terminal networks. As a corollary of his result, it is possible to prove that some other networks have the uniqueness property as well by adding common fictitious origin and destination. In the present work, we find a necessary condition for networks with several origin–destination pairs to have the uniqueness property in terms of excluded minors or subgraphs. As a key result, we characterize completely bidirectional rings for which the uniqueness property holds: it holds precisely for nine networks and those obtained from them by elementary operations. For other bidirectional rings, we exhibit affine cost functions yielding to two distinct equilibrium flows. Related results are also proven. For instance, we characterize networks having the uniqueness property for any choice of origin–destination pairs.     

Macroscopic traffic models: Shifting from densities to “Celerities”

The advent of techniques to measure velocities of “GPS equipped vehicles” using satellite technology, replacing the density of the road traffic sensors, motivates and justifies the revision of conceptual, mathematical algorithms and software based models. This paper summarizes studies on the traffic evolutions achieving the minimum of a congestion function controlled “macroscopic traffic velocities” called “celerities” instead of founding traffic regulation on the measures of traffic densities. The flux valued function is the Fenchel transform of the fundamental diagram and is a convex decreasing function. We use the properties of capture basins investigated in viability theory, specifically a Lax-Hopf formula characterizing them and the “Max-Plus” morphism of capture basins for deriving the statements proved in this paper. Traffic conditions involve as well boundary conditions or conditions on trajectories inside the domain.     

A network-consistent time-dependent travel time layer for routing optimization problems

In the vehicle routing literature, there is an increasing focus on time-dependent routing problems, where the time (or cost) to travel between any pair of nodes (customers, depots) depends on the departure time. The aim of such algorithms is to be able to take recurring congestion into account when planning logistics operations. To test algorithms for time-dependent routing problems, time-dependent problem data is necessary. This data usually comes in the form of three-dimensional travel time matrices that add the departure time as an extra dimension. However, most currently available time-dependent travel time matrices are not network-consistent, i.e., the travel times are not correlated both in time and in space. This stands in contrast to the behavior of real life congestion, which generally follows a specific pattern, appearing in specific areas and then affecting all travel times to and from those areas. As a result of the lack of available network-consistent travel time matrices, it is difficult to develop algorithms that are able to take this special structure of the travel time data into account.     

Random queues and risk averse users

We analyze Nash equilibrium in time of use of a congested facility. Users are risk averse with general concave utility. Queues are subject to varying degrees of random sorting, ranging from strict queue priority to a completely random queue. We define the key “no residual queue” property, which holds when there is no queue at the time the last user arrives at the queue, and prove that this property holds in equilibrium under all queueing regimes considered. The no residual queue property leads to simple results concerning the equilibrium utility of users and the timing of the queue.     

Driver choice compared to controlled diversion for a freeway double on-ramp in the framework of three-phase traffic theory

Two diversion schemes that apportion demand between two on-ramps to reduce congestion and improve throughput on a freeway are analyzed. In the first scheme, drivers choose to merge or to divert to a downstream on-ramp based on information about average travel times for the two routes: (1) merge and travel on the freeway or (2) divert and travel on a surface street with merging downstream. The flow, rate of merging at the ramps, and the travel times oscillate strongly, but irregularly, due to delayed feedback. In the second scheme, diversion is controlled by the average mainline velocities just upstream of the on-ramps. Driver choice is not involved. If the average upstream velocity on the mainline drops below a predetermined value (20 m/s) vehicles are diverted to the downstream ramp. When the average mainline velocity downstream becomes too low, diversion is no longer permitted. The resultant oscillations in this scheme are nearly periodic. The period is dominated by the response time of the mainline to interruption of merging rather than delayed feedback, which contributes only a minor component linear in the distance separating the on-ramps. In general the second scheme produces more effective congestion reduction and greater throughput. Also the travel times for on-ramp drivers are less than that obtained by drivers who attempt to minimize their own travel times (first scheme). The simulations are done using the Kerner-Klenov stochastic three-phase theory of traffic [B.S. Kerner, S.L. Klenov, Phys. Rev. E 68 (2003) 036130].     

Towards a physics of Internet traffic in a geographic network

A set of equations from a biased random walk are shown to describe the time-based Gaussian distributions of Internet traffic relative to the Earth’s time zones. The Internet is an example of a more general physical problem dealing with motion near the speed of light relative to different time frames of reference. The second order differential equation (DE) takes the form of ‘time diffusion’ near the speed of light or alternatively considered as a complex variable with real time and imaginary longitudinal components. Congestion waves are generated by peak global traffic from different time zones following the Earth’s revolution. The DE is divided into space and time operators for discussion and each component solution, including constants, is illustrated using data from a global network compiled by the Stanford Linear Accelerator Centre (SLAC). Indices of global and regional phase congestion for the monitoring sites are calculated from standardised regressions from the Earth’s rotation. There is also a J-curve limit to transferring information by the Internet and this is expressed as an inequality underpinned by the speed of light with examples from US and European traffic. The research returns to an often little known theme of Isaac Newton’s: mixing physics with geography. In our case, the equations define trajectories of information packets travelling near the speed of light, navigating within networks and between longitudes, relative to the Earth’s rotation.     

Cone dominance and efficiency in DEA

This paper incorporates cones on virtual multipliers of inputs and outputs into DEA analysis. Cone DEA models are developed to generalize the dual of the BCC models as well as congestion models. Input-output data and/or numbers of DMUs for BCC models are inadequate to capture many aspects where judgments, expert opinions, and other external information should be taken into analysis. Cone DEA models, on the other hand, offer improved definitions of efficiency over general cone and polyhedral cone structures. The relationships between cone models and BCC models as well as those between cone models and congestion models are discussed in the development. Two numerical examples are provided to illustrate our findings.